# Toward Unbiased Multiple-Target Fuzzing with Path Diversity

Huanyao Rong
Indiana University Bloomington  Wei You
Renmin University of China  Xiaofeng Wang
Indiana University Bloomington  Tiaohao Mao
Indiana University Bloomington

###### Abstract

Directed fuzzing is an advanced software testing approach that systematically
guides the fuzzing campaign toward user-defined target sites, enabling
efficient discovery of vulnerabilities related to these sites. However, we
have observed that some complex vulnerabilities remain undetected by directed
fuzzers even when the flawed target sites are frequently tested by the
generated test cases, because triggering these bugs often requires the
execution of additional code in related program locations. Furthermore, when
fuzzing multiple targets, the existing energy assignment in directed fuzzing
lacks precision and does not ensure the fairness across targets, which leads
to insufficient fuzzing effort spent on some deeper targets.

In this paper, we propose a novel directed fuzzing solution named AFLRun,
which features target path-diversity metric and unbiased energy assignment.
Firstly, we develop a new coverage metric by maintaining extra virgin map for
each covered target to track the coverage status of seeds that hit the target.
This approach enables the storage of waypoints into the corpus that hit a
target through interesting path, thus enriching the path diversity for each
target. Additionally, we propose a corpus-level energy assignment strategy
that guarantees fairness for each target. AFLRun starts with uniform target
weight and propagates this weight to seeds to get a desired seed weight
distribution. By assigning energy to each seed in the corpus according to such
desired distribution, a precise and unbiased energy assignment can be
achieved.

We built a prototype system and assessed its performance using a standard
benchmark and several extensively fuzzed real-world applications. The
evaluation results demonstrate that AFLRun outperforms state-of-the-art
fuzzers in terms of vulnerability detection, both in quantity and speed.
Moreover, AFLRun uncovers 29 previously unidentified vulnerabilities,
including 8 CVEs, across four distinct programs.

##  1 Introduction

Fuzzing is a testing technique that examines a program’s behavior by
subjecting it to a range of generated inputs, identifying any anomalous
behaviors that arise and reporting inputs causing such anomalies. In recent
years, coverage-guided fuzzing [4, 5, 1, 20] has made a significant stride in
uncovering software vulnerabilities. However, coverage-guided fuzzing is
designed to test all code regions within a program, but in certain security
scenarios, such as static analysis report verification [15] and patch testing
[11], the focus is on fuzzing specific code locations known as _target sites_.
As a result, directed fuzzing [12], building upon coverage-guided fuzzing, has
emerged as an alternative, receiving a lot of research attention [13, 32, 41,
23, 19, 40, 28]. The key idea of directed fuzzing is to approach and test the
target sites by prioritizing the seeds (stored test cases) whose execution
traces get to the vicinity of the target sites. This is achieved by evaluating
the seeds using a distance oracle and assigning more energy (which determines
the effort spent on fuzzing a given seed) to those coming closer to the
targets than others. In this way, the fuzzer is expected to quickly discover
the test cases capable of reaching the target sites and activating the
security flaws (the vulnerabilities) at these sites (e.i., triggering the
crash).

⬇

const char* get_string() {

if (/*Easy Constraint*/) return "default";

… // Constaints solvable by genetic approach

return get_input(); // Get attacker-controllable input

}

void foo() {

char victim[128];

const char* p = get_string();

if (/*Hard Constraint*/)

strcpy(victim, p); // Potential Overflow

}

Figure 1: Example of Preconditioned Trigger

Limitations and challenges. However, directed fuzzing today are impeded by the
limitations of techniques, rendering it less effective than expected in
discovering vulnerabilities. Specifically, as observed in our research,
oftentimes, hitting a target site does not necessarily trigger the
vulnerability it carries: that is, the execution of the seed fails to produce
a detectable crash. Instead, to activate the flaw, the execution trace needs
to cover some other code locations, which could be far away from this target
site. For example, in Listing 1, the flaw at the target site (Line 10) can
only be activated when the seed’s execution goes through Line 4, instead of
Line 2, since receiving a long input is the precondition for overflowing the
vulnerable buffer at the target site. We call such a scenario, in which a
unique path needs to be covered before hitting the vulnerable target site for
triggering such vulnerability at the target, _preconditioned flaw activation_
or _PFA_. Another scenario is that at the target site only the root cause of a
security flaw is present while the flaw can only be activated in a different
program location: as illustrated by the example in Listing 3, the target site
(Line 15-20) introduces an uninitialized pointer, which has only be
dereferenced (thereby causing a crash) at Line 28 and 29. We call this
scenario _post-target activation_ or _PTA_.

Moreover, in the presence of multiple target sites, a directed fuzzer is
supposed to generate test cases to fuzz these sites in an unbiased way.
However, today’s energy assignment strategy relies primarily on a scalar
distance oracle that determines a seed’s priority using average. As pointed by
the prior work [37, 27, 40], this strategy fails to take into account the
dynamic status of each target (e.g., whether it is easier than others to
reach), causing global optimum discrepancy, which could lead to _a bias
against certain targets or even favor the seed unable to reach any target_. As
a result, deeper target sites may receive insufficient fuzzing effort,
potentially leaving some vulnerabilities at these locations undiscovered.
Prior attempts to address the problem mostly focus on design of different
distance oracles to mitigate the bias [13, 27]. These approaches, however, are
still less effective due to their continued use of aggregate information like
average across all targets, thereby missing the individual information of each
target, such as the extent to which the paths to a specific target have been
covered by the current corpus. Even the most recent approach, FishFuzz [40],
which utilizes a vector-based oracle instead of a distance oracle, still does
not pay enough attention to the path diversity, ignoring the seed that hits a
target visited frequently but is associated with the paths much less traversed
than others.

Solutions. To address those limitations, we developed a new directed fuzzer by
enhancing the greybox fuzzer with two innovative techniques. First, we
introduce _target path-diversity metric_. More specifically, our fuzzer,
called AFLRun, aims at generating the seeds not only reaching a given target
site but covering as many paths involving the target as possible. For this
purpose, AFLRun maintains an extra virgin map for each target to record the
coverage status of all seeds that hit the target. When deciding whether a
mutated test case should be used to fuzz a program again (that is, storing the
test case into the fuzzer’s corpus as a seed), AFLRun not only checks its
execution trace with the virgin map of the coverage-guided fuzzer to evaluate
its potential to improve the total code coverage, but also with our extra
virgin maps to determine its capability of diversifying the execution paths
involving the target site.

Second, we introduce _unbiased energy assignment_ to enable fair exploration
and exploitation of each target. AFLRun first assigns each target block (the
basic block containing the target site) a weight, which takes the same value
to ensure their fair chance to be visited. Then it propagates the weights from
the targets to a set of critical blocks, which include both the target blocks
visited before and a set of critical boundary blocks: that is, a visited block
leading to a target with none of other blocks (including the target) between
the block and the target being covered before. For a given seed, our approach
computes its energy (which determines its mutation priority) by adding the
weights of the critical blocks it passes. In this way, AFLRun always
prioritizes the seeds with the highest potentials to get to a new target site
and the seeds that cover any target sites, ensuring each target to have a fair
chance to be tested. When applied together with the targeted path-diversity
metric, the energy assignment strategy can further improve the path diversity
of each target.

We implemented AFLRun on top of AFL++ [20] and AFLGo [12], and evaluated it on
a standard benchmark Magma [21] and real-world programs intensively fuzzed by
the OSS-Fuzz project [7]. Our evaluation on the Magma benchmark shows that
compared with state-of-the-art fuzzers (AFLGo, AFL++, Parmesan [32], FishFuzz
[40] and Hawkeye [13]), AFLRun achieves an average speedup of $168\%$,
$109\%$, $235\%$, $183\%$ and $147\%$ and triggers $38\%$, $20\%$, $162\%$,
$29\%$ and $24\%$ more vulnerabilities. In addition, AFLRun has discovered 29
previously unknown vulnerabilities in real-world programs, with 8 CVE IDs
assigned so far.

Contributions. We have made the following contributions:

$\bullet$ New techniques. To the best of our knowledge, we present the first
directed fuzzing technique that improves path diversity and fairness in energy
assignment for each target at the same time, in a systematic way. Serving this
purpose are two new techniques, including a new coverage metric that captures
both PFA and PTA to improve the chance to activate the flaws related to target
sites, and a new energy assignment strategy that ensures the target fairness
and prioritizes testing of the new paths involving the targets. Both are found
to be highly effective.

$\bullet$ Implementation, evaluation and findings. We implemented a prototype
system and will release its code upon publication. AFLRun has discovered 29
zero-day vulnerabilities from the real-world software that have been
intensively fuzzed before, which provides evidence to the efficacy of our
techniques.

##  2 Background

In this section, we introduce the basic concepts and overall workflow of
coverage-guided fuzzing (section 2.1) and directed fuzzing (section 2.2).

###  2.1 Coverage-guided Fuzzing

The workflow of the current coverage-guided fuzzing technique can be
summarized as follows: (1) At the beginning of a fuzzing campaign, one or more
inputs are provided as the initial seed corpus. (2) The fuzzer selects a seed
from the corpus, which is then mutated to create a test case that is executed
by the program under test (PUT); this mutation and execution process is
repeated several times for each selected seed. (3) If the test case triggers
any new behavior not yet triggered by the current corpus, it is stored as a
seed for future mutation. (4) The fuzzer repeats steps 2-3 in an infinite
loop. Since our approach focuses on improving energy assignment and seed
storage by modifying steps 2 and 3 in AFL++ [1, 20], we will discuss how AFL++
implements these two steps in greater detail.

In AFL++, the fuzzer process and the PUT process share a segment of memory to
record the execution path of the PUT, allowing the fuzzer to access this
information. Each byte in the shared memory represents an edge connecting two
basic blocks. The PUT is instrumented so that each time an edge is traversed
during execution, the corresponding byte is incremented by one111AFL++
classifies value of each non-zero byte according to $8$ predefined ranges,
each corresponding to a bit in the byte. Ultimately, the byte is set to the
bit corresponding to the classified range. The comparison between the
execution trace and the virgin map is performed at bit level.. In the shared
memory, the fuzzer obtains a bitmap that abstractly represents the execution
path of a single run. In this paper, we refer to this bitmap as the _execution
trace_. Additionally, AFL++ maintains a global bitmap to record all bits
covered by at least one execution trace of seeds in the corpus so far. We
refer to this bitmap as the _virgin map_ in this paper. Specifically, the
virgin map is an array with the same length as the execution trace,
initialized with all bits set to $1$. When a new seed covers a new bit, the
corresponding bit in the virgin map is set to $0$. Each time a mutated test
case is executed, AFL++ compares the generated execution trace with the virgin
map. If the execution trace covers a new bit that has not been covered by any
previous seeds’ execution traces, the test case will be added to the corpus as
a seed. By incrementally adding new seeds into corpus, total coverage of the
PUT can be improved.

