Guiding Greybox Fuzzing with Mutation Testing

  Vasudev Vikram            Isabella Laybourn                                                  Ao Li

Carnegie Mellon University Carnegie Mellon University Carnegie Mellon University Pittsburgh, PA, USA Pittsburgh, PA, USA Pittsburgh, PA, USA vasumv@cmu.edu ilaybour@andrew.cmu.edu aoli@cmu.edu

   Nicole Nair                Kelton OBrien                                                Rafaello Sanna
Swarthmore College       University of Minnesota                                      University of Rochester

Swarthmore, PA, USA Minneapolis, MN, USA Rochester, NY, USA nnair1@swarthmore.edu obri0707@umn.edu rsanna@u.rochester.edu Rohan Padhye Carnegie Mellon University Pittsburgh, PA, USA rohanpadhye@cmu.edu ABSTRACT ACM Reference Format: Greybox fuzzing and mutation testing are two popular but mostly Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, independent fields of software testing research that have so far Rafaello Sanna, and Rohan Padhye. 2023. Guiding Greybox Fuzzing with had limited overlap. Greybox fuzzing, generally geared towards Mutation Testing. In Proceedings of the 32nd ACM SIGSOFT International searching for new bugs, predominantly uses code coverage for Symposium on Software Testing and Analysis (ISSTA ’23), July 17–21, 2023, selecting inputs to save. Mutation testing is primarily used as a Seattle, WA, USA. ACM, New York, NY, USA, 13 pages. https://doi.org/10. stronger alternative to code coverage in assessing the quality of 1145/3597926.3598107 regression tests; the idea is to evaluate tests for their ability to 1 identify artificially injected faults in the target program. But what INTRODUCTION if we wanted to use greybox fuzzing to synthesize high-quality Greybox fuzzing [9, 49, 52, 81] and coverage-guided property test- regression tests? ing [44, 58] have become increasingly popular for automated testing. In this paper, we develop and evaluate Mu2, a Java-based frame- Their key idea is to evolve a corpus of test inputs via an evolutionary work for incorporating mutation analysis in the greybox fuzzing search that maximizes code coverage: in each iteration, a new input loop, with the goal of producing a test-input corpus with a high mu- is synthesized by randomly mutating an existing input from the cor- tation score. Mu2 makes use of a differential oracle for identifying pus. The mutated input is added to the corpus if the corresponding inputs that exercise interesting program behavior without causing execution of the test program increases code coverage. crashes. This paper describes several dynamic optimizations imple- Fuzzing is traditionally used to discover inputs that crash pro- mented in Mu2 to overcome the high cost of performing mutation grams and reveal security vulnerabilities [5, 11, 14, 20, 25, 42, 50, analysis with every fuzzer-generated input. These optimizations 54, 59, 68]. In the absence of new bugs, fuzzers are evaluated based introduce trade-offs in fuzzing throughput and mutation killing on code coverage achieved during the fuzzing campaign [10, 48]. ability, which we evaluate empirically on five real-world Java bench- However, in the vast majority of fuzzing research, the end goal is marks. Overall, variants of Mu2 are able to synthesize test-input to find bugs in the moment [42]; not much attention is paid to the corpora with a higher mutation score than state-of-the-art Java inputs saved along the way. fuzzer Zest. In this paper, we explicitly focus on the quality of the test-input corpus produced at the end of a fuzzing campaign. Such a corpus CCS CONCEPTS can be used for continuous regression testing during subsequent • Software and its engineering → Software testing and debug- program development. This practice is recommended by Google’s ging. OSS-Fuzz [28], and is already adopted by some mature projects. For example, in SQLite, “Historical test cases from AFL, OSS Fuzz, and KEYWORDS dbsqlfuzz are collected [...] and then rerun by the fuzzcheck utility fuzz testing, mutation testing, test generation program whenever one runs make test” [71]. Similarly, OpenSSL uses several distinct fuzzer-generated corpora and their correspond- Permission to make digital or hard copies of part or all of this work for personal or ing fuzz drivers for continuous testing [72]. Even though these test classroom use is granted without fee provided that copies are not made or distributed corpora are used for regression testing, the only metric being tar- for profit or commercial advantage and that copies bear this notice and the full citation This work is licensed under a Creative Commons Attribution 4.0 Interna- geted by conventional greybox fuzzers is code coverage. However, on the first page. Copyrights for third-party components of this work must be honored. tional License. coverage alone is not the necessarily the strongest predictor of fault For all other uses, contact the owner/author(s). ©ISSTA ’23, July 17–21, 2023, Seattle, WA, USA detection ability [15, 36]. 2023 Copyright held by the owner/author(s). Now, the technique of mutation testing [19], which evaluates the ACM ISBN 979-8-4007-0221-1/23/07. https://doi.org/10.1145/3597926.3598107 ability of tests to catch artificially injected bugs (a.k.a. mutation

929

ISSTA ’23, July 17–21, 2023, Seale, WA, USA Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye

Seeds (Program Mu2 employing different strategies for improving performance. Our Input ? Mutants) Input Input Pick Input Random Program’ combined evaluation represents 21,600 CPU-hours (2.5 CPU-years) Input Mutation Input’ Execute Program’ Program’ of fuzzing campaigns. Add Our results indicate: (1) an optimized version of Mu2 has an Input’ overall improvement of up to 20% in mutation scores across five benchmarks (5% increase on average); (2) mutation-analysis feed- Yes Execution feedback back generates test-input corpora with higher reliability of killing Save? nontrivial mutants compared to coverage-only feedback; (3) the New mutants 𝑚𝑢𝑡𝑎𝑡𝑖𝑜𝑛_𝑠𝑐𝑜𝑟𝑒 differential testing oracle is significantly valuable to Mu2, detecting killed? No 30% more mutants on average than a conventional fuzzing oracle; To summarize, this paper makes the following contributions: (1) We investigate the various challenges of combining muta- Figure 1: A mutation-analysis-guided fuzzing loop. Each tion testing and greybox fuzzing, and propose solution ap- fuzzer-generated input is run through a set of program mu- proaches to include in our framework. tants to compute a mutation score. Inputs are saved to the (2) We incorporate differential testing as an oracle for mutation corpus if they improve mutation score. testing in the fuzzing loop and find that it significantly im- proves the strength of the fuzzing oracle. analysis), has shown promise as an adequacy criteria for improving (3) We employ multiple sound performance optimizations that test-suite effectiveness [15, 39, 64]. A test is said to kill a program enable mutation analysis to run in the fuzzing loop, and mutant if it fails when executed on the mutant, whereas mutants propose aggressive optimizations that are able to scale Mu2 that fail no tests are said to survive. A goal of mutation testing is to to larger programs. produce a test corpus that has a high mutation score, defined as the (4) We present an empirical evaluation of Mu2 on 5 real-world fraction of all mutants that are killed by the test suite. A natural Java benchmarks, with Zest [59] as a baseline. question thus arises: can we use mutation scores to guide the fuzzer? (5) We open-source Mu2 for use by practitioners and to enable In this paper, we develop and evaluate a framework for incor- reproduction and extension by researchers. porating mutation analysis in the fuzzing loop, building on our 2 previous work which first proposed the approach [46]. The idea is BACKGROUND as follows (see Fig. 1): after a new input is synthesized by a fuzzer 2.1 Greybox Fuzzing and Corpus Generation via random mutation of a previously saved input, it is evaluated by Coverage-guided greybox fuzzing (CGF) is a technique for auto- executing a set of mutants of the program under test. If the new in- matic test-input generation using lightweight program instrumenta- put kills any previously surviving program mutant, then it is added tion. It was first popularized by open-source tools such as AFL [81] to the corpus. In this process, we distinguish between input muta- and libFuzzer [49], but has since been heavily studied and variously tions (e.g., randomly setting input bits or fields to zero) and program extended in academic research [5, 9, 14, 20, 25, 44, 50, 52, 58, 59]. mutations (e.g., replacing the expression a+b with a-b in the tar- Algorithm 1 describes the basic greybox fuzzing algorithm, with get’s source code). Our Java-based implementation, called Mu2—for many details elided. First, a corpus of test inputs is initialized with a Mutation-Based Greybox Fuzzing + Mutation Testing—incorporates set of one or more seed inputs (Line 2), which could be user-provided program mutations from the popular PIT toolkit [17] into a custom or randomly generated. Then, in each iteration of the fuzzing loop guidance in the JQF [58] greybox fuzzing framework. Mu2 is open (Line 3), a new input is synthesized by first picking an existing source and available at: https://github.com/cmu-pasta/mu2. input 𝑥 from the corpus (Line 4) and then performing random mu- This paper details two main aspects of Mu2’s design. First, with tations to produce 𝑥 ′ (Line 5). The heuristics to sample an input a conventional fuzzing oracle that only identifies program crashes (PickInput) vary, and often use some sort of energy schedule [9]. or aborts, many inputs will be discarded for not killing any mu- Some inputs may also be marked as favored, and receive higher tant even though they exercise interesting program functionality. energy than other inputs. The random mutations performed on 𝑥 to For mutation testing to be useful, we need a stronger test oracle. get 𝑥 ′ (MutateInput) also vary depending on the known format of Mu2 incorporates the idea of differential mutation testing, which inputs (e.g., bitflips for binary data or random keyword insertion for validates the output of program execution. Second, evaluating each text files). Structure-aware fuzzing tools [4, 44, 59, 65, 76] perform fuzzer-generated input on the set of all program mutants is pro- mutations that preserve the syntax or type safety of inputs, e.g. by hibitively expensive, thereby reducing fuzzing throughput. Mu2 mutating parse trees using a grammar or by mutating pseudoran- prunes the set of mutants to run at each fuzzing iteration using dom choices backing a Quickcheck-like [16] generator function. dynamic analysis of the original program’s execution in two ways: The program under test 𝑃 is then executed with the new input 𝑥 ′, (a) sound optimizations that prune mutants which cannot be killed using lightweight instrumentation to collect code coverage during by a given input, and (b) aggressive optimizations that select only a execution. The function coverage referenced in Algorithm 1 re- bounded subset of candidate mutants to run in each iteration. turns a set of program locations executed when processing an input. We evaluate Mu2 on five real-world Java targets using state-of- If the run of 𝑥 ′ causes new code to be covered (Line 8), then 𝑥 ′ is the-art greybox fuzzer Zest [59], which is also built on top of the JQF saved to the corpus (Line 9); thus, 𝑥 ′ may be used as the basis for framework, as a baseline. We also empirically evaluate 7 variants of further input mutation in subsequent iterations of the fuzzing loop.

                                                                          930

    Guiding Greybox Fuzzing with Mutation Testing                                                               ISSTA ’23, July 17–21, 2023, Seale, WA, USA

