basicstyle=, numberblanklines=false, language=python, tabsize=2,
commentstyle=, keywordstyle=, morekeywords=assert, stringstyle=,
procnamestyle=, procnamekeys=def, columns=flexible, identifierstyle=

# Mutation Analysis: Answering the Fuzzing Challenge

Rahul Gopinath  CISPA Helmholtz Center
for Information Security
Email<EMAIL_ADDRESS>Philipp Görz  CISPA Helmholtz Center
for Information Security
Email<EMAIL_ADDRESS>Alex Groce  Northern Arizona University
Email<EMAIL_ADDRESS>
###### Abstract

Fuzzing is one of the fastest growing fields in software testing. The idea
behind fuzzing is to check the behavior of software against a large number of
randomly generated inputs, trying to cover all interesting parts of the input
space, while observing the tested software for anomalous behaviour. One of the
biggest challenges facing fuzzer users is how to validate software behavior,
and how to improve the quality of oracles used.

While mutation analysis is the premier technique for evaluating the quality of
software test oracles, mutation score is rarely used as a metric for
evaluating fuzzer quality. Unless mutation analysis researchers can solve
multiple problems that make applying mutation analysis to fuzzing challenging,
mutation analysis may be permanently sidelined in one of the most important
areas of testing and security research.

This paper attempts to understand the main challenges in applying mutation
analysis for evaluating fuzzers, so that researchers can focus on solving
these challenges.

##  I Introduction

In the new millennium, fuzz testing (fuzzing) has rapidly become one of the
most popular techniques used in cybersecurity to test the robustness of
programs [1]. It is used by industry giants such as Google [2, 3], Microsoft
[4], Amazon [5], Meta [6] and others. Industry behemoths such as Microsoft now
mandate fuzzing of every untrusted interface of every product [7].
Practitioners have used fuzzing to find thousands of vulnerabilities [7, 8]
and other bugs in various applications. Indeed fuzzing has in effect
democratized the field of software testing. Organizations such as small
businesses can buy off-the-shelf fuzzers, or make use of online services [9],
to evaluate their software, and have confidence that their applications are
free of easily exploitable vulnerabilities.

While fuzzing has taken the world by storm, several challenges remain. The
foremost among them is the question of oracles [10]. Traditional first
generation fuzzers typically focused on finding inputs that made the program
under evaluation crash. However, this is no longer sufficient. As Firefox
fuzzing directions [11] note: _Fuzzing is only effective if you are able to
know when a problem has been found._ That is, we need fuzzers to be able to
identify more types of vulnerabilities. We need to find bugs that do not only
manifest as a program crash. Going forward, we need to evaluate fuzzers not
just on their ability to cover the program code, but also on their
intelligence in detecting different kinds of incorrect behaviors.

Fuzzing research typically uses two metrics for evaluating fuzzer
effectiveness: (1) various forms of coverage, with paths taken seen as the
best measure [12] and branches taken being another common measure; and (2)
artificial benchmarks with seeded bugs (Magma [13], LAVA-M [14], BugBench
[15], CGC [16], Google FTS [17], FuzzBench [18], UNIFUZZ [19], Apocalypse
[20], EvilCoder [21]) which are often considered the _ground truth_.

However, we know that coverage can often be quickly saturated [22], and that
adequate coverage is a necessary, but not sufficient condition for all bugs to
be detected. Indeed, fuzzing researchers are aware of the limitations of
coverage as a proxy measure [23].

Regarding seeded bugs, the basic problem is that the distribution of such bugs
is subject to human bias. That is, engineers who are tasked with inserting
bugs may often be biased about what kind of bugs are possible and where they
may be present. Hence, the distribution of such seeded bugs need not follow
the actual real-world distribution. If one relies on automatic tools, the bug
distribution may also be biased due to the capability of the tool in question.
Indeed, as Bundt et al. [24] notes, these are limited by the the reachability
of their analysis, limited bug types, and bug realism.

On the other hand, if one uses harvested bugs from existing programs [25],
this too introduces a bias. The issue is that, the availability of bugs does
not mean that the particular program elements contained more bugs. Rather, it
only means that the bugs in those elements were more easily detected. That is,
any tool that performs well in those benchmarks is likely to be better at
finding bugs that we already know how to detect; such an approach may well
penalize tools that are most suited for finding new _kinds_ of bugs.

A related problem is that tools such as AFL are commonly used to find and
remove bugs in programs before they become deployed or published. This means
that the bugs found by such popular tools are likely to be found less and less
in the bugs available for harvesting (e.g. in CVEs). This, in contrast,
rewards tools that may be less able to detect bugs AFL finds easily, but are
able to find bugs AFL cannot find easily.

A final issue in using such benchmarks is that fuzzers can become overfitted
to finding bugs in such benchmarks [23, 24]. That is, we run the risk that our
fuzzers become more and more efficient in exploring the bug-inducing
statements in the benchmark, and more effective in triggering the bugs in the
benchmark to the detriment of their real-world performance.

Various proposals for handling these problems have been posed; for instance
Gavrilov et al. [26] propose using multiple versions of a program and
detecting differences exposed by fuzzers as a richer evaluation measure (they
also provide a more in-depth examination of the weakness of the coverage and
seeded-bug measures discussed above). However, such an approach requires the
availability of multiple versions of a program, and is not fundamentally tied
to measuring bug detection (if outputs differ but are not flagged as faulty,
this is seen as a difference in appeal, regardless of oracle strength).

Given the importance of oracles in fuzzing, one might expect mutation analysis
to be actively used for fuzzer evaluation. Mutation analysis is free of all
the above problems that we identified. For example, mutation analysis is much
harder to saturate than code coverage [22], and is more robust than various
forms of coverage as a proxy for the fault revealing power of the test suite.

Similarly, the mutations produced by mutation analysis are based on a simple
fault model that correspond fairly well to real-world [27] faults. That is,
the simple faults produced by mutation analysis are free of influence from
human biases. Further, given that the mutations produced are not based on any
sort of harvested bugs, these are free of bias due to availability: mutation
analysis will induce bugs that are both easy and hard for, e.g., AFL to
detect.

Unfortunately, out of the numerous fuzzing evaluation research papers
available [23, 19, 24, 28, 29, 30, 26] _none_ recommends the use of mutation
analysis for fuzzing. Indeed, none of the papers we examined [1, 31, 32, 33]
actually used mutation score as a means of evaluation. To our knowledge, the
only published paper that uses mutation to evaluate fuzzing is a Software
Engineering in Practice short paper [34] discussing an effort to improve
fuzzing for Bitcoin Core (suggesting that _practitioners_ are interested in
the possibility, even if researchers are not, yet). This is surprising because
mutation analysis can actually answer many of the challenges posed by fuzzing
researchers such as computing residual risk [10, C.7], and producing faults
that are similar to real bugs [10, C.11, C.12]. Indeed, the theory of mutation
analysis is well researched, and mature.

In this paper, we examine the reasons why mutation analysis has, so far,
evaded the attention of security researchers. We identify a few likely
reasons, propose mitigations, and identify areas of future research.

##  II Background

###  II-A Fuzzing

Fuzzing is simple in concept. Given any application that accepts user
specified inputs, the application is executed with inputs, generated by the
fuzzer, that try to exercise as much of the application behaviour as possible.
The program execution is monitored for crashes or other surprising behavior
that can be detected by the available oracles [1].

Fuzzers, and test generators in general are typically evaluated based on the
(1) speed of their turn around, their (2) speed of generation of inputs, and
the (3) quality of their oracles. We define the following metrics for fuzzer
evaluation111 We note that there is no agreement on what these terms mean in
fuzzing research. For example, Böhme et al. [10] defines efficiency as the
rate at which vulnerabilities are discovered, and effectiveness as the total
number of vulnerabilities that a fuzzer can discover in the limit (i.e. given
infinite time). However, given that code coverage is used to measure
_effectiveness_ in a majority of papers [23], we believe that _effectiveness_
as used by the fuzzing community relates to the quality of inputs rather than
the oracle used. Hence, we use _efficacy_ to denote the oracle quality here as
it seems unused in fuzzing literature (and we could not find a corresponding
term for oracle quality in fuzzing research). Finally, the speed at which
vulnerabilities can be found seems to be related to the speed at which one can
execute the tests (assuming a uniform distribution and difficulty of finding
them). Hence, we use _efficiency_ to denote the speed of execution. .

