Reinforcement Learning-based Hierarchical Seed
Scheduling for Greybox Fuzzing
Jinghan Wang, Chengyu Song, Heng Yin
University of California, Riversidejwang131@ucr.edu, {csong, heng}@cs.ucr.edu

Abstract—Coverage metrics play an essential role in greybox
fuzzing. Recent work has shown that fine-grained coverage
metrics could allow a fuzzer to detect bugs that cannot be coveredby traditional edge coverage. However, fine-grained coverage
metrics will also select more seeds, which cannot be efficiently
scheduled by existing algorithms. This work addresses this problem by introducing a new concept of multi-level coverage metricand the corresponding reinforcement-learning-based hierarchicalscheduler. Evaluation of our prototype on DARPA CGC showedthat our approach outperforms A FL and A FL FAST significantly: it
can detect 20% more bugs, achieve higher coverage on 83 out of
180 challenges, and achieve the same coverage on 60 challenges.
More importantly, it can detect the same number of bugs andachieve the same coverage faster. On FuzzBench, our approachachieves higher coverage than A FL ++ (Qemu) on 10 out of 20
projects.

I.

I NTRODUCTION

Greybox fuzzing is a state-of-the-art testing technique thathas been widely adopted by the industry and has successfully
found tens of thousands of vulnerabilities in widely usedsoftware. For example, the OSS-Fuzz [20] project has foundmore than 10,000 bugs in popular open-sourced projects like
OpenSSL since its launch in December 2016.
As shown in Figure 1, greybox fuzzing can be modeled
as a genetic process where new inputs are generated throughmutation and crossover/splice. The generated inputs are selected according to a fitness function. Selected inputs are thenadded back to the seed pool for future mutation. Unlike natural
evolution, due to the limited processing capability, only a few
inputs from the seed pool will be scheduled to generate thenext batch of inputs. For example, a single fuzzer instance canonly schedule one seed at a time.
The most common fitness function used by off-the-shelf
fuzzers like American Fuzzy Lop (A FL) [55] is edge coverage,i.e., inputs that cover new branch(es) will be added to theseed pool, as its goal is to achieve higher edge coverage ofthe code. While most fuzzers are coverage-guided (i.e., use
new coverage as the fitness function), recent research has
shown that the genetic process can also be used to discover

Network and Distributed Systems Security (NDSS) Symposium 2021
21-24 February 2021, San Diego, CA, USA
ISBN 1-891562-61-4
https://dx.doi.org/10.14722/ndss.2021.24486
www.ndss-symposium.org

Instrumented
ProgramSeed
Selection
Seed Mutation

Test Caseinteresting!

Fitness
Function
New
Seed

Seed
Seed
Scheduling

Seed PoolFig. 1: Overview of greybox fuzzing
a diversity of program properties by using a variety of fitness
functions [26], [32], [34].
An important property of a fitness function (e.g., a coverage
metric) is its ability to preserve intermediate waypoints [32].
To better illustrate this, consider flipping a magic number
check a = 0xdeadbeef as an example. If a fuzzer only
considers edge coverage, then the probability of generating
the correct a with random mutations is 232 . However, if the
fuzzer can preserve important waypoints, e.g., by breaking
the 32-bit magic number into four 8-bit number [25], thensolving this checking will be much more efficient since theanswer can be generated from a sequence as 0xef, 0xbeef,
0xadbeef, and 0xdeadbeef. This check can also be solved
faster by understanding distances between current value of aand the target value [12]–[14], [18], [42]. More importantly,
recent research has shown that many program states cannot bereached without saving critical waypoints [30], [45].
Wang et al. [45] formalize the ability to preserve intermediate waypoints as the sensitivity of a coverage metric.
Conceptually, a more sensitive metric would lead to moreprogram states (e.g., code coverage). However, the empiricalevaluation of [45] shows that this is not always the case. The
reason is that, a more sensitive coverage metric will selectmore seeds, which could cause seed explosion and exceed thefuzzer’s ability to schedule. As a result, many seeds may neverbe scheduled or be scheduled without enough time/power tomake a breakthrough [9].
In this work, we aim to address the seed explosion problem with a hierarchical scheduler. Specifically, fuzzing canbe modeled as a multi-armed bandit (MAB) problem [49],where the scheduler needs to balance between exploration andexploitation. With a more sensitive coverage metric like branch
distance, exploitation can be considered as focusing on solving
a hard branch (e.g., magic number check), and exploration can“quality” of a generated test case. Test cases with good quality
will then be saved as a new seed into the seed pool. This step
allows a greybox to gradually evolve towards a target (e.g.,more coverage). The effectiveness and efficiency of greybox
fuzzing depend on the following factors.

be considered as exercising an entirely different function. Our
crucial observation is that when a coverage metric Cj is moresensitive than Ci , we can use Cj to save all the intermediate
waypoints without losing the ability to discover more program
states; but at the same time, we can use Ci to cluster seeds
into a representative node and schedule at node level to achieve
better exploration. More specifically, the scheduler will choose
a node first, and then choose a seed in that node. Based on
this observation, we propose to organize the seed pool as amulti-level tree where leaf nodes are real seeds and internal
nodes are less sensitive coverage measurements. The closer
a node is to the leaf, the more sensitive the corresponding
coverage measurement is. Then we can utilize the existing
MAB algorithms to further balance between exploitation andexploration.

Algorithm 1: Greybox Fuzzing Algorithm
Input: target program P , set of initial seeds S 0
Output: unique seed set S ∗ ,bug-triggering seed set S v
Data: seed s and test case I
0
1 Function Main(P , S ):
∗
0
2
S ←S
3
Sv ← ∅
4
while true do
5s ← SelectNextSeedToFuzz(S ∗ )6s.power ← AssignPower()
7
while s.power > 0 do
8s.power ← s.power − 1
9I ← MutateSeed(s)10status ← RunAndEval(I)11
if status is Bug then12
S v ← S v ∪ {I}13else if status is NewCovExplored then14
S ∗ ← S ∗ ∪ {I}
15
else
16
continue // drop I
17
end
18
end
19
PayReward(s)20
end
21 EndTo validate our idea, we implemented two prototypes: one
A FL -H IER based on A FL and the other A FL ++-H IER basedon A FL ++. We performed extensive evaluation on the DARPA
Cyber Grand Challenge (CGC) dataset [10] and Google
FuzzBench [21] benchmarks. Compared to A FL FAST [9],A FL -H IER can find more bugs in CGC (77 vs. 61). A FL -H IER
also achieved better coverage in about 83 of 180 challenges
and the same coverage on 60 challenges. More importantly,
A FL -H IER can find the same amount of bugs and achieve thesame coverage faster than A FL FAST. On FuzzBench, A FL ++H IER achieved higher coverage on 10 out of 20 projects thanA FL ++ (Qemu).
Contributions. This paper makes the following contributions:• We propose multi-level coverage metrics that bring anovel approach to incorporate sensitive coverage metrics
in greybox fuzzing.
• We design a hierarchical seed scheduling algorithm tosupport the multi-level coverage metric based on themulti-armed bandits model.
• We implement our approach as an extension to A FL and
A FL ++ and release the source code at https://github.com/
bitsecurerlab/aflplusplus-hier.
• We evaluate our prototypes on DARPA CGC and Google
FuzzBench. The results show that our approach not only
can trigger more bugs and achieve higher code coverage,
but also can achieve the same coverage faster than existing
approaches.
II.

Test case measurement. As a genetic process, the fitness
function of the fuzzer decides what kind of program properties the fuzzer can discover [32]. While fuzzing has beensuccessfully applied to many different domains in recent years
with different fitness functions, the most popular one is stillcode coverage (i.e., a test case that triggers new coverage will
be saved as a new seed). However, coverage measurements
can be diverse. Notably, A FL [55] measures the edge coverageof test cases. More precisely, it maintains a global map where
the hashed value of an edge (i.e., the pair of the current basic
block address and the next basic block address) is used as anindexing key to access the hit_count of the edge, which
records how many times it has been taken so far. The hit counts
are bucketized into small powers of two. After a test casecompletes its execution, the global hit_count map will be
updated according to its edges, and it will be selected as a
new seed if a new edge is found or the hit count of one edge
increases into a new bucket. As we can see, this measurement
does not consider the order of edges and can miss interesting
seeds is the hash of a new edge collides with the hash of analready covered edge [19].

BACKGROUND

A. Greybox Fuzzing
Algorithm 1 illustrates the greybox fuzzing process in moredetail. Given a program to fuzz and a set of initial seeds, thefuzzing process consists of a sequence of loops named rounds.
Each round starts with selecting the next seed for fuzzing fromthe pool according to the scheduling criteria. The scheduled
seed is assigned to a certain amount of power that determines
how many new test cases will be generated in this round.
Next, test cases are generated through (random) mutation andcrossover based on the scheduled seed. Compared to blackbox
and whitebox fuzzing, the most distinctive step of greybox
fuzzing is that, when executing a newly generated input, thefuzzer uses lightweight instrumentations to capture runtime
features and expose them to the fitness function to measure theSeed scheduling criteria. The limited processing capability
makes it essential to prioritize some seeds over others inorder to maximize the coverage. For example, A FL [55]prefers seeds with small sizes and short execution time toachieve a higher fuzzing throughput. Furthermore, it maintains
2

bandit algorithms that perform impressively. Specifically, they
construct a confidence interval to estimate each arm’s true
reward, and select the arm with the highest UCB each time.
Notably, the confidence interval is designed to shrink when thearm with its reward is sampled more. As a result, while thealgorithm tends to select arms with high average rewards, itwill periodically try less explored arms since their estimatedrewards have wider confidence intervals.

a minimum set of seeds that stress all the code coverage
so far, and focus on fuzzing them (i.e., prefers exploitation).
A FL FAST [9] models greybox fuzzing as a Markov chain andprefers seeds exercising paths that are rarely exercised, as
high-frequency paths tend to be covered by invalid test cases.
LIB F UZZER [39] prefers seeds generated later in a fuzzing
campaign. Entropic [7] prefers seeds with higher information
gains.

