# Constructing More Complete Control Flow Graphs Utilizing Directed Gray-Box Fuzzing
## 1 Introduction  
A control flow graph (CFG) represents all paths of a program that might be traversed during execution and is a fundamental data structure in program analysis. In a CFG, nodes represent basic blocks of instructions and directed edges represent jumps in the control flow. The CFG laws foundation for many other program analysis techniques, such as data flow analysis [1, 2], taint analysis [3, 4], and symbolic execution [5, 6, 7]. The CFG is also widely applied in program verification [8, 9], malware detection [10, 11, 12, 13], code similarity analysis[14, 15, 16], and software vulnerability detection [17, 18]. Therefore, utilizing appropriate approaches to construct complete and precise CFG is necessary. However, _indirect jumps_ bring challenges to constructing complete CFGs [19]. In C/C++ programs, a program's jump can be categorized as direct or indirect. A direct jump has a statically specified target which points to a single location in the program, whereas an indirect branch has a dynamically specified target which may point to any number of locations in the program. Indirect jumps are commonly used to realize dynamic program behaviors by implementing common programming constructs, such as virtual function calls and calls through function pointers. Although indirect jumps are common and useful, due to their dynamic nature, it is usually difficult to resolve the target of an indirect jump through static analysis. This leads to inherent challenges in constructing complete CFGs. Current solutions for CFG construction fall into three categories: static analysis, dynamic analysis, and hybrid analysis. Static techniques [20, 21, 22] do not need to concreteexecute of target programs, and only need to analyze the code to understand the program structure. The approaches can traverse the whole program code and has the advantages of high coverage and low time cost. Therefore, static analysis tools for constructing CFGs, such as IDA Pro [20] for binary code and LLVM [22] for source code, are widely applied in various program analyses. However, static techniques have poor completeness because it is difficult to resolve indirect jump relations statically. Dynamic techniques execute programs on a set of test cases and extract the control flow information from the execution traces. The approaches can resolve a certain of indirect jumps and discover precise control flow. However, the completeness of the CFG constructed by the approaches depends on the capability of the test cases to cover indirect jumps. In order to improve the coverage of test cases, [PERSON] et al. [23] proposed to systematically force a program's execution to explore both branches of each conditional. However, because forced execution is a heavyweight analysis technique, the approach still has poor coverage in analysis of large-scale programs. In recent years, hybrid techniques [24; 25; 26; 27] have been proposed to resolve indirect jumps that cannot be handled by pure static analyses, and to improve the completeness of CFGs. [PERSON] et al. [24] combined dynamic and static techniques to construct CFGs. They computed an underapproximation of the transition relation by resolving indirect jumps with a set of seed tests, and augmenting the computed relation with statically computed direct jumps. In their approach, the completeness of CFGs still depends on the coverage of the seed test cases. However, in their work, they only generated test cases randomly and did not study how to generate effective test cases. [PERSON] et al. [26] proposed using _coverage-based gray-box fuzzing_ (_CGF_) to generate test cases to handle indirect jumps. Gray-box fuzzing is a scalable and practical approach to software testing. It is widely applied to vulnerability detection and test case generation. Existing gray-box fuzzers usually use an evolutionary algorithm to generate test cases based on the feedback information from the execution.