In addition, AFL++ maintains a record of the best seed for each edge using an
array, based on metrics such as the seed’s length and execution time. We refer
to this array as the _top-rated array_ in this paper. When a new seed is added
to the corpus, AFL++ attempts to update the top-rated array based on the
seed’s edge coverage and metrics. If any updates occur, a process called
_queue culling_ selects a subset of seeds from the corpus to be marked as
favored, and these favored seeds are chosen for fuzzing more frequently than
the others.

###  2.2 Directed Fuzzing

Directed fuzzing, built upon coverage-based fuzzing, focuses on testing a
specific set of user-defined target sites rather than all code regions. The
main concept involves using a seed oracle (i.e., dynamic information gathered
by executing the PUT with the seed as input) to determine the proximity
between the seed and the target sites. This oracle is then used to assign
energy for preferentially testing these sites. The energy assigned to a seed
is defined by the number of times the fuzzer is going to mutate the seed and
execute the PUT using the mutated test case as input.

The seed oracle is commonly referred to as the _distance_ in the context of
directed fuzzing. To achieve such an oracle, both static analysis and dynamic
information are required. Static analysis of the PUT computes the distance
from each code location (e.g., basic block) to all target sites, typically
averaged using the harmonic mean. During a fuzzing campaign, each time the PUT
is executed with a particular seed as input, the seed’s distance value to
target sites (i.e., seed oracle) can be obtained by calculating the arithmetic
mean of the distance values of the relevant code locations covered during the
execution.

With this seed oracle, directed fuzzing assigns energy to each seed such that
seeds with lower distance values receive higher amounts of energy. By
adjusting energy assignment to favor seeds closer to the target sites, the
fuzzing campaign focuses on testing these specific sites.

##  3 Motivation

In this section, we present a vulnerability as our motivating example and
discuss the directed fuzzing scenario intended to discover such a
vulnerability. (section 3.1) We also examine how current directed fuzzing
approaches fail to find it, while AFLRun is capable of successfully detecting
it. (section 3.2)

###  3.1 Vulnerability and Fuzzing Scenario

We use the discovery of a zero-day vulnerability (CVE-2023-25588) in binutils
as an example to demonstrate the limitations of existing techniques and
motivate the idea of AFLRun. Listing 3 shows the simplified vulnerable code
snippet. The dump_bfd function invokes the bfd_get_synthetic_symtab function
pointer (Line 9) to create synthetic symbols for indirect symbols and invokes
the disassemble_data function (Line 11) to disassemble the contents of an
object file. When processing a Mach-O executable, the function pointer points
to the bfd_mach_o_get_synthetic_symtab function (Line 15-21), in which an
array of the asymbol structure is allocated without initialization for its
the_bfd pointer field. A pointer to the allocated array is stored in the
global variable synthsyms. The disassemble_data function performs complex
logic and finally calls the compare_symbols function to sort symbols. During
comparison, the the_bfd field of the elements stored in the synthsyms array
will be dereferenced, resulting in access of uninitialized pointer.

dump_bfd2slurp_symtab1ptbfd_mach_o_ get_synthetic_
symtab0disassemble_data1compare_symbolsxmalloc0 Figure 2: Partial call graph
that involves the critical functions to trigger the vulnerability. Another
target in xmalloc is also included. The distance value of each function is
annotated above the rectangular in red.

⬇

typedef struct bfd_symbol {

struct bfd *the_bfd;

/* other fields are omitted */

} asymbol;

\parasymbol *synthsyms;

long *(bfd_get_synthetic_symtab)(…);

\parvoid dump_bfd (…) {

bfd_get_synthetic_symtab(…, &synthsyms);

disassemble_data(…);

}

\par/* bfd_get_synthetic_symtab for Mach-O executable */

long bfd_mach_o_get_synthetic_symtab(…, asymbol **ret) {

size_t size = count * sizeof(asymbol) + 1;

char *s_start = bfd_malloc(size);

*ret = (asymbol *) s_start;

/* intialize each field of the asymbol structure,

except for the the_bfd pointer field */

}

\par/* disassemble_data finally calls compare_symbols */

int compare_symbols(const void *ap, const void *bp) {

/* a and b point to the elements in synthsyms. */

const asymbol *a = * (const asymbol **) ap;

const asymbol *b = * (const asymbol **) bp;

/* code to dereference a->the_bfd and b->the_bfd,

resulting in access of uninitialized pointer */

}

\par/* Another target site detected by static analysis */

void * xmalloc (size_t size) {

void *newmem = malloc (size);

return (newmem);

}

Figure 3: Simplified vulnerable code snippet.

Figure 2 illustrates the partial call graph involving the critical functions
needed to trigger the vulnerability. As depicted, in order to trigger the
vulnerability, a test case must cover the location of dereference (Line 28 in
compare_symbols) after executing the location of allocation (Line 17 in
bfd_mach_o_get_synthetic_symtab). It is important to note that these two
locations are distant from each other in the code base. This vulnerability
belongs to the PTA mentioned earlier in section 1.

Consider a security scenario that utilizes directed fuzzing to verify a report
from static analysis. An aggressive, yet comprehensive and scalable static
checker might identify potential risks if it detects a function that allocates
a piece of heap memory without initializing the content within the function
scope. When employing such a checker on binutils, it reports multiple program
locations, which are treated as target sites for directed fuzzing. The root
cause of this vulnerability, located at Line 17, is one of these target sites.
Additionally, there are other false positive target sites, including Line 34
at xmalloc, which is simply a wrapper for the malloc function. Figure 2 also
includes some functions that invoke xmalloc. For simplicity, we only show two
functions that call xmalloc, as it is a utility commonly used by numerous
functions. Thus, an ideal directed fuzzer should be able to discover the
vulnerability by generating a test case that both creates and dereferences the
uninitialized variable, despite the interference from false positive target
sites like Line 34. Besides, it is worth noting that these target locations
conform to the format used by AFLGo [12], instead of targets with explicit
dependency information required by some works [31, 25].

###  3.2 Limitations and Solutions

However, the current state-of-the-art directed fuzzer struggles to efficiently
trigger this bug under the scenario we described earlier, even if the flawed
target site at bfd_mach_o_get_synthetic_symtab is already covered by the
corpus during the fuzzing campaign. We outline two limitations that contribute
to this issue and explain how our approaches address them.

First, current directed fuzzers still rely on the coverage metric of coverage-
guided fuzzing, which is designed to improve the total code coverage of the
corpus. Specifically, once a constraint is solved, the edge of the constraint
will be marked as non-virgin in the virgin map, meaning that subsequent test
cases that cover the same edge will not be stored in the corpus. In this
example vulnerability, if the constraints on the path to Line 28 (i.e., the
dereference of the_bfd) are solved with a seed that cannot cover Line 17
(i.e., the location that creates the uninitialized pointer), the edges of
these constraints are no longer considered virgin. Consequently, if a test
case that covers the target site of uninitialized pointer allocation later
solves any of these constraints, it will not be stored in the corpus. As a
result, seeds that cover this target site cannot make progress on these
constraints by taking advantage of the genetic approach employed by the
greybox fuzzer, which ultimately restricts the subsequent fuzzing campaign
from discovering this potential crash.

We have observed that, in order to trigger this bug, path diversity for the
target site with the uninitialized pointer allocation is crucial. In other
words, we aim to maximize the total code coverage given the target site Line
17 is covered, in order to increase the likelihood of executing the code
location that accesses the uninitialized pointer. Our approach, by maintaining
an additional virgin map for this target site, does store test cases that
improve path diversity for this target site in the corpus, even if the
original coverage metric of AFL++ would deem the test case uninteresting.

Second, the energy assignment in existing directed fuzzing, which relies on
the scalar distance oracle, may be biased toward certain targets, resulting in
inadequate fuzzing efforts spent on the vulnerable target site. In this
particular example scenario, we demonstrate the bias toward the target Line
34. For simplicity, we only consider these two target sites and part of the
program illustrated in Figure 2, and assume there are only two categories of
seeds in the corpus: $S_{a}$ and $S_{b}$. Seeds in $S_{a}$ can visit target
site Line 17, while those in $S_{b}$ cannot. Both categories of seeds are able
to cover xmalloc through slurp_symtab and disassemble_data. Since Line 17 is
an uncommonly covered target, $S_{a}$ makes up only a small proportion of the
corpus. To avoid loss of generality, we calculate the seed distance values
using a simplified method that approximately represents current directed
fuzzing approaches [12, 32, 13]. Using the distance value of each function in
Figure 2, we can calculate the distance values of $S_{a}$ and $S_{b}$ as
$\frac{2+1+1+0+0}{5}=0.8$ and $\frac{2+1+1+0}{4}=1$, respectively. It is worth
noting that covering Line 17 only contributes one additional term and does not
significantly influence the average scalar value. As a result, the final
energy assigned to each seed in $S_{a}$ and $S_{b}$ does not differ greatly.
However, since the size of $S_{a}$ is small, the total energy assigned to
seeds in $S_{a}$ is also low, causing the fuzzing campaign to lose directness
toward target site Line 17 and become biased toward Line 34.

Instead, as we do not know which target site contains the vulnerability
beforehand, the importance of each target is unknown a priori. Therefore, a
best scheme is to treat each target (e.g., Line 17 and Line 34) equally during
the fuzzing campaign. Our approach achieves this by assigning a uniform weight
to each target and propagating such weight to seeds for energy assignment. To
be specific, the weight assigned to $S_{a}$ is
$\frac{1}{|S_{a}|}+\frac{1}{|S_{a}|+|S_{b}|}$, and the weight assigned to
$S_{b}$ is $\frac{1}{|S_{a}|+|S_{b}|}$.222Here, we assume that the seeds in
$|S_{a}|$ and $|S_{b}|$ have equal importance; however, in reality, the energy
assignment among seeds in such set is not uniform. See section 6.3 for more
details. Since $|S_{a}|$ is a much smaller value than $|S_{b}|$, the weight
assigned to each seed of $S_{a}$ is significantly greater than that of
$S_{b}$. Therefore, even though $S_{a}$ comprises only a small set of seeds in
the corpus, Line 17 will still be assigned an equal amount of weight as the
others, ensuring that it receives enough energy to trigger the bug.

##  4 Design Overview

In this section, we provide a brief design overview of AFLRun, including its
workflow (section 4.1) and the fuzzing loop (section 4.2).

###  4.1 Workflow

Figure 4 illustrates the workflow of AFLRun. In the static stage, AFLRun first
takes the program source code and target sites for static analysis and
instrumentation. The static analysis generates a partial interprocedural
control flow graph (ICFG) with vertices representing basic blocks that can
reach at least one of the target blocks, along with distance values to these
target blocks for each vertex. Each of these blocks is instrumented with our
runtime callback function. In the dynamic stage, our unbiased energy
assignment generates energy values for all seeds, which determine the number
of mutations and executions for each seed. For each execution of a mutated
test case, we employ our target path-diversity metric to determine whether the
test case should be stored in the corpus. If so, we also use it to update
critical blocks and target clusters. Target clusters are utilized to group
targets exhibiting similar behavior, thereby reducing the runtime overhead,
particularly when the number of targets is substantial.

Figure 4: Workflow of AFLRun.

###  4.2 Fuzzing Loop

