# Differential testing

Differential testing runs the implementation under test and a
second, independently trusted implementation on the same inputs,
then compares outputs. The second implementation is the
**oracle** — it removes the need for the test author to predict the
expected output for each input. When the two disagree, one of them
is wrong; usually the new optimized version, sometimes the old
reference. The principle is mechanical: if A is known correct and B
matches A on every tested input, B is at least as correct as A on
those inputs.

## What it catches

- **Optimized-vs-reference divergence.** Compilers test optimizers
  against simple interpreters. Crypto libraries test SIMD paths
  against scalar paths. Databases test query planners against
  full-table scans. ML frameworks test GPU kernels against CPU
  reference implementations.
- **Port and rewrite drift.** A Go-to-Rust port that disagrees with
  the original is wrong somewhere; the differential test names the
  input where it diverges.
- **Cross-implementation incompatibilities.** Two services that
  agreed to a spec but one drifted. Two SQL engines that both claim
  ANSI compliance.
- **Regressions across versions.** Old version vs new version on
  recorded production traffic; any disagreement is a behavioral
  change.

Differential testing by itself does **not** catch bugs present in
*both* implementations. If A and B share an ancestor (forked
codebases) or a specification gap (both misread the standard), they
will agree on the wrong answer. Composing differential testing with
[fuzzing](https://quality.stereobooster.com/fuzzing.md) and [property-based testing](https://quality.stereobooster.com/property-based-testing.md)
narrows the gap.

## Three canonical deployment patterns

1. **Self-play across versions.** Chess engines like **Stockfish**
   run each new version against the previous version in matches of
   many thousands of games; regression is reported as a *rating
   delta* across the match, not as a per-game pass/fail. The oracle
   is the previous version. Generalizes to any ranked or scored
   system where new vs old can play each other.
2. **Cross-language port verification.** When reimplementing a
   library in a new language, call the original from the new code
   and diff. The oracle is the trusted prior implementation. Works
   for compilers ([CompCert](https://compcert.org/) vs gcc), language runtimes,
   business-logic migrations (Java → Go rewrite), and ML training-vs-inference
   parity checks.
3. **Scalar → SIMD (or → GPU) optimization.** Write the algorithm
   in plain scalar code, then hand-roll the SIMD version, and diff
   the two — the scalar code is the oracle. SIMD libraries that keep
   a scalar fallback beside the vectorized path (CRoaring, simdjson)
   already have the reference. Same pattern for GPU vs CPU paths,
   fixed-point vs floating-point ports, and any "fast path replaces
   slow path" optimization.

Each pattern needs an input generator that reliably triggers edge
cases — boundary values, near-overflow, structured bit patterns,
property-based generation, or recorded production traffic.

The same differential oracle shows up at three levels of rigor. *Prove* the two
agree on every input and it is [equivalence
checking](https://quality.stereobooster.com/equivalence-checking.md); *observe* them on live traffic
instead of an offline generator and it is a [parallel
run](https://quality.stereobooster.com/parallel-run.md), where the existing code is the oracle and the
new code is checked on every real request. Differential testing is the *test*
level in the middle.

## Tools

### Compilers

- **[Csmith](https://github.com/csmith-project/csmith)** (Yang et al. 2011)[^yang2011] — generates random valid C programs and
  compares their behavior across compilers.
- **[YarpGen](https://github.com/intel/yarpgen)** — Csmith's successor for C/C++; generates programs
  that exercise miscompilation patterns the authors found Csmith
  missed.
- **[fuzzilli](https://github.com/googleprojectzero/fuzzilli)** — JavaScript engine fuzzing; differential against
  multiple JS engines.

### Databases

- **[SQLancer](https://github.com/sqlancer/sqlancer)** (Rigger and Su 2020)[^rigger2020] — differential and metamorphic
  oracles for SQL engines. It has found bugs in SQLite, MySQL, PostgreSQL,
  CockroachDB, TiDB, and DuckDB; the running
  [bug ledger](https://www.manuelrigger.at/dbms-bugs/) is public.

### Crypto

- **[Wycheproof](https://github.com/C2SP/wycheproof)** (Google) — test vectors generated against reference
  implementations; runs differentially against any candidate library.
- **[fiat-crypto](https://github.com/mit-plv/fiat-crypto)** (Erbsen et al. 2019)[^erbsen2019] — verified crypto primitives
  that other libraries can cross-check against.

### Numerical / ML

- Common pattern: write the operator twice — once in pure
  Python/NumPy, once in optimized CUDA/Triton — and assert
  agreement under tolerance over a Hypothesis-generated input grid.
  No single famous tool; the pattern is standard practice inside
  PyTorch, JAX, TensorFlow.

### General-purpose harnesses

- **[Hypothesis](https://hypothesis.readthedocs.io/)** (Python), **[fast-check](https://fast-check.dev/)** (TS), **[proptest](https://github.com/proptest-rs/proptest)** (Rust) —
  any property-based testing framework runs a differential oracle
  trivially: `assert ref(x) == impl(x)` is the entire property.
- **[Atheris](https://github.com/google/atheris)**, **[libFuzzer](https://llvm.org/docs/LibFuzzer.html)**, **[AFL++](https://github.com/AFLplusplus/AFLplusplus)** — fuzzers run differential
  oracles by encoding "the two implementations disagree" as the
  crash condition.

## When to use, when not

**Use:**

- A reference implementation correct by inspection, however slow.
  Simple interpreters, brute-force scans, reference crypto
  primitives, a Python port of the Rust version, the previous
  release.
- A port across languages, or a rewrite of an internal algorithm —
  the original is the reference.
- Multiple implementations of one standard (SQL engines, JS
  engines, JSON parsers, regex engines, image decoders). Each pair
  is a differential oracle.
- An output space rich enough that an example test would cover only
  a tiny slice. Compilers and databases are the canonical cases.

**Don't:**

- When no reference exists. Differential testing requires two
  implementations of the same function, so code that *is* the
  reference — an entirely new behavior — belongs to
  [property-based testing](https://quality.stereobooster.com/property-based-testing.md) or
  [metamorphic testing](https://quality.stereobooster.com/metamorphic-testing.md) instead.
- When the reference and the implementation share a bug source.
  Forks of the same codebase, two libraries reading the same
  ambiguous spec, or two implementations of an internal pseudocode
  spec written by the same person will agree on the same wrong
  answer.
- For floating-point code without a tolerance model. Bit-exact
  agreement across IEEE 754 implementations is rare; design the
  comparison around an explicit ULP bound.

## Evidence

- **Csmith** found 325+ previously unknown bugs in GCC, LLVM, and
  other C compilers over three years — the single cleanest
  empirical demonstration of differential testing at industrial
  scale (Yang et al. 2011)[^yang2011].
- **SQLancer** reported 123 bugs across three mature
  DBMSs — SQLite, MySQL, and PostgreSQL — 99 of them fixed or
  verified (Rigger and Su 2020)[^rigger2020].
- **The CompCert outlier**: Csmith found no wrong-code bugs in its
  formally [verified](https://quality.stereobooster.com/theorem-proving.md) middle-end
  (Leroy 2009; Yang et al. 2011)[^leroy2009] [^yang2011] — a benchmark for what verification (the
  reference side) can achieve.

## Related

**Generative testing**

These methods blur together because they all run the code and check the result
without a hand-written expected value. Two roles pull them apart, and a single test
picks one of each.

**Input generators** choose the input, and differ by the steering signal (the
Generative subtree of the [input axis](https://quality.stereobooster.com/input.md)):

- Random: [property-based testing](https://quality.stereobooster.com/property-based-testing.md) samples
  from a generator or schema.
- Coverage feedback: [fuzzing](https://quality.stereobooster.com/fuzzing.md) mutates inputs steered by
  coverage (raw bytes); [automated test generation](https://quality.stereobooster.com/automated-test-generation.md)
  runs the same feedback loop as a fitness-guided search over structured call sequences.
- Solver: [symbolic execution](https://quality.stereobooster.com/symbolic-execution.md) derives an input
  that reaches a chosen path.
- Systematic: [combinatorial testing](https://quality.stereobooster.com/combinatorial-testing.md) builds a
  covering array over every t-way combination.

**Oracle suppliers** provide the verdict when no expected value is written:

- [Metamorphic testing](https://quality.stereobooster.com/metamorphic-testing.md) checks a relation between
  the outputs of two related inputs.
- Differential testing compares against a
  trusted second implementation.

Pick one generator and one oracle: they compose. A coverage-guided fuzzer that checks a
metamorphic relation is fuzzing and metamorphic at once. (The written-answer end, where
the author picks rows and answers by hand, is [example / parameterized
tests](https://quality.stereobooster.com/example-tests.md).)

**Differential oracle**

These all answer the same question — *does the candidate match a trusted
reference?* — and differ in how rigorously you compare, and in what the
reference is. By rigour:

- [Equivalence checking](https://quality.stereobooster.com/equivalence-checking.md) — *prove* they
  agree on every input.
- Differential testing — *test* them on
  sampled inputs before release.
- [Parallel run](https://quality.stereobooster.com/parallel-run.md) — *observe* them side by side
  on live production traffic.

The reference itself varies too: a trusted implementation (a peer, the previous
version, a gold-standard library), or a deliberately simple [executable
spec](https://quality.stereobooster.com/executable-specifications.md) authored to *be* the
reference.

## Classification

- **Quality dimensions:** Functionality, Security (when one side is a security-hardened reference).
- **Area:** Compilers, databases, crypto libraries, numerical and ML kernels; ports and rewrites with the predecessor as oracle.
- **Guarantee:** Empirical — relative correctness only; as strong as the reference A and the input distribution.

## Referenced by

- [Quality dimensions](https://quality.stereobooster.com/quality-dimensions.md) · Quality dimensions
- [Effect scope](https://quality.stereobooster.com/effect.md) · The axes
- [The axes](https://quality.stereobooster.com/axes.md) · The axes
- [Automated test generation](https://quality.stereobooster.com/automated-test-generation.md) · Methods
- [Equivalence checking](https://quality.stereobooster.com/equivalence-checking.md) · Methods
- [Example tests](https://quality.stereobooster.com/example-tests.md) · Methods
- [Formal methods](https://quality.stereobooster.com/formal.md) · Methods
- [Metamorphic testing](https://quality.stereobooster.com/metamorphic-testing.md) · Methods
- [Parallel run](https://quality.stereobooster.com/parallel-run.md) · Methods
- [Snapshot and approval testing](https://quality.stereobooster.com/snapshot-testing.md) · Methods
- [Testing machine-learning systems](https://quality.stereobooster.com/testing-ml-systems.md) · Methods
- [Verifying numerical code](https://quality.stereobooster.com/numbers.md) · Methods
- [Verifying time and date handling](https://quality.stereobooster.com/time-and-date.md) · Methods
- [How AI fits into software quality](https://quality.stereobooster.com/ai.md) · AI
- [Choosing methods](https://quality.stereobooster.com/choosing.md) · Overview

## References

[^yang2011]: Yang, Xuejun, Yang Chen, Eric Eide, and John Regehr. 2011. "[Finding and Understanding Bugs in C Compilers](https://users.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf)." *Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '11)*, 283–94. <https://doi.org/10.1145/1993498.1993532>.
[^rigger2020]: Rigger, Manuel, and Zhendong Su. 2020. "[Testing Database Engines via Pivoted Query Synthesis](https://www.usenix.org/system/files/osdi20-rigger.pdf)." *Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20)*. <https://doi.org/10.48550/arXiv.2001.04174>.
[^erbsen2019]: Erbsen, Andres, Jade Philipoom, Jason Gross, Robert Sloan, and Adam Chlipala. 2019. "[Simple High-Level Code for Cryptographic Arithmetic: With Proofs, Without Compromises](https://dspace.mit.edu/bitstreams/77b6c2d1-49af-427f-a5a7-bf393f3bd5de/download)." *IEEE Symposium on Security and Privacy (s&p '19)*, 1202–19. <https://doi.org/10.1109/SP.2019.00005>.
[^leroy2009]: Leroy, Xavier. 2009. "[Formal Verification of a Realistic Compiler](https://xavierleroy.org/publi/compcert-CACM.pdf)." *Communications of the ACM* 52 (7): 107–15. <https://doi.org/10.1145/1538788.1538814>.

## Acronyms

- SIMD — single instruction, multiple data
- ULP — unit in the last place