# Not All Seeds Are Important: Fuzzing Guided by Untouched Edges
## 4 Design of UntouchFuzz
### Untouched Edges Tracking  
As mentioned in Section 2.1.2, AFL employs a lightweight instrumentation technique to track program edge coverage. In essence, AFL's instrumentation assigns a random ID to each basic block within the target program's CFG. During program execution, the instrumentation codes calculate the corresponding edge index based on Equation (1) and use this index to update the coverage bitmap. To ensure minimal impact on program execution speed, AFL utilizes a lightweight XOR operation for computing coverage indices. Similarly, the instrumentation codes responsible for gathering untouched edge information should also be lightweight to minimize disruption to program execution. We introduce our instrumentation approach with a practical example. Figure 4 provides a snippet of branches within the program's CFG. The hexadecimal values in green boxes represent random IDs allocated by the AFL instrumentation for each basic block. According to Equation (1), the edge index for the transition from basic block BB1 to BB2 is calculated as \((0 xabcd\gg 1)\oplus 0x1234=0x47d2\), while the edge index for the transition from basic block BB1 to BB3 is calculated as \((0 xabcd\gg 1)\oplus 0x5678=0x039e\). Suppose a particular seed triggers a transition from basic block BB1 to BB2, leaving the transition from BB1 to BB3 unexplored. In this scenario, we label edge \(0x039e\) as an untouched edge within the execution path of the seed. A straightforward method for capturing untouched edges is to insert instrumentation codes within basic block BB2. Such codes update a byte of untouched edge bitmap by using \(0x039e\) as a static index pre-allocated during compilation. This approach works efficiently when a basic block has only one predecessor, but confusion arises when a basic block has multiple incoming edges. Consider the seed's execution path: BB0\(\rightarrow\)BB1\(\rightarrow\)BB2\(\rightarrow\)BB1. Basic block BB1 has two incoming edges: \(0x693\) from BB0 and \(0 xa2d7\) from BB2. The corresponding unexplored edges are \(0 xb6a5\) and \(0 xb2a1\). Employing the aforementioned instrumentation codes, distinguishing between these two untouched edges becomes a challenging endeavor. Figure 3: Overview of UntouchFuzz. Upon analyzing the above example, it becomes evident that static pre-allocation of untouched edge IDs is impractical when a basic block has multiple predecessors. To address this challenge, we propose a dynamic method for obtaining untouched edge IDs based on the properties of XOR operations. Specifically, we employ a global variable named \"_afl_bb_ids_\" to maintain the XOR value of the IDs of two basic blocks at branch transition point. When a transition between basic blocks occurs, we perform an XOR operation on the ID of the transitioned-to basic block with \"_afl_bb_ids_\" to retrieve the ID of the other unexplored basic block. Furthermore, we define the equation for calculating untouched edge IDs as follows:  
\[edge_{untouch}=(prev_{bb}\gg 1)\oplus(\_afl\_bb\_ids\oplus cur_{bb}) \tag{2}\]  
\[where,\_afl\_bb\_ids=cur_{bb}\oplus untouch_{bb} \tag{3}\]  
Illustrated with the control flow graph in Figure 4, consider the branch transition point within basic block BB1, which leads to two transitions to basic blocks BB2 and BB3. At BB1, we update the value of \"_afl_bb_ids_\" by performing an XOR operation on the IDs of BB2 and BB3, resulting in \(0x1234\oplus 0x5678=0x444c\). When a transition occurs from basic block BB1 to BB2, we can recover the ID of the unexplored basic block BB3 by using \"_afl_bb_ids_\": \"_afl_bb_ids_\(\oplus\)\(ID_{BB2}=0x444c\oplus 0x1234=0x5678\)\". Subsequently, we calculate the untouched edge ID between BB1 and BB3 using Equation (1): \"(\(0 xabcd\gg 1)\oplus 0x5678=0x039e\)\". The calculated value is then utilized to update the bitmap information for the untouched edges. Algorithm 2 delineates the process of instrumenting untouched edges.