Efficiency of the framework.

The turn-around time for the fuzzer. It is influenced by the speed of
generation of inputs for execution, whether the fuzzer can be parallelized,
the speed of execution of the program for a given input.

Effectiveness of the generator.

The effectiveness of the tests generated in covering all features of the
program, and the effectiveness of inputs for triggering failures.

Efficacy of the oracle.

The capability of the fuzzer oracle to detect triggered changes in behavior,
especially failures or vulnerabilities.

####  II-A1 Input Generation Techniques

Fuzzers rely on being able to test the program under fuzzing a large number of
times. They rely on raw computing power to accomplish this fast (that is,
within a given time budget), and there is a lot of focus on improving the
speed of execution of the input generator [35, 36] as well as fast execution
of programs under test [37]. As to the _intelligence_ used for generation of
inputs, test generators in general are typically classified based on the
assumptions they make about the program in question. These include:

White-box generator.

White-box generators assume the availability of source code for both static as
well as dynamic analysis. These generators are also called clear-box
generators or structural test generators. The availability of source code has
traditionally meant that the program input specification is also known. Sage
[4] is a canonical example.

Grey-box generator.

Grey-box generators are a spectrum of generators where deep program analysis
may be impossible or prohibitive to perform. Instead, these generators assume
that the program can be instrumented, and the feedback can be used to guide
the program input generation. AFL [37] is a canonical feedback driven grey-box
generator. A grey-box or white-box generator can be used even if the formal
program interface is not known. Starting with an initial seed corpus, that may
just be a single empty input, the generator mutates one input of the corpus,
such as randomly changing a byte, and observing the resulting feedback.
Interesting inputs are added to the corpus for further mutations, a typical
evolutionary algorithm. The efficacy of this approach can be enhanced by a
seed corpus that excerises larger parts of the target program, providing a
larger frontier to find interesting inputs. Fuzzers that rely on mutation of a
seed corpus for exploring the input space are called _mutation fuzzers_. AFL
is again a canonical example. Both mutation and generation can also be
combined as in AFLSmart [38].

Black-box generator.

Black-box generators are used when the source code of the program under test
is not available, and it is impossible to instrument the program for feedback.
These generators typically assume that the program input specification is
known [35] which is used for intelligent generation of inputs222 Black-box
testing is also called _specification-based_ testing. . These kinds of fuzzers
are also called _generational fuzzers_ or _grammar fuzzers_.

Hidden-box generator.

Traditionally called dumb generators, these are generators that make the least
amount of assumptions about the program in question. They assume _nothing_
about what kind of inputs are accepted by the program, but rely on the fact
that program crashes are undesirable. Pure random fuzzers [39] are the best
known, but not the only kind of hidden-box generator. Other examples include
Anti-random [40] and failure-feedback [41] generators.

####  II-A2 Type of Oracles

Different fuzzers can also be distinguished by their oracle efficacy, as
follows.

Explicit oracles.

These are contracts that are explicitly specified by the practitioner [42].
These are also called _specification based_ oracles [43]. An example of an
explicit contract is that the output should conform to, say, a given XML
schema, or that the output should be a valid JSON file. Property based testers
such as QuickCheck [44] can make use of sufficiently detailed contracts for
strong oracles.

Implicit oracles.

Implicit oracles are oracles that describe the general valid state of the
program. These are the typical oracles used in general fuzzers [42]. Tools
such as DeepState [45] make it possible to use QuickCheck-style property-based
specifications with off-the-shelf fuzzers like AFL. Sanitizers are one of the
most common types of _implicit oracles_ used for fuzzing. A number of
sanitisers exist that can be used with general fuzzers [46]. The most popular
ones [47] are memory (MSAN) sanitiser which detects uses of uninitialized
memory, address (ASAN) sanitizer which targets use-after-free buffer-overflows
and memory leaks, thread sanitizer (TSAN) which detects data races and
deadlocks, floating-point sanitizer (NSAN), and undefined behaviour sanitizer
(UB-San) [46, 48].

Differential oracles.

These are also called pseudo oracles [49, 50, 51]. If there exists a different
program that implements the same specification, then one can make use of a
differential oracle. The idea is to generate inputs and compare the behavior
of different programs. If there is a difference between the two
implementations, at least one of them is wrong. Common examples include
parsers for common file formats, virtual machines such as CLR, WASM, and JVM,
and protocol implementations such as FTP and HTTP. A common variant of this
idea is the regression oracle [52]. In this case, a different version of the
same program is used to verify that only expected features differ. Finally,
tools such as Evosuite [53] that make use of mutants for generating test cases
also use the same idea.

Metamorphic oracles.

These are oracles that rely on metamorphic relations between inputs [54, 55,
56, 57] An important category of metamorphic oracles is cross-checking oracles
[58], which use redundant operations in software APIs as a way of constructing
possibly equivalent API call test sequences and assertions.

Dynamic invariants.

The final approach involves monitoring the invariants between program
variables during execution, and tries to identify outlying executions. These
are exemplified by Daikon [59].

###  II-B Mutation Analysis

Mutation analysis is a technique for evaluating the fault revealing power of
test suites on a given program. We define the following mutation related
terms:

Mutation.

A mutation is a small syntactic change that can be induced in the program,
that will likely lead to a semantic difference.

Mutation operator.

Mutation operators are replacement patterns that describe how mutations are
induced in the program. A mutation operator, when applied to a matching
location in the program, will produce a _mutant_.

Mutant.

A mutant is a new program that contains differences (mutations) from the
original. A _first order_ mutant contains only a single mutation. A _higher
order_ mutant contains multiple mutations.

Trivial mutants.

These are mutants that can be killed (detected as failure inducing) without
targeted intelligence. That is, an input that covers the mutation location in
the original program already killed them, such as a fuzzer’s seed input.

Redundant mutants.

A mutant A is redundant with respect to another mutant B if any test that can
kill mutant B is guaranteed to kill A.

Duplicate mutants.

A mutant A is duplicate of another mutant B if any test that kills A will kill
B and vice versa.

Stubborn Mutants.

These are mutants that remained alive even after coverage reached their
mutation locations.

Intelligent mutants.

These are mutants that were killed by fuzzers on individual evaluation (i.e.,
they required intelligence to kill).

Immortal mutants.

Mutants that can’t be killed by any weak oracles such as crash oracles in the
current program.

Equivalent mutants.

An equivalent mutant is a mutant that, while different from the original
program syntactically, has the same semantics.

####  II-B1 Error Model

For mutation analysis, we start with the following _error model_ : Any
token333A token is the smallest syntactical element in the program. in a
program is a possible location for a fault to exist, and faults are likely
caused during transcription of the concept in the developer’s mind to the code
artifact. Further, we assume that the developer uses automatic tools such as
compilers which can identify and remove a limited category of faults. This
gives us a way to generate possible faults without human bias: Simply generate
all possible instances of faults for each source code element that will get
past the compiler. Unfortunately, this can lead to a combinatorial explosion.
Hence, we rely on a few axioms to limit the number of faults generated. The
_finite neighborhood hypothesis_ and the _coupling effect_.

####  II-B2 Fundamental Axioms

The _finite neighborhood hypothesis_ states that faults, if present in the
program, are within a limited edit distance away from the correct formulation
[27]. The _coupling effect_ claims that simple faults are coupled to complex
faults, such that tests capable of detecting failures due to simple faults
will, with high probability, detect the failures due to complex faults. Hence,
the probability of fault masking is very low [60]. Both these axioms are well
researched, with well-founded theory [61, 62, 63, 64], and confirmed in large
number of real world software [65, 64, 66, 67]. With these two axioms, we can
limit the faults that we need to test. Allowing us to focus only on changes to
the smallest program elements, such as tokens and statements, and still expect
that the created mutations are representative of real bugs.

Given this error model, the idea of mutation analysis is to simply collect
possible fault patterns (a single fault pattern is called a _mutation
operator_). Identify possible faults in the program (called _mutations_),
generate corresponding faulty programs (called _mutants_) each containing a
single _mutation_ , and finally evaluate each _mutant_ separately using each
software verifier (test suites, static analyzers [68], static test generators,
and fuzzers) and check whether the verifier is able to detect the changed
behavior of the mutant (called _killing the mutant_). The idea is that the
number of mutants thus killed by each verifier provides a simple and effective
criteria to compare verifiers.