Take UCB1 [2], which is almost the most fundamental one,as an example. It starts with selecting each arm once to obtainan initial reward. Then atqeach time step, it selects arm a that)maximizes Q(a) + C × log(Nwhere Q(a) is the averagenareward obtained
from
arm
a,
C
is
a
predefined constant that is√
usually set to 2, N is the overall number of selections done
so far, and na is the number of times arm a has been selected.

Seed mutation strategy. The mutation strategy decides how
likely a new test case could trigger new coverage(s) and be
selected as a new seed. Off-the-shelf fuzzers like A FL and
LIB F UZZER use random mutation and crossover. Recent work
aims to improve the likelihood by using data-flow analysis
to identify which input bytes should be mutated [18], [37],[52], by using directed searching [12], [13], [40], [42], and bylearning the best mutation strategies [11], [29].

Seed scheduling can be modeled as a multi-armed bandit
problem where seeds are regarded as arms [49], [54]. However,
to make the fuzzer benefit from this model, such as maximizing
the code coverage, we need to design the reward of schedulinga seed carefully.

Fuzzing throughput. Fuzzing throughput is another criticalfactor that decides how fast a fuzzer can discover new coverage. A FL [55] uses the fork server and persistent mode to
reduce initialization overhead, thus improving the throughput.
Xu et al. [51] proposed new OS primitives to improve fuzzing
throughput further. FirmAFL [57] uses augmented emulation
to speed-up fuzzing firmware. Because high throughput isthe key factor that allows greybox fuzzers to beat whitebox
fuzzers in practice, one must pay special attention to thetrade-off between throughput and the above three factors(coverage measurement, scheduling algorithm, and mutation
strategy). That is, improvements of the above three factors
at the cost of throughput may unexpectedly result in worse
fuzzing performance.

III.

M ULTI -L EVEL C OVERAGE M ETRICS

In this section, we discuss what are multi-level coverage
metrics and why they are useful for greybox fuzzing.
A. Sensitivity of Coverage Metrics
Given a mutation-based greybox fuzzer, a fuzzing campaign starts with a set of initial seeds. As the fuzzing goeson, more seeds are added into the seed pool through mutating
the existing seeds. By tracking the evolution of the seed pool,
we can see how each seed can be traced back to an initial
seed via a mutation chain, in which each seed is generated
from mutating its immediate predecessor. If we consider a bug
triggering test case as the end of a chain and the corresponding
initial seed as the start, those internal seeds between themserve as waypoints that allow the fuzzer to gradually reduce
the search space to find the bug [32].

B. Multi-Armed Bandit Model
The multi-armed bandit model offers a fundamental framework for algorithms that learn optimal resource allocation
policies over time under uncertainty. The term “bandit” comesfrom a gambling scenario where the player faces a row of slot
machines (also known as one-armed bandits) yielding random
payoffs and seeks the best strategy of playing these machines
to gain the highest long-term payoffs.

The coverage metric used by a fuzzer plays a vital rolein creating such chains, from two main aspects. First, if thechain terminates earlier before reaching the bug triggering test
case, then the bug may never be discovered by the fuzzer.
Wang et al. [45] formally model this ability to preserve critical
waypoints in seed chains as the sensitivity of a coverage metric.
For example, consider the maze game in Listing 1, which is
widely used to demonstrate the capability of symbolic execution of exploring program states. In this game, a player needs
to navigate the maze via the pair of (x, y) that determines alocation for each step. In order to win the game, a fuzzer has
to try as many sequences of (x, y) pairs as possible to find theright route from the starting location to the crashing location.
This simple program is very challenging for fuzzers using edge
coverage as the fitness function, because there are only four
branches related to every pair of (x, y), each checking against a
relatively simple condition that can be satisfied quite easily. For
instance, five different inputs: “a,” “u,” “d,” “l,” and “r” areenough to cover all branches/cases of the switch statement.
After this, even if the fuzzer can generate new interesting

In the basic formulation, a multi-armed bandit problem isdefined as a tuple (A, R), where A is a known set of K arms
(or actions) and Ra (r) = P[r|a] is an unknown but fixedprobability distribution over rewards. At each time step t theagent selects an arm at , and observes a reward rt P
∼ Rat . The
T
objective is to maximize the cumulative rewards t=1 rt .
Initially, the agent has no information about which arm is
expected to have the highest reward, so it tries some randomly
and observes the rewards. Then the agent has more information
than before. However, it has to face the trade-off between“exploitation” of the arm that is with the highest expected
reward so far, and “exploration” to obtain more information
about the expected rewards of the other arms so that it does
not miss out on a valuable one by simply not trying it enoughtimes.
Various algorithms are proposed to make the optimal
trade-off between exploitation and exploration of arms. Upper
Confidence Bound (UCB) algorithms [5] are a family of3

c h a r maze [ 7 ] [ 1 1 ] = {"+−+−−−+−−−+" ,3"| ||#| " ,
4
" | | −−+ | | " ,5"| || | |",
6" | +−− | | | " ,
7
"|
|
|",
8
"+−−−−−+−−−+" } ;9 int
x = 1 , y = 1;
10 f o r ( i n t
i = 0 ; i < MAX_STEPS ; i ++) {11
switch ( steps [ i ]) {12
c a s e ’ u ’ : y−−; b r e a k ;13
c a s e ’ d ’ : y ++; b r e a k ;14
c a s e ’ l ’ : x−−; b r e a k ;15
c a s e ’ r ’ : x ++; b r e a k ;16default :17
p r i n t f ( " Bad s t e p ! " ) ; r e t u r n 1 ;18}
19i f ( maze [ y ] [ x ] == ’ # ’ ) {20
p r i n t f ( " You win ! " ) ;21
return 0;
22}23
i f ( maze [ y ] [ x ] ! = ’ ’ ) {24
p r i n t f ( " You l o s e . " ) ;25
return 1;
26}
27 }28 r e t u r n
1;bugs, the empirical results from [45] showed this is notalways the case. For instance, while memory access coverage
would allow a fuzzer to win the maze game (Listing 1), it
did not perform very well on many of the DARPA CGC
challenges. The reason is that, a more sensitive coverage metricwill also create a larger seed pool. As a result, the seedscheduler needs to examine more candidates each time whenchoosing the next seed to fuzz. In addition to the increased
workload of the scheduler, a larger seed pool also increases thedifficulty of seed exploration, i.e., trying as many fresh seeds as
possible. Since the time of a fuzzing campaign is fixed, moreabundant seeds also imply that the average fuzzing time ofeach seed could be decreased, which could negatively affectseed exploitation, i.e., not fuzzing interesting seeds enoughtime to find critical waypoints.

1
2

Overall, a more sensitive coverage metric boosts the capability (i.e., upper bound) of a fuzzer to explore deeper program
states. Nevertheless, in order to effectively utilize its power andmitigate the side effects of the resulting excessive seeds, thecoverage metric and the corresponding seed scheduler should
be carefully crafted to strike a balance between explorationand exploitation.
B. Seed Clustering via Multi-Level Coverage Metrics
The similarity and diversity of seeds, which can be measured in terms of the exercised coverage, drive the seed
exploration and exploitation in a fuzzing campaign. In general,a set of similar seeds gains less information about the program
under test than a set of diverse seeds. When a coverage metricmeasures more fine-grained coverage information (e.g., edge),
it can dim the coarse-grained diversity (e.g., block) among
different seeds. First, it encourages smaller variances between
seeds. Second, it loses the awareness of the potential larger
variance between seeds that can be detected by a more coarsegrained metric. For instance, a metric measuring edge coverage
is unaware of whether two seeds exercise two different setsof basic blocks or the same set of basic blocks but throughdifferent edges. Therefore, it is necessary to illuminate seedsimilarity and diversity when using a more sensitive coverage
metric.

Listing 1: A Simple Maze Game

inputs that indeed advance the program’s state towards thegoal (e.g., “dd“), these inputs will not be selected as newseeds because they do not provide new edge coverage. As aresult, it is extremely hard, if not impossible, for fuzzers that
use the edge coverage to win the game [3].
On the contrary, as we will show in §V-G, if a fuzzer
can measure the different combinations of x and y (e.g., bytracking different memory accesses via ∗(maze + y + x)
at line 10), then reaching the winning point will be mucheasier [3], [45]. Similarly, researchers have also observedthat the orderless of branch coverage and hash collisions cancause a fuzzer to drop critical waypoints hence prevent certain
code/bugs from being discovered [19], [27], [30].

Clustering is a technique commonly used in data analysis
to group a set of similar objects. Objects in the same cluster
are more similar to each other than to those in a different
cluster. Inspired by this technique, we propose to perform seedclustering so that seeds in the same cluster are similar whileseeds in different clusters are more diverse. In other words,
these clusters offer another perspective that allows a scheduler
to zoom in the similarity and diversity among seeds.

The second impact of a coverage metric has on creating
seed chains is the stride between a pair of seeds in a chain.
Specifically, the sensitivity of a coverage metric also determines how likely (i.e., the probability) a newly generated test
case will be saved as a new seed. For instance, it is easier
for a fuzzer that uses edge coverage to discover a new seedthan a fuzzer that uses block coverage. Similarly, as we havediscussed in §I, it is much easier to find a match for an 8bit integer than a 32-bit integer. Böhme et al. [9] model theminimum effort to discover a neighbouring seed as the required
power (i.e., mutations). Based on this modeling, a moresensitive coverage metric requires less power to make progress,
i.e., a shorter stride between two seeds. Although each seed
only carries a small step of progress, the accumulation of them
can narrow the search space faster.

Based on the observation that the sensitivity of most
coverage metrics for greybox fuzzing can be directly compared(i.e., the more sensitive coverage metric can subsume the lesssensitive one), we propose an intuitive way to cluster seeds—
using a coarse-grained coverage measurement to cluster seeds
selected by a fine-grained metric. That is, seeds in the samecluster will have the same coarse-grained coverage measurement. Moreover, we can use more than one level of clustering
to provide more abstraction at the top level and more fidelity
at the bottom level. To this end, the coverage metric should
allow the co-existence of multiple coverage measurements. We
name such a coverage metric a multi-level coverage metric.

While the above discussion seems to suggest that a moresensitive coverage metric would allow fuzzers to detect more4I ∈ I , and produces a set of features that are exercised by itat least once, denoted as M ∈ Γ∗ .

root

MF

MD

MF

... M

ME

ME

ME

... M

MD

MD

MD

MD

E

F

ME

... M

ME

D

Since coverage metric is mainly characterized by the coverage space Γ, it can be simplified with the coverage space.
Some typical coverage metrics are:MF

MD

• CF measures the functions that are exercised by an
execution.
• CB measures the blocks that are exercised by an execution.
• CE measures the edges that are exercised by an execution.

ME

MD

MD

MD

Finally, we give the definition of a multi-level coverage
metric.
Definition III.3. A coverage metric C n : (P × I ) →hΓ∗1 , . . . , Γ∗n i consists of a sequence of coverage metrics
hC1 , . . . , Cn i. It measures the execution of a program P ∈ P
with an input I ∈ I , and produces a sequence of measurements
hM1 , . . . , Mn i.

Fig. 2: A multi-level coverage metric that measures function
coverage at top-level, edge coverage at mid-level, and hamming distance of comparison operands at leaf-level. The root
node is a virtual node only used by the scheduler.
C. Incremental Seed Clustering

A multi-level coverage metric combines multiple metrics at
different levels to assess a seed. As a result, it relies on lowerlevel coverage measurements to preserve minor variancesamong seeds so that there will be more abundant seeds ina chain. This helps to reduce the search space of finding bug
triggering test cases. Meanwhile, it allows a scheduler to use
upper-level measurements to detect major differences among
seeds. Note that when n = 1, it is reduced to a traditional
single level coverage metric.

With the multi-level coverage metric in place, if a test
case is assessed as exercising a new coverage (feature) by
any of the measurements, it will be retained as a new seed
and put in a proper cluster as described in Algorithm 2.
Generally, except for the top-level measurement M1 that
directly classifies all seeds into different clusters, the following
lower-level measurement Mi (i = 2, · · · , n) works on each of
the clusters generated by Mi−1 separately, classifying seeds in
it into smaller sub-clusters, which is named incremental seedclustering.

D. Principles and Examples of Multi-level Coverage Metrics

In more detail, given a multi-level coverage metric asshown in Figure 2, a test case exercising any new function,edge, or distance coverage will be assessed as a new seed.
Then the root node starts the seed clustering. It will find fromits child nodes an existing MF node that covers the samefunctions as the new seed, or create a new MF node if thedesired node does not exist. Next, the seed clustering continues
in a similar way that puts the new seed into a ME node withthe same edge coverage. Finally, a child MD node of the ME
node is selected to save the new seed according to its distancecoverage.

To further illustrate how a multi-level coverage metricworks, we propose some representative examples. We first
discuss some principles for developing an effective multi-level
coverage metric C n ∼ hC1 , . . . , Cn i for fuzzing a program P .
1) Principles: Through the incremental seed clustering, allseeds are put into a hierarchical tree that lays the foundationof our hierarchical seed scheduling algorithm, which will be
described in §IV. However, the scheduling makes sense only
when a node at an upper level can have multiple child nodes
at lower levels. This indicates that the cases where if a set ofseeds are assessed to be with the same coverage measurement
Mi , all following measures Mi+1 , . . . , Mn will also be thesame should be excluded. Motivated by this fundamental
requirement, the main principle is that measurements generated
by a less sensitive metric should always cluster seeds prior
to more sensitive ones. Here, we use the same definition ofsensitivity between two coverage metrics as in [45].

