# Constructing More Complete Control Flow Graphs Utilizing Directed Gray-Box Fuzzing
## 1 Introduction
CGF is the most prevalent fuzzing scheme, which guides test case generation with the coverage information and aims to generate test cases which can achieve the maximum code coverage. CGF uses lightweight instrumentation to gain coverage information during runtime. Test cases exercising new path are added to the seed pool, and new test cases are generated by mutating the inputs in the seed pool. AFL is the state-of-the-art coverage-based gray-box fuzzer. It and its extensions have shown high practicability and scalability in vulnerability detection. [PERSON] et al. [26] used CGF for the first time in CFG construction and resolved a certain of indirect jumps. Nevertheless, the purpose of CGF is to improve the coverage of the whole program, not the coverage of indirect jumps. The approach spends a lot of resources to test the code unrelated to indirect jumps. Therefore, it cannot exercise indirect jumps efficiently, which resulting in the constructed CFG is not enough completeness. In summary, the hybrid analysis is a promising approach to construct more complete and precise CFGs. How to generate test cases that exercise more indirect jumps is the key of hybrid approaches. In the state-of-the-art approach to constructing CFGs, the test case generation still faces the following problems. * **Undirected. ** In order to resolve indirect jumps, the existing approaches use CGF to generate test cases. CGF seeks to increase the coverage of a seed tests for entire analyzed program rather than indirect jumps. However, stressing code unrelated to indirect jumps is a waste of resources in constructing CFGs. Therefore, CGF is considered to be undirected and unable to resolve indirect jumps efficiently in CFG construction. * **Unsustainable. ** The existing CGF uses coverage information obtained during runtime to guide test case generation. Many previous work showed that CGF always reaches a \"stuck\" state because it cannot obtain new information in the later stage. In the state, testing is unable to generate test cases to cover new code and to exercise new indirect jumps. In this paper, we propose a novel hybrid approach combining dynamic and static analysis to resolve indirect jumps and construct more complete CFGs for C/C++ programs. The approach is motivated by the observation that only a few jumps in programs are indirect, and directed testing of indirect jumps code may resolve more indirect jumps than CGF used in existing approaches. Instead of CGF, our key insight is to use _directed gray-box fuzzing (DGF)_ to efficiently generate test cases that exercise indirect jumps. DGF is an improvement of traditional gray-box fuzzing proposed by [PERSON] et al. [28]. Its main idea is to focus on interesting parts of code, rather than to spend a lot of time on undirected exploration of the whole program like coverage-based fuzzing. Previous studies [28; 29; 30; 31; 32; 33; 34] have shown that DGF has good practicability in the vulnerability detection. When testing large-scale programs, it can generate test cases to exercise the given targets more effectively than the coverage-based fuzzing. More specifically, we first use static analysis to resolve direct jumps and construct static inter-procedural CFGs. Then, taking indirect jump locations as targets, DGF is used to generate test cases that can exercise as many indirect jumps as possible. We run the analyzed program with the generated test cases and resolve the indirect jump targets. Finally, the results of static and dynamic analysis are combined to construct the CFG with indirect control-flow transitions. Our other observation is that the combined CFGs contains new structure information of the program, which can be used to further optimize the DGF-based test case generation. Therefore, we propose an _iterative feedback mechanism_ to continuously optimize the input generation. The CFG constructed through multiple iterations is taken as the final output.