Algorithm 1 provides a high-level overview of the fuzzing loop in AFLRun. Each
iteration of the outermost loop constitutes one cycle, during which all seeds
in the corpus are supposed to be selected for fuzzing once. At the beginning
of each cycle, the assign_energy function, our unbiased energy assignment, is
invoked to assign an energy value to each seed. Unlike other greybox fuzzing
approaches, including directed ones, our energy assignment algorithm operates
globally for the entire corpus rather than locally for individual seeds. This
global perspective is crucial for ensuring unbiased energy assignment.

In the second loop, we iterate through each seed-energy pair returned from
assign_energy in descending order based on energy, which allows AFLRun to fuzz
seeds with higher energy first. The seed is mutated using mutate_input, the
mutation algorithm from AFL++ [20], and executed by the PUT with our
instrumentation using execute. The execution results $t^{\prime}$ are examined
similarly to other greybox fuzzing methods. However, has_new_coverage is now
replaced by our target path-diversity metric, rather than the previous
coverage metric used in AFL++. Additionally, if a new seed updates the current
critical blocks, the cycle is immediately halted to restart the next cycle.
This is because our unbiased energy assignment depends on critical blocks;
thus, if any updates occur with them, AFLRun should discard the obsolete
energy results and re-assign energy using the updated critical blocks.

Algorithm 1 Fuzzing Loop of AFLRun

0: Initial _corpus_

1: repeat

2: $seed\\_energy$ := assign_energy($E$, corpus)

3: for $(seed,energy)\in seed\\_energy$ in descending order do

4: for $i$ from $1$ to $energy$ do

5: $s^{\prime}$ := mutate_input($seed$)

6: $t^{\prime}$ := execute($s^{\prime}$)

7: if $t^{\prime}$ crashes then

8: add $s^{\prime}$ to $crashes$

9: else if has_new_coverage($t^{\prime}$) then

10: add $s^{\prime}$ to $corpus$

11: if $t^{\prime}$ updates critical blocks then

12: break

13: end if

14: end if

15: end for

16: end for

17: until timeout reached or abort-signal

18: return $crashes$

##  5 Target Path-Diversity Metric

In this section, we will discuss how our coverage metric improves the path
diversity of already-covered targets. We introduce our multiple virgin maps in
section 5.1 and explain how we reduce overhead through clustering in section
5.2.

###  5.1 Virgin Maps for Target Path Diversity

Given a particular corpus state during a fuzzing campaign, the path diversity
of a target is defined by the total coverage of seeds that cover this target.
To enhance this path diversity, we propose to introduce an extra set of virgin
maps. As we discussed in section 2.1, AFL++ [20] uses a virgin map to store
the coverage information of the current seed corpus. When the execution trace
of a test case covers any new bits not yet covered by the corpus, the virgin
map is updated, and the test case is stored to the corpus. In our approach,
rather than using a single virgin map, we maintain and compare the execution
trace of each test case against multiple virgin maps. These multiple virgin
maps consist of the original virgin map used by AFL++, referred to as _primary
virgin map_ , and a set of extra virgin maps derived from all targets covered
by the test case, referred to as _target virgin maps_. After executing each
test case, besides comparing its execution trace with primary virgin map like
AFL++, we also compare it with our extra target virgin maps. If any of these
virgin maps indicate that new bits have been covered, the test case will be
stored to the corpus, and the bits of corresponding virgin map will be marked
as non-virgin. This approach is detailed in Algorithm 2.

Algorithm 2 Coverage Metric for Test Case

0:  _path_trace_ and _virgin_maps_

1: store := false

2: data := set()

3: for i := 1 to N do

4: if path_trace[i] $=$ 1 then

5: updates := set()

6: for map $\in$ virgin_maps do

7: if map[i] $=$ 1 then

8: map[i] := 0

9: store := true

10: updates.insert(map)

11: end if

12: end for

13: if $|updates|\neq 0$ then

14: data.insert(updates)

15: end if

16: end if

17: end for

18: return store, data

The parameter $path\\_trace$ is a bit array of length $N$, which is the
execution trace of test case that has just been executed. The parameter
$virgin\\_maps$ is a set of virgin maps including primary virgin map and
target virgin maps, each of which is also a bit array of length $N$. The
algorithm is somewhat similar to the original one of AFL++, except we compare
execution trace with multiple virgin maps instead of a single virgin map.
Furthermore, for each bit location where an update occurs, we record all the
virgin maps that have experienced an update at that bit location. While this
information is not useful for determining whether to store the test case, it
is useful for target clustering, which will be discussed later.

###  5.2 Target Clustering

Another question to consider is how to obtain the set of target virgin maps
from a set of targets covered by a test case. A naive approach would be to
maintain a target virgin map for each of the targets that have been covered by
seeds in the corpus. However, this approach could suffer from performance
overhead: since comparing the execution trace with virgin maps is a frequent
event, a large number of targets covered by each test case would require
comparisons with a correspondingly large number of virgin maps, resulting in a
non-negligible overhead. Initially, we implemented this naive approach and, by
observing how each target virgin map was updated with new bits from the
execution trace, we discovered that some virgin maps frequently update the
same bits simultaneously. The general idea is that we can cluster these virgin
maps into a single virgin map. This can reduce the overhead caused by repeated
comparisons while still maintaining the desired path diversity.

Obtaining clusters. Algorithm 3 outlines the process of selecting the set of
clusters from targets covered by the execution of a test case. Each cluster
corresponds to one virgin map and vice versa. First, we insert primary cluster
corresponding to the primary virgin map. Then, for each target covered by the
test case, we find its cluster using $get\\_cluster$, which maps each target
to the cluster containing it, and insert the returned cluster into $clusters$.
Since targets are now clustered and different targets can return the same
cluster from $get\\_cluster$, we use a unique set as the data type for
$clusters$ to prevent duplication of elements. With these clusters obtained,
we can get the set of virgin maps to be used in Algorithm 2.

Algorithm 3 Obtaining Set of Clusters

0:  _covered_targets_ and _primary_cluster_

1: clusters = unique_set()

2: clusters.insert(primary_cluster)

3: for target $\in$ covered_targets do

4: clusters.insert(get_cluster(target))

5: end for

6: return clusters

Association rule mining. Before discussing the details of our clustering
algorithm, we will first introduce some concepts related to association rule
mining used in this paper, which differ slightly from the original
definitions. Assume we have a given set of items
$I=\\{i_{1},i_{2},...,i_{n}\\}$ and a database $D=\\{t_{1},t_{2},...,t_{m}\\}$
where $\forall_{t\in D}\ t\subseteq I$. In other words, the database consists
of multiple subsets of items. In this paper, we define an association rule [9]
between two items, denoted as $i_{a}\Rightarrow i_{b}$, where $i_{a}\in I$ and
$i_{b}\in I$. Intuitively, this rule suggests that when $i_{a}$ appears in a
set $t$ within the database, $i_{b}$ is also likely to appear. Several metrics
have been defined to measure the extent to which a given rule holds in a given
database. The support count of an itemset $X\subseteq I$ is the number of
times the itemset appears in the database. In other words, the support count,
denoted as $\sigma(X)$, is the number of $t\in D$ such that $X\subseteq t$.
The confidence of a rule $i_{a}\Rightarrow i_{b}$ is a ratio measuring the
frequency of $i_{b}$ appearing given that $i_{a}$ appears, calculated by
$\frac{\sigma({\\{i_{a},i_{b}\\}})}{\sigma({i_{a}})}$. In this paper, we
consider a rule $i_{a}\Rightarrow i_{b}$ to be valid if both its support count
$\sigma(\\{i_{a},i_{b}\\})$ and its confidence are larger than a specified
threshold.

When a new target is covered by the corpus, a new cluster containing only that
target is created. At this point, the virgin map selection for this target is
equivalent to the naive implementation mentioned earlier. As the fuzzing
campaign progresses, more dynamic information is gathered, enabling us to
merge clusters together. Specifically, we use $data$ from all seeds in the
corpus, collected through Algorithm 2, as a database for association rule
mining [9]. This allows AFLRun to identify target virgin maps that can be
clustered together. In Algorithm 2, we can observe that $data$ consists of
sets of clusters, as each virgin map corresponds to a cluster. We treat each
cluster as an item and consider the union of $data$ from all seeds in the
corpus as the database in the context of association rule mining.
Additionally, since our dataset is constructed by joining the dataset of each
individual seed, we denote the dataset of a single seed $s$, which is a subset
of the entire dataset, as $I_{s}$.

Algorithm 4 outlines the process of updating support count after a new seed is
added to the corpus. The parameter $data$ comes from the return value of
Algorithm 2, and the parameter $support\\_count$ is a global map used to
record the support count of each itemset with one or two elements. For each
set in $data$, we count both single items and pairs of items by
$\frac{1}{|data|}$ instead of $1$. This design choice is made to prevent bias
caused by some seeds that trigger many new bits. As a result, we only assign a
total support count of $1$ for each seed, which is then distributed uniformly
among all sets of items it contains.

Algorithm 4 Support Count Update for Each New Seed

0:  _data_ and _support_count_

1: for items $\in$ data do

2: for $i$ $\in$ items do

3: support_count[$\\{i\\}$] += $\frac{1}{|data|}$

4: end for

5: for $\\{i_{a},i_{b}\\}$ $\subseteq$ items do

6: support_count[$\\{i_{a},i_{b}\\}$] += $\frac{1}{|data|}$

7: end for

8: end for

Using the support count from Algorithm 4, we can calculate the confidence
value of a given rule $i_{a}\Rightarrow i_{b}$ using the formula described
earlier.

Clustering. Given an association rule $i_{a}\Rightarrow i_{b}$, if both its
support count and confidence are higher than the threshold values, we can
consider it to be valid. This semantically implies that if the execution trace
of a new seed covers a new virgin bit in $i_{a}$, it will typically also cover
the same new virgin bit in $i_{b}$. In other words, the behavior of virgin bit
updates in $i_{a}$ is very similar to that of $i_{b}$, so we can merge such
redundant cluster $i_{a}$ into $i_{b}$ to reduce overhead while keeping the
capability of improving path diversity for covered targets. Finally, it is
important to note that the primary cluster cannot be merged into any other
cluster, but other clusters can be merged into it.

##  6 Unbiased Energy Assignment

In this section, we describe the definition of critical blocks for each target
(section 6.1) and the process of selecting favored seeds (section 6.2). We
then introduce how AFLRun assigns energy among seeds at the beginning of each
cycle with such information (section 6.3).

###  6.1 Critical Blocks

We firstly define a set $R$ as the set of all basic blocks that have been
covered by the current seed corpus, with $v\in R$ denoting a covered block
within the set. Next, we define _critical blocks_ $C_{t}$ for each target $t$
as a subset of $R$. The underlying idea is to identify a set of blocks for
each target at a given state, so that we should concentrate our fuzzing energy
on seeds that cover these blocks, ultimately enabling more efficient
exploration or exploitation of the target. In this section, we introduce this
concept.