Terms used in the algorithm are defined as follows.
Definition III.1. A coverage space Γ defines the set of
enumerable features we pay attention to that can be coveredby executing a program.
Some typical coverage spaces are:• ΓF is the set of all program functions.
• ΓB is the set of all program blocks.
• ΓE is the set of all program edges. Note that an edge isa transition from one block to the next.

Definition III.4. Given two coverage metrics Ci and Cj , we
say Ci is “more sensitive” than Cj , denoted as Ci s Cj , if

It is worth mentioning that in real-world fuzzers such as
A FL, the coverage information is recorded via well-crafted
hit_count maps. Consequently, the features are signified
by entries of the maps.

(ii) ∃P ∈ P , ∃I1 , I2 ∈ I , Cj (P, I1 ) = Cj (P, I2 ) ∧Ci (P, I1 ) 6= Ci (P, I2 )(i) ∀P ∈ P , ∀I1 , I2 ∈ I , Ci (P, I1 ) = Ci (P, I2 ) →Cj (P, I1 ) = Cj (P, I2 ), andSpecifically, take the multi-level metric in Figure 2 as an
example. Seeds in the same MF clusters must have the samefunction coverage. However, since ME is more sensitive than

Definition III.2. A coverage metric C : (P × I ) → Γ∗measures the execution of a program P ∈ P with an input
5The most important one is the bottom-level metric, whichis the most sensitive one. In this work, we mainly evaluated abottom-level metric called distance metric CD . It traces conditional jumps (i.e., edges) of a program execution, calculates
the hamming distances of the two arguments of the conditions
as covered features, and treats each observed new distance ofa conditional jump as new coverage. Unlike CE or CF that
traces control flow features, CD focuses on data-flow features
and actively accumulates progress made in passing condition
checks for fuzzing.

Algorithm 2: Seed Selection Algorithm
Input: test case I
Output: return a status code indicating whether I
triggers a bug or covers new features
Data: program being fuzzed P ,existing seed set S ∗ ,existing feature set M ∗ ,current working cluster cc,
map from feature sets to sub clusters cc.map,
coverage metric C n ∼ hC1 , . . . , Cn icoverage measurements hM1 , · · · , Mn i
Result: put I in a proper cluster if it is a new seed
1 Function RunAndEval(I):2hM1 , . . . , Mn i ←RunWithInstrument(P, I, C n )3
if bug triggered then4
return Bug
5end
6
M t ← M1 ∪ · · · ∪ Mn
7
if M t ⊆ M ∗ then8
return Known
9
else
10
M∗ ← M∗ ∪ Mt
11
foreach i ∈ {1, . . . , n} do12
next_cc ← cc.map[Mi ]13
if next_cc = N U LL then14
next_cc ← new_cluster()
15
end
16
move I into next_cc
17cc.map[Mi ] ← next_cc
18cc ← next_cc
19
end
20
return NewCovExplored
21
end
22 EndTo understand whether our approach can support different
coverage metrics (fitness functions), we also evaluated anothercoverage metric called memory access metric CA . As thename implies, this metric traces all memory reads and writes,
captures continuous access addresses as array indices, andtreats each new index of a memory access as new coverage. CA
pays attention to data flow features and accumulates progress
made in accessing arrays that might be long. To distinguishmemory accesses that happen at different program locations,the measurement also includes the address of the last branch.
However, since not all basic blocks contain memory accesses,
CA is not directly comparable to CE using sensitivity. However, we observe that CA can generate much more seeds thanCE , so CA comes after CE and its measurement MA stays at
the bottom level.
IV.

H IERARCHICAL S EED S CHEDULINGThis section discusses how to schedule seeds against hierarchical clusters generated by a multi-level coverage metric.
A. Scheduling against A Tree of Seeds
Conceptually, a multi-level coverage metric C n ∼hC1 · · · Cn i organizes coverage measurements (Mi ) and seeds
as a tree, where each node at layer (or depth) i ∈ {1, · · · , n}represents a cluster represented by Mi and its child nodes atlayer i+1 represent sub-clusters represented by Mi+1 . At leaflevel, each node is associated with real seeds. Additionally, atlayer 0 is a virtual root node representing the whole tree. To
schedule a seed, the scheduler needs to seek a path from theroot to a leaf node.

MF , these seeds are likely to have different edge coverage,
resulting in multiple different sub-clusters. However, if we use
ME to cluster seeds prior to MF , since seeds with the sameedge coverage must also have the same function coverage, it is
impossible further to put them into different sub- MF clusters.
As a result, each ME node will have only a single MF node,
making the clustering useless.

Exploration vs Exploitation. The main challenge a seedscheduler faces is the trade-off between seed exploration(trying out other fresh seeds) and exploitation (keep fuzzing
a few interesting seeds to trigger a breakthrough). On the one
hand, fresh seeds that have rarely been fuzzed may lead tosurprisingly new coverage. On the other hand, a few valuable
seeds that have led to significantly more new coverage thanothers in recent rounds encourage to focus on fuzzing them.

As discussed in [45], s is a partial order, so it is possiblethat two metrics are not comparable. To solve this problem,
we propose a weaker principle: given two non-comparable
coverage metrics, we should cluster a seed with the metricthat will select fewer seeds before the one that will select moreseeds.
2) Examples: Following the above principles, we propose
two multi-level coverage metrics as examples. Both examples
use three-level clustering that works well in our evaluation.

Organizing seeds in a tree with hierarchical clusters facilitates a more flexible control over the seed exploration andexploitation. Specifically, fuzzers can focus on a single cluster
in which seeds cover the same functions at the first layer andthen try out many (sub-)clusters with seeds exercising different
edges at the second layer. Alternatively, fuzzers can also try
out seeds exercising different groups of functions, then only
pick seeds covering some specific edges.

The top-level metric in both examples is CF , whichmeasures the function coverage. The middle-level metric isedge coverage CE . Functions invoked are essential runtime
features that are commonly used to characterize an execution,and edge coverage is widely used in fuzzers such as A FL and
LIB F UZZER . Notably CE s CF .
6

In this work, we explore the feasibility of modeling the
fuzzing process as a multi-armed bandit (MAB) problem [49],[54] and using the existing MAB algorithms to balance
between exploitation and exploration. After trying several
different MAB algorithms, we decide to adopt the UCB1
algorithm [2], [5] to schedule seeds, since it works the best
empirically, despite being one of the simplest MAB algorithms.
As illustrated by function SelectNextSeedToFuzz()
in Algorithm 3, starting from the root node, our schedulingalgorithm selects the child node with the highest score, whichis calculated based on the coverage measurements, until reaching the last layer to select among leaf nodes that are associatedwith real seeds. Because all seeds have the same coverageat the leaf level, we scheduling them with round robin forsimplicity.

B. Seed Scoring
How to score seeds directly affect the trade-off between
exploration and exploitation. First, for exploitation, seeds thathave performed well recently should have high scores as they
are expected to make more progress. Second, for exploration,
the scoring system should also consider the uncertainty ofrarely explored seeds. We extended the UCB1 algorithm [2],[5] to achieve a balance between exploitation and exploration.
From a high level, our scoring method considers three aspectsof a seed: (1) its own rareness, (2) easiness to discover new
seeds from this seed, and (3) uncertainty.
In order to discuss this in more detail, let us first definesome terms more formally. First, we define the hit count ofa feature F ∈ Γl at level l as the number of test cases evergenerated that cover the feature.

At the end of each round of fuzzing, nodes along thescheduled path will be rewarded based on how much progress
the current seed has made in this round, e.g., whether there
are new coverage features exercised by all the generated test
cases. In this way, seeds that perform well are expected to haveincreased scores for competing in the following rounds, whileseeds making little progress will be de-prioritized.

Definition IV.1. Let P be the program under fuzzing, I be
the set of all test cases that have been generated so far. The
hit count of a feature F is num_hits[F ] = |{I ∈ I : F ∈Cl (P, I)}|.
As observed in [9], features that are rarely exercised by test
cases deserve more attention because they are not likely to be
exercised by valid inputs. The rareness of a feature describes
how rarely it is hit, which is the inverse of the hit count.

Note that a traditional MAB problem assumes a fixed
number of arms (nodes in our case) so that all arms can get
an estimation of their rewards at the beginning. However, oursetup breaks this assumption since the number of nodes grows
as more and more seeds are generated. To address this issue,
we introduce a rareness score of a node, so that each newnode will have an initial score to differentiate itself from othernew nodes. We will discuss seed scoring in more detail laterin §IV-B.

