# Make out like a (Multi-Armed) Bandit: Improving the Odds of Fuzzer Seed
Scheduling with T-Scheduler

Simon Luo  The University of New South WalesAustralia<EMAIL_ADDRESS>,
Adrian Herrera  Australian National UniversityAustralia ,  Paul Quirk  ,
Michael Chase  Defence Science & Technology GroupAustralia ,  Damith C.
Ranasinghe  University of AdelaideAustralia and  Salil S. Kanhere  The
University of New South WalesAustralia

(2024)

###### Abstract.

Fuzzing is an industry-standard software testing technique that uncovers bugs
in a target program by executing it with mutated inputs. Over the lifecycle of
a fuzzing campaign, the fuzzer accumulates inputs inducing new and interesting
target behaviors, drawing from these inputs for further mutation and
generation of new inputs. This rapidly results in a large pool of inputs to
select from, making it challenging to quickly determine the “most promising”
input for mutation. Reinforcement learning (RL) provides a natural solution to
this seed scheduling problem—a fuzzer can dynamically adapt its selection
strategy by learning from past results. However, existing RL approaches are
(a) computationally expensive (reducing fuzzer throughput), and/or  (b)
require hyperparameter tuning (reducing generality across targets and input
types).  To this end, we propose T-Scheduler, a seed scheduler built upon
multi-armed bandit theory to automatically adapt to the target. Notably, our
formulation does not require the user to select or tune hyperparameters and is
therefore easily generalizable across different targets. We evaluate
T-Scheduler over 35CPU- fuzzing effort, comparing it to 11 state-of-the-art
schedulers. Our results show that T-Scheduler improves on these 11 schedulers
on both bug-finding and coverage-expansion abilities.

Fuzzing, Software Testing, Thompson Sampling, Reinforcement Learning, Multi-
Armed Bandits

††copyright: acmcopyright††journalyear: 2024††doi:
XXXXXXX.XXXXXXX††conference: The 19th ACM ASIA Conference on Computer and
Communications Security; July 01–05, 2024; Singapore††price: 15.00††isbn:
978-1-4503-XXXX-X/18/06††ccs: Security and privacy Software and application
security††ccs: Computing methodologies Machine learning

##  1\. Introduction

> “Make out like a bandit”. Idiom. To make a large profit.
>
> Merriam-Webster Dictionary

Fuzzing is a software testing technique for automatically finding bugs and
vulnerabilities in a target program. Fuzzers find bugs by mutating inputs to
induce new behavior in the target. Intuitively, mutated inputs are more likely
to exercise corner cases in the target’s behaviors, leading to bugs. While
most of these mutations do not lead to anything interesting, there remains a
chance that the mutated input induces new and interesting target behaviors.

Intelligently selecting which inputs to mutate is critical for maximizing
fuzzer effectiveness; inputs more likely to uncover new behaviors should be
prioritized for mutation. This prioritization of inputs is known as _seed
scheduling_ 111We use the term “seed scheduling”, rather than “seed
selection”, to disambiguate it from the (offline) process of selecting an
initial set of inputs to bootstrap the fuzzer. (Manès et al., 2021; Wang et
al., 2021a). Seed schedulers typically use heuristics to determine an input’s
position in the fuzzer’s queue. In a coverage-guided greybox fuzzer—the most
common type of fuzzer—seed scheduling can be driven by a combination of:  (i)
code coverage (inputs leading to new code uncover new behaviors);  (ii) input
size (smaller inputs are faster to mutate);  (iii) execution time (inputs with
shorter execution time mean more fuzzer iterations);  (iv) the number of times
the input has been previously selected (avoiding local optima); and  (v)
similarity with other inputs (improving diversity).  However, seed scheduling
is challenging because of a combination of the  (a) large number of inputs
generated via mutation (and thus requiring prioritization),  (b) large search
space of the target, and  (c) computational requirements (e.g., CPU time,
memory, and storage).

Machine learning (ML)—in particular, reinforcement learning (RL)—is commonly
applied to solve challenges in fuzzing (Li et al., 2022; Wang et al., 2020a;
Saavedra et al., 2019; Wang et al., 2021a, b; Böttinger et al., 2018; Scott et
al., 2020; Godefroid et al., 2017; Cheng et al., 2019; Zong et al., 2020; Chen
et al., 2020; Karamcheti et al., 2018). Notably, RL has been used to
adaptively learn seed scheduling strategies more likely to lead to increased
code coverage. In turn, this increases the likelihood of uncovering new bugs
(after all, one cannot find bugs in code that is never executed). However,
integrating RL into fuzzing introduces two challenges: _performance tradeoffs_
and _hyperparameter tuning_.

##### Performance tradeoffs

A fuzzer’s iteration rate is the number of inputs the fuzzer executes per unit
of time; the faster the fuzzer’s iteration rate, the quicker the fuzzer can
discover new and interesting behaviors. However, balancing performance and
“cleverness” in selecting the best input to mutate is difficult. Moreover, RL
algorithms require computational resources to train and evaluate, impacting a
fuzzer’s iteration rate. Naïvely introducing RL into a fuzzer (notably, for
seed scheduling) can increase run-time overhead without any performance
improvement. For example, we found AFL-Hier (Wang et al., 2021a) (a fuzzer
using RL for seed scheduling) introduced $\mathord{>}2\times$ overhead over
AFL++’s (Fioraldi et al., 2020) heuristic-based scheduler without any
improvement in fuzzing outcomes.

##### Hyperparameter tuning

RL algorithms use hyperparameters to configure their learning process. The
number of hyperparameters depends on the RL algorithm used. For example,
AFLFast (Böhme et al., 2016), EcoFuzz (Yue et al., 2020), AFL-Hier (Wang et
al., 2021a), and MobFuzz (Zhang et al., 2022) (fuzzers using RL in their seed
schedulers) each have two hyperparameters. Hyperparameters must be set before
learning (and hence fuzzing) begins. However, empirically selecting optimal
hyperparameter values is time-consuming and difficult to generalize; optimal
values are likely to vary across targets and input formats. Suboptimal
hyperparameter values reduce fuzzing performance.

We propose an RL approach that addresses these challenges and improves fuzzing
outcomes. Our approach models seed scheduling as a _multi-armed bandit_ (MAB)
problem, which we solve using _Thompson sampling_. Thompson sampling allows us
to adaptively and efficiently model the probability of the fuzzer uncovering
new and interesting behaviors. In doing so, the fuzzer can make more
intelligent seed scheduling decisions with  (a) no hyperparameters to tune,
(b) theoretical optimality guarantees (Agrawal and Goyal, 2017), and  (c)
constant-time overheads.  Our approach also uses a self-balancing mechanism to
prioritize inputs covering rare paths and newly-discovered code.

We implement our RL-based seed scheduler, T-Scheduler, in AFL++ (the current
state-of-the-art coverage-guided greybox fuzzer) and evaluate it on 35
programs across two widely-used fuzzer benchmarks (Magma (Hazimeh et al.,
2020) and FuzzBench (Metzman et al., 2021)). Our evaluation shows that
T-Scheduler consistently improves on 11 state-of-the-art seed schedulers on 26
programs. We contribute:

  * •

A theoretical formulation of the seed scheduling problem. We formulate seed
scheduling as a MAB problem. Our formulation allows the fuzzer to prioritize
inputs corresponding to newly-discovered target behaviors, based on learning
the historical success of past seed inputs (Sections 3.1 to 3.5).

  * •

An RL-based seed scheduler with no hyperparameters. We design and implement
T-Scheduler, based on solving our MAB problem using Thompson sampling. Using
Thompson sampling means that we benefit from the inherent theoretical
guarantee that model errors grow sublinearly—important for facilitating long
fuzzing campaigns. Moreover, our implementation has no hyperparameters, making
it more generalizable to different targets and input formats. We integrate our
implementation into AFL++ (Section 3.5).

  * •

An effective and generalizable seed scheduler. We evaluate T-Scheduler by
fuzzing real-world programs ($\mathord{>}\qty{35}{CPU\textrm{-}}$). Our
approach outperforms current state-of-the-art schedulers across both bug-
finding and coverage-expansion metrics (Section 4).

  * •

Analysis of seed scheduler costs. Seed schedulers must carefully balance
overhead costs and precision. To this end, we empirically analyze the cost of
existing schedulers to understand their impact on fuzzing outcomes (Section
4.4).

We release our implementation and results at
https://github.com/asiaccs2024-t-scheduler.

##  2\. Background

###  2.1. Fuzzing

Fuzz testing (“fuzzing”) is a dynamic analysis for uncovering bugs in
software. In a security context, fuzzers have been wildly successful at
discovering tens of thousands of security-critical vulnerabilities in widely-
used code (Chang, 2023). Bugs are found by (rapidly) subjecting a target
program to automatically-generated inputs. The fuzzer generates inputs to
expose and explore corner cases in the target not considered by the developer.
Intuitively, it is in these corner cases where bugs are most likely to lie.

Figure 1. Overview of Greybox Fuzzing.

Figure 1 illustrates the fuzzing process. A fuzzing campaign begins with
curating a corpus of “well-formed” inputs. These inputs are commonly exemplar
input data accepted by the target (Fig. 1(a)) (Rebert et al., 2014; Herrera et
al., 2021). At run time, the fuzzer maintains a queue—initially populated from
this curated corpus—from which an input is selected to fuzz (Fig. 1(b)). The
selected input is mutated and fed into the target to expose corner cases in
program behavior. How does the fuzzer select these inputs?

_Greybox_ fuzzers use lightweight instrumentation to track code executed (or
“covered”) by the target (in contrast, _blackbox_ fuzzers have no internal
view of the target). The fuzzer records code coverage in a _coverage map_ ,
which tracks the number of times a particular coverage element—typically, an
edge in the target’s control-flow graph (CFG)—is executed (Fig. 1(c)). By
tracking code coverage, the fuzzer can determine if the mutated input triggers
new target behaviors. Inputs triggering new behaviors are saved back into the
queue; otherwise, the input is discarded (Fig. 1(d)). This guides the fuzzer
to prioritize inputs leading to new program behaviors (as captured by the
instrumentation). Selecting and prioritizing inputs for mutation is handled by
the _seed scheduler_ (Fig. 1(e)).

###  2.2. Seed Scheduling

An efficient seed scheduler (the blue box in Fig. 1) must satisfy two
competing constraints. First, the seed scheduler must _select the most-
promising input for mutation_ ; i.e., the input most likely to cover new
program behaviors. Second, it must make this selection from a (potentially)
large queue with _minimal run-time overhead_. AFL-based (Zalewski, 2015)
fuzzers solve this problem by bounding the input queue to a fixed size via an
_input filtering and favoring_ phase (Wang et al., 2020b).

##### Input filtering and favoring

The fuzzer only retains inputs that induce new and interesting behaviors in
the target; e.g., an input that covers a new element in the coverage map.
These inputs are made available for future mutations, potentially uncovering
more new behaviors. AFL “favors” an input if it is the fastest and smallest
input for any of the coverage map elements (Böhme et al., 2016) (Fig. 1(f)).
Thus, tracking favored inputs gives the fuzzer a minimal set of inputs (that
are both small and fast) covering all of the elements seen in the coverage map
so far (approximating a _weighted minimum set cover_ , with size and speed as
weights (Fioraldi et al., 2020)). Maintaining a set of favored inputs
implicitly reduces the seed scheduling problem from an unbounded number of
inputs (the union of the initial seed corpus and the inputs generated so far)
to a bounded number of inputs: the number of favored inputs; i.e., the
coverage map’s size.

After filtering and favoring, the scheduler has a bounded number of inputs
from which to select an input to fuzz. From this, the scheduler selects the
“best” input to mutate. For example, AFL selects an input based on a score
calculated using a set of heuristics. These heuristics calculate a performance
score based on an input’s:  (i) coverage;  (ii) execution time (faster inputs
are preferred);  (iii) “depth” (i.e., the number of inputs mutated to reach
the given input); and  (iv) the fuzzer’s run time (newer inputs are
prioritized).  A _power schedule_ (Böhme et al., 2016; Fioraldi et al., 2020)
then distributes fuzzing time across inputs by scaling the performance score
based on the number of times the input has been selected, biasing fuzzing time
to less-fuzzed inputs. Higher energy means the fuzzer spends more time
mutating the corresponding (favored) input.

Notably, AFL’s heuristics are based on intuition and experimentation. Other
fuzzers (e.g., EcoFuzz (Yue et al., 2020), AFL-Hier (Wang et al., 2021a),
MobFuzz (Zhang et al., 2022), and K-Scheduler (She et al., 2022)) also rely on
hyperparameters that must be tuned per target to achieve optimal results. In
contrast, our approach (described in Section 3) replaces these heuristics with
an RL algorithm that uses run-time statistics to dynamically learn and adapt a
seed schedule. Moreover, our approach has no hyperparameters to tune, leading
to more efficient and informed input selection.

###  2.3. Reinforcement Learning

Reinforcement learning (RL) is an ML paradigm that trains an agent by
observing changes in state and rewarding the selected actions (Sutton and
Barto, 2018). The agent aims to select the best action to maximize the
cumulative reward. However, the expected reward for each action is often
unknown and must be learned dynamically via experimentation. This
experimentation leads to a trade-off between _exploiting_ what is already
known and _exploring_ territory.

An RL algorithm is typically defined in terms of _states_ , _actions_ , and
_rewards_. The state is a set of variables describing the environment. Based
on the current state, the agent  (a) selects an action to perform, and  (b)
receives feedback on its selection in the form of a reward.  The agent’s
objective is thus to maximize the cumulative reward over a given time.

These concepts apply naturally to fuzzing. In particular, the fuzzer’s seed
scheduler must select an input (to mutate) from a pool of constantly-changing
possibilities. Ideally, this selection maximizes the discovery of new code, or
(ideally) a bug. _The seed scheduler must balance exploring the input queue
and exploiting the input uncovering the most code_. This requires a careful
trade-off between making intelligent input prioritization decisions and
maintaining the fuzzer’s iteration rate. We satisfy this trade-off by
formulating seed scheduling as a _multi-armed bandit_.

####  2.3.1. Multi-Armed Bandit

The multi-armed bandit (MAB) is a well-explored RL problem focusing on the
trade-off between exploration and exploitation (Lattimore and Szepesvári,
2020). Given a state, the agent selects an action $a_{k}\in\mathcal{A}$ at
each time step $t\in[1,\ldots,T]$. The agent’s goal is to maximize the
cumulative reward (by performing a sequence of actions) over $T$.

The classic MAB involves $K$ slot machines (“bandits”), where each
$k\in[1,\ldots,K]$ has an unknown probability $\theta_{k}$ of paying out when
played. At each time step $t$, the player (i.e., agent) selects a slot machine
to play. Once played, the player is either rewarded with a payout (with
probability $\theta_{k}$) or receives nothing (with probability
$1-\theta_{k}$). Naturally, any rational player would focus on the bandit
paying out the most (thus achieving their goal of maximizing the cumulative
reward). Unfortunately, _this information is unknown to the player_.
Consequently, the player must trade-off between _exploiting_ the bandit with
the (current) highest expected payout and _exploring_ different bandits to
learn more about the probability $\theta_{k}$ (in the hope of finding a higher
payout). What is the best strategy for selecting between exploration and
exploitation?

_Thompson sampling_ (Thompson, 1933) is a popular approach for addressing this
exploration/exploitation trade-off. This popularity is due to simplicity, fast
execution time, and optimality guarantees (ensuring errors grow sublinearly
over time (Agrawal and Goyal, 2017)). Consequently, we adopt Thompson sampling
in T-Scheduler, our RL-based seed scheduler.

##  3\. Approach

Our seed scheduler, T-Scheduler, formulates greybox fuzzing as a Beta-
Bernoulli bandit, which we solve with Thompson sampling. We first provide a
high-level description of the T-Scheduler algorithm (Section 3.2) and a
motivating example (Section 3.2.1), followed by a mathematical formulation of
our Beta-Bernoulli bandit model (Sections 3.3 to 3.5).

###  3.1. Notation and Definitions

A fuzzer measures its progress fuzzing target $\mathcal{P}$ in a coverage map
$\mathcal{C}(\mathcal{P},\iota)\in\mathbb{N}^{K}$ of size $K$. Typically, each
_feature_ $x\in\mathcal{C}(\mathcal{P},\iota)$ records the number of times a
particular edge in the target’s control-flow graph (CFG)222 Some fuzzers
eschew edge coverage for other coverage metrics (e.g., context-sensitive edge
or data flow). Our approach is agnostic to the underlying coverage metric. is
executed by an input $\iota\in\mathcal{I}$, where $\mathcal{I}$ is the set of
inputs representing the union of the initial corpus and the set of inputs
generated by the fuzzer. We refer to this count as a _hit count_ (given by the
function hit_count).

_Feature rareness_ prioritizes features covered less by $\mathcal{I}$. We
adopt the definition by Wang et al. (2021a), where feature rareness is the
inverse of $x$’s hit count. Feature hit counts and rareness are defined for
each feature in the coverage map and the inputs generated so far. These
definitions enable a seed scheduler that prioritizes both newly-discovered and
hard-to-reach code.

###  3.2. The T-Scheduler Algorithm

1

2

3

4$\boldsymbol{\alpha}\leftarrow\\{1\,|\,k\in[1,\ldots,K]\\}$

5 $\boldsymbol{\beta}\leftarrow\\{\,1|\,k\in[1,\ldots,K]\\}$

6

7Function  _UpdatePosterior(_$\mathcal{C}(\mathcal{P},\iota)$ ,
$\boldsymbol{\alpha},\boldsymbol{\beta}$_)_

8 for  _$k,x\in\mathcal{C}(\mathcal{P},\iota)$_ do

9 if  _$x\neq 0$_ then

10 if  _$\textnormal{{IsInteresting}}(\iota)$_ then

11 $\alpha_{k}\leftarrow\alpha_{k}+1$

12

13 else

14 $\beta_{k}\leftarrow\beta_{k}+1$

15

16

17

18 return _$\boldsymbol{\alpha},\boldsymbol{\beta}$_

19

20Function  _SelectInput(_$\boldsymbol{\alpha},\boldsymbol{\beta}$_)_

21 for  _$k\leftarrow[1,\ldots,K]$_ do

22 $\hat{\theta}_{k}\sim\mathrm{Beta}(\alpha_{k},\beta_{k})$

23 $\psi_{k}\sim\mathrm{Beta}(\alpha_{k}+\beta_{k},\alpha_{k}^{2})$

24

25
$a_{t}\leftarrow\arg\max[\psi_{1}\hat{\theta}_{1},\ldots,\psi_{K}\hat{\theta}_{K}]$

26 $\mathcal{I}^{(t+1)}\leftarrow\textnormal{{FavoredInputs}}(a_{t})$

27

28 return _$\mathcal{I}^{(t+1)}$_

