# Compositional Fuzzing
Aided by Targeted Symbolic Execution

Saahil Ognawala<EMAIL_ADDRESS>Fabian Kilger  Alexander Pretschner
Faculty of Informatics, Technical University of Munich,
Boltzmannstr. 3, 85748 Garching, Germany

###### Abstract

Guided fuzzing has, in recent years, been able to uncover many new
vulnerabilities in real-world software due to its fast input mutation
strategies guided by path-coverage. However, most fuzzers are unable to
achieve high coverage in deeper parts of programs. Moreover, fuzzers heavily
rely on the diversity of the seed inputs, often manually provided, to be able
to produce meaningful results.

In this paper, we present _Wildfire_ , a novel open-source compositional
fuzzing framework. Wildfire finds vulnerabilities by fuzzing isolated
functions in a C-program and, then, using targeted symbolic execution it
determines the feasibility of exploitation for these vulnerabilities. Based on
our evaluation of 23 open-source programs (nearly 1 million LOC), we show that
Wildfire, as a result of the increased coverage, finds more true-positives
than baseline symbolic execution and fuzzing tools, as well as state-of-the-
art coverage-guided tools, in only 10% of the analysis time taken by them.
Additionally, Wildfire finds many other potential vulnerabilities whose
feasibility can be determined compositionally to confirm if they are false-
positives. Wildfire could also reproduce almost all (15 out of 16) of the
known vulnerabilities and found several previously-unknown vulnerabilities in
three open-source libraries.

###### keywords:

Vulnerability analysis , Source-code coverage , Fuzzing , Symbolic execution ,
Compositional analysis

††journal: Journal of Systems and Software

##  1 Introduction

Fuzzing and symbolic execution are the two most popular techniques for
automatically generating test-cases and finding vulnerabilities that have had
a significant impact in the form of data and economic loss [53]. Fuzzing, in
particular, has recently been very successful [32, 45, 4] in revealing
exploitable vulnerabilities in open-source and widely used software, that
exposed them to severe security-related implications, such as buffer-
overflows. Fuzzing tools, such as AFL [57] and Peach [5], employ mutation
strategies that rapidly change the user-supplied seed-inputs based on some
heuristics. With appropriate instrumentation and fast mutation of inputs, the
fuzzer may trigger interesting parts in the code where improper input handling
may lead to a program crash, hang, or other undesirable behaviours. Most of
the vulnerabilities found by fuzzers, however, are located in parts of the
code that are relatively easy to reach [23, 36] for randomly mutated input
data. The more _complex_ parts of the program, which are guarded by branching
conditions that cannot be satisfied by most random mutations are not reached,
and hence not sufficiently explored, by the state-of-the-art fuzzers.

On the whitebox analysis side, symbolic execution [26], and their practical
approaches such as concolic execution [43, 12] and whitebox fuzzing [24],
suffer from the well-known path-explosion problem [11] due to which execution
gets stuck in the shallow branches. Compositional analysis has been proposed
in the past [40, 7] as a technique to alleviate the path-explosion problem in
symbolic execution. It analyzes individual components that make up a larger
system and, then, prunes away those paths in the program that do not lead to
interesting executions of those components, such as vulnerability triggers.
Results show [16, 34] that compositional analysis is trivially able to cover
more parts of the program than plain symbolic execution and also, indeed,
discovers more vulnerabilities in programs.

Fuzzing has not been, to the best of our knowledge, considered as a viable
option for compositional analysis yet. We aim to bridge this research gap in
this paper. The goal of our work is to improve vulnerability detection
capability of fuzzers through increasing coverage in isolated functions. We
define _isolated functions_ as those functions that are parameterized, i.e.
g(int a) can be isolated but not g(void). Our central premise is that, as
shown by previous works [34, 23], higher coverage in isolated functions leads
to an increase in discovered vulnerabilities as well. Then, our methodology
employs targeted symbolic execution to perform a reachability analysis for the
vulnerabilities discovered by fuzzing, so that we may confirm which
vulnerabilities can also be exploited from higher level calling contexts.

##### Problem

Even though state-of-the-art fuzzers are capable of effectively finding
vulnerabilities in programs that accept input from files or standard input,
the line coverage achieved by these fuzzers is insufficient. In particular, as
shown by previous studies [36], the coverage of functions lying deeper in the
call-graph of the program is very low for fuzzers. As a result, these fuzzers
miss many vulnerabilities in deep-lying parts of programs.

##### Solution

Drawing inspiration from past works in the improvement of plain symbolic
execution [16, 21], we present a compositional analysis approach for fuzzing
large real-world programs. We, first of all, fuzz isolated functions using
automatically generated seed-inputs. In this step, functions at all depths of
the program’s call-graph can be covered. Next, the framework summarises the
vulnerabilities found by the fuzzer in isolated functions and replaces the
respective functions by their summaries. Finally, we use targeted symbolic
execution to determine whether the vulnerabilities in isolated functions can
be triggered by their parent (calling) functions, with the process repeated
till a top-level function, such as main, is reached. This way, we can
determine to a high degree of confidence whether a vulnerability in an
isolated function may be a false-positive because the calling arguments are
sanitised in the parent functions.

##### Contribution

In this paper, we have made the following main contributions

  1. 1.

We describe a novel _compositional fuzzing_ technique for finding
vulnerabilities in programs using a combination of fuzzing and targeted
symbolic execution.

  2. 2.

The design of fuzzing drivers, described in section 4, can automatically
generate seed inputs for any previously-unknown program, even if the goal may
be to apply a fuzzer without compositional analysis.

  3. 3.

The design and implementation of the framework can effectively make use of
parallel cores, making it more _scalable and efficient_ to find
vulnerabilities in large-scale programs, than state-of-the-art fuzzers and
symbolic execution engines.

  4. 4.

Our evaluation of various open-source programs demonstrates that Wildfire can
find more vulnerabilities than symbolic execution and fuzzing, through higher
coverage in less time. Secondly, using three case studies, we show that
compositional fuzzing can reproduce almost all exploitable vulnerabilities in
open-source libraries and find new ones.

  5. 5.

The accompanying tool, _Wildfire_ 111Wildfire or, more precisely, Macke-with-
Wildfire-mode can be downloaded for free at https://github.com/tum-i22/macke,
implements the techniques described in this paper for C-programs, and is the
first of its kind in hybrid (involving fuzzing and symbolic execution)
compositional analysis tools. We have released Wildfire as an open-source
tool.

We start this paper by briefly introducing the background to our methodology
in section 2. Then, using a real-world example of a program, we motivate the
problem-statement in section 3. Our methodology is, then, described in section
4 followed by some implementation details in section 5. In section 6, we
evaluate Wildfire based on three research questions and list some limitations
in section 7. We list some related work to our research of symbolic execution,
fuzzing and compositional analysis, in section 8. Finally, in section 9, we
conclude the paper.

##  2 Background

Before describing our compositional analysis approach we, first, describe the
essential background of the underlying techniques of our methodology – fuzzing
and targeted symbolic execution.

###  2.1 Fuzzing

Fuzzing is an automated testing technique [49, 52] that makes use of
mutations222In this paper, we only refer to the mutation-based fuzzing
techniques, such as [57] and [8] as _fuzzers_ , and not include in this
terminology generation-based fuzzers such as [19], [23] and [25]. This
distinction will be clarified further in section 8 of _seed inputs_ to execute
the program under test and observe the return values and the external state of
the system. It is known as a blackbox technique because it does not rely on
information about the internal structure of the program but employs mutation
strategies that change individual or groups of bits in the seed inputs to
discover new paths in the program. The advantage fuzzing has over whitebox
analysis techniques is that, due to the fast mutation strategies that do not
depend on solving path-constraints, fuzzing can generate quickly invalid data
to trigger vulnerabilities in programs, thereby causing unwanted behaviour,
such as program crash. As a result, fuzzers can find many real vulnerabilities
[32, 50, 8] in programs that may be missed by other means of analysis.

###  2.2 Targeted Symbolic Execution

Symbolic execution [26] is a _whitebox_ automated testing technique that
collects _path-constraints_ along a program path from an entry point (e.g.
main function) to an exit point (e.g. return statement) and solves these
constraints using a constraint solver (e.g. SMT solver) to generate concrete
test-cases that execute the respective path. Most symbolic execution engines,
such as KLEE [12] and Mayhem [13], employ a path-exploration strategy that
prioritises unseen paths in the program. However, in many cases, inputs need
to be generated that will trigger specific functionality or known areas of
interest in a program, such as payload processing [23] or patches [31] that
may potentially break existing functionality. In these cases, the symbolic
execution engine needs to prioritise those paths that lead to the target of
interest instead of new paths only. Various techniques [29, 34, 54] have been
suggested in the past for effectively focussing symbolic execution towards
interesting areas of code. In addition to finding inputs for reaching targets
of interest, targeted symbolic execution also helps in reducing the path-
explosion problem, that is one of the main bottlenecks for classical symbolic
execution techniques.

##  3 Motivation

Having described the background of fuzzing and symbolic execution we will now
motivate our problem statement by referring to a vulnerability in a commonly
used UNIX tool, _Bzip2_ 333www.bzip2.org. Bzip2 is a UNIX tool for compressing
and decompressing files using a block-sorting compression algorithm,
accompanied by an API (_Libbzip2_) that developers may use in their programs.
The existence of such an API indicates a need for extensive testing of the
library, because there may be many potential entry points to the library, not
only the main function, resulting in a large attack surface.

Listing 1: Code of the function BZ2_hbCreateDecodeTables

⬇

1void BZ2_hbCreateDecodeTables (Int32 *limit,

2 Int32 *base, Int32 *perm, UChar *length,

3 Int32 minLen, Int32 maxLen, Int32 alphaSize)

4{

5 Int32 pp, i, j, vec;

6

7 pp = 0;

8 for (i = minLen; i <= maxLen; i++)

9 for (j = 0; j < alphaSize; j++)

10 /* potential buffer-overflow here */

11 if (length[j] == i) { perm[pp] = j; pp++; };

12

13 /* …

14 * some more processing omitted here */

15}

