基于深度优先搜索的模糊测试用例生成方法

模糊测试是挖掘网络协议漏洞的重要方法之一.现有的模糊测试方法存在覆盖路径不完全、效率低下等问题.为了解决这些问题,文中提出了基于深度优先搜索的模糊测试用例生成方法,该方法将状态机转换成有向无回路图,以获得状态迁移路径,并通过提高测试用例在发送报文中的占比来提升模糊测试效率.该方法主要包括合并状态迁移、消除循环路径、搜索状态迁移路径、标记重复状态迁移和基于测试用例引导的模糊测试5个阶段.在合并状态迁移阶段,将首尾状态相同的状态迁移进行合并.在消除循环路径阶段,根据深度优先搜索判断图中的循环,并通过删除边将状态机转换成有向无回路图.在搜索状态迁移路径阶段,搜索有向无回路图从初始状态到终止状态的全路径,并对原状态机图使用Floyd算法补充被去除的边构造测试路径,以确保充分测试状态机中的每一个状态迁移.在标记重复状态迁移阶段,对重复状态迁移进行标记,避免对重复的状态迁移进行反复测试,以缩减测试的冗余.在基于测试用例引导的模糊测试阶段,生成针对状态迁移的测试用例,并将测试用例均匀分发到重复的状态迁移上,其中的部分测试用例能够起到引导状态迁移的作用,对被测目标进行模糊测试.实验结果表明,所提方法能够取得更高的有效测试用例比例.

Fuzzing Test Case Generation Method Based on Depth-first Search