For covered targets. During a fuzzing campaign, we can categorize the set of
all targets into two groups: one set consists of targets already covered by
the current corpus (i.e., $t\in R$), and the other set contains targets not
yet covered by the current corpus (i.e., $t\notin R$). If a target is already
covered, the critical block for this target is simply the target block itself.
Consequently, to fuzz this target, we should focus on fuzzing seeds that cover
such a target.

For uncovered targets. If a target is not yet covered, we should instead
attempt to find a seed that covers the target by fuzzing seeds in the current
corpus. Drawing on the intuition from [34], we define the critical blocks for
such a target as the blocks that lie at the _boundary between the explored and
unexplored parts of the path toward the target_ in the ICFG, known as critical
boundary blocks.

We firstly need to define some notations to introduce the exact definition of
critical blocks. Given a target basic block $t$, we can define a path333Here,
the term “path” does not refer to the program’s execution path. Instead, it
refers to the concept of a path as defined in graph theory. toward the target
in the ICFG as follows:

$v_{1}\rightarrow v_{2}\rightarrow...\rightarrow v_{n}\rightarrow t$

In the path above, $v_{i}$ with $i\in\\{1,...,n\\}$ are basic block vertices
in the ICFG, and each arrow is either a control flow edge or a call edge that
connects two adjacent vertices in the ICFG. The idea behind critical boundary
blocks is to find each block visited by the corpus such that there exists a
path from this block to target, and all vertices along this path are basic
blocks not yet visited by the corpus except for the block itself. This
definition aligns with the intuition of finding covered blocks at the boundary
mentioned earlier, with the uncovered blocks considered as the unexplored
part. Formally, critical blocks of an uncovered target $t$ can be defined as
all blocks $v_{1}\in R$ such that there exists a path from $v_{1}$ to $t$ with
$\forall_{v\in\\{v_{2},v_{3},...,v_{n},t\\}}v\notin R$.

Example. We provide an example to illustrate concept of critical blocks.
Figure 5 is the CFG of a program, with $1$ and $2$ as target blocks. We now
have three seeds in corpus with paths $A\rightarrow B\rightarrow C\rightarrow
H$, $A\rightarrow B\rightarrow D\rightarrow E$ and $A\rightarrow K\rightarrow
2$. We mark basic blocks covered by the corpus in gray. Among these blocks,
$C$ and $D$ are critical blocks of target $1$, because we can have two paths
to target $C\rightarrow 1$ and $D\rightarrow F\rightarrow G\rightarrow 1$
respectively, with $F$, $G$, $1$ not yet covered by the corpus. Furthermore,
$2$ itself is the critical block of target $2$, because the target has already
been covered by the corpus.

ABKCD2LHFEGI1J

Figure 5: Control Flow Graph

###  6.2 Favored Seed Selection

Besides a target virgin map for each cluster introduced in section 5.2, AFLRun
also maintains a top-rated array for each cluster, similar to the original
top-rated array discussed in section 2.1. When a new seed is added to the
corpus, a set of top-rated arrays are selected using Algorithm 3, and we
update these top-rated arrays using the same method as AFL++.

Using these top-rated arrays, we can select a set of favored seeds. We can
apply the queue culling algorithm, similar to AFL++, on all top-rated arrays
of all clusters to select the favored seeds. The process is described in
Algorithm 5. The parameter $top\\_rated\\_arrays$ represents the set of all
top-rated arrays, and the parameter $seeds$ represents the set of all seeds in
the corpus. For each top-rated array, we use the queue culling algorithm from
AFL++ to select a set of favored seeds, and we then take the union of each set
of favored seeds from each top-rated array to obtain the total set of favored
seeds.

Algorithm 5 Favored Seed Selection

0: $top\\_rated\\_arrays$ and $seeds$

1: favored_seeds = unique_set()

2: for top_rated $\in$ top_rated_arrays do

3: favored_seeds.union(cull_queue(top_rated))

4: end for

5: return favored_seeds

###  6.3 Energy Assignment

In this section, we will introduce the method for assigning energy among seeds
using critical blocks of each target. In previous directed fuzzing works, a
distance-to-target metric for each seed is used as the oracle for energy
assignment. By contrast, instead of using such distance oracle, we utilize
_critical blocks covered by each seed_ as the oracle for energy assignment.
The primary concept behind our algorithm involves distributing uniform weight
from targets through critical blocks to seeds. Our goal is to assign energy to
each seed at the beginning of a cycle so that the total energy of each seed
after assignment can approach the proportion of such seed weight as much as
possible. We will discuss this energy assignment algorithm in greater detail
in the following part.

Target weight. As mentioned earlier, AFLRun starts with uniform weight values
for all target basic block. Specifically, we have a vector of ones
representing the weight for each target, denoted as $\mathbf{1}$. However, our
approach does allow users to specify a customized weight value for each
target. We provide a detailed description of this by-product in Appendix B.

Block weight. In this part, we discuss how we distribute weight from each
target to its critical blocks. For each target $t$, we have a set of critical
blocks $C_{t}\subseteq R$. By taking the union of $C_{t}$ for all targets, we
obtain the set of all critical blocks $C\subseteq R$, where $R$ is the set of
all covered blocks defined earlier. We can now define a matrix $B$ for weight
distribution: each column of $B$ represents a corresponding target in the
weight vector $w$, and each row of $B$ represents a block in $C$. An element
of the matrix at row $b$ and column $t$ is defined as follows:

$B_{b,t}=\begin{cases}\frac{1}{distance[b,t]+k}&\text{if $b\in C_{t}$}\\\
0&\text{otherwise}\end{cases}$

In the equation, the term $distance[b,t]$ represents the distance from the
basic block $b$ to the target $t$, computed using the method described in
Appendix D, because this distance computation is only an auxiliary component
of our approach. The constant $k$ is a positive value that controls how
significantly the distance value influences the preference for a block. The
larger the value of $k$, the smaller the effect will be. Next, the matrix $B$
is normalized to $\hat{B}$, ensuring that each column of the matrix sums to
$1$. Now, the distribution of the set of critical blocks can be obtained by
calculating the product $\hat{B}\mathbf{1}$, which distributes weight from
each target to each critical block.

Seed weight. The process of distributing weight from each critical block to
seeds is quite similar to the distribution mentioned earlier. We also have a
matrix $S$ for this distribution: each column of $S$ represents a critical
block in $C$, while each row of $S$ represents a seed in the corpus. An
element at row $s$ and column $b$ can be defined as follows:

$S_{s,b}=\begin{cases}score[s]&\text{if favored $s$ covers $b$}\\\ 0.05\cdot
score[s]&\text{if unfavored $s$ covers $b$}\\\ 0&\text{otherwise}\end{cases}$

Next, matrix $S$ is also normalized to $\hat{S}$ to ensure that the sum of
each column is equal to $1$. The term $score[s]$ represents the energy
assigned to seed $s$ when fuzzed in coverage-guided mode, as computed by the
algorithm from AFL++. This energy can, in some sense, represent the preference
of a seed from AFL++’s perspective. We utilize this preference when
distributing weight from each critical block to seeds. Additionally, AFL++
skips unfavored seeds with a $95\%$ probability. We also follow this design by
calculating an expected energy for unfavored seeds. The favorability of a seed
is determined using the favored seeds selected in Algorithm 5. Finally, we can
calculate the seed weight vector by computing $\hat{S}\hat{B}\mathbf{1}+c$.
This final seed weight vector is also normalized to $r$, representing the
final ratio to be approached.

Seed energy assignment. Now, AFLRun can assign energy to seeds using the
obtained $r$. AFLRun also maintains a vector $b$ representing the energy that
has been assigned to each seed previously. Given a total energy value $E$ for
this cycle, we assign energy $E$ to each seed in the form of vector $x$, such
that $x+b$ can approach the ratio $r$ as closely as possible, under the
constraint $\sum_{i}x_{i}=E$. Instead of using a general algorithm of
mathematical optimization, we develop an algorithm with a worst-case
complexity of $O(n^{2})$ that guarantees the optimal solution. We discuss this
algorithm in Appendix A, as it is unrelated to fuzzing.

Preventing local optima. One problem of our energy assignment based on
critical blocks is the potential for local optima. To mitigate such issue,
during the calculation of the seed weight vector, we add a vector $c$, which
represents the energy assignment of each seed in coverage-guided fuzzing. The
sum of $c$ is calculated by multiplying the total energy (e.i., the number of
targets) by a small fraction.

##  7 Evaluation

In this section, we explore the following research questions through
experiments. RQ1: How effective is AFLRun at triggering vulnerabilities
compared to other fuzzers and ablated versions of AFLRun? (section 7.1) RQ2:
How effective is AFLRun in ensuring fairness for each target? (section 7.2)
RQ3: What is the runtime overhead incurred by AFLRun during fuzzing campaign?
(section 7.3) RQ4: Can AFLRun discover new zero-day vulnerabilities in
programs extensively fuzzed by OSS-Fuzz using state-of-the-art industrial
fuzzers? (section 7.4) RQ5: Do the extra seeds generated by AFLRun assist in
triggering vulnerabilities? (Appendix F)

Experiment setup. Unless otherwise specified, all experiments were conducted
on an Ubuntu 20.04.5 LTS machine equipped with an Intel(R) Xeon(R) Gold 5318S
CPU featuring 96 logical cores and 256 GB of RAM.

###  7.1 Fuzzer Comparison

We use two sets of vulnerabilities for experiments. Firstly, to compare AFLRun
with other fuzzers, we employ the Magma [21], a benchmark commonly used by
many fuzzing works, to evaluate multi-target directed fuzzing for bug
reproduction. Additionally, to demonstrate the individual contribution from
each component of AFLRun, we use another set of vulnerabilities in a real-
world bug discovery scenario to conduct an ablation study.

Settings. We set the confidence threshold to $100\%$ to only cluster target
blocks that consistently dominate each other, because the target sites do not
cause significant overhead in these experiments. We also individually remove
two key components from AFLRun, resulting in variations denoted as AFLRun\-
and AFLRun*. AFLRun\- refers to AFLRun devoid of the target path-diversity
metric, while AFLRun* denotes AFLRun employing AFL++’s energy assignment
rather than our unbiased energy assignment. Following the fuzzing papers’
general experimental approach, we ran each fuzzing campaign for 24 hours and
repeated 10 times. To prevent interference between experiments, we left some
CPU cores unused, in line with previous research practices.

####  7.1.1 Evaluation on Magma

Magma operates by reintroducing multiple 1-day bugs into real-world programs
using patches, enabling us to set multiple targets based on these patches and
simultaneously fuzz multiple bugs. We excluded some bugs that can be found in
less than ten minutes by coverage-guided fuzzers, as these bugs can also be
discovered by directed fuzzers while still in coverage-guided mode, which
would not effectively demonstrate the efficacy of directed fuzzing.

Fuzzers for comparison. We compare AFLRun with five fuzzers: AFL++ [20], AFLGo
[12], Hawkeye [13], Parmesan [32], and FishFuzz [40]. We choose AFL++ because
it is the grey box fuzzer upon which we build AFLRun, and select AFLGo and
Parmesan as they are open-source directed fuzzers commonly used for
comparison. We also include Hawkeye and FishFuzz, as they both attempt to
address the global optimum discrepancy problem. However, since Hawkeye is not
open-source, we implement our own prototype based on the approaches described
in the paper. We exclude works that are orthogonal to our approach [35, 28,
23, 41], because these works can be applied on top of AFLRun without modifying
both methods.