##  III Mutation Analysis for Fuzzing – Advantages

Böhme et al. [12] identified the following questions as the current challenges
in fuzzing. We mark each question that mutation analysis or mutation analysis
research can potentially answer ( ), help answer ( ), evaluate ( ), or provide
insights on(✓).

  * C.1.

How to fuzz more types of software.

  * C.2.

How to identify more types of vulnerabilities.

  * C.3.

How to find more deep bugs. ✓

  * C.4.

What kind of vulnerabilities are not found by fuzzing.

  * C.5.

How to leverage the auditor.

  * C.6.

How to improve the usability of fuzzing tools.

  * C.7.

How to assess the residual security risk.

  * C.8.

What are the limitations of fuzzing.

  * C.9.

How to evaluate more specialized fuzzers.

  * C.10.

How to prevent overfitting to a specific benchmark?

  * C.11.

Are synthetic bugs representative?

  * C.12.

Are bugs discovered by fuzzers, representative?

  * C.13.

Is coverage a good measure for fuzzer effectiveness?

  * C.14.

What is a fair time budget?

  * C.15.

How to evaluate techniques instead of implementations.

Mutation analysis can help in overcoming 10 out of 15 challenges in fuzzing.
Next we discuss how and why this is the case for each challenge in more
detail.

####  C.2. How to identify more types of vulnerabilities.

This is a major limitation in current fuzzing benchmarks [24]. As discussed in
the introduction, this is the most obvious way mutation analysis can aid
fuzzing research. Research currently uses either structural coverage (which
almost always provides no insight into oracles and vulnerability types) or
seeded/harvested bugs, where adding new categories of bug is labor-intensive
and prone to either human or tool bias.

Mutation analysis has a lot to offer here. In particular, mutation analysis is
fault-based, which means that it explicitly evaluates the oracular strength.
Something structural coverage metrics are not able to do, additionally,
mutation analysis does not get saturated as fast as coverage does.

Indeed, mutation analysis is one of the best fault based evaluation techniques
we have, as it is based on a well founded theory, and was created with the
explicit purpose of avoiding the pitfalls of fault seeding (i.e. benchmarks).

Mutation analysis avoids pitfalls of fault seeding benchmarks, and can induce
a much larger variety of bugs that match the real world bugs in behavioral
variety and difficulty.

Mutation analysis exhaustively seeds the program with first order variations.
As a consequence, there is no bias in the kinds of bugs that are seeded,
avoiding the possibility of fuzzers overfitting. All in all, mutation analysis
can adequately answer the challenge posed by Böhme [10, C.2].

####  C.3. How to find more deep bugs.

Solving this challenge can likely be achieved by improving the quality of
input generators. However, inducing subtle faults into predicates as T-Fuzz
[69] does can help. However, the induced faults need to be small enough so as
to affect the validity of the input execution minimally. Mutation analysis
research can help here [70]; in work-in-progress (citation blinded for
review), we have used mutation to generate program variants to explore deep
behavior. Furthermore, unlike traditional fault-injection techniques such as
LAVA-M [14], faults injected by mutation analysis is not limited to a limited
reachable subset of the program as it faithfully recreates possible errors by
the programmer anywhere in the program. Hence, bugs induced by mutation
analysis can distinguish the capability of fuzzers to detect deep bugs.

The faults injected by mutation analysis is not limited by any analysis.

####  C.4. What is the nature of vulnerabilities that are not found?

This challenge is about identifying the nature of bugs that evaded detection
after long fuzzing campaigns. While empirical studies are certainly helpful
here, mutation analysis has something to offer as well. In particular,
mutation analysis is a mature field with well established research on the
nature of bugs [71, 65].

Second, mutation analysis has a well founded theory based on exhaustively
seeding first order faults. The first order faults serve as the base case and
the coupling effect hypothesis which serves as the induction to ensure that a
large majority ($>99$% [64]) of the higher order faults are found by test
suites adequate to detect these first order mutants. Further, for those rare
faults that slip through, mutation analysis can be easily extended with new
operators that need not be first order [72, 73].

The mutants that remain after a fuzzing campaign indicates the kinds of bugs a
fuzzing campaign missed.

What about failures that require interaction between multiple faults? Such
faults are impossible to find by first order mutation. However, there are two
mitigations here. The first is that surpricingly small number of faults are
sufficient for a majority of FTFI (failure-triggering fault interactions)
found [74, 64], with more than 90% of the failures observed involving just one
or two faults. Indeed, most failures were triggered by a single erroneous
parameter to a function, and almost all could be induced by fewer than 4
faults. Second, one may induce subtle mutations using higher order mutation
[72] which can adequately represent such rare faults.

####  C.7. How to assess the residual security risk?

One of the main reasons for using mutation analysis is that it provides the
best estimate for _residual defects_ in a program, the number of defects that
remain in a program after testing is completed444At this point, we assume that
no _detected faults_ remain in the program. Any that were found were fixed..
Assume for a moment that the fault was small enough to be a mutation, and one
of our mutants reverses this fault. If so, (assuming sound testers), a testing
professional would never have written a test to kill the mutant. Rather, it
would have been flagged a defect, and fixed. If, on the other hand, the
difference between the corrected version and the faulty version was bigger
than any mutant, by the coupling effect hypothesis, there must still exist
multiple mutants that correspond to different parts of the failure behavior
(not necessarily representing the correct behavior). If so, for a tester to
kill such mutants, the tester has to assert the correct behavior for that
mutant, and given that the failure behavior is different from the correct
behavior, this would again have been flagged as a fault and fixed. This is
true for assertions from any oracle, so long as the oracle is sound. We note
that fuzzing relies on weak crash oracles that are sound but not complete.
Hence, as the number of mutants that remain undetected decreases, the number
of defects that remain undetected also decreases monotonically. Hence, the
number of mutants that remain alive is a _true ordinal measure_ 555 By true
ordinal measure, we simply mean a measure that corresponds to the definitions
from measure theory [75]. That is, it follows monotonicity of the measured
quantity, and additivity of measures between independent subsets. That is, it
is different from mere correlation. for the residual defects in the program.

Mutation analysis can comprehensively answer the question of residual risk
after fuzzing.

####  C.9. How to evaluate more specialized fuzzers.

This question is about the challenge of evaluating fuzzers that are focused on
specific kinds of bugs, or specific kinds of programs. For example, one may be
out of luck if one is looking for parser bugs, or specifically binary parser
bugs because the baselines may not contain such parsers. As Böhme notes [10],
current benchmarks are often not designed for such tasks, and he advocates for
suitable programs and baselines for comparison. The trouble is that, adding
new programs to your benchmark is only postponing the problem. Say you have –
after many months of manual effort – added a few parsers and corresponding
harvested bugs to your benchmark. A new language feature, or a new kind of
parsing such as combinatorial parsing can make such benchmarks inadequate to
deal with the new kinds of bugs introduced, while removing the bugs that are
evaluated in your benchmark. Hence, improving the benchmark is not a solution
here.

However, mutation analysis has a simple solution here. If a particular kind of
program is not present in the benchmark, simply add the program, and let
mutation analysis generate the bugs to be evaluated. This removes the manual
effort present in keeping the benchmark up to date.

####  C.10. How to prevent overfitting to a specific benchmark?

In this question, Böhme points out that fuzzers can become overfitted to a
specific benchmark irrespective of the superiority of a benchmark. Böhme
proposes various solutions involving collecting even more benchmarks. The
trouble here is again that for fault-seeding, one needs not only programs, but
also harvested or seeded bugs on these programs. This is a labour intensive
task.

As before, the mutation analysis solution is simple. Collect as many programs
as are possible. So long as you are able to run it, mutation analysis will
take care of seeding the right bugs for you. Indeed, if you are a user of
specific kinds of programs such as the military or government, with the
traditional approach of fault seeding, it is nearly impossible to find
preexisting benchmarks that suit your purpose. With mutation analysis, you can
make your own benchmark, and evaluate fuzzers on it without much manual
effort.

Further, one can extend mutation analysis with new kinds of mutation operators
as well as higher order mutants [72, 73] deriving more value out of an
existing benchmark.

