The best bug reports often look suspiciously small.

input: 12 lines
expected: no crash
actual: crash

That smallness is not cosmetic. A tiny failing input is a compressed argument. It says: the failure is not hiding in the rest of the program, the rest of the file, the rest of the workload, or the rest of the weekend.

The hard part is that failures rarely arrive tiny. They arrive as generated C programs, browser sessions, serialized requests, traces, notebooks, ASTs, emails, configuration bundles, and fuzz inputs. The first artifact proves the bug exists. The reduced artifact makes the bug negotiable.

Delta debugging is the little machine that performs that negotiation.

The Reducer Has One Question

Zeller and Hildebrandt’s 2002 delta debugging paper begins from a simple premise: given a failing test case, find which circumstances are responsible for the failure.1 Their ddmin algorithm treats the input as a set or sequence of removable changes and repeatedly asks one question:

if I keep or remove this chunk,
does the interesting failure still happen?

The answer comes from a test function. In practice that function might compile a file, replay a browser session, run a differential test, check a sanitizer trace, or compare an assertion. For the algorithm, the oracle only needs to return three kinds of information:

FAIL        the same interesting failure still happens
PASS        the failure is gone
UNRESOLVED  the candidate cannot be judged

UNRESOLVED matters. If deleting half a C program leaves a syntactically invalid fragment, the compiler crash did not disappear in a meaningful way. You asked a malformed question.

The classic loop is almost rude in its simplicity:

  1. Split the current failing input into n chunks.
  2. If a chunk alone still fails, keep that chunk.
  3. Otherwise, if removing a chunk still fails, drop that chunk.
  4. Otherwise, increase n and ask finer questions.
  5. Stop when every single remaining atom is individually necessary.

The last sentence is the contract. ddmin aims for a 1-minimal failing input: remove any one remaining atom and the failure no longer reproduces. That is not the same as “smallest possible input.” It is a local certificate under the questions the reducer happened to ask.

A Small Reducer Lab

The lab below runs an exact implementation of ddmin and, for structured inputs, a small tree-aware reducer in the style of hierarchical delta debugging.2 It is deterministic: every number shown comes from the JavaScript shipped with this post.

Try the Two independent bugs case first. In the natural order, flat ddmin returns a five-atom witness. Exhaustive search over the same 16 atoms finds a two-atom witness. That is not a bug in the algorithm; it is the difference between 1-minimal and globally minimum. Now switch Atom order to Short witness first. The reducer finds the two-atom witness because its first successful questions lead into a different basin.

Then switch to Structured input. Flat deletion spends most of its time asking invalid questions. The tree-aware reducer removes whole syntactic regions first, then trims inside the surviving regions while preserving the syntax shell.

Minimal Is Not Minimum

The Two independent bugs case is the trap I want people to remember.

The original input contains two unrelated failure recipes:

five atoms reproduce bug A
two atoms reproduce bug B

In natural order, ddmin first finds a failing half that contains the five-atom recipe. From then on it reduces inside that half. The final five atoms are 1-minimal: remove any one and bug A is gone. But the whole original input still contained a smaller bug B witness that the reducer discarded early.

This is not a condemnation of delta debugging. It is a warning about what its certificate means.

If you need the absolute smallest witness, exhaustive search is the obvious definition and the impossible method. Even in the tiny lab, exhaustive search is only enabled for small cases. Real reducers survive by using a cheaper contract:

small enough to understand
still reproduces the interesting failure
locally irreducible under the reducer's atoms

That contract is often exactly what a maintainer needs.

The Oracle Is Part of the Algorithm

The reducer is only as good as its test function.

A poor oracle answers the wrong question:

does the program crash?

A better oracle asks:

does the same interesting failure still happen?

Those are different. A reduced input that triggers a parser error instead of the optimizer crash is not a successful reduction. A C program whose behavior depends on undefined behavior is not a clean compiler bug report. A flaky test that fails one time in ten is not the same object as a deterministic failure.