Definition IV.2. The rareness of a feature F is rareness[F ] =1
num_hits[F ]Before describing how we calculate the reward of a roundof fuzzing, we first define the feature coverage of fuzzing seeds at round t.
Definition IV.3. Let P be the program under fuzzing, Is,t be
the set of test cases generated at round t via fuzzing seed s.
We denote the feature coverage at level Cl , l ∈ {1, · · · , n} asf cov[s, l, t] = {F : F ∈ C(P, I) ∀I ∈ Is,t }It is also worth mentioning that a recent work Ecofuzz [54]proposed using a variant of the adversarial multi-armed bandit(AMAB) model to perform seed scheduling. However, it
can not solve the seed exploration problem caused by moresensitive coverage metrics, as it attempts to explore all existing
seeds at least once. Moreover, we have also experimented with
the EXP3 algorithm that aims to solve the AMAB problem;
but it performed worse than UCB1 in our setup.

Next, we describe how we calculate the reward to theseed just fuzzed after a round of fuzzing. An intuitive way
is to count the number of new features covered as the reward.
However, we quickly noticed that this does not work well. As
the fuzzing campaign goes on, the probability of exercising
new coverage is dramatically decreased, indicating that a seed
can hardly obtain new rewards. Consequently, the mean reward
of seeds may quickly decrease to zero. When we have many
seeds with minor variances near zero, the UCB algorithm
cannot properly prioritize seeds. Moreover, under the common
observation that infrequent coverage features deserve more
exploration than others, seeds that can lead to inputs thatexercise rare features are definitely more valuable, even if they
do not cover new features. Motivated by these observations,
we take the rareness of the rarest feature that is exercised by all
generated inputs as the reward to the schedule seed. Formally,
for a seed s that is fuzzed at round t, its fuzzing reward w.r.t.
coverage metric Cl is

Algorithm 3: Seed Scheduling Algorithm
Input: seed set S
Output: return the seed to fuzz
Data: the tree T with n layers
current working tree node cx
1 Function SelectNextSeedToFuzz(S):2T ← S.tree
3cx ← T.root
4
foreach i ∈ {1, · · · , n} do
5children ← cx.child_nodes
6
cx ← argmaxx∈children Score(x)7end8s ← cx.next_seed()9
return s
10 EndSeedReward(s, l, t) =max(rareness[F ])F ∈f cov[s,l,t]

(1)

11

Based on the seed reward, we compute the reward to a7

exploration. More formally, given a seed a and its parent a0 ,we calculate U (a) as

cluster by propagating seed rewards to clusters scheduled at
upper levels. More formally, let ha1 , . . . , an , an+1 i be thesequence of nodes (in the seed tree) selected at round t, wherean+1 is the seed node for s and ai is coverage measurements
for the corresponding clusters. Since scheduling node al affects
the following scheduling of nodes al+1 , · · · , an at lower
layers, the reward of node al as feedback consists of the seed
reward regarding coverage levels l, l + 1, · · · , n as illustrated
in Equation 2. Note that we use the geometric mean here since
it can handle different scalars of the involved values with ease.

Reward(al , t) =sn−l+1 Ys
U (a) = C ×

SeedReward(s, k, t) (2)Right now, we are able to estimate the expected performance of fuzzing a node using the formula of UCB1 [2], [5].
Formally, the fuzzing performance of a node a is estimated as(3)

Q(a) is the empirical average of fuzzing rewards that aobtains so far, and U (a) is radius of the upper confidence
interval.

N [a,t]−1P
p=0

Q(a, t) =1+w×N [a,t]−1P

log N [a0 ]
N [a]

(5)

The fuzzing performance estimated by Equation 3 basedon fuzzing coverage is limited by what can be observed. This
limitation can impact seeds that have never been scheduled
and seeds that exercise rare features themselves but usuallylead to inputs that exercise high-frequency features (e.g., for a
program with rigorous input syntax checks, random mutations
usually lead to invalid paths, hence lowering the reward).
To mitigate this limitation, when evaluating a seed, we also
consider features that it exercises. Particularly, we calculate therareness of a seed via aggregating the rareness of features thatit covers. More formally, let P be the program under fuzzing,given a seed s, its rareness regarding Ml , l ∈ {1, · · · , n} is

Unlike UCB1 which calculates Q(a) using the arithmetic
mean of the rewards that node a obtains so far, we use theweighted arithmetic mean instead. More specifically, during
the fuzzing, the rareness of a feature is decreasing as it isexercised by more and more test cases. As a result, even thesame fuzzing coverage can lead to different fuzzing rewards
for mutating a seed: the reward of an earlier round might besignificantly higher than that of a later round. To address thisissue, we introduce a discount factor as weight in order tofavor newer rewards rather than older ones. More formally,
given a node a that is selected for round t, we update its
weighted mean at the end of round t in such a way that we
progressively decrease the weight to the previous mean reward
in order to give higher weights to newer rewards as illustrated
in Equation 4

Reward(a, t) + w × Q(a, t0 ) ×s

Y [a] denotes the number of seeds in the cluster of node a,and N [a] denotes the times a has been selected so far. C is a
pre-defined parameter that configures the relative strength of
exploration and exploitation. In particular, a larger C results
in a relatively wider radius in Equation 3, which encourages
exploring fresh nodes that have been fuzzed fewer times. Thiscan help a fuzzer get out of code regions that are too hard tosolve. On the contrary, a smaller C indicates that the empirical
average of fuzzing rewards gets weighted more, thus promoting
nodes that have recently led to good progress. As a result,the fuzzer will focus on these nodes and is expected to reachmore new code coverage. To further demonstrate how it affects
the fuzzing performance, we fuzz the CGC benchmark withdifferent values of C and show the results in §V-F. Based on
the results, we set C to 1.4 in our evaluation.

l≤k≤n

F uzzP erf (a) = Q(a) + U (a)Y [a]×Y [a0 ]

sP
SeedRareness(s, l) =2
F ∈Cl (P,s) rareness [F ]|{F : F ∈ Cl (P, s)}|(6)Note that here we take quadratic mean rather than, e.g.,arithmetic mean because it preserves more data diversity. The
rareness of a node al measured by Ml is completely decided
by its child seeds as they share the same coverage regarding
Ml . Let ha1 , · · · , an , an+1 i be the sequence of nodes selected
at round t, where an+1 is the leaf node representing a real
seed s, then at the end of round t the rareness of node al is
updated as

wp
(4)

wp

p=0

N [a, t] denotes the number of times that node a has been
selected so far at the end of round t, t0 is the last round at which
node a was selected, and w is the discount factor. Note thatthe smaller w is, the more we ignore the past rewards. Whenw is set to 0, all the past rewards are ignored. To study how
w affects the fuzzing performance, we conduct an empiricalexperiments (§V-F). Based on the results, we empirically set
w to 0.5 in our evaluation.

Rareness(al ) = SeedRareness(s, l)(7)

Notably, we update the rareness score of seeds and nodes
lazily for two reasons. First, it reduces the performance overhead. Second, it can lead to overestimating the rareness of anode that has not been fuzzed for a long time, so that seed ismore likely to be scheduled.

U (a) is the estimated radius factoring in the number oftimes a has been selected. In addition, we also consider thenumber of seeds that a contains based on the insight that
nodes with more seeds should be scheduled more for seedIn addition to updating the rareness of a node picked in
the past round, we also calculate the rareness of each newnode similarly. As discussed previously, this makes each new8

effects of randomness. Each fuzzing starts with a single seed“123\n456\n789\n”. We chose this initial because theinitial seed affects the fuzzing progress a lot: seeds that are
too good may make most code covered at the beginning if
the program is not complex, while poor ones may make thefuzzing get stuck before reaching the core code of the program.
These two cases both will make the fuzzing reach the plateau
early, and fail to show the performance differences between
our approach and other fuzzers. The seed we chose showed
a good capability to reveal performance differences between
fuzzers.

node have an initial score to differentiate itself from other new
nodes before its reward is estimated.
Finally, we have the score of a node a via multiplying its
rareness and estimated fuzzing performance together as shownin Equation 8. This score is the one used in Algorithm 3 todetermine which nodes will be picked and which seed will be
fuzzed next.
Score(a) = Rareness(a) × F uzzP erf (a)V.

(8)

E VALUATIONThe second benchmark set is the Google FuzzBench [21]that offers a standard set of tests for evaluating fuzzer performance. These tests are derived from real-world open-sourced
projects (e.g., libxml, openssl, and freetype) that are widelyused in file parsers, protocols, and font operations. For thisdataset, we used the standard automation script to run thebenchmarks, so each benchmark uses the seeds provided by
Google.

Our main hypothesis is that our multi-level coverage metricand hierarchical seed scheduling algorithm driven by the MAB
model can achieve a good balance between exploitation andexploration, thus boosting the fuzzing performance. To validate
our hypothesis, we implemented two prototypes A FL -H IER
and A FL ++-H IER, one based on A FL [55] and the other basedon A FL ++ [17], and evaluated them on various benchmarks
aiming to answer the following research questions.

2) Implementations: For evaluation over the CGC dataset,
we used a prototype built on top of the code open-sourced by
Wang et al. [45], which is based on A FL QEMU-mode, for
its support for binary-only targets and its emulation of CGC
system calls. For evaluation over the FuzzBench dataset, weused a prototype built upon the A FL ++ project [17] (QEMUmode only), for its support of persistent mode and higher
fuzzing throughput.

• RQ1 Can A FL -H IER/A FL ++-H IER detect more bugs thanthe baseline?
• RQ2 Can A FL -H IER/A FL ++-H IER achieve higher coverage than the baseline?
• RQ3 How much overhead does our technique impose on
the fuzzing throughput?

3) Baseline Fuzzers: For A FL-based prototype, we choose
three fuzzers as the baseline for comparison: the original
A FL [55], A FL FAST [9], and A FL -F LAT [45]. A FL -F LAT isconfigured with edge sensitivity CE and distance sensitivity
CD (see §III-D2 for more details), but uses the power scheduler from A FL FAST instead of our hierarchical scheduler. As
discussed in §II-A, the performance of greybox fuzzing is
mainly affected by four factors: seed selection, seed scheduling, mutation strategies, and fuzzing throughput. We made all
fuzzers use the same mutation strategy to reflect the benefit of
our approach, and ran the experiments ten times to minimize
the impact of randomness [24]. We also ran all fuzzers in the
QEMU mode so they can have similar fuzzing throughput,
which also makes it easier to assess A FL -H IER’s performance
overhead. Comparisons with A FL and A FL FAST aim to show
the overall performance improvement of A FL -H IER; and comparison with A FL -F LAT aims to show the necessity/benefit ofour scheduler (i.e., increasing the sensitivity of the coverage
metric alone is not enough).