Similarly, if you are working on a new or less popular language, you are again
out of luck with the traditional fault-seeding benchmarks. With mutation
analysis, you can simply collect programs, and mutation analysis to seed bugs,
given the existence of _universal_ mutation tools that apply to essentially
any program language [76].

Using mutation analysis fuzzing researchers can avoid overfitting to
benchmarks.

####  C.11. Are synthetic bugs representative?

This question is about whether the seeded bugs designed by engineers or by
artificial injectors such as LAVA-M [14] are representative of the real bugs
[24]. If not, what can we do to make them so? This is a question that was
comprehensively answered by mutation analysis research. Indeed, we know that
the faults seeded by mutation analysis are representative of real world bugs
both in terms of syntax [27] as well as semantics [77, 78], and having a
higher mutation score means lesser number of found bugs in the future [79,
80], and thus mutants are valid substitutes for real faults [65]. That is, if
one is to rely on bugs induced by mutation analysis, one can have high
confidence that the bugs induced are representative of the real world.

The bugs induced by mutation analysis can match the realism of real world
bugs.

####  C.12. Are bugs discovered previously by fuzzers, representative?

This question is about bugs collected through harvesting preexisting bugs for
benchmarks. As we discussed in _C.11_ , the faults induced by mutation
analysis are indeed representative of real world. Further, new fault patterns
can be easily mined and added if necessary.

####  C.13. Is coverage a good measure for fuzzer effectiveness?

The problem with coverage is that it is a necessary but not sufficient
condition for detecting faults. In particular, covering a fault is a necessary
but not a sufficient precondition for triggering that failure, and even if the
failure is triggered, we need adequate oracles that can detect the failure.
Coverage does not measure the quality of oracles available. Secondly, coverage
is often easily saturated [22]. Once coverage is saturated, there is little
feedback available for further fuzzing.

####  C.14. What is a fair time budget?

In this question Böhme points out that there may be a difference between
fuzzers in terms of the number of vulnerabilities that they can detect in the
limit (given infinite time). However, even a hidden-box fuzzer assuming
nothing about the program in question can, in the limit, generate any input.
Any fuzzer that doesn’t can be trivially extended with a hidden-box fuzzer to
be maximally effective in terms of its inputs. However, the idea here seems to
have been about distinguishing between fuzzers in terms of the trade-off
between efficiency and effectiveness in terms of the curve of discovery. We
note that the complexity of a program is related to the number of mutants it
can have [81]. Hence, any fair budget should correspond to the number of
mutants produced. We discuss how to measure this curve in more detail in
Section IV-B2.

Mutation analysis can adequately answer or help answer, evaluate, or provide
insights on 10 of the 15 major challenges faced by fuzzing research.

##  IV Mutation Analysis for Fuzzing – Challenges

Mutation score and structural coverage metrics are typically used for two
different but related purposes in the software-engineering world.

  1. (1)

The first, and traditional, use is by a practitioner to evaluate the
_adequacy_ of a test suite. That is, if one considers statement coverage, a
coverage result of 100% means that all statements in the program were executed
at least once. That is, the test suite is coverage adequate.

  2. (2)

The second common use of mutation score and other coverage metrics is as a
means of _comparing between two test suites_.

The _adequacy_ of a test suite was often the most important factor when
considering static test suites. The reason is that, in traditional testing
scenario, one rarely needed to compare different ways of creating test cases,
because there was often only one kind – developer written test cases. However,
with the advent of test generators such as Evosuite [53], Randoop [82], and
different fuzzers, the situation has changed. Most of these fuzzers and other
test generators can make use of any and all computational resources as you can
provide them. There is no fixed point at which they stop. Unfortunately, there
is an exponential increase in difficulty in finding the next bug [12]. Hence,
we need to decide how to allocate limited testing budget, and for that we need
to find the best test generator.

###  IV-A Computational Expense

The main problem with mutation analysis is its computational requirements. The
number of mutants that have to be evaluated increases with the size of the
program. Further, for fuzzing we need to evaluate each input produced
independently on each mutant. That is, we can’t tell if a mutant will be
killed by an input without executing the mutant on that input. We can’t even
assume that the fuzzer will produce the same input on the original as well as
the mutant because the fuzzer may find the mutation in the program using
static analysis, and take steps to reach it or to induce failure on a
perceived fault. Further, most feedback driven fuzzers (e.g., AFL) will modify
their next input correspondingly to take advantage of any new coverage found,
which may be induced by the mutation. Hence, it is highly likely that the
fuzzer generated inputs are different for the original code and various
mutants. This means that there is a quadratic increase in the number of
program executions required with program size.

There are a number of traditional optimizations to make mutation analysis less
computationally demanding. However, most of these techniques assume static
test suites, which makes them inapplicable to fuzzers. For example, two
algorithms try to reduce the number of mutants to be evaluated by identifying
which tests are applicable to which mutants. The first, called lazy mutation
analysis, by Fleyshgakker [83] uses weak mutation kills to identify which
tests to run on which mutants. A less complex approach is to use code coverage
for the same purpose [84, 85]. The idea is to find the statements in the
program that are covered by the specific tests in the test suite, then only
run tests against mutants they cover. Unfortunately, these techniques are
inapplicable to fuzzers because fuzzers may not use the same input sequences
on all mutants, as we mentioned above.

That is, a fuzzer may analyze the source code statically and modify its
behavior correspondingly resulting in different fuzzer behaviors for the
original program and the mutant (violating the clean program assumption [67]).
Another optimization is to use _weak mutations_ [86] which only check whether
an input would have resulted in a different state in the mutant when compared
to the original. This again assumes that the test suite will not change when a
mutation is present. Partitioning infected states [87], split stream execution
[88, 89] and equivalence modulo states [90] assume again that the same inputs
are used for both mutant and original program. A recent optimization technique
is to memorize expensive methods [91] so that if function calls with the same
arguments are present in the original and the mutant, then the results can be
reused. The effectiveness of this technique again depends on the same inputs
being used for original and mutant. Indeed, even the relatively harmless
schemata based mutation execution optimization [92, 93, 94] can induce changes
in the fuzzer behavior, as the fuzzer can wastefully try to generate inputs in
an attempt to reach the disabled mutations when another mutation is enabled.

Techniques such as test selection [95, 96] can’t be used for fuzzing because
they rely on a static test suite.

Thus, these traditional optimization techniques do not work well for fuzzers.

Challenge 1: Find optimizations that do not rely on static test suites.

###  IV-B Comparing Test Generators

####  IV-B1 Non-determinism

One of the challenges in evaluating test generators is that many of these are
dependent on non-deterministic execution for their effectiveness. The problem
with non-determinism is also that the results achieved depend on the initial
random seed, and also on the seed corpus [23]. Hence, one evaluation alone is
insufficient for statistical confidence in the evaluation rankings [23].

Unlike coverage techniques which impose very little overhead over the program,
mutation analysis can be costly. Hence, running mutation analysis multiple
times for statistical certainty can be prohibitive.

####  IV-B2 Distribution

The second challenge in evaluating test generators is that there is no single
point at which a test generator stops. Secondly, the speed of analysis and
execution plays a large role in how effective a fuzzer is. For example, a
naive fuzzer [39] or a simple grammar fuzzer [35] can run circles around a
more intelligent symbolic execution based fuzzer in the initial stages [4]
because program analysis and symbolic execution can take time. However, beyond
the easily explorable program paths, the symbolic fuzzer can leverage
information about the predicates guarding program paths, and make better use
of the computational resources at a later stage [23]. Finally, any fuzzer can
(or can be trivially extended with a hidden-box fuzzer to) find all bugs that
its oracle can detect, in the limit. This is because, in the limit, all inputs
will be tried at some point.

Hence, we need to identify the fault revealing curve of a test generator for
adequate comparison, which should be provided to the practitioners. A single
score will no longer cut it.

However, unlike coverage which can be obtained from a single program, multiple
mutants need to be evaluated for mutation analysis. This means that there can
be impacts due to parallelization, scheduling algorithms etc., on the average
number of mutants detected at any point in time.

Challenge 2: Find ways to incorporate statistical and time based distribution
of mutant kills cost-effectively.

###  IV-C Problems with Redundancy

