# Not All Seeds Are Important: Fuzzing Guided by Untouched Edges
## 4 Design of UntouchFuzz
### Seed Scheduling Based on Untouched Edges  
In the preceding Section 4.2, we introduced the method for obtaining untouched edge information. In this section, we delve into seed scheduling based on the collected untouched edges. Similar to AFL, we maintain an array, '_untouch_top_rated_', with a size of MAP_SIZE to store the most favored seed for each untouched edge. We also employ a greedy algorithm, specifically the minimum covering set algorithm [34], to generate an optimal seed set that contains all currently untouched edges. Algorithm 3 describes the seed scheduling algorithm based on untouched edges. Initially, in line 1, the algorithm feeds the newly added seed, denoted as's', to the instrumented program '\(P^{\prime}\)' with untouched edges. Subsequently, it acquires the edge coverage bitmap and the untouched edge bitmap of that seed. Following this, in lines 2-27, the algorithm iterates through each index value in the bitmap. ```
Input: New seed \(s\), program \(P^{\prime}\) instrumented by Algorithm 1, untouch_top\({}_{rated}\) Output: A favored seed set \(trace\_bits,untouch\_bits\gets execute(P^{\prime},s)\) for\(i=0\to MAP\_SIZE\)do if\(trace\_bits[i]\)then if\(untouch\_bits[i]\)then untouch_bits[i] = 0 // handle cases when executing in loops
6 end if if\(virgin\_untouch[i]\)then virgin_untouch[i] = 255 // the edge is explored
7 end if
8 end if
9
10 end if
11 if\(untouch\_bits[i]\&\&\(virgin\_untouch[i]\
eq 255\)then virgin_untouch[i] = 1 // The edge is not explored by other seeds
12 end if
13 if\(virgin\_untouch[i]=255\)then untouch_top_rated[i] \(\gets NULL\) continue
14 end if
15 if\(untouch\_bits[i]\
eq NULL\)then if\(untouch\_top_rated[i]\)then fav_factor \(\gets s^{\prime}\ execution\ time\times s^{\prime}\ file\) size if\(fav\_factor>untouch\_top_{rated}[i]\) execution time \(\times\) its file sizethen continue
16 end if
17
18 end if
19
20 end if
21\(\text{untouch\_top}_{rated}[i]=s\)
22 end if
23
24 end if
25
26 end if
27
28 return\(coverMinSet(untouch\_top_{rated})\)
```  
**Algorithm 3** Seed scheduling based on untouched edges  
Specifically, in lines 3-10, the algorithm first checks whether the edge has been both marked as a touched edge and an untouched edge in the two bitmaps. If this condition is true, it suggests that the edge is likely in a loop structure. Due to the repeated edges covered in loops, it is possible that edges untouched in a previous iteration of the loop are now covered in the current iteration. To mitigate this effect, the algorithm sets the value of the untouched edge bitmap corresponding to this edge's index to 0. The algorithm also maintains a global array called '\(virgin\_untouch\)'. The indices of this array correspond to edge IDs, and the array values indicate the status of the respective untouched edges: 0 denotes an untouched edge that has not been covered by the execution path of any seed, 1 denotes that a seed's execution path includes this untouched edge, and 255 denotes an untouched edge that has been covered by the execution path of another seed, i.e., it has been \"explored\". If the current edge is covered by seed's', and the corresponding value in the '\(virgin\_untouch\)' array is not 0, the algorithm updates the value to 255. Moving on to lines 11-13, if the edge is an untouched edge for the current seed's' and has not been \"explored\" by other seeds in history, the algorithm updates the value in the _'virgin_untouch'_ array to 1. In lines 14-17, if the corresponding _'virgin_untouch'_ value for this edge is 255, indicating that the edge is no longer untouched, the algorithm sets the _'untouch_top_rated'_ value for this edge to NULL. The _'untouch_top_rated'_ maintains the best seed for each untouched edge. In lines 18-26 of the algorithm, the current seed s is compared with the metrics of the best seed for this untouched edge. We continue to use AFL's default metrics, which is the seed's execution speed multiplied by its file size.