• RQ4 How well does our hierarchical seed schedulingmitigate the seed explosion problem caused by highsensitive of coverage metrics?
• RQ5 How do the hyper-parameters affect the performanceof our hierarchical seed scheduling algorithm?
• RQ6 How flexible is our framework to integrate othercoverage metrics?
A. Experiment Setup
1) Benchmarks: The first set of programs are from DARPA
Cyber Grand Challenge (CGC) [10]. These programs arecarefully crafted by security experts that embed different
kinds of technical challenges (e.g., complex I/O protocols
and input checksums) and vulnerabilities (e.g., buffer overflow, integer overflow, and use-after-free) to comprehensively
evaluate automated vulnerability discovery techniques. There
are 131 programs from CGC Qualifying Event (CQE) and74 programs from CGC Final Event (CFE), a total of 205.
CGC programs are designed to run on a special kernel withseven essential system calls so that competitors can focus
on vulnerability discovery techniques. In order to run those
programs within a normal Linux environment, we use QEMU
to emulate the special system calls. Unfortunately, due toimperfect simulation, some CGC programs fail to be runcorrectly. We also cannot handle programs that consist ofmultiple binaries, which communicate with each other throughpre-defined inter-process communication (IPC) channels. As
a result, we can only successfully fuzz 180 CGC programs(or binaries, in other words). We fuzz each binary for twohours and repeat each experiment 10 times to mitigate the

For A FL ++-based prototype, we choose two fuzzers as thebaseline1 : the original A FL ++2 [17] and A FL ++-F LAT. We ran
all fuzzers in the QEMU-mode and enabled persistent modefor better throughput
4) Computing Resources: All the experiments are conducted on a 64-bit machine with 48 cores (2 Intel(R) Xeon(R)Platinum 8260 @2.40GHz), 375GB of RAM, and Ubuntu
18.04. Each fuzzing instance is bound to a core to avoid
interference.
1 We are working with Google to provide a more thorough comparison withother fuzzers.
2 The version is 2.68c which our prototype is built on.

9afl-hierafl-flat
aflfast
afl
58

60

62

64

66 68 70 72 74
number of crashed binaries

76

78

uniquely crashed by a fuzzer across ten rounds of trails.
As we can see, the added (distance) sensitivity CD allows
A FL -F LAT and A FL -H IER to crash a considerable amount ofbinaries that edge sensitivity (i.e., A FL and A FL FAST) cannot
crash. However, due to the seed explosion problem, A FL -F LAT
could not efficiently explore the seed pool; so it also missed
many bugs A FL and A FL FAST can trigger. In contrast, A FL H IER can achieve a good balance between exploration andexploitation: it crashed more unique binaries and missed much
less.

80

(a) Number of crashed CGC binaries.

80
75
number of crashed binaries

70

Next, we measured the time to first crash (TFC) and show
the accumulated number within a 95% confidence of binaries
crashed over time in Figure 3b. As shown in recent studies [6],[22], TFC is a good metric to measure the performance offuzzers. The x-axis presents the time in minutes, and the yaxis shows the number of crashed binaries. As shown in thegraph, A FL -H IER stably crashed about 20% more binaries thanother fuzzers from the beginning to the end. Notably, A FL H IER crashed the same number of binaries in 30 minutes as
A FL FAST did in 120 minutes; and crashed the same number ofbinaries in 40 minutes as A FL did in 120 minutes. In contrast,
A FL FAST was lagging behind A FL and A FL FAST in most of
the time and only surpassed A FL FAST after 100 minutes. This
result showed that our hierarchical scheduler not only can findmany unique bugs but also can efficiently explore the search
space.

65
60
55
50

afl
aflfastafl-flat
afl-hier

45
40
35
30 0

10 20 30 40 50 60 70 80 90 100 110 120
time to crash (min)(b) Number of CGC binaries crashed over time.

Fig. 3: Crash detection on CGC benchmarks.

C. RQ 2. Code Coverage? Results on CGC binaries demonstrate that A FL -H IER
generally achieved more code coverage and achieved thesame coverage faster. Specifically, A FL -H IER increases thecoverage by more than 100% for 20 binaries, and achieves
the same coverage in 15 minutes that A FL FAST achieves in
120 minutes for about half of the binaries. On FuzzBench,
A FL ++-H IER achieved higher coverage on 10 out of 20
projects.

B. RQ 1. Bug Detection? In experiments with CGC benchmarks, A FL -H IER
crashes more binaries and faster. Especially, it crashes thesame number of binaries in 30 minutes, that A FL FAST
crashes in 2 hours.
In this experiment, we evaluate fuzzers’ capability of detecting known bugs embedded in the CGC binaries. Figure 3ashows the number of crashed CGC binaries across ten roundsof trials. Note that since each binary supposedly only has one
vulnerability, this number equals the total number of uniquecrashes. On average, A FL crashed 64 binaries, A FL FAST
crashed 61 binaries, and A FL -F LAT crashed 62 binaries. In
contrast, A FL -H IER crashes about 77 binaries on average,
which is about 20% more binaries in the 2-hour fuzzing
campaign. A FL -H IER also performed much better when we
look at the lower and upper bound: its lower bound of crashes(74) is always higher than the upper bound of all otherfuzzers. Notably, these vulnerabilities are carefully designedby security experts to highly mimic real-world security-criticalvulnerabilities.

CGC Benchmark. In this experiment, we first measured theedge coverage achieved by fuzzers using QEMU (i.e., captured
during binary translation) on CGC binaries.
Figure 4a illustrates the mean code coverage increase of
A FL -H IER over other fuzzers for the 180 CGC binaries, after
2 hours of fuzzing. The curve above 0% means A FL -H IER
covered more and the curse below 0% means A FL -H IER
covered less. The x-axis presents the accumulated number ofbinaries within a 95% confidence, and the y-axis shows theincreased coverage in logarithmic scale. For example, there
are about 20 binaries for which the code coverage is increased
by at least 100%, and about 45 binaries for which the code
coverage is increased by at least 10%. After 2 hours of fuzzing,
A FL -H IER achieved more coverage for about 90 binaries thanother fuzzers and achieved the same coverage for 50 binaries.
Among about 30 binaries on which A FL -H IER achieves lesscoverage, on half of them the difference is lower than 2%; andonly on five of them the difference is greater than 10%. This
result shows that our approach can cover more or similar codeon most binaries besides detecting more bugs.

Table I shows the pairwise comparisons of CGC binaries
TABLE I: Pairwise comparisons (row vs. column) of uniquely
crashed on CGC benchmark.

A FL
A FL FAST
A FL -F LAT
A FL -H IER

A FL

A FL FAST

A FL -F LAT

A FL -H IER

3
11
17

8
13
22

16
13
18

5
5
1
-

Figure 4b illustrates how fast A FL -H IER can achieve thesame coverage as other fuzzers in two hours. The dashed lines
10

200%
50%
10%
2%
0%
-2%
-10%
-50%
-200%

afl-hier vs afl
afl-hier vs aflfast
afl-hier vs afl-flat

0

20

40

60

The x-axis represents the time in minutes and the y-axis shows
the accumulated number of binaries within a 95% confidence
that A FL -H IER won on coverage. We can observe that after
10 minutes, A FL -H IER already won for about 40 binaries over
A FL and A FL FAST. After 1 hour, it further increased the gap bywinning for more than 70 binaries. Overall, A FL -H IER steadily
won for more and more binaries throughout the process of the
2-hour fuzzing campaign. This indicates that A FL -H IER cancontinuously make breakthroughs in new coverage for binaries
when other fuzzers plateaued.

80 100 120 140 160 180
number of binaries(a) Mean coverage increase. For X binaries, A FL -H IER
achieves at least Y% more coverage than other fuzzers. A curve
towards upper-right indicates that A FL -H IER outperforms theother more significantly.

FuzzBench. Next, we compare A FL ++-H IER with two baseline fuzzers (A FL ++ and A FL ++-F LAT) on Google FuzzBench
benchmarks. Figure 5 shows the mean coverage (with confidence intervals) over time during 6-hour fuzzing campaigns3 .
The y-axis presents the number of covered edges and the x-axis
represents time. Please note that the x-axis is in logarithmic
scale, as recent work suggests the required efforts to achieve
more coverage grow exponentially [6]. Meanwhile, the VarghaDelaney [43] effect size Â12 is shown at the bottom of eachsub-figure, where the left one is of between A FL ++-H IER
over A FL ++ (Qemu) and the right one is of between A FL ++H IER and A FL ++-F LAT, respectively. A value above 0.5735,
0.665, 0.737 (or below 0.4265, 0.335, 0.263) indicates a small,medium, large effect size. More intuitively, a larger value
above 0.5 indicates a higher probability of that A FL ++-H IER
will cover more edges than A FL ++ (Qemu) or A FL ++-F LAT
in a fuzzing campaign. Moreover, a value starting with a star
indicates a statistical significance tested by Wilcoxon signedrank test (p < 0.05). Overall, A FL ++-H IER could beat A FL ++(Qemu) and A FL ++-F LAT on about ten projects, and achieved
significantly more coverage on projects openthread, sqlite3,
and proj4.

time (min)120
100
afl-hier vs afl
80
afl-hier vs aflfast
60
afl-hier vs afl-flat
40
20
0 0
20 40 60 80 100 120 140 160 180
number of binaries(b) Time to coverage. For X binaries, A FL -H IER achieved
the same coverage in Y minutes, as the other fuzzer achievedin 2 hours (solid line). A curve in solid line towards thelower right with its counterpart in dashed line towards lower
left indicates a more statistical significance of that A FL -H IER
achieve coverage faster than the opponent.

number of binaries

100
80
60
40
20
0
0

afl-hier vs afl
afl-hier vs aflfast
afl-hier vs afl-flat
10 20 30 40 50 60 70 80 90 100 110 120
time (min)Table II shows the unique edge coverage of A FL ++ (Qemu)
and A FL ++-H IER. The results indicate even on programs
where A FL ++-H IER has lower mean coverage than A FL ++,it still can cover some unique edges A FL ++ does not cover.
Note that here we union edge coverage across different runs, so
for some benchmarks like lcms and libpcap, though the mean
coverage differences are large, the unique coverage differences
are much smaller.

(c) Better coverage. After X minutes of fuzzing, A FL -H IER
achieves more coverage than other fuzzers for Y binaries. An
curve towards upper left indicates that A FL -H IER achieves
better coverage than the opponent more significantly.

Compared to the results on the CGC benchmarks, weobserve that our performance is not significantly better thanA FL ++ on most of the FuzzBench benchmarks. We suspect
the reason is that our UCB1-based scheduler and the hyperparameters we used in the evaluation prefer exploitation over
exploration. As a result, when the program under test is
relatively smaller (e.g., CGC benchmarks), our scheduler candiscover more bugs without sacrificing the overall coverage
by too much. But on FuzzBench programs, breaking throughsome unique edges (Table II) can be overshadowed by not
exploring other easier to cover edges.

Fig. 4: Coverage improvement on the CGC benchmarks.