One of the problems with mutation analysis is that the mutants produced may be
redundant or there may even be true duplicate mutants. The problem with such
mutants is that they can affect the correlation of mutation score to the real
fault detection. That is, say you have N duplicate mutants. If we have an
input that kills these N mutants, it is only worth one mutant, but will be
counted as N in the mutation score. On the other hand, if these mutants remain
undetected, the number of mutants yet to be killed is inflated. Hence,
redundant and duplicate mutants are undesirable. The traditional approach to
eliminating them has been to compute the full mutation matrix of tests x
mutants result, and compute the minimal mutant set. However, with fuzzing this
is not possible for two reasons: (1) there is no end point for fuzzing. Hence,
the size of test suite is limited only by the available time and (2) the test
suites may differ between each mutant. That is, we have no simple way to
compute duplicate and redundant mutants during fuzzing.

Challenge 3: Determine how to account for redundant mutants during fuzzer
comparison.

###  IV-D Equivalent Mutants

A somewhat similar problems with mutation analysis is equivalent mutants.
These are mutants that are semantically the same as the original program. For
example, given a cache optimization for a complex computation such as below,

⬇

1if (cache.has(key))

2 return cache.get(key);

3return compute(key);

removing the cache check need not induce a failure. The problem with
equivalent mutants is that they make the final mutation score unreliable. That
is, we do not know for sure if the live mutants remaining are actually
killable or not. Indeed, anywhere from 10% to 40% of generated mutants could
be equivalent [97, 98]666Later analysis suggests a more refined figure of 23%
[99].. However, the actual percentages are very program dependent.

One of the promising approaches toward estimation of equivalent mutants is
using _species richness estimation_ as proposed by Böhme. [100]. The idea is
to use the frequency of counts of mutants that are found by different test
cases to estimate the number of mutants that are yet to be found. This can
provide us with an estimate of the total _killable_ mutants if one is given
the full kill matrix that describes which mutants are killed by which tests (M
$\times$ T). Unfortunately, given that the test cases are not static between
different mutants, this method can’t be used for estimation of equivalent
mutants during fuzzing.

While equivalent mutants are troublesome for interpretation of mutation score,
such equivalent mutants are less of a concern for fuzzer comparison, because,
for comparison, the only concern is the number of relative mutant kills
between fuzzers.

Challenge 4: Determine how to account for equivalent mutants in fuzzer
evaluation.

###  IV-E Lack of mutation analysis Frameworks that Focus on Fuzzers

One of the difficulties encountered when trying to use mutation analysis with
fuzzers is that there are no mutation frameworks that are capable of running
fuzzers on mutants efficiently. Fuzzers typically rely on framework support
for coverage feedback. Further, many fuzzers also rely on starting seeds.
Accounting for, and managing such seeds while also parallelizing mutation
analysis is not yet available in mutation frameworks.

Challenge 5: Build mutation analysis frameworks that are fully capable of
fuzzer evaluation.

###  IV-F Lack of Awareness Among Researchers

While we have identified possible technical reasons for the dismal popularity
of mutation analysis among security researchers, lack of awareness may also be
an equally important reason. Indeed, none of the fuzzing review papers we
examined contained any reference to mutation analysis.

Challenge 6: Improve visibility of mutation analysis among fuzzing
researchers.

##  V Promising Directions for Research

###  V-A Computational Expense

Computational expense in running mutation analysis is one of the major
impediments for the use of mutation analysis to evaluate fuzzers. We discuss a
few possibilities to mitigate this problem.

####  V-A1 Mutant reduction

One of the possible ways to reduce the cost of mutation analysis without
assuming anything about the test suite is to reduce the number of mutants
evaluated. Indeed, this is one of the traditional techniques for reducing the
cost of mutation analysis. However, one needs to be careful how the number of
mutants is reduced. In particular, mutation operator selection techniques can
have unexpected disadvantages [101]. The best reduction can be achieved using
random sampling or various forms of strata sampling techniques with different
strata such as program elements or operators.

Sampling may not sound promising because it comes with associated non-
determinism and loss of distinguishing power for mutation analysis (when we
sample, we are essentially accepting a more limited accuracy for the metric).

####  V-A2 Splitting the evaluation

However, there may be a better way out. It may be observed that during
fuzzing, one needs both effectiveness as well as efficacy. That is, one needs
to generate inputs that can cover all possible input features. Further, we
need oracles that can validate these inputs. Given that coverage is good in
the first part, and mutation analysis is good at the second part, why not
split them?

The idea is to use coverage as the evaluator for fuzzers until coverage is
saturated. We use the standard 24 hours timeout for fuzzing [23]. Once
coverage is saturated for all fuzzers, we collect any and all inputs that are
required to cover the program maximally, and minimize them to produce a
minimal test suite with the same coverage. Let us call this the _coverage
seed_. Next, we use this test suite as a static test suite, and run mutation
analysis with it, removing any mutant that is killed using this set of inputs.
At this point, all traditional optimizations of mutation analysis can be
applied. This allows us to remove _trivial mutants_ cheaply. We then run
mutation analysis for each fuzzer starting with the minimal test suite as the
seed corpus for each. With this technique, we only evaluate _intelligently
selected mutants_ with fuzzing runs.

####  V-A3 Supermutants

A third way out is to evaluate multiple mutants at once. The idea is to
produce higher order mutants where the individual mutations are independent of
each other in terms of semantics [102] and fuzz the higher order mutant. The
idea is to produce higher order mutants such that any input will cover at most
one simple mutation in the higher order mutant. Count any crash as killing the
mutant corresponding to the mutation that was covered by the crash inducing
input. The higher order mutant is completely killed when all corresponding
simple mutants are killed. This can reduce the number of mutants to be
independently evaluated.

###  V-B Comparing Test Generators

For comparing test generators, we need the curve of discovery as we discussed
in Section IV-B2. However, if we split the evaluation into a coverage part and
a mutation analysis part as discussed in Section V-A2, then we can reduce the
computational requirements for computing the curve as follows. For every
_chosen mutant_ , we keep track of the time at which it was killed. We also
have the coverage curve which is comparatively easy to obtain, and the
corresponding lines of code that were covered.

Now, for computing the mutation curve, the idea is as follows. For any trivial
mutant, the time taken for detection is the time taken for covering the
corresponding program element. For any chosen mutant, the time taken for
killing is the time taken for covering its corresponding mutation along with
the time taken to kill it. Once we compute the time to kill for each mutant,
it can be plotted, and the curve of mutant detection can be obtained for any
time period.

###  V-C Redundancy

For evaluating the redundancy of mutants, we propose the following solution.
For any mutant, identify the input that kills it during fuzzing. This may be
from the _coverage seed_ collection or during later fuzzing. Next, use this
final set of inputs as a static test suite (let us call this the _final static
test suite_), and run full matrix mutation analysis using the traditional
optimizations. This will allow us to compute the minimal set of mutants using
the traditional minimal mutant computation.

###  V-D Equivalent Mutants

Once we have the final static test suite, we propose to use the _final static
test suite_ along with _species richness estimation_ by Böhme [100] for
evaluating the range of equivalent mutants. However, we note that this is yet
to be validated even for traditional mutation analysis. A second possibility
is to sample from the remaining mutants to evaluate whether the sampled mutant
is killable. We note that detecting equivalent mutants will be no different
for fuzzers than in traditional mutation analysis.

##  VI Related Work

The latest research in mutation analysis is discussed by Papadakis et al.
[103] who also discuss numerous techniques to reduce the computational
expenditure involved in traditional mutation analysis.

The survey paper by Pizzoleto et al. [104] focuses on cost reduction of
mutation analysis and suggests that one of the main areas of research in this
direction recently has been in trying to reduce the number of mutants
executed. Other options include various forms of selective mutation,
statistical sampling of mutants, clustering and then sampling mutants, finding
subsuming mutants, and so forth. Researchers have also explored various
strategies for cost reduction including higher order mutation, weak and firm
mutation [105, 86, 106, 107, 108]. Finally, another possibility is to use a
proxy for mutation score such as checked coverage [109].

Lima et al. [110] examines different strategies including different higher
order mutants for reducing the cost of execution of mutants. They found _each-
choice_ strategy was the best in this regard.

There have been numerous ideas focused on improving the efficiency of
evaluation. Some of the work in this area involves parallelization of mutation
analysis using MIMD [111] and SIMD [112] machines, in HPC systems [113], and
using Hadoop [114].

