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 two must agree or, where outputs can be ranked, the new one must do at least as well. 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 built to one spec disagree once one of them drifts, and two SQL engines that both claim ANSI compliance return different results for some queries.
  • 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 play each new version against the previous version over many thousands of games, and the check is same or better: the new version must not lose rating across the match, decided by a statistical test rather than a per-game pass/fail. The pattern generalizes to any ranked or scored system where new vs old can play each other.
  2. Cross-language port verification. A library reimplemented in a new language is tested by calling the original from the new code and diffing the outputs. The oracle is the trusted prior implementation. The pattern works for language runtimes, business-logic migrations (Java → Go rewrite), and ML training-vs-inference parity checks.
  3. Scalar → SIMD (or → GPU) optimization. The plain scalar version of an algorithm is the oracle for its hand-written SIMD version, and the test diffs the two on the same inputs. SIMD libraries that keep a scalar fallback beside the vectorized path (CRoaring, simdjson) already have the reference. The same pattern covers 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 real requests. 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 — generates C and C++ programs that exercise miscompilation patterns.
  • fuzzilli — coverage-guided JavaScript engine fuzzer whose own oracle is a crash; differential extensions of it compare an engine's interpreter against its own JIT compiler.

Databases

  • SQLancer — finds logic bugs in one SQL engine at a time, because a differential oracle needs systems that implement the same semantics for a given input and SQL dialects diverge (Rigger and Su 2020)2. It has found bugs in SQLite, MySQL, PostgreSQL, CockroachDB, TiDB, and DuckDB; the running bug ledger is public.

Crypto

  • Wycheproof (Google) — test vectors for known attacks, each carrying its expected result, so a candidate library is checked against recorded answers rather than against a live second implementation.
  • fiat-crypto — generates C code for elliptic-curve field arithmetic with machine-checked proofs of functional correctness, and BoringSSL replaced existing specialized code with its output (Erbsen et al. 2019)3. On the reference side of a differential test, that code is proven correct rather than trusted by inspection.

Numerical / ML

  • The common pattern writes the operator twice — once in pure Python/NumPy, once in optimized CUDA/Triton — and asserts agreement under tolerance over a Hypothesis-generated input grid. The two-implementation comparison is standard practice inside PyTorch, JAX and TensorFlow, and needs no dedicated tool.

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 between two floating-point implementations is not guaranteed, so the comparison needs an explicit ULP bound.

Evidence

  • Csmith found 325+ previously unknown bugs in GCC, LLVM, and other C compilers over three years by comparing their outputs on generated programs (Yang et al. 2011)1.
  • The CompCert outlier: Csmith found no wrong-code bugs in its formally verified middle-end (Yang et al. 2011)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), Performance (when the compared score is speed or latency against a baseline).
  • Area: Compilers, databases, crypto libraries, numerical and ML kernels; ports and rewrites with the predecessor as oracle.
  • Guarantee: Empirical.

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. ↩