Target locations. Magma inserts one or more MAGMA_LOG macros into the tested
program for each bug to notify when the bug is covered or triggered during
execution. We designate the locations of these macros as targets for each bug.
Furthermore, Magma patches the program to invert the commits that fix the
bugs, and we set these locations as targets as well.

Table 1: Magma Benchmark Results

Bug ID | AFL++ | AFLGo | Parmesan | FishFuzz | Hawkeye | AFLRun |  AFLRun-
---|---|---|---|---|---|---|---
LUA002 | T.O. | T.O. | T.O. | T.O. | T.O. | T.O. | 23.32h
LUA004 | 4.23h | 8.69h | T.O. | 5.93h | 3.37h | 15.41h | 20.42h
PDF002 | T.O. | T.O. | N/A | T.O. | 21.72h | 17.10h | 21.65h
PDF003 | 6.60h | 3.84h | N/A | 5.74h | 7.78h | 4.04h | 2.15h
PDF006 | 17.49h | T.O. | N/A | T.O. | T.O. | 22.81h | T.O.
PDF011 | 22.83h | T.O. | N/A | T.O. | T.O. | T.O. | T.O.
PDF014 | T.O. | T.O. | N/A | T.O. | T.O. | 21.32h | 21.69h
PDF018 | 14.87h | 21.67h | N/A | 19.37h | 22.48h | 36.39m | 3.13h
PDF019 | 20.51h | 21.63h | N/A | T.O. | T.O. | T.O. | 18.44h
PDF021 | 23.89h | 23.47h | N/A | T.O. | T.O. | T.O. | 22.55h
PHP004 | 17.97h | 8.67m | N/A | 77.75m | 48.82m | 9.86m | 12.87m
PHP009 | 25.55m | 7.04m | N/A | 50.94m | 6.96m | 2.81m | 8.01m
PNG001 | T.O. | 22.73h | T.O. | T.O. | 21.61h | 22.12h | 18.46h
PNG007 | 9.97h | 3.86h | T.O. | 4.07h | 1.68h | 8.44m | 29.83m
SND017 | 15.02m | 17.23m | N/A | 31.44m | 10.99h | 13.27m | 15.10m
SND020 | 37.07m | 38.38m | N/A | 3.04h | 19.92h | 20.96m | 25.15m
SQL002 | 67.21m | 13.84m | N/A | 55.77m | 6.55m | 13.68m | 7.73m
SQL003 | 21.87h | 21.83h | N/A | 22.57h | T.O. | 23.79h | 20.12h
SQL012 | 20.06h | 22.61h | N/A | 20.09h | 23.88h | 19.15h | 15.70h
SQL013 | 22.81h | 22.93h | N/A | 22.91h | 23.29h | T.O. | 21.42h
SQL014 | 3.45h | 2.29h | N/A | 3.63h | 2.17h | 25.32m | 22.27m
SQL015 | 23.10h | 22.68h | N/A | 21.39h | 20.03h | T.O. | T.O.
SQL020 | 18.33h | 22.41h | N/A | 20.90h | 14.94h | 15.16h | 5.96h
SSL001 | 6.49h | 10.19h | 21.26h | 9.30h | 14.40h | 3.61h | 59.40m
SSL020 | 21.59h | 21.07h | 3.74h | 21.03h | 22.89h | 1.68h | 2.41h
TIF001 | T.O. | T.O. | T.O. | T.O. | 23.32h | 23.91h | T.O.
TIF002 | T.O. | 9.93h | T.O. | 16.09h | 11.31h | 19.90h | 16.38h
TIF005 | T.O. | 23.60h | 10.45h | 23.85h | T.O. | T.O. | 23.38h
TIF006 | 13.12h | 15.35h | 8.89h | 17.43h | 10.09h | 14.12h | 17.25h
TIF008 | T.O. | T.O. | T.O. | 22.26h | T.O. | 22.09h | T.O.
TIF009 | 11.63h | 15.96h | T.O. | 23.25h | 11.98h | 56.93m | 8.78h
TIF014 | 53.90m | 92.69m | 15.84h | 64.99m | 81.53m | 8.21m | 43.59m
XML001 | T.O. | 21.72h | 8.86h | 20.37h | 15.35h | 83.88m | 54.90m
XML002 | T.O. | T.O. | T.O. | T.O. | 22.11h | T.O. | T.O.
XML003 | 31.69m | 22.08m | 2.61m | 1.71h | 39.14m | 14.57m | 16.06m
XML006 | T.O. | T.O. | T.O. | 23.18h | T.O. | 22.36h | T.O.
XML009 | 42.69m | 6.69m | 13.28h | 37.59m | 11.95m | 8.04m | 9.31m
XML010 | T.O. | 23.18h | T.O. | T.O. | 22.36h | 14.63h | 8.75h
XML012 | T.O. | 20.48h | T.O. | 21.71h | 13.93h | 19.68h | 8.82h

Results. The results are presented in Table 1. Each entry in the table
represents the average exposure time required for the fuzzer to trigger the
vulnerability, calculated using survival analysis. We also computed p-values
using the Mann-Whitney U test [30], employing the alternative hypothesis that
AFLRun has a shorter exposure time. P-values are included in Table 6 of
Appendix. T.O. indicates that the bug was not triggered in any fuzzing
campaign. Note that Parmesan failed to run on some programs at either compile
time or runtime, even after we fixed some of its bugs, so we mark those
entries as N/A. We observe that AFLRun(-) outperforms other counterparts in
most cases. On average, using the geometric mean, AFLRun achieves speedup
factors of $168\%$, $109\%$, $235\%$, $183\%$ and $147\%$, and discovers
$38\%$, $20\%$, $162\%$, $29\%$ and $24\%$ more vulnerabilities compared to
AFL++, AFLGo, Parmesan, FishFuzz, and Hawkeye, respectively.

####  7.1.2 Evaluation on Real Scenario

The results from the Magma benchmark reveal that AFLRun does not significantly
outperform AFLRun-. Upon further investigation, we discovered that most bugs
in Magma are quite simple, probably because Magma requires easy detection of
bug trigger. However, our target path-diversity metric is designed to handle
complex bugs that require path diversity for triggering, thus the benchmark
results fail to fully illustrate the impact of our method. Moreover, the Magma
experiments are designed to test bug reproduction capability when the bug
sites are known. Yet, in real vulnerability discovery scenario such as the one
detailed in section 3.1, numerous false positive targets might also exist.
This situation has not been evaluated in the aforementioned benchmarking
experiment.

To address this deficiency of Magma benchmark, we conduct an additional
experiment in a different setting, using some bugs that align with our
scenario. To demonstrate the impact of encountering false-positive targets
(emulating real-world bug detection), we carry out the experiment under two
conditions: with and without the introduction of false-positive targets. Those
false-positive targets are randomly chosen from the bug reports detected by
Clang static analyzer [3]. The bug triggering time results are displayed in
Table 2.

We observe that AFLRun significantly outperforms AFLRun-. Furthermore, with
the introduction of false-positive targets, AFLRun generally exhibits superior
bug-triggering capability compared to AFLRun*. This indicates that the
unbiased energy assignment indeed helps in managing the seed explosion caused
by the increased target count.

These results are further elucidated by graphing the path diversity curves
from several experiments. For the corpus created by each fuzzing campaign, we
track the increase in path diversity of basic block coverage necessary to
trigger the vulnerability over time. For each set of repeated experiments, we
compute the mean and the corresponding confidence interval. The outcomes are
depicted in Figure 6. As seen in the figure, the target path-diversity metric
significantly enhances the path diversity of the target.

Table 2: Ablation Results

| without False Positives |  |  | with False Positives |  |
---|---|---|---|---|---|---
Bug ID | AFLRun |  AFLRun- |  AFLRun* | AFLRun |  AFLRun- |  AFLRun*
CVE-2023-25588 | 11.26h | T.O. | 9.25h | 14.97h | T.O. | 16.91h
CVE-2023-25587 | 6.86h | T.O. | 5.62h | 10.44h | T.O. | 11.86h
CVE-2022-44408 | 0.31h | 13.14h | 1.20h | 0.59h | 5.58h | 23.50h
CVE-2018-13785 | 0.55h | T.O. | 0.92h | 0.42h | T.O. | 0.56h
CVE-2013-6954 | 0.57h | 3.50h | 0.37h | 0.46h | 2.74h | 0.32h

Figure 6: Path diversity curves

###  7.2 Target Fairness Comparison

In this experiment, we evaluate the effectiveness of AFLRun in balancing each
target compared to its counterparts, addressing RQ2. We aim to scale up the
total number of targets by utilizing recently introduced commits as target
sites for each program in the Magma benchmark [21]. We also disable the bugs
introduced by Magma, as we are not concerned with their triggering in this
experiment. Furthermore, since the primary goal of this experiment is to
assess the effectiveness of our unbiased energy assignment, we have ablated
the target path-diversity metric (i.e., we use AFLRun-).

We conducted the experiment for three directed fuzzers: Hawkeye, FishFuzz, and
AFLRun-. For each fuzzer, we carried out an 8-hour fuzzing campaign, repeating
each experiment 10 times. We recorded the energy assigned (i.e., the number of
mutations and executions performed) to each seed. Additionally, we used a
modified version of afl-showmap to determine the target coverage of each seed.
With this information, we computed the total energy spent on fuzzing each
target. We sorted the energy for each target and plotted a graph similar to
the one in FishFuzz [40]. The results are illustrated in Figure 7. The x-axis
represents all targets ordered incrementally by energy spent on them, and the
y-axis is the corresponding energy. We can see that AFLRun generates flatter
curves compared to other counterparts, indicating a more balanced energy
assignment for each target, especially for libtiff and libxml2.

Figure 7: Energy spent on each target

###  7.3 Overhead Measurement

To evaluate the overhead incurred by AFLRun at runtime in response to RQ3, we
aim to scale up the total number of targets by utilizing target sites of
recent commits from section 7.2. Similarly, the fuzzing campaign is conducted
with the vulnerabilities introduced into these programs disabled.

To demonstrate the effectiveness of our clustering algorithm, we conducted
overhead experiments under five different configurations: for three of them,
we enabled target clustering with varying confidence threshold values of
$50\%$, $70\%$, and $90\%$ and a consistent support count threshold value of
$500$; for one of them, the clustering was disabled, meaning each target
corresponds to a distinct virgin map and top-rated array; for the last one, we
removed our path diversity component (AFLRun-). We ran each experiment for 3
hours, which was repeated 20 times. We recorded the number of clusters at the
end of each fuzzing campaign and calculated the arithmetic mean across all
repeated experiments for each configuration. Similarly, we profiled the
proportion of time spent in AFLRun process to total time for each fuzzing
campaign and calculated the mean. The results are shown in Table 3.
Additionally, we measured the overhead incurred by the instrumented code.
However, such overhead is negligible: it occupies less than $0.01\%$ of total
time in every fuzzing campaign.