##  VII Conclusion

Mutation analysis has been relegated to the sidelines in fuzzing research.
However, we find that two thirds of the key challenges identified in fuzzing
research can potentially be addressed using mutation analysis.

At the same time, we find that mutation analysis still requires solutions to
some significant challenges before it can be used for fuzzing. Of particular
imortance is the computational cost. Mutation analysis is a costly technique
even in traditional settings with static test suites. When used for fuzzing,
most of the traditional optimization techniques can’t be used because they
assume static test suites. Further, the fuzzing itself is computationally
costly, with fuzzing campaigns on programs typically recommended to run for at
least 24 hours. Finally, the requirement of statistical confidence because of
non-determinism in fuzzing adds even more computational requirement for
successful use of mutation analysis in fuzzing.

Lack of frameworks that can do both mutation analysis and fuzzing is another
problem that discourages use of mutation analysis in fuzzing. Finally, lack of
awareness of mutation analysis may also be a factor in cybersecurity
researchers ignoring mutation analysis for fuzzer evaluation.

In this paper, we document the ways in which mutation analysis can potentially
help fuzzing research, or help the fuzzing practitioner, identify the
challenges ahead before mutation analysis can be considered a viable
alternative to bug benchmarks and coverage for fuzzer evaluation, and propose
a few possible mitigation strategies.