(on the right-hand-side after hitting 120 min) show for thecases where baseline fuzzers achieved more final coveragein two hours. The x-axis shows the accumulated number ofbinaries within a 95% confidence, while the y-axis shows
the time in minutes. We can see that for about half of thetotal 180 binaries, A FL -H IER achieved the same coverage in
15 minutes as baseline fuzzers did in 2 hours. Moreover, forabout 110 binaries, A FL -H IER achieves the same coverage inhalf an hour; and for about 130 binaries, A FL -H IER achieves
the same coverage in one hour. Similar to TFC (time to firstcrash), this result also shows that our approach can achieve
the same coverage faster, indicating it can balance explorationand exploitation well.

? Results on CGC benchmarks show that A FL -H IER has
a competitive throughput as A FL and A FL FAST. Moreover,even built on the faster fuzzer A FL ++, A FL ++-H IER still

Figure 4c shows the number of binaries for which A FL H IER achieved more coverage than other fuzzers over time.

3 We are working with Google to provide a 23-hour run that compares withmore fuzzers.

D. RQ 3. Fuzzing Throughput

11freetype2-2017

1.0

harfbuzz-1.3.2

17500

lcms-2017-03-21

15000

2000

7000

12500
10000

6000

1500

7500

5000

1000

15m
0.8

30m

0.72 0.50
1h
2h

4h 6h

libpng-1.2.56

1650

30m

0.51 *0.93
1h
2h

4h 6h

number of edges

30m*0.11 *0.00
1h
2h

20000

30m

0.69 *1.00
1h
2h

4h 6h

4h 6h

*0.25 *0.86
1h
2h

4h 6h

openssl_x509

5400
5200

2000

6000

30m

*0.72 *0.93
1h
2h

4h 6h

bloaty_fuzz_target

30m

0.50 0.50
1h
2h

30m

0.39 0.39
1h
2h

5000

4h 6h

15m

libpcap_fuzz_both15m

re2-2014-12-09

3500

30m

*0.00 *0.83
1h
2h

30m

0.58 *0.72
1h
2h

4h 6h

15m

15m

4h 6h

curl_curl_fuzzer_http30m*0.92 0.50
1h
0.4
2h

4h 6h

1800
1600
1400
1200
1000
800

15m

time

15m

30m

0.44 0.19
1h
2h

4h 6h

proj4-2017-08-14

5000
3000
2000

30m

*0.79 0.56
1h
2h

1000

4h 6h

woff2-2016-05-06

625

4h 0.26h*0.97 *0.94
1h
2h

4000

7600

630

*0.00 *0.00
1h
2h

30m

15000

4h 6h

7800

635

30m

4h 6h

openthread-2019-12-23

15500

8000

640

2500

*0.18 0.22
1h
2h

16000

mbedtls_fuzz_dtlsclientsystemd_fuzz-link-parser

3000

15m

17000

5500

0

4h 6h

5000

30m

16500

1000

400

15m

5800

2000

500

2600

10000

15m

3000

600

30m

5600

6500

jsoncpp_jsoncpp_fuzzer

2800

12000

2100

15m

3000

14000

8000

1900

18000

3200

16000

vorbis-2017-12-11

22000

2000
0.0
15m
0.0

15m

sqlite3_ossfuzz

24000

15m
0.2

15m

libxml2-v2.9.2

3000

26000

300

4h 6h

4000

1500

15m
0.4

*0.22 *0.00
1h
2h

5000

1550

15m
0.6

30m

6000

1600

1450

15m

libjpeg-turbo-07-2017
3400

8000

15m
1000

30m

600

4h 6h

4h 6h

zlib_zlib_uncompress_fuzzer

800*0.78 0.35
30m 0.6 1h2h*0.94 *0.89
1h2h

15m0.8 30m

afl++
afl++-flat
afl++-hier*1.00 *0.89
1h
2h

4h 6h
1.0

Fig. 5: Mean coverage in a 6 hour fuzzing campaign on FuzzBech benchmarks.
has a comparable throughput as shown by the results on
FuzzBench benchmarks.

Next, we measured the throughput of A FL -H IER versus
A FL and A FL FAST on CGC benchmarks. Figure 6 shows theratio of A FL -H IER’s throughput over A FL and A FL FAST in an
ascending order. The x-axis represents different CGC binaries
while the y-axis shows the ratio within a 95% confidence
in logarithmic scale. Surprisingly, A FL -H IER only leads toa lower throughput for about a quarter of the binaries; andfor another quarter of the binaries, A FL -H IER’s throughput is
at least twice as A FL FAST’s. This indicates that the specificoptimizations for A FL -H IER act very well. A similar trend
is also observed on the A FL ++-based prototype, as shownin Figure 8.

A multi-level coverage metric requires collecting morecoverage measurements during runtime and performing more
operations to insert a seed into the seed tree. Similarly, ourhierarchical scheduler also requires more steps than the powerscheduler of A FL and A FL FAST. Therefore, we expect ourapproach to have a negative impact on fuzzing throughput.
Moreover, the multi-level coverage metric is sensitive to minor
variances of test cases and execution paths; consequently, it ismore likely to schedule larger and more complex seeds leading
to longer execution time.

E. RQ 4. Performance Boost via Hierarchical Seed SchedulingTo quantify the impact on fuzzing throughput, we first investigated the proportion of the time that A FL -H IER spends inscheduling, which involves maintaining the incidence frequencies and the tree of seeds and choosing the next seed to fuzz.
The results on CGC benchmarks are shown in Figure 7, where
the x-axis represents individual runs (in total 10×180 = 1800)
and the y-axis shows the portion of time spent on scheduling.
We can see that the median overhead is as low as 3%, and mostoverhead is lower than 10%. On A FL ++-based prototype, we
observed lower performance overhead, as shown in Figure 9.

? Experiment results on CGC and FuzzBench benchmarks demonstrate that our hierarchical seed scheduler
dramatically reduces the number of candidates to be
examined.
Previous experiments already show that our hierarchicalseed scheduler is more suitable for highly sensitive coverage
metrics, as A FL -H IER can achieve higher coverage fasterthan A FL -F LAT and find more bugs. In this evaluation, we
12TABLE II: Unique edge coverage between afl++ (Qemu) andafl++-hier (Hier) on FuzzBench benchmarks. The coverage isunion over different runs.
Total

Hier - Qemu

Qemu - Hier

bloaty_fuzz_target
curl_curl_fuzzer_httpfreetype2-2017
harfbuzz-1.3.2
jsoncpp_jsoncpp_fuzzer
lcms-2017-03-21
libjpeg-turbo-07-2017
libpcap_fuzz_both
libpng-1.2.56
libxml2-v2.9.2
mbedtls_fuzz_dtlsclient
openssl_x509
openthread-2019-12-23
proj4-2017-08-14
re2-2014-12-09
sqlite3_ossfuzz
systemd_fuzz-link-parser
vorbis-2017-12-11
woff2-2016-05-06
zlib_zlib_uncompress

102417143182
56114
13073
2583
12817
18486
11800
5944
89852
32046
115381
42901
10434
5904
48181
4167
6372
6401
1664

24
203
774
58
0
36
0
141
6
52
142
26
344
109
2
1880
0
8
54
24

674
114
1227
124
0
33
237
195
54
210
102
14
0
67
100
965
0
4
8
0

throughput ratio

500%

10%

6%
4%
2%
0%

runs

Fig. 7: Overhead of A FL -H IER Scheduler on CGC benchmarks.

500%

afl-hier vs afl
afl-hier vs aflfast
afl-hier vs afl-flat

afl++-hier vs afl++
afl++-hier vs afl++-flat

200%

200%

100%

100%
50%
20%
10%

8%

throughput ratio

1000%

12%
overhead proportion

Benchmark

14%

50%

20%
binaries

binaries

Fig. 8: Comparison between Throughput of A FL ++-H IER,
A FL ++, and A FL ++-F LAT on FuzzBench benchmarks.

Fig. 6: Comparison between Throughput of A FL -H IER, A FL,
A FL FAST and A FL -F LAT on CGC benchmarks.

fuzzing performance (in terms of coverage and detected bugs)
than baseline fuzzers.

investigate the number of seeds generated by each fuzzer
to validate that such improvement is indeed caused by thescheduler. Figure 10 shows the number of seeds generated byeach fuzzer on the left side, as well as the number of nodes
at different levels of the tree in A FL -H IER on the right side.
The y-axis is in logarithmic scale. We can observe that due
to the increased sensitivity of distance metric CD , both A FL H IER and A FL -F LAT selected one magnitude more seeds thanA FL and A FL FAST, which uses edge coverage with hit count.
However, by clustering the seeds in a hierarchical structure,
A FL -H IER dramatically reduced the number of candidates to
examine when scheduling. Specifically, on average there areabout 21 + 1102/21 + 2350/1102 + 2608/2350 ≈ 77 examinations to perform for each scheduling, which is significantly
less than examining 2608 seeds. As a result, even with themost number of seeds (more than A FL -F LAT), A FL -H IER canstill balance exploration and exploitation and achieve better

On FuzzBench benchmarks, we also observed a similarlevel of reduction, as shown in Figure 11. More importantly,
we can see that our scheduling algorithm can scale to larger
programs with significantly more edges and more saved seeds.
As shown in Table II, all the benchmarks have at least
thousands of edges in total, and some even contain more than
one hundred thousand edges.
F. RQ 5. Hyper-parameters? Experiment results on CGC benchmarks demonstratethat the hyper-parameters will affect the performance interms of crashes and edge coverage.
As discussed in §IV-B, the seed scoring involves two hyperparameters. One is w in Equation 4 that determines how much
13

2%

50000
20000
10000
5000

number of seeds & nodes

overhead proportion

1.5%

1%

0.5%

0%

13199

9332

13191

2016
731

200
100
50
20
10

runs

afl++

Fig. 9: Overhead of A FL ++-H IER Scheduler on FuzzBench
benchmarks.

50000
20000
10000
5000
2000
1000
500
200
100
50
20
10

2000
1000
500

14501

afl++-flat

afl++-hier

l1

l2

l3

Fig. 11: Number of Seeds and Nodes on FuzzBech benchmarks.
TABLE III: Average number of crashed CGC binaries andmean edge coverage with different values of hyper-parameterC.

number of seeds & nodes

2480

2608

2350
1102

181

0

0.014

0.14

1.4

14

Crash
Edge Cov

74
776

75
667

75
748

76
727

75
746

178

seed chain in one run, it also takes the risk of being trapped infuzzing other seeds that previously have led to rarely explored
coverage, thus missing the crash in other runs. In other words,
high exploitation may do better in crash triggering than crash
reproducing. Meanwhile, the result of edge coverage indicatesthat exploring more coverage may not be closely related tobug detection as expected when under different configurationsof the relative strength of exploration and exploitation. For
example, setting C to 0.014 will lead to significantly lesscoverage, but it crashes almost the same number of binaries
as others.