Table 3: Overhead Results: The upper values of each program are average number
of clusters; the lower values are time ratio spent in the PUT.

Program | Threshold = 50% | Threshold = 70% | Threshold = 90% | w/o Cluster | w/o Diversity
---|---|---|---|---|---
libpng | 157.85 | 159.35 | 157.05 | 327.05 | 1.0
| 86.03% | 86.07% | 86.31% | 80.41% | 93.26%
libsndfile | 303.05 | 302.35 | 307.95 | 332.6 | 1.0
| 97.60% | 97.66% | 97.62% | 97.08% | 98.33%
libtiff | 188.75 | 190.2 | 189.25 | 188.3 | 1.0
| 78.27% | 80.00% | 77.29% | 81.97% | 91.24%
libxml2 | 156.45 | 171.95 | 188.25 | 366.15 | 1.0
| 96.85% | 96.97% | 96.79% | 95.46% | 98.23%
lua | 342.2 | 326.85 | 339.2 | 335.2 | 1.0
| 97.73% | 97.69% | 97.70% | 97.75% | 99.45%
poppler | 159.95 | 169.35 | 164.85 | 173.65 | 1.0
| 99.06% | 99.08% | 99.07% | 98.98% | 99.48%

Each row in the table represents a different configuration. The first three
columns represent experiments with varying confidence threshold values; the
fourth column represents an experiment without the clustering algorithm; and
the last column represents an experiment with AFLRun-. Each entry displays a
pair of values: the upper value represents the average number of clusters when
the fuzzing campaigns terminate, and the lower value is the average ratio of
time spent executing the PUT over the total time of each fuzzing campaign. We
can observe that the overhead is not significant compared to the time spent in
executing the PUT. Additionally, the clustering algorithm that reduces the
total number of virgin maps significantly does decrease some overhead spent in
the fuzzer.

###  7.4 Vulnerability Discovery

Lastly, we present all vulnerabilities found by AFLRun to answer RQ4. We use
AFLRun to fuzz the latest versions of some famous programs that have been
continuously fuzzed by the OSS-Fuzz project [7] using powerful Google
machines. We integrate AFLRun into OSS-Fuzz to simplify fuzzing each program
without struggling with the environment. Since AFLRun is a directed fuzzer, we
set target locations using two approaches. First, we attempt to fuzz recently
introduced commits by setting recently changed code locations as targets. The
intuition behind this is that recently modified code may be more error-prone
because older code has already been thoroughly fuzzed by OSS-Fuzz, while new
code is less fuzzed. Second, we use the static analysis tool to identify
suspicious code locations. Specifically, we write CodeQL [17] queries to find
potentially vulnerable code locations as our targets.

Table 4: Zero-day vulnerabilities found by AFLRun.

Project | ID | Type | Status
---|---|---|---
wabt | CVE-2022-44407 | Out-of-bounds Read | Fixed
wabt | CVE-2022-44408 | Type Confusion | Fixed
wabt | CVE-2022-44409 | Out-of-bounds Read | Fixed
skia | issue-40045089 | Uncontrolled Recursion | Accepted
freetype | issue-1159 | Uncontrolled Recursion | Fixed
binutils | CVE-2023-25585 | Access of Uninitialized Pointer | Fixed
binutils | CVE-2023-25587 | NULL Pointer Dereference | Fixed
binutils | CVE-2023-25588 | Access of Uninitialized Pointer | Fixed
binutils | CVE-2023-25586 | Use of Uninitialized Variable | Fixed
binutils | CVE-2023-25584444This CVE consists of a group of 20 vulnerabilities in total. We conduct a case study for this CVE and list each of the individual vulnerability IDs in the Appendix C. | Out-of-bounds Read | Fixed

We discovered 29 previously unknown vulnerabilities in these programs, which
are listed in Table 4. We responsibly reported them to the vendors. All
vulnerabilities marked as Fixed have already been addressed by the developers
in the upstream. At the time of writing, 28 vulnerabilities have been fixed,
and 8 CVE IDs have been assigned.

##  8 Related Work

###  8.1 Improving Coverage Metric

Numerous studies aim to enhance fuzzing effectiveness by refining the coverage
metric. Angora [14] considers call context under which each edge is covered to
make coverage metric context-sensitive. MemFuzz [16] uses address of memory
access as extra coverage metric. Ankou [29] designs a new fitness function
based on distance between execution paths of test cases, and their approach
also allows to store extra seeds that do not achieve new coverage. Ijon [10]
improves coverage metric to explore deep state in specific tested program by
taking advantage of the guidance of user-defined annotations marked on
important data in the program. AFL-Hier [36] proposes a multi-level coverage
metric and a reinforcement-learning-based hierarchical scheduler in order to
handle seed explosion problem introduced by more fine-grained coverage metric.

Some other works also have proposed coverage metric in order to find domain-
specific bugs. SlowFuzz [33] uses number of executed instructions as metric to
find bugs caused by worst case of algorithm complexity. PerfFuzz [26]
similarly uses maximum count of each program location as storage metric of new
seed to also find complexity bugs. MemLock [38] proposes memory usage as
guidance to store extra seeds in order to find uncontrolled memory consumption
bugs. Krace [39] designs a coverage tracking metric specially designed to find
bugs caused by data races in kernel file system.

All of these works have developed new coverage metrics for coverage-guided
fuzzing, while in contrast, AFLRun introduces a new coverage metric
specifically for directed fuzzing. To the best of our knowledge, we are the
first to primarily focus on this task, utilizing the coverage metric based on
multiple virgin maps for targets. Moreover, some of the mentioned works [29,
36] devise novel seed scheduling algorithms to address the seed explosion
problem caused by their new coverage metrics. Similarly, AFLRun also proposes
a new energy assignment algorithm for directed fuzzing, which not only serves
the path diversity but also tackles the seed explosion problem.

###  8.2 Directed Fuzzing

AFLGo [12] firstly proposes directed greybox fuzzing to guide greybox fuzzing
toward a set of user-defined targets. It proposes a distance oracle for each
seed, which is used for energy assignment to favor seed closer to targets.
However, such distance oracle is a very crude metric representing preference
of seed with respect to targets. Hawkeye [13] improves directed fuzzing on top
of design of AFLGo based on several desired properties it should hold.
Parmesan [32] finds targets using information from compiler sanitizer passes,
and it also proposes some methods of directed fuzzing such as dynamically
constructing ICFG during fuzzing campaign. WindRanger [19] improves distance
computation from a seed to targets by only considering basic blocks that
deviate from path toward targets. However, it does not take multiple targets
into account when obtaining such blocks. In addition, their definition of
deviation block is local and is based on only one seed, while our critical
blocks are global and take all seeds in corpus into account. LeoFuzz [27] is
the first work that realizes the problem of using harmonic average distance of
all targets, and it proposes a method based on target sequence in order to
solve it. FishFuzz [40] also addresses such problem by using a distance vector
for each seed instead of an average distance. By contrast, energy assignment
of AFLRun not only solves such problem in a more fine-grained way, but also
serves for our path diversity component. Finally, CAFL [25] takes sequence of
locations with constraints as target, but such sequence requires more manual
effort than other directed fuzzers.

There are other works that try to improve performance of directed fuzzing by
trimming redundant parts considered irrelevant to targets in fuzzing campaign.
FuzzGuard [41] uses deep learning to filter out test case considered to be
unhelpful for reaching target, so it is not executed by tested program
beforehand. BEACON [23] applies static analysis to terminate program early if
current program state is guaranteed to be unable to reach any targets.
SieveFuzz [35] also terminates the program early by restricting fuzzing to
search space guaranteed relevant to reaching targets. SelectFuzz [28]
selectively instruments and explores only target-relevant code, and it also
proposes a novel distance metric from a basic block to target based on multi-
path reaching probability. These works about trimming are considered
orthogonal to our approach.

##  9 Conclusion

This paper proposes AFLRun, a novel directed fuzzing approach that aims to
improve the path diversity of already-covered targets for better triggering of
vulnerabilities. It utilizes target path-diversity metric, in which an extra
virgin map is maintained for each target to record the coverage status of the
seeds that hit the target. It also involves unbiased energy assignment, in
which the seeds that cover the same target split the weight assigned to the
target. Through evaluation on a standard benchmark and real-world programs, we
demonstrate that AFLRun outperforms the state-of-the-art fuzzers in triggering
known bugs and discovering zero-day vulnerabilities.