Algorithm 1 T-Scheduler.

We present the T-Scheduler algorithm in Algorithm 1. It consists of two
functions: UpdatePosterior and SelectInput.

The UpdatePosterior function—called each time an input $\iota$ is
executed—uses two $K$-length vectors—$\boldsymbol{\alpha}$ and
$\boldsymbol{\beta}$ (Algorithms 1 and 1)—to store the number of times a
coverage map feature is hit or missed, respectively. Each element $\alpha_{k}$
and $\beta_{k}$ (where $k\in[1,\ldots,K]$) represents the number of times
$\iota$ hits or misses $x\in\mathcal{C}(\mathcal{P},\iota)$. These vectors are
used to compute a probability distribution for each coverage map feature,
modeling the probability of an input inducing new behaviors in $\mathcal{P}$.

The SelectInput function is called when the queue has been exhausted. It
samples $\boldsymbol{\theta}=[\theta_{1},\ldots,\theta_{K}]$ from $K$ Beta
distributions (Algorithm 1) to determine the “best” input to fuzz (see Section
3.3). However, using only $\boldsymbol{\theta}$ leads the fuzzer to repeatedly
select the same inputs, because it implicitly penalizes rarely-covered
features in the coverage map. Thus, we introduce a _correction factor_
$\boldsymbol{\psi}=[\psi_{1},\ldots,\psi_{K}]$ (Algorithm 1) based on feature
rareness to penalize frequently-covered coverage map features (see Section
3.4).

Finally, the next input to fuzz is chosen from FavoredInputs using
$\hat{\theta}_{k}$ and $\psi_{k}$ (Algorithms 1 to 1; see Section 3.5).
FavoredInputs stores a single “best” input corresponding to each feature in
the coverage map. Per Section 2.2, the fuzzer determines this input by a
combination of execution time, input size, and the number of times the input
has been fuzzed.

####  3.2.1. Motivating Example

⬇

1void foo(int a, int b) {

2 if (a > 10)

3 if (a > 20)

4 if (b > 10)

5 bug();

6}

(a) The program. The parameters a and b are derived from user input.

ptLine 2$t=1$$(a\leftarrow 15,b\leftarrow 0)$$t=2$$(a\leftarrow 25,b\leftarrow
0)$$t=3$$(a\leftarrow 0,b\leftarrow 15)$$t=4$$(a\leftarrow 0,b\leftarrow
25)$$t=5$$(a\leftarrow 25,b\leftarrow 5)$$t=6$$(a\leftarrow 25,b\leftarrow
25)$Line
3$t=0,\alpha=1,\beta=1,\bar{p}=0.25$$t=1,\alpha=2,\beta=1,\bar{p}=0.29$$t=2,\alpha=3,\beta=1,\bar{p}=0.28$$t=3,\alpha=3,\beta=1,\bar{p}=0.30$$t=4,\alpha=3,\beta=1,\bar{p}=0.31$$t=5,\alpha=3,\beta=2,\bar{p}=0.29$$t=6,\alpha=4,\beta=2,\bar{p}=0.27$Line
4$t=0,\alpha=1,\beta=1,\bar{p}=0.25$$t=1,\alpha=1,\beta=1,\bar{p}=0.21$$t=2,\alpha=2,\beta=1,\bar{p}=0.25$$t=3,\alpha=2,\beta=1,\bar{p}=0.26$$t=4,\alpha=2,\beta=1,\bar{p}=0.28$$t=5,\alpha=2,\beta=2,\bar{p}=0.24$$t=6,\alpha=3,\beta=2,\bar{p}=0.25$Line
5$t=0,\alpha=1,\beta=1,\bar{p}=0.25$$t=1,\alpha=1,\beta=1,\bar{p}=0.21$$t=2,\alpha=1,\beta=1,\bar{p}=0.19$$t=3,\alpha=1,\beta=1,\bar{p}=0.20$$t=4,\alpha=1,\beta=1,\bar{p}=0.21$$t=5,\alpha=1,\beta=1,\bar{p}=0.24$$t=6,\alpha=2,\beta=1,\bar{p}=0.27$Line
6$t=0,\alpha=1,\beta=1,\bar{p}=0.25$$t=1,\alpha=2,\beta=1,\bar{p}=0.29$$t=2,\alpha=3,\beta=1,\bar{p}=0.28$$t=3,\alpha=3,\beta=2,\bar{p}=0.24$$t=4,\alpha=3,\beta=3,\bar{p}=0.21$$t=5,\alpha=3,\beta=4,\bar{p}=0.24$$t=6,\alpha=3,\beta=5,\bar{p}=0.21$$\mathbf{a\leq
10}$$\mathbf{a>10}$$\mathbf{a>20}$$\mathbf{a\leq 20}$$\mathbf{a\leq
20}$$\mathbf{b>10}$

(b) CFG showing the changing parameters $\alpha_{k}$ and $\beta_{k}$ at each
time step $t$. The mean probability for each time step is shown as $\bar{p}$.

Figure 2.  An example showing how T-Scheduler updates its parameters after
each input is executed. Six different values for a and b (corresponding to six
different inputs) are shown in the root node. The parameter $\alpha$ is
incremented when the input discovers new program behavior, otherwise $\beta$
is incremented. The probability $\bar{p}_{k}$ is the normalized mean of the
Beta distribution in Algorithm 1 in Algorithm 1 using Eq. 1.

We use the example in Fig. 2 to illustrate T-Scheduler’s approach. T-Scheduler
is an _adaptive_ scheduler, meaning the probability of selecting a given input
(for mutation) changes as the scheduler receives coverage feedback from the
fuzzer. In this example, coverage feedback is used to update $\alpha$
(Algorithm 1 in Algorithm 1) and $\beta$ (Algorithm 1), storing the positive
and negative feedback of past scheduling decisions, respectively. The
scheduler uses the updated parameters $\alpha$ and $\beta$ to assign a
probability for selecting an input (Algorithm 1). We show the mean of this
probability distribution

(1)
$\displaystyle\bar{p}_{k}=\frac{\mathbb{E}[\mathrm{Beta}(\alpha_{k},\beta_{k})]}{\sum_{k=1}^{K}\mathbb{E}[\mathrm{Beta}(\alpha_{k},\beta_{k})]},$

because of the difficulty visualizing $\hat{\theta}_{k}$ in Fig. 2.
Importantly, Algorithm 1 does not need to compute $\bar{p}_{k}$ and is only
used to visualize how the mean of the probability distribution changes over
time.

Figure 2 uses six example inputs to show how the parameters are updated.
Inputs discovering new program behaviors are stored in the corresponding node
and $\bar{p}$ is the probability of the input being selected by the scheduler.
This assumes that prior inputs that discovered new program behaviors are more
likely to discover new program behaviors. At $t=1$, the input covers lines 3
and 6 (Fig. 2(a)) for the first time, so $\alpha$ is incremented and $\bar{p}$
increases. At $t=2$, the input covers lines 3, 4, and 6. Line 4 is covered for
the first time and $\alpha$ is incremented for lines 3, 4, and 6. Notably,
$\bar{p}$ in line 4 increases but $\bar{p}$ decreases at lines 3 and 6 because
we favor rarer paths. The input covers line 6 at $t=3$ and $t=4$. Line 6 has
already been covered, so $\beta$ is incremented and $\bar{p}$ decreases
(because we penalize inputs that do not uncover new program behaviors).
Similarly, at $t=5$ the input covers lines 3, 4, and 6, which have also been
covered by previous inputs. Thus, $\bar{p}$ decreases at these lines while
$\bar{p}$ increases for lines 2 and 6. Finally, line 5 is covered for the
first time at $t=6$. This results in $\alpha$ increasing at lines 3, 4, and 5
and $\bar{p}$ changing disproportionally to favor rarer paths.

(a) Greedy.

(b) T-Scheduler.

(c) Regret.

Figure 3. An example scheduler demonstrating the probability of an input being
selected over $1,000$ iterations (the $x$-axis is iteration count). The regret
quantifies the error by taking the difference between the optimal decision and
the input selected. The inputs $\iota_{1}$, $\iota_{2}$, and $\iota{3}$ have
latent probabilities of 0.7, 0.8, and 0.9, respectively. The greedy algorithm
has a constant regret, while the T-Scheduler algorithm’s regret approaches
zero over time. Highlight colors reflect those in the plots.

The scheduler selects an input to executed based on the probability that
mutating the input will lead to new program behaviors. This probability is
unknown. Thus, inputs with a higher probability for discovering new program
behaviors must be estimated and prioritized by the scheduler. Figure 3
illustrates the impact different scheduling algorithms have on these
estimates. Here, we assume that a scheduler has three inputs to select
from—$\iota_{1}$, $\iota_{2}$, and $\iota_{3}$—with probabilities 0.7, 0.8,
and 0.9 that a mutation will discover new program behavior (which is unknown
and needs to be estimated by the scheduler in a fuzzing campaign),
respectively to demonstrate the behavior of the algorithm.333In a fuzzing
campaign these probabilities change as new program behaviors are discovered.
Here, we can see input $\iota_{3}$ should be selected because it has the
highest probability to discover new program behavior. But the scheduler does
not know these values and is required to estimate them to assign a scheduling
probability to each input. Figures 3(a) and 3(b) show the convergence of
$\bar{p}$ for two scheduling approaches—a greedy algorithm and
T-Scheduler—when selecting inputs using the scheduling probabilities
($\bar{p}$ or $\hat{\theta}$). T-Scheduler allows for sub-optimal decisions at
a given time by sampling from a distribution (Algorithm 1 in Algorithm 1)
meaning the input with the highest $\bar{p}$ is not always selected. These
sub-optimal decisions allow the model to “explore” early on in the fuzzing
campaign and “exploit” inputs when it has more information. The greedy
approach shown in Fig. 3(a) always tries to select the highest scheduling
probability which does not lead to the optimal solution. Figure 3(c)
illustrates the regret of T-Scheduler converging to zero over time leading to
the optimal solution while a constant regret remains for the greedy approach.
In this example, this can only be achieved if the scheduler always picks
$\iota_{3}$. Current state-of-the-art schedulers (e.g., AFLFast (Böhme et al.,
2016), Entropic (Böhme et al., 2020), and TortoiseFuzz (Wang et al., 2020b))
use a greedy approach to make decisions. T-Scheduler makes more optimal
decisions (compared to greedy algorithms), particularly in long fuzzing
campaigns.

With the T-Scheduler algorithm presented, we now turn our attention to the
probabilistic modeling that underpins our approach.

###  3.3. Adapting the Beta-Bernoulli Bandit

Thompson sampling frames exploration and exploitation as a Bayesian posterior
estimation, choosing an action that maximizes a reward based on a randomly-
drawn prior belief (Section 2.3.1). We assume that information derived from
previous inputs can be used to improve input scheduling in the future. The
reward function provides feedback to the fuzzer after each input $\iota$ is
executed. In particular, the fuzzer is (positively) rewarded for discovering
new target behaviors, and penalized otherwise.

We begin our formulation with a $K$-armed bandit; i.e., there are $K$ actions
for the fuzzer to choose from. Here, $K$ is the size of
$\mathcal{C}(\mathcal{P},\iota)$, and each entry of the coverage map
corresponds to a favored input in a many-to-one relationship (Section 2.2). We
define a fuzzing campaign with respect to a time step $t\in[1,\ldots,T]$,
where $T$ is the length of the campaign (i.e., the number of executed inputs).
Each input $\iota^{(t)}$ at time step $t$ will produce a coverage map
$\mathcal{C}(\mathcal{P},\iota)^{(t)}$. After performing action $k\in[1,\ldots
K]$ the fuzzer is rewarded by:

(2) $r_{k}^{(t)}:=\begin{cases}1,&\text{if }x_{k}^{(t)}\neq 0\text{ and
}\iota^{(t)}\text{ is interesting},\\\ 0,&\text{if }x_{k}^{(t)}\neq
0,\end{cases}$

where $x_{k}^{(t)}\in\mathcal{C}(\mathcal{P},\iota)^{(t)}$ is the coverage map
feature at index $k$. For each time step $t$ the reward is represented as the
vector $\mathbf{r}^{(t)}=[r_{1}^{(t)},\ldots,r_{K}^{(t)}]$. The fuzzer is
rewarded for inducing interesting behaviors in the target (e.g., uncovering
new code). Intuitively, this ensures the scheduler selects inputs that are
more likely to induce new behaviors in $\mathcal{P}$.

####  3.3.1. Estimating Probabilities and Rewarding the Fuzzer

The probability that the fuzzer generates an input (by mutating the current
input) inducing new behaviors is
$\boldsymbol{\theta}=[\theta_{1},\ldots,\theta_{K}]$. Importantly,
$\boldsymbol{\theta}$ is unknown and must be estimated over time through
experimentation. Per Section 2.3, learning $\boldsymbol{\theta}$ requires a
careful balance between exploration and exploitation to maximize the
cumulative reward over $T$. The estimated $\boldsymbol{\theta}$ guides the
seed scheduler to select the next (best) input to fuzz.

We design the reward function in Eq. 2 such that $\theta_{k}$ (the _posterior
distribution_) can be estimated using the Beta-Bernoulli bandit. In this
setting, $\theta_{k}$ is the probability that the input induces new behaviors
in $\mathcal{P}$, and is estimated by a Bernoulli distribution with
observations $r^{(t)}_{k}$ (the _likelihood_) and a Beta distribution over
$\hat{\theta}^{(t)}_{k}$ (the _prior distribution_); i.e.,

(3) $r_{k}^{(t)}\sim
p(r_{k}^{(t)}|\hat{\theta}^{(t)}_{k})=\mathrm{Bernoulli}(\hat{\theta}^{(t)}_{k})$

and

(4) $\hat{\theta}^{(t)}_{k}\sim
p(\hat{\theta}^{(t)}_{k};\alpha_{k},\beta^{(t)}_{k})=\mathrm{Beta}(\alpha_{k}^{(t)},\beta_{k}^{(t)}).$

The prior distribution is modeled as a Beta distribution with parameters
$\boldsymbol{\alpha}^{(t)}=[\alpha^{(t)}_{1},\ldots,\alpha^{(t)}_{K}]$ and
$\boldsymbol{\beta}^{(t)}=[\beta_{1}^{(t)},\ldots,\beta_{K}^{(t)}]$
(Algorithms 1 and 1, Algorithm 1), while the parameters $\alpha_{k}^{(0)}$ and
$\beta_{k}^{(0)}$ are initialized to $1$ at $t=0$ (Algorithms 1 and 1,
Algorithm 1). The parameter $\boldsymbol{\alpha}-1$ represents the number of
times each $x\in\mathcal{C}(\mathcal{P},\iota)$ has been covered (for all
$\mathcal{I}$ executed so far) by an interesting input, while
$\boldsymbol{\beta}-1$ represents the number of times each
$x\in\mathcal{C}(\mathcal{P},\iota)$ was covered by input that was _not_
considered interesting.

Using Bayes rule, the posterior distribution $p(\hat{\theta}|r_{k}^{(t)})$ is

(5) $\displaystyle p(\hat{\theta}^{(t)}_{k}|r_{k}^{(t)})$
$\displaystyle=\frac{p(r_{k}^{(t)}|\hat{\theta}^{(t)}_{k})p(\hat{\theta}^{(t)}_{k};\alpha^{(t)}_{k},\beta^{(t)}_{k})}{p(r_{k}^{(t)})}$
$\displaystyle\propto
p(r_{k}^{(t)}|\hat{\theta}^{(t)}_{k})p(\hat{\theta}^{(t)}_{k};\alpha_{k}^{(t)},\beta_{k}^{(t)}).$

The prior distribution
$p(\hat{\theta}^{(t)}_{k};\alpha_{k}^{(t)},\beta_{k}^{(t)})$ represents the
distribution at the previous time step; i.e.,

(6)
$p(\hat{\theta}^{(t)}_{k};\alpha_{k}^{(t)},\beta_{k}^{(t)}):=p(\hat{\theta}^{(t-1)}_{k}|r_{k}^{(t-1)}),$

while the likelihood $p(r_{k}^{(t)}|\hat{\theta}^{(t)}_{k})$ takes into
account the coverage achieved at the current time step. Equation 6 provides a
mechanism for the fuzzer to update its model to ensure it selects the “best”
seed. The recursive structure defined in Eqs. 5 and 6 means the model is
dependent on previously selected inputs. The fuzzer continuously updates the
model by receiving feedback from the reward function (Eq. 2) at each timestep.
This approximates the posterior distribution
$p(\hat{\theta}^{(t)}_{k}|r_{k}^{(t)})$, which is now the probability that a
fuzzer-generated input will cover this feature in the coverage map.

####  3.3.2. Improving Performance

Directly sampling from Eq. 5 to compute $\boldsymbol{\theta}$ is
computationally expensive. However, using the Beta distribution (which is a
_conjugate prior_ to the Bernoulli distribution) avoids expensive numerical
computations (that are typical in Bayesian inference), leading to simpler
updates after each time step. In particular, solving Eq. 5 with Eqs. 3 and 4
gives the following update rule for the posterior distribution:

(7)
$(\alpha_{k}^{(t)},\beta_{k}^{(t)})=(\alpha_{k}^{(t-1)},\beta_{k}^{(t-1)})+(r_{k}^{(t)},1-r_{k}^{(t)}).$

This is the approach taken in UpdatePosterior (Algorithm 1): the parameters
$\alpha^{(t)}_{k}$ and $\beta^{(t)}_{k}$ are updated incrementally (at each
time step) with each observation of success and failure, respectively. The
update rule has been illustrated in Fig. 2, where $\alpha_{k}$ is incremented
for the path of the input if the input discovered new program behavior,
otherwise $\beta_{k}$ is incremented. For example, at $t=1$, input covered
lines 3 and 6 for the first time so $\alpha$ was incremented for both of these
nodes, and at $t=3$, the input covered Line 6 but did not discover new code
coverage, so $beta$ was incremented for Line 6.

Following these updates, Eq. 5 is sampled by drawing from a Beta distribution
with parameters $\alpha_{k}$ and $\beta_{k}$,

(8) $\hat{\theta}^{(t)}_{k}\sim
p(\theta=\hat{\theta}^{(t)}_{k}|\tilde{r}_{k}^{(t+1)}=1)=\mathrm{Beta}(\alpha^{(t)}_{k},\beta^{(t)}_{k}),$

where $\theta_{k}$—the probability of covering feature
$x\in\mathcal{C}(\mathcal{P},\iota)$—is dependent on the inputs seen so far.

Unfortunately, using $\boldsymbol{\theta}$ (at Algorithm 1, Algorithm 1) to
select the next input will likely result in the fuzzer repeatedly selecting
the same few inputs. This is because incrementing $\boldsymbol{\alpha}$ in Eq.
7 rewards the model, ultimately skewing the probability density function (PDF)
towards one and making it more likely that the fuzzer will select this input.
Similarly, incrementing $\boldsymbol{\beta}$ penalizes the model, skewing the
PDF towards zero and making it less likely that the fuzzer will select this
input. However, this has the side-effect of penalizing actions that are not
selectable. We describe this issue and how we correct for it in Section 3.4.