21

afl

Value of C

aflfastafl-flat

afl-hier

l1

l2

l3

Fig. 10: Number of Seeds and Nodes on CGC benchmarks.

In terms of the hyper-parameter w, note that a larger w
makes old rewards more weighted, thus encourages seed exploitation rather than exploration. We can observe that setting
w either too high (as 1.0) or too low (as 0.5) will lead to worse
coverage, while setting w to 0.5 will lead to significantly moreunique crashes.

we will decrease weights to old rewards when calculating themean reward. The other one is C in Equation 5 that controls
the trade-off between seed exploration and exploitation. In
this evaluation, we investigate when they are set to different
values, how the fuzzing performance will vary. Table III
and Table V show the average number of crashed binaries andcovered edges with different values of C and w, respectively.
In addition, we also investigate the number of binaries uniquely
crashed as shown in Table IV and Table VI, where each cell
represents the number of binaries that have been crashed by
the setting of the row once but never by the setting of thecolumn. We can observe that different settings will lead todifferent results.

Overall, we can observe that when setting C to 1.4, w to
0.5, they perform reasonably well in average crashes, uniquecrashes, and mean edge coverage. Thus we adapt these settingsin our current implementation.
G. RQ 6. Ability to Support other Coverage Metrics? Experiment results on the maze problem show that
our hierarchical scheduler can also improve the fuzzing
performance when using other sensitive coverage metrics.

Notably, when C is set to 0, which extremely encourages
exploitation, it uniquely crashes the most binaries, but on
average, it crashes the least. This indicates that althoughkeeping exploitation may help to trigger a crash at the end of a

As discussed in §III-A, it is very hard, if not impossible, touse edge or even distance coverage to solve the maze problem
14

TABLE IV: Pairwise comparisons (row vs. column) of
uniquely crashed on CGC benchmarks with different valuesof hyper-parameter C.
Value of C

0

0.014

0.14

1.4

14

0
0.014
0.14
1.4
14

3
4
3
3

8
4
7
3

7
2
7
2

4
3
5
4

9
4
5
9
-

Our approach relies little on these techniques and is orthogonal
to these work. On the other hand, there is an increasing numberof greybox fuzzers that are carefully crafted to test specifictypes of programs such as OS kernels [38], [53], firmware [57],protocol [35], smart contracts [31], deep neural networks [50].
It is promising for these fuzzers to adopt our techniques toimprove their efficiency.
B. Improving Coverage Metric
Angora [12] involves calling context, and MemFuzz [15]involves memory accesses when calculating edge coverage
to explore program states more pervasively. However, they
pay little attention to the potential seed explosion problem.
CollAFL [19] improves edge coverage accuracy via ensuring
each edge has a unique hash, and utilizes various kinds ofcoverage information to prioritize seeds. However, it requires
a precise analysis of the control flow graph of the target
program. Wang et al. [47] differentiate edges based on theircorresponding memory operations for seed prioritization tofind memory corruption bugs. However, it is incapable of preventing a test case involving diverse memory operations frombeing dropped since it still relies on edge coverage to evaluate
the quality of test cases. Greyone [18] augments edge coveragewith data flow features where lightweight and accurate tainttracking is necessary. IJON [3] designs various primitives forannotating source code that will adapt the coverage metric todifferent kinds of challenges of exploring deep state space.
However, it requires domain knowledge of the target programand much manual work. Ankou [30] proposes a new coverage
metric that measures distances between execution paths of test
cases, and employs adaptive seed pool update to mitigate seed
explosion. By comparison, the distance we propose is between
two arguments of conditions in conditional branches, and weaddress the seed explosion problem via organizing the seedpool as a multi-level tree.

TABLE V: Average number of crashed CGC binaries and meanedge coverage with different values of hyper-parameter W.
Value of W

0.10

0.25

0.50

0.75

0.90

1.00

Crash
Edge Cov

74
698

73
758

76
727

72
666

75
739

75
660

(Listing 1). However, it is possible to solve it using memory
sensitivity CA (see §III-D2 for details). In this experiment, weinvestigate whether our hierarchical scheduler can also boost
the performance of coverage metrics other than code-related
coverage. Specifically, we configured A FL -F LAT and A FL H IER to use memory access metric CA instead of distancemetric CD and evaluate the two fuzzers on the maze problem.
Table VII shows the results. As we can see, compared to thepower scheduler used by A FL -F LAT, our hierarchical scheduler
allows A FL -H IER to solve the maze problem much faster.
This empirical result suggests that our scheduler is flexible
to support different coverage metrics.
VI.

R ELATED W ORK

A. Coverage Guided Greybox Fuzzing
Greybox fuzzing was introduced as early as in 2016 by
Sidewinder [16]. Since then it has been extensively used inpractice with the popularity of A FL [55] and LIB F UZZER [1].
Meanwhile, it has gained tremendous academic interest in various areas. On the one hand, various techniques including tainttracking [12], [37], [46], symbolic execution [4], [41], programtransformation [23], [33], and deep learning [36], [40], areincorporated into greybox fuzzing to boost its performance.

Some research focuses on finding domain-specific bugs
via specially designed coverage metrics. MemLock [48] takes
memory consumption into account when evaluating a test casein order to trigger memory consumption bugs. SlowFuzz [34]counts the number of instructions executed by test case ascoverage features to detect algorithm complexity bugs. Furthermore, PerfFuzz [26] records the number of times each blockis executed by a test case and considers the test case as a newseed if it increases the execution count for any block in order
to find hot spots. KRACE [56] develops a new coverage that
captures the exploration progress in the concurrency dimension
to find data races in kernel file systems. Our work offers aframework to combine these metrics with others so that they
can benefit from more general metrics.

TABLE VI: Pairwise comparisons (row vs. column) of
uniquely crashed on CGC benchmarks with different valuesof hyper-parameter W.
Value of W

0.10

0.25

0.50

0.75

0.90

1.00

0.10
0.25
0.50
0.75
0.90
1.00

1
8
2
4
4

5
11
4
5
6

2
1
2
3
4

3
1
9
4
5

4
1
9
3
5

3
1
9
3
4
-

Wang et al. [45] systematically evaluate multiple coverage
metrics, revealing that there is no grand slam coverage metricthat can beat others, and it is promising to combine different
coverage metrics together through cross seeding between multiple fuzzing instances. We combine coverage metrics within
one fuzzing instance, avoiding the overhead of synchronizing
seeds as well as redundant fuzzing. FuzzFacotry [32] provides
a platform that makes combining different coverage metrics
easy and flexible. However, it does not address the seed
explosion problem, as our experimental results demonstrate

TABLE VII: Average solving time for the maze problem(Listing 1).
FuzzerA FL -F LAT

A FL -H IER

Time (sec)383 ± 92

180 ± 36

15

R EFERENCES

that randomly combining different metrics without a properorganization may lead to negative impacts.

[1]
[2]

C. Smart Seed Scheduling
A FL FAST [9] focuses on fuzzing seeds exercising lowfrequency paths and assigns more power to them throughmodeling greybox fuzzing as a Markov chain. FairFuzz [27]identifies low-frequency edges and prioritizes mutations satisfying these edges. Entropic [7] targets on the test cases thata seed has generated, evaluating the diversity of coveragefeatures they exercise via the information-theoretic entropy.
Consequently, seeds with higher information gains are more
likely to be scheduled. Vuzzer [37] de-prioritizes seeds hitting
error-handling or frequently visited code that is identified
via heavyweight static and dynamic analysis. Cerebo [28]prioritizes seeds via various metrics including code complexity,
coverage, and execution time. AFLGo [8] and UAFL [44]are directed fuzzers that favor seeds closer to targeted code.
Compared to these work, our scheduling algorithm considers
the rareness of both static features it covers and test cases it
has generated when evaluating a seed.

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Modeling scheduling as an MAB problem. Woo et al. [49]model blackbox mutational fuzzing as a classic Multi-Armed
Bandit (MAB) problem. Nevertheless, its goal is to search for
an optimal arrangement for a fixed set of program-seed pairs
to maximize the unique bugs found. EcoFuzz [54] proposesa variant of the Adversarial Multi-Armed Bandit model formodeling seed scheduling. However, it explicitly puts seed
exploration and exploitation in separate stages, launching exploitation only when all existing seeds have been explored
once. Thus it is incapable of solving the seed explosion
problem.

[10]
[11]
[12]
[13]

[14]

[15]

VII.

C ONCLUSION[16]

Fine-grained coverage metrics, such as distances between
operands of comparison operations and array indices involved
in memory accesses, allow greybox fuzzers to detect bugs thatcannot be triggered by traditional edge coverage. However,existing seed scheduling algorithms cannot efficiently handle
the increased number of seeds. In this work, we present
a new coverage metric design called multi-level coverage
metric, where we cluster seeds selected by fine-grained metrics
using coarse-grained metrics. Combined with a reinforcementlearning-based hierarchical scheduler, our approach significantly outperforms existing edge-coverage-based fuzzers on
DARPA CGC challenges.

[17]

[18]

[19]

[20]
[21]

ACKNOWLEDGMENT[22]

This work is supported, in part, by National Science
Foundation under Grant No. 1664315, No, 1718997, Officeof Naval Research under Award No. N00014-17-1-2893, and
UCOP under Grant LFR-18-548175. Any opinions, findings,
and conclusions or recommendations expressed in this paper
are those of the authors and do not necessarily reflect the viewsof the funding agencies.

[23]

[24]

16

