# Effective Seed Scheduling for Directed Fuzzing with Function Call Sequence Complexity Estimation
## 2 Background and Related Work
### Motivating Example  
Suppose that we are trying to use DGF (e.g., with AFLGo [16] or Hawkeye [7]) to reproduce CVE-2016-4491. Figure 1 shows a code snippet crafted from the CVE; the call graph of the code snippet; and four function execution traces of seeds A, B, A*, and B*. The presented code snippet displays the complete function call chain from the program's _main()_ entry point to the target function _d_print_mod_list_, which appears at the bottom of the snippet containing the vulnerable code responsible for the CVE. In the call graph, the notation of X:Y in each node means that X is the serial number of the function (highlighted in green within the presented code snippet) and Y is the distance of the function towards the target (the minimum number of edges from the current node to the target node, originally defined in AFLGo). For example, the first node with notation of 1:7 means the function textitmain and it can reach the target site function _d_print_mod_list_ by traversing at least seven edges. For the execution traces of four seeds in the figure, the executed functions are marked with a dark green background, and the executed edges are represented with dashed lines. For clarity, we use the number of edges between a function and the shortest path to the target site as its distance value. In AFLGo and Hawkeye, harmonic means are used to balance the distance between multiple target sites. In this paper, we focus on improving the seed evaluation method, so we use a naive approach to calculate the function distance in this example for simplicity.  
After configuring the target function _d_print_mod_list_, we initiate the directed fuzzing campaign. Under the shortest-distance-based scheduling policy, DGF progressively approximates the target function. After a certain period, the directed grey-box fuzzer has found two seeds A and B, and their execution traces are shown in Figure 1. Now, we need to calculate the distance of each seed to decide which one should be prioritized during scheduling. Following the rule of the scheduler in DGF, e.g., with AFLGo and Hawkeye, where the distance of a seed is the arithmetic mean of the distances of all the functions on its execution trace, the prioritization is always the seed with the shortest distance. With the distances of seeds A and B being \(\frac{7+6+5+4+3}{5}=5\) and \(\frac{7+6+5+4+5+4+3}{7}\approx 4.86\), it seems seed B should be preferred based on these distances. However, in reality, functions 6 and 7 have hundreds of lines of code containing additional complex branch conditions, which means it is more time-consuming for the fuzzer to execute seed B than seed A, meaning that selecting seed B to fuzz is likely slower to reach target function 13 than selecting seed A. As a result, seed B is not a good choice if we consider the function sequence complexity.  
In addition, after a certain period, the descendant seeds A* and B* of seeds A and B have reached the respective target sites, while the bug is still not triggered. In this case, the fuzzer, e.g., AFLGo and Hawkeye, does not know which seed is better to fuzz for vulnerability exposure because the seeds have arrived at the destination, which means the distance guidance mechanism has failed. The discussion about the above-mentioned seeds shows that only using the distance between nodes to guide DGF is not sound enough; the function complexity in the execution trace should also be considered. Similarly, other distance-guided directed grey-box fuzzers inevitably encounter these same fundamental limitations because their seed-scheduling strategies have a shared reliance on distance heuristics.  
In this paper, we propose a quantitative measure for function call sequence complexity in the context of directed grey-box fuzzing with selective instrumentation. To address the limitations of distance-based seed scheduling, we introduce a two-stage seed-scheduling strategy that adaptively combines function call sequence complexity metrics with distance guidance.