Investigating Coverage Guided Fuzzing with Mutation Testing

Ruixiang Qian, Quanjun Zhang, Chunrong Fang, Lihua Guo

Abstract

Coverage-guided fuzzing (CGF) has become the industry standard for automated software testing, yet it relies on a potentially flawed premise: that increasing code coverage is a sufficient proxy for discovering bugs. This paper introduces $μ$CGF, a novel fuzzing framework that integrates mutation testing into the feedback loop. By utilizing mutation scores rather than simple path coverage to guide input prioritization, $μ$CGF identifies inputs that are demonstrably better at detecting subtle logic errors. Our evaluation across five Java benchmarks demonstrates that $μ$CGF, particularly the N-$μ$Zest variant, achieves superior fault detection and faster coverage compared to traditional CGF baselines.

1. Introduction

Modern software security relies heavily on fuzzing to identify vulnerabilities. Coverage-guided fuzzers work by generating random inputs and retaining those that reach previously unvisited code paths. However, simply executing a line of code does not guarantee that a bug on that line will be triggered or observed. This gap between execution and fault detection suggests that traditional CGF may be discarding high-quality inputs that, while not covering new paths, are more effective at exposing logic errors. This paper proposes bridging this gap by using mutation testing—the practice of injecting intentional, small bugs into a program—to provide a more granular feedback signal for the fuzzer.

2. The Problem: The Weakness of Code Coverage

The fundamental limitation of standard CGF is that code coverage is a "weak" proxy for bug detection. For a bug to be found, an input must satisfy three conditions: it must reach the faulty code (execution), trigger a state change (infection), and that state change must propagate to an observable output or crash (propagation).

Traditional fuzzers often suffer from the "redundant input" fallacy. If two inputs, A and B, both cover the same code path, the fuzzer will typically discard whichever one was found second. However, if Input B is closer to triggering a crash than Input A, the fuzzer has effectively lost progress. By ignoring the internal state and logic sensitivity of the code, CGF misses opportunities to explore deep-seated vulnerabilities.

3. Methodology: $μ$CGF

The authors propose $μ$CGF, which augments the standard fuzzing loop with a mutation testing engine. The framework operates through four primary stages:

  1. Mutant Pool Generation: Prior to the fuzzing session, the system generates a pool of "mutants" using tools like PIT. These are versions of the target program with minor logic changes (e.g., swapping arithmetic operators or modifying boundary conditions).
  2. Differential Feedback: As the fuzzer generates new inputs, it executes them against both the original program and a small, randomly selected subset of mutants.
  3. Mutation Score Guidance: If an input causes a mutant to behave differently than the original program, it is said to "kill" the mutant. This serves as a signal that the input is "bug-revealing."
  4. Energy Allocation: The fuzzer uses a "Matthew Effect" algorithm to assign "energy" (the number of mutations to perform on a specific seed). Two variants were tested:
  5. P-$μ$Zest (Positive): Increases energy for inputs that kill any mutants, encouraging deeper exploration of suspicious logic.
  6. N-$μ$Zest (Negative): Penalizes inputs that only kill "old" mutants already covered by other seeds, forcing the fuzzer to prioritize inputs that explore new, "fresher" logic areas.

To maintain performance, the framework utilizes efficiency via subsampling. Rather than running every input against the entire mutant pool, it checks a small subset (typically 10 mutants) per execution, providing a sufficient signal without prohibitive computational overhead.

4. Experimental Evaluation

The framework was evaluated using five Java benchmarks (C01-C05), ranging from algorithmic tasks to large-scale libraries:

  • Small Algorithms: SortingFuzz, MatrixInverseFuzz, and SuffixArrayFuzz.
  • Large Libraries: SimpleRegressionFuzz (from Apache Commons Math3) and DivFuzz (from Apache Commons Numbers).

The researchers used the Zest fuzzer as a baseline and the PIT mutation testing tool for mutant generation.

5. Key Results and Insights

The experimental results indicate that mutation-guided fuzzing significantly improves testing outcomes:

  • Superior Bug Detection: Both $μ$CGF variants outperformed the baseline Zest in mutant kill rates across all benchmarks. In the SimpleRegression benchmark, the mutation-guided approach detected 10 more unique mutants than the standard coverage-guided approach.
  • Accelerated Coverage: In 60% of the benchmarks, the N-$μ$Zest variant reached maximum branch coverage faster than the baseline, suggesting that mutation guidance actually aids in the discovery of new code paths by prioritizing high-quality seeds.
  • The Efficacy of Negative Feedback: N-$μ$Zest generally performed better than P-$μ$Zest. By pushing the fuzzer away from "solved" logic and toward unexplored state spaces, the negative feedback mechanism proved more effective at maintaining diversity in the seed corpus.

6. Limitations and Future Work

While promising, $μ$CGF introduces new challenges. The primary concern is computational overhead; even with subsampling, running mutants requires more CPU resources than standard fuzzing. Additionally, the effectiveness of the guidance is tethered to mutant quality. If mutants are placed in trivial or unreachable code, the guidance signal becomes noise.

Future research should focus on scaling this approach to multi-million line systems and developing more intelligent, coverage-aware mutant selection strategies to further reduce overhead and improve the signal-to-noise ratio.

7. Conclusion

$μ$CGF demonstrates that mutation testing is a viable and powerful feedback mechanism for coverage-guided fuzzing. By treating mutants as artificial targets, the fuzzer can better distinguish between inputs that merely execute code and those that are likely to reveal genuine software defects. This shift from simple coverage to fault-aware guidance represents a significant step forward in automated software quality assurance.

Summary updated

BibTeX
@inproceedings{qian2022investigating,
  author = {Ruixiang Qian and Quanjun Zhang and Chunrong Fang and Lihua Guo},
  title = {{Investigating Coverage Guided Fuzzing with Mutation Testing}},
  booktitle = {Internetware},
  year = {2022},
  doi = {10.1145/3545258.3545285},
}
Figure