Algorithm 1 Coverage-guided greybox fuzzing 𝑃 (𝑥 ) = 𝑃 ′(𝑥 ). Similar to code coverage—where 100% may not be 1: procedure CGF(Program 𝑃 , Set of inputs seeds, Budget 𝑇 ) achievable due to unreachable code—the best use of the adequacy 2: corpus ← seeds ⊲ Initialize saved inputs score is as a relative measurement rather than an absolute one. 3: repeat ⊲ Fuzzing loop One of the most mature and actively developed mutation testing 4: 𝑥 ← PickInput(corpus) ⊲ Sample using heuristics frameworks, PIT [17], targets Java programs by mutating JVM 5: 𝑥′ ← MutateInput(𝑥 ) ⊲ Synthesize new input bytecode. PIT’s default mutation operators include: 6:7: if running 𝑃 (𝑥′ ) leads to a crash then • Conditional boundary mutator (e.g., a<b to a<=b)) coverage(𝑃, 𝑥′ ) ⊈ 𝑥 ∈corpus coverage(𝑃, 𝑥 ) then 8: if raise 𝑥′ Ð ⊲ Bug found! • Increments mutator (e.g., a++ to a--) 9: corpus ← corpus ∪ 𝑥′ •• Invert negatives (e.g., -a to a) 10: until budget 𝑇 Math mutators (e.g., a+b to a*b) 11: return corpus ⊲ Final corpus • Negate conditionals (e.g., a==b to a!=b) • Return values mutator (e.g., replacing operands in return statements with a constant such as null, 0, 1, false, etc. If the execution of any synthesized input 𝑥 ′ causes the program to depending on type). crash, then a bug is reported (Line 7). The fuzzing loop continues 3 until a user-provided resource budget 𝑇 runs out (Line 10), where MUTATION-ANALYSIS-GUIDED FUZZING this budget may be in terms of the number of fuzzing trials (i.e., 3.1 Problem Statement and Scope iterations of the fuzzing loop) or in terms of wall-clock time. The In this paper, we focus on the following problem: corpus of fuzzer-synthesized test inputs is finally returned (Line 11) Can we use mutation analysis to guide greybox fuzzing in order and may be used either as a regression test suite, for seeding future to synthesize a test-input corpus with high mutation score? fuzzing campaigns, or for other applications [28, 55, 71, 72, 75]. The quality of the final test-input corpus is often evaluated using code Recently, Gopinath et al. [31] have identified and discussed sev- coverage [10, 42], though mutation scores—which we describe in eral challenges of combining mutation analysis with fuzzing, in- the next section—have also been used [75]. cluding (1) the strength of oracles used by the fuzzer, (2) the compu- 2.2 Mutation Testing tational expense of performing mutation analysis, (3) dealing with equivalent mutants, and (4) the lack of mutation testing frameworks Mutation testing (also known as a mutation analysis) is a method- that focus on fuzzers. We directly address such challenges in this ology for assessing the adequacy of a set of tests using artificially paper. Oracles are discussed in Section 3.3 and performance con- injected “bugs”, or program mutants [19, 37]. In assessing test ade- cerns in Section 3.4. Our evaluation is not dependent on identifying quacy [27], we are given a program 𝑃 and a suite of passing tests equivalent mutants, since we only care about relative mutation 𝑋 . The goal is to evaluate the quality of 𝑋 by computing a score scores (higher=better) rather than the exact number of mutants that grows monotonically [79] with additions to the set 𝑋 . Code killed by a test-input corpus. Section 3.4.2 deals with reducing the coverage is an example of a test adequacy criteria. performance impact of equivalent mutations. In mutation testing, a set of program mutants, say Mutants(𝑃 ), is first generated. Each mutant 𝑃 ′ ∈ Mutants(𝑃 ) is a program that Scope. Since there is a vast amount of literature on the many differs from 𝑃 in a very small way. Most commonly, mutations are variables involved in mutation analysis, as surveyed by Papadakis replacements of program expressions. For example, an expression et al. [63], we restrict ourselves in this paper to investigating only a+b at line 42 in 𝑃 may be replaced with the expression a-b. We the aspects of combining mutation analysis with greybox fuzzing. can use the notation ⟨𝑃, a+b, a-b, 42⟩ to refer to this mutation. For In particular, we (1) work with the assumption that a high muta- purposes of this paper, we use the notation: tion score is a desirable property of a test-input corpus used for 𝑃 ′ = ⟨𝑃, 𝑒, 𝑒′, 𝑛⟩ regression testing, referring the reader to several empirical stud- ies examining the relationship between mutation scores and real to refer to a program mutant 𝑃 ′ as a modification of program 𝑃 faults [2, 12, 15, 32, 39, 41, 64], and (2) directly use the default set of where expression 𝑒 is replaced with 𝑒′ at program location 𝑛. The mutation operators provided by PIT (ref. Section 2.2), which have main idea is that a program mutation simulates a simple program- been chosen based on several empirical studies of effectiveness, mer error or an artificially injected “bug”. sufficiency, and to align with developer expectations [1, 17, 45, 57]. The test suite 𝑋 is then run on each mutant 𝑃 ′. If some test 𝑥 ∈ 𝑋 fails when run on mutant 𝑃 ′, then the mutant 𝑃 ′ is said to be killed, 3.2 The Mu2 Framework which we denote as Kills(𝑃 ′, 𝑥). If the test suite 𝑋 still passes, then To address our problem statement, we present the mutation- the mutant 𝑃 ′ is said to survive. analysis-guided greybox fuzzing technique in Algorithm 2. This Ideally, we want our tests to be able to identify “bugs” and so we is an extension of Alg. 1, with changes highlighted in grey. The hope to have tests that fail on each mutant 𝑃 ′. So, the adequacy of key additions of this algorithm are in evaluating whether a fuzzer- test suite 𝑋 is defined by the mutation score, which is computed as generated input 𝑥 ′ should be saved to the corpus. The function the fraction of mutants killed: | {𝑃′∈Mutants| (𝑃 ) | ∃𝑥 ∈𝑋:kills(𝑃′,𝑥 ) } | . Mutants(𝑃 ) | ProgMuts2Run (Line 8) returns a set of program mutants to eval- In general, a mutation score of 100% is rarely achievable because uate with input 𝑥 ′. For now, assume it to return Mutants(P) as some mutants 𝑃 ′ may actually be equivalent to 𝑃 —that is, ∀𝑥 : defined in Section 2.2, though we will refine this in Section 3.4.2.

    931

ISSTA ’23, July 17–21, 2023, Seale, WA, USA Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye

