# Constructing More Complete Control Flow Graphs Utilizing Directed Gray-Box Fuzzing
## 3 Overview  
In order to solve the aforementioned limitations in existing approaches, we propose a DGF-based hybrid approach to constructing CFGs. The approach aims to efficiently generate test cases that exercise indirect jumps and to construct more complete CFGs. Figure 2 shows the overview of our proposed approach. The input is a program to be analyzed, which can be either source code or binary code. The output is the constructed inter-procedural control flow graph (iCFG) with indirect jumps. Our approach consists of three major components: static iCFG construction, DGF-based test case generation, and indirect jump monitoring. **Static iCFG construction**. First, we use a static analysis to obtain the call graph (CG) of the program and CFGs of each function. There are some popular static tools that can be used to construct CG and functions' CFGs, such as LLVM [22] for source code and IDA Pro [20] for binary code. Then, we combine the CG and CFGs to construct the iCFG. We present more details in Section 4.1. **DGF-based test case generation**. The main function of this component is to generate test cases that can exercise indirect jumps. First, a static analysis is used to search all indirect jump locations in the target program. Then, the indirect jump locations are taken as the targets to implement a distance-based DGF. DGF casts the reachability of target locations as optimization problem and minimizes the distance of the generated test cases to the targets. We collect the test cases that execute unique paths during the DGF and add them to the test case queue, which will be used in the following dynamic execution. The details of the test case generation are given in Section 4.2. **Indirect jump monitoring**. The purpose of this component is to execute the target program using the generated test cases and to resolve the target addresses of indirect jumps through runtime monitoring. First, we instrument the target program at each of indirect jump locations. When an indirect jump is triggered, the instrumented program can record its target address. Then, all test cases generated by DGF are provided to the target program in turn. We can obtain all indirect jump relations triggered during the execution. More details of the component are shown in Section 4.3. By combining the results of static iCFG construction and indirect jump monitoring, an iCFG with indirect jumps can be constructed. Figure 1: Example of indirect jumps. (**a**) is the source code of the example. (**b**) is the control flow graph (CFG) of the example. We observe that a new iCFG is constructed with the test cases generated by DGF. However, the distance calculation in DGF in turn depends on the iCFG. The new iCFG contains the new structure information of the program, which can be used to further direct the test case generation. Therefore, we propose an _iterative feedback mechanism_ in CFG construction. The mechanism makes full use of the new information and further improves the completeness of CFGs. We present more details of the iterative feedback mechanism in Section 4.4. The workflow of our approach is shown in Algorithm 1. At the beginning of the algorithm, a static analysis is used to analyze the target program \(p\) and to construct a static iCFG. Then, we search the locations of all indirect jump instructions in \(p\), and instrument each of them to obtain the instrumented program \(p^{\prime}\). Next, the loop with iterative feedback starts at line 5. At the beginning of feedback loop, iCFG is set as static iCFG. Taking the locations of indirect jumps as the targets, DGF calculates the test case distance according to iCFG and generates test cases which are added to the test cases queue. Then, all instances in the test case queue are used to execute the instrumented program \(p^{\prime}\), and the indirect jump relations are resolved through runtime monitoring. We update the iCFG by combining the new indirect jump edges with the original iCFG.