Figure 1: Pruned call graph of _Bzip2-1.0.6_. A possible path from main to a
vulnerable function, BZ2_hbCreateDecodeTables, is shown here

LABEL:lst:function-code shows a condensed version of the code of
Bz2_hbCreateDecodeTables function of Bzip2, that has a potential vulnerability
in line $11$. Basically, if the value of parameter, alphaSize, is bigger than
the size of the buffer, length, an attacker can cause a buffer-overflow on
line $11$ (j $\geq$ sizeof(length)) resulting in a program crash, i.e. denial-
of-service. One possible sequence of function calls that can lead to
BZ2_hbCreateDecodeTables is shown in figure 1. One would expect there to be a
check on the alphaSize variable (whether it is less than the size of length)
in at least one of the functions between main and BZ2_hbCreateDecodeTables.
However, upon inspecting the code of all these functions, we discovered that
such a check simply does not exist, i.e. the vulnerability in line $11$ can be
exploited from main444This vulnerability has already been reported to, and
acknowledged by, _secteam_ at FreeBSD project and the author of Bzip2. We are
currently awaiting analysis for a CVE.. One would hope that popular test-case
generation methods of fuzzing or symbolic execution would generate at least
one test-case to exploit it.

We ran KLEE [12] (with default path-search strategy) and AFL [57] (with 7
unique compressed files, as seed input) on Bzip2 for _10 hours_ , each. To
make the path exploration more focused for discovering our target function of
BZ2_hbCreateDecodeTables, we supplied the “-d” flag, which forces
decompression (calling the uncompress function) without necessarily performing
expensive initialization.

We found that neither KLEE nor AFL was able to spot the vulnerability in
BZ2_hbCreateDecodeTables function. While AFL covered all the functions from
main to BZ2_hbCreateDecodeTables, KLEE covers up to the function
BZ2_decompress. However, even though the vulnerable instruction was covered by
AFL in 10 hours, none of the two tools were able to trigger the vulnerability
itself, i.e. cause a program crash resulting due to buffer-overflow.

The above demonstrates the limitation of fuzzing and symbolic execution tools
in achieving reasonable path coverage in programs that take as input files or
data-structures encoded in a particular format, such as block-sorted files.
Because of potentially complex branching-conditions in the
BZ2_hbCreateDecodeTables function, AFL cannot mutate our seed inputs to
generate the correct file headers to exploit the vulnerability in this
function. Symbolic execution, on the other hand, also had to deal with path-
explosion in the BZ2_decompress function, and could never cross them to reach
BZ2_hbCreateDecodeTables. In this paper, we describe a method to force
coverage of almost _all_ functions in programs like Bzip2, while also being
able to determine whether potential vulnerabilities, such as the one in
BZ2_hbCreateDecodeTables, can be exploited.

##  4 Compositional Fuzzing – Methodology

We will now describe the design of our compositional fuzzing framework,
Wildfire, and its components.

###  4.1 Overview

Figure 2: Technical design of Wildfire

The technical design of our framework, Wildfire, is shown in figure 2. In this
figure, the steps of our framework and their inputs and outputs are shown in
white boxes, which we will discuss first. The specific tools and
implementation details to assist in various tasks are shown in grey/black
boxes and boxed-arrows that we will discuss in section 5.

The multi-threaded workflow of Wildfire, depicted in figure 3, consists of the
following steps, in order:

Figure 3: Workflow of Wildfire

  1. 1.

_Instrumentation and compilation_ of the source-code to LLVM intermediate
representation.

  2. 2.

_Generating fuzzing drivers_ to populate seed-inputs for isolated functions
and to extract function arguments from the inputs generated by the fuzzer.

  3. 3.

_Generating test-cases with fuzzing_ of the drivers generated in the previous
step, for isolated functions.

  4. 4.

_Generating crash reports_ by replaying the test-cases generated by a fuzzer
on an instrumented version of the program and reporting vulnerabilities.

  5. 5.

_Summarizing functions_ and replacing the isolated functions with exploit
test-cases, thereby condensing functions to only the paths leading to
potential vulnerabilities.

  6. 6.

_Determining feasibility of discovered vulnerabilities_ using stack-trace
matching and targeted symbolic execution to recursively generate, until an
entry-point is reached, concrete arguments to trigger the vulnerabilities.

We now describe all but the first steps in more detail below. The first step
is a trivial compilation procedure for LLVM. However, the description of
compiled objects, as shown in figure 2, will be presented in section 5.

###  4.2 Generating Fuzzing Drivers

To fuzz isolated functions in a program, Wildfire needs to generate fuzzing
drivers that act as wrappers around these functions, to  1. given the
parameter list, generate seed-inputs (known, from now on, as _seed-arguments_)
for the function, and  2. correctly assign the inputs generated by the fuzzer
to the function arguments.  We will now describe the design of driver
generation w.r.t. both requirements listed above.

####  4.2.1 Seed-argument Generation

Various possibilities, such as thresholded symbolic execution [38, 36] and
taint analysis [19, 55] have been proposed to generate seed-inputs for
fuzzing. However, while they may be useful for programs containing many
parsing functions, the overhead of symbolic execution is too high for our
approach where we directly fuzz isolated functions. We prefer to generate
seed-arguments statically, i.e. without executing the function first. We
propose two methods to generate seed-arguments for isolated functions. In the
first method, Wildfire generates two byte-streams – an _empty_ stream and a
stream consisting of random characters from the English alphabet, $[a-z]$.
Providing a random character is important because we cannot fuzz a target if
_all_ the seed-inputs lead to a program crash or hang (due to the limitation
imposed by our fuzzer, as discussed in section 5). For a parameter of pointer
type, a function is more likely to crash due to buffer-overflow with an empty
byte-stream than with a non-empty one. In the second method for generating
seed-arguments, Wildfire generates a byte-stream with as many _delimiter_
characters in the seed-argument byte-stream as there are parameters for the
function. As we will see in section 4.2.2, the delimiter character determines
the start and end within a byte-stream between which an argument must be
extracted.

####  4.2.2 Argument Extraction

Figure 4: How function arguments are extracted from a byte-stream.

The input provided by the fuzzer, including seed-arguments, is a byte-stream.
We need to extract bytes from this byte-stream (and cast, if necessary) and
assign to function arguments. Two example scenarios for argument extraction
from a byte-stream are shown in figure 4. Our method, first and foremost,
distinguishes function parameters as one of two types - _non-pointer_ and
_pointer_ data-type. We will ignore any functions with parameters with double-
or more pointers. This is a limitation in our framework, and we will discuss
this further in section 7.

The first scenario depicted in figure 4 is that of a function foo that accepts
two non-pointer type (integer) arguments. In algorithm 1, we show the
algorithm for extracting non-pointer type arguments, such as int or char. The
ExtractFixedSizedArgument function simply copies typeSize number of bytes
(line 4 in algorithm 1) from the byte-stream to the argument and casts it to
the required type. If there are not at-least typeSize number of bytes left in
the stream to consume, the stream is padded with null character bytes, as
shown in lines 8 and 9.

Algorithm 1 Algorithm for extracting _non-pointer_ arguments

1:procedure ExtractFixedSizedArgument(int typeSize, char[] remData, int
remSize)

2: $type$ [] $t$

3: if $typeSize\leq remSize$ then

4: $t\leftarrow type(remData[:typeSize])$

5: $remData\leftarrow remData[typeSize:]$

6: $remSize\leftarrow remSize-typeSize$

7: else

8: $memset(t,^{\prime}\setminus 0^{\prime},typeSize)$

9: $t[0:remSize]\leftarrow remData$

10: $remData\leftarrow$ [ ]

11: $remSize\leftarrow 0$

12: end if

13: return $type(t),remData,remSize$

14:end procedure

Algorithm 2 Algorithm for extracting _pointer_ arguments

1:procedure ExtractDynamicSizedArgument(int typeSize, char[] remData, int
remSize)

2: $type$ [] $t$, $int$ $bufSize$, $int$ $givenSize$

3: $givenSize\leftarrow LookForDelimiter(remData,remSize)$

4: $bufSize\leftarrow RoundDown(givenSize,typeSize)$

5: $t\leftarrow remData[:bufSize]$

6: if $(bufSize\leq remSize)$ then

7: $remSize\leftarrow remSize-givenSize$

8: $remData\leftarrow remData[givenSize:]$

9: else

10: $remData\leftarrow[]$

11: $remSize\leftarrow 0$

12: end if

13: return $t,remData,remSize$

14:end procedure