Algorithm 2 Mutation-analysis-guided fuzzing. Changes to Alg. 1 1 class Sort { are highlighted. 2 static int[] insertionSort(int[] arr) { 1: procedure Mu2 (Program 𝑃 , Set of inputs seeds, Budget 𝑇 ) 3 for (int j = 1; j < arr.length; j++) { 2: corpus ← seeds 4 int key = arr[j], i = j-1; 5 while (i >= 0 && // P'2 changes >= to > 3: repeat 6 key < arr[i]) { 4: 𝑥 ← PickInput(corpus) 7 arr[i+1] = arr[i]; // P'3 sets RHS to 1 5: 𝑥′ ← MutateInput(𝑥Ð) 8 i = i-1; // P'4 removes -1 6: if coverage(𝑃, 𝑥′ ) ⊈ 𝑥 ∈corpus coverage(𝑃, 𝑥 ) then 9 } 7: corpus ← corpus ∪ 𝑥′ 10 arr[i+1] = key; // P'1 removes +1 8: for all 𝑃 ′ ∈ ProgMuts2Run(𝑃, corpus, 𝑥′ ) do 11 }}} return arr; 9: if kills(𝑃 ′, 𝑥′ ) ∧ 𝑃 ′ ∉ killed(𝑃, corpus) then 12 10: corpus ← corpus ∪ 𝑥′ Figure 2: Java program that implements insertion sort, anno- 11: until budget 𝑇 12: return corpus tated with four sample program mutants. 13: function killed(Program 𝑃 , Set of inputs X) 14: return {𝑃 ′ | 𝑃 ′ ∈ Mutants(𝑃 ) ∧ ∃𝑥 ∈ X : kills(𝑃 ′, 𝑥 ) } defined in Figure 2 and the following test method, which is written in the property-testing style using JQF’s @Fuzz annotation: 1 @Fuzz // Inputs generated using greybox fuzzing We then determine whether the input 𝑥 ′ is the first input to kill 2 void fuzzInsertionSort(int[] input) { some mutant 𝑃 ′. If 𝑃 ′ is killed by 𝑥 ′ and 𝑃 ′ has not previously been 3 } assert(isSorted(Sort.insertionSort(input))); 4 killed by any input in the corpus (Lines 9 and 14), then we add 𝑥 ′ to For Mu2, we could use this property test as an oracle. Con- the corpus (Line 10). Broadly, this algorithm saves fuzzer-generated sider the following examples, using the notation introduced in inputs if they increase either code coverage or mutation score. Addi- Section 2.2: executing mutant 𝑃 ′ = ⟨Sort, i+1, i, 10⟩ with tionally, inputs that increase mutation score are marked as favored, 1 giving them more energy to be picked for fuzzing (Line 4). As be- input array 𝑥 = [3, 2, 1] would result in an uncaught fore, the final corpus of fuzzer-generated inputs is returned as the IndexOutOfBoundsException (-1) on line 10, triggering result (Line 12). a failure via the implicit oracle. Additionally, executing 𝑃2′ = We have implemented Algorithm 2 for fuzzing Java programs by ⟨Sort, i>=0, i>0, 5⟩ with 𝑥 would result in an assertion failure in integrating PIT [17] into JQF [58]. We call this system Mu2, since it the property test because the result of 𝑃2′(𝑥 ) would be the array [3, combines Mutation-based Greybox Fuzzing with Mutation Testing. 1, 2], which is not sorted. So, both mutants 𝑃1′ and 𝑃2′ would get We chose PIT and JQF because of their maturity, extensibility, killed by the fuzzer if it discovers such an input. and their common target platform. As described in Section 2.2, PIT Unfortunately, the property test is not a complete oracle in that is an actively developed mutation testing framework that operates it does not fully specify the expected behavior of the sort function. on JVM bytecode. The JQF framework [58] was originally designed Consider a third mutant 𝑃3′ = ⟨Sort, arr[i], 1, 7⟩, which assigns for coverage-guided property-based testing, which is a structure- a constant to every array element at line 7. This is clearly a bug in aware variant of greybox fuzzing (ref. Section 2.1) and instruments insertion sort, yet the output is always sorted. For example, when= 𝑥 JVM bytecode for collecting code coverage. JQF also has a highly [3, 2, 1], the result of 𝑃3′(𝑥 ) is [1, 1, 1]. Such a mutant extensible design for creating pluggable guidances, which supports would incorrectly survive on any input the fuzzer generates. rapid prototyping of new fuzzing algorithms [43, 55, 56, 59, 69, 75, Writing a complete oracle for testing insertion sort is possible, 83]. but quite cumbersome. In general, this is a hard problem [6]. For In Mu2, Mutants(𝑃 ) includes all of PIT’s default expression many applications, a complete oracle would need to be as complex mutation operators (ref. Sections 2.2 and 3.1). For heuristics such as (or in some cases exactly the same) as the original program itself. PickInput and MutateInput, Mu2 reuses the logic and code from In Mu2, we use the well-known concept of differential testing Zest [59], which we also use as a baseline for evaluation (Section 4). to define our oracle. In differential testing [21, 53], different im- plementations of a program that are expected to satisfy the same 3.3 Oracle: Differential Mutation Testing specification are executed on a single input, and their results are compared to identify discrepancies. In Mu2, our different "imple- One challenge of mutation-analysis-guided fuzzing is determining mentations" are the original program and program mutants; any whether a program mutant is killed by a particular input. This discrepancy between the original program output and a mutant’s corresponds to the kills function invoked in line 9 of Algorithm 2. output leads to that mutant being killed. In mutation testing, a program mutant 𝑃 ′ is considered killed if To support the comparison of outputs, we create a differential any test in the test suite fails. The logic that determines whether a mutation testing framework. This allows for (1) output values to test passes or fails is known as the test oracle. be returned from a fuzzing driver (as opposed to the void returns Greybox fuzzing generally relies on implicit oracles, which aim used by conventional property testing methods) and (2) a user- to detect anomalous behavior such as crashes or uncaught excep- defined comparison function for specifying how outputs from the tions, or property tests, which assert a predicate over the output of original program and a program mutant should be compared. An some computation. For example, consider the insertion sort method example of differential mutation testing methods in our framework

                 932

Guiding Greybox Fuzzing with Mutation Testing ISSTA ’23, July 17–21, 2023, Seale, WA, USA

1 @Diff // inputs generated by Mu2 Table 1: Geometric mean of speedups achieved by the execu- 2 int[] runInsertionSort(int[] input) { tion and infection based optimizations (Alg. 3, Line 4) from 3 return Sort.insertionSort(input); the PIE model [38] across 10 repetitions of 3 hours each1. 4 } 5 @Compare // outputs compared with mutant 6 boolean checkEq(int[] outOrig, int[] outMut) { Mean Speedup From: Execution Opt. Infection Opt. 7 return Arrays.equals(outOrig, outMut); ChocoPy 3.6× 7.4× 8 } Gson 18.2× 23.2× Jackson 60.5× 77.4× Figure 3: A Mu2 differential mutation test driver and com- Tomcat 13.6× 23.8× parison method for the insertionSort method (Fig. 2). Algorithm 3 Logic for determining which mutants to run in a is shown in Figure 3. The @Diff method runInsertionSort given iteration of the fuzzing loop (Alg. 2) returns an output value of type int[]. The user-defined com- 1: function ProgMuts2Run(Program 𝑃 , Old inputs corpus, New input 𝑥) parison method checkEq simply determines if the output ar- 2: surviving ← mutants(𝑃 ) \ killed(𝑃, corpus) rays are equal. If unspecified, the @Compare function defaults to 3: killable ← {𝑃 ′ = ⟨𝑃, 𝑒, 𝑒′, 𝑛⟩ | (𝑃 ′ ∈ surviving) ∧ the java.lang.Objects.equals() method. Our interface 4: (𝑛 ∈ coverage(𝑃, 𝑥 ) ) ∧ (infect(𝑃, 𝑒, 𝑒′, 𝑥 ) ) } is general enough to support complex differential testing oracles 5: if AGGRESSIVE_OPT is configured then such as the ones used in CSmith [80]. 6: return filter (killable, AGGRESSIVE_OPT ) With differential mutation testing, we are able to kill mutants 7: return killable such as 𝑃3′ described above with an input like [3, 2, 1], where the output of insertionSort on the original program—[1, 2, methods are expected to be self-contained and not depend on global 3]—is not equal to the output of the mutant—[1, 1, 1]. state. Like JQF and Zest, Mu2 is designed to work in a single JVM. We can now precisely define Kills(𝑃 ′, 𝑥) which was referenced Mu2 thus adopts a different strategy than PIT and takes advan- in Algorithm 2. Given a mutant 𝑃 ′ = ⟨𝑃, 𝑒, 𝑒′, 𝑛⟩ and an input 𝑥 , tage of the Java class-loader mechanism to load and run program Kills(𝑃 ′, 𝑥) returns true iff: mutants within the same JVM, essentially by having copies of the (1) 𝑃 (𝑥 ) = ~ ∧ 𝑃 ′(𝑥 ) = ′ ∧ ¬Compare(, ~′), where Compare entire class hierarchy (one per mutant) in memory at the same time. is the user-defined @Compare method (e.g., checkEq in Fig- First, a CoverageClassLoader (CCL) is responsible for loading ure 3) or Object.equals() if one is not defined; or the original target program 𝑃 and collecting code coverage using (2) 𝑃 (𝑥 ) = ~ but executing 𝑃 ′(𝑥 ) results in an uncaught run-time on-the-fly instrumentation. For differential testing, the CCL-loaded exception being thrown; or classes compute the ground-truth outcome 𝑃 (𝑥 ). Second, a family (3) Executing 𝑃 ′(𝑥 ) takes longer than a predefined TIMEOUT. of MutationClassLoaders (MCL) are used to load program The timeout is required for killing mutants such as 𝑃4′ = mutants; one MCL per mutant 𝑃 ′ = ⟨𝑃, 𝑒, 𝑒′, 𝑛⟩. When a mutant ⟨Sort, i-1, i, 8⟩, which effectively removes the decrement of i, test program is loaded by the MCL, it performs on-the-fly bytecode leading to an infinite loop on the input [3, 1, 2]. instrumentation exactly at location 𝑛, replacing expression 𝑒 with We evaluate the improvement in completeness using the differ- 𝑒′ and loading the rest of the program without changing semantics. ential oracle over the greybox fuzzing implicit oracle in Section 4.4. The MCL adds instrumentation at backward jumps (i.e., loops) in order to detect timeouts and exit test execution cleanly if necessary. 3.4 Performance Further, assuming that fuzz tests do not affect global state, Mu2 The biggest challenge with incorporating mutation testing inside loads only one copy of each library class (defined as classes outside a fuzzing loop is performance. Given its need to execute many a specified package identifying the target application as long as they mutants on each iteration, mutation testing is in general a very and their transitive dependencies do not reference any application expensive technique [63], so scaling Mu2 to real-world software class) using a common SharedClassLoader—this dramatically is a non-trivial task. Two aspects of improving scalability are: (1) reduces memory pressure when mutating large programs. reducing the average time required to execute each program mutant, To validate our design, we ran an informal preliminary exper- and (2) reducing the number of program mutants that must be iment of performing mutation analysis with PIT and Mu2’s in- evaluated at each iteration of the fuzzing loop. memory set-up on a fixed corpus of seed inputs for the Google 3.4.1 Improving Performance of Mutant Execution. When running Closure Compiler [30]. In the steady state (after the first 8 inputs), a mutation testing tool such as PIT [17], each mutant and test is run Mu2’s in-memory analysis runs with a 9.6× speed-up over PIT. in a different JVM. For general mutation testing, this is ideal because 3.4.2 Reducing the Number of Mutants to Run in the Fuzzing Loop. it simplifies managing multiple copies of the same program (sans For each trial—i.e., iteration of the fuzzing loop—(1) the input must mutations), and prevents global state changes from one program be executed once by the original program and (2) the input must mutant affecting the state of another program mutant. However, be executed by each mutant. Thus, we can model the time required this is not necessary for Mu2. For in-process fuzzing, test driver to execute each trial as the following: 1The Closure Compiler benchmark was too large to run without the execution and trialTime = timeorig + 𝑀 ∗ avgTimemut (1) infection optimizations, so we did not include the speedups in this table. where 𝑀 = |ProgMuts2Run(𝑃, corpus, 𝑥)| as per Algorithm 2.

 933

ISSTA ’23, July 17–21, 2023, Seale, WA, USA Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye

          Observe that the time per trial scales linearly with 𝑀. We can                                 fuzzing campaign. This is a novel reduction strategy designed
     improve the fuzzing throughput (i.e., the number of trials executed        specifically for the fuzzing loop.
       per unit time) directly by reducing 𝑀. From Algorithm 2 (Lines 9–                           Section 4.2 evaluates the impact of these aggressive optimizations.
      10), we can see that we only care about executing a program mutant

if it will help us determine if a given input is the first input to kill it. 4 We can therefore reduce 𝑀 by dynamically pruning mutants whose EVALUATION execution will necessarily lead to Line 9 evaluating to false. We evaluate Mu2 on 5 different Java program benchmarks, using So, we begin by applying the following conditions for a given state-of-the-art coverage-guided fuzzer Zest [59] as the baseline. 𝑃 ′ = ⟨𝑃, 𝑒, 𝑒′, 𝑛⟩, which are shown in Algorithm 3, lines 2–4: We structure our evaluation around four research questions: RQ1: Does mutation-analysis guidance produce a higher quality (1) If 𝑃 ′ ∈ killed(𝑃, corpus), then 𝑃 ′ does not need to be exe- test-input corpus than coverage-only feedback in greybox fuzzing? cuted for any future inputs. RQ2: How do the performance optimizations impact the quality of (2) If the program mutant 𝑃 ′ applies a mutation to a program the test-input corpus produced by mutation-analysis guidance? location 𝑛, but 𝑛 is not covered when executing the original RQ3: How does the reliability of killing nontrivial mutants differ program on 𝑥 , then 𝑃 ′ cannot be killed by 𝑥 . This corresponds between mutation-analysis guidance and coverage guidance? to execution-based pruning in the PIE model [38]. RQ4: How much stronger is the differential mutation testing oracle (3) If we can guarantee that all dynamic evaluations of 𝑒 during than the implicit oracle? the execution of 𝑃 on 𝑥 are equivalent to the corresponding Benchmarks. We consider five real-world Java programs:2 evaluations of mutated expression 𝑒′, then 𝑃 ′ cannot be killed by 𝑥 . This corresponds to infection-based pruning in (1) ChocoPy [7, 61] reference compiler (6K LoC): The test driver the PIE model [38], which we implemented as a dynamic (reused from [75]) reads in a program in ChocoPy (a statically analysis of the execution of the original program 𝑃 (𝑥 ). typed dialect of Python) and runs the semantic analysis stage of the ChocoPy reference compiler to return a type-checked The last two strategies from the PIE model require additional over- AST object. head when executing 𝑥 : (1) the execution-based pruning depends on (2) Gson [29] JSON Parser (26K LoC): The test driver parses a coverage instrumentation, and (2) infection-based pruning requires input JSON string and returns a Java object output. evaluating and comparing the mutation expression 𝑒 each time (3) Jackson [22] JSON Parser (49K LoC): The test driver acts that it is executed by 𝑥 . Referring to Equation 1, the optimization similar to that of Gson. results in a trade-off for trialTime due to the increase in timeorig (4) Apache Tomcat [3] WebXML Parser (10K LoC): The test and decrease in the number of mutants to run 𝑀. However, we find driver parses a string input and returns the WebXML repre- this is quite beneficial overall. Table 1 shows the results of prelim- sentation of the parsed output. inary experiments on 4 benchmarks included in our evaluations (5) Google Closure Compiler [30] (~250K LoC): The test driver in Section 4 to validate these optimizations; clearly, they improve (reused from [59] and [75]) takes in a JavaScript program performance significantly. and performs source-to-source optimizations. It then returns We note that all the pruning methods mentioned above are sound the optimized JavaScript code. optimizations: a mutant is pruned only if it is guaranteed to sur- Mutation selection. Following previous work on semantic vive when executed. Effectively, we are pruning mutants that are fuzzing [59, 75], we filter on package names to identify classes equivalent modulo inputs [47]. relating to the core logic of the program under test. The mutation 3.4.3 Aggressive Mutant Selection Optimizations. While the execu- operators are then applied on these classes. We use the same gen- tion and infection optimizations significantly improve the overall erators, oracles, and filters for both Zest and Mu2. All of the test throughput of Mu2, the 𝑀 factor in Equation 1 still grows linearly drivers return objects that override Object.equals, and were with the size of the program (more code = more mutants). We can thus properly compared by the differential oracle. be aggressive about reducing 𝑀 by attempting to bound it by a Duration. Following best practices [42], we use a time bound of constant 𝑘 , at the risk of potentially missing out on analyzing some 24 hours for each experiment. mutants that could have been killed by a given input. We call these aggressive optimizations. We use the function filter in Algorithm 3 Repetitions. To account for the randomness in fuzzing, we run (Line 6) to optionally apply a selection strategy [66, 73] that returns each experiment 20 times and report statistics. a bounded subset of the killable mutants. We have implemented Metrics. For our evaluations, we compute the branch coverage two types of filters in Mu2: and mutation scores across each fuzzer-generated test-input corpus. (1) 𝑘 -Random Mutant Filter: For each generated input, 𝑘 mutants We report mutation scores as the absolute number of mutants killed are randomly sampled from the killable set in Alg. 3. instead of as a fraction (ref. Section 2.2), since we only care about (2) 𝑘 -Least-Executed Mutant Filter: For each generated input, comparing these numbers across fuzzing variants, and since the the killable mutants are sorted by the number of times they denominator is meaningless when considering a single test entry have been executed on previous inputs. The first 𝑘 mutants point. We additionally compute the kill frequency of each of the are then selected. The goal is to prioritize executing mutants 2 that have not been tested as frequently during the fuzzing While we note lines of code (LoC) for completeness, only a fraction of this code is reachable from fuzz drivers. Fig. 5 indicates actual code coverage.

    934

Guiding Greybox Fuzzing with Mutation Testing                                                                             ISSTA ’23, July 17–21, 2023, Seale, WA, USA

                 ChocoPy                    Gson                     Jackson                          Tomcat                       Closure
          290                           310                        400                                                          270
          285                           300                        380                            235                           260
          280                           290                        360                            230                           250
                                                                                                                                240
          275                           280                        340                            225                           230
          270
            Zest Mu2-     Mu2-    Mu2-      Zest Mu2-    Mu2-    Mu2-  Zest  Mu2-   Mu2-    Mu2-      Zest Mu2-   Mu2-    Mu2-     Zest Mu2-   Mu2-    Mu2-
                 Default  Split   OPT       Default      Split   OPT       Default  Split   OPT          Default  Split   OPT        Default   Split   OPT

Figure 4: Box plots showing the number of killed mutants by Zest and Mu2-generated test corpora across 20 repetitions of
24-hour fuzzing campaigns (higher is better). Mu2-Split and Mu2-OPT are two variants of Mu2 detailed in Section 4.1.

                                      Branch Coverage                               significant increases in all three. Additionally, Figure 5 shows equiv-
  1.00                                                                              alent branch coverage between Zest and Mu2 for these benchmarks.
                                                                                    For the Tomcat WebXML parser, the number of killed mutants
  0.75                                                                              saturated at 239 in almost all of the repetitions of the fuzzing cam-
                                                                                    paigns. For the Closure Compiler, our largest benchmark, the Mu2-
  0.50           Zest                                                               Default corpora achieve, on average, approximately 17% less branch
                 Mu2-Split                                                          performance overhead of running mutation analysis for a large
  0.25           Mu2-Default                                                        coverage than Zest (shown in Figure 5). This is likely due to the
  0.00           Mu2-OPT                                                            benchmark, and also likely accounts for the Zest corpora on aver-
          ChocoPy          Gson          Jackson Tomcat          Closure            age killing 12 more mutants than Mu2-Default, as covering code is a
           (4856)          (645)          (2217)    (990)        (30792)            necessary condition for killing mutants in that part of the code. This
                                        Benchmark                                   suggests Mu2-Default may not scale well to very large programs.
Figure 5: Branch coverage across all benchmarks normal-                                       One way to mitigate this slowdown is to add mutation-analysis
ized to the mean coverage achieved by Zest. The number of                           feedback to coverage-guided fuzzing later in the campaign. The
branches covered by Zest (used to normalize) is listed below                        Mu2-Split variant utilizes coverage-only feedback for the first half
each target. Error bars represent 95% confidence intervals.                         of the campaign (which is very efficient) and then introduces ex-
                                                                                    pensive mutation-analysis feedback for the second half. This is
                                                                                    based on an idea by Gopinath et al. [31], who suggested saturating
nontrivial mutants across the repetitions. When reporting statistical               coverage before adding mutation analysis to the fuzzing loop. The
significance, a Mann-Whitney-U test was performed with 𝛼 = 0.05.                   Mu2-Split-generated corpora show statistically significant increases
                                                                                    in mutation score over Zest for the first 4 benchmarks (Fig. 4), al-
 Default variant. Unless explicitly qualified with an aggressive                    though the effect for Tomcat is very small. There is also a major
optimization strategy, the default variant of Mu2 used in our evalu-                improvement over Mu2-Default in the Closure benchmark; Mu2-
ation only uses sound optimizations described in Section 3.4.2.                     Split is able to bridge the gap in coverage (Fig. 5) and mutation
 Reproducibility and Data Availability.          We have published a repli-         scores (Fig. 4) that Mu2-Default had with the Zest baseline.
cation package and evaluation data at: https://doi.org/10.5281/                              Another method of scaling Mu2 is to apply the aggressive opti-
zenodo.7647828. The evaluation data contains logs of fuzzing cam-                   mizations detailed in Section 3.4.3. Mu2-OPT is a particular vari-
paigns used to generate all evaluation figures and tables [74].                     ant we chose that applies the k-Least-Executed filter with 𝑘      = 10
                                                                                    mutants. The Mu2-OPT generated corpus similarly achieves sta-
4.1                        RQ1: Test-Input Corpus Quality                           tistically significant increases in mutation scores across the first
 Does mutation-analysis guidance produce a higher quality test-                     four benchmarks over Zest, with up to 20% increase in the Jackson
 input corpus than coverage-only feedback in greybox fuzzing?                       JSON parser (Fig. 4). There is no significant difference between the
                                                                                    mutation scores of Mu2-OPT and Zest on the Closure Compiler.
 RQ1 focuses on evaluating mutation-analysis-guided fuzzing                         Mu2-OPT achieves slightly less coverage than Zest on two bench-
with a fixed time budget. Higher mutation score from the Mu2-                       marks (ChocoPy and Closure) and more on one (Jackson)—however,
produced corpus and comparable coverage results would demon-                        the differences are fairly small (below 2%).
strate that mutation-analysis can be used as an off-the-shelf re-                                We are also curious about whether the additional saving of
placement for coverage-only guidance. We first discuss results for                  mutant-killing inputs in Mu2 may bloat the size of the generated
Mu2-Default, then evaluate two variants against the Zest baseline.                  test-input corpus, impacting its use in regression testing. Table 2
 Figure 4 visualizes the mutation scores for each fuzzer-generated                  displays the average sizes and runtimes for each fuzzer-generated
corpus. The default mutation-analysis guidance (Mu2-Default) is                     corpus and show that no such bloat occurs in Mu2. While there
able to produce a corpus with higher mutation scores than coverage-                 are some differences in the number of test inputs, the runtime of
only feedback in the first three benchmarks, achieving statistically                the Mu2-produced corpora are not significantly higher than those



                                                                 935

Coverage Relative to Zest Killed Mutants

ISSTA ’23, July 17–21, 2023, Seale, WA, USA        Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye

Table 2: Average number of test inputs (and average runtime,                                ChocoPy       Gson
in parentheses below) of fuzzer-generated corpora. Corre-
sponding standard deviations also listed.                                           290                300

             Zest      Mu2-                          Mu2-              Mu2-         285                290
                             Default                Split              OPT
 ChocoPy   864 ± 34          711 ± 47              725 ± 36          746 ± 40       280                280
       (18.6 s ± 2.1 s)  (9.8 s ± 0.8 s)       (11.7 s ± 1.3 s)  (10.4 s ± 1.0 s)
  Gson     467 ± 18          461 ± 17              469 ± 15          489 ± 21               Jackson       Tomcat
       (1.7 s ± 0.1 s)   (1.7 s ± 0.1 s)       (1.7 s ± 0.0 s)   (1.7 s ± 0.0 s)   407.5
 Jackson   598 ± 19          655 ± 16              641 ± 19          673 ± 15      405.0               235
       (2.4 s ± 0.1 s)   (2.4 s ± 0.1 s)       (2.4 s ± 0.0 s)   (2.4 s ± 0.1 s)
 Tomcat    138 ± 7           122 ± 6               136 ± 6           171 ± 5       402.5
       (2.6 s ± 0.1 s)   (2.5 s ± 0.1 s)       (2.6 s ± 0.1 s)   (2.7 s ± 0.1 s)   400.0               230
 Closure  4885 ± 205        1075 ± 219     4044 ± 146               4037 ± 192     397.5
        (554 s ± 82 s)    (58 s ± 13 s)         (360 s ± 27 s)    (353 s ± 30 s)   395.0               225
                                                                                   392.5
                                                                                        Closure
Table 3: Geometric mean of speedups achieved by each ag-
gressively filtered variant of Mu2 over Mu2-Default. 20/10/5                       280                    Variant (in order)
refer to the sizes of the filtered subset of mutants.                              270                    Mu2-Default
                                                                                   290
                                                                                   260                    Mu2-Random-20
      LeastExecuted (20/10/5)                                                      250                    Mu2-LeastExecuted-20
           Random (20/10/5)                                                        285                    Mu2-Random-10
  ChocoPy    1.1/1.7/2.8×                      1.1/1.6/2.5×                        240                    Mu2-LeastExecuted-10
    Gson    0.9/1.1/1.3×                       1.0/1.2/1.3×                        230                    Mu2-Random-5
                                                                                   280                    Mu2-LeastExecuted-5
  Jackson    1.0/1.1/1.3×                      1.1/1.0/1.2×
   Tomcat    3.4/3.5/8.2×                      2.3/6.0/7.9×              Figure 6: Box plots showing number of killed mutants by
  Closure  10.4/13.8/21.3×     13.8/19.2/24.9×                           each aggressively optimized variant of Mu2 and the default,
                                                                         across 20 repetitions of 24 hour campaigns (higher is better).

produced by Zest. Thus, mutation-analysis-guided fuzzing is able
to produce a higher quality test-input corpus and can be feasibly        Closure benchmark. This makes sense, as the main purpose of
used for regression testing.                                             aggressive optimizations is to enable scaling to large programs.
  We believe that an aggressively optimized version of mutation-                    Due to the aggressive nature of the mutant filtering, it is possible
analysis-guided fuzzing can be used as a replacement for coverage-       that input candidates that do kill mutants are not saved simply
guided fuzzing if the goal is to produce a test input corpus with high   because those killable mutants were filtered. To determine whether
mutation score. Mu2-OPT provides an improvement for 4 bench-             the speedup actually results in a test-input corpus with higher muta-
marks and scales to the largest target without paying a performance      tion score, we must also measure the impact of these optimizations
penalty.                                                                 on the mutation score of the generated corpus.
4.2     RQ2: Aggressive Optimizations                                               Figure 6 displays the mutation scores of all of the variants for
                                                                         each of the 5 benchmarks. At least one optimized variant was bet-
  How do the performance optimizations impact the quality of             ter than the default in all benchmarks. Somewhat surprisingly, we
  the test-input corpus produced by mutation-analysis guidance?          observe similar mutation scores between the Mu2-LeastExecuted-𝑘
                                                                         and Mu2-Random-𝑘 variants for the same value of 𝑘 in the first
  This RQ focuses on understanding the benefit of the aggressive         four benchmarks. The one exception is Closure Compiler, where
optimizations in mitigating the scalability concerns of Mu2-Default.     Mu2-LeastExecuted-10 achieves a statistically significantly higher
We created variants Mu2-LeastExecuted-𝑘       and Mu2-Random-𝑘 ,       mutation score than Mu2-Random-10. Again, the effect of aggres-
each applying the corresponding filter described in Section 3.4.3,       sive optimizations is most pronounced in the largest target.
and chose three different values of 𝑘     ∈ {5, 10, 20}.                           Another interesting observation is that we can visualize the
  First, we measure just the performance benefit. Table 3 shows          trade-off between execution speed and mutation score in the Jack-
the speedups achieved—in terms of number of inputs evaluated             son benchmark: although the Mu2-Random-5 variant has a faster
over a 24-hour period—by each variant over Mu2-Default. The              execution speed than Mu2-Random-10 (Tab. 3) due to the smaller
improvement for the benchmarks Gson and Jackson is relatively            number of mutants, the mutation score slightly decreases (Fig. 6)
minor due to the already small number of mutants executed for each       since the optimization might skip some mutants at the wrong time.
input after applying the execution and infection optimizations (ref.     Nonetheless, the speedup displayed by the variants for the Closure
Section 3.4.2 and Table 1). However, the aggressive optimizations        Compiler results in better test-input corpus quality. All of the Mu2
provide significant improvement for the larger benchmarks, with          variants are able to achieve statistically significantly higher muta-
almost 25× speedup for the Mu2-LeastExecuted-5 variant on the            tion scores than Mu2-Default. Specifically, Mu2-LeastExecuted-10,



                                               936

killed Killed Mutants

Guiding Greybox Fuzzing with Mutation Testing                                                                                        ISSTA ’23, July 17–21, 2023, Seale, WA, USA

Mu2-Random-5, and Mu2-LeastExecuted-5 kill ∼15 more mutants                                             ChocoPy                                                 20                 Gson
on average than Mu2-Default.                                                      10
          We found that Mu2-LeastExecuted-10 and Mu2-LeastExecuted-5               8                                                                            15
were the strongest variants, as they had a statistically significant               6                                                                            10
increase in mutation score over Mu2-Default in the most bench-                     4
marks (3 out of 5) out of all variants. There was no significant                   2                                                                            5
difference in mutation scores between these two variants in any                    0                                                                            0
benchmarks, so we arbitrarily picked Mu2-LeastExecuted-10 as the                        -20  -15  -10   -5 0     5     10   15   20      -20                            -15 -10  -5  0 5 10 15 20
optimized version of mutation-analysis-guided fuzzing (Mu2-OPT)                   40                    Jackson                                                 6                Tomcat
in our evaluation of RQ1 and RQ4. We do however note for future                                                                                                 5
practitioners that the best aggressively optimized variant of Mu2                 30                                                                            4
may change depending on the target program.                                       20                                                                            3
                                                                                                                                                                2
                                                                                  10
                                                                                                                                                                1

4.3     RQ3: Nontrivial Mutants                                                    0    -20  -15  -10   -5 0     5     10   15   20                             0 -20  -15  -10  -5  0 5 10 15 20
                                                                                                                                     Closure
 How does the reliability of killing nontrivial mutants differ                                                   50                                                     Mu2-OPT
 between mutation-analysis guidance and coverage guidance?                                                       40                                                     Zest

Not all mutants are equal—some mutants are easier to kill than                                                   30
others. We define a mutant 𝑃 ′ = ⟨𝑃, 𝑒, 𝑒′, 𝑛⟩ as trivial if it is killed                                   20
by the first input that executes 𝑛 in every experiment (this is the                                             10
dynamic version of Kaufman et al.’s definition [40]). Since trivial                                              0
mutants are killed as soon as the corresponding code is covered,                                                       -20  -15  -10 -5 0   5                          10   15   20
                                                                                                                            Difference in Kill Frequency
conventional coverage-guided fuzzing like Zest suffices to capture                                                              (bars further right indicate higher reliability of Mu2)
them. On the other hand, since nontrivial mutants may or may
not be killed even after the mutated expression is covered, we are                Figure 7: Histogram of difference in kill-rate of nontrivial
interested to know whether these get killed based on pure luck or                 mutants between Zest and Mu2-OPT over 20 experiments.
whether these get killed reliably across repetitions potentially due              X-axis is the difference in repetitions (ranging from -20 to
to the guidance in the fuzzing algorithm. We measure reliability                  20), and Y-axis is the number of mutants. Larger positive dif-
by counting the number of repetitions in which each mutant is                     ferences (right) are better for Mu2-OPT, and larger negative
killed. In particular, we study the difference in reliability of killing          differences (left) are better for Zest.
nontrivial mutants between Zest and the best variant of Mu2.
 Figure 7 is a histogram showing the difference in kill rate of
nontrivial mutants between Mu2-OPT and Zest. The values on the                    4.4        RQ4: Differential Mutation Testing
right side (green) correspond to mutants killed more reliably by                        How much stronger is the differential mutation testing oracle
Mu2-OPT than Zest. For the sake of visualization, the mutants with                      than the implicit oracle?
no difference in kill rate (X-axis value 0) are excluded from the
charts.                                                                                 Described in Section 3.3, the differential mutation testing oracle
 Mu2-OPT is able to achieve a significantly higher kill frequency                 is responsible for determining whether an input kills a mutant by
of nontrivial mutants in ChocoPy and Jackson. In fact, there are                  comparing the outputs of the executions. We contrast it with the
29 mutants in Jackson that are killed during all      repetitions of              incomplete greybox fuzzing implicit oracle, which only detects un-
Mu2-OPT and zero repetitions of Zest. This is a strong indication                 caught exceptions or failed property checks. To study the strength
that mutation-analysis feedback can consistently discover mutant-                 of the differential oracle, we evaluate the improvement in the num-
killing inputs that coverage-only feedback is incapable of finding.               ber of killed mutants over the implicit oracle.
For the Gson parser, there are 22 vs. 24 nontrivial mutants killed                                                               Figure 8 shows the difference in mutant kills across the bench-
more reliably by Zest and Mu2-OPT respectively, though the X-                     marks with the two types of oracles. The differential oracle is able
axis values are generally higher for Mu2-OPT. For Closure, there                  to kill a significantly higher number of mutants across all 5 bench-
are over 60 mutants killed by at least one more repetition of Mu2-                marks, with an average increase of 25%. In the ChocoPy benchmark,
OPT compared to the 4 by Zest. Overall, Mu2-OPT is able to kill                   over 85 more mutants are caught! This is because certain mutants
nontrivial mutants more reliably than Zest.                                       are unkillable by the implicit oracle due to their effect on program
 We also note that Figure 7 provides some insight into the di-                    behavior. We describe one of these mutants below. For brevity, we
versity of mutants, particularly redundant mutants. By definition,                describe the code functionality, omitting the actual code snippet.
redundant mutants are grouped together in the same bars since                                                                       The ChocoPy type-checker has a function to check that the
they are always killed at the same frequency. Flattening the size of              left and right operand types of an expression match when using
each bar to 1 removes at least all redundant mutants and acts as a                the “+" operator. If so, the type is returned and assigned to the
lower bound on the number of nonredundant mutants.                                corresponding expression node in the output AST; otherwise, an



 937

Number of Mutants

ISSTA ’23, July 17–21, 2023, Seale, WA, USA    Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye

        Strength of Oracle                                                 of mutation-analysis-guided fuzzing on mutation score and code
    400                                        Implicit                    coverage.
    300                                        Differential                             Our implementation simply reused all the fuzzing hyperparame-
                                                                           ters (e.g., PickInput and MutateInput in Algorithms 1 and 2) that
    200                                                                    were set by the baseline Zest fuzzer. Tuning these heuristics could
                                                                           affect our results, but the size of this search space is too large for
    100                                                                    us to explore systematically. We stick with the baseline-provided
                                                                           defaults for simplicity and make sure to use the same hyperparam-
      0                                                                    eters for both Zest and Mu2 so that our conclusions are exclusively
        ChocoPy     Gson Jackson     Tomcat        Closure                 based on the inclusion of mutation-analysis guidance in Mu2 only.
                        Benchmark
                                                                            Threats to external validity.           Since our implementation is based
Figure 8: Number of killed mutants detected by the differen-               on JQF [58] and PIT [17], which both target JVM bytecode, we
tial oracle vs. the implicit oracle across 20 repetitions of 24            used Zest as the baseline. We do not know if our conclusions will
hour campaigns with Mu2-Default (higher is better). Error                  generalize to other programming languages or fuzzing platforms,
bars represent 95% confidence intervals.                                   such as the family of tools based on AFL [81] and libFuzzer [49].
                                                                           The available mutation testing infrastructure for C/C++ appears
                                                                           to be less mature than that for Java/JVM. Another threat to exter-
error message for the expression is added to the output AST error          nal validity arises from our selection bias in choice of benchmark
list. Consider a mutant 𝑃 ′ that modifies this function to return         programs. Our targets have input and output formats which make
null instead of the correct type. Executing 𝑃 ′ on the well-typed         them amenable to differential mutation testing. This is not always
ChocoPy program [1]+([2]+[3]) results in a type-checking                   true for all applications that can be fuzzed—e.g., PDF viewers and
error, since the [int] type of [1] does not match the mutated              other programs whose output is graphical. The study of the general
null return type of ([2]+[3]). The differential oracle kills 𝑃 ′          test oracle problem [6] is outside the scope of this paper.
since the output AST produced by 𝑃 ′ contains a type error, whereas       6
𝑃  does not. The implicit oracle fails to kill this mutant since no        RELATED WORK
exceptions are triggered.                                                               Greybox fuzzing. The field of coverage-guided greybox fuzzing
    We conclude that the differential oracle is substantially stronger     has a vast literature, as surveyed by Manès et al. [52]; a more recent
than a traditional implicit oracle and is valuable for capturing a         and evolving publication list is maintained by Wen [78]. The ma-
larger set of mutant program execution behaviors.                          jority of fuzzing research focuses on improving heuristics such as
                                                                           seed-picking power schedules [9], input mutations [5, 48, 50], and
5   THREATS TO VALIDITY                                                    coverage feedback [14, 25]. FuzzFactory [60] generalizes the feed-
    Threats to construct validity. First, the measurement of mutation      back of greybox fuzzing beyond code coverage to domain-specific
score is of course dependent on the set of mutation operators be-          metrics that satisfy certain conditions. Our proposed mutation-
ing applied to generate program mutants [62]. We aim to mitigate           analysis guidance fits into this framework.
this threat by using the default set of operators in the widely used                   Greybox fuzzing for regression testing. A family of techniques
PIT framework, as justified in Section 3.1. Second, our test oracles       have been developed for directing fuzz testing towards specific
(ref. Section 3.3) report an outcome of TIMEOUT if a mutant execu-         code locations [8, 13, 77] or code commits [84], which can be used
tion does not terminate within a predefined limit. Such a bound is         for identifying regressions. However, this still requires running a
necessary to catch infinite loops (e.g., for mutants that negate loop      full fuzzing campaign, which can take hours or days. In contrast,
conditions). However, if this bound is too small, then it is possible      we focus on synthesizing a high-quality test-input corpus which
in theory that some mutants could be marked as “killed” by a fuzzer-       can be quickly executed in CI—usually taking a few seconds or
generated input even if their execution would eventually produce           minutes—as is often already practiced (ref. Section 1).
a correct output. To mitigate this threat, we compute the mutation
scores for the final test-input corpus by re-running saved inputs           Guiding fuzzing with mutation testing.              We first proposed the
on all program mutants using a larger timeout. We also manually            idea of using mutation testing to augment greybox fuzzing in a
analyzed a sample of reported timeouts to confirm correspondence           student research competition [46]; independently, Qian et al. [67]
to infinite loops—we found no false kills.                                 published a similar idea at a regional symposium. However, we
                                                                           believe the current paper is the first to thoroughly evaluate the
    Threats to internal validity. Our evaluation uses mutation score       performance and scalability of incorporating mutation testing in
when comparing the quality of the generated test-input corpora             the fuzzing loop. In particular, we identified that the evaluation in
since our goal was to synthesize a test-input corpus with high             Qian et al.’s paper [67] uses an unsound comparison to the baseline
mutation score (ref. Section 3.1). We assume that a high mutation          Zest; they use mutation analysis with multiple threads but run
score is a valuable objective for fuzzers. However, there is a potential   Zest only single threaded for the same time bound, hence giving
bias from using mutation score as an evaluation metric, as Mu2             higher CPU time to their technique and obscuring the effects of the
benefits from incorporating mutation testing in the fuzzing loop.          increased overhead of performing mutation testing. Additionally,
Our results nevertheless capture the performance overhead impact           they use a selection strategy to choose 10 mutants at random, but



                                               938

Killed Mutants

Guiding Greybox Fuzzing with Mutation Testing ISSTA ’23, July 17–21, 2023, Seale, WA, USA

do not measure the impact on the overall mutation score, since 7 CONCLUSION they never run all killable mutants. We were unable to perform a We investigated the challenges of incorporating mutation analysis head-to-head evaluation between Mu2 and their technique since to guide greybox fuzzing. Our implementation, Mu2, integrates PIT their implementation is not open source. mutation testing into the JQF framework, and is aimed at producing Using mutation testing in automated test generation. In a regis- a test-input corpus with high mutation score. In our design, we in- tered report, Groce et al. [33] propose fuzzing specially mutated corporated a differential testing as an oracle for killing mutants and targets to find inputs triggering interesting control flow not in the proposed optimizations to improve fuzzing throughput by dynami- original program, and then use those inputs as seeds for coverage- cally pruning the number of mutants to be executed. We applied guided fuzzing. However, they do not target maximizing mutant both sound and aggressive optimizations for Mu2 to help scale it to kills—for example, a mutant which only changes return codes gets larger programs. After conducting a thorough evaluation on Mu2 low fuzzing priority in their approach because it won’t affect con- and several variants, we found that mutation-analysis feedback can trol flow [33]. In contrast, Mu2 aims to find inputs that differentiate improve the mutation score of a test-input corpus and more reliably program output on potentially semantics-altering mutants, which kill nontrivial mutants than coverage-guided fuzzing. often change data values but not necessarily control flow. Our ap- One of the challenges identified by Gopinath et al. [31] was to proach is therefore orthogonal to Groce et al.’s and could potentially “improve visibility of mutation analysis among fuzzing researchers.” even be combined. We hope our work increases awareness of mutation analysis tech- 𝜇-test [24] and EvoSuite [23] are evolutionary test-generation niques in the fuzzing community and encourages other researchers techniques that can use mutation scores as an objective as well to develop more advanced hybrid techniques. as a fitness function. 𝜇-test, which is based on Javalanche [70], ACKNOWLEDGMENTS uses a form of differential testing to compare the coverage traces of the original program and a mutant. Unlike these tools, which This research was funded in part by NSF grant CCF-2120955, a seed generate unit test methods for exercising program API, greybox grant from CMU’s CyLab, and an Amazon Research Award. fuzzing focuses on the generation of inputs for system testing, given a fixed entry point. REFERENCES Improving the performance of mutation testing. A lot of research [1] Paul Ammann. 2015. Transforming mutation testing from the technology of the future into the technology of the present. In International conference on software has been conducted to speed up mutation testing [18, 37, 63, 66, 73]. testing, verification and validation workshops (ICST): Mutation workshop. IEEE. The approaches fall into three categories: (1) reducing the number https://mutation-workshop.github.io/2015/program/MutationKeynote.pdf of mutants to generate, (2) pruning mutants to run on a given test, [2] J. H. Andrews, L. C. Briand, and Y. Labiche. 2005. Is Mutation an Appropriate Tool for Testing Experiments?. In Proceedings of the 27th International Conference on and (3) speeding up mutant evaluation on a given test. For exam- Software Engineering (St. Louis, MO, USA) (ICSE ’05). Association for Computing ple, many techniques have been developed to avoid generating Machinery, 402–411. https://doi.org/10.1145/1062455.1062530 [3] Apache Foundation. 2022. Tomcat. https://github.com/apache/tomcat. Retrieved redundant or equivalent mutants [51]; we do not currently make August 31, 2022. an attempt to identify these statically. Just et al. [39] introduce the [4] Cornelius Aschermann, Tommaso Frassetto, Thorsten Holz, Patrick Jauernig, propagation, infection, execution (PIE) model to prune mutants that Ahmad-Reza Sadeghi, and Daniel Teuchert. 2019. Nautilus: Fishing for Deep Bugs with Grammars. In 26th Annual Network and Distributed System Security are test-equivalent using dynamic analysis. Mu2 implements the Symposium (NDSS ’19). https://doi.org/10.14722/ndss.2019.23412 execution and infection optimizations from this work. MeMu [26] [5] Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, and speeds up PIT’s mutation analysis by memoizing unmutated meth- Thorsten Holz. 2019. REDQUEEN: Fuzzing with Input-to-State Correspondence.. In NDSS, Vol. 19. 1–15. https://doi.org/10.14722/ndss.2019.23371 ods with long execution time; this is a promising approach that [6] Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo. 2015. could be integrated into Mu2. Kaufman et al. [40] prioritize mu- The Oracle Problem in Software Testing: A Survey. IEEE Transactions on Software Engineering 41, 5 (2015), 507–525. https://doi.org/10.1109/TSE.2014.2372785 tants to reach test completeness faster. All these optimizations are [7] U. C. Berkeley. 2019. ChocoPy. https://chocopy.org/. Reference compiler JAR sound—they do not avoid analyzing mutants that may be killable. retrieved on January 12, 2022. Other research directions aim to reduce mutation-analysis costs [8] Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. 2017. Directed greybox fuzzing. In Proceedings of the 2017 ACM SIGSAC Conference while potentially trading off soundness. For example, weak muta- on Computer and Communications Security. 2329–2344. https://doi.org/10.1145/ tion [35] has been proposed to terminate mutant evaluation quickly 3133956.3134020 by observing the intermediate state after executing the mutated pro- [9] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage- based Greybox Fuzzing as Markov Chain. In Proceedings of the 2016 ACM SIGSAC gram locations. Many techniques have been developed for mutation Conference on Computer and Communications Security (CCS). 1032–1043. https: reduction [63, 66, 73]—where only a subset of mutants are evaluated //doi.org/10.1145/2976749.2978428 [10] Marcel Böhme, László Szekeres, and Jonathan Metzman. 2022. On the Reliability based on some program-specific criteria. In this paper, we have of Coverage-Based Fuzzer Benchmarking. In 44th IEEE/ACM International Confer- evaluated the random sampling approach and a novel least-executed ence on Software Engineering (ICSE’22). https://doi.org/10.1145/3510003.3510230 approach to mutant selection. Recently, Guizzo et al. [34] have to appear. [11] Sang Kil Cha, Maverick Woo, and David Brumley. 2015. Program-adaptive proposed an evolutionary approach to automate the generation mutational fuzzing. In 2015 IEEE Symposium on Security and Privacy. IEEE, 725– of optimal cost reduction strategies. Further, predictive mutation 741. https://doi.org/10.1109/SP.2015.50 testing [82] uses machine learning to estimate which mutants are [12] Thierry Titcheu Chekam, Mike Papadakis, Yves Le Traon, and Mark Harman. 2017. An empirical study on mutation, statement and branch coverage fault most likely to be killed. Incorporating such advanced models into revelation that avoids the unreliable clean program assumption. In 2017 IEEE/ACM the Mu2 framework are promising directions for future work. 39th International Conference on Software Engineering (ICSE). IEEE, 597–608. https://doi.org/10.1109/ICSE.2017.61 [13] Hongxu Chen, Yinxing Xue, Yuekang Li, Bihuan Chen, Xiaofei Xie, Xiuheng Wu, and Yang Liu. 2018. Hawkeye: Towards a desired directed grey-box fuzzer. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2095–2108. https://doi.org/10.1145/3243734.3243849

939

ISSTA ’23, July 17–21, 2023, Seale, WA, USA Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye

   [14] Peng Chen and Hao Chen. 2018. Angora: Efficient fuzzing by principled search.       [36] Laura Inozemtseva and Reid Holmes. 2014. Coverage is not strongly correlated

In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 711–725. https: with test suite effectiveness. In Proceedings of the 36th international conference on //doi.org/10.1109/SP.2018.00046 software engineering (ICSE’14). 435–445. https://doi.org/10.1145/2568225.2568271 [15] Yiqun T. Chen, Rahul Gopinath, Anita Tadakamalla, Michael D. Ernst, Reid [37] Yue Jia and Mark Harman. 2010. An analysis and survey of the development of Holmes, Gordon Fraser, Paul Ammann, and René Just. 2020. Revisiting the Re- mutation testing. IEEE transactions on software engineering 37, 5 (2010), 649–678. lationship between Fault Detection, Test Adequacy Criteria, and Test Set Size. https://doi.org/10.1109/TSE.2010.62 In Proceedings of the 35th IEEE/ACM International Conference on Automated Soft- [38] René Just, Michael D Ernst, and Gordon Fraser. 2014. Efficient mutation analysis ware Engineering (Virtual Event, Australia) (ASE ’20). Association for Computing by propagating and partitioning infected execution states. In Proceedings of the Machinery, 237–249. https://doi.org/10.1145/3324884.3416667 2014 International Symposium on Software Testing and Analysis (ISSTA’14). 315– [16] Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for 326. https://doi.org/10.1145/2610384.2610388 Random Testing of Haskell Programs. In Proceedings of the 5th ACM SIGPLAN [39] René Just, Darioush Jalali, Laura Inozemtseva, Michael D Ernst, Reid Holmes, and International Conference on Functional Programming (ICFP). https://doi.org/10. Gordon Fraser. 2014. Are mutants a valid substitute for real faults in software 1145/351240.351266 testing?. In Proceedings of the 22nd ACM SIGSOFT International Symposium on [17] Henry Coles, Thomas Laurent, Christopher Henard, Mike Papadakis, and An- Foundations of Software Engineering (FSE’14). 654–665. https://doi.org/10.1145/ thony Ventresque. 2016. PIT: a practical mutation testing tool for Java. In Pro- 2635868.2635929 ceedings of the 25th International Symposium on Software Testing and Analysis [40] Samuel J. Kaufman, Ryan Featherman, Justin Alvin, Bob Kurtz, Paul Ammann, (ISSTA’16). 449–452. https://doi.org/10.1145/2931037.2948707 and René Just. 2022. Prioritizing Mutants to Guide Mutation Testing. In Pro- [18] Fabiano Cutigi Ferrari, Alessandro Viola Pizzoleto, and Jeff Offutt. 2018. A Sys- ceedings of the 44th International Conference on Software Engineering (Pittsburgh, tematic Review of Cost Reduction Techniques for Mutation Testing: Preliminary Pennsylvania) (ICSE ’22). Association for Computing Machinery, 1743–1754. Results. In 2018 IEEE International Conference on Software Testing, Verification and https://doi.org/10.1145/3510003.3510187 Validation Workshops (ICSTW). 1–10. https://doi.org/10.1109/ICSTW.2018.00021 [41] Marinos Kintis, Mike Papadakis, Andreas Papadopoulos, Evangelos Valvis, Nicos [19] R.A. DeMillo, R.J. Lipton, and F.G. Sayward. 1978. Hints on Test Data Selection: Malevris, and Yves Le Traon. 2018. How effective are mutation testing tools? Help for the Practicing Programmer. Computer 11, 4 (1978), 34–41. https: An empirical analysis of Java mutation testing tools with manual analysis and //doi.org/10.1109/C-M.1978.218136 real faults. Empirical Software Engineering 23, 4 (2018), 2426–2463. https: [20] Zhen Yu Ding and Claire Le Goues. 2021. An Empirical Study of OSS-Fuzz Bugs. //doi.org/10.1007/s10664-017-9582-5 In 2021 IEEE/ACM 18th International Conference on Mining Software Repositories [42] George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018. (MSR). IEEE, 131–142. https://doi.org/10.1109/MSR52588.2021.00026 Evaluating fuzz testing. In Proceedings of the 2018 ACM SIGSAC Conference on [21] Robert B Evans and Alberto Savoia. 2007. Differential testing: a new approach Computer and Communications Security. 2123–2138. https://doi.org/10.1145/ to change detection. In The 6th Joint Meeting on European software engineering 3243734.3243804 conference and the ACM SIGSOFT Symposium on the Foundations of Software En- [43] James Kukucka, Luís Pina, Paul Ammann, and Jonathan Bell. 2022. CONFETTI: gineering: Companion Papers. 549–552. https://doi.org/10.1145/1295014.1295038 Amplifying Concolic Guidance for Fuzzers. In 44th IEEE/ACM International [22] FasterXML. [n. d.]. Jackson: JSON for Java. https://github.com/FasterXML/ Conference on Software Engineering (ICSE’22). https://doi.org/10.1145/3510003. jackson. Retrieved August 31, 2022. 3510628 [23] Gordon Fraser and Andrea Arcuri. 2011. EvoSuite: Automatic Test Suite Gen- [44] Leonidas Lampropoulos, Michael Hicks, and Benjamin C Pierce. 2019. Cover- eration for Object-oriented Software. In Proceedings of the 19th ACM SIGSOFT age guided, property based testing. Proceedings of the ACM on Programming Symposium and the 13th European Conference on Foundations of Software Engi- Languages 3, OOPSLA (2019), 1–29. https://doi.org/10.1145/3360607 neering (ESEC/FSE ’11). https://doi.org/10.1145/2025113.2025179 [45] Thomas Laurent, Mike Papadakis, Marinos Kintis, Christopher Henard, Yves [24] Gordon Fraser and Andreas Zeller. 2010. Mutation-driven Generation of Unit Le Traon, and Anthony Ventresque. 2017. Assessing and improving the mutation Tests and Oracles. In Proceedings of the 19th International Symposium on Software testing practice of PIT. In 2017 IEEE International Conference on Software Testing, Testing and Analysis (Trento, Italy) (ISSTA ’10). ACM, 147–158. https://doi.org/ Verification and Validation (ICST). IEEE, 430–435. https://doi.org/10.1109/ICST. 10.1145/1831708.1831728 2017.47 [25] Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, [46] Isabella Laybourn. 2022. 𝜇2: Using Mutation Analysis to Guide Mutation-Based and Zuoning Chen. 2020. GREYONE: Data flow sensitive fuzzing. In 29th USENIX Fuzzing. In Proceedings of the ACM/IEEE 44th International Conference on Software Security Symposium (USENIX Security 20). 2577–2594. https://doi.org/10.5555/ Engineering: Companion Proceedings (Pittsburgh, Pennsylvania) (ICSE ’22). As- 3489212.3489357 sociation for Computing Machinery, 331–333. https://doi.org/10.1145/3510454. [26] Ali Ghanbari and Andrian Marcus. 2022. Faster Mutation Analysis with MeMu. 3522682 In Proceedings of the 31st ACM SIGSOFT International Symposium on Software [47] Vu Le, Mehrdad Afshari, and Zhendong Su. 2014. Compiler Validation via Testing and Analysis (Virtual, South Korea) (ISSTA 2022). 781–784. https://doi. Equivalence modulo Inputs. In Proceedings of the 35th ACM SIGPLAN Confer- org/10.1145/3533767.3543288 ence on Programming Language Design and Implementation (PLDI ’14). 216–226. [27] John B. Goodenough and Susan L. Gerhart. 1975. Toward a Theory of Test Data https://doi.org/10.1145/2594291.2594334 Selection. SIGPLAN Not. 10, 6 (apr 1975), 493–510. https://doi.org/10.1145/390016. [48] Caroline Lemieux and Koushik Sen. 2018. Fairfuzz: A targeted mutation strategy 808473 for increasing greybox fuzz testing coverage. In Proceedings of the 33rd ACM/IEEE [28] Google. 2019. Ideal integration with OSS-Fuzz. https://google. International Conference on Automated Software Engineering. 475–485. https: github.io/oss-fuzz/advanced-topics/ideal-integration/#regression-testing. //doi.org/10.1145/3238147.3238176 https://web.archive.org/web/20200301084941/https://google.github.io/oss- [49] LLVM Compiler Infrastructure. 2016. libFuzzer. https://llvm.org/docs/LibFuzzer. fuzz/advanced-topics/ideal-integration/#regression-testing Retrieved August 31, html. Accessed February 11, 2022. 2022. [50] Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, and [29] Google. 2021. Gson: A Java serialization/deserialization library to convert Java Raheem Beyah. 2019. MOPT: Optimized mutation scheduling for fuzzers. In 28th Objects into JSON and back. https://github.com/google/gson. Retrieved August USENIX Security Symposium (USENIX Security 19). 1949–1966. https://doi.org/10. 31, 2022. 5555/3361338.3361473 [30] Google. 2022. Google Closure Compiler. https://github.com/google/closure- [51] Lech Madeyski, Wojciech Orzeszyna, Richard Torkar, and Mariusz Jozala. 2013. compiler. Retrieved August 31, 2022. Overcoming the equivalent mutant problem: A systematic literature review and a [31] Rahul Gopinath, Philipp Görz, and Alex Groce. 2022. Mutation Analysis: An- comparative experiment of second order mutation. IEEE Transactions on Software swering the Fuzzing Challenge. CoRR abs/2201.11303 (2022). arXiv:2201.11303 Engineering 40, 1 (2013), 23–42. https://doi.org/10.1109/TSE.2013.44 https://arxiv.org/abs/2201.11303 [52] Valentin Jean Marie Manès, HyungSeok Han, Choongwoo Han, Sang Kil Cha, [32] Rahul Gopinath, Carlos Jensen, and Alex Groce. 2014. Mutations: How Close Manuel Egele, Edward J Schwartz, and Maverick Woo. 2019. The art, science, are they to Real Faults?. In 2014 IEEE 25th International Symposium on Software and engineering of fuzzing: A survey. IEEE Transactions on Software Engineering Reliability Engineering. 189–200. https://doi.org/10.1109/ISSRE.2014.40 (2019). https://doi.org/10.1109/TSE.2019.2946563 [33] Alex Groce, Goutamkumar Tulajappa Kalburgi, Claire Le Goues, Kush Jain, and [53] William M. McKeeman. 1998. Differential Testing for Software. DIGITAL TECH- Rahul Gopinath. 2022. Registered Report: First, Fuzz the Mutants. In International NICAL JOURNAL 10, 1 (1998), 100–107. Fuzzing Workshop (FUZZING’22). [54] Barton P. Miller, Louis Fredriksen, and Bryan So. 1990. An Empirical Study [34] Giovani Guizzo, Federica Sarro, Jens Krinke, and Silvia R. Vergilio. 2022. Sentinel: of the Reliability of UNIX Utilities. Commun. ACM 33, 12 (dec 1990), 32–44. A Hyper-Heuristic for the Generation of Mutant Reduction Strategies. IEEE https://doi.org/10.1145/96267.96279 Transactions on Software Engineering 48, 3 (2022), 803–818. https://doi.org/10. [55] Hoang Lam Nguyen and Lars Grunske. 2022. BeDivFuzz: Integrating Behav- 1109/TSE.2020.3002496 ioral Diversity into Generator-Based Fuzzing. In Proceedings of the 44th Inter- [35] William E. Howden. 1982. Weak mutation testing and completeness of test national Conference on Software Engineering (Pittsburgh, Pennsylvania) (ICSE sets. IEEE Transactions on Software Engineering SE-8, 4 (1982), 371–379. https: ’22). Association for Computing Machinery, New York, NY, USA, 249–261. //doi.org/10.1109/TSE.1982.235571 https://doi.org/10.1145/3510003.3510182

                      940

Guiding Greybox Fuzzing with Mutation Testing    ISSTA ’23, July 17–21, 2023, Seale, WA, USA


      [56] Hoang Lam Nguyen, Nebras Nassar, Timo Kehrer, and Lars Grunske. 2020. Mo-    2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE).
   Fuzz: A fuzzer suite for testing model-driven software engineering tools. In 2020    IEEE, 1410–1421.   https://doi.org/10.1145/3377811.3380399
     35th IEEE/ACM International Conference on Automated Software Engineering (ASE).   [70] David Schuler and Andreas Zeller. 2009. Javalanche: Efficient Mutation Testing
IEEE, 1103–1115. https://doi.org/10.1145/3324884.3416668                                for Java. In Proceedings of the 7th Joint Meeting of the European Software En-
[57] A. Jefferson Offutt, Ammei Lee, Gregg Rothermel, Roland H. Untch, and Christian    gineering Conference and the ACM SIGSOFT Symposium on The Foundations of
Zapf. 1996.            An Experimental Determination of Sufficient Mutant Operators.    Software Engineering (Amsterdam, The Netherlands) (ESEC/FSE ’09). Association
ACM Trans. Softw. Eng. Methodol. 5, 2 (apr 1996), 99–118.   https://doi.org/10.1145/    for Computing Machinery, 297–298. https://doi.org/10.1145/1595696.1595750
227607.227610                                                                        [71] SQLite Authors. 2019. How SQLite is Tested. https://www.sqlite.org/testing.html#
    [58] Rohan Padhye, Caroline Lemieux, and Koushik Sen. 2019. JQF: Coverage-guided    the_fuzzcheck_test_harness. https://web.archive.org/web/20200427011538/https:
          Property-based Testing in Java. In Proceedings of the 28th ACM SIGSOFT In-    //www.sqlite.org/testing.html#the_fuzzcheck_test_harness Retrieved August 31,
         ternational Symposium on Software Testing and Analysis (ISSTA’19). 398–401.    2022.
https://doi.org/10.1145/3293882.3339002                                                  [72] The OpenSSL Project. 2016. Run the fuzzing corpora as tests. https://github.
          [59] Rohan Padhye, Caroline Lemieux, Koushik Sen, Mike Papadakis, and Yves    com/openssl/openssl/commit/90d28f05.           https://github.com/openssl/openssl/
     Le Traon. 2019. Semantic Fuzzing with Zest. In Proceedings of the 28th ACM SIG-    tree/openssl-3.0.0/fuzz/corpora Retrieved August 31, 2022.
      SOFT International Symposium on Software Testing and Analysis (Beijing, China)   [73] Macario Polo Usaola and Pedro Reales Mateo. 2010.        Mutation Testing Cost
(ISSTA 2019). ACM, 329–340. https://doi.org/10.1145/3293882.3330576                     Reduction Techniques: A Survey.   IEEE Software 27, 3 (2010), 80–86.        https:
      [60] Rohan Padhye, Caroline Lemieux, Koushik Sen, Laurent Simon, and Hayawardh    //doi.org/10.1109/MS.2010.79
        Vijayakumar. 2019. FuzzFactory: domain-specific fuzzing with waypoints. Pro-   [74] Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello
         ceedings of the ACM on Programming Languages 3, OOPSLA, Article 174 (2019),    Sanna, and Rohan Padhye. 2023. Mu2: Guiding Greybox Fuzzing with Mutation
29 pages.  https://doi.org/10.1145/3360600                                              Testing (Artifact). https://doi.org/10.5281/zenodo.8006662
    [61] Rohan Padhye, Koushik Sen, and Paul N. Hilfinger. 2019. ChocoPy: A Program-       [75] Vasudev Vikram, Rohan Padhye, and Koushik Sen. 2021. Growing A Test Corpus
         ming Language for Compilers Courses. In Proceedings of the 2019 ACM SIGPLAN    with Bonsai Fuzzing. In 43rd IEEE/ACM International Conference on Software
             Symposium on SPLASH-E (Athens, Greece) (SPLASH-E 2019). Association for    Engineering, ICSE 2021, Madrid, Spain, 22-30 May 2021. IEEE, 723–735.       https:
Computing Machinery, 41–45. https://doi.org/10.1145/3358711.3361627                     //doi.org/10.1109/ICSE43902.2021.00072
   [62] Mike Papadakis, Christopher Henard, Mark Harman, Yue Jia, and Yves Le Traon.        [76] Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2019. Superion: Grammar-
     2016. Threats to the validity of mutation-based test assessment. In Proceedings    Aware Greybox Fuzzing. In 41st International Conference on Software Engineering
      of the 25th International Symposium on Software Testing and Analysis. 354–365.    (ICSE ’19). https://doi.org/10.1109/ICSE.2019.00081
https://doi.org/10.1145/2931037.2931040                                                [77] Pengfei Wang, Xu Zhou, Kai Lu, Tai Yue, and Yingying Liu. 2022.       SoK: The
    [63] Mike Papadakis, Marinos Kintis, Jie Zhang, Yue Jia, Yves Le Traon, and Mark    progress, challenges, and perspectives of directed greybox fuzzing. arXiv preprint
        Harman. 2019. Mutation testing advances: an analysis and survey. In Advances    (2022). https://doi.org/10.48550/arXiv.2005.11907
in Computers. Vol. 112. Elsevier, 275–378.    https://doi.org/10.1016/bs.adcom.2018.     [78] Cheng Wen. 2022. Recent Papers Related To Fuzzing. https://wcventure.github.
03.015                                                                                  io/FuzzingPaper/. Retrieved March 16, 2022.
[64] Mike Papadakis, Donghwan Shin, Shin Yoo, and Doo-Hwan Bae. 2018.            Are  [79] Elaine J Weyuker. 1986. Axiomatizing software test data adequacy. IEEE transac-
       mutation scores correlated with real fault detection? a large scale empirical    tions on software engineering 12 (1986), 1128–1138.
         study on the relationship between mutants and real faults. In 2018 IEEE/ACM     [80] Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Under-
        40th International Conference on Software Engineering (ICSE). IEEE, 537–548.    standing Bugs in C Compilers. In Proceedings of the 32nd ACM SIGPLAN conference
https://doi.org/10.1145/3180155.3180183                                                 on Programming language design and implementation (PLDI ’11). Association for
          [65] Van-Thuan Pham, Marcel Böhme, Andrew Edward Santosa, Alexandru Razvan    Computing Machinery, 283–294.     https://doi.org/10.1145/1993498.1993532
        Caciulescu, and Abhik Roychoudhury. 2019. Smart greybox fuzzing. IEEE Trans-     [81] Michal Zalewski. 2014. American Fuzzy Lop. https://lcamtuf.coredump.cx/afl/.
    actions on Software Engineering (2019). https://doi.org/10.1109/TSE.2019.2941681    Accessed February 11, 2022.

[66] Alessandro Viola Pizzoleto, Fabiano Cutigi Ferrari, Jeff Offutt, Leo Fernandes, and [82] Jie Zhang, Ziyi Wang, Lingming Zhang, Dan Hao, Lei Zang, Shiyang Cheng, Márcio Ribeiro. 2019. A systematic literature review of techniques and metrics to and Lu Zhang. 2016. Predictive Mutation Testing. In Proceedings of the 25th reduce the cost of mutation testing. Journal of Systems and Software 157 (2019), International Symposium on Software Testing and Analysis (Saarbrücken, Ger- 110388. https://doi.org/10.1016/j.jss.2019.07.100 many) (ISSTA 2016). Association for Computing Machinery, New York, NY, USA, [67] Ruixiang Qian, Quanjun Zhang, Chunrong Fang, and Lihua Guo. 2022. Inves- 342–353. https://doi.org/10.1145/2931037.2931038 tigating Coverage Guided Fuzzing with Mutation Testing. In Proceedings of the [83] Qian Zhang, Jiyuan Wang, Muhammad Ali Gulzar, Rohan Padhye, and Miryung 13th Asia-Pacific Symposium on Internetware (Hohhot, China) (Internetware ’22). Kim. 2020. Bigfuzz: Efficient fuzz testing for data analytics using framework ab- Association for Computing Machinery, 272–281. https://doi.org/10.1145/3545258. straction. In 2020 35th IEEE/ACM International Conference on Automated Software 3545285 Engineering (ASE). IEEE, 722–733. https://doi.org/10.1145/3324884.3416641 [68] Alexandre Rebert, Sang Kil Cha, Thanassis Avgerinos, Jonathan Foote, David [84] Xiaogang Zhu and Marcel Böhme. 2021. Regression Greybox Fuzzing. In Pro- Warren, Gustavo Grieco, and David Brumley. 2014. Optimizing seed selection ceedings of the 2021 ACM SIGSAC Conference on Computer and Communications for fuzzing. In 23rd USENIX Security Symposium (USENIX Security 14). 861–875. Security (Virtual Event, Republic of Korea) (CCS ’21). Association for Computing https://doi.org/10.5555/2671225.2671280 Machinery, 2169–2182. https://doi.org/10.1145/3460120.3484596 [69] Sameer Reddy, Caroline Lemieux, Rohan Padhye, and Koushik Sen. 2020. Quickly generating diverse valid test inputs with reinforcement learning. In Received 2023-02-16; accepted 2023-05-03

941