Skip to content

Software Quality

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 and property-based testing 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 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; observe them on live traffic instead of an offline generator and it is a parallel run, 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 (Yang et al. 2011)1 — generates random valid C programs and compares their behavior across compilers.
  • YarpGen — Csmith's successor for C/C++; generates programs that exercise miscompilation patterns the authors found Csmith missed.
  • fuzzilli — JavaScript engine fuzzing; differential against multiple JS engines.

Databases

  • SQLancer (Rigger and Su 2020)2 — differential and metamorphic oracles for SQL engines. It has found bugs in SQLite, MySQL, PostgreSQL, CockroachDB, TiDB, and DuckDB; the running bug ledger is public.

Crypto

  • Wycheproof (Google) — test vectors generated against reference implementations; runs differentially against any candidate library.
  • fiat-crypto (Erbsen et al. 2019)3 — 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 (Python), fast-check (TS), proptest (Rust) — any property-based testing framework runs a differential oracle trivially: assert ref(x) == impl(x) is the entire property.
  • Atheris, libFuzzer, AFL++ — 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 or metamorphic testing 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)1.
  • SQLancer reported 123 bugs across three mature DBMSs — SQLite, MySQL, and PostgreSQL — 99 of them fixed or verified (Rigger and Su 2020)2.
  • The CompCert outlier: Csmith found no wrong-code bugs in its formally verified middle-end (Leroy 2009; Yang et al. 2011)4 1 — a benchmark for what verification (the reference side) can achieve.

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):

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

  • Metamorphic testing 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.)

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 — prove they agree on every input.
  • Differential testing — test them on sampled inputs before release.
  • Parallel run — 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 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

References

  1. Yang, Xuejun, Yang Chen, Eric Eide, and John Regehr. 2011. "Finding and Understanding Bugs in C Compilers." Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '11), 283–94. https://doi.org/10.1145/1993498.1993532. ↩↩↩

  2. Rigger, Manuel, and Zhendong Su. 2020. "Testing Database Engines via Pivoted Query Synthesis." Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20). https://doi.org/10.48550/arXiv.2001.04174. ↩↩

  3. Erbsen, Andres, Jade Philipoom, Jason Gross, Robert Sloan, and Adam Chlipala. 2019. "Simple High-Level Code for Cryptographic Arithmetic: With Proofs, Without Compromises." IEEE Symposium on Security and Privacy (s&p '19), 1202–19. https://doi.org/10.1109/SP.2019.00005. ↩

  4. Leroy, Xavier. 2009. "Formal Verification of a Realistic Compiler." Communications of the ACM 52 (7): 107–15. https://doi.org/10.1145/1538788.1538814. ↩