This is why practical reducers are full of domain checks. Regehr, Chen, Cuoq, Eide, Ellison, and Yang made this explicit in their PLDI 2012 work on C compiler test-case reduction: validity is part of the problem, not a cleanup step after minimization.3 Their C-Reduce line of work did not merely delete text; it used transformations and checks designed to keep the reduced C program suitable for a real compiler bug report.

The lab’s Structured input case is a cartoon of the same issue. Flat deletion can remove an opening syntax token while keeping the body. The test function returns UNRESOLVED, because that candidate is not a meaningful question about the original bug. The tree-aware reducer avoids those questions by deleting subtrees first.

The machine is not just:

search over subsets

It is:

search over meaningful variants

Why Halves Work So Well

The magic is not that halving always guesses the culprit. It usually does not. The magic is that a failed coarse question still tells you how to spend the next question.

Suppose removing a half keeps the failure. You just deleted a large irrelevant region. Suppose no half works. Then maybe the failure is scattered, so you raise the granularity and try smaller pieces. The algorithm alternates between optimism and humility:

maybe the bug is concentrated
maybe the bug is distributed
ask cheaply, then adapt

Zeller and Hildebrandt’s paper includes case studies where large browser and fuzzing inputs shrink dramatically, including a Mozilla HTML crash reduced to a single relevant line in their experiment.1 That empirical punchline is easy to misread as “divide and conquer finds the cause.” The subtler lesson is that the reducer turns an expensive human search into a sequence of executable questions.

The ordering of those questions still matters. In the lab’s optimizer case, the same four-token witness is found under all displayed orders, but the number of tests changes. In the independent-bug case, the output itself changes. A real reducer can exploit this by trying likely chunks first, preserving syntax, using passes that understand the language, and caching every test result.

What I Would Want in a Real Reducer

For a production reducer, I would want five boring things before I wanted one clever thing.

First, the oracle should fingerprint the failure. Exit code is usually too weak. Stack signature, assertion text, sanitizer category, differential output, and minimized nondeterminism are all part of the contract.

Second, the reducer should cache aggressively. Re-running the same candidate is common once complements and finer granularities interact.

Third, the atomization should match the artifact. Lines are fine for logs. Tokens are better for source. AST nodes are better still when syntax validity matters. For structured inputs, Misherghi and Su’s HDD result is the right instinct: use the tree you already have.2

Fourth, the reducer should report its own uncertainty. “1-minimal under these atoms” is more honest than “minimal.”

Fifth, every reduced witness should be treated as a bug-report artifact, not as the explanation itself. A tiny input can focus attention. It cannot prove which line in the implementation is wrong.

The final witness is a good suspect. The trial still has to happen.

The Small Print I Trust

The lab exports the same functions used by the page. Its audit checks:

  • the original cases fail;
  • flat ddmin returns failing 1-minimal outputs;
  • the monotone optimizer case shrinks from 20 atoms to 4 triggers;
  • the independent-bug case has a 5-atom 1-minimal result while exhaustive search finds a 2-atom global witness;
  • changing the order can expose that shorter witness;
  • the structured case produces unresolved flat tests;
  • the tree-aware reducer produces zero unresolved candidates on that case.

On the default independent-bug case, the relevant facts are:

{
  "atoms": 16,
  "flatSize": 5,
  "flatTests": 30,
  "flatOneMinimal": true,
  "globalSize": 2
}

That is the whole lesson in miniature. A reducer is not an oracle of truth. It is a disciplined way to ask the failure what it can live without.

  1. Andreas Zeller and Ralf Hildebrandt, “Simplifying and Isolating Failure-Inducing Input”, IEEE Transactions on Software Engineering, 2002. ↩ ↩2

  2. Ghassan Misherghi and Zhendong Su, “HDD: Hierarchical Delta Debugging”, International Conference on Software Engineering, 2006. ↩ ↩2

  3. John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang, “Test-Case Reduction for C Compiler Bugs”, Programming Language Design and Implementation, 2012. ↩