###  3.4. Rareness Correction

Section 3.3 introduced the standard MAB setting, where we assume all $K$
actions are selectable. However, this is not the case in practice: the fuzzer
cannot select inputs corresponding to unexercised coverage map features.
Moreover, the update rule in Eq. 7 penalizes rarely-covered features in
$\mathcal{C}$.

We use _feature rareness_ to penalize frequently-covered coverage map
features, introducing a _correction factor_ to account for the update rule’s
penalty. This ensures favored inputs corresponding to less-covered features in
the coverage map have a greater chance of being selected, prioritizing newly-
discovered and hard-to-reach code. We apply this penalty using the chain rule
on the joint probability between the reward at the next time step
$\tilde{r}_{k}^{(t+1)}$ and the probability of the fuzzer selecting an input
covering feature $k$, $\hat{\theta}_{k}^{(t)}$:

(9) $p(\tilde{r}_{k}^{(t+1)}=1|\theta=\hat{\theta}^{(t)}_{k})\propto
p(\theta=\hat{\theta}^{(t)}_{k}|\tilde{r}_{k}^{(t+1)}=1)p(\tilde{r}_{k}^{(t+1)}=1),$

where $\tilde{r}_{k}^{(t+1)}$ is the predicted reward at the next time step.

Eq. 9 is a binary classification with dependent variables. Here, the
conditional probability with dependent variable $\tilde{r}_{k}^{(t+1)}=1$ is
drawn from Eq. 8, and the constraint for rareness applied by the marginal
probability of $\tilde{r}_{k}^{(t+1)}=1$ is

(10) $\psi_{k}^{(t)}\sim
p(\tilde{r}_{k}^{(t+1)}=1)=\mathrm{Beta}\left(\alpha_{k}^{(t)}+\beta_{k}^{(t)},\left(\alpha_{k}^{(t)}\right)^{2}\right).$

The conditional probability
$p(\hat{\theta}^{(t)}_{k}|\tilde{r}_{k}^{(t+1)}=1)$ represents the probability
action $a_{k}$ selects an $\iota$ that will discover new behaviors. The
marginal probability $p(\tilde{r}_{k}^{(t+1)}=1)$ applies a constraint
penalizing features in the coverage map with a high hit count, thus
prioritizing under-explored code. Eq. 11 shows this:

(11)
$\phi^{(t)}_{k}=\mathbb{E}[p(\tilde{r}_{k}^{(t+1)}=1)]=\frac{\alpha^{(t)}_{k}+\beta^{(t)}_{k}}{\left(\alpha^{(t)}_{k}\right)^{2}+\alpha^{(t)}_{k}+\beta^{(t)}_{k}}.$

For $\alpha_{k}>>\beta_{k}$, then
$\phi^{(t)}_{k}\rightarrow\frac{1}{\alpha_{k}}$; i.e., a penalty is applied if
the input is selected too frequently. Similarly, for $\beta_{k}>>\alpha_{k},$
then $\phi^{(t)}_{k}\rightarrow 1$; i.e., the penalty is removed if the input
is infrequently chosen. This prioritizes rare features in $\mathcal{C}$.

The correction factor is self-balancing: if less-explored favored inputs fail
to discover any new inputs then $\beta_{k}\rightarrow\infty$ and
$\phi^{(t)}_{k}\rightarrow 1$. After each time step, $\phi_{k}$ progressively
removes the penalty if the fuzzer fails to discover any new interesting
behavior. This allows $\theta_{k}$ to dominate the seed scheduling process.
Similarly, $\phi_{k}$ dominates if new behaviors are quickly discovered.

###  3.5. Input Selection

A fuzzer must balance exploration and exploitation when selecting the “best”
input to fuzz. Thompson sampling draws a value from $K$ Beta distributions
(Eq. 8), then selects the next input to fuzz from the posterior distribution
(Eq. 5). Importantly, sampling a distribution generates a new distribution,
enabling both exploration and exploitation.

Here, we present two approaches for selecting the next input to fuzz: input
selection without and with rareness correction (Sections 3.3 and 3.4,
respectively). This enables us to evaluate rareness correction’s impact on
fuzzing outcomes (Section 4.5).

We express input selection _without_ rareness correction by sampling directly
from Eq. 8; i.e.,

(12)
$a^{(t+1)}=\arg\max[\hat{\theta}^{(t)}_{1},\ldots,\hat{\theta}^{(t)}_{K}].$

After applying rareness correction, we express input selection as

(13)
$a^{(t+1)}=\arg\max[\psi^{(t)}_{1}\hat{\theta}^{(t)}_{1},\ldots,\psi^{(t)}_{K}\hat{\theta}^{(t)}_{K}],$

where $\psi^{(t)}_{k}$ is computed by Eq. 10. The action $a^{(t+1)}$ is then
used to select the next input from the set of favored inputs (Algorithm 1,
Algorithm 1). Intuitively the parameter $a^{(t+1)}$ represents the index of an
edge with the highest scheduling probability ($\theta_{k}$ or $\bar{p}$) for
each time-step (e.g., for $t=4$ in Fig. 2, $a^{(t+1)}$ will select an input
that has covered Line 3 because $\bar{p}=0.31$ is the highest). An alternate
formulation can be made by setting $\psi^{(t)}_{k}$ to the expected value
$\phi^{(t)}_{k}$ in Eq. 11.

##  4\. Evaluation

We evaluate T-Scheduler over 35CPU- of fuzzing, comparing it to four fuzzers
and 11 schedulers across 35 programs from the Magma (Hazimeh et al., 2020) and
FuzzBench (Metzman et al., 2021) benchmarks. Our evaluation aims to answer the
following research questions:

  1. RQ 1

Does T-Scheduler improve bug discovery? (Section 4.2)

  2. RQ 2

Does T-Scheduler improve code coverage? (Section 4.3)

  3. RQ 3

What are the run-time costs of T-Scheduler? (Section 4.4)

  4. RQ 4

How do T-Scheduler’s design choices impact fuzzing outcomes? (Section 4.5)

###  4.1. Methodology

##### Fuzzer Selection

We evaluate three T-Scheduler variants:

Rare$-$:

No rareness correction (Eq. 12).

Rare$+$:

Rareness correction via the expected value (i.e., with
$\psi_{k}^{(t)}:=\phi_{k}^{(t)}$ in Eq. 13).

Sample:

Rareness correction via sampling (Eq. 13).

All three variants are implemented in AFL++ (v4.01a) (Fioraldi et al., 2020).
We build on AFL++—rather than AFL (Zalewski, 2015)—because it incorporates
state-of-the-art fuzzing improvements that T-Scheduler can leverage. Rare$+$
deterministically selects the next input by computing the model’s expected
value. In contrast, Sample probabilistically selects the next input by drawing
samples from the model’s distribution.

To emphasize T-Scheduler’s generality, we evaluate it against four fuzzers
using two instrumentation schemes: LLVM compiler and QEMU binary. While QEMU
significantly reduces fuzzer iteration rates, it is important to understand
fuzzer performance when source code is not available. Importantly, this
reduction is consistent across all fuzzers, so does not (dis)advantage any
particular fuzzer. We select fuzzers using LLVM to answer RQ 1 and fuzzers
using QEMU to answer RQ 2. These fuzzers are:

AFL++ (v4.01a) (Fioraldi et al., 2020):

The current state-of-the-art greybox fuzzer. We run AFL++ with eight supported
power schedules (Fioraldi et al., 2020): the six AFLFast (Böhme et al., 2016)
schedules (EXPLORE, FAST, COE, QUAD, LIN, and EXPLOIT), and AFL++’s MMOPT
(increases the score for new inputs to focus on newly-discovered paths) and
RARE (ignores the input’s run-time and focuses on inputs covering rarely-
discovered features). We use AFL++ to answer both RQs 1 and 2. For RQ 1 we use
LLVM’s link-time optimization and also fuzz with an additional
“CmpLog”-instrumented target (for logging comparison operands (Aschermann et
al., 2019)).

K-Scheduler (She et al., 2022):

Schedules inputs based on _Katz centrality_ (Katz, 1953) analysis of the CFG.
Katz centrality measures the “influence” of an input. This analysis helps seed
scheduling by revealing the potential coverage gains from mutating a
particular input. The AFL based K-Scheduler is implemented using LLVM’s CFG
analysis, so we use it to answer RQ 1.

TortoiseFuzz (Wang et al., 2020b):

Introduces three new coverage metrics for input scheduling operating on the
function, loop, and basic block levels. TortoiseFuzz uses prior information on
memory operations to gain further insights in prioritizing seeds leading to
memory corruption bugs. This focus on memory corruption bugs and reliance on
LLVM analyses means we use the AFL based TortoiseFuzz to answer RQ 1.

AFL-Hier (Wang et al., 2021a):

Combines a hierarchy of coverage metrics (ranging from coarse-grained to fine-
grained) and an RL-based hierarchical seed scheduler for managing clusters of
inputs (preventing fine-grained coverage metrics from flooding the queue). The
AFL based AFL-Hier’s hierarchy of coverage metrics is implemented in QEMU, and
thus we use it to answer RQ 2.

##### Benchmark Selection

We evaluate these fuzzers on the Magma and FuzzBench benchmarks. At the time
of writing, FuzzBench’s libxml and libpcap failed to download. Thus, we omit
these two targets from our evaluation. K-Scheduler also failed to construct
CFGs for (and thus fuzz) php and poppler.

##### Experimental Setup

Each target is fuzzed for 72 and repeated ten times to ensure statistically-
sound results. We bootstrap each target with the default seeds provided by the
benchmark. We conduct all experiments on a server with a 48-core Intel® Xeon®
Gold 5118 2.30 CPU, 512 of RAM, and running Ubuntu 18.04.

###  4.2. Bug Discovery (RQ 1)

The ultimate goal of fuzzing is to find bugs. To this end, we evaluate the
LLVM-based fuzzers presented in Section 4.1 on the Magma benchmark
($\mathord{>}\qty{16}{CPU\textrm{-}}$ of fuzzing). Magma distinguishes between
bugs _reached_ and _triggered_. A bug is reached when “the faulty line of code
is executed” (i.e., control-flow constraints are met) and triggered when “the
fault condition is satisfied” (i.e., data-flow constraints are met). We focus
on triggering bugs (not just reaching them) and say that fuzzer/scheduler
$\mathcal{F}_{1}$ outperforms $\mathcal{F}_{2}$ on a given bug if  (a)
$\mathcal{F}_{1}$finds the bug and $\mathcal{F}_{2}$ does not, or  (b)
$\mathcal{F}_{1}$finds the bug faster than $\mathcal{F}_{2}$.