The next scenario depicted in figure 4 is that of a function bar that accepts
one pointer type (integer pointer) and one non-pointer type argument. For
parameters of pointer type, our approach is based on a special _delimiter_
character (assumed to be “//” in figure 4) in the byte-stream that splits it
for assigning to dynamically-sized parameter types. As shown in algorithm 2,
for each pointer type argument, ExtractDynamicSizedArgument copies the input
byte-stream to t (line 5) till the first delimiter character is encountered,
or the end of byte-stream has been reached. The helper function,
LookForDelimiter (line 3) returns the location of the first delimiter
character in the leftover byte-stream, or the end of the stream, whichever
comes first. RoundDown rounds givenSize down to a multiple of typeSize.

For the motivating example in section 3, this step will generate drivers for
fuzzing the functions main, uncompress, uncompressStream, BZ2_bzRead,
BZ2_bzDecompress, BZ2_decompress, BZ2_hbCreateDecodeTables and all other
functions in the Bzip2 program.

###  4.3 Generating Test-cases using Parallel Fuzzing

After generating fuzzing drivers, the next step in our framework is to apply
the fuzzer to the isolated functions with the generated seed-arguments. The
inputs to fuzzing are the generated drivers (implying, directly, the function)
which, as described in section 4.2, can be directly executed by the fuzzer.
This step can be run in parallel for all isolated functions because the
calling contexts of the isolated functions are ignored for now.

For all isolated functions, the output of this step is a list, $T_{f}$, of all
test-cases generated by the fuzzer for function, $f$.

$\displaystyle T_{f}=\\{t_{1},t_{2},\dots t_{n}\\},$ (1)

where $n$ is the number of unique test-cases generated by the fuzzer. If the
function $f$ accepts $m$ arguments, then,

$\displaystyle t_{i}=\langle I_{i_{1}},I_{i_{2}},\dots I_{i_{m}}\rangle,$ (2)

where $I_{i_{k}}$ is the $k^{th}$ argument.

For the motivating example in section 3, this step applies the fuzzer to the
function BZ2_hbCreateDecodeTables and saves the list of arguments, limit,
base, perm, length, minLen, maxLen, alphaSize (LABEL:lst:function-code),
generated by the fuzzer. An instance of test-case generated for
BZ2_hbCreateDecodeTables is shown in figure 5.

Figure 5: Example of a test-case (byte-stream) generated by the fuzzer for
BZ2_hbCreateDecodeTables.

In this example, the delimiter, “//” splits the first part of the generated
test-case into the pointers limit, base, perm and length. The later part of
the test-case is three integers minLen, maxLen and alphaSize.

###  4.4 Generating Crash Reports using Test-cases Replay

Fuzzing of isolated functions is carried out on a _lightweight_ compiled
object, without heavy instrumentation. Therefore, to obtain crash-reports that
include the function’s arguments and the stack-trace of crashing executions,
we must obtain details of all crashing (due to discovered vulnerabilities)
executions to be passed to the next steps. To do this, the first step is to
minimize the set of all generated test-cases, using _afl-cmin_ [1] and _afl-
tmin_ [3]. These two programs reduce the size of an input corpus by  1.
removing inputs that execute redundant paths in the program, and  2. removing
starting and trailing _null bytes_ from an input byte-stream while keeping the
executed path unchanged.

Then, we pass the minimised set of test-cases to an instrumented version of
the compiled object that gracefully handles crashing executions due to buffer-
overflows, illegal pointer operations or null-pointer dereferencing. The input
to this step, as shown in figure 2, are the test-cases generated by the fuzzer
in section 4.3. The first output of this step is the list, $T^{\prime}_{f}$,
of all test-cases (arguments) that result in a program crash. The second
output of this step is a set of stack-traces for crashes reported in the
isolated functions. A stack-trace, $S_{f_{0}}$, of a crashing execution of the
function, $f_{0}$, with arguments, $t_{i}$ (equation 1), is an ordered set

$\displaystyle S_{f_{0}}(t_{i})=\langle L(f_{0}),L(f_{1}),L(f_{2})\dots
L(f_{n})\rangle,$ (3)

where $f_{i}$ calls $f_{i+1}$. Here, $L$ returns the vulnerable instruction
(line number) and name of the function.

We call all buffer-overflows, null-pointer dereferences and other index-out-
of-bounds memory operations reported in the crashing function as
_vulnerabilities_ and an isolated function that contains at least one
vulnerability as a _vulnerable function_.

For the motivating example in section 3, this step would generate the stack-
trace for a crash found in BZ2_hbCreateDecodeTables as shown in figure 6.

Figure 6: Stack-trace generated by ASAN for a crash due to a vulnerability
discovered in BZ2_hbCreateDecodeTables.

We see the top element in the stack-trace is the location of the discovered
vulnerability (line number and function name). The next two lines in the stack
are the location of the artificial entry-points inserted by our framework to
generate a test-driver for BZ2_hbCreateDecodeTables.

###  4.5 Summarizing Vulnerable Functions

After generating crash reports for vulnerable functions, Wildfire replaces the
isolated functions with a summary of the crash reports, to allow targeted
symbolic execution for some of them. The rationale behind this step is to
tackle the path-explosion problem in symbolic execution. To assist the
symbolic execution engine in not getting stuck due to path-explosion, we
replace the set of paths in a vulnerable function by just the set of value-
assignments for its arguments that will trigger the vulnerabilities.

Let, for a vulnerable function $f_{0}$, the parameter list be $P$.

$\displaystyle P=\langle p_{1},p_{2},\dots p_{m}\rangle,$ (4)

where $p_{i}$ is the $i^{th}$ formal parameter for $f_{0}$. Then, the summary,
$f_{summary}$, generated for the $f_{0}$ is as shown in algorithm 3.

Algorithm 3 Summary of a vulnerable function, $f$

1:function $f_{summary}$(P)

2: assert$(P\neq t_{1})$

3: assert$(P\neq t_{2})$

4: $\vdots$

5: assert$(P\neq t_{n})$

6: return f$(P)$

7:end function

In algorithm 3, $t_{i}$ is as described by equation 2. Intuitively, the
function summaries simply compare the formal parameters with actual argument
values that were found to trigger a vulnerability. For pointer data-types,
this entails comparing the exact content of the allocated memory using memcmp.
We assert a _negation_ of equality because, then, Wildfire reports an
assertion error (and stops further processing) when there is a match found for
$P$ that is equal to $t_{i}$. Such an assertion error implies that the
vulnerability in $f$ can, indeed, be triggered from a calling function of $f$.
If there is no assertion-error (calling function cannot generate crashing
inputs), we proceed with the processing by calling the original function $f$,
as intended, to ensure that we include its side effects on the function and
its variables. Please note that, unlike previous work, such as [40, 30], where
formal parameters are compared to the input pre-conditions (in the form of
constraint systems), our technique only matches the concrete values of the
arguments, because we are limited by the fuzzer, which only generates concrete
inputs and not general path-constraints.

For the motivating example in section 3, let us consider again the vulnerable
function BZ2_hbCreateDecodeTables.

Figure 7: CFG of the original BZ2_hbCreateDecodeTables (left) and the
transformed CFG of the summarized $BZ2\\_hbCreateDecodeTables_{summarized}$.

The control-flow graph (CFG) of this function (extraced from the LLVM bitcode
using Opt [6]) is shown on the left-hand side of figure 7. We can see from the
original CFG that symbolic execution will encounter path-explosion in this
function due to the many input-dependant loops in original function. On the
right-hand side of figure 7, we see the summarized version of the same
function with no loops, because we have replaced the original body with
assertion statements described above. In this way, symbolic execution is more
likely to generate test-cases that trigger the discovered vulnerability in
BZ2_hbCreateDecodeTables.

###  4.6 Determining Feasibility of Reported Vulnerabilities

After finding and reporting potential vulnerabilities in isolated functions,
any compositional analysis framework needs to determine whether these
vulnerabilities can be exploited in a real usage of the program, e.g. through
a program’s API. This determination of exploitation can be done pairwise for
functions, i.e. can a vulnerability in function $f$ be exploited from
functions that call $f$ and, if yes, can it exploited from the functions that
call the functions that call $f$, and so on till an interface function is
reached. Wildfire performs the above determination in two phases, which we
will now describe.

####  4.6.1 Phase 1: Stack-trace Matching

As explained in section 4.4, the crash reports generated by the instrumented
version of the program contain stack-traces of crashing executions of isolated
functions. Our framework, in this phase, determines that a vulnerability in
$f_{a}$ can be exploited by $f_{b}$ if there were at least two _matching_
stack-traces, $S_{f_{a}}$ and $S_{f_{b}}$. We call two stack-traces,
$S_{f_{a}}$ and $S_{f_{b}}$, matching [34] if $S_{f_{a}}\subset_{O}S_{f_{b}}$.
Here $\subset_{O}$ denotes an _ordered subset_ , meaning that the elements in
the smaller set occur in the same sequence as in the larger set. Intuitively,
this phase of feasibility determination checks if a crashing execution of a
function, $f_{b}$, is due to the same vulnerable instruction as another
crashing execution of function $f_{a}$ that will, potentially, be called by
$f_{b}$.

For the motivating example in section 3, we have shown an example of stack-
trace matching in figure 8.

Figure 8: The stack-trace of crashing execution of BZ2_decompress (bottom,
after removing intialization code) matches the stack-trace of crashing
execution of BZ2_hbCreateDecodeTables (top).

The top functions (above __user_main) in the call-stack of
BZ2_hbCreateDecodeTables is a subset of that of BZ2_decompress. We can see
from this example that the stack-trace of a crashing execution of the caller
function BZ2_decompress matches the stack-trace of the crashing execution of
the callee function BZ2_hbCreateDecodeTables.

####  4.6.2 Phase 2: Targeted Symbolic Execution

A pair of matching stack-traces, $S_{f_{a}}$ and $S_{f_{b}}$, in phase 1
implies that fuzzing was able to cover the path in $f_{b}$ that leads to the
vulnerable function, $f_{a}$, with arguments triggering the vulnerability.
However, if no such matching stack-trace can be found for $S_{f_{a}}$, it
might be because the fuzzer was not able to generate any test-cases to trigger
the said path, and not merely because such a path does not exist. In phase 2,
Wildfire tries to exploit the vulnerable functions from calling functions
using symbolic execution to target only those vulnerable functions for which
no matching stack-traces were found in phase 1.

Phase 2 of feasibility determination takes as input the function summaries,
$f_{summary}$, generated in section 4.5. After replacing the function bodies
with their summaries, we use targeted symbolic execution from parent functions
to find paths leading to a vulnerable function. Consider again a vulnerable
function $f_{a}$, for which phase 1 did not find any matching stack-trace. In
phase 2, all functions, $f_{b}$, that potentially call $f_{a}$ are
symbolically executed by our framework where the target is set as
$f_{a_{summary}}$, which is the summarized version of $f_{a}$. When a targeted
search strategy is applied, all those branches are ignored (based on distance
in the control-flow graph) that do not potentially lead to the target. In
contrast to the _explore-new-paths-first_ [12] strategy, which is commonly the
default in symbolic execution engines, a targeted symbolic execution is less
likely to get stuck due to path-explosion because it eliminates uninteresting
paths as soon as it can determine that they would never lead to the target.
Additionally, the function summary $f_{a_{summary}}$ also has fewer paths to
explore than the original function, $f_{a}$. In this phase, therefore, we
increase our chances of determining if a vulnerability found in $f_{a}$ can
also be exploited from functions, $f_{b}$, that potentially call $f_{a}$.

For the motivating example in section 3, we see in figure 9 the stack-trace of
crashing execution of BZ2_bzDecompress.

Figure 9: The stack-trace of crashing execution showing BZ2_bzDecompress
calling the summarized version of BZ2_decompress, when executed with targeted
symbolic execution.

In this example, BZ2_decompress was, first, summarized using the technique
described in section 4.5 and, then, the calling function BZ2_bzDecompress was
analyzed with targeted symbolic execution to determine the feasibility of the
discovered vulnerability. We see in figure 9 that the vulnerable function
BZ2_hbCreateDecodeTables is not in the stack-trace because, with function
summaries, we no longer need to verify the entire path from BZ2_bzDecompress
to BZ2_hbCreateDecodeTables to determine that the vulnerability can be
exploited.

Wildfire applies both, phase 1 and phase 2, recursively until the main
function or a library’s API functions are reached. The output of this stage is
a list of vulnerability reports, each containing the vulnerable instruction,
function and the chain of functions through which it is feasible to exploit
it.

##  5 Implementation

We have implemented Wildfire as an extension to Macke [34], which is our
existing compositional analysis tool for C programs. The original
implementation of Macke, described and released in 2016, utilized the source-
code of the analyzed program to perform several compositional analysis steps,
including targeted symbolic execution. However, in its current form, we have
introduced several enhancements, in addition to compositional fuzzing, that
make Macke more portable and precise, by utilizing a program’s LLVM bitcode
for _all_ compositional analysis steps. Below we describe some implementation
details for Wildfire and, wherever applicable, list differences from the
original Macke [34].

##### Different LLVM Versions

It was necessary for our framework to compile the program-under-test to two
target objects, LLVM 3.4 and 6.0 [27] bitcodes. This was because the choice of
our fuzzing and symbolic execution tools could only accept LLVM 6.0 and LLVM
3.4 bitcodes, respectively. Moreover, to insert dynamic instrumentation, we
could only use intermediate LLVM representations and not binaries.

##### AFL for Fuzzing

For fuzzing isolated functions, we use AFL [57], which is a state-of-the-art
fuzzing tool for binaries and LLVM. We make use of the _deferred
instrumentation_ mode in AFL [2] that lets us dynamically dictate to the
fuzzer that the driver selection (which functions to fuzz), should be skipped
and only the original function body must be fuzzed.

##### ASAN for Generating Crash Reports

Using Opt, we insert ASAN [46] instrumentation into LLVM 6.0 bitcode. The
test-cases generated by AFL are sent as inputs to this ASAN instrumented
version of the program to obtain crash reports caused by illegal memory-
related operations, such as buffer-overflows or use-after-free, as described
in section 4.4.

##### KLEE22 for Symbolic Execution

Our choice of symbolic execution tool for determining the feasibility of
vulnerabilities is KLEE22 [37]. KLEE22 is a custom fork of KLEE [12], which
implements targeted-search based on arbitrary function-calls in a program.

##  6 Evaluation

We will now describe the experiments, metrics, results and, finally, a
synthesis of our observations.

###  6.1 Comparison Baseline

We start the description of our experiments by listing the tools that we will
compare with Wildfire. There exist many competing frameworks and tools, such
as Driller [48], AFLGo [9], FairFuzz [28] and Angora [15] , that have proposed
many improvements over state-of-the-art mutation-based fuzzing. However, we
picked our baseline tools mainly based on whether a tool  1. was available as
an open-source tool,  2. had reasonably complex user-guide or documentation,
and could be used “out-of-the-box” for our analysed programs, and  3. promised
a higher coverage or higher rate of vulnerability-discovery for _general-
purpose UNIX-based_ programs, compared to other techniques.

With the above inclusion criteria in sight, we concretely divide the state-of-
the-art, and comparative, tools in the following three categories.

  1. 1.

Basic tools: The first set of tools that we will compare with are basic
symbolic execution and fuzzing tools. For symbolic execution, we will pick
_KLEE_ [12] and for fuzzing, we will pick _AFL_ [57]. Both of these tools are
considered state-of-the-art in the fundamental techniques used in this paper.

  2. 2.

Coverage-guided tools: Next, we include more sophisticated tools involving
symbolic execution and fuzzing, that improve upon these fundamental techniques
by actively monitoring structural coverage of the program-under-test. We will
pick _AFLFast_ [8] and _Munch_ [36] in this category. More details on these
tools can be found in section 8.

  3. 3.

Compositional tool: Finally, we include _Macke_ [34], which is the only other
compositional analysis tool, to the best of our knowledge, which is open-
source and available out-of-the-box for C-language programs. We must mention
here, for the sake of full disclosure, that Macke and Wildfire are based on
the same underlying technologies, as described in section 5. But they differ,
specifically, in how vulnerabilities are discovered in isolated components
(section 4.3), arguments are extracted from byte-streams (section 4.2.2),
test-cases are replayed (section 4.4) and functions are summarized in terms of
discovered vulnerabilities (section 4.5).

###  6.2 Research Questions

To evaluate Wildfire, we will try to answer the following research questions

  * RQ1

How does the in-depth coverage of analysed programs by Wildfire compare to
those of the basic and coverage-guided tools?

  * RQ2

Following from coverage, how does the vulnerability finding capability of
Wildfire compare to those of the basic, compositional and coverage-guided
tools?

  * RQ3

Can Wildfire be used to effectively test libraries without manual
intervention, such as writing drivers?

###  6.3 Experimental Setup

For answering the research questions, we selected _8 open-source C programs_
and _12 GNU Binutils_ (only Unix-specific ones), listed in table 1, for RQ1
and RQ2. In terms of LOC and functions, this set contains a wide range from
basic utilities to much larger programs.

Table 1: Open-source programs analyzed

Prog.# |  Program | LOC | Functions | Analysis time (minutes)
---|---|---|---|---
|  |  |  |  Wildfire and Macke [34] |  Other tools
1 |  bc 1.06 | 3.5k | 129 |  22.5 |  283.2
2 |  bzip2 1.0.6 | 3.3k | 108 |  36.4 |  383.3
3 |  diff 3.4 | 7.8k | 391 |  103.0 |  849.9
4 |  flex 2.6.0 | 6.5k | 260 |  58.0 |  716.6
5 |  grep 2.25 | 8.0k | 461 |  130.5 |  933.3
6 |  less 481 | 7.9k | 459 |  66.7 |  800.1
7 |  lz4 r131 | 4.7k | 205 |  68.6 |  999.9
8 |  sed 4.2.2 | 3.2k | 213 |  57.9 |  349.9
|  _Binutils 2.31.1_ |  |  |  |
9 |  addr2line | 49.0k | 1485 |  607.0 |  1440.2
10 |  ar | 50.2k | 1547 |  605.0 |  1584.0
11 |  as | 65.8k | 2088 |  603.2 |  1584.1
12 |  cxxfilt | 48.9k | 1484 |  274.3 |  1584.0
13 |  gprof | 51.2k | 1540 |  404.4 |  1439.9
14 |  ld | 64.3k | 1953 |  510.2 |  1440.3
15 |  nm | 49.5k | 1509 |  383.4 |  1440.3
16 |  objcopy | 56.2k | 1656 |  187.1 |  1584.1
17 |  objdump | 64.5k | 1876 |  234.2 |  1584.0
18 |  ranlib | 50.3k | 1547 |  394.0 |  1440.3
19 |  readelf | 17.5k | 249 |  42.9 |  514.8
20 |  size | 49.1k | 1491 |  380.5 |  1439.9
|  _Libraries_ |  |  |  |
21 |  Libtiff 4.0.9 | 82.7k | 639 |  368.0 |  –
22 |  Libpng 1.6.35 | 43.8k | 516 |  360.0 |  –
23 |  Libcurl 7.59.0 | 209.2k | 692 |  680.0 |  –

For answering RQ3, we selected three case studies (table 1) of open-source
libraries.

We repeated all experiments _five times_ 555Due to reasonably limited
resources and long experiment times ($\approx$ 13 hours per repetition per
benchmark, per tool) we could not perform more than 5 repetitions. on an Intel
Xeon CPU E5-1650 v2 with _12 cores_ , 3.50GHz per core, 126 GB of RAM, and
running 64-bit Ubuntu 16.04.4 LTS.

In each repetition, we allowed Wildfire to fuzz each isolated function for _60
seconds_ each (maximum) and we gave each run of targeted-search a total of _60
seconds_ to reach the vulnerable function and trigger the vulnerability. For
comparison, we ran Macke [34] for the same amount of time as Wildfire.
Generation of test-cases for functions could be carried out in parallel
(section 4.3) for isolated functions in Wildfire and Macke, i.e. all 12 cores
could be utilised at the same time. Therefore, for a fair comparison, we
allowed the other baseline tools, KLEE [12], AFL [57], AFLFast [8] and Munch
[36], to run for approximately 12 times the total time taken by Wildfire or 24
hours, whichever was smaller. We recognize that for many programs, especially
Binutils, the cap of 24 hours is significantly less than a supposedly fair 12
times of the time taken by Wildfire and Macke. We justify the choice of
limiting the experiment times for the baseline tools to 24 hours as follows

  1. 1.

However, 24 hours is a reasonably long time budget for most real-world
programs (and is also used by state-of-the-art fuzzing research papers, such
as [48], [8] and [28]), and is longer than the usual nightly build times.

  2. 2.

Having run (without repetition) KLEE, AFL, AFLFast and Munch on the “ _as_ ”
program for 12 times the time taken by Wildfire, i.e.  _7238.4 minutes_ , we
found that the coverage (line and function) and vulnerabilities discovered by
these tools did not increase. While the same verification w.r.t. coverage and
vulnerabilities would not have been feasible for all the benchmarked programs,
with or without repetition, we may use the anecdotal example of _as_ as an
indication that 24 hours might be a sufficiently high time budget for most
programs.

Times taken in each repetition of every benchmarked program are listed in
table 1.

###  6.4 Coverage and Vulnerabilities

For evaluating coverage, we compare Wildfire to the basic and coverage-guided
tools. For evaluating vulnerabilities, we compare Wildfire to basic, coverage-
guided and compositional tools.

Figure 10: Comparison of line coverage Figure 11: Comparison of function
coverage Figure 12: Comparison of line coverage grouped by call-graph depth

Figure 10 shows the average (over 5 repetitions) line-coverage (%) achieved by
Wildfire, KLEE, AFL, AFLFast and Munch in the given time-limits. Figure 11
shows the average (over 5 repetitions) function-coverage (%) achieved by the
same techniques. Figure 12 shows the average (over all functions and 5
repetitions) line-coverage at every depth of the call-graph of all programs,
e.g. the lines of code in the main function are counted at $x=0$ in figure 12,
and so on. Please note that at every call-graph depth, we only averaged over
those programs that contained at least one function at that depth.

Figures 10, 11 and 12 show that the in-depth line coverage and function
coverage for all programs is larger with Wildfire than plain symbolic
execution and fuzzing, as implemented in KLEE and AFL, respectively, as well
as advanced tools that improve upon these techniques based on coverage, viz.
AFLFast and Munch. We see from these results that the line coverage for _bc_
and _Binutils_ is not as high (22% and 16%, respectively) as other programs
with Wildfire. The reason for this discrepancy is that these programs,
especially Binutils, have a few very large functions in terms of lines of code
that could not be covered sufficiently by fuzzing. However, as is the case
with all the programs, the line coverage in these programs is also higher for
Wildfire than with the basic and coverage-guided tools. Wildfire even achieves
higher coverage at $depth=0$ due to the following reason – more lines in the
main function are covered when targeted symbolic execution is used for
determining feasibility of vulnerabilities, than when only fuzzing or symbolic
execution is applied without a set target. The reason that function coverage
was not 100% for Wildfire was, as explained in section 4.2.2, that Wildfire
does not fuzz functions that contain any parameter of double- or more pointer
type. In this study, we take no measures to handle this case and, instead,
rely on targeted symbolic execution in phase 2 (section 4.6) to generate test-
cases for those functions that could not be fuzzed by AFL.

Table 2: Vulnerability-related metrics for Wildfire and the compositional tool

Prog. | Vulnerabilities | $|chain|>1$ | $chain\prec P2$
---|---|---|---
| Wildfire | Macke | Wildfire | Macke | Wildfire | Macke
bc | 72 | 57 | 42 | 30 | 7 | 16
bzip2 | 96 | 71 | 33 | 22 | 0 | 0
diff | 219 | 256 | 205 | 166 | 32 | 7
flex | 124 | 106 | 46 | 40 | 3 | 12
grep | 319 | 261 | 186 | 132 | 24 | 7
less | 167 | 166 | 151 | 124 | 15 | 14
lz4 | 102 | 92 | 119 | 100 | 43 | 3
sed | 124 | 93 | 109 | 86 | 37 | 8
addr2line | 979 | 804 | 404 | 226 | 10 | 9
ar | 983 | 794 | 386 | 234 | 10 | 8
as | 1230 | 1051 | 586 | 355 | 24 | 10
cxxfilt | 895 | 811 | 294 | 234 | 4 | 6
gprof | 982 | 837 | 398 | 238 | 9 | 6
ld | 1218 | 1005 | 522 | 326 | 15 | 13
nm | 948 | 847 | 362 | 247 | 10 | 7
objcopy | 862 | 0 | 221 | 0 | 0 | 0
objdump | 1008 | 0 | 258 | 0 | 0 | 0
ranlib | 944 | 850 | 360 | 242 | 9 | 7
readelf | 159 | 106 | 62 | 50 | 11 | 0
size | 948 | 791 | 375 | 216 | 9 | 9
strings | 1106 | 0 | 550 | 0 | 10 | 0
strip | 872 | 0 | 221 | 0 | 0 | 0

An increased coverage can be easily explained because we directly fuzz
isolated functions. In fact, simply increasing line or function coverage would
be insufficient if the increased coverage also did not increase the
vulnerability discovery capability of a dynamic analysis method, such as
fuzzing. And the goal of our evaluation is precisely to show this – does
increased line coverage result in an increased likelihood of covering a
potentially vulnerable line in the program.

Let us now see how increased line coverage affects vulnerability discovery.
Table 2 lists the results related to vulnerability discovery for Wildfire and
the only other compositional analysis tool in our study, Macke [34]. For these
two tools, we have listed in this table the following three measures – The
column “Vulnerabilities” lists the total number of vulnerabilities found by
these tools, determined by a uniquely vulnerable instruction (equation 3). To
determine whether any calling function could exploit the vulnerabilities
discovered by Wildfire or Macke, we list the “$|chain|>1$” criteria, listed in
the next column, that counts only those vulnerabilities that can be, according
to feasibility analysis (section 4.6), exploited by _at least one_ calling
function. Some of these chains were reported by simple stack-trace matching,
as described in phase 1 of feasibility determination (section 4.6), while
others were reported from targeted symbolic execution towards summarised
functions in phase 2. The number of such chains whose ends (highest-level
vulnerable functions) were reported by phase 2, and not by simple stack-trace
matching, are listed in the next column in table 2 as “$chain\prec
P2$”666“$chain\prec P2$” should be read as “chains ending with a function
found by phase-2 of feasibility analysis.”.

We can see from table 2 that Wildfire was almost always (except _diff_) able
to find more vulnerabilities than Macke. Moreover, the number of chains
discovered by Wildfire with $|chain|>1$ was also more than with Macke. Lastly,
for most programs, Wildfire discovered as many, or more, chains of
vulnerabilities with $chain\prec P2$. From table 2, we can see that Wildfire
performs better than, or the same as, Macke on most metrics described for
compositional analysis tools.

(a) All chains

(b) $chain\prec P2$

Figure 13: Distribution of vulnerability-chains’ lengths across all programs.
72% of the vulnerabilities that could be exploited from main() required
targeted symbolic execution to be found

The total distribution of the lengths of chains of functions where a unique
vulnerable instruction may be exploited, as per Wildfire, is shown in figure
13(a). This distribution shows that Wildfire can generate chains of various
lengths and, in fact, finds that about half of all discovered vulnerabilities
can be exploited by at least one other function. In some cases, chains of 6 or
more functions in the call-graph are also found. For 72% of all chains ending
at the main function, targeted symbolic execution was necessary to trigger the
vulnerabilities. Additionally, while the average length of all chains reported
by Wildfire is $\approx 1.6$ (figure 13(a)), it is $\approx 2.6$ (figure
13(b)) for chains where $chain\prec P2$. The above demonstrates the usefulness
of combining targeted symbolic execution with isolated functions’ fuzzing for
discovering high-impact vulnerabilities.

However, some of the vulnerabilities discovered by Wildfire or Macke may never
be exploited because their calling functions might sanitise the inputs before
calling the vulnerable functions. Therefore, as a final comparison with state-
of-the-art tools, we present in table 3 the count of vulnerabilities that
could be triggered from the _main_ function of a program. Since this factor
can be measured for any baseline tool of our study, we have included basic
tools (KLEE and AFL), coverage-guided tools (AFLFast and Munch), and
compositional tool (Macke) for comparison.

Table 3: Vulnerability-related metrics for all baseline tools

Prog. |  main vulnerabilities
---|---
| Wildfire | KLEE [12] | AFL [57] | AFLFast [8] | Munch [36] | Macke [34]
bc | 3 | 0 | 1 | 1 | 0 | 5
bzip2 | 0 | 0 | 0 | 0 | 0 | 0
diff | 2 | 0 | 0 | 0 | 0 | 2
flex | 0 | 0 | 1 | 1 | 1 | 0
grep | 0 | 0 | 0 | 0 | 0 | 0
less | 1 | 1 | 0 | 0 | 0 | 1
lz4 | 1 | 1 | 0 | 0 | 1 | 2
sed | 1 | 0 | 0 | 0 | 0 | 1
addr2line | 1 | 0 | 0 | 0 | 0 | 1
ar | 0 | 0 | 0 | 0 | 0 | 0
as | 7 | 0 | 0 | 0 | 0 | 6
cxxfilt | 0 | 0 | 0 | 0 | 0 | 0
gprof | 0 | 0 | 0 | 0 | 0 | 0
ld | 3 | 3 | 1 | 1 | 2 | 3
nm | 2 | 1 | 0 | 0 | 1 | 2
objcopy | 0 | 0 | 0 | 0 | 0 | 0
objdump | 0 | 0 | 0 | 0 | 0 | 0
ranlib | 0 | 0 | 0 | 0 | 0 | 0
readelf | 0 | 0 | 0 | 0 | 0 | 0
size | 1 | 0 | 0 | 0 | 0 | 1
Total | 22 | 6 | 3 | 3 | 5 | 24

We can see from table 3 that for all but one (_Flex_ will be explained later)
programs, the number of such vulnerabilities found by Wildfire was higher than
or equal to other baseline tools, in almost 90% less time (considering
parallelism). However, for _bc_ and _lz4_ , Macke outperformed Wildfire and
found 2 and 1 more vulnerability from main function, respectively.

In terms of its effectiveness in finding vulnerabilities that can be exploited
from main function, we see that Macke (symbolically executing isolated
functions) was able to find _two more vulnerabilities_ in the analyzed
programs than Wildfire. At first glance, it may seem that Wildfire reports
more false-positives (comparing values from table 2 and table 3) than Macke.
However, in reality, there are two justifications for why the true-positives
listed in table 3 should not be the sole criterion for comparison –

  1. 1.

Many of the vulnerabilities found in isolated functions by Wildfire may not be
found to be feasible from main due to path-explosion in the higher-level
functions. An example of this is the vulnerable function
BZ2_hbCreateDecodeTables discussed in the motivating example (section 3). This
vulnerability was found by Wildfire in the given time limit, and the reported
chain of vulnerability contained functions BZ2_bzDecompress and
BZ2_decompress, but not main. However, as discussed earlier (section 3), this
vulnerability can indeed be exploited by a specially crafted file with
dishonest parameter for the length of the compressed file block. The above
demonstrates that, for a true comparison of the effectiveness between
compositional tools, we must consider all, total number of reported
vulnerabilities, chain of reported vulnerabilities and reported true-
positives.

  2. 2.

Functions may be reused in unforeseable ways in the future and, therefore,
vulnerabilities discovered in them need to be compositionally analyzed,
irrespective of whether they were found to be exploitable through main.

We will elaborate both the above points further in section 6.6.

Please also note that all the numbers in table 2 and table 3 are the _common_
results from the five repetitions of Wildfire, KLEE, AFL, AFLFast, Munch and
Macke, i.e. we only list those vulnerabilities and chains that were reported
by _all five runs_ of the respective method.

##### The Flex exception

We saw in table 3 that AFL, AFLFast and Munch discovered more main
vulnerabilities in _Flex_ than Wildfire. In the code of Flex, the majority of
the functionality is contained within a function that lie close to the main
function, viz. flex_main function. Due to this fact, Wildfire should have
given more time to this large function than other smaller functions, because
the baseline tools get much more overall time to analyze this single function
close to the entry point than Wildfire. We leave time-scaling based on the
size of isolated-functions as future work.

Thus, we have shown, using 20 benchmarks, that a compositional fuzzing
approach makes it more likely to discover vulnerabilities in a considerably
shorter time than basic and coverage-guided tools, by deliberately executing
functions in isolation, and performing a bottom-up feasibility analysis.

###  6.5 Real Vulnerabilities in the Wild

In section 6.4, we have shown how Wildfire outperforms state-of-the-art
techniques on programs that have a single user-interface, i.e.  _main_
function. We will now show that Wildfire can also find vulnerabilities in
open-source libraries that have many possible entry points, i.e. APIs, that
increase their attack surface. Unlike fuzzing and symbolic execution, Wildfire
can analyze these libraries _automatically_ , without the need for manually
writing API drivers.

To demonstrate that Wildfire can effectively be used to test libraries without
writing test-drivers, such as is the case with baseline tools, viz. AFL, KLEE,
AFLFast and Munch, we picked _three popular open-source libraries_ , listed
below.

  1. 1.

Libtiff 4.0.9 777http://www.simplesystems.org/libtiff/ – A library used by
application developers to process images of TIFF, and a few other, formats.

  2. 2.

Libpng 1.6.35 888https://libpng.sourceforge.io/ – A library used by
application developers to process PNG images.

  3. 3.

Libcurl 7.59.0 999https://curl.haxx.se/ – A library for transferring data
using various secure and non-secure transfer protocols.

Our goal with these case studies was to find out if we can reproduce the
vulnerabilities reported in the past for them and if we can find any new ones.

For finding vulnerabilities, we filtered the list of all reported
vulnerabilities (by Wildfire) to those where there was at least one API
function in the chain of vulnerability. Table 4 lists all previously known
vulnerable functions in the respective versions of Libtiff, Libpng and
Libcurl.

Table 4: Known Vulnerabilities in Libtiff 4.0.9, Libpng 1.6.35 and Libcurl
7.59.0

Function |  CVE | Found by Wildfire
---|---|---
TIFFSetupStrips |  CVE-2017-17095 | ✓
PackBitsEncode |  CVE-2017-17942 | ✓
TIFFPrintDirectory |  CVE-2017-18013 | ✓
TIFFSetDirectory |  CVE-2018-5784 | ✓
TIFFPrintDirectory |  CVE-2018-7456 | ✓
LZWDecodeCompat |  CVE-2018-8905 | ✓
TIFFWriteDirectorySec |  CVE-2018-10963 | ✓
png_set_text_2 |  CVE-2016-10087 | ✓
png_set_PLTE |  CVE-2015-8126 | ✓
png_get_PLTE |  CVE-2015-8126 | ✓
png_do_expand_palette |  CVE-2013-6954 | ✓
png_free_data |  CVE-2018-14048 | ✓
Curl_http_readwrite _headers |  CVE-2018-1000301 | ✓
Curl_smtp_escape_eob |  CVE-2018-0500 | ✓
Curl_auth_create_ntlm _type3_message |  CVE-2019-3822 | ✗
Curl_pp_readresp |  CVE-2018-1000300 | ✓

Table 5: New Vulnerabilities Discovered in Libtiff 4.0.9, Libpng 1.6.35 and
Libcurl 7.59.0

Vulnerable Function |  Affected API
---|---
TIFFFindField |  TIFFGetFieldDefaulted
unixErrorHandler |  TIFFFdOpen
TIFFRGBAImageOK |  TIFFReadRGBAImage
TIFFSwabArrayOfShort |  TIFFSwabArrayOfShort
TIFFSwabArrayOfLong |  TIFFSwabArrayOfShort
TIFFWriteBufferSetup |  TIFFWriteTile
png_set_filler |  png_set_add_alpha
png_warning |  png_set_compression_method
png_colorspace_set_chromaticities |  png_set_cHRM
png_error |  png_set_compression_buffer_size
png_set_keep_unknown_chunks |  png_image_skip_unused_chunks
png_icc_check_header |  png_set_iCCP
png_rtran_ok |  png_set_alpha_mode
png_get_y_pixels_per_meter |  png_get_y_pixels_per_inch
png_get_y_offset_microns |  png_get_y_offset_inches
curl_easy_cleanup |  curl_easy_cleanup
curl_easy_perform |  curl_easy_perform
curl_getdate |  curl_getdate
curl_mime_init |  curl_mime_init
curl_slist_append |  curl_slist_append
curl_slist_free_all |  curl_slist_free_all
curl_easy_escape |  curl_easy_escape
curl_easy_unescape |  curl_easy_unescape

We obtained this list from NVD101010https://nvd.nist.gov/ and then filtered
them by the name of the library and the corresponding latest version. The
second column of table 4 lists the known CVE identifier for the respective
vulnerabilities. The last column shows whether Wildfire could find the same
vulnerability in the given time-out. As we can see from table 4, all the known
vulnerabilities in Libtiff and Libpng, and all but one vulnerabilities in
Libcurl, could be found by Wildfire under the given time-limit.

We also found _23_ new vulnerabilities in these three libraries that could be
exploited through at-least one function in the respective libraries’ API.
Table 5 lists the previously unknown vulnerabilities (of type “buffer errors”)
in Libtiff, Libpng and Libcurl that can be exploited by an improper (but
valid) use of their APIs.

###  6.6 Synthesis of the Results

####  6.6.1 RQ1– Coverage

Several works in the past [34, 48, 23] have shown that the primary reason that
state-of-the-art test-case generation techniques are unable to find many
vulnerabilities is a lack of coverage in deeper parts of the code, often
guarded by complex checks for malformed inputs. We, therefore, hypothesised
that forcing higher coverage in programs would also lead to discovering
previously unknown vulnerabilities. Compared to dynamic analysis techniques of
symbolic execution and fuzzing, we showed in section 6.4 that Wildfire
achieves higher line- and function-coverage. The reason for higher in-depth
coverage was merely the under-constrained nature of the fuzzing stage, where
isolated functions were analyzed directly. Symbolic execution and fuzzing
tools could not cover as much of the source-code or functions because they had
to overcome complex _frontier nodes_ [38] to execute these functions.

RQ1 – Our results show that, for the selected benchmarks, Wildfire achieves
higher in-depth line coverage and function coverage than basic and coverage-
guided baseline tools.

####  6.6.2 RQ2– Vulnerabilities

Our second research question was whether, as a result of higher coverage,
Wildfire could also find more vulnerabilities in programs than the comparison
baseline. Our conjecture was based on several previous works [16, 21, 34] that
use symbolic execution at the level of isolated functions and found more
vulnerabilities and increased coverage. In section 6.4, we found that, in
fact, the number of vulnerabilities (including potential false-positives, as
we will discuss soon) reported by Wildfire is always higher than state-of-the-
art symbolic execution and fuzzing tools and, for most programs, is higher
than the state-of-the-art compositional tool. Additionally, the number of
vulnerabilities that could be exploited from the main function is also the
same or higher for basic and coverage-guided tools.

Importantly, a compositional fuzzing framework can also help reduce the
problems of _false-positives_ , as follows. In particular, not all reported
vulnerabilities that cannot be triggered from an interface, such as the main
function, are false-positives. We provide three reasons for this claim here.
1. If a vulnerability can be shown to be exploitable through multiple caller-
callee pairs ($|chain|>1$), then it could _potentially_ be _true-positive_
and, hence, should be fixed. Anecdotal evidence of this is our observation on
the motivating example of Bzip2 (section 3). The vulnerability in
BZ2_hbCreateDecodeTables was reported by Wildfire by, first, analyzing the
isolated functions (section 4.4) and, then, determining feasibility of the
vulnerabilities through compositional analysis (section 4.6). The reported
chain, $BZ2\\_bzDecompress\rightarrow BZ2\\_decompress\rightarrow
BZ2\\_hbCreateDecodeTables$, with $|chain|>1$, should indicate that the
vulnerability should be fixed, even if the framework could not reproduce the
feasible path from main function. Manually confirming all reported
vulnerabilities with $|chain|>1$ was not feasible in our work, but sorting
vulnerabilities by $|chain|$ should be the first step in bug-triage. A
combination with targeted symbolic execution allows Wildfire also to report
more chains ($chain\prec P2$ in table 2) than from simply fuzzing the isolated
functions and examining their stack-traces. Without targeted symbolic
execution, as discussed in section 6.4, we would not have been able to find
many critical vulnerabilities, some of which were reproducible through the
top-level interface.  2. There may be many other factors [18], such as the
degree of connectedness of a function [33] and the distance to an interface
such as main function [35], that affect if a vulnerability may be exploited,
even if an exploit from main could not be generated.  3. In practice,
functions tend to be reused in unforeseen contexts and, hence, it may be
advisable to fix vulnerabilities directly inside functions that may be reused.
RQ2 – Our results show that, for all but one selected benchmarks, Wildfire
finds more vulnerabilities than basic, coverage-guided and compositional
baseline tools. It also finds more, or the same number of, true-positives as
the basic and coverage-guided tools and the two less true-positives than the
compositional tool.

####  6.6.3 RQ3– Testing Libraries

Our final research question was whether Wildfire could help in effectively
testing libraries to find vulnerabilities, without the time-consuming process
of writing drivers. By applying our framework to three popular open-source
libraries, Libtiff, Libpng and Libcurl, we showed in section 6.5 that almost
all of the known vulnerabilities, could have been found by Wildfire. We were
also able to find new vulnerabilities and report them to their development
teams. This is a key contribution of our research because open-source
libraries with public APIs are often used as daemon or microservices on remote
servers accepting input through standard protocols, such as HTTP. If a
malicious user was to send malformed input to the API to trigger the
discovered vulnerabilities, they could cause a denial-of-service resulting in
a substantial monetary and functional loss. Our motivation was to show that a
compositional analysis framework, unlike non-compositional ones, such as AFL,
KLEE and AFLFast, is necessary to trigger vulnerabilities in libraries,
without writing specialized test-drivers. Wildfire, by reporting all chains of
potential vulnerabilities directly affecting the API functions, would discover
and help in mitigating these vulnerabilities at the earliest. For the
vulnerabilities that could not be confirmed to be feasible from the API, i.e.
potential false-positives, we argue for them in the same manner as earlier,
viz. with reports containing chains of vulnerable functions, it makes it
easier for developers and testers to triage the reported bugs.

RQ3 – Our results show that, for the selected open-source libraries, Wildfire
can effectively find vulnerabilities in them without writing specialised
drivers for automatically testing them.

##  7 Limitations

##### Pointer Analysis

Currently, support for a few kinds of pointers in Wildfire is insufficient.
Particularly, if a function parameter list contains at least one parameter of
double- or more pointers (such as array-of-arrays), then the function will not
be isolated and fuzzed. The same is true if there is at least one parameter of
_function-pointer_ type. In case of pointers to structures which may,
themselves, contain members of pointer data-types, Wildfire attempts to
allocate memory for them (using malloc) and extract values for them from the
function arguments, as described in section 4.2.2. However, if there are no
explicit checks on pointers inside structures, then a crash resulting from
their access will be, correctly, reported.

##### Global Variables

Another limitation of Wildfire is that it does not take into account, and
hence fuzz, the values of global variables that might affect the internal
states of isolated functions. However, as is also true for past works in
compositional analysis [16, 22, 34], when including all possible global
variables in the argument extraction procedure, the search space for possible
executions explodes intractably.

Due to the above reasons, and possibly more, our results may not generalise to
other kinds of C programs that may functionally or structurally differ from
our evaluation set. However, we have taken care to, firstly, not exclude any
programs by design in our study and, secondly, include programs varying from
medium- to large-scale, in terms of the number of high-level source-code lines
and functions. We applied these selection criteria to, both, open-source
programs with a main entry point and open-source libraries that are popularly
used by many third-party applications.

##### Programming Language

The final limitation that needs to be noted is related to the programming
language that our analysis method is restricted to, i.e.  _C_. Even though the
underlying fuzzing and targeted symbolic execution engines can function at the
intermediate level of LLVM, we are limited by the symbolic model for several
system and third-party libraries for programming languages other than C. Due
to this reason, Wildfire can only be used for programs written in C language.
However, the fundamental higher-level ideas described in this paper may be
implemented for other programming languages too.

##  8 Related Work

###  8.1 Fuzzing tools and advancements

Fuzzing [49] is a blackbox or greybox strategy, often guided by lightweight
instrumentation [57], to generate test-cases for a program. Libfuzzer [47] is
a fuzzing tool for libraries and arbitrary functions using an _in-process_ and
coverage-guided fuzzing algorithm based on AFL [57]. However, due to the in-
process nature of Libfuzzer where the fuzzing logic is executed for each
iteration in the same process as the target application, Libfuzzer cannot
recover automatically after finding a crashing input. Due to the above,
Libfuzzer was not a suitable choice of fuzzing tool in Wildfire, because it
would be too expensive to restart the fuzzer process for every crashing
execution in isolated functions. Several state-of-the-art fuzzers such as
AFLFast [8], Honggfuzz [51], Peach [5], and Vuzzer [41] have been developed in
the past decade alone that have specialized optimizations in terms of directed
path search [9], guided seed selection [42] and controlled frequency of path
selection [14, 56]. Many of these advanced fuzzers have also found several
previously unknown vulnerabilities [8].

Please note that we do not include _generative fuzzing_ techniques under the
terminology of fuzzing because, unlike mutation-based methods, most generative
techniques employ methods such as symbolic execution [23], existing input
grammars [19] and parsers for exising models [25]. Due to their reliance on
underlying solvers, such as SMT, generative fuzzing techniques also suffer
from the constraint solving problems associated with symbolic execution. For
demonstrating the effectiveness of the techniques in our paper, therefore, we
have differentiated between solver based techniques (symbolic execution) and
mutation-based techniques (sometimes guided by coverage).

###  8.2 Compositional Analysis

To handle the issues of path-explosion and constraint-solving in symbolic
execution [11], several approaches have been proposed of which compositional
analysis [34, 16, 44, 22, 39] is one. Breaking down a larger program into
smaller modules has shown to improve [21, 44, 30, 54] the structural coverage
of symbolic execution engines, as expected. With the compositional analysis of
discovered vulnerabilities (using targeted symbolic execution [29]), some
techniques [17, 16, 34] can also report the extent to which the calling
functions are affected.

##### Comparison with Macke

The only open-source compositional analysis tool available for comparison was
Macke [34]. Since it forms the basis of Wildfire too, below we have listed the
difference in our contribution over Macke.

  1. 1.

The original implementation of Macke did not include any _support for fuzzing
isolated function_ and, therefore, this is an entirely novel addition.

  2. 2.

The original implementation of Macke required re-compilation for every
isolated function before it could be analyzed with symbolic execution. We
enhanced it in the current version (including Wildfire mode) by allowing to
_dynamically insert entry-points in the compiled LLVM bitcode_ , for every
isolated function. This enhancement saves compilation time and disk space by
not storing multiple compiled objects for the same program.

  3. 3.

Support for _generating crash reports from ASAN_ is a novel contribution
because the original Macke did not support fuzzing or gracefully handling
crashing test-cases generated by AFL. Additionally, we also modified Macke to
convert ASAN crash reports to a compatible format that could be read and
analyzed by KLEE22. This modification is also useful because Macke can, in
future, be modified to include _any mode of dynamic analysis_ , such that if
the test-cases can be used by ASAN for generating crash reports, the tool can
perform compositional analysis.

  4. 4.

KLEE22 contains a complete rehaul of _the targeted symbolic execution
technique_ described in the original Macke implementation [34]. In its earlier
version, KLEE22 used a distance metric based only on the lines of source-code
in a function between its entry-point and the call instruction to the
vulnerable function. However, in the current version (including Wildfire
mode), KLEE22 calculates distances based on instructions in the _entire_ LLVM
bitcode of the program, inline functions, and return addresses of called
functions on the stack. Due to these enhancements, the targeted symbolic
execution in current Macke version is more precise than the earlier version.

To the best of our knowledge, there has been no past work to explore fuzzing,
instead of symbolic execution or static analysis [20], as a possible strategy
for finding vulnerabilities in isolated functions. In addition to extensive
evaluation of compositional analysis, such a fuzzing-based compositional
analysis technique is our main contribution.

###  8.3 Hybrid Fuzzing and Symbolic Execution

Driller [48] is a hybrid tool that employs selective symbolic execution to
help the fuzzer overcome saturation w.r.t. new paths discovered. It was able
to discover many previously unknown vulnerabilities and performed especially
well on the Darpa Cyber Grand Challenge dataset. Taintscope [55] and
BuzzFuzz[19] employed dynamic taint tracking, to focus fuzzing on interesting
byte-regions of input that may affect suspicious regions of the code.
Böttinger and Eckert [10] presented DeepFuzz, a tool that finds
vulnerabilities in binaries by using symbolic execution to estimate the
probability of exploring new paths with a seed mutation during fuzzing. Munch
[36] is a hybrid tool introduced to increase function coverage by employing
two combinations of symbolic execution and fuzzing – fuzzing with seed-inputs
generated by symbolic execution, and targeted symbolic execution when fuzzing
saturates. Finally, Pak [38] presented a hybrid method to feed the fuzzers
with inputs generated by symbolic execution by solving the path-constraints
after a new branch has been visited. As mentioned before, none of these hybrid
works analyzes isolated components, but only applied at the single entry-point
of programs. An alternative to our hybrid and compositional approach would
have been to use state-of-the-art methods such as symbolic execution to find
vulnerabilities in isolated components, just like Macke [34], and confirm the
feasibility of vulnerabilities by biasing a mutation-based fuzzer, as done in
AFLGo [9], towards generating inputs to execute the target vulnerabilities.
This is an orthogonal approach to our technique and, therefore, will not be
discussed in this paper.

There are, to the best of our knowledge, no previous solutions based on
compositional analysis to overcome the known difficulties of fuzzing
(insufficient path-coverage) and symbolic execution (path-explosion and
constraint solving). Wildfire plugs this gap in hybrid research.

##  9 Conclusion

In this paper, we presented Wildfire, an open-source compositional analysis
framework based on a novel combination of fuzzing and symbolic execution.
Wildfire can find more real, and potentially exploitable, vulnerabilities in
open-source programs and libraries than state-of-the-art fuzzing, symbolic
execution, in only $10\%$ as much time in most cases, accounting for
parallelisation of analysis. Compared to the only other compositional analysis
tool at our disposal, Wildfire was able to find more vulnerabilities and
almost the same number of true-positives in the same amount of time, also
taking into account parallelisation. Wildfire deals with false-positives by
precisely reporting the chains of functions through which a vulnerability can
be exploited. This can be, as shown by our case studies, particularly useful
and practical for testing libraries where there may be multiple entry-points
to a program. In the future, we would like to implement summarisation of
vulnerabilities by path-constraints rather than concrete argument values. We
also wish to extend Wildfire by combining with symbolic execution to
adaptively switch between the two techniques when one saturates in isolated
functions. By using heuristics from existing bug reports, we would, in the
future, include an automated bug-triage plugin for vulnerabilities discovered
by Wildfire.

## References

  * afl [a] “Afl-cmin,” http://www.tin.org/bin/man.cgi?section=1&topic=afl-cmin.
  * afl [c] “LLVM-based instrumentation for afl-fuzz,” https://github.com/mcarpenter/afl/tree/master/llvm_mode.
  * afl [b] “Afl-tmin,” http://www.tin.org/bin/man.cgi?section=1&topic=afl-tmin.
  * ary [2012] “Fuzzing for security,” https://blog.chromium.org/2012/04/fuzzing-for-security.html, 2012.
  * [5] “Peach fuzzing platform,” http://peachfuzzer.com.
  * [6] “LLVM Opt,” http://llvm.org/docs/CommandGuide/opt.html, accessed: 2017-09-09.
  * Anand et al. [2008] S. Anand, P. Godefroid, and N. Tillmann, “Demand-driven compositional symbolic execution,” in _TACAS_ , 2008.
  * Böhme et al. [2017a] M. Böhme, V.-T. Pham, and A. Roychoudhury, “Coverage-based Greybox Fuzzing as Markov Chain,” _IEEE Transactions on Software Engineering_ , 2017\.
  * Böhme et al. [2017b] M. Böhme, V.-T. Pham, M.-D. Nguyen, and A. Roychoudhury, “Directed greybox fuzzing,” in _ACM SIGSAC Conference on Computer and Communications Security, Proceedings of the_ , 2017.
  * Böttinger and Eckert [2016] K. Böttinger and C. Eckert, “DeepFuzz: Triggering Vulnerabilities Deeply Hidden in Binaries,” in _Detection of Intrusions and Malware, and Vulnerability Assessment_ , 2016.
  * Cadar and Sen [2013] C. Cadar and K. Sen, “Symbolic execution for software testing: three decades later,” _ACM Communications_ , 2013.
  * Cadar et al. [2008] C. Cadar, D. Dunbar, and D. Engler, “KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs.” in _OSDI_ , 2008.
  * Cha et al. [2012] S. Cha, T. Avgerinos, A. Rebert, and D. Brumley, “Unleashing Mayhem on Binary Code,” in _Security and Privacy, IEEE Symposium on_ , 2012.
  * Cha et al. [2015] S. Cha, M. Woo, and D. Brumley, “Program-adaptive mutational fuzzing,” in _Security and Privacy (S &P), IEEE Symposium on_, 2015.
  * Chen and Chen [2018] P. Chen and H. Chen, “Angora: Efficient fuzzing by principled search,” in _2018 IEEE Symposium on Security and Privacy (SP)_ , 2018.
  * Christakis and Godefroid [2015a] M. Christakis and P. Godefroid, “IC-Cut: A compositional search strategy for dynamic test generation,” in _Model Checking Software_ , 2015.
  * Christakis and Godefroid [2015b] M. Christakis and P. Godefroid, “Proving memory safety of the ANI Windows image parser using compositional exhaustive testing,” in _VMCAI_ , 2015\.
  * El Emam et al. [2001] K. El Emam, W. Melo, and J. Machado, “The prediction of faulty classes using object-oriented design metrics,” _Journal of Systems and Software_ , 2001\.
  * Ganesh et al. [2009] V. Ganesh, T. Leek, and M. Rinard, “Taint-based directed whitebox fuzzing,” in _ICSE_ , 2009.
  * Gao et al. [2016] F. Gao, L. Wang, and X. Li, “Bovinspector: automatic inspection and repair of buffer overflow vulnerabilities,” in _IEEE/ACM International Conference on Automated Software Engineering_ , 2016.
  * Godefroid [2007] P. Godefroid, “Compositional dynamic test generation,” in _ACM Sigplan Notices_ , 2007.
  * Godefroid et al. [2005] P. Godefroid, N. Klarlund, and K. Sen, “DART: directed automated random testing,” in _ACM Sigplan Notices_ , 2005.
  * Godefroid et al. [2008a] P. Godefroid, A. Kiezun, and M. Levin, “Grammar-based whitebox fuzzing,” in _ACM PLDI_ , 2008.
  * Godefroid et al. [2008b] P. Godefroid, M. Levin, and D. Molnar, “Automated whitebox fuzz testing.” in _NDSS_ , 2008.
  * Hodován et al. [2018] R. Hodován, Á. Kiss, and T. Gyimóthy, “Grammarinator: a grammar-based open source fuzzer,” in _Proceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation_ , 2018.
  * King [1976] J. King, “Symbolic execution and program testing,” _ACM Communications_ , 1976\.
  * Lattner and Adve [2004] C. Lattner and V. Adve, “Llvm: A compilation framework for lifelong program analysis & transformation,” in _International Symposium on Code Generation and Optimization (CGO)_ , 2004.
  * Lemieux and Sen [2017] C. Lemieux and K. Sen, “Fairfuzz: Targeting rare branches to rapidly increase greybox fuzz testing coverage,” _arXiv preprint arXiv:1709.07101_ , 2017\.
  * Ma et al. [2011] K. Ma, K. Phang, J. Foster, and M. Hicks, “Directed symbolic execution,” in _SAS_ , 2011.
  * Majumdar and Xu [2009] R. Majumdar and R. Xu, “Reducing test inputs using information partitions,” in _CAV_ , 2009.
  * Marinescu and Cadar [2013] P. Marinescu and C. Cadar, “Katch: high-coverage testing of software patches,” in _Proceedings of the Joint Meeting on Foundations of Software Engineering_ , 2013.
  * Miller et al. [1990] B. Miller, L. Fredriksen, and B. So, “An empirical study of the reliability of unix utilities,” _ACM Communications_ , 1990.
  * Nagappan et al. [2006] N. Nagappan, T. Ball, and A. Zeller, “Mining metrics to predict component failures,” in _International conference on Software engineering_ , 2006.
  * Ognawala et al. [2016] S. Ognawala, M. Ochoa, A. Pretschner, and T. Limmer, “MACKE: Compositional analysis of low-level vulnerabilities with symbolic execution,” in _ASE_ , 2016.
  * Ognawala et al. [2018c] S. Ognawala, R. N. Amato, A. Pretschner, and P. Kulkarni, “Automatically assessing vulnerabilities discovered by compositional analysis,” in _Proceedings of the 1st International Workshop on Machine Learning and Software Engineering in Symbiosis_ , 2018.
  * Ognawala et al. [2018a] S. Ognawala, T. Hutzelmann, E. Psallida, and A. Pretschner, “Improving function coverage with munch: A hybrid fuzzing and directed symbolic execution approach,” in _Proceedings of the Symposium on Applied Computing_. ACM, 2018.
  * Ognawala et al. [2018b] S. Ognawala, A. Pretschner, T. Hutzelmann, E. Psallida, and R. N. Amato, “Reviewing klee’s sonar-search strategy in context of greybox fuzzing,” _1st International KLEE Workshop_ , 2018.
  * Pak [2012] B. Pak, “Hybrid fuzz testing: Discovering software bugs via fuzzing and symbolic execution,” Ph.D. dissertation, CMU, 2012.
  * Pretschner [2001] A. Pretschner, “Classical search strategies for test case generation with constraint logic programming,” in _Formal Approaches to Testing of Software_ , 2001.
  * Pretschner [2003] A. Pretschner, “Compositional generation of mc/dc integration test suites,” _Electronic Notes in Theoretical Computer Science_ , vol. 82, 2003.
  * Rawat et al. [2017] S. Rawat, V. Jain, A. Kumar, L. Cojocar, C. Giuffrida, and H. Bos, “Vuzzer: Application-aware evolutionary fuzzing,” in _NDSS_ , 2017.
  * Rebert et al. [2014] A. Rebert, S. K. Cha, T. Avgerinos, J. Foote, D. Warren, G. Grieco, and D. Brumley, “Optimizing seed selection for fuzzing.” in _USENIX Security Symposium_ , 2014.
  * Sen et al. [2005] K. Sen, D. Marinov, and G. Agha, “CUTE: A concolic unit testing engine for C,” in _ACM SIGSOFT Software Engineering Notes_ , 2005.
  * Sen et al. [2015] K. Sen, G. Necula, L. Gong, and W. Choi, “Multise: Multi-path symbolic execution using value summaries,” in _FSE_ , 2015.
  * Serebryany [2016a] K. Serebryany, “Sanitize, Fuzz, and Harden Your C++ Code.” USENIX Association, 2016.
  * Serebryany et al. [2012] K. Serebryany, D. Bruening, A. Potapenko, and D. Vyukov, “AddressSanitizer: A Fast Address Sanity Checker.” in _USENIX_ , 2012.
  * Serebryany [2016b] K. Serebryany, “Continuous fuzzing with libfuzzer and addresssanitizer,” in _2016 IEEE Cybersecurity Development (SecDev)_ , 2016.
  * Stephens et al. [2016] N. Stephens, J. Grosen, C. Salls, A. Dutcher, R. Wang, J. Corbetta, Y. Shoshitaishvili, C. Kruegel, and G. Vigna, “Driller: Augmenting fuzzing through selective symbolic execution,” in _NDSS_ , 2016.
  * Sutton et al. [2007] M. Sutton, A. Greene, and P. Amini, _Fuzzing: brute force vulnerability discovery_. Pearson Education, 2007.
  * Sutton and Greene [2005] M. Sutton and A. Greene, “The art of file format fuzzing,” in _Blackhat USA conference_ , 2005.
  * Swiecki [2016] R. Swiecki, “Honggfuzz,” http://code.google.com/p/honggfuzz, 2016.
  * Takanen et al. [2008] A. Takanen, J. D. Demott, and C. Miller, _Fuzzing for software security testing and quality assurance_. Artech House, 2008.
  * Tassey [2002] G. Tassey, “The Economic Impacts of Inadequate Infrastructure for Software Testing,” National Institute of Standards and Technology, Tech. Rep., 2002.
  * [54] D. Trabish, A. Mattavelli, N. Rinetzky, and C. Cadar, “Chopped symbolic execution,” in _ACM/IEEE International Conference on Software Engineering_.
  * Wang et al. [2010] T. Wang, T. Wei, G. Gu, and W. Zou, “Taintscope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection,” in _Security & Privacy_, 2010.
  * Woo et al. [2013] M. Woo, S. K. Cha, S. Gottlieb, and D. Brumley, “Scheduling black-box mutational fuzzing,” in _ACM SIGSAC Computer & Communications Security, Proceedings of the_, 2013.
  * [57] M. Zalewski, “Afl fuzzer,” http://lcamtuf.coredump.cx/afl.