A Control Flow Graph Optimization Method for Enhancing Fuzz Testing

Abstract

The American Fuzzy Lop (AFL) is a tool that automatically generates random data to expose vulnerabilities in software programs. However, it has some drawbacks, such as the lack of visibility in test case generation and suboptimal allocation of test case variation energy. To address these issues, we propose an enhanced fuzz testing approach based on the Program Control Flow Graph. Firstly, we construct the program control flow graph using a symbolic execution tool. The precise addresses of the assembly instructions are obtained using the IDA Pro reverse engineering tool. Secondly, the control flow graph is then optimized by adjusting for address jumps, and nodes without edges are considered difficult to reach within the program. A set of paths is then extracted by slicing the refined control flow graph, in which paths through these difficult nodes are marked with sensitive signals. Thirdly, the constraint solver then generates inputs capable of traversing each path within the set. Finally, these inputs are used as the initial seed for fuzz testing. In the testing process, the sensitive signal paths obtained during symbol execution serve as the benchmark for the fuzz testing energy allocation mechanism, and the seed passing through the sensitive signal path is endowed with higher variation energy to guide the seed variation and make the fuzz testing explore in the deeper level of the program. The experimental results show that the enhanced fuzz testing method based on the program control flow graph is more efficient than the original fuzz testing. On the Cyber Grand Challenge (CGC) test-set, this method finds 2.7 times more unique crashes compared to the original fuzz testing. In addition, our approach uncovers two more unique crashes than standard fuzz testing in two real-world programs.

Keywords

• Control flow graph
• fuzz testing
• symbolic solution
• AFL