## References

  * [1] American fuzzy lop.  https://lcamtuf.coredump.cx/afl/technical_details.txt.
  * [2] Analyzing data flow in c and c++.  https://codeql.github.com/docs/codeql-language-guides/analyzing-data-flow-in-cpp/.
  * [3] Clang static analyzer.  https://clang-analyzer.llvm.org/.
  * [4] Honggfuzz.  https://honggfuzz.dev/.
  * [5] libfuzzer - a library for coverage-guided fuzz testing.  https://llvm.org/docs/LibFuzzer.html.
  * [6] Llvm link time optimization: Design and implementation.  https://llvm.org/docs/LinkTimeOptimization.html.
  * [7] Oss-fuzz.  https://google.github.io/oss-fuzz/.
  * [8] robin_hood unordered map & set.  https://github.com/martinus/robin-hood-hashing.
  * [9] Rakesh Agrawal, Tomasz Imielinski, and Arun N. Swami.  Mining association rules between sets of items in large databases.  In ACM SIGMOD Conference, 1993.
  * [10] Cornelius Aschermann, Sergej Schumilo, Ali Reza Abbasi, and Thorsten Holz.  Ijon: Exploring deep state spaces via fuzzing.  2020 IEEE Symposium on Security and Privacy (SP), pages 1597–1612, 2020.
  * [11] Marcel Böhme, Bruno C. d. S. Oliveira, and Abhik Roychoudhury.  Regression tests to expose change interaction errors.  In Bertrand Meyer, Luciano Baresi, and Mira Mezini, editors, Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE’13, Saint Petersburg, Russian Federation, August 18-26, 2013, pages 334–344. ACM, 2013.
  * [12] Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury.  Directed greybox fuzzing.  Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017.
  * [13] Hongxu Chen, Yinxing Xue, Yuekang Li, Bihuan Chen, Xiaofei Xie, Xiuheng Wu, and Yang Liu.  Hawkeye: Towards a desired directed grey-box fuzzer.  Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018.
  * [14] Peng Chen and Hao Chen.  Angora: Efficient fuzzing by principled search.  2018 IEEE Symposium on Security and Privacy (SP), pages 711–725, 2018.
  * [15] Maria Christakis, Peter Müller, and Valentin Wüstholz.  Guiding dynamic symbolic execution toward unverified program executions.  In Laura K. Dillon, Willem Visser, and Laurie A. Williams, editors, Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016, pages 144–155. ACM, 2016.
  * [16] Nicolas Coppik, Oliver Schwahn, and Neeraj Suri.  Memfuzz: Using memory accesses to guide fuzzing.  2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST), pages 48–58, 2019.
  * [17] Oege de Moor, Mathieu Verbaere, Elnar Hajiyev, Pavel Avgustinov, Torbjörn Ekman, Neil Ongkingco, Damien Sereni, and Julian Tibble.  Keynote address: .ql for source code analysis.  Seventh IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2007), pages 3–16, 2007.
  * [18] Edsger W. Dijkstra.  A note on two problems in connexion with graphs.  Numerische Mathematik, 1:269–271, 1959.
  * [19] Zhengjie Du, Yuekang Li, Yang Liu, and Bing Mao.  Windranger: A directed greybox fuzzer driven by deviation basic blocks.  2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE), pages 2440–2451, 2022.
  * [20] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse.  Afl++ : Combining incremental steps of fuzzing research.  In WOOT @ USENIX Security Symposium, 2020.
  * [21] Ahmad Hazimeh, Adrián Herrera, and Mathias Payer.  Magma: A ground-truth fuzzing benchmark.  ACM SIGMETRICS Performance Evaluation Review, 49:81 – 82, 2020.
  * [22] Marc Heuse, Heiko Eißfeldt, Andrea Fioraldi, and Dominik Maier.  afl-clang-lto - collision free instrumentation at link time.  https://github.com/AFLplusplus/AFLplusplus/blob/stable/instrumentation/README.lto.md, 1 2022.
  * [23] Heqing Huang, Yiyuan Guo, Qingkai Shi, Peisen Yao, Rongxin Wu, and Charles Zhang.  Beacon: Directed grey-box fuzzing with provable path pruning.  2022 IEEE Symposium on Security and Privacy (SP), pages 36–50, 2022.
  * [24] Chris Lattner and Vikram S. Adve.  Llvm: a compilation framework for lifelong program analysis & transformation.  International Symposium on Code Generation and Optimization, 2004. CGO 2004., pages 75–86, 2004.
  * [25] Gwangmu Lee, Woo-Jae Shim, and Byoungyoung Lee.  Constraint-guided directed greybox fuzzing.  In USENIX Security Symposium, 2021.
  * [26] Caroline Lemieux, Rohan Padhye, Koushik Sen, and Dawn Xiaodong Song.  Perffuzz: automatically generating pathological inputs.  Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, 2018.
  * [27] Hongliang Liang, Xianglin Cheng, Jie Liu, and Jin Li.  Multiple targets directed greybox fuzzing.  ArXiv, abs/2206.14977, 2022.
  * [28] Changhua Luo, Wei Meng, and Penghui Li.  Selectfuzz: Efficient directed fuzzing with selective path exploration.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 1050–1064. IEEE Computer Society, 2022.
  * [29] Valentin J. M. Manès, Soomin Kim, and Sang Kil Cha.  Ankou: Guiding grey-box fuzzing towards combinatorial difference.  2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE), pages 1024–1036, 2020.
  * [30] Henry B. Mann and Douglas R. Whitney.  On a test of whether one of two random variables is stochastically larger than the other.  Annals of Mathematical Statistics, 18:50–60, 1947.
  * [31] Manh-Dung Nguyen, Sébastien Bardin, Richard Bonichon, Roland Groz, and Matthieu Lemerre.  Binary-level directed fuzzing for use-after-free vulnerabilities.  In International Symposium on Recent Advances in Intrusion Detection, 2020.
  * [32] Sebastian Österlund, Kaveh Razavi, Herbert Bos, and Cristiano Giuffrida.  Parmesan: Sanitizer-guided greybox fuzzing.  In USENIX Security Symposium, 2020.
  * [33] Theofilos Petsios, Jason Zhao, Angelos D. Keromytis, and Suman Sekhar Jana.  Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities.  Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017.
  * [34] Dongdong She, Abhishek Shah, and Suman Sekhar Jana.  Effective seed scheduling for fuzzing with graph centrality analysis.  2022 IEEE Symposium on Security and Privacy (SP), pages 2194–2211, 2022.
  * [35] Prashast Srivastava, Stefan Nagy, Matthew Hicks, Antonio Bianchi, and Mathias Payer.  One fuzz doesn’t fit all: Optimizing directed fuzzing via target-tailored program state restriction.  Proceedings of the 38th Annual Computer Security Applications Conference, 2022.
  * [36] Jinghan Wang, Chengyu Song, and Heng Yin.  Reinforcement learning-based hierarchical seed scheduling for greybox fuzzing.  In Network and Distributed System Security Symposium, 2021.
  * [37] Pengfei Wang and Xu Zhou.  Sok: The progress, challenges, and perspectives of directed greybox fuzzing.  ArXiv, abs/2005.11907, 2020.
  * [38] Cheng Wen, Haijun Wang, Yuekang Li, Shengchao Qin, Yang Liu, Zhiwu Xu, Hongxu Chen, Xiaofei Xie, Geguang Pu, and Ting Liu.  Memlock: Memory usage guided fuzzing.  2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE), pages 765–777, 2020.
  * [39] Meng Xu, Sanidhya Kashyap, Hanqing Zhao, and Taesoo Kim.  Krace: Data race fuzzing for kernel file systems.  2020 IEEE Symposium on Security and Privacy (SP), pages 1643–1660, 2020.
  * [40] Han Zheng, Jiayuan Zhang, Yuhang Huang, Zezhong Ren, He Wang, Chunjie Cao, Yuqing Zhang, Flavio Toffalini, and Mathias Payer.  Fishfuzz: Throwing larger nets to catch deeper bugs.  ArXiv, abs/2207.13393, 2022.
  * [41] Peiyuan Zong, Tao Lv, Dawei Wang, Zizhuang Deng, Ruigang Liang, and Kai Chen.  Fuzzguard: Filtering out unreachable inputs in directed grey-box fuzzing through deep learning.  In USENIX Security Symposium, 2020.

##  Appendix A Mathematical Optimization Algorithm

We can state the problem as follows. We are given with a ratio vector
$r\in\mathbb{R}^{n}$ that satisfies $\sum_{i=1}^{n}r_{i}=1$, a vector
$b\in\mathbb{R}^{n}$ and a scalar value $E\in\mathbb{R}$, and these values
should all be non-negative. We want to find a non-negative vector
$x\in\mathbb{R}^{n}$ such that $\sum_{i=1}^{n}x_{i}=E$, so that distribution
of $x+b$ can approach ratio vector $r$ as much as possible. A naive algorithm
is to convert the problem into a convex optimization problem by minimizing
cross entropy loss between normalized $x+b$ and $r$ under certain constraints.
However, if $n$ is large, state-of-art solvers are not able to get the optimal
solution in feasible time limit. Instead, we develop an algorithm with worst
time complexity $O(n^{2})$ that guarantees the optimal solution.

The key intuition of the algorithm is to calculate the sum of total value
after assignment by $E^{\prime}=E+\sum_{i=1}^{n}b_{i}$, with such value we can
calculate the most desirable result for $x+b$ by $d={E^{\prime}}r$. In ideal
situation where $d_{i}\geq b_{i}$ for $i\in\\{1,...,n\\}$, we can achieve such
most desirable result by $x=d-b$.

However, in reality, there must be some entries where $d_{i}<b_{i}$. Since
elements of $x$ cannot be negative, we cannot do $x=d-b$. The idea is that we
for all $i$ such that $d_{i}<b_{i}$, we can know that we must let $x_{i}=0$.
Therefore, we can remove all such entries to create another sub-problem, and
we do this recursively until $d_{i}\geq b_{i}$ always holds. The algorithm is
detailed in Algorithm 7.

##  Appendix B Target Weight Calculation

At compile time, AFLRun can be provided with a set of target locations with
their corresponding weight. Target location is a pair of file name and line
number, usually in format file.c:123. Target basic block, on the other hand,
is the basic block in tested program that contains at least one target
location. We show how we compute weight of target block from weight of target
location in this section. Each target location can be contained by one or more
target basic blocks, and each target block can also contain one or more target
locations. With such information, we distribute weight from target locations
to target blocks using distribution matrix. Each column of the matrix
represent a target location, and each row of the matrix represent a target
block. We define matrix $\Phi$ as follows:

${\Phi}_{b,l}=\begin{cases}\frac{1}{N_{l}}&\text{if target block $b$ contains
target location $l$}\\\ 0&\text{otherwise}\end{cases}$

$N_{l}$ is the total number of target blocks that contain target location $l$,
and we should note that each column of this matrix sums to $1$. Finally, we
can multiply $\Phi$ by weight vector of target locations to obtain weight of
each target block. At this point, we can discard these target locations, and
unless otherwise specified, we use target to denote target basic block instead
of target location in this paper.

##  Appendix C CVE-2023-25584

We demonstrate how we were able to find CVE-2023-25584, a group of out-of-
bounds read vulnerabilities in binutils, using AFLRun. The first vulnerability
in this group we have discovered occurs at the parse_module function in the
vms-alpha.c file. This bug was discovered by targeting recently changed code
locations, and indeed, the file had been recently modified to fix some bugs.
The root cause of this bug, although not directly related to these changed
code locations, could also be tested when fuzzing these targets, which
ultimately led to its discovery.

We subsequently analyzed this vulnerability and discovered that numerous
nearby locations appeared to exhibit a similar issue due to the access of the
same pointer, ptr. We wrote a simple static taint analysis query using CodeQL
[17, 2] to collect all locations that access ptr. We then initiated several
concurrent fuzzing campaigns using these locations as targets. Consequently, a
significant number of vulnerabilities were uncovered within 24 hours.

For these fuzzing campaigns, the initial corpus was unable to cover any blocks
that could reach any targets in the ICFG due to the indirect call. This
resulted in an empty set of critical block, prompting AFLRun to first run in
coverage-guided mode.

As the fuzzing campaigns progress, coverage-guided fuzzing manages to find a
seed that covers some of these blocks, generating critical blocks and
prompting AFLRun to transition into directed fuzzing mode. However, certain
constraints along the path to the target sites are difficult to solve,
preventing other fuzzers from hitting these targets and causing these
vulnerabilities to remain undetected by OSS-Fuzz. Thanks to our energy
assignment algorithm, AFLRun assigns a significant amount of energy to fuzz
this seed, effectively passing these constraints and subsequently covering the
targets. By fuzzing these targets, a group of out-of-bounds read
vulnerabilities has been identified.

We list all vulnerability IDs of this CVE as follows:

  * •

29848

  * •

29882

  * •

29873

  * •

29874

  * •

29875

  * •

29876

  * •

29877

  * •

29878

  * •

29879

  * •

29880

  * •

29881

  * •

29883

  * •

29884

  * •

29885

  * •

29886

  * •

29887

  * •

29888

  * •

29889

  * •

29890

  * •

29891

##  Appendix D Static Distance Computation

We have developed an efficient method for computing the distance from each
block to each target in $O(|T||E|+|T||V|log|V|)$, where $V$ and $E$ represent
vertices and edges of the ICFG, and $T\subset V$ denotes the target blocks. We
firstly define the weight of each edge from vertex $v_{src}$ to vertex
$v_{dst}$ as follows:

