# Effective Seed Scheduling for Directed Fuzzing with Function Call Sequence Complexity Estimation
## 3 System Overview
### Dynamic Switch Between Two Stages  
Although the purpose of DGF is to reach the targets as fast as possible, DGF still needs enough coverage exploration to avoid becoming stuck in a local optimum. For example, AFLGo adopts a user-defined time budget in advance to split the exploration stage and exploitation stage. However, strong domain knowledge is required for users to find suitable time budgets for different programs. To address this issue, we propose dynamically switching between the exploration and exploitation stages according to the execution status of instrumented functions. Specifically, during fuzzing, SEZZ maintains all instrumented functions as a global set. In the exploit stage, when all reached seeds in \(\mathbb{P}_{R^{*}}\) have been exploited adequately, SEZZ switches to the exploration stage. Whether a reached seed has been exploited adequately is decided according to the efficiency of edge finding on each function executed by the seed. Formally, whether an input \(I\) can hit an edge \(E\) (denoted as \(edgeHit(I,E)\)) or not can be defined as \(edgeHit(I,E)=\{1,\ E\in\zeta(I);\ 0,\ E\
otin\zeta(I)\}\), where \(\zeta(I)\) are all basic blocks in the execution trace of \(I\). During fuzzing, SEZZ records the number of edges in which each instrumented function \(F\) has been hit. Formally, the edge hit count as a function is  
\[numEdgeHit(F,\mathbb{P})=\sum_{I\in\mathbb{I}_{\mathbb{P}},E\in F}edgeHit(I,E) \tag{5}\]  
where \(\mathbb{I}_{\mathbb{P}}\) are all the inputs produced by the seed pool \(\mathbb{P}\). In addition to counting the number of hits on edges within an instrumented function, we also need the number of times the function is executed. Similarly, whether a function \(F\) executed by an input \(I\) (denoted as \(funcExec(I,F)\)) can be defined as \(funcExec(I,F)=\{1,\ F\in\eta(I);\ 0,\ F\
otin\eta(I)\}\), where \(\eta(I)\) consists of an instrumented function call sequence in the execution trace of \(I\). During fuzzing, SEZZ also records the number of times the instrumented function \(F\) has been executed. Formally, the hit count of a function is  
\[numFuncExec(F,\mathbb{P})=\sum_{I\in\mathbb{I}_{\mathbb{P}}}funcExec(I,F) \tag{6}\]  
where \(\mathbb{I}_{\mathbb{P}}\) are all inputs produced by the seed pool \(\mathbb{P}\). Now, we can define the efficiency of edge finding in a function as  
\[\Theta(F,\mathbb{P})=\frac{numEdgeHit(F,\mathbb{P})}{numFuncExec(F,\mathbb{P})} \tag{7}\]  
A reached seed \(S\) from the reached seed pool \(\mathbb{P}_{R^{*}}\) is considered to be exploited adequately when \(\Theta(F^{*},\mathbb{P}_{R^{*}})\geq\Theta(F^{*},\mathbb{P}_{R})\), where \(F^{*}\) is a function from the reached seeds' executed functions, \(\mathbb{P}_{R^{*}}\) is the reached seeds pool, and \(\mathbb{P}_{R}\) is the reaching seeds pool. As for switching from the exploration stage to the exploitation stage, if SEZZ discovers a newly reached seed during the exploration stage, it will switch to the exploitation stage. Moreover, the proposed scheduling strategy narrows the search space for DGF to expose the vulnerability in the target code. Here, we can theoretically demonstrate the effectiveness of the proposed methods compared with other fuzzers. Proof. : Let \(A\) and \(B\) denote two seeds that are reachable for the target vulnerability but not reached, \(C(A)\) and \(C(B)\) denote the complexity of two seeds to the target code, \(D(A)\) and \(D(B)\) denote the distance of two seeds to the target code, \(S(A)\) and \(S(B)\) denote the search space of two seeds to the target code, \(SEZZ\) denotes the proposed scheduling strategy, and \(\
eg SEZZ\) denotes another distance-based strategy. The goal is to prove the proposed method can select the seed with smaller search space to fuzz while other methods cannot, which means \(S(A)<S(B)\iff SEZZ(A,B)=A\) and \(\exists S(A)<S(B)\implies\
eg SEZZ(A,B)=B\) are true.