# Effective Seed Scheduling for Directed Fuzzing with Function Call Sequence Complexity Estimation
## 1 Introduction  
Fuzzing [1, 2, 3], a widely adopted security testing technique [4, 5], has identified numerous vulnerabilities in real-world programs. Fuzzers automatically explore the input space of a program, aiming to identify specific inputs that may trigger potentially exploitable buggy behaviors. General-purpose fuzzing tools, such as AFL [6], usually use code coverage to guide the program in exploring more code paths, aiming to discover more program errors. However, for scenarios where directed testing is performed for a given code location, such as patch testing [7, 8, 9], crash reproduction [10, 11, 12], or PoC verification [13, 14], a code-coverage-guided fuzzer usually spends excessive resources exploring code paths unrelated to the target location, reducing the efficiency of fuzzing. Directed grey-box fuzzing (DGF) [15] focuses more on specific program statements, with the key being to approach the target code region as quickly as possible, rather than extensively exploring all code regions, and to avoid wasting resources on irrelevant program code. The effectiveness metric of DGF is the duration required for the fuzzer to first trigger the target bug, alsoknown as the time-to-exposure (TTE) [8; 16; 17; 18], rather than the crash quantity or coverage breadth used in the code coverage fuzzer [3; 6; 17]. Though being widely used in crash reproduction and vulnerability validation, one primary problem of prior directed fuzzers is that they often explore a large number of program codes and paths that cannot trigger the crashes. Most existing approaches follow AFLGo's solution and use coverage feedback to explore code areas. Many code areas are irrelevant and unrequired for reaching the target sites. Such code areas are still unnecessarily explored. Prior directed fuzzers utilize the distance metrics based on the control flow graph (CFG) and call graph (CG). The distance metrics do not consider the path conditions, such as control flow and data flow conditions. As a result, executions that cannot trigger the vulnerabilities at the target sites because of unsatisfiable control flow or data flow conditions might still gain short distances and be overly favored. Excessive testing efforts are thus wasted, e.g., Hawkeye and CAFL incorporate call traces into their distance metric designs but they do not utilize these traces to eliminate unnecessary code or paths. An effective approach to mitigate the above-mentioned problem is to determine the specific program code that could reach and trigger the crashes, and then to fuzz these codes. Beacon [8] employs a backward interval analysis to determine the necessary preconditions for reaching the target locations and halts the execution of any processes that do not meet these criteria. SieveFuzz [19], on the other hand, examines the inter-procedural control flow graph (ICFG) to pinpoint the necessary functions for accessing the target locations and ceases the execution once it encounters functions that are not required. SelectFuzz [18] statically identifies the code that is both control- and data-dependent on the target locations. However, they only consider the control flow reachability but fail to consider other conditions for reaching the target sites and triggering the vulnerabilities, e.g., the complexity of the reaching sequence before the target sites. In this article, we estimate the complexity of the reaching sequence before the target sites and conduct a two-stage investigation into the issue of choosing the expected reaching sequence. First, we analyze the properties of the instrumented functions' call graph generated after selective instrumentation. We try to evaluate the complexity of the nodes in the graph, and therefore, the complexity of the sequences in the graph can be evaluated. Second, we consider the entire fuzzing campaign process of DGF and believe that this process can be divided into two parts: one is before reaching the target node, and the other is after reaching the target node.