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

Fuzzing Test Case Generation Method Based on Depth-first Search

作　　者：李毅豪 洪征 林培鸿 LI Yi-hao;HONG Zheng;LIN Pei-hong(Command and Control Engineering College,Army Engineering University of PLA,Nanjing 210000,China)

机构地区：[1]中国人民解放军陆军工程大学指挥控制工程学院,南京210000

出　　处：《计算机科学》2021年第12期85-93,共9页Computer Science

基　　金：国家重点研发计划(2017YFB0802900)。

摘　　要：模糊测试是挖掘网络协议漏洞的重要方法之一。现有的模糊测试方法存在覆盖路径不完全、效率低下等问题。为了解决这些问题,文中提出了基于深度优先搜索的模糊测试用例生成方法,该方法将状态机转换成有向无回路图,以获得状态迁移路径,并通过提高测试用例在发送报文中的占比来提升模糊测试效率。该方法主要包括合并状态迁移、消除循环路径、搜索状态迁移路径、标记重复状态迁移和基于测试用例引导的模糊测试5个阶段。在合并状态迁移阶段,将首尾状态相同的状态迁移进行合并。在消除循环路径阶段,根据深度优先搜索判断图中的循环,并通过删除边将状态机转换成有向无回路图。在搜索状态迁移路径阶段,搜索有向无回路图从初始状态到终止状态的全路径,并对原状态机图使用Floyd算法补充被去除的边构造测试路径,以确保充分测试状态机中的每一个状态迁移。在标记重复状态迁移阶段,对重复状态迁移进行标记,避免对重复的状态迁移进行反复测试,以缩减测试的冗余。在基于测试用例引导的模糊测试阶段,生成针对状态迁移的测试用例,并将测试用例均匀分发到重复的状态迁移上,其中的部分测试用例能够起到引导状态迁移的作用,对被测目标进行模糊测试。实验结果表明,所提方法能够取得更高的有效测试用例比例。Fuzzing test is an important method to exploit network protocol vulnerability.Existing fuzzing test methods have some problems such as incomplete path coverage and low efficiency.To solve these problems,this paper proposes a depth-first search based fuzzing test case sgeneration method.The method transforms the state machine into a directed acyclic graph to obtain the state transition paths,and increases the proportion of test cases in the testing messages to improve the fuzzing efficiency.The method includes five stages:merging state transition,eliminating loops,searching state transition paths,marking the same state transitions,and test case guidance based fuzzing test.Firstly,the state transitions which have the same start states and end states are merged.Secondly,according to the depth-first search,the loops in the graph are found,and the state machine is converted into a directed acyclic graph by deleting the edges of the loops.Thirdly,the directed acyclic graph is analyzed for the full path from the initial state to the end state,and the original state machine graph is supplemented with the removed edges using Floyd algorithm to construct the complete test paths,so as to ensure that each state transition in the state machine can be fully tested.Fourthly,repeated state transitions are marked to avoid repeated test of similar state transitions and reduce testing redundancy.Finally,test cases for state transitions are generated,and test cases which may guide the state transition are distributed evenly over the repetitive state transitions to carry out fuzzing test on the target.Experimental results show that the proposed method can achieve higher proportion of valid test cases.

关 键 词：模糊测试 漏洞挖掘 有状态协议 协议状态机 深度优先搜索 

分 类 号：TP398.08[自动化与计算机技术—计算机应用技术]