Research on Collision-Free Grey Box Fuzzing Method

Abstract:

Grey-box fuzzing technology has been proved to be an efficient and practical vulnerability mining technology. It is widely used in the field of vulnerability mining, and many high-risk vulnerabilities are found through grey-box fuzzing. American Fuzzy Lop(AFL) is a classic representative of grey-box fuzzing and many subsequent grey-box fuzzing are improved on the basis of AFL according to different conditions but AFL still faces certain issues.AFL uses random numbers to represent instrumentation points when performing instrumentation on target program, the random numbers of the two instrumentation points are used to perform the XOR operation in the testing process, and the result is used to represent an edge.This method can lead to HASH collision problems when performing edge statistics, which decreases the probability of discovering new edges and affects AFL''s vulnerability mining efficiency, especially for larger code sizes..In this paper, by improving the way of assembly-level instrumentation, the basic block-sensitive instrumentation is changed to branchsensitive instrumentation, so that the control flow graph of the program is changed into a binary tree form, and non-random numbers are used to mark each instrumentation point, which is relatively well solved the problem of HASH collision. Experiments show that the propsosed method is effective, and since the improvement is transparent to the upper layer, it can be applied to various AFL-based grey-box fuzzing tools, thereby improving the efficiency of the fuzzing test.