“Libfuzzer: a library for coverage-guided fuzz testing,” https://llvm.org/
docs/LibFuzzer.html.
R. Agrawal, “Sample mean based index policies with o (log n) regret
for the multi-armed bandit problem,” Advances in Applied Probability,
pp. 1054–1078, 1995.
C. Aschermann, S. Schumilo, A. Abbasi, and T. Holz, “Ijon: Exploring
deep state spaces via fuzzing,” in IEEE Symposium on Security andPrivacy (Oakland), 2020.
C. Aschermann, S. Schumilo, T. Blazytko, R. Gawlik, and T. Holz,“Redqueen: Fuzzing with input-to-state correspondence,” in Annual
Network and Distributed System Security Symposium (NDSS), 2019.
P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of themultiarmed bandit problem,” Machine learning, vol. 47, no. 2-3, pp.
235–256, 2002.
M. Böhme and B. Falk, “Fuzzing: On the exponential cost of vulnerability discovery,” in ACM SIGSOFT Symposium on the Foundations ofSoftware Engineering (FSE), 2020.
M. Böhme, V. Manes, and S. K. Cha, “Boosting fuzzer efficiency: An
information theoretic perspective,” in ACM SIGSOFT Symposium on
the Foundations of Software Engineering (FSE), 2020.
M. Böhme, V.-T. Pham, M.-D. Nguyen, and A. Roychoudhury, “Directed greybox fuzzing,” in ACM Conference on Computer and Communications Security (CCS), 2017.
M. Böhme, V.-T. Pham, and A. Roychoudhury, “Coverage-based greybox fuzzing as markov chain,” in ACM Conference on Computer andCommunications Security (CCS), 2016.
D. CGC, “Darpa cyber grand challenge binaries,” https://github.com/
CyberGrandChallenge, 2014.
S. K. Cha, M. Woo, and D. Brumley, “Program-adaptive mutationalfuzzing,” in IEEE Symposium on Security and Privacy (Oakland), 2015.
P. Chen and H. Chen, “Angora: Efficient fuzzing by principled search,”
in IEEE Symposium on Security and Privacy (Oakland), 2018.
P. Chen, J. Liu, and H. Chen, “Matryoshka: Fuzzing deeply nested
branches,” in ACM Conference on Computer and Communications
Security (CCS), 2019.
J. Choi, J. Jang, C. Han, and S. K. Cha, “Grey-box concolic testingon binary code,” in International Conference on Software Engineering(ICSE), 2019.
N. Coppik, O. Schwahn, and N. Suri, “Memfuzz: Using memory
accesses to guide fuzzing,” in IEEE Conference on Software Testing,
Validation and Verification (ICST), 2019.
S. Embleton, S. Sparks, and R. Cunningham, “Sidewinder: An evolutionary guidance system for malicious input crafting.” in BlackHat,
2006.
A. Fioraldi, D. Maier, H. Eißfeldt, and M. Heuse, “Afl++: Combining incremental steps of fuzzing research,” in USENIX Workshop on
Offensive Technologies (WOOT), 2020.
S. Gan, C. Zhang, P. Chen, B. Zhao, X. Qin, D. Wu, and Z. Chen,“Greyone: Data flow sensitive fuzzing,” in USENIX Security Symposium(Security), 2019.
S. Gan, C. Zhang, X. Qin, X. Tu, K. Li, Z. Pei, and Z. Chen, “Collafl:
Path sensitive fuzzing,” in IEEE Symposium on Security and Privacy(Oakland), 2018.
Google, “OSS-Fuzz - continuous fuzzing of open source software,”https://github.com/google/oss-fuzz, 2016.
——, “Fuzzbench: Fuzzer benchmarking as a service,” https://google.
github.io/fuzzbench/, 2020.
A. Hazimeh, A. HERRERA, and M. Payer, “Magma: A groundtruth fuzzing benchmark,” in ACM on Measurement and Analysis ofComputing Systems (SIGMETRICS), 2021.
U. Kargén and N. Shahmehri, “Turning programs against each other:high coverage fuzz-testing using binary-code mutation and dynamic
slicing,” in Proceedings of the 2015 10th Joint Meeting on Foundationsof Software Engineering, 2015.
G. T. Klees, A. Ruef, B. Cooper, S. Wei, and M. Hicks, “Evaluating
fuzz testing,” in ACM Conference on Computer and Communications
Security (CCS), 2018.

[25]lafintel, “Circumventing fuzzing roadblocks with compiler transformations,” https://lafintel.wordpress.com/, 2016.

[26]

C. Lemieux, R. Padhye, K. Sen, and D. Song, “Perffuzz: automatically generating pathological inputs,” in International Symposium on
Software Testing and Analysis (ISSTA), 2018.

[27]

C. Lemieux and K. Sen, “Fairfuzz: A targeted mutation strategy forincreasing greybox fuzz testing coverage,” in IEEE/ACM International
Conference on Automated Software Engineering (ASE), 2018.

[47]

[48]

[28]

Y. Li, Y. Xue, H. Chen, X. Wu, C. Zhang, X. Xie, H. Wang, and Y. Liu,
“Cerebro: context-aware adaptive fuzzing for effective vulnerability detection,” in ACM SIGSOFT Symposium on the Foundations of Software
Engineering (FSE), 2019.

[29]

C. Lyu, S. Ji, C. Zhang, Y. Li, W.-H. Lee, Y. Song, and R. Beyah,“Mopt: Optimized mutation scheduling for fuzzers,” in USENIX Security Symposium (Security), 2019.

[30]

V. J. Manès, S. Kim, and S. K. Cha, “Ankou: Guiding grey-box
fuzzing towards combinatorial difference,” in International Conference
on Software Engineering (ICSE), 2020.

[31]

T. D. Nguyen, L. H. Pham, J. Sun, Y. Lin, and Q. T. Minh, “sfuzz: An
efficient adaptive fuzzer for solidity smart contracts,” in International
Conference on Software Engineering (ICSE), 2020.

[32]

R. Padhye, C. Lemieux, K. Sen, L. Simon, and H. Vijayakumar,“Fuzzfactory: domain-specific fuzzing with waypoints,” in Annual ACM
Conference on Object-Oriented Programming, Systems, Languages, andApplications (OOPSLA), 2019.

[53]

H. Peng, Y. Shoshitaishvili, and M. Payer, “T-fuzz: fuzzing by programtransformation,” in IEEE Symposium on Security and Privacy (Oakland), 2018.

[54]

[33]

[34]

[49]

[50]

[51]

[52]

T. Petsios, J. Zhao, A. D. Keromytis, and S. Jana, “Slowfuzz: Automateddomain-independent detection of algorithmic complexity vulnerabilities,” in ACM Conference on Computer and Communications Security(CCS), 2017.

[35]

V.-T. Pham, M. Böhme, and A. Roychoudhury, “Aflnet: A greybox
fuzzer for network protocols,” in IEEE International Conference on
Software Testing, Verification and Validation (Testing Tools Track),
2020.

[36]

M. Rajpal, W. Blum, and R. Singh, “Not all bytes are equal: Neuralbyte sieve for fuzzing,” arXiv preprint arXiv:1711.04596, 2017.

[37]

S. Rawat, V. Jain, A. Kumar, L. Cojocar, C. Giuffrida, and H. Bos,
“Vuzzer: Application-aware evolutionary fuzzing,” in Annual Network
and Distributed System Security Symposium (NDSS), 2017.

[38]

S. Schumilo, C. Aschermann, R. Gawlik, S. Schinzel, and T. Holz,“kafl: Hardware-assisted feedback fuzzing for os kernels,” in USENIX
Security Symposium (Security), 2017.

[39]

K. Serebryany, “Continuous fuzzing with libfuzzer and addresssanitizer,” in IEEE Cybersecurity Development (SecDev). IEEE, 2016.

[40]

D. She, K. Pei, D. Epstein, J. Yang, B. Ray, and S. Jana, “Neuzz:
Efficient fuzzing with neural program learning,” in IEEE Symposium
on Security and Privacy (Oakland), 2019.

[41]

N. Stephens, J. Grosen, C. Salls, A. Dutcher, R. Wang, J. Corbetta,
Y. Shoshitaishvili, C. Kruegel, and G. Vigna, “Driller: Augmenting
fuzzing through selective symbolic execution,” in Annual Network andDistributed System Security Symposium (NDSS), 2016.

[42]

L. Szekeres, “Memory corruption mitigation via software hardening andbug-finding,” Ph.D. dissertation, Stony Brook University, 2017.

[43]

A. Vargha and H. D. Delaney, “A critique and improvement of the clcommon language effect size statistics of mcgraw and wong,” Journalof Educational and Behavioral Statistics, vol. 25, no. 2, pp. 101–132,
2000.

[44]

H. Wang, X. Xie, Y. Li, C. Wen, Y. Li, Y. Liu, S. Qin, H. Chen,
and Y. Sui, “Typestate-guided fuzzer for discovering use-after-freevulnerabilities,” in International Conference on Software Engineering(ICSE), 2020.

[45]

J. Wang, Y. Duan, W. Song, H. Yin, and C. Song, “Be sensitiveand collaborative: Analyzing impact of coverage metrics in greybox
fuzzing,” in International Symposium on Research in Attacks, Intrusions
and Defenses (RAID), 2019.

[46]

T. Wang, T. Wei, G. Gu, and W. Zou, “Taintscope: A checksum-aware

[55]
[56]

[57]

17

directed fuzzing tool for automatic software vulnerability detection,” inIEEE Symposium on Security and Privacy (Oakland), 2010.
Y. Wang, X. Jia, Y. Liu, K. Zeng, T. Bao, D. Wu, and P. Su, “Not all
coverage measurements are equal: Fuzzing by coverage accounting for
input prioritization,” in Annual Network and Distributed System Security
Symposium (NDSS), 2020.
C. Wen, H. Wang, Y. Li, S. Qin, Y. Liu, Z. Xu, H. Chen, X. Xie, G. Pu,
and T. Liu, “Memlock: Memory usage guided fuzzing,” in International
Conference on Software Engineering (ICSE), 2020.
M. Woo, S. K. Cha, S. Gottlieb, and D. Brumley, “Scheduling black-box
mutational fuzzing,” in ACM Conference on Computer and Communications Security (CCS), 2013.
X. Xie, L. Ma, F. Juefei-Xu, M. Xue, H. Chen, Y. Liu, J. Zhao,
B. Li, J. Yin, and S. See, “Deephunter: A coverage-guided fuzz testing
framework for deep neural networks,” in International Symposium on
Software Testing and Analysis (ISSTA), 2019.
W. Xu, S. Kashyap, C. Min, and T. Kim, “Designing new operating
primitives to improve fuzzing performance,” in ACM Conference on
Computer and Communications Security (CCS), 2017.
W. You, X. Wang, S. Ma, J. Huang, X. Zhang, X. Wang, and B. Liang,“Profuzzer: On-the-fly input type probing for better zero-day vulnerability discovery,” in IEEE Symposium on Security and Privacy (Oakland),2019.
W. You, P. Zong, K. Chen, X. Wang, X. Liao, P. Bian, and B. Liang,“Semfuzz: Semantics-based automatic generation of proof-of-concept
exploits,” in ACM Conference on Computer and Communications
Security (CCS), 2017.
T. Yue, P. Wang, Y. Tang, E. Wang, B. Yu, K. Lu, and X. Zhou,“Ecofuzz: Adaptive energy-saving greybox fuzzing as a variant of
the adversarial multi-armed bandit,” in USENIX Security Symposium(Security), 2020.
M. Zalewski, “American fuzzy lop.(2014),” http://lcamtuf.coredump.cx/
afl, 2014.
M. X. S. K. H. Zhao and T. Kim, “Krace: Data race fuzzing for kernel
file systems,” in IEEE Symposium on Security and Privacy (Oakland),2020.
Y. Zheng, A. Davanian, H. Yin, C. Song, H. Zhu, and L. Sun, “Firm-afl:
high-throughput greybox fuzzing of iot firmware via augmented processemulation,” in USENIX Security Symposium (Security), 2019.