## References

  * [1] V. J. M. Manès, H. Han, C. Han, S. K. Cha, M. Egele, E. J. Schwartz, and M. Woo, “The art, science, and engineering of fuzzing: A survey,” _IEEE TSE_ , 2019.
  * [2] D. Babić, S. Bucur, Y. Chen, F. Ivančić, T. King, M. Kusano, C. Lemieux, L. Szekeres, and W. Wang, “Fudge: fuzz driver generation at scale,” in _ESEC/FSE_ , 2019, pp. 975–985.
  * [3] K. Ispoglou, D. Austin, V. Mohan, and M. Payer, “Fuzzgen: Automatic fuzzer generation,” in _USENIX Security Symposium)_ , 2020.
  * [4] P. Godefroid, M. Y. Levin, and D. Molnar, “Sage: Whitebox fuzzing for security testing: Sage has had a remarkable impact at microsoft.” _Queue_ , vol. 10, no. 1, pp. 20–27, 2012.
  * [5] G. Mocanu, C. Carabaş, and N. Ţăpuş, “Fuzz testing in aws firecracker hypervisor,” in _ISPDC_. IEEE, 2021, pp. 130–137.
  * [6] P. Marinescu, “Autonomous testing of services at scale,” https://engineering.fb.com/2021/10/20/developer-tools/autonomous-testing/, 2022\.
  * [7] P. Godefroid, “Fuzzing: Hack, art, and science,” _CACM_ , vol. 63, no. 2, pp. 70–76, 2020.
  * [8] Z. Y. Ding and C. L. Goues, “An empirical study of oss-fuzz bugs,” _CoRR_ , vol. abs/2103.11518, 2021. [Online]. Available: https://arxiv.org/abs/2103.11518
  * [9] “Microsoft announces new Project OneFuzz framework, an open source developer tool to find and fix bugs at scale - Microsoft Security Blog,” Nov 2021, [Online; accessed 15. Jan. 2022]. [Online]. Available: https://www.microsoft.com/security/blog/2020/09/15/microsoft-onefuzz-framework-open-source-developer-tool-fix-bugs
  * [10] M. Boehme, C. Cadar, and A. Roychoudhury, “Fuzzing: Challenges and reflections.” _IEEE Software_ , vol. 38, no. 3, pp. 79–86, 2021.
  * [11] “Fuzzing – Firefox Source Docs documentation,” https://firefox-source-docs.mozilla.org/tools/fuzzing/index.html, Jan 2022, [Online; accessed 20. Jan. 2022].
  * [12] M. Böhme and B. Falk, “Fuzzing: On the exponential cost of vulnerability discovery,” in _ESEC/FSE_. ACM, 2020\.
  * [13] A. Hazimeh, A. Herrera, and M. Payer, “Magma: A ground-truth fuzzing benchmark,” _ACM on Measurement and Analysis of Computing Systems_ , vol. 4, no. 3, pp. 1–29, 2020.
  * [14] B. Dolan-Gavitt, P. Hulin, E. Kirda, T. Leek, A. Mambretti, W. Robertson, F. Ulrich, and R. Whelan, “LAVA: Large-scale automated vulnerability addition,” in _IEEE SP_. San Jose, CA: IEEE, 2016.
  * [15] S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou, and Y. Zhou, “Bugbench: Benchmarks for evaluating bug detection tools,” in _Workshop on the evaluation of software defect detection tools_ , 2005.
  * [16] N. Lee, “Darpa’s cyber grand challenge (2014–2016),” in _Counterterrorism and Cybersecurity_. Springer, 2015, pp. 429–456.
  * [17] G. Inc., “Google fuzzer test suite,” https://github.com/google/fuzzer-test-suite.
  * [18] J. Metzman, L. Szekeres, L. Simon, R. Sprabery, and A. Arya, “Fuzzbench: an open fuzzer benchmarking platform and service,” in _ESEC/FSE_. USA: ACM, 2021, pp. 1393–1403.
  * [19] Y. Li, S. Ji, Y. Chen, S. Liang, W.-H. Lee, Y. Chen, C. Lyu, C. Wu, R. Beyah, P. Cheng _et al._ , “UNIFUZZ: A holistic and pragmatic metrics-driven platform for evaluating fuzzers,” in _USENIX Security Symposium_ , 2021\.
  * [20] S. Roy, A. Pandey, B. Dolan-Gavitt, and Y. Hu, “Bug synthesis: Challenging bug-finding tools with deep faults,” in _ESEC/FSE_. ACM, pp. 224–234.
  * [21] J. Pewny and T. Holz, “Evilcoder: Automated bug insertion,” in _ACSAC_. ACM, pp. 214–225.
  * [22] Y. Chen, R. Gopinath, A. Tadakamalla, M. D. Ernst, R. Holmes, G. Fraser, P. Ammann, and R. Just, “Revisiting the relationship between fault detection, test adequacy criteria, and test set size,” in _IEEE/ACM ASE_. IEEE, 2020.
  * [23] G. Klees, A. Ruef, B. Cooper, S. Wei, and M. Hicks, “Evaluating fuzz testing,” in _ACM SIGSAC CCS_ , 2018, pp. 2123–2138.
  * [24] J. Bundt, A. Fasano, B. Dolan-Gavitt, W. Robertson, and T. Leek, “Evaluating synthetic bugs,” in _ACM CCS_ , 2021, pp. 716–730.
  * [25] S. Neuhaus, T. Zimmermann, C. Holler, and A. Zeller, “Predicting vulnerable software components,” in _Proceedings of the 14th ACM conference on Computer and communications security_ , 2007, pp. 529–540.
  * [26] M. Gavrilov, K. Dewey, A. Groce, D. Zamanzadeh, and B. Hardekopf, “A practical, principled measure of fuzzer appeal: A preliminary study,” in _International Conference on Software Quality, Reliability and Security_ , 2020, pp. 510–517.
  * [27] R. Gopinath, C. Jensen, and A. Groce, “Mutations: How close are they to real faults?” in _ISSRE_ , Nov 2014, pp. 189–200.
  * [28] D. Paaßen, S. Surminski, M. Rodler, and L. Davi, “My fuzzer beats them all! developing a framework for fair evaluation and comparison of fuzzers,” in _European Symposium on Research in Computer Security_. Springer, 2021, pp. 173–193.
  * [29] M. Wang, J. Liang, C. Zhou, Y. Chen, Z. Wu, and Y. Jiang, “Industrial oriented evaluation of fuzzing techniques,” in _IEEE ICST_ , 2021.
  * [30] T. Tan, B. Wang, H. Zhang, G. Chen, J. Wang, Y. Tang, and X. Zhou, “A new quantitative evaluation method for fuzzing,” in _International Conference on Artificial Intelligence and Security_. Springer, 2019.
  * [31] J. Li, B. Zhao, and C. Zhang, “Fuzzing: a survey,” _Cybersecurity_ , vol. 1, no. 1, pp. 1–13, 2018.
  * [32] H. Liang, X. Pei, X. Jia, W. Shen, and J. Zhang, “Fuzzing: State of the art,” _IEEE TR_ , vol. 67, no. 3, pp. 1199–1218, 2018.
  * [33] C. Chen, B. Cui, J. Ma, R. Wu, J. Guo, and W. Liu, “A systematic review of fuzzing techniques,” _Computers & Security_, vol. 75, 2018.
  * [34] A. Groce, K. Jain, R. van Tonder, G. Tulajappa, and C. L. Goues, “Looking for lacunae in bitcoin core’s fuzzing efforts,” in _International Conference on Software Engineering_ , 2022, accepted for publication.
  * [35] R. Gopinath and A. Zeller, “Building fast fuzzers,” _CoRR_ , vol. abs/1911.07707, 2019. [Online]. Available: http://arxiv.org/abs/1911.07707
  * [36] P. Srivastava and M. Payer, “Gramatron: Effective grammar-aware fuzzing,” in _ISSTA_ , ser. ISSTA 2021. New York, NY, USA: Association for Computing Machinery, 2021, p. 244–256.
  * [37] M. Zalewski, “American fuzzy lop (2.52 b),” https://afl-1.readthedocs.io/en/latest/fuzzing.html, 2019.
  * [38] V.-T. Pham, M. Böhme, A. E. Santosa, A. R. Caciulescu, and A. Roychoudhury, “Smart greybox fuzzing,” _IEEE TSE_ , 2019.
  * [39] B. P. Miller, L. Fredriksen, and B. So, “An empirical study of the reliability of unix utilities,” _Communications of the ACM_ , vol. 33, no. 12, pp. 32–44, 1990.
  * [40] Y. K. Malaiya, “Antirandom testing: Getting the most out of black-box testing,” in _ISSRE_. IEEE, 1995, pp. 86–95.
  * [41] R. Gopinath, B. Bendrissou, B. Mathis, and A. Zeller, “Fuzzing with fast failure feedback,” _CoRR_ , vol. abs/2012.13516, 2020. [Online]. Available: https://arxiv.org/abs/2012.13516
  * [42] E. T. Barr, M. Harman, P. McMinn, M. Shahbaz, and S. Yoo, “The oracle problem in software testing: A survey,” _IEEE TSE_ , vol. 41, 2014.
  * [43] P. A. Nardi and E. F. Damasceno, “A survey on test oracles,” https://revista.univem.edu.br/jadi/article/download/1034/393/0, 2015.
  * [44] K. Claessen and J. Hughes, “Quickcheck: a lightweight tool for random testing of haskell programs,” _ACM SIGPLAN Notices_ , vol. 46, no. 4, pp. 53–64, 2011.
  * [45] P. Goodman and A. Groce, “DeepState: Symbolic unit testing for C and C++,” in _NDSS Workshop on Binary Analysis Research_ , 2018.
  * [46] D. Song, J. Lettner, P. Rajasekaran, Y. Na, S. Volckaert, P. Larsen, and M. Franz, “Sok: sanitizing for security,” in _2019 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2019, pp. 1275–1295.
  * [47] Y. Jeon, W. Han, N. Burow, and M. Payer, “Fuzzan: Efficient sanitizer metadata design for fuzzing,” in _USENIX Annual Technical Conference_. USENIX Association, Jul. 2020, pp. 249–263.
  * [48] C. Courbet, “Nsan: A floating-point numerical sanitizer,” in _30th ACM SIGPLAN International Conference on Compiler Construction_ , ser. CC 2021\. New York, NY, USA: Association for Computing Machinery, 2021, p. 83–93. [Online]. Available: https://doi.org/10.1145/3446804.3446848
  * [49] W. M. McKeeman, “Differential testing for software,” _Digital Technical Journal_ , vol. 10, no. 1, pp. 100–107, 1998.
  * [50] E. J. Weyuker, “On testing non-testable programs,” _The Computer Journal_ , vol. 25, no. 4, pp. 465–470, 1982.
  * [51] M. D. Davis and E. J. Weyuker, “Pseudo-oracles for non-testable programs,” in _ACM Conference_ , 1981, pp. 254–257.
  * [52] R. B. Evans and A. Savoia, “Differential testing: a new approach to change detection,” in _ESEC/FSE_ , 2007, pp. 549–552.
  * [53] G. Fraser and A. Arcuri, “Evosuite: automatic test suite generation for object-oriented software,” in _ESEC/FSE_ , 2011, pp. 416–419.
  * [54] T. Y. Chen, F.-C. Kuo, W. Ma, W. Susilo, D. Towey, J. Voas, and Z. Q. Zhou, “Metamorphic testing for cybersecurity,” _Computer_ , 2016.
  * [55] S. Segura and Z. Q. Zhou, “Metamorphic testing 20 years later: A hands-on introduction,” in _ICSE_ , 2018, pp. 538–539.
  * [56] Z. Q. Zhou, D. Huang, T. Tse, Z. Yang, H. Huang, and T. Chen, “Metamorphic testing and its applications,” in _ISFST 2004_. Software Engineers Association Xian, China, 2004, pp. 346–351.
  * [57] S. Segura, G. Fraser, A. B. Sanchez, and A. Ruiz-Cortés, “A survey on metamorphic testing,” _IEEE TSE_ , vol. 42, no. 9, 2016.
  * [58] A. Carzaniga, A. Goffi, A. Gorla, A. Mattavelli, and M. Pezzè, “Cross-checking oracles from intrinsic software redundancy,” in _ICSE_ , 2014.
  * [59] M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, and C. Xiao, “The daikon system for dynamic detection of likely invariants,” _Science of computer programming_ , vol. 69, 2007.
  * [60] A. J. Offutt, “Investigations of the software testing coupling effect,” _ACM TOSEM_ , vol. 1, no. 1, pp. 5–20, 1992.
  * [61] K. H. T. Wah, “A theoretical study of fault coupling,” _Software testing, verification and reliability_ , vol. 10, no. 1, pp. 3–45, 2000.
  * [62] ——, “Theoretical insights into the coupling effect,” in _Mutation testing for the new century_. USA: Springer, 2001, pp. 62–70.
  * [63] ——, “An analysis of the coupling effect i: single test data,” _Science of Computer Programming_ , vol. 48, no. 2-3, pp. 119–161, 2003.
  * [64] R. Gopinath, C. Jensen, and A. Groce, “The theory of composite faults,” in _ICSTW_ , IEEE. USA: IEEE, 2017, pp. 47–57.
  * [65] R. Just, D. Jalali, L. Inozemtseva, M. D. Ernst, R. Holmes, and G. Fraser, “Are mutants a valid substitute for real faults in software testing?” in _ESEC/FSE_ , 2014, pp. 654–665.
  * [66] G. Petrović, M. Ivanković, G. Fraser, and R. Just, “Does mutation testing improve testing practices?” in _ICSE_. IEEE, 2021, pp. 910–921.
  * [67] T. T. Chekam, M. Papadakis, Y. Le Traon, and M. Harman, “An empirical study on mutation, statement and branch coverage fault revelation that avoids the unreliable clean program assumption,” in _IEEE/ACM ICSE_. IEEE, 2017, pp. 597–608.
  * [68] A. Groce, I. Ahmed, J. Feist, G. Grieco, J. Gesi, M. Meidani, and Q. H. Chen, “Evaluating and improving static analysis tools via differential mutation analysis,” in _QRS_ , 2021.
  * [69] H. Peng, Y. Shoshitaishvili, and M. Payer, “T-Fuzz: Fuzzing by program transformation,” in _2018 IEEE Symposium on Security and Privacy (SP)_ , 2018, pp. 697–710.
  * [70] W. Visser, “What makes killing a mutant hard,” in _ASE_ , 2016.
  * [71] S. Shamshiri, R. Just, J. M. Rojas, G. Fraser, P. McMinn, and A. Arcuri, “Do automatically generated unit tests find real faults? an empirical study of effectiveness and challenges,” in _IEEE/ACM ASE_ , 2015.
  * [72] Y. Jia and M. Harman, “Constructing subtle faults using higher order mutation testing,” in _2008 Eighth IEEE International Working Conference on Source Code Analysis and Manipulation_ , IEEE. USA: IEEE, 2008, pp. 249–258.
  * [73] M. Harman, Y. Jia, and W. B. Langdon, “A manifesto for higher order mutation testing,” in _ICSTW_. IEEE, 2010, pp. 80–89.
  * [74] D. R. Kuhn, D. R. Wallace, and A. M. Gallo, “Software fault interactions and implications for software testing,” _IEEE transactions on software engineering_ , vol. 30, no. 6, pp. 418–421, 2004.
  * [75] T. Tao, _An introduction to measure theory_. American Mathematical Society Providence, RI, 2011, vol. 126.
  * [76] A. Groce, J. Holmes, D. Marinov, A. Shi, and L. Zhang, “An extensible, regular-expression-based tool for multi-language mutant generation,” in _ICSE_. IEEE, 2018.
  * [77] J. H. Andrews, L. C. Briand, and Y. Labiche, “Is mutation an appropriate tool for testing experiments?” in _ICSE_ , 2005, pp. 402–411.
  * [78] J. H. Andrews, L. C. Briand, Y. Labiche, and A. S. Namin, “Using mutation analysis for assessing and comparing testing coverage criteria,” _IEEE TSE_ , vol. 32, no. 8, pp. 608–624, 2006.
  * [79] I. Ahmed, R. Gopinath, C. Brindescu, A. Groce, and C. Jensen, “Can testedness be effectively measured,” in _ACM SIGSOFT International Symposium on the Foundations of Software Engineering_. ACM, 2016.
  * [80] M. Papadakis, D. Shin, S. Yoo, and D.-H. Bae, “Are mutation scores correlated with real fault detection? a large scale empirical study on the relationship between mutants and real faults,” in _IEEE/ACM ICSE_ , 2018, pp. 537–548.
  * [81] A. Parsai and S. Demeyer, _Mutant Density: A Measure of Fault-Sensitive Complexity_. New York, NY, USA: Association for Computing Machinery, 2020, p. 742–745.
  * [82] C. Pacheco and M. D. Ernst, “Randoop: feedback-directed random testing for java,” in _ACM SIGPLAN conference on Object-oriented programming systems and applications companion_ , 2007, pp. 815–816.
  * [83] V. N. Fleyshgakker and S. N. Weiss, “Efficient mutation analysis: A new approach,” in _ISSTA_ , 1994.
  * [84] D. Schuler and A. Zeller, “Javalanche: Efficient mutation testing for java,” in _ESEC/FSE_ , 2009, pp. 297–298.
  * [85] P. R. Mateo and M. P. Usaola, “Reducing mutation costs through uncovered mutants,” _STVR_ , vol. 25, no. 5-7, pp. 464–489, 2015.
  * [86] W. E. Howden, “Weak mutation testing and completeness of test sets,” _IEEE TSE_ , no. 4, pp. 371–379, 1982.
  * [87] R. Just, M. D. Ernst, and G. Fraser, “Efficient mutation analysis by propagating and partitioning infected execution states,” in _ISSTA_ , 2014\.
  * [88] S. Tokumoto, H. Yoshida, K. Sakamoto, and S. Honiden, “Muvm: Higher order mutation analysis virtual machine for c,” in _ICST_. IEEE, 2016.
  * [89] R. Gopinath, C. Jensen, and A. Groce, “Topsy-turvy: a smarter and faster parallelization of mutation analysis,” in _38th International Conference on Software Engineering Companion_ , 2016, pp. 740–743.
  * [90] B. Wang, Y. Xiong, Y. Shi, L. Zhang, and D. Hao, “Faster mutation analysis via equivalence modulo states,” in _ISSTA_ , 2017.
  * [91] A. Ghanbari and A. Marcus, “Toward speeding up mutation analysis by memoizing expensive methods,” in _ICSE-NIER_. IEEE, 2021.
  * [92] R. H. Untch, A. J. Offutt, and M. J. Harrold, “Mutation analysis using mutant schemata,” in _ISSTA_ , 1993, pp. 139–148.
  * [93] P. R. Mateo and M. P. Usaola, “Mutant execution cost reduction: Through music (mutant schema improved with extra code),” in _IEEE ICST_. IEEE, 2012, pp. 664–672.
  * [94] R. Just, G. M. Kapfhammer, and F. Schweiggert, “Using conditional mutation to increase the efficiency of mutation analysis,” in _International Workshop on Automation of Software Test_ , 2011, pp. 50–56.
  * [95] L. Chen and L. Zhang, “Speeding up mutation testing via regression test selection: An extensive study,” in _IEEE ICST_. IEEE, 2018.
  * [96] L. Zhang, D. Marinov, and S. Khurshid, “Faster mutation testing inspired by test prioritization and reduction,” in _ISSTA_ , 2013.
  * [97] Y. Jia and M. Harman, “An analysis and survey of the development of mutation testing,” _IEEE TSE_ , vol. 37, no. 5, pp. 649–678, 2010.
  * [98] B. J. Grün, D. Schuler, and A. Zeller, “The impact of equivalent mutants,” in _ICSTW_. IEEE, 2009, pp. 192–199.
  * [99] X. Yao, M. Harman, and Y. Jia, “A study of equivalent and stubborn mutation operators using human analysis of equivalence,” in _36th International Conference on Software Engineering_ , ser. ICSE 2014. New York, NY, USA: ACM, 2014, pp. 919–930. [Online]. Available: http://doi.acm.org/10.1145/2568225.2568265
  * [100] M. Böhme, “Assurances in software testing: A roadmap,” in _ICSE-NIER_. IEEE, 2019, pp. 5–8.
  * [101] R. Gopinath, I. Ahmed, M. A. Alipour, C. Jensen, and A. Groce, “Mutation reduction strategies considered harmful,” _IEEE Transactions on Reliability_ , vol. 66, no. 3, pp. 854–874, 2017.
  * [102] R. Gopinath, B. Mathis, and A. Zeller, “If you can’t kill a supermutant, you have a problem,” in _ICSTW_ , IEEE. USA: IEEE, 2018, pp. 18–24.
  * [103] M. Papadakis, M. Kintis, J. Zhang, Y. Jia, Y. Le Traon, and M. Harman, “Mutation testing advances: an analysis and survey,” in _Advances in Computers_. Elsevier, 2019, vol. 112, pp. 275–378.
  * [104] A. V. Pizzoleto, F. C. Ferrari, J. Offutt, L. Fernandes, and M. Ribeiro, “A systematic literature review of techniques and metrics to reduce the cost of mutation testing,” _JSS_ , vol. 157, p. 110388, 2019.
  * [105] A. J. Offutt, G. Rothermel, and C. Zapf, “An experimental evaluation of selective mutation,” in _ICSE_. IEEE, 1993, pp. 100–107.
  * [106] A. J. Offutt and S. D. Lee, “How strong is weak mutation?” in _ICST_ , 1991, pp. 200–213.
  * [107] ——, “An empirical evaluation of weak mutation,” _IEEE TSE_ , vol. 20, no. 5, pp. 337–344, 1994.
  * [108] V. H. Durelli, J. Offutt, and M. E. Delamaro, “Toward harnessing high-level language virtual machines for further speeding up weak mutation testing,” in _ICST_. IEEE, 2012.
  * [109] D. Schuler and A. Zeller, “Checked coverage: an indicator for oracle quality,” _STVR_ , vol. 23, no. 7, 2013.
  * [110] J. A. P. Lima, G. Guizzo, S. R. Vergilio, A. P. Silva, H. L. J. Filho, and H. V. Ehrenfried, “Evaluating different strategies for reduction of mutation testing costs,” in _Brazilian Symposium on Systematic and Automated Software Testing_ , 2016, pp. 1–10.
  * [111] A. J. Offutt, R. P. Pargas, S. V. Fichter, and P. K. Khambekar, “Mutation testing of software using mimd computer.” in _ICPP_ , 1992.
  * [112] E. W. Krauser, A. P. Mathur, and V. J. Rego, “High performance software testing on simd machines,” _IEEE TSE_ , vol. 17, no. 5, 1991.
  * [113] P. C. Cañizares, M. G. Merayo, and A. Núñez, “Eminent: Embarrassingly parallel mutation testing,” _Procedia Computer Science_ , 2016\.
  * [114] I. Saleh and K. Nagi, “Hadoopmutator: A cloud-based mutation testing framework,” in _ICSR_. Springer, 2015\.