Fuzzing Test Case Generation Method Based on Depth-first Search

Abstract

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.

Keywords

• fuzzing test|vulnerability discovery|stateful protocol|protocol state machine|depth first search