Differential Fuzzing

Definition

Differential fuzzing is a software testing and bug-finding technique in which multiple implementations of the same specification are executed on the same randomized inputs and their outputs or behaviors are compared. An implementation is treated as potentially erroneous when its behavior differs from another implementation's behavior on the same input ^[1]. The technique replaces traditional fuzzer oracles (such as crashes, hangs, or unsound memory accesses) with a difference oracle, in which agreement among implementations is treated as evidence of correctness and disagreement is treated as evidence of a bug ^[1].

As a dynamic analysis technique, differential fuzzing operates as a guided randomized search aimed at finding inputs that maximize the difference between implementations' outputs or behaviors [arxiv:2511.02927v1].

How It Works

The core mechanism is:

1. Generate (or mutate) a test input.
2. Feed the same input to two or more implementations of the specification.
3. Compare the outputs or observable behaviors of those implementations.
4. If they diverge, flag the divergence as a potential bug.

Because no formal specification oracle is required, differential fuzzing is especially useful when a reference implementation, a hardware reference, or another independent implementation can serve as ground truth ^[1]. When no single implementation is trusted as ground truth (as in instruction decoder testing), the technique can still find discrepancies among many decoders, and analysts can then identify which side is correct ^[1].

Applications

Cryptography and Complex Format Parsers

Differential fuzzing has been applied successfully to cryptography software and to complex application format parsers such as PDF and ELF ^[1].

x86-64 Instruction Decoders

Differential fuzzing was applied to x86-64 instruction decoders in the MISHEGOS tool. MISHEGOS produces hundreds of millions of decoder tests per hour on modest hardware, uses a novel sliding fuzzing strategy for variable-length architectures based on an overapproximated model of machine instructions, and has been used to discover hundreds of errors in popular x86-64 instruction decoders without relying on a hardware decoder for ground truth ^[1]. MISHEGOS includes an extensible framework for analyzing fuzzing-campaign results to identify errors in a single decoder or discrepancies among multiple decoders ^[1].

CPU RTL Fuzzing

Differential fuzzing is also used in CPU RTL fuzzers such as DifuzzRTL, in which an instruction-set simulator (ISS) is used as a reference model and the hardware RTL implementation is compared against it ^[2]. Cascade (a follow-on CPU fuzzer) observes that programs generated by DifuzzRTL contain only a small proportion of fuzzing instructions — most executed instructions are overhead/setup instructions — and proposes asymmetric ISA pre-simulation to generate valid programs with high data–control dependence ^[2].

Side-Channel Detection in Java Libraries

Differential fuzzing has been used to find information leaks via side channels in real-world Java libraries by searching for inputs that maximize observable behavioral differences [arxiv:2511.02927v1].

Functional Equivalence of LLM-Generated Code Refactorings

A differential-fuzzing-based equivalence checker was used to evaluate whether LLM-generated refactorings (CodeLlama, Codestral, StarChat2, Qwen-2.5, Olmo-3, and GPT-4o across three datasets and two refactoring types) preserve program semantics. In a large-scale evaluation, 19–35% of LLM refactorings were found functionally non-equivalent, and about 21% of these non-equivalent refactorings were undetected by existing test suites [arxiv:2602.15761v1].

Risk Estimation

Because fuzzing provides no guarantees on the absence of bugs, statistical methods have been proposed to estimate the risk of missing bugs after a differential fuzzing campaign. Extreme Value Theory (EVT) has been applied to the tail of the maximum-difference distribution observed during a campaign; in experiments on Java side-channel detection, EVT-based extrapolation outperformed baseline statistical methods (Markov's inequality, Chebyshev's inequality, and the Bayes factor) in 14.3% of cases and tied with the baseline in 64.2% of cases, enabling early stopping and an average saving of tens of millions of bytecode executions [arxiv:2511.02927v1].

Tools

• MISHEGOS — a differential fuzzer for x86-64 instruction decoders that produces hundreds of millions of tests per hour and discovers discrepancies without a hardware ground truth ^[1].

Key Concepts

• Difference Oracle — the comparison-based oracle used in differential fuzzing, in which disagreement among implementations on the same input indicates a potential bug ^[1].
• Differential Testing — the broader technique (introduced by McKeeman, 1998) of comparing multiple implementations' executions simultaneously, of which differential fuzzing is a randomized-search-driven variant ^[1].
• Reference Implementation / ISS as Ground Truth — when an implementation cannot serve as ground truth alone (e.g., x86-64 decoders), multiple implementations are compared pairwise and discrepancies are triaged ^[1].
• Extreme Value Theory (EVT) — a statistical framework for estimating the tail of the maximum-difference distribution in differential fuzzing campaigns, enabling risk-bounded early stopping [arxiv:2511.02927v1].

References

• W. M. McKeeman, "Differential Testing for Software," 1998 ^[1].
• R. McNally, K. Yiu, D. A. Grove, D. Gerhardy, "Fuzzing: The State of the Art," 2012 ^[1].
• B. P. Miller, L. Fredriksen, B. So, "An empirical study of the reliability of UNIX utilities," Communications of the ACM, 1990 ^[1].
• N. Jay, B. P. Miller, "Structured random differential testing of instruction decoders," 2018 ^[1].
• R. Paleari, L. Martignoni, G. F. Roglia, D. Bruschi, "N-version disassembly," 2010 ^[1].