$W(v_{src},v_{dst})=\begin{cases}{log}_{2}(N_{out}(v_{src}))&\text{for
control-flow edge}\\\ 0&\text{for call edge}\end{cases}$

The term $N_{out}(v_{src})$ represents the number of control-flow outgoing
edges of vertex $v_{src}$. The rationale behind this weight definition is to
assign higher weight to edges that are less likely to be traversed after
executing the basic block $v_{src}$. As a result, the weight of both call
edges and unconditional control-flow edges should be $0$, while the weight of
conditional control-flow edges grows logarithmically with respect to the
number of outgoing edges.

After obtaining the weight for each edge, we can define the distance from
block $v$ to target $t$ as the sum of weight along the shortest path from $v$
to $t$. This can be computed using Dijkstra’s algorithm [18]. A naive approach
involves applying Dijkstra’s algorithm for each $v\in V$, as done by AFLGo
[12]. However, this method has a time complexity of $O(|V||E|+|V|^{2}log|V|)$,
which can be very slow for large ICFGs. Instead, we compute this distance by
_reversing each edge_ of the ICFG and applying Dijkstra’s algorithm for each
$t\in T$, since the shortest distance from $v$ to $t$ in the ICFG is equal to
the shortest distance from $t$ to $v$ in the transposed ICFG. As the set of
targets $T$ is usually much smaller than the set of basic blocks $V$ in
directed fuzzing, this method is significantly more efficient than the naive
one. We describe this method in Algorithm 6.

Algorithm 6 Distance Computation

0:  _ICFG_

1: ICFG’ = transpose(ICFG)

2: distance: $V\times T\rightarrow\mathbb{R}$

3: for $t\in T$ do

4: for (b, d) $\in$ Dijkstra(ICFG’, t) do

5: distance[b, t] = d

6: end for

7: end for

8: return distance

##  Appendix E Implementation

We have implemented AFLRun, a prototype based on the ideas presented, using
the source code from AFL++ [20] and AFLGo [12], totaling over 5,000 lines of
C/C++ code. In this section, we will discuss some implementation details.

Static analysis and instrumentation. The compilation stage of AFLRun is built
upon the LLVM [24] Link Time Optimization (LTO) pass [6] by modifying the
AFL++ LTO compiler [22]. First, we identify all target basic blocks. Then,
using information from LLVM, we construct the ICFG of the PUT. With the ICFG,
we gather all basic blocks that can reach at least one of the target blocks,
including the target blocks themselves, and calculate their distances to each
target block using the method described in appendix D. Each of these basic
blocks is assigned a unique ID. Moreover, to obtain critical blocks at
runtime, we record the subgraph of the ICFG with these blocks as vertices.
These blocks are instrumented with a function at the beginning, which will be
called with the block ID as an argument when the block is executed.

Virgin map comparison. In AFL++, when comparing the execution trace with the
virgin map, it avoids inefficiently comparing each bit individually. Instead,
it compares 64 bits at a time by casting pointers into 64-bit arrays. For each
64-bit value in the execution trace and virgin map, AFL++ calculates their
bitwise AND value, and a non-zero result indicates new bit coverage by the
execution trace. We employ the same technique for efficient comparisons with
multiple virgin maps by calculating the bitwise AND value between the
execution trace and each virgin map. Each non-zero AND value at each location
for each virgin map is also recorded and used to obtain $data$ in Algorithm 2.

Target clusters. We assign each cluster an ID, and each cluster contains a set
of targets recorded using an array indexed by the cluster ID. In addition to
recording the set of targets in each cluster, we also need to map each target
to its respective cluster in order to efficiently implement get_cluster
function in Algorithm 3. This is achieved using hash map [8].

Association rule mining. We implement support_count in Algorithm 4 using two
data structures: one for counting 1-itemsets and another for counting
2-itemsets. We record 1-itemset support counts using an array indexed by
cluster ID, while 2-itemset support counts are recorded using hash map [8],
utilizing order-insensitive pairs as keys.

Covered blocks. For efficiency, we only consider covered blocks that can reach
at least one target in the ICFG, each of which is assigned an ID during static
analysis. To trace the set of blocks covered by the execution of a test case,
we use a shared memory with $n$ bits, where $n$ is the number of blocks
assigned with an ID. Each bit in memory represents a distinct block. In the
instrumented function for each block with an ID, the block ID is obtained from
the argument, allowing instrumented code to set the corresponding bit in the
shared memory to $1$ to indicate that the block is covered during execution.
Furthermore, similar to the virgin map, we also have a virgin block bitmap
with $n$ bits to record each block covered by the corpus, enabling AFLRun to
determine whether a new seed covers any new blocks.

Energy assignment. The energy assignment algorithm discussed in section 6.3
involves matrix multiplication. However, since the related matrices are
typically sparse, computing matrix multiplication explicitly can be
inefficient. To address this, we represent each weight vector as a hash map
[8] and use the relevant information to directly distribute weight from one
hash map to another.

##  Appendix F Quality of Extra Seeds

In this appendix, we address RQ5 by counting the number of unique crashes that
are mutated from the extra seeds generated by our target path-diversity metric
and calculating its ratio over the total number of crashes. We continued to
use the results from the Magma benchmark [21] and enabled the fatal canary
feature in Magma, causing any bug trigger to result in a crash. For each seed
generated during the fuzzing campaign, AFLRun annotates its filename with the
factor contributing to its storage. Specifically, if a seed covers any new
bits in the primary virgin map, AFLRun marks a cov flag in its filename, and
similarly adds a div flag if any new bits are covered in the target virgin
map. Moreover, each unique crash is marked with the seed ID from which the
unique crash is mutated, also known as the source seed. Using this
information, we can track the flags of the source seed for each unique crash.
We consider a unique crash to be mutated from the extra seed only if its
source seed contains solely the div flag. We denote such unique crash as the
diversity crash. The results are presented in Table 5. We observe that for the
majority of programs, more than half of the unique crashes are mutated from
our extra seeds, demonstrating the ability of these extra seeds to discover
vulnerabilities.

Table 5: Statistics about Unique Crashes

Program | No. Diversity Crashes | No. Total Crashes | Ratio
---|---|---|---
libpng | 1336 | 1437 | 92.97%
libsndfile | 97 | 169 | 57.40%
libtiff | 4485 | 5476 | 81.90%
libxml2 | 3711 | 4448 | 83.43%
lua | 430 | 584 | 73.63%
openssl | 31 | 38 | 81.58%
php | 943 | 1084 | 86.99%
poppler | 753 | 1076 | 69.98%
sqlite3 | 675 | 1395 | 48.39%

Algorithm 7 approach_ratio

0: $E\in\mathbb{R}$, $b\in\mathbb{R}^{n}$ and $r\in\mathbb{R}^{n}$

1: $d$ := $(E+\sum_{i=1}^{n}b_{i})r$

2: remove := set()

3: for i := 1 to n do

4: if $d_{i}<b_{i}$ then

5: remove.insert(i)

6: end if

7: end for

8: $x\in\mathbb{R}^{n}$

9: if $|remove|=0$ then

10: for i := 1 to n do

11: $x_{i}$ := $d_{i}-b_{i}$

12: end for

13: return x

14: end if

15: $x^{\prime}\in\mathbb{R}^{n-|remove|}$,
$b^{\prime}\in\mathbb{R}^{n-|remove|}$, $r^{\prime}\in\mathbb{R}^{n-|remove|}$

16: j := 1

17: for i := 1 to n do

18: if i $\notin$ remove then

19: ${b^{\prime}}_{j}$ := $b_{i}$, ${r^{\prime}}_{j}$ := $r_{i}$

20: j := j + 1

21: end if

22: end for

23: $x^{\prime}$ := approach_ratio($E$, $b^{\prime}$, $r^{\prime}$)

24: j := 1

25: for i := 1 to n do

26: if i $\in$ remove then

27: $x_{i}$ := 0

28: else

29: $x_{i}$ := ${x^{\prime}}_{j}$

30: j := j + 1

31: end if

32: end for

33: return x

Table 6: P-values of Magma Benchmark Results

Bug ID | AFL++ | AFLGo | Parmesan | FishFuzz | Hawkeye
---|---|---|---|---|---
LUA002 | 0.18 | 0.18 | 0.18 | 0.18 | 0.18
LUA004 | 1.00 | 0.96 | <.01 | 0.99 | 1.00
PDF002 | 0.04 | 0.04 |  | 0.04 | 0.14
PDF003 | <.01 | 0.03 |  | 0.01 | <.01
PDF006 | 0.95 | 0.18 |  | 0.18 | 0.18
PDF011 | 0.86 | 1.00 |  | 1.00 | 1.00
PDF014 | 0.08 | 0.08 |  | 0.08 | 0.08
PDF018 | <.01 | <.01 |  | <.01 | <.01
PDF019 | 0.22 | 0.06 |  | <.01 | <.01
PDF021 | 0.50 | 0.50 |  | 0.18 | 0.18
PHP004 | <.01 | 0.76 |  | 0.45 | 0.21
PHP009 | <.01 | 0.11 |  | <.01 | 0.89
PNG001 | 0.02 | 0.07 | 0.02 | 0.02 | 0.11
PNG007 | <.01 | <.01 | <.01 | <.01 | <.01
SND017 | 0.55 | 0.24 |  | 0.14 | <.01
SND020 | <.01 | <.01 |  | <.01 | <.01
SQL002 | <.01 | 0.14 |  | <.01 | 0.76
SQL003 | 0.19 | 0.19 |  | 0.17 | 0.04
SQL012 | 0.06 | <.01 |  | 0.05 | <.01
SQL013 | 0.44 | 0.25 |  | 0.25 | 0.25
SQL014 | <.01 | <.01 |  | <.01 | 0.06
SQL015 | 0.86 | 0.86 |  | 0.94 | 0.97
SQL020 | <.01 | <.01 |  | <.01 | 0.01
SSL001 | <.01 | <.01 | <.01 | <.01 | <.01
SSL020 | <.01 | <.01 | 0.03 | <.01 | <.01
TIF001 | 0.18 | 0.18 | 0.18 | 0.18 | 0.56
TIF002 | <.01 | 0.96 | <.01 | 0.61 | 0.93
TIF005 | 0.18 | 0.50 | 0.99 | 0.50 | 0.18
TIF006 | 0.58 | 0.45 | 0.93 | 0.28 | 0.90
TIF008 | 0.04 | 0.04 | 0.04 | 0.19 | 0.04
TIF009 | <.01 | <.01 | <.01 | <.01 | <.01
TIF014 | <.01 | <.01 | <.01 | <.01 | <.01
XML001 | <.01 | <.01 | <.01 | <.01 | <.01
XML002 | 1.00 | 1.00 | 1.00 | 1.00 | 0.94
XML003 | 0.04 | 0.05 | 0.99 | <.01 | <.01
XML006 | 0.18 | 0.18 | 0.18 | 0.50 | 0.18
XML009 | <.01 | 0.37 | <.01 | <.01 | 0.06
XML010 | <.01 | <.01 | <.01 | <.01 | <.01
XML012 | <.01 | <.01 | <.01 | <.01 | 0.05