Table 1. Summary of Magma bug-finding results (across 10 trials). Count =
number of bugs found in a target. Total = number of bugs found across all
targets. Best = number of times a fuzzer found the most bugs in a given
target. Unique = number of bugs found in any of the ten trials. Fastest =
number of times a fuzzer found a bug first (per the restricted mean survival
time (Arcuri and Briand, 2011) and log-rank test (Mantel, 1966)). Missed =
number of times a fuzzer failed to find a bug across all ten trials.
Consistency = mean number of unique bugs found per trial (i.e., total / unique
/ # trials). The best-performing fuzzer(s) for each metric is in green.
Targets that failed to build or run with the given fuzzer are marked with ✗.
Full results are presented in Appendix A.

Fuzzer AFL++ T-Scheduler Target Driver EXPLORE FAST COE QUAD LIN EXPLOIT MMOPT
RARE K-Sched Tortoise Rare$-$ Rare$+$ Sample libpng libpng_read_fuzzer 23 29
25 24 17 30 24 23 11 11 19 18 18 libsndfile sndfile_fuzzer 70 70 70 70 70 70
70 70 28 20 70 70 70 tiff_read_rgba_fuzzer 36 34 35 31 32 35 37 34 20 17 37 33
35 libtiff tiffcp 49 49 48 43 43 50 49 52 41 34 53 48 49
xml_read_memory_fuzzer 31 34 34 30 34 30 40 31 10 10 30 34 35 libxml2 xmllint
27 25 28 22 25 20 27 24 13 10 27 28 31 lua lua 10 10 10 10 6 9 9 10 10 9 13 11
11 asn1 18 20 19 18 18 20 20 19 11 10 20 20 20 client 10 10 10 10 10 10 10 10
10 3 10 10 10 server 10 10 10 10 10 10 10 10 20 20 18 18 16 openssl x509 0 1 1
0 0 3 0 4 0 8 0 0 0 php exif 16 19 18 14 14 26 18 20 ✗ 30 30 30 30 pdf_fuzzer
32 27 27 25 25 31 30 30 ✗ 20 33 32 34 pdfimages 35 42 40 29 25 32 38 32 ✗ 16
34 35 38 poppler pdftoppm 42 42 46 28 30 32 46 37 ✗ 20 38 40 37 Count sqlite3
sqlite3_fuzz 45 50 38 29 49 33 42 39 2 0 36 41 43 Total 454 472 459 393 408
441 471 445 176 238 468 468 477 Best 2 5 3 2 2 4 6 2 2 3 7 4 6 Unique 63 63 65
54 61 59 63 60 24 29 62 63 65 Fastest 11 10 4 6 8 7 9 4 1 3 7 5 11 Missed 15
15 13 24 17 19 15 18 54 49 16 15 13 Consistency 0.72 0.75 0.71 0.73 0.67 0.75
0.75 0.74 0.73 0.82 0.75 0.73 0.73

Table 1 shows that Sample was the best-performing scheduler across four out of
five (80) of our bug-finding metrics (“total”, “unique”, “fastest”, and
“missed”), while Rare$-$ scored the highest on the remaining metric (“best”).
Of the eight AFL++ schedulers, FAST found the most bugs (“total” = 472) and
was the second-best performer across the “best”, “unique”, “fastest”, and
“missed” metrics (after MMOPT, COE, EXPLORE, and COE, respectively). These
results reinforce the AFL++ developers’ decision to make FAST the default
scheduler. Notably, the EXPLOIT scheduler (the original AFL’s scheduler) was
one of the worst performers (e.g., it was the third worst performer in missed
bugs).

COE found more unique bugs (65) than Rare$-$ (62) and Rare$+$ (63). However,
the higher “total” results across the T-Scheduler variants suggest that
T-Scheduler produces more-consistent bug-finding results. We reinforce this
result with a “consistency” metric, defined as the total number of bugs
divided by the number of unique bugs averaged across all ten trials. Based on
this metric, Rare$-$ outperformed or performed as well as all AFL++
schedulers. That is, the number of bugs discovered by T-Scheduler remains
consistent as the number of trials decreases.

All three T-Scheduler variants outperformed K-Scheduler and TortoiseFuzz—two
state-of-the-art schedulers—across four of the five (80) bug-finding metrics
(“total”, “best”, “unique”, and “missed”). Sample (the best-performing
T-Scheduler variant) outperformed or performed as well as K-Scheduler on 11
out of 12 drivers (we exclude php and poppler because they failed to build).
Similarly, Sample outperformed or performed as well as TortoiseFuzz on 14 out
of 16 drivers. We examine these results in the following sections.

####  4.2.1. K-Scheduler Comparison

Of the 35 bugs found by Sample or K-Scheduler, the former:  (i) outperformed
K-Scheduler on 27 bugs;  (ii) performed as well as K-Scheduler on six bugs;
and  (iii) was outperformed by K-Scheduler on two bugs.  Notably, K-Scheduler
failed to discover 16 of the 27 (59) bugs where T-Scheduler outperformed
K-Scheduler. Moreover, K-Scheduler was, on average, $\mathord{\sim}$$50\times$
slower at finding the remaining ten bugs. We attribute these results to
K-Scheduler prioritizing “exploration” over “exploitation”. Prior work on
directed greybox fuzzing (Böhme et al., 2017; Wang and Zhou, 2020; Zheng et
al., 2022) has shown that fuzzers must both “explore” interesting code and
“exploit” specific data-flow conditions to trigger bugs.444This is an
unfortunate overloading of terms, and should not be confused with a MAB’s
exploration and exploitation phases. Concentrating on CFG expansion means that
K-Scheduler does not focus on this exploitation phase, potentially harming bug
discovery.

##### Finding: TIF009

One exception to these results is TIF009, which K-Scheduler found after 3.29
(mean time over ten trials). In comparison, Rare$-$, Rare$+$, and Sample found
it after 14.31;33.37;33.77, respectively (4–10$\times$ slower). TIF009
(CVE-2019-7663 (NIST, 2019)) is a NULL pointer dereference located in
TIFFWriteDirectoryTagTransferfunction. This vulnerable function is reachable
via TIFFWriteDirectory when the TransferFunction field is set in a TIFF
directory entry (Adobe, 1992), and the bug is triggered when the transfer
function pointers are NULL.

K-Scheduler and T-Scheduler trigger the bug within 3120 of reaching it,
suggesting the bug does not require satisfying complex data-flow constraints
(which pure mutational fuzzers—e.g., AFL++—may have difficulty satisfying).
Moreover, multiple inputs from the initial seed set reach TIFFWriteDirectory
without _any_ mutation. Ultimately, K-Scheduler’s centrality score led it to
the vulnerable function faster because it prioritized inputs that explored
TIFFWriteDirectory, which had a relatively high centrality score (0.288). In
comparison, neighboring CFG nodes had significantly lower centrality scores
(0.047; while the median centrality score was 0.22). The relatively-simple
data-flow constraints (a struct field set to NULL) meant that K-Scheduler’s
prioritization of exploration over exploitation was an advantage.

####  4.2.2. TortoiseFuzz Comparison

37 of the 55 (67) bugs discovered across all 13 fuzzers/schedulers were memory
safety bugs (e.g., stack/heap buffer overflow/over-read, NULL pointer
dereference). Thus, we expected TortoiseFuzz to demonstrate superior results
in discovering these bugs (due to its design targeting memory safety bugs).
However, TortoiseFuzz was outperformed by the other fuzzers/schedulers (in
particular, T-Scheduler): it failed to trigger 20 of the 37 (54) memory safety
bugs in _any_ trial, and was slower at triggering another eight. TortoiseFuzz
was outperformed by Rare$-$, Rare$+$, and Sample on 51, 53, and 58 bugs,
respectively.

Notably TortoiseFuzz and K-Scheduler use a different set of heuristics based
on the assumption that inputs reaching specific target sites are more likely
to induce new program behaviors. TortoiseFuzz prioritizes memory-sensitive
bugs allowing it to detect several memory-sensitive bugs earlier such as
TIF009, SSL009, and PDF010. In contrast, T-Scheduler heuristics are derived
from the assumption that  (a) information derived from previous test cases can
be used to improve input scheduling in the future, and  (b) it is beneficial
to spend resources on paths less explored to gain more information about the
program to improve input scheduling.  A potential improvement is to extend the
model to be a directed greybox fuzzing where they have a different set of
assumptions where the scheduler should prioritize specific sites such as
memory-sensitive functions which are more likely to induce new program
behaviors.

##### Finding: sqlite3

TortoiseFuzz failed to find any bugs in sqlite3. In contrast, Rare$-$ found
seven bugs, while Rare$+$ and Sample found eight. This was due to the limited
coverage expanded by TortoiseFuzz: it achieved only $\mathord{\sim}$7 line
coverage, while Sample achieved $\mathord{>}\qty{50}{}$ line coverage. We
attribute this low coverage to TortoiseFuzz’s iteration rate: only 58 . In
contrast, T-Scheduler achieved an iteration rate $\mathord{>}\qty{450}{\per}$.
This reinforces the importance of reducing run-time overheads to maximize
throughput.

Sample was the (equal) best performer across the most (four out of five) bug-
finding metrics: it found the most unique bugs, was the fastest, and missed
the fewest bugs. Rare$-$ outperformed in the “best” metric.

###  4.3. Code Coverage (RQ 2)

Bugs are sparse, making it challenging to evaluate fuzzers fairly using bug-
centric metrics. Fuzzer evaluations commonly use code coverage as a proxy for
evaluating fuzzer performance (a bug cannot be found in code never executed).
We repeat this practice here.

We compare coverage using QEMU binary instrumentation on 19 FuzzBench targets
($\mathord{>}\qty{19}{CPU\textrm{-}}$ of fuzzing). Comparisons are made across
two measures: final coverage and coverage area under curve (AUC). Coverage is
measured using Clang’s source-based coverage instrumentation (Clang Team,
2022). We use AUC because we found several targets had maximized coverage
before the end of a 72 trial. A higher AUC indicates that the fuzzer uncovers
behaviors at a faster rate, which is important if the length of a fuzzing
campaign is constrained. We use the Mann-Whitney $U$ test to determine
statistical significance (Klees et al., 2018).

Table 2. FuzzBench coverage, presented as mean coverage with 95 bootstrap CI.
The best-performing fuzzer(s) for each target (per the Mann-Whitney $U$ test)
is in green (larger is better). “Best” is the number of targets a fuzzer
achieved the highest coverage.

Fuzzer AFL++ T-Scheduler Target EXPLORE FAST COE QUAD LIN EXPLOIT MMOPT RARE
AFL-Hier Rare$-$ Rare$+$ Sample $5,884.70$ $5,767.60$ $5,998.50$ $5,514.40$
$5,794.30$ $6,069.50$ $5,944.10$ $5,935.50$ $6,113.20$ $5,918.20$ $6,001.70$
$6,069.20$ bloaty $\,\pm\,109.18$ $\,\pm\,97.83$ $\,\pm\,74.35$
$\,\pm\,131.59$ $\,\pm\,108.91$ $\,\pm\,61.48$ $\,\pm\,141.67$ $\,\pm\,88.13$
$\,\pm\,126.46$ $\,\pm\,41.84$ $\,\pm\,47.54$ $\,\pm\,47.18$ $18,968.10$
$16,778.90$ $19,375.40$ $18,738.90$ $18,660.50$ $18,204.40$ $19,164.40$
$18,712.20$ $13,370.10$ $16,795.20$ $16,776.30$ $16,786.00$ curl
$\,\pm\,46.26$ $\,\pm\,35.11$ $\,\pm\,45.64$ $\,\pm\,149.82$ $\,\pm\,64.69$
$\,\pm\,148.61$ $\,\pm\,72.55$ $\,\pm\,88.77$ $\,\pm\,9.31$ $\,\pm\,124.08$
$\,\pm\,53.54$ $\,\pm\,79.30$ $14,396.00$ $14,585.80$ $16,419.70$ $13,836.00$
$14,246.40$ $15,609.50$ $15,053.80$ $15,364.90$ $14,598.80$ $15,860.40$
$16,018.10$ $15,734.60$ freetype2 $\,\pm\,197.46$ $\,\pm\,356.16$
$\,\pm\,181.27$ $\,\pm\,272.73$ $\,\pm\,204.66$ $\,\pm\,275.23$
$\,\pm\,399.48$ $\,\pm\,201.14$ $\,\pm\,924.03$ $\,\pm\,171.62$
$\,\pm\,219.93$ $\,\pm\,176.92$ $7,642.40$ $7,550.50$ $7,777.10$ $7,333.60$
$7,222.30$ $7,470.00$ $7,640.00$ $7,560.30$ $6,616.10$ $7,727.60$ $7,577.60$
$7,663.00$ harfbuzz $\,\pm\,118.41$ $\,\pm\,104.96$ $\,\pm\,58.23$
$\,\pm\,144.77$ $\,\pm\,115.52$ $\,\pm\,71.30$ $\,\pm\,101.47$ $\,\pm\,70.59$
$\,\pm\,317.23$ $\,\pm\,31.45$ $\,\pm\,35.36$ $\,\pm\,24.29$ $639.00$ $639.00$
$639.00$ $639.00$ $639.00$ $636.00$ $639.00$ $639.00$ $545.10$ $639.00$
$639.00$ $639.00$ jsoncpp $\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.00$
$\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.00$
$\,\pm\,56.91$ $\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.00$ $1,227.20$ $1,223.80$
$1,317.10$ $1,235.80$ $1,370.10$ $1,262.00$ $1,224.70$ $1,235.30$ $2,293.22$
$1,254.70$ $1,233.40$ $1,251.40$ lcms $\,\pm\,0.58$ $\,\pm\,1.18$
$\,\pm\,17.45$ $\,\pm\,8.95$ $\,\pm\,136.16$ $\,\pm\,16.67$ $\,\pm\,1.83$
$\,\pm\,6.69$ $\,\pm\,135.79$ $\,\pm\,11.71$ $\,\pm\,2.09$ $\,\pm\,13.38$
$3,561.10$ $3,656.60$ $3,745.90$ $3,451.40$ $3,442.40$ $3,140.70$ $3,749.80$
$3,057.90$ $2,909.60$ $3,764.40$ $3,497.00$ $3,517.60$ libjpeg-turbo
$\,\pm\,55.74$ $\,\pm\,49.42$ $\,\pm\,41.05$ $\,\pm\,44.76$ $\,\pm\,21.84$
$\,\pm\,36.43$ $\,\pm\,31.54$ $\,\pm\,11.70$ $\,\pm\,75.03$ $\,\pm\,29.95$
$\,\pm\,47.71$ $\,\pm\,54.57$ $2,089.40$ $2,084.10$ $2,084.50$ $2,076.10$
$2,082.40$ $2,091.40$ $2,097.40$ $2,056.20$ $1,619.00$ $2,079.20$ $2,074.30$
$2,064.10$ libpng $\,\pm\,4.80$ $\,\pm\,5.07$ $\,\pm\,7.94$ $\,\pm\,5.29$
$\,\pm\,6.32$ $\,\pm\,4.53$ $\,\pm\,5.72$ $\,\pm\,7.82$ $\,\pm\,32.11$
$\,\pm\,6.11$ $\,\pm\,6.13$ $\,\pm\,7.27$ $7,698.00$ $7,642.30$ $8,147.80$
$7,659.90$ $7,701.80$ $7,749.20$ $7,652.20$ $7,693.10$ $7,467.10$ $8,025.70$
$7,652.70$ $7,631.20$ mbedtls $\,\pm\,10.83$ $\,\pm\,19.18$ $\,\pm\,17.13$
$\,\pm\,13.89$ $\,\pm\,13.86$ $\,\pm\,13.00$ $\,\pm\,5.68$ $\,\pm\,16.09$
$\,\pm\,100.39$ $\,\pm\,26.42$ $\,\pm\,21.38$ $\,\pm\,24.86$ $13,731.20$
$13,745.80$ $13,750.80$ $13,720.10$ $13,730.30$ $13,754.30$ $13,738.80$
$13,728.60$ $13,695.30$ $13,738.40$ $13,731.80$ $13,735.80$ openssl
$\,\pm\,3.34$ $\,\pm\,3.13$ $\,\pm\,3.72$ $\,\pm\,2.15$ $\,\pm\,4.85$
$\,\pm\,2.10$ $\,\pm\,4.11$ $\,\pm\,4.80$ $\,\pm\,4.64$ $\,\pm\,4.33$
$\,\pm\,3.71$ $\,\pm\,4.42$ $5,643.20$ $5,764.80$ $5,703.10$ $5,364.10$
$5,390.20$ $5,706.60$ $5,740.70$ $5,750.50$ $5,424.22$ $5,802.70$ $5,594.80$
$5,617.40$ openthread $\,\pm\,38.42$ $\,\pm\,20.37$ $\,\pm\,31.87$
$\,\pm\,42.34$ $\,\pm\,59.08$ $\,\pm\,15.50$ $\,\pm\,29.01$ $\,\pm\,32.94$
$\,\pm\,157.82$ $\,\pm\,18.32$ $\,\pm\,79.15$ $\,\pm\,55.67$ $42,342.10$
$42,459.60$ $42,961.10$ $41,627.00$ $41,505.80$ $41,907.40$ $42,364.50$
$42,344.90$ $41,117.30$ $44,736.60$ $42,190.00$ $44,198.10$ php
$\,\pm\,106.95$ $\,\pm\,100.18$ $\,\pm\,61.12$ $\,\pm\,61.70$ $\,\pm\,38.58$
$\,\pm\,109.88$ $\,\pm\,136.80$ $\,\pm\,99.31$ $\,\pm\,534.67$ $\,\pm\,70.01$
$\,\pm\,143.45$ $\,\pm\,73.78$ $5,610.70$ $5,699.10$ $6,579.70$ $5,132.90$
$5,112.60$ $5,310.30$ $5,807.10$ $5,129.00$ $2,320.80$ $6,466.50$ $6,092.50$
$6,132.00$ proj4 $\,\pm\,141.28$ $\,\pm\,76.92$ $\,\pm\,91.73$ $\,\pm\,80.43$
$\,\pm\,54.38$ $\,\pm\,132.76$ $\,\pm\,121.24$ $\,\pm\,86.67$ $\,\pm\,369.80$
$\,\pm\,106.58$ $\,\pm\,205.82$ $\,\pm\,67.97$ $3,506.10$ $3,498.50$
$3,518.00$ $3,486.00$ $3,504.00$ $3,475.70$ $3,502.60$ $3,502.70$ $3,055.30$
$3,530.10$ $3,486.70$ $3,484.50$ re2 $\,\pm\,3.59$ $\,\pm\,4.15$ $\,\pm\,4.18$
$\,\pm\,7.05$ $\,\pm\,1.69$ $\,\pm\,4.83$ $\,\pm\,5.71$ $\,\pm\,6.87$
$\,\pm\,22.87$ $\,\pm\,5.40$ $\,\pm\,7.58$ $\,\pm\,4.90$ $21,191.10$
$21,651.90$ $23,210.00$ $21,281.40$ $21,558.00$ $23,197.10$ $22,097.90$
$22,479.50$ $19,041.60$ $23,301.90$ $22,028.80$ $22,021.20$ sqlite3
$\,\pm\,151.57$ $\,\pm\,306.67$ $\,\pm\,366.46$ $\,\pm\,113.28$
$\,\pm\,159.46$ $\,\pm\,386.04$ $\,\pm\,194.40$ $\,\pm\,127.28$
$\,\pm\,177.51$ $\,\pm\,577.27$ $\,\pm\,78.95$ $\,\pm\,143.47$ $637.60$
$639.40$ $640.00$ $640.00$ $638.20$ $633.40$ $638.80$ $639.40$ $613.56$
$640.00$ $640.00$ $640.00$ systemd $\,\pm\,0.92$ $\,\pm\,0.56$ $\,\pm\,0.00$
$\,\pm\,0.00$ $\,\pm\,1.21$ $\,\pm\,1.57$ $\,\pm\,1.14$ $\,\pm\,0.57$
$\,\pm\,13.21$ $\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.00$ $2,098.40$ $1,991.70$
$2,140.40$ $2,030.90$ $2,061.70$ $2,043.70$ $2,087.10$ $1,986.90$ $1,549.00$
$2,156.30$ $2,073.20$ $2,062.70$ vorbis $\,\pm\,16.27$ $\,\pm\,39.81$
$\,\pm\,8.86$ $\,\pm\,26.69$ $\,\pm\,32.15$ $\,\pm\,17.80$ $\,\pm\,18.38$
$\,\pm\,23.53$ $\,\pm\,0.00$ $\,\pm\,4.42$ $\,\pm\,8.68$ $\,\pm\,22.25$
$1,769.80$ $1,694.40$ $1,841.30$ $1,773.10$ $1,744.60$ $1,731.40$ $1,775.10$
$1,678.00$ $1,498.56$ $1,860.90$ $1,717.60$ $1,699.10$ woff2 $\,\pm\,14.61$
$\,\pm\,13.88$ $\,\pm\,9.47$ $\,\pm\,7.82$ $\,\pm\,14.93$ $\,\pm\,5.95$
$\,\pm\,6.69$ $\,\pm\,8.61$ $\,\pm\,49.29$ $\,\pm\,9.41$ $\,\pm\,5.69$
$\,\pm\,7.14$ $945.40$ $942.20$ $953.80$ $932.80$ $932.20$ $940.20$ $947.20$
$948.50$ $920.30$ $960.10$ $954.90$ $959.40$ zlib $\,\pm\,4.12$ $\,\pm\,5.24$
$\,\pm\,3.91$ $\,\pm\,3.71$ $\,\pm\,3.42$ $\,\pm\,4.81$ $\,\pm\,5.06$
$\,\pm\,5.02$ $\,\pm\,3.69$ $\,\pm\,1.65$ $\,\pm\,4.67$ $\,\pm\,3.49$ Best 3 5
16 2 2 5 6 4 3 13 5 5

Table 3. FuzzBench AUC, presented as mean AUC with 95 bootstrap CI. The best-
performing fuzzer(s) for each target (per the Mann-Whitney $U$ test) is in
green (larger is better). “Best” is the number of times a fuzzer achieved the
highest AUC for the evaluated targets.

Fuzzer AFL++ T-Scheduler Target EXPLORE FAST COE QUAD LIN EXPLOIT MMOPT RARE
AFL-Hier Rare$-$ Rare$+$ Sample $1,855.49$ $1,798.74$ $1,881.75$ $1,739.14$
$1,832.82$ $1,901.46$ $1,860.15$ $1,882.21$ $720.66$ $1,876.27$ $1,903.64$
$1,917.34$ bloaty $\,\pm\,36.81$ $\,\pm\,29.02$ $\,\pm\,21.23$ $\,\pm\,37.05$
$\,\pm\,32.55$ $\,\pm\,18.05$ $\,\pm\,39.57$ $\,\pm\,26.01$ $\,\pm\,88.80$
$\,\pm\,12.40$ $\,\pm\,12.70$ $\,\pm\,12.21$ $5,935.13$ $5,297.44$ $6,128.42$
$5,876.09$ $5,845.46$ $5,685.59$ $5,981.73$ $5,899.21$ $22.31$ $5,270.48$
$5,284.60$ $5,278.60$ curl $\,\pm\,32.79$ $\,\pm\,8.34$ $\,\pm\,21.96$
$\,\pm\,49.73$ $\,\pm\,32.48$ $\,\pm\,42.23$ $\,\pm\,11.66$ $\,\pm\,16.57$
$\,\pm\,4.41$ $\,\pm\,31.77$ $\,\pm\,15.11$ $\,\pm\,23.71$ $4,485.76$
$4,524.82$ $5,026.24$ $4,316.93$ $4,433.65$ $4,794.04$ $4,617.88$ $4,691.47$
$1,596.44$ $4,892.82$ $4,911.98$ $4,821.05$ freetype2 $\,\pm\,63.39$
$\,\pm\,102.24$ $\,\pm\,53.00$ $\,\pm\,83.98$ $\,\pm\,52.09$ $\,\pm\,71.91$
$\,\pm\,108.91$ $\,\pm\,37.17$ $\,\pm\,349.75$ $\,\pm\,58.15$ $\,\pm\,46.05$
$\,\pm\,42.39$ $2,367.14$ $2,326.66$ $2,407.32$ $2,270.86$ $2,237.21$
$2,292.35$ $2,358.83$ $2,340.57$ $1,317.19$ $2,425.86$ $2,372.57$ $2,396.13$
harfbuzz $\,\pm\,34.39$ $\,\pm\,31.08$ $\,\pm\,16.32$ $\,\pm\,41.14$
$\,\pm\,30.87$ $\,\pm\,21.88$ $\,\pm\,30.49$ $\,\pm\,21.70$ $\,\pm\,211.41$
$\,\pm\,11.06$ $\,\pm\,13.43$ $\,\pm\,7.54$ $203.63$ $203.23$ $203.71$
$203.54$ $203.69$ $202.66$ $203.46$ $203.49$ $80.35$ $202.70$ $203.39$
$203.27$ jsoncpp $\,\pm\,0.07$ $\,\pm\,0.17$ $\,\pm\,0.05$ $\,\pm\,0.02$
$\,\pm\,0.01$ $\,\pm\,0.02$ $\,\pm\,0.11$ $\,\pm\,0.01$ $\,\pm\,15.07$
$\,\pm\,0.28$ $\,\pm\,0.17$ $\,\pm\,0.15$ $389.70$ $387.03$ $393.74$ $390.46$
$406.59$ $392.60$ $388.93$ $390.42$ $572.34$ $394.88$ $389.15$ $390.45$ lcms
$\,\pm\,0.33$ $\,\pm\,0.57$ $\,\pm\,0.81$ $\,\pm\,0.96$ $\,\pm\,15.81$
$\,\pm\,1.47$ $\,\pm\,0.49$ $\,\pm\,0.46$ $\,\pm\,48.40$ $\,\pm\,1.99$
$\,\pm\,0.57$ $\,\pm\,1.55$ $1,085.49$ $1,096.15$ $1,160.83$ $1,071.70$
$1,072.38$ $973.90$ $1,121.60$ $954.81$ $750.88$ $1,173.16$ $1,064.67$
$1,067.75$ libjpeg-turbo $\,\pm\,9.90$ $\,\pm\,11.33$ $\,\pm\,11.89$
$\,\pm\,8.03$ $\,\pm\,3.32$ $\,\pm\,4.95$ $\,\pm\,12.41$ $\,\pm\,6.06$
$\,\pm\,38.03$ $\,\pm\,11.36$ $\,\pm\,15.36$ $\,\pm\,16.61$ $663.27$ $660.20$
$663.96$ $657.04$ $660.73$ $661.04$ $665.76$ $650.26$ $442.56$ $658.86$
$657.18$ $652.64$ libpng $\,\pm\,1.60$ $\,\pm\,1.99$ $\,\pm\,2.50$
$\,\pm\,2.20$ $\,\pm\,2.07$ $\,\pm\,1.43$ $\,\pm\,1.78$ $\,\pm\,2.72$
$\,\pm\,28.84$ $\,\pm\,2.12$ $\,\pm\,1.97$ $\,\pm\,2.12$ $2,436.35$ $2,419.82$
$2,541.22$ $2,436.52$ $2,446.75$ $2,455.33$ $2,420.35$ $2,436.75$ $1,941.63$
$2,471.21$ $2,428.81$ $2,418.06$ mbedtls $\,\pm\,2.24$ $\,\pm\,5.30$
$\,\pm\,5.61$ $\,\pm\,3.85$ $\,\pm\,3.71$ $\,\pm\,3.24$ $\,\pm\,3.02$
$\,\pm\,3.06$ $\,\pm\,231.06$ $\,\pm\,9.09$ $\,\pm\,6.12$ $\,\pm\,7.74$
$4,369.59$ $4,370.03$ $4,382.95$ $4,372.61$ $4,376.14$ $4,378.27$ $4,373.62$
$4,374.11$ $2,414.84$ $4,355.91$ $4,377.09$ $4,368.88$ openssl $\,\pm\,3.07$
$\,\pm\,4.42$ $\,\pm\,1.09$ $\,\pm\,0.94$ $\,\pm\,1.51$ $\,\pm\,0.70$
$\,\pm\,1.99$ $\,\pm\,2.01$ $\,\pm\,513.73$ $\,\pm\,7.69$ $\,\pm\,1.14$
$\,\pm\,4.03$ $1,748.75$ $1,762.49$ $1,791.13$ $1,668.19$ $1,660.39$
$1,746.66$ $1,790.89$ $1,784.31$ $1,254.70$ $1,825.09$ $1,729.62$ $1,713.15$
openthread $\,\pm\,17.22$ $\,\pm\,12.70$ $\,\pm\,11.93$ $\,\pm\,13.06$
$\,\pm\,19.64$ $\,\pm\,8.34$ $\,\pm\,10.25$ $\,\pm\,6.85$ $\,\pm\,180.57$
$\,\pm\,6.25$ $\,\pm\,21.97$ $\,\pm\,16.16$ $13,390.60$ $13,388.88$
$13,584.21$ $13,194.36$ $13,177.75$ $13,183.46$ $13,389.12$ $13,337.44$
$1,151.67$ $14,016.82$ $13,414.13$ $14,016.68$ php $\,\pm\,31.39$
$\,\pm\,32.36$ $\,\pm\,23.81$ $\,\pm\,9.33$ $\,\pm\,9.90$ $\,\pm\,25.63$
$\,\pm\,36.87$ $\,\pm\,23.16$ $\,\pm\,280.18$ $\,\pm\,19.42$ $\,\pm\,38.98$
$\,\pm\,26.92$ $1,647.87$ $1,670.72$ $2,020.40$ $1,491.32$ $1,467.89$
$1,426.01$ $1,671.35$ $1,327.46$ $436.16$ $1,977.17$ $1,770.04$ $1,785.75$
proj4 $\,\pm\,43.23$ $\,\pm\,28.16$ $\,\pm\,28.88$ $\,\pm\,30.43$
$\,\pm\,23.12$ $\,\pm\,41.85$ $\,\pm\,46.43$ $\,\pm\,30.11$ $\,\pm\,76.83$
$\,\pm\,39.66$ $\,\pm\,66.98$ $\,\pm\,25.78$ $1,107.15$ $1,102.90$ $1,116.69$
$1,097.35$ $1,099.13$ $1,082.91$ $1,103.85$ $1,097.64$ $719.14$ $1,121.36$
$1,100.35$ $1,095.72$ re2 $\,\pm\,1.24$ $\,\pm\,1.06$ $\,\pm\,0.94$
$\,\pm\,1.67$ $\,\pm\,1.17$ $\,\pm\,2.76$ $\,\pm\,1.47$ $\,\pm\,1.79$
$\,\pm\,32.05$ $\,\pm\,1.38$ $\,\pm\,2.12$ $\,\pm\,2.18$ $6,546.16$ $6,549.26$
$6,966.93$ $6,659.31$ $6,684.83$ $6,776.79$ $6,770.59$ $6,917.85$ $3,163.01$
$7,032.32$ $6,862.27$ $6,815.92$ sqlite3 $\,\pm\,37.64$ $\,\pm\,84.99$
$\,\pm\,70.91$ $\,\pm\,23.54$ $\,\pm\,42.71$ $\,\pm\,62.16$ $\,\pm\,31.57$
$\,\pm\,23.47$ $\,\pm\,228.67$ $\,\pm\,78.15$ $\,\pm\,20.75$ $\,\pm\,31.30$
$202.70$ $202.93$ $204.00$ $202.95$ $202.97$ $200.68$ $202.86$ $202.53$
$148.28$ $203.38$ $203.29$ $203.16$ systemd $\,\pm\,0.37$ $\,\pm\,0.20$
$\,\pm\,0.02$ $\,\pm\,0.25$ $\,\pm\,0.41$ $\,\pm\,0.33$ $\,\pm\,0.45$
$\,\pm\,0.28$ $\,\pm\,26.43$ $\,\pm\,0.28$ $\,\pm\,0.16$ $\,\pm\,0.26$
$621.37$ $597.84$ $655.33$ $613.50$ $618.62$ $627.95$ $624.02$ $616.59$ $2.07$
$669.33$ $625.59$ $625.32$ vorbis $\,\pm\,4.06$ $\,\pm\,3.77$ $\,\pm\,2.96$
$\,\pm\,4.78$ $\,\pm\,4.97$ $\,\pm\,4.83$ $\,\pm\,5.24$ $\,\pm\,5.06$
$\,\pm\,0.22$ $\,\pm\,1.99$ $\,\pm\,4.40$ $\,\pm\,4.44$ $540.76$ $528.67$
$564.95$ $549.08$ $543.36$ $540.87$ $541.73$ $526.76$ $197.68$ $580.63$
$538.27$ $533.78$ woff2 $\,\pm\,1.79$ $\,\pm\,2.04$ $\,\pm\,2.12$
$\,\pm\,1.01$ $\,\pm\,3.23$ $\,\pm\,1.03$ $\,\pm\,1.71$ $\,\pm\,1.75$
$\,\pm\,73.95$ $\,\pm\,2.47$ $\,\pm\,1.04$ $\,\pm\,1.61$ $299.20$ $298.56$
$301.50$ $296.07$ $295.10$ $291.20$ $300.56$ $299.10$ $273.63$ $302.06$
$301.07$ $302.36$ zlib $\,\pm\,1.05$ $\,\pm\,1.48$ $\,\pm\,1.22$ $\,\pm\,0.77$
$\,\pm\,0.50$ $\,\pm\,0.75$ $\,\pm\,1.34$ $\,\pm\,1.35$ $\,\pm\,10.12$
$\,\pm\,1.34$ $\,\pm\,1.26$ $\,\pm\,1.04$ Best 4 2 13 0 0 2 4 3 1 13 4 3

Per Table 2, AFL++’s COE achieved the (equal) highest coverage on 16 of the 19
targets (84). Of the T-Scheduler variants, Rare$-$ achieved the highest
coverage on 13 targets (68) and was the next best performer after COE. Rare$+$
and Sample performed similarly (equal best on five targets). Rare$+$’s smaller
95 bootstrap CI indicates less variance (across trials); we attribute this to
Rare$+$’s deterministic approach for rareness correction. AFL-Hier was the
third worst performing fuzzers (only beating QUAD and LIN, and tying with
EXPLORE). Curiously, it was the best performer on lcms, achieving twice as
much coverage as the next best fuzzer.

COE was again the (equal) best performer for AUC (Table 3). However, this time
it also tied with Rare$-$. Following Böhme et al. (2022), we use Cohen’s kappa
(Cohen, 1960) to measure the agreement between total coverage and AUC of the
best-performing fuzzer(s). We found the results in Tables 2 and 3 are in weak
agreement ($\kappa=0.56$). Outliers including jsoncpp, openssl, and systemd
contributed to this weak agreement. For example, Rare$-$ outperformed Rare$+$
and Sample on openssl in Table 2, while the opposite is true in Table 3. These
results were due to inaccurate AUC measurements: coverage measurements occur
at 15 intervals, and all fuzzers had saturated within the first 15.

COE achieved the (equal) highest coverage on 16 of the 19 targets (84).
Rare$-$ tied with COE when using AUC.

###  4.4. Scheduler Overheads (RQ 3)

Scheduler overhead impacts a fuzzer’s iteration rate. Prior work (Xu et al.,
2017; Herrera et al., 2021) has shown that increased iteration rates lead to
improved fuzzing outcomes. Here we investigate the scheduler’s impact on
iteration rates and fuzzing outcomes. To measure this impact, we:  (i)
instrument the scheduler to compute run-time overhead, recording the time the
fuzzer spends updating the queue and selecting an input to fuzz;  (ii) count
the number of times the queue is updated (i.e., the number of times the fuzzer
performs “filtering and favoring”); and  (iii) examine the iteration rate
reported by the fuzzer.  We adopt the process used by She et al. (2022) and
run our instrumentation across 19 FuzzBench targets for 24, repeating this
experiment ten times to minimize variance.

Table 4. Scheduler overheads and iteration rates with 95 bootstrap CI. Update
count = number of times the queue is updated in a single trial (geometric
mean). Update time = time spent (ms) on each queue update (arithmetic mean).
Update variance = how much the queue update time varies (ms2) in a single
trial (arith. mean). Overhead = total time (s) the fuzzer spends selecting an
input to fuzz in a trial (arith. mean). Iteration rate = number of inputs
executed per second (arith. mean).

Fuzzer AFL++ T-Scheduler EXPLORE FAST COE QUAD LIN EXPLOIT MMOPT RARE AFL-Hier
Rare$-$ Rare$+$ Sample $269.97$ $873.86$ $283.12$ $328.12$ $590.47$ $80.03$
$281.25$ $124.42$ $88.84$ $672.38$ $649.44$ $635.84$ Update count (#)
$\,\pm\,44.62$ $\,\pm\,156.92$ $\,\pm\,46.29$ $\,\pm\,57.84$ $\,\pm\,135.07$
$\,\pm\,7.91$ $\,\pm\,46.43$ $\,\pm\,17.73$ $\,\pm\,17.17$ $\,\pm\,87.68$
$\,\pm\,86.14$ $\,\pm\,81.63$ $14.96$ $9.29$ $9.52$ $15.17$ $16.77$ $29.88$
$15.62$ $39.77$ $106.55$ $41.76$ $42.05$ $79.83$ Update time (ms)
$\,\pm\,3.47$ $\,\pm\,1.32$ $\,\pm\,1.30$ $\,\pm\,3.26$ $\,\pm\,7.29$
$\,\pm\,7.25$ $\,\pm\,2.83$ $\,\pm\,7.99$ $\,\pm\,23.59$ $\,\pm\,0.09$
$\,\pm\,0.11$ $\,\pm\,0.23$ $0.40$ $0.01$ $0.00$ $0.09$ $0.12$ $0.11$ $0.04$
$0.52$ $0.75$ $0.00$ $0.00$ $0.00$ Update variance (ms2) $\,\pm\,0.37$
$\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.04$ $\,\pm\,0.10$ $\,\pm\,0.06$
$\,\pm\,0.02$ $\,\pm\,0.32$ $\,\pm\,0.51$ $\,\pm\,0.00$ $\,\pm\,0.00$
$\,\pm\,0.00$ $57.84$ $85.35$ $49.34$ $58.18$ $62.00$ $49.18$ $56.38$ $64.13$
$207.68$ $2,488.36$ $2,419.26$ $4,443.65$ Overhead (s) $\,\pm\,9.32$
$\,\pm\,11.90$ $\,\pm\,7.66$ $\,\pm\,9.37$ $\,\pm\,9.23$ $\,\pm\,7.02$
$\,\pm\,8.71$ $\,\pm\,10.14$ $\,\pm\,47.91$ $\,\pm\,319.63$ $\,\pm\,317.35$
$\,\pm\,559.37$ $83.52$ $210.19$ $85.06$ $89.26$ $87.61$ $99.86$ $89.42$
$58.52$ $84.84$ $96.79$ $94.46$ $93.60$ Iteration rate (inputs/s)
$\,\pm\,13.33$ $\,\pm\,39.23$ $\,\pm\,12.20$ $\,\pm\,16.73$ $\,\pm\,15.89$
$\,\pm\,16.94$ $\,\pm\,13.30$ $\,\pm\,9.79$ $\,\pm\,17.28$ $\,\pm\,16.75$
$\,\pm\,16.36$ $\,\pm\,16.67$

Table 4 shows that, despite an orders-of-magnitude increase in overhead,
T-Scheduler achieves iteration rates comparable to (and, in most cases, higher
than) the eight AFL++ schedulers. Of the eight AFL++ schedulers, FAST had the
highest overhead (85), which we attribute to the high number of queue updates
(873 over a single 24 trial). However, this again did not impact iteration
rates; FAST’s iteration rate of 210 was the highest. The libpng and zlib
targets dominated this result, achieving iteration rates over 500;700 ,
respectively.

Unlike T-Scheduler, AFL-Hier’s relatively high update time (106) and overhead
(3) appeared to impact its iteration rate, which was the third lowest. We
attribute these results to the hierarchical tree structure AFL-Hier uses to
abstract the queue.

####  4.4.1. Scalability

Queue update times should remain constant (per trial) as the fuzzer expands
coverage and the queue grows. This is particularly important for large fuzzing
campaigns (e.g., Google’s OSS-Fuzz (Serebryany, 2017)), where the queue can
grow to tens of thousands of inputs. To this end, we investigate a scheduler’s
scalability by examining how much queue update times vary (across a single 24
trial). Table 4 shows these results under “update variance”.

Like queue update time, queue update time variance is negligible. T-Scheduler
has effectively no variance, making it ideal for long-running fuzzing
campaigns. AFL-Hier and AFL++’s RARE have the highest variance. This is
unsurprising; RARE focuses on queue entries that hit rare coverage map
elements, requiring additional computation to find those rare elements, while
operations on AFL-Hier’s hierarchical tree structure have $\mathcal{O}(n)$
complexity.

T-Scheduler maintains high iteration rates, despite increased scheduling
overheads. T-Scheduler is also scalable: queue update times remain constant
over fuzzing campaigns.

###  4.5. Ablation Study (RQ 4)

We undertake an ablation study to understand better the impacts the individual
T-Scheduler components have on our results. We study:  (i) AFL++ FAST;  (ii)
Rare$-$, replacing the FAST scheduler with a MAB; and  (iii) Sample, adding a
correction for rareness.  We select FAST because it is AFL++’s default
scheduler, and Sample because it generally outperforms Rare$+$ (RQs 1 and 2).

2Rare$-$ 5FAST4Sample 25353 Figure 4. Venn diagram of unique bug count between
AFLFast, Rare$-$, and Sample (74 unique bugs found across all drivers).

Figure 4 visualizes the unique bug counts from Table 1. FAST found 63 unique
bugs, of which five were only found by FAST. Replacing FAST with Rare$-$
decreased the number of unique bugs to 62. However, Rare$-$ found two bugs
missed by the other two schedulers. When adding rareness correction (via
Sample) to Rare$-$, the number of bugs increased to 65. Moreover, four of
these 65 bugs were only found by Sample, and were found  (a) late into the
fuzzing process (after $\mathord{\sim}$60), and  (b) by only a small number of
fuzzers/schedulers,  suggesting they are difficult to trigger.

Sample’s bug-finding performance improved towards the end of the fuzzing
campaign (here, after 45 of fuzzing), triggering nine bugs that were missed by
FAST. Three of these bugs (XML001, XML002, and PDF011) are buffer overflow
bugs in functions that are frequently covered by FAST. FAST assigns higher
priority to an input depending on the number of times it covers an edge, while
penalizing inputs that cover paths with high frequency (Böhme et al., 2016).
This is a limitation of FAST, as a high-frequency path does not necessarily
mean a lower chance of discovering new program behavior. T-Scheduler does not
apply a penalty to high-frequency paths if previously scheduled inputs have
discovered new program behaviors.

Code coverage increased when replacing the FAST scheduler with Rare$-$’s MAB-
based scheduler. Notably, Rare$-$ achieved the (equal) highest coverage on
most FuzzBench targets (Tables 2 and 3). In particular, harfbuzz was the only
target where FAST achieved the most coverage and did not tie with Rare$-$
(Table 2). This is in contrast to bug finding, where Sample outperformed
Rare$-$ (except for the “best” metric in Table 1). We attribute this to
Rare$-$’s single objective (in the RL algorithm) to maximize code coverage. In
contrast, Sample uses a multi-objective optimization that balances exploring
rare paths and maximizing code coverage.

Iteration rates decreased by $\mathord{\sim}$50 when replacing FAST with
Rare$-$ (Table 4). However, this decrease was also true of the other seven
AFL++ schedulers (and was sometimes even more pronounced; up to 72). Sample
increased the scheduler overhead from 40 to 74 (an 84 increase). We attribute
this increase to costs associated with sampling from the Beta distribution
twice (Eq. 13). In contrast, Rare$-$ only samples from it once. However, this
has negligible impact on iteration rates: a reduction of $\mathord{\sim}$1 .
Similarly, the variance across queue update times remains zero when replacing
Rare$-$ with Sample, demonstrating its scalability.

##### To Sample or not to Sample?

Our ablation study focused on Sample, which probabilistically samples for
rareness correction. However, it is worth revisiting Rare$+$—which
deterministically computes an expected value for rareness correction—to
understand what impact the probabilistic approach has on fuzzing outcomes.
Sample outperformed Rare$+$ across all bug-finding metrics (Table 1). Sample
also slightly outperformed Rare$+$ (by a single target) on total coverage
(Table 2) and performed the same on coverage AUC (Table 3). While
probabilistically sampling resulted in higher scheduler overhead, this had a
negligible impact on the fuzzer’s iteration rate (Table 4). In most
applications, the probabilistic approach should outperform a deterministic
approach. Thus, we recommend Sample for general use based on our results.

Accounting for rare coverage elements (with Sample) improves bug-finding
performance (over Rare$-$). However, Rare$-$’s single objective of maximizing
coverage leads to higher coverage. Both improve upon FAST.

##  5\. Related Work

Woo et al. (2013) were one of the first to formulate fuzzing as a MAB. Their
work focused on _blackbox_ fuzzing, where there is no coverage feedback to
guide the fuzzer. Woo et al. (2013) proposed using the exp3 algorithm (Seldin
et al., 2013), with the fuzzer rewarded based on the number of unique bugs
found. However, bugs are sparse, so assigning a reward based on their
discovery is impractical. In contrast, AFLFast (Böhme et al., 2016) focused on
_greybox_ fuzzing, introducing the power schedule for seed scheduling (see
Section 2.2). Entropic (Böhme et al., 2020) expanded this with an entropy-
based power schedule for prioritizing _information gain_.

Prior work has applied MAB to greybox fuzzing. Karamcheti et al. (2018); Koike
et al. (2022) use a MAB over the fuzzer’s mutation operators, while EcoFuzz
(Yue et al., 2020), AFL-Hier (Wang et al., 2021a), and MobFuzz (Zhang et al.,
2022) use a MAB for seed scheduling.

EcoFuzz (Yue et al., 2020) eschews a traditional MAB for an _adversarial
bandit_. While an adversarial bandit removes assumptions about the bandits’
probability distributions, this generality requires more hyperparameters to
tune. In particular, EcoFuzz has two hyperparameters—exploration and decay—and
uses entropy to compute the probability of an input’s (potential) information
gain.

AFL-Hier (Wang et al., 2021a) combines a multiplayer MAB with a hierarchical
tree structure to balance exploration/exploitation across coverage metrics.
Like EcoFuzz, AFL-Hier has two hyperparameters (exploration and decay).
However, unlike EcoFuzz, AFL-Hier rewards rare code paths, encouraging the
scheduler to select inputs that cover less-explored paths.

Finally, MobFuzz (Zhang et al., 2022) uses a multi-objective optimization
formulated as a multiplayer MAB, maximizing three objectives: execution speed,
memory consumption, and the length of memory comparisons. MobFuzz uses a
weighted average of these three objectives to compute the reward for each
input.

##  6\. Conclusions

We present T-Scheduler, an RL-based fuzzer seed scheduler. Unlike prior RL-
based schedulers, T-Scheduler does not require hyperparameter tuning. We
empirically demonstrate T-Scheduler’s effectiveness over 35CPU- of fuzzing. On
Magma, T-Scheduler found the most bugs and missed the fewest. On FuzzBench, it
was the fastest at expanding coverage on the most targets. T-Scheduler also
maintains consistently-high iteration rates (even as the queue grows). Given
our results, we recommend the adoption of our Sample variant. Interestingly,
our results also show that AFL++’s default FAST scheduler was generally
outperformed by the MMOPT scheduler (across both bug-finding and coverage-
expansion metrics). We encourage others to adopt and build upon T-Scheduler,
available at https://github.com/asiaccs2024-t-scheduler.

###### Acknowledgements.

This work was supported by the Defence Science and Technology Group Next
Generation Technologies Fund (Cyber) program via the _KRONOS_ Data61
Collaborative Research Project.

## References

  * (1)
  * Adobe (1992) Adobe. 1992.  TIFF, Revision 6.0.  https://www.loc.gov/preservation/digital/formats/fdd/fdd000022.shtml
  * Agrawal and Goyal (2017) Shipra Agrawal and Navin Goyal. 2017.  Near-Optimal Regret Bounds for Thompson Sampling.  _Jorunal of the ACM_ 64, 5, Article 30 (2017), 24 pages.  https://doi.org/10.1145/3088510
  * Arcuri and Briand (2011) Andrea Arcuri and Lionel Briand. 2011.  A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering. In _International Conference on Software Engineering_ _(ICSE)_. ACM, 1–10.  https://doi.org/10.1145/1985793.1985795
  * Aschermann et al. (2019) Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and Thorsten Holz. 2019\.  REDQUEEN: Fuzzing with Input-to-State Correspondence. In _Network and Distributed System Security_ _(NDSS)_. The Internet Society, 15 pages.  https://doi.org/10.14722/ndss.2019.23371
  * Böhme et al. (2020) Marcel Böhme, Valentin J. M. Manès, and Sang Kil Cha. 2020\.  Boosting Fuzzer Efficiency: An Information Theoretic Perspective. In _European Software Engineering Conference and Foundations of Software Engineering_ _(ESEC/FSE)_. ACM, 678–689.  https://doi.org/10.1145/3368089.3409748
  * Böhme et al. (2017) Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. 2017.  Directed Greybox Fuzzing. In _Computer and Communications Security_ _(CCS)_. ACM, 2329–2344.  https://doi.org/10.1145/3133956.3134020
  * Böhme et al. (2016) Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016.  Coverage-Based Greybox Fuzzing as Markov Chain. In _Computer and Communications Security_ _(CCS)_. ACM, 1032–1043.  https://doi.org/10.1145/2976749.2978428
  * Böhme et al. (2022) Marcel Böhme, László Szekeres, and Jonathan Metzman. 2022.  On the Reliability of Coverage-Based Fuzzer Benchmarking. In _International Conference on Software Engineering_ _(ICSE)_. ACM, 1621–1633.  https://doi.org/10.1145/3510003.3510230
  * Böttinger et al. (2018) Konstantin Böttinger, Patrice Godefroid, and Rishabh Singh. 2018\.  Deep Reinforcement Fuzzing. In _Security and Privacy Workshops_ _(SPW)_. IEEE, 116–122.  https://doi.org/10.1109/SPW.2018.00026
  * Chang (2023) Oliver Chang. 2023\.  Taking the next step: OSS-Fuzz in 2023.  https://security.googleblog.com/2023/02/taking-next-step-oss-fuzz-in-2023.html
  * Chen et al. (2020) Yaohui Chen, Mansour Ahmadi, Reza Mirzazade farkhani, Boyu Wang, and Long Lu. 2020.  MEUZZ: Smart Seed Scheduling for Hybrid Fuzzing. In _Research in Attacks, Intrusions and Defenses_ _(RAID)_. USENIX, 77–92.
  * Cheng et al. (2019) Liang Cheng, Yang Zhang, Yi Zhang, Chen Wu, Zhangtan Li, Yu Fu, and Haisheng Li. 2019.  Optimizing Seed Inputs in Fuzzing with Machine Learning. In _International Conference on Software Engineering: Companion_ _(ICSE)_. IEEE, 244–245.  https://doi.org/10.1109/ICSE-Companion.2019.00096
  * Clang Team (2022) Clang Team. 2022\.  Source-based Code Coverage.  https://clang.llvm.org/docs/SourceBasedCodeCoverage.html
  * Cohen (1960) Jacob Cohen. 1960\.  A Coefficient of Agreement for Nominal Scales.  _Educational and Psychological Measurement_ 20, 1 (1960), 37–46.  https://doi.org/10.1177/001316446002000104
  * Fioraldi et al. (2020) Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. 2020.  AFL++: Combining Incremental Steps of Fuzzing Research. In _Workshop on Offensive Technologies_ _(WOOT)_. USENIX, 12 pages.
  * Godefroid et al. (2017) Patrice Godefroid, Hila Peleg, and Rishabh Singh. 2017\.  Learn&Fuzz: Machine Learning for Input Fuzzing. In _Automated Software Engineering_ _(ASE)_. IEEE, 50–59.
  * Hazimeh et al. (2020) Ahmad Hazimeh, Adrian Herrera, and Mathias Payer. 2020\.  Magma: A Ground-Truth Fuzzing Benchmark.  _Measurement and Analysis of Computing Systems_ 4, 3, Article 49 (2020), 29 pages.  https://doi.org/10.1145/3428334
  * Herrera et al. (2021) Adrian Herrera, Hendra Gunadi, Shane Magrath, Michael Norrish, Mathias Payer, and Antony L. Hosking. 2021\.  Seed Selection for Successful Fuzzing. In _International Symposium on Software Testing and Analysis_ _(ISSTA)_. ACM, 230–243.  https://doi.org/10.1145/3460319.3464795
  * Herrera et al. (2022) Adrian Herrera, Mathias Payer, and Antony L. Hosking. 2022\.  Registered Report: datAFLow Towards a Data-Flow-Guided Fuzzer. In _Fuzzing Workshop_ _(FUZZING)_. The Internet Society, 11 pages.  https://doi.org/10.14722/fuzzing.2022.23001
  * Karamcheti et al. (2018) Siddharth Karamcheti, Gideon Mann, and David Rosenberg. 2018\.  Adaptive Grey-Box Fuzz-Testing with Thompson Sampling. In _Artificial Intelligence and Security_ _(AISec)_. ACM, 37–47.  https://doi.org/10.1145/3270101.3270108
  * Katz (1953) Leo Katz. 1953.  A new status index derived from sociometric analysis.  _Psychometrika_ (1953), 39–43.  https://doi.org/10.1007/BF02289026
  * Klees et al. (2018) George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018.  Evaluating Fuzz Testing. In _Computer and Communications Security_ _(CCS)_. ACM, 2123–2138.  https://doi.org/10.1145/3243734.3243804
  * Koike et al. (2022) Yuki Koike, Hiroyuki Katsura, Hiromu Yakura, and Yuma Kurogome. 2022.  SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzing. In _Proceedings of the 38th Annual Computer Security Applications Conference_ _(ACSAC)_. ACM, 519–533.  https://doi.org/10.1145/3564625.3564659
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári. 2020.  _Bandit algorithms_.  Cambridge University Press.
  * Li et al. (2022) Siqi Li, Xiaofei Xie, Yun Lin, Yuekang Li, Ruitao Feng, Xiaohong Li, Weimin Ge, and Jin Song Dong. 2022\.  Deep Learning for Coverage-Guided Fuzzing: How Far are We?  _Transactions on Dependable and Secure Computing_ (2022), 1–13.  https://doi.org/10.1109/TDSC.2022.3200525
  * Mantel (1966) Nathan Mantel. 1966\.  Evaluation of survival data and two new rank order statistics arising in its consideration.  _Cancer Chemotherapy Reports_ 50, 3 (1966), 163–170.
  * Manès et al. (2021) Valentin J.M. Manès, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo. 2021\.  The Art, Science, and Engineering of Fuzzing: A Survey.  _Transactions on Software Engineering_ 47, 11 (2021), 2312–2331.  https://doi.org/10.1109/TSE.2019.2946563
  * Metzman et al. (2021) Jonathan Metzman, László Szekeres, Laurent Maurice Romain Simon, Read Trevelin Sprabery, and Abhishek Arya. 2021.  FuzzBench: An Open Fuzzer Benchmarking Platform and Service. In _European Software Engineering Conference and Foundations of Software Engineering_ _(ESEC/FSE)_. ACM, 1393–1403.  https://doi.org/10.1145/3468264.3473932
  * NIST (2019) NIST. 2019.  CVE-2019-7663.  https://nvd.nist.gov/vuln/detail/CVE-2019-7663
  * Rebert et al. (2014) Alexandre Rebert, Sang Kil Cha, Thanassis Avgerinos, Jonathan Foote, David Warren, Gustavo Grieco, and David Brumley. 2014.  Optimizing Seed Selection for Fuzzing. In _USENIX Security_ _(SEC)_. USENIX, 861–875.
  * Saavedra et al. (2019) Gary J. Saavedra, Kathryn N. Rodhouse, Daniel M. Dunlavy, and W. Philip Kegelmeyer. 2019\.  A Review of Machine Learning Applications in Fuzzing.  _arXiv Preprint_ abs/1906.11133 (2019), 12 pages.  https://doi.org/10.48550/arXiv.1906.11133
  * Scott et al. (2020) Joseph Scott, Federico Mora, and Vijay Ganesh. 2020\.  BanditFuzz: A Reinforcement-Learning Based Performance Fuzzer for SMT Solvers. In _Verified Software: Theories, Tools, and Experiments_ _(VSTTE)_. Springer-Verlag, 68–86.  https://doi.org/10.1007/978-3-030-63618-0_5
  * Seldin et al. (2013) Yevgeny Seldin, Csaba Szepesvári, Peter Auer, and Yasin Abbasi-Yadkori. 2013.  Evaluation and Analysis of the Performance of the EXP3 Algorithm in Stochastic Environments. In _Proceedings of Machine Learning Research_ _(PMLR, Vol. 24)_. PMLR, 103–116.  http://proceedings.mlr.press/v24/seldin12a.html
  * Serebryany (2017) Kostya Serebryany. 2017\.  OSS-Fuzz - Google’s continuous fuzzing service for open source software. In _USENIX Security_ _(SEC)_. USENIX.
  * She et al. (2022) Dongdong She, Abhishek Shah, and Suman Jana. 2022.  Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis. In _Security and Privacy_ _(S &P)_. IEEE, 2194–2211.  https://doi.org/10.1109/SP46214.2022.9833761
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Thompson (1933) William R Thompson. 1933\.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ 25, 3-4 (1933), 285–294.
  * Wagner (2017) Jonas Benedict Wagner. 2017\.  _Elastic Program Transformations: Automatically Optimizing the Reliability/Performance Trade-off in Systems Software_.  Ph. D. Dissertation. EPFL.  https://doi.org/10.5075/epfl-thesis-7745
  * Wang et al. (2021b) Daimeng Wang, Zheng Zhang, Hang Zhang, Zhiyun Qian, Srikanth V. Krishnamurthy, and Nael Abu-Ghazaleh. 2021b.  SyzVegas: Beating Kernel Fuzzing Odds with Reinforcement Learning. In _USENIX Security_ _(SEC)_. USENIX, 2741–2758.
  * Wang et al. (2021a) Jinghan Wang, Chengyu Song, and Heng Yin. 2021a.  Reinforcement Learning-based Hierarchical Seed Scheduling for Greybox Fuzzing. In _Network and Distributed System Security Symposium_ _(NDSS)_. The Internet Society, 17 pages.  https://doi.org/10.14722/ndss.2021.24486
  * Wang and Zhou (2020) Pengfei Wang and Xu Zhou. 2020.  SoK: The Progress, Challenges, and Perspectives of Directed Greybox Fuzzing.  _CoRR_ abs/2005.11907 (2020).
  * Wang et al. (2020a) Yan Wang, Peng Jia, Luping Liu, Cheng Huang, and Zhonglin Liu. 2020a.  A systematic review of fuzzing based on machine learning techniques.  _PLOS ONE_ 15, 8 (2020), 1–37.  https://doi.org/10.1371/journal.pone.0237749
  * Wang et al. (2020b) Yanhao Wang, Xiangkun Jia, Yuwei Liu, Kyle Zeng, Tiffany Bao, Dinghao Wu, and Purui Su. 2020b.  Not All Coverage Measurements Are Equal: Fuzzing by Coverage Accounting for Input Prioritization. In _Network and Distributed Systems Security_ _(NDSS)_. The Internet Society, 17 pages.  https://doi.org/10.14722/ndss.2020.24422
  * Woo et al. (2013) Maverick Woo, Sang Kil Cha, Samantha Gottlieb, and David Brumley. 2013.  Scheduling Black-Box Mutational Fuzzing. In _Computer and Communications Security_ _(CCS)_. ACM, 511–522.  https://doi.org/10.1145/2508859.2516736
  * Xu et al. (2017) Wen Xu, Sanidhya Kashyap, Changwoo Min, and Taesoo Kim. 2017\.  Designing New Operating Primitives to Improve Fuzzing Performance. In _Computer and Communications Security_ _(CCS)_. ACM, 2313–2328.  https://doi.org/10.1145/3133956.3134046
  * Yue et al. (2020) Tai Yue, Pengfei Wang, Yong Tang, Enze Wang, Bo Yu, Kai Lu, and Xu Zhou. 2020\.  EcoFuzz: Adaptive Energy-Saving Greybox Fuzzing as a Variant of the Adversarial Multi-Armed Bandit. In _USENIX Security_ _(SEC)_. USENIX, 2307–2324.
  * Zalewski (2015) Michał Zalewski. 2015\.  American Fuzzy Lop (AFL).  http://lcamtuf.coredump.cx/afl/
  * Zhang et al. (2022) Gen Zhang, Pengfei Wang, Tai Yue, Xiangdong Kong, Shan Huang, Xu Zhou, and Kai Lu. 2022.  MobFuzz: Adaptive Multi-objective Optimization in Gray-box Fuzzing. In _Network and Distributed Systems Security_ _(NDSS)_. The Internet Society, 18 pages.  https://doi.org/10.14722/ndss.2022.24314
  * Zheng et al. (2022) Han Zheng, Jiayuan Zhang, Yuhang Huang, Zezhong Ren, He Wang, Chunjie Cao, Yuqing Zhang, Flavio Toffalini, and Mathias Payer. 2022.  FishFuzz: Throwing Larger Nets to Catch Deeper Bugs.  _CoRR_ abs/2207.13393 (2022).  https://doi.org/10.48550/arXiv.2207.13393
  * Zong et al. (2020) Peiyuan Zong, Tao Lv, Dawei Wang, Zizhuang Deng, Ruigang Liang, and Kai Chen. 2020\.  FuzzGuard: Filtering out Unreachable Inputs in Directed Grey-box Fuzzing through Deep Learning. In _USENIX Security_ _(SEC)_. USENIX, 2255–2269.

##  Appendix A Magma Survival Analysis

Following prior work (Arcuri and Briand, 2011; Wagner, 2017; Hazimeh et al.,
2020; Herrera et al., 2021, 2022), we model bug finding using survival
analysis. This allows us to reason about censored data; i.e., the case where a
fuzzer does not find a bug. Table 5 presents the restricted mean survival time
(RMST) of a given bug; i.e., the mean time the bug “survives” being discovered
by a fuzzer across ten repeated 72 campaigns. Lower RMSTs imply a fuzzer finds
a bug “faster”, while a smaller confidence interval (CI) means the bug is
found more consistently. Applying the log-rank test (Mantel, 1966) under the
null hypothesis that two fuzzers share the same survival function allows us to
statistically compare survival times. Thus, two fuzzers have statistically
equivalent bug survival times if the log-rank test’s $p\textrm{-value}>0.05$.
The survival analysis results in Table 5 augment those presented in the main
paper.

Table 5. Magma bugs triggered, presented as the restricted mean survival time
(RMST; in hours) with 95 bootstrap CI. Bugs never found by a particular fuzzer
have an RMST of $\top$ (to distinguish bugs with a 72 RMST). Targets that fail
to build with a given fuzzer are marked with ✗. The best-performing fuzzer
(fuzzers if the bug survival times are statistically equivalent per the log-
rank test) for each bug is highlighted in green (smaller is better).

Fuzzer AFL++ T-Scheduler Target Driver Bug EXPLORE FAST COE QUAD LIN EXPLOIT
MMOPT RARE K-Sched Tortoise Rare$-$ Rare$+$ Sample $71.51$ $\top$ $\top$
$\top$ $\top$ $70.53$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$ PNG001
$\,\pm\,1.67$ $\,\pm\,5.00$ $14.40$ $0.01$ $0.01$ $7.21$ $28.80$ $0.01$ $7.21$
$7.21$ $0.01$ $0.01$ $0.01$ $0.01$ $0.01$ PNG003 $\,\pm\,25.24$ $\,\pm\,0.00$
$\,\pm\,0.01$ $\,\pm\,14.11$ $\,\pm\,30.92$ $\,\pm\,0.01$ $\,\pm\,18.93$
$\,\pm\,17.28$ $\,\pm\,0.01$ $\,\pm\,0.01$ $\,\pm\,0.01$ $\,\pm\,0.01$
$\,\pm\,0.01$ $14.45$ $0.08$ $0.04$ $7.24$ $28.83$ $0.05$ $7.25$ $7.26$ $\top$
$\top$ $\top$ $\top$ $\top$ PNG006 $\,\pm\,17.84$ $\,\pm\,0.05$ $\,\pm\,0.02$
$\,\pm\,12.76$ $\,\pm\,24.43$ $\,\pm\,0.03$ $\,\pm\,12.75$ $\,\pm\,12.75$
$39.28$ $35.25$ $51.15$ $38.13$ $47.51$ $26.85$ $42.04$ $52.84$ $68.36$
$70.22$ $28.31$ $30.63$ $28.02$ libpng libpng_read_fuzzer PNG007
$\,\pm\,19.37$ $\,\pm\,13.41$ $\,\pm\,19.63$ $\,\pm\,21.00$ $\,\pm\,20.87$
$\,\pm\,14.18$ $\,\pm\,19.27$ $\,\pm\,18.18$ $\,\pm\,12.35$ $\,\pm\,6.03$
$\,\pm\,15.21$ $\,\pm\,14.04$ $\,\pm\,16.30$ $0.64$ $0.41$ $0.46$ $1.29$
$1.43$ $2.46$ $0.56$ $0.45$ $34.02$ $\top$ $0.24$ $0.21$ $0.32$ SND001
$\,\pm\,0.24$ $\,\pm\,0.11$ $\,\pm\,0.21$ $\,\pm\,0.52$ $\,\pm\,0.31$
$\,\pm\,1.64$ $\,\pm\,0.36$ $\,\pm\,0.17$ $\,\pm\,0.53$ $\,\pm\,0.08$
$\,\pm\,0.11$ $\,\pm\,0.08$ $0.97$ $0.78$ $1.09$ $3.92$ $2.88$ $6.57$ $1.51$
$1.02$ $\top$ $2.82$ $0.41$ $0.55$ $0.48$ SND005 $\,\pm\,0.27$ $\,\pm\,0.32$
$\,\pm\,0.42$ $\,\pm\,1.48$ $\,\pm\,1.07$ $\,\pm\,3.59$ $\,\pm\,0.68$
$\,\pm\,0.43$ $\,\pm\,1.20$ $\,\pm\,0.10$ $\,\pm\,0.24$ $\,\pm\,0.13$ $1.11$
$1.10$ $0.85$ $0.98$ $5.69$ $6.36$ $1.00$ $0.34$ $68.24$ $\top$ $0.40$ $0.45$
$0.36$ SND006 $\,\pm\,0.86$ $\,\pm\,1.23$ $\,\pm\,0.51$ $\,\pm\,0.46$
$\,\pm\,7.29$ $\,\pm\,2.68$ $\,\pm\,0.44$ $\,\pm\,0.14$ $\,\pm\,12.76$
$\,\pm\,0.14$ $\,\pm\,0.19$ $\,\pm\,0.08$ $0.70$ $0.85$ $0.46$ $1.27$ $1.57$
$2.86$ $1.27$ $0.66$ $56.23$ $\top$ $0.60$ $0.80$ $0.79$ SND007 $\,\pm\,0.32$
$\,\pm\,0.30$ $\,\pm\,0.27$ $\,\pm\,0.53$ $\,\pm\,0.61$ $\,\pm\,1.42$
$\,\pm\,0.56$ $\,\pm\,0.27$ $\,\pm\,15.46$ $\,\pm\,0.26$ $\,\pm\,0.18$
$\,\pm\,0.31$ $0.34$ $0.47$ $0.57$ $0.89$ $1.67$ $0.59$ $0.57$ $0.74$ $1.94$
$0.67$ $1.35$ $0.36$ $0.34$ SND017 $\,\pm\,0.19$ $\,\pm\,0.31$ $\,\pm\,0.23$
$\,\pm\,0.69$ $\,\pm\,1.19$ $\,\pm\,0.15$ $\,\pm\,0.20$ $\,\pm\,0.41$
$\,\pm\,0.12$ $\,\pm\,0.13$ $\,\pm\,0.90$ $\,\pm\,0.31$ $\,\pm\,0.22$ $0.75$
$0.80$ $1.06$ $1.40$ $2.18$ $2.03$ $1.12$ $1.14$ $\top$ $\top$ $2.96$ $3.36$
$2.63$ SND020 $\,\pm\,0.30$ $\,\pm\,0.29$ $\,\pm\,0.21$ $\,\pm\,0.49$
$\,\pm\,0.83$ $\,\pm\,0.74$ $\,\pm\,0.25$ $\,\pm\,0.27$ $\,\pm\,0.93$
$\,\pm\,1.52$ $\,\pm\,0.96$ $0.59$ $0.38$ $0.30$ $0.98$ $0.93$ $2.62$ $0.97$
$0.34$ $60.41$ $\top$ $0.38$ $0.45$ $0.35$ libsndfile sndfile_fuzzer SND024
$\,\pm\,0.27$ $\,\pm\,0.27$ $\,\pm\,0.14$ $\,\pm\,0.46$ $\,\pm\,0.37$
$\,\pm\,1.27$ $\,\pm\,0.43$ $\,\pm\,0.14$ $\,\pm\,15.52$ $\,\pm\,0.15$
$\,\pm\,0.19$ $\,\pm\,0.08$ $60.02$ $60.46$ $60.19$ $65.84$ $66.72$ $62.47$
$56.93$ $58.95$ $\top$ $\top$ $58.99$ $66.96$ $64.17$ TIF002 $\,\pm\,15.10$
$\,\pm\,18.66$ $\,\pm\,10.33$ $\,\pm\,20.91$ $\,\pm\,11.50$ $\,\pm\,14.48$
$\,\pm\,15.73$ $\,\pm\,17.79$ $\,\pm\,13.38$ $\,\pm\,8.80$ $\,\pm\,12.92$
$0.07$ $0.08$ $0.04$ $0.12$ $0.06$ $0.05$ $0.03$ $0.04$ $1.66$ $4.45$ $0.03$
$0.04$ $0.02$ TIF007 $\,\pm\,0.04$ $\,\pm\,0.03$ $\,\pm\,0.02$ $\,\pm\,0.14$
$\,\pm\,0.03$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.03$ $\,\pm\,0.40$
$\,\pm\,1.58$ $\,\pm\,0.02$ $\,\pm\,0.03$ $\,\pm\,0.01$ $67.16$ $64.98$ $\top$
$\top$ $\top$ $66.81$ $63.17$ $67.89$ $\top$ $\top$ $66.63$ $\top$ $64.90$
TIF008 $\,\pm\,9.80$ $\,\pm\,23.84$ $\,\pm\,11.22$ $\,\pm\,17.41$
$\,\pm\,13.95$ $\,\pm\,14.58$ $\,\pm\,14.50$ $1.52$ $1.92$ $1.25$ $3.05$
$1.75$ $1.44$ $1.35$ $1.84$ $2.42$ $51.10$ $1.37$ $0.97$ $0.90$ TIF012
$\,\pm\,0.56$ $\,\pm\,1.01$ $\,\pm\,0.34$ $\,\pm\,1.04$ $\,\pm\,0.35$
$\,\pm\,0.72$ $\,\pm\,0.36$ $\,\pm\,0.49$ $\,\pm\,0.54$ $\,\pm\,18.80$
$\,\pm\,0.66$ $\,\pm\,0.34$ $\,\pm\,0.39$ $5.63$ $2.72$ $4.17$ $4.12$ $3.11$
$2.49$ $3.68$ $1.59$ $\top$ $64.30$ $2.15$ $3.85$ $2.04$ tiff_read_rgba_fuzzer
TIF014 $\,\pm\,2.44$ $\,\pm\,1.17$ $\,\pm\,1.69$ $\,\pm\,2.89$ $\,\pm\,2.39$
$\,\pm\,1.27$ $\,\pm\,2.52$ $\,\pm\,0.65$ $\,\pm\,19.23$ $\,\pm\,1.41$
$\,\pm\,2.27$ $\,\pm\,0.98$ $\top$ $68.29$ $\top$ $\top$ $\top$ $69.71$
$70.72$ $66.34$ $\top$ $\top$ $65.47$ $\top$ $66.71$ TIF002 $\,\pm\,12.58$
$\,\pm\,7.78$ $\,\pm\,4.35$ $\,\pm\,10.97$ $\,\pm\,15.84$ $\,\pm\,10.45$
$69.44$ $65.94$ $65.84$ $\top$ $61.04$ $66.74$ $\top$ $\top$ $\top$ $\top$
$68.74$ $\top$ $\top$ TIF005 $\,\pm\,8.68$ $\,\pm\,20.57$ $\,\pm\,20.90$
$\,\pm\,22.01$ $\,\pm\,10.31$ $\,\pm\,11.05$ $22.19$ $22.62$ $13.46$ $51.00$
$46.21$ $31.89$ $16.42$ $12.05$ $64.89$ $41.90$ $14.92$ $20.82$ $20.53$ TIF006
$\,\pm\,8.76$ $\,\pm\,13.97$ $\,\pm\,5.32$ $\,\pm\,17.15$ $\,\pm\,22.09$
$\,\pm\,14.87$ $\,\pm\,13.61$ $\,\pm\,4.82$ $\,\pm\,24.15$ $\,\pm\,17.22$
$\,\pm\,7.82$ $\,\pm\,12.40$ $\,\pm\,9.97$ $0.05$ $0.06$ $0.17$ $0.14$ $0.05$
$0.07$ $0.05$ $0.05$ $0.23$ $9.52$ $0.04$ $0.04$ $0.03$ TIF007 $\,\pm\,0.03$
$\,\pm\,0.03$ $\,\pm\,0.16$ $\,\pm\,0.09$ $\,\pm\,0.03$ $\,\pm\,0.04$
$\,\pm\,0.03$ $\,\pm\,0.03$ $\,\pm\,0.11$ $\,\pm\,2.80$ $\,\pm\,0.02$
$\,\pm\,0.03$ $\,\pm\,0.02$ $65.04$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$
$\top$ $\top$ $\top$ $\top$ $\top$ $\top$ TIF008 $\,\pm\,23.61$ $28.49$
$30.93$ $25.45$ $37.69$ $33.09$ $23.03$ $18.79$ $19.39$ $3.29$ $10.62$ $14.31$
$33.37$ $33.77$ TIF009 $\,\pm\,19.49$ $\,\pm\,20.82$ $\,\pm\,19.99$
$\,\pm\,17.37$ $\,\pm\,22.14$ $\,\pm\,18.04$ $\,\pm\,11.26$ $\,\pm\,14.14$
$\,\pm\,2.11$ $\,\pm\,1.53$ $\,\pm\,3.47$ $\,\pm\,15.03$ $\,\pm\,17.58$ $1.26$
$0.86$ $1.33$ $7.77$ $2.41$ $1.36$ $0.89$ $1.37$ $7.30$ $54.88$ $2.43$ $1.53$
$1.15$ TIF012 $\,\pm\,0.30$ $\,\pm\,0.31$ $\,\pm\,0.51$ $\,\pm\,5.61$
$\,\pm\,1.05$ $\,\pm\,0.45$ $\,\pm\,0.22$ $\,\pm\,0.57$ $\,\pm\,5.82$
$\,\pm\,15.72$ $\,\pm\,0.99$ $\,\pm\,0.79$ $\,\pm\,0.39$ $4.06$ $3.18$ $1.80$
$9.53$ $3.93$ $2.48$ $1.32$ $1.05$ $5.68$ $61.01$ $1.29$ $0.93$ $0.87$ libtiff
tiffcp TIF014 $\,\pm\,1.99$ $\,\pm\,1.49$ $\,\pm\,0.60$ $\,\pm\,7.82$
$\,\pm\,2.29$ $\,\pm\,1.06$ $\,\pm\,0.43$ $\,\pm\,0.33$ $\,\pm\,2.66$
$\,\pm\,15.90$ $\,\pm\,0.61$ $\,\pm\,0.44$ $\,\pm\,0.39$

Table 6. Magma bugs (cont.).

Fuzzer AFL++ T-Scheduler Target Driver Bug EXPLORE FAST COE QUAD LIN EXPLOIT
MMOPT RARE K-Sched Tortoise Rare$-$ Rare$+$ Sample $\top$ $\top$ $67.43$
$\top$ $\top$ $\top$ $43.49$ $\top$ $\top$ $\top$ $\top$ $65.80$ $65.02$
XML001 $\,\pm\,8.15$ $\,\pm\,14.41$ $\,\pm\,8.42$ $\,\pm\,13.91$ $\top$ $\top$
$\top$ $\top$ $71.33$ $\top$ $65.73$ $67.52$ $\top$ $\top$ $\top$ $68.72$
$61.70$ XML002 $\,\pm\,2.27$ $\,\pm\,21.28$ $\,\pm\,15.20$ $\,\pm\,11.15$
$\,\pm\,20.67$ $5.49$ $2.78$ $2.59$ $1.94$ $2.63$ $8.58$ $9.29$ $3.58$ $\top$
$\top$ $4.93$ $1.69$ $2.84$ XML003 $\,\pm\,2.49$ $\,\pm\,2.09$ $\,\pm\,0.92$
$\,\pm\,1.16$ $\,\pm\,0.80$ $\,\pm\,5.46$ $\,\pm\,12.41$ $\,\pm\,1.82$
$\,\pm\,2.74$ $\,\pm\,0.83$ $\,\pm\,1.21$ $1.11$ $1.52$ $1.43$ $2.45$ $5.16$
$4.83$ $8.16$ $1.82$ $\top$ $\top$ $1.55$ $1.64$ $1.20$ XML009 $\,\pm\,0.23$
$\,\pm\,0.48$ $\,\pm\,0.46$ $\,\pm\,0.92$ $\,\pm\,2.16$ $\,\pm\,1.73$
$\,\pm\,12.59$ $\,\pm\,0.88$ $\,\pm\,0.90$ $\,\pm\,0.91$ $\,\pm\,0.46$ $69.16$
$60.42$ $70.18$ $\top$ $63.83$ $\top$ $48.18$ $\top$ $\top$ $\top$ $\top$
$\top$ $71.61$ XML012 $\,\pm\,9.65$ $\,\pm\,11.63$ $\,\pm\,6.19$
$\,\pm\,12.93$ $\,\pm\,18.08$ $\,\pm\,1.33$ $0.02$ $0.02$ $0.02$ $0.04$ $0.06$
$0.02$ $7.21$ $0.03$ $0.02$ $0.03$ $0.02$ $0.02$ $0.03$ xml_read_memory_fuzzer
XML017 $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.06$ $\,\pm\,0.04$
$\,\pm\,0.02$ $\,\pm\,16.00$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.03$
$\,\pm\,0.02$ $\,\pm\,0.01$ $\,\pm\,0.02$ $58.72$ $62.41$ $63.36$ $68.58$
$60.06$ $\top$ $54.85$ $65.02$ $\top$ $\top$ $62.34$ $52.02$ $57.17$ XML001
$\,\pm\,11.70$ $\,\pm\,9.50$ $\,\pm\,7.42$ $\,\pm\,11.62$ $\,\pm\,16.06$
$\,\pm\,11.93$ $\,\pm\,10.46$ $\,\pm\,8.09$ $\,\pm\,11.68$ $\,\pm\,8.30$
$65.11$ $71.07$ $68.13$ $\top$ $66.00$ $\top$ $\top$ $66.75$ $\top$ $\top$
$69.56$ $66.25$ $65.02$ XML002 $\,\pm\,14.82$ $\,\pm\,3.16$ $\,\pm\,13.14$
$\,\pm\,20.38$ $\,\pm\,17.82$ $\,\pm\,8.29$ $\,\pm\,11.28$ $\,\pm\,23.70$
$1.47$ $2.03$ $2.01$ $5.89$ $6.37$ $6.17$ $2.30$ $2.70$ $66.68$ $\top$ $1.11$
$0.93$ $0.64$ XML009 $\,\pm\,0.72$ $\,\pm\,0.92$ $\,\pm\,0.80$ $\,\pm\,2.55$
$\,\pm\,2.64$ $\,\pm\,2.18$ $\,\pm\,1.27$ $\,\pm\,1.53$ $\,\pm\,9.16$
$\,\pm\,0.40$ $\,\pm\,0.46$ $\,\pm\,0.21$ $\top$ $\top$ $65.92$ $65.67$
$66.99$ $\top$ $65.99$ $\top$ $\top$ $\top$ $\top$ $\top$ $67.14$ XML012
$\,\pm\,12.90$ $\,\pm\,21.48$ $\,\pm\,17.02$ $\,\pm\,20.39$ $\,\pm\,14.06$
$0.03$ $0.05$ $0.04$ $0.07$ $0.06$ $0.02$ $0.03$ $0.02$ $0.01$ $0.13$ $0.04$
$0.03$ $0.03$ libxml2 xmllint XML017 $\,\pm\,0.02$ $\,\pm\,0.05$ $\,\pm\,0.03$
$\,\pm\,0.07$ $\,\pm\,0.04$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.02$
$\,\pm\,0.02$ $\,\pm\,0.09$ $\,\pm\,0.03$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\top$
$\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $67.10$ $69.76$
$71.10$ LUA002 $\,\pm\,6.58$ $\,\pm\,7.61$ $\,\pm\,3.04$ $5.68$ $8.15$ $5.75$
$14.95$ $36.47$ $35.36$ $5.89$ $10.19$ $9.93$ $7.21$ $9.69$ $6.24$ $10.03$ lua
lua LUA004 $\,\pm\,2.17$ $\,\pm\,2.27$ $\,\pm\,2.87$ $\,\pm\,5.97$
$\,\pm\,20.63$ $\,\pm\,9.31$ $\,\pm\,3.57$ $\,\pm\,4.25$ $\,\pm\,4.11$
$\,\pm\,17.28$ $\,\pm\,2.90$ $\,\pm\,2.08$ $\,\pm\,2.58$ $35.11$ $25.39$
$28.46$ $44.71$ $47.63$ $8.58$ $19.74$ $38.69$ $66.85$ $\top$ $5.72$ $5.45$
$6.53$ SSL001 $\,\pm\,12.55$ $\,\pm\,7.22$ $\,\pm\,9.54$ $\,\pm\,11.97$
$\,\pm\,13.78$ $\,\pm\,3.50$ $\,\pm\,6.45$ $\,\pm\,9.26$ $\,\pm\,17.47$
$\,\pm\,2.27$ $\,\pm\,2.84$ $\,\pm\,3.68$ $0.06$ $0.06$ $0.06$ $0.06$ $0.06$
$0.06$ $0.06$ $0.06$ $0.16$ $0.26$ $0.06$ $0.07$ $0.07$ asn1 SSL003
$\,\pm\,0.07$ $\,\pm\,0.06$ $\,\pm\,0.06$ $\,\pm\,0.06$ $\,\pm\,0.06$
$\,\pm\,0.05$ $\,\pm\,0.05$ $\,\pm\,0.05$ $\,\pm\,0.00$ $\,\pm\,0.00$
$\,\pm\,0.04$ $\,\pm\,0.08$ $\,\pm\,0.07$ $0.08$ $0.17$ $0.07$ $0.08$ $0.08$
$0.08$ $0.07$ $0.08$ $0.17$ $50.42$ $0.09$ $0.08$ $0.09$ client SSL002
$\,\pm\,0.06$ $\,\pm\,0.20$ $\,\pm\,0.05$ $\,\pm\,0.06$ $\,\pm\,0.06$
$\,\pm\,0.05$ $\,\pm\,0.05$ $\,\pm\,0.05$ $\,\pm\,0.00$ $\,\pm\,37.31$
$\,\pm\,0.08$ $\,\pm\,0.06$ $\,\pm\,0.06$ $0.11$ $0.11$ $0.12$ $0.16$ $0.11$
$0.12$ $0.16$ $0.11$ $0.22$ $0.35$ $0.11$ $0.11$ $0.12$ SSL002 $\,\pm\,0.08$
$\,\pm\,0.08$ $\,\pm\,0.08$ $\,\pm\,0.09$ $\,\pm\,0.08$ $\,\pm\,0.08$
$\,\pm\,0.09$ $\,\pm\,0.08$ $\,\pm\,0.00$ $\,\pm\,0.00$ $\,\pm\,0.08$
$\,\pm\,0.08$ $\,\pm\,0.09$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$
$\top$ $18.62$ $16.42$ $29.93$ $37.10$ $46.80$ server SSL020 $\,\pm\,4.02$
$\,\pm\,3.27$ $\,\pm\,16.92$ $\,\pm\,14.20$ $\,\pm\,16.06$ $\top$ $71.49$
$66.82$ $\top$ $\top$ $64.89$ $\top$ $54.42$ $\top$ $27.31$ $\top$ $\top$
$\top$ openssl x509 SSL009 $\,\pm\,1.74$ $\,\pm\,17.60$ $\,\pm\,12.55$
$\,\pm\,19.80$ $\,\pm\,17.28$ $57.62$ $70.00$ $49.60$ $57.61$ $\top$ $48.32$
$65.14$ $51.48$ ✗ $2.77$ $5.61$ $5.48$ $2.88$ PHP004 $\,\pm\,28.19$
$\,\pm\,6.80$ $\,\pm\,23.07$ $\,\pm\,28.20$ $\,\pm\,16.34$ $\,\pm\,23.29$
$\,\pm\,27.52$ $\,\pm\,0.06$ $\,\pm\,3.11$ $\,\pm\,5.15$ $\,\pm\,2.54$ $56.61$
$30.29$ $49.65$ $68.83$ $61.50$ $15.25$ $27.63$ $33.01$ ✗ $3.51$ $1.22$ $0.64$
$0.98$ PHP009 $\,\pm\,17.72$ $\,\pm\,17.40$ $\,\pm\,24.01$ $\,\pm\,8.99$
$\,\pm\,14.04$ $\,\pm\,7.36$ $\,\pm\,19.74$ $\,\pm\,20.78$ $\,\pm\,0.22$
$\,\pm\,0.76$ $\,\pm\,0.28$ $\,\pm\,0.57$ $2.55$ $1.67$ $3.16$ $1.54$ $3.80$
$0.70$ $1.42$ $1.11$ ✗ $2.23$ $0.13$ $0.21$ $0.22$ php exif PHP011
$\,\pm\,1.37$ $\,\pm\,1.89$ $\,\pm\,2.88$ $\,\pm\,1.14$ $\,\pm\,3.16$
$\,\pm\,0.41$ $\,\pm\,1.03$ $\,\pm\,0.94$ $\,\pm\,0.03$ $\,\pm\,0.06$
$\,\pm\,0.07$ $\,\pm\,0.09$ $1.28$ $2.28$ $2.62$ $9.57$ $3.56$ $3.70$ $1.31$
$1.21$ $62.10$ $\top$ $2.83$ $5.19$ $2.77$ SQL002 $\,\pm\,0.50$ $\,\pm\,0.88$
$\,\pm\,1.98$ $\,\pm\,2.10$ $\,\pm\,0.99$ $\,\pm\,1.32$ $\,\pm\,0.63$
$\,\pm\,0.41$ $\,\pm\,19.45$ $\,\pm\,1.26$ $\,\pm\,1.63$ $\,\pm\,1.09$ $\top$
$68.65$ $\top$ $68.44$ $66.47$ $\top$ $\top$ $\top$ $\top$ $\top$ $\top$
$69.81$ $71.67$ SQL003 $\,\pm\,11.38$ $\,\pm\,12.09$ $\,\pm\,18.78$
$\,\pm\,7.45$ $\,\pm\,1.13$ $\top$ $\top$ $\top$ $\top$ $68.12$ $\top$ $70.78$
$\top$ $\top$ $\top$ $66.87$ $\top$ $\top$ SQL010 $\,\pm\,13.19$ $\,\pm\,4.15$
$\,\pm\,17.42$ $48.45$ $56.60$ $63.50$ $\top$ $54.90$ $\top$ $61.02$ $60.32$
$\top$ $\top$ $67.25$ $63.18$ $54.53$ SQL012 $\,\pm\,14.52$ $\,\pm\,10.60$
$\,\pm\,13.57$ $\,\pm\,20.57$ $\,\pm\,9.13$ $\,\pm\,13.18$ $\,\pm\,9.35$
$\,\pm\,15.02$ $\,\pm\,23.44$ $\top$ $67.15$ $69.68$ $\top$ $69.31$ $\top$
$\top$ $\top$ $\top$ $\top$ $71.16$ $67.38$ $62.88$ SQL013 $\,\pm\,8.35$
$\,\pm\,7.89$ $\,\pm\,7.06$ $\,\pm\,2.86$ $\,\pm\,9.07$ $\,\pm\,13.30$ $8.63$
$8.64$ $17.78$ $44.40$ $18.42$ $17.90$ $19.91$ $30.75$ $\top$ $\top$ $13.94$
$29.72$ $15.60$ SQL014 $\,\pm\,4.36$ $\,\pm\,2.56$ $\,\pm\,6.82$
$\,\pm\,13.27$ $\,\pm\,9.06$ $\,\pm\,9.91$ $\,\pm\,11.24$ $\,\pm\,10.16$
$\,\pm\,4.39$ $\,\pm\,10.17$ $\,\pm\,7.58$ $70.67$ $64.43$ $67.36$ $\top$
$57.17$ $\top$ $66.12$ $64.72$ $\top$ $\top$ $\top$ $69.17$ $66.67$ SQL015
$\,\pm\,4.50$ $\,\pm\,14.97$ $\,\pm\,15.75$ $\,\pm\,22.20$ $\,\pm\,12.17$
$\,\pm\,14.34$ $\,\pm\,9.61$ $\,\pm\,14.13$ $4.60$ $3.98$ $8.58$ $19.84$
$4.72$ $12.69$ $3.40$ $3.90$ $\top$ $\top$ $5.64$ $5.41$ $6.21$ SQL018
$\,\pm\,1.56$ $\,\pm\,1.64$ $\,\pm\,4.84$ $\,\pm\,10.26$ $\,\pm\,1.11$
$\,\pm\,4.12$ $\,\pm\,1.66$ $\,\pm\,1.99$ $\,\pm\,2.30$ $\,\pm\,1.50$
$\,\pm\,1.59$ $42.36$ $46.39$ $60.29$ $69.81$ $40.07$ $55.64$ $55.97$ $67.64$
$\top$ $\top$ $61.24$ $59.17$ $64.01$ sqlite3 sqlite3_fuzz SQL020
$\,\pm\,12.23$ $\,\pm\,14.82$ $\,\pm\,15.71$ $\,\pm\,7.45$ $\,\pm\,14.72$
$\,\pm\,21.97$ $\,\pm\,18.59$ $\,\pm\,7.93$ $\,\pm\,21.57$ $\,\pm\,15.05$
$\,\pm\,11.64$

Table 7. Magma bugs (cont.).

Fuzzer AFL++ T-Scheduler Target Driver Bug EXPLORE FAST COE QUAD LIN EXPLOIT
MMOPT RARE K-Sched Tortoise Rare$-$ Rare$+$ Sample $\top$ $65.08$ $\top$
$\top$ $\top$ $\top$ $\top$ $\top$ ✗ $\top$ $\top$ $\top$ $\top$ PDF001
$\,\pm\,23.48$ $1.15$ $1.82$ $1.89$ $5.25$ $5.63$ $2.07$ $1.96$ $1.61$ ✗
$0.10$ $0.99$ $1.23$ $1.24$ PDF010 $\,\pm\,0.53$ $\,\pm\,0.50$ $\,\pm\,1.34$
$\,\pm\,2.81$ $\,\pm\,2.40$ $\,\pm\,2.03$ $\,\pm\,1.22$ $\,\pm\,0.56$
$\,\pm\,0.10$ $\,\pm\,0.47$ $\,\pm\,0.52$ $\,\pm\,0.69$ $65.59$ $\top$ $66.53$
$60.79$ $\top$ $65.88$ $\top$ $\top$ ✗ $\top$ $67.01$ $65.70$ $55.79$ PDF011
$\,\pm\,21.76$ $\,\pm\,18.57$ $\,\pm\,21.97$ $\,\pm\,20.79$ $\,\pm\,12.96$
$\,\pm\,21.39$ $\,\pm\,21.95$ $0.04$ $0.05$ $0.06$ $0.07$ $0.03$ $0.04$ $0.04$
$0.07$ ✗ $0.25$ $0.04$ $0.04$ $0.05$ PDF016 $\,\pm\,0.02$ $\,\pm\,0.03$
$\,\pm\,0.04$ $\,\pm\,0.09$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.02$
$\,\pm\,0.04$ $\,\pm\,0.00$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.03$ $37.84$
$40.38$ $38.25$ $\top$ $\top$ $33.83$ $29.91$ $20.92$ ✗ $\top$ $12.75$ $9.40$
$10.99$ PDF018 $\,\pm\,22.46$ $\,\pm\,20.71$ $\,\pm\,19.84$ $\,\pm\,13.80$
$\,\pm\,16.76$ $\,\pm\,12.37$ $\,\pm\,6.18$ $\,\pm\,4.68$ $\,\pm\,5.44$ $\top$
$\top$ $\top$ $\top$ $69.39$ $62.62$ $\top$ $\top$ ✗ $\top$ $\top$ $\top$
$\top$ PDF019 $\,\pm\,8.85$ $\,\pm\,21.37$ $52.56$ $\top$ $\top$ $62.32$
$55.67$ $\top$ $60.34$ $65.11$ ✗ $\top$ $70.08$ $68.57$ $68.76$ pdf_fuzzer
PDF021 $\,\pm\,19.39$ $\,\pm\,13.10$ $\,\pm\,18.47$ $\,\pm\,23.04$
$\,\pm\,23.38$ $\,\pm\,6.50$ $\,\pm\,11.63$ $\,\pm\,10.99$ $\top$ $\top$
$65.84$ $\top$ $\top$ $\top$ $\top$ $\top$ ✗ $\top$ $\top$ $65.56$ $65.57$
PDF002 $\,\pm\,20.92$ $\,\pm\,21.87$ $\,\pm\,21.84$ $10.42$ $11.24$ $7.80$
$13.40$ $9.72$ $32.29$ $31.47$ $31.91$ ✗ $\top$ $23.56$ $5.98$ $9.75$ PDF003
$\,\pm\,5.69$ $\,\pm\,4.53$ $\,\pm\,2.47$ $\,\pm\,5.75$ $\,\pm\,3.65$
$\,\pm\,18.22$ $\,\pm\,16.99$ $\,\pm\,18.48$ $\,\pm\,11.40$ $\,\pm\,2.64$
$\,\pm\,4.05$ $67.30$ $47.78$ $50.65$ $64.93$ $\top$ $70.10$ $59.23$ $56.30$ ✗
$48.95$ $55.77$ $65.02$ $35.84$ PDF011 $\,\pm\,15.96$ $\,\pm\,23.75$
$\,\pm\,21.96$ $\,\pm\,24.01$ $\,\pm\,6.46$ $\,\pm\,18.00$ $\,\pm\,22.15$
$\,\pm\,13.93$ $\,\pm\,22.48$ $\,\pm\,15.35$ $\,\pm\,17.81$ $0.03$ $0.01$
$0.03$ $0.02$ $0.03$ $0.02$ $0.03$ $0.02$ ✗ $0.09$ $0.04$ $0.03$ $0.02$ PDF016
$\,\pm\,0.02$ $\,\pm\,0.01$ $\,\pm\,0.02$ $\,\pm\,0.01$ $\,\pm\,0.02$
$\,\pm\,0.01$ $\,\pm\,0.02$ $\,\pm\,0.01$ $\,\pm\,0.06$ $\,\pm\,0.03$
$\,\pm\,0.02$ $\,\pm\,0.02$ $15.29$ $10.03$ $12.76$ $62.63$ $68.55$ $17.24$
$5.49$ $7.89$ ✗ $\top$ $4.86$ $5.23$ $3.85$ PDF018 $\,\pm\,9.90$ $\,\pm\,5.12$
$\,\pm\,3.98$ $\,\pm\,14.63$ $\,\pm\,9.41$ $\,\pm\,8.60$ $\,\pm\,3.25$
$\,\pm\,8.87$ $\,\pm\,1.36$ $\,\pm\,1.38$ $\,\pm\,1.57$ $59.02$ $46.57$
$59.70$ $64.94$ $\top$ $65.11$ $65.89$ $67.23$ ✗ $\top$ $59.00$ $59.37$ $\top$
PDF019 $\,\pm\,25.54$ $\,\pm\,21.60$ $\,\pm\,24.13$ $\,\pm\,23.96$
$\,\pm\,23.39$ $\,\pm\,9.77$ $\,\pm\,10.93$ $\,\pm\,25.48$ $\,\pm\,24.76$
$68.11$ $56.31$ $57.63$ $53.10$ $64.80$ $60.48$ $60.53$ $\top$ ✗ $\top$ $\top$
$\top$ $\top$ pdfimages PDF021 $\,\pm\,7.83$ $\,\pm\,22.81$ $\,\pm\,20.14$
$\,\pm\,19.80$ $\,\pm\,11.22$ $\,\pm\,17.74$ $\,\pm\,16.80$ $\top$ $69.18$
$\top$ $\top$ $\top$ $66.84$ $70.95$ $\top$ ✗ $\top$ $\top$ $\top$ $\top$
PDF002 $\,\pm\,9.57$ $\,\pm\,17.53$ $\,\pm\,3.55$ $\top$ $\top$ $66.15$ $\top$
$\top$ $\top$ $\top$ $\top$ ✗ $\top$ $\top$ $\top$ $\top$ PDF004
$\,\pm\,12.04$ $37.74$ $47.02$ $39.42$ $\top$ $67.36$ $62.16$ $43.73$ $57.99$
✗ $\top$ $65.15$ $68.07$ $69.96$ PDF006 $\,\pm\,16.73$ $\,\pm\,17.98$
$\,\pm\,19.31$ $\,\pm\,15.77$ $\,\pm\,19.31$ $\,\pm\,15.04$ $\,\pm\,27.47$
$\,\pm\,13.44$ $\,\pm\,7.54$ $\,\pm\,6.93$ $3.21$ $2.98$ $2.51$ $3.79$ $4.14$
$2.79$ $3.01$ $2.08$ ✗ $0.11$ $0.87$ $0.81$ $1.15$ PDF010 $\,\pm\,1.70$
$\,\pm\,1.53$ $\,\pm\,0.90$ $\,\pm\,1.56$ $\,\pm\,2.63$ $\,\pm\,1.96$
$\,\pm\,1.40$ $\,\pm\,0.82$ $\,\pm\,0.08$ $\,\pm\,0.82$ $\,\pm\,0.41$
$\,\pm\,0.48$ $61.79$ $\top$ $51.66$ $68.18$ $54.37$ $64.07$ $59.46$ $62.30$ ✗
$\top$ $66.46$ $61.80$ $55.98$ PDF011 $\,\pm\,20.01$ $\,\pm\,27.29$
$\,\pm\,12.97$ $\,\pm\,24.48$ $\,\pm\,16.67$ $\,\pm\,19.30$ $\,\pm\,19.04$
$\,\pm\,18.79$ $\,\pm\,20.31$ $\,\pm\,22.97$ $0.07$ $0.03$ $0.03$ $0.02$
$0.03$ $0.04$ $0.03$ $0.03$ ✗ $0.19$ $0.04$ $0.07$ $0.04$ PDF016 $\,\pm\,0.04$
$\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.02$
$\,\pm\,0.02$ $\,\pm\,0.02$ $\,\pm\,0.00$ $\,\pm\,0.04$ $\,\pm\,0.07$
$\,\pm\,0.03$ $29.16$ $22.78$ $21.64$ $65.46$ $65.66$ $61.72$ $24.27$ $22.05$
✗ $\top$ $8.02$ $7.30$ $8.73$ PDF018 $\,\pm\,14.25$ $\,\pm\,16.31$
$\,\pm\,6.97$ $\,\pm\,22.20$ $\,\pm\,21.51$ $\,\pm\,17.43$ $\,\pm\,12.33$
$\,\pm\,8.44$ $\,\pm\,5.23$ $\,\pm\,2.37$ $\,\pm\,2.30$ $66.98$ $\top$ $69.24$
$\top$ $65.84$ $\top$ $\top$ $64.85$ ✗ $\top$ $66.97$ $69.87$ $\top$ PDF019
$\,\pm\,17.05$ $\,\pm\,9.37$ $\,\pm\,12.95$ $\,\pm\,24.28$ $\,\pm\,17.06$
$\,\pm\,7.24$ $49.11$ $48.91$ $56.02$ $47.02$ $64.56$ $54.78$ $42.11$ $66.85$
✗ $\top$ $52.93$ $63.05$ $56.91$ poppler pdftoppm PDF021 $\,\pm\,22.90$
$\,\pm\,12.70$ $\,\pm\,16.93$ $\,\pm\,16.10$ $\,\pm\,11.22$ $\,\pm\,20.24$
$\,\pm\,18.53$ $\,\pm\,11.22$ $\,\pm\,18.80$ $\,\pm\,13.16$ $\,\pm\,21.43$