# Constructing More Complete Control Flow Graphs Utilizing Directed Gray-Box Fuzzing
## 4 Methodology
### DGF-Based Test Case Generation
#### 4.2.1 Distance Calculation  
The seed distance calculation is introduced from AFLGo [28], and it can determine the importance of the seed. The calculation is based on the constructed iCFG and consists of the following three steps.  
(1) **Function-level distance on CG**. If a function contains indirect jump instructions, it is taken as target function. The set of all target functions is represented as \(F_{t}\). We use \(d_{f}(f_{i},f_{t})\) to represent the distance between any two functions on CG, i.e., the number of edges on the shortest path between the two functions. The function-level distance determines the distance between an arbitrary function to all target functions. Supposing a function \(f\) and target functions \(F_{t}\) are given, the function-level distance of \(f\), represented as \(d_{f}(f,F_{t})\), is defined as the harmonic mean of the distance between the function \(f\) to all target functions as follows.  
\[d_{f}(f,F_{t})=\begin{cases}+\infty,&R(f,F_{t})=\emptyset\\ \left[\sum_{f_{i}\in R(f,F_{t})}d_{f}(f,f_{t})^{-1}\right]^{-1},&R(f,F_{t}) \
eq\emptyset\end{cases} \tag{1}\]  
where \(R(f,F_{t})\) is the set of functions that are members of \(F_{t}\) and are reachable from \(f\).  
(2) **Basic block-level distance on iCFG**. The basic blocks containing indirect jump instructions are called target basic blocks. The set of all target basic blocks is represents as \(B_{t}\). We use \(d_{b}(b_{i},b_{j})\) to represent distance between any two basic block. In a function, the distance is the number of edges on the shortest path between the two basic blocks on the CFG. The basic block-level distance determines the distance from an arbitrary basic block to target basic blocks, which is represented as \(d_{b}(b_{i},B_{t})\). Based on the function-level distance, the basic block-level distance is calculated as follows.  
\[d_{b}(b_{i},B_{t})=\begin{cases}0,&if\quad b_{i}\in B_{t}\\ \alpha\cdot\min_{b_{i}\in N(f)}(d_{f}(f,F_{t})),&if\quad b_{i}\in T\\ \left[\sum_{t\in T}\left(d_{b}(b_{i},t)+d_{b}(t,B_{t})\right)^{-1}\right]^{-1 },&otherwise\end{cases} \tag{2}\]  
where \(N(f)\) is the set of all basic blocks in function \(f\). \(\alpha\) is a constant that represents the average length of functions in distance calculation. \(T\) represents a set of special basic blocks that we call _transfer basic blocks_. A transfer basic block should satisfy the following conditions: (a) the basic block ends with a call instruction and (b) the target function called by the call instruction can reach the target functions on CG.  
Figure 4: Input generation based on DGF.  
(3) **Seed distance**. Based on the basic block-level distance, the distance from an arbitrary seed \(s\) to the target basic blocks is calculated and represented as \(d(s,B_{t})\). More specifically, the seed distance is defined as the average distance of all basic blocks on the seed execution trace, i.e.,  
\[d(s,B_{t})=\frac{\sum_{b\in\lambda(s)}d_{b}(b,B_{t})}{|\lambda(s)|} \tag{3}\]  
where \(\lambda(s)\) is the set of basic blocks on the execution trace of the seed \(s\).  
An example is taken to describe the basic block-level distance calculation in Figure 5. In the example, \(a\) is the considered basic block and \(f\) is the target block. The gray basic blocks \(b\) and \(d\) are transfer basic blocks. According to the iCFG, there is a reachable path from \(a\) to \(f\), i.e., \(a\to b\to c\to d\to e\to f\). Therefore, the basic-block-level distance from \(a\) to the target block \(f\) is calculated as follows.  
\[d_{b}(a,B_{t})=d_{b}(a,b)+d_{b}(b,B_{t})=d_{b}(a,b)+\alpha\cdot d_{f}(f_{1},f_ {3})=1+\alpha\cdot 2.\]  
The distances of function-level and basic-block-level (steps (1) and (2)) are calculated by static analysis. Only the seed distance calculation (step (3)) needs to be performed at runtime and instrumented into target programs.