What is delta debugging?

What is delta debugging?

Delta debugging is an automated technique that shrinks a failing input or set of changes, keeping each cut that still fails and undoing the rest. A script reruns the test after each cut. Every part of the result is needed for the failure. Delta debugging is one method of test case reduction, also called test case minimization.

Andreas Zeller introduced delta debugging in 1999 to find the code changes that cause a failure. With Ralf Hildebrandt, he set out the method for failing input in a 2002 paper, which calls its minimizing algorithm ddmin. The paper's abstract says the algorithm "simplifies some failing test case to a minimal test case that still produces the failure." Here minimal means 1-minimal, so removing any single remaining part makes the failure go away. In the paper, ddmin reduced an HTML page that crashed the Mozilla browser during printing to the text <SELECT>.

Delta debugging automates the step of debugging that cuts a failing case down to a minimal reproducible example. A person does the same work by hand when no script can check each cut. The small case is quicker to read, and it can become a regression test after the fix.

How does delta debugging work?

Delta debugging needs a failing input that splits into parts, e.g. lines, and a test that can run any subset. The test returns one of three outcomes:

• Fail. The subset still shows the original failure.
• Pass. The subset runs without the failure.
• Unresolved. The subset cannot be tested, e.g. it no longer parses.

The ddmin algorithm then repeats these steps:

1. The algorithm splits the input into n parts of about equal size, starting with n = 2.
2. The algorithm reruns the test with each part removed in turn. The paper's version also tests each part alone.
3. If a smaller input fails, the algorithm keeps it, and n goes down or stays the same.
4. If none fails, the algorithm doubles n, up to the number of elements.
5. When no single element can be removed, the algorithm stops.

When one element causes the failure and each subset that holds it fails, the number of runs grows with the logarithm of the input's size, as in a binary search.

Other reducers cut and rerun differently:

• Source files. C-Reduce reduces C and C++ programs, e.g. one that crashes a compiler. With its --not-c option, it also reduces files in other languages.
• Fuzz inputs. Fuzzing tools can reduce crashing inputs in a separate run, e.g. libFuzzer with -minimize_crash=1. Teams keep the reduced inputs when they turn fuzz findings into tests.
• Generated inputs. Property-based testing frameworks shrink failing inputs. Hypothesis reruns its generator with simpler choices.
• Python calls. The Debugging Book publishes ddmin and a DeltaDebugger class that reduces a failing Python call's arguments.

What is an example of delta debugging?

Here is an illustrative example. A developer at Acme Co. asked a coding agent to "Let customers edit their delivery address during checkout." A browser recording of 8 actions ends in the bug. The address saved, but the cart emptied.

Actions 1 to 4 open the home page, search, add an Oak Chair, and view the cart. Actions 5 to 8 add a Pine Table, start checkout, set the address to 12 Elm Street, and view the order summary. The developer reduces the recording:

1. The developer writes a test function that replays actions against a local test store. It returns FAIL when the cart lacks an added item, and UNRESOLVED when an action cannot run.
2. First, ddmin checks that the full recording fails. Run 1 keeps actions 5 to 8 and still fails, so actions 1 to 4 go.
3. Run 2 keeps actions 7 and 8, which cannot run before checkout. Run 3 keeps actions 5 and 6, which pass.
4. Runs 4 to 7 each remove one action. Only removing the order summary still fails.
5. Runs 8 to 10 remove each remaining action, and none fails.

from debuggingbook.DeltaDebugger import ddmin, PASS, FAIL, UNRESOLVED
from acme_replay import replay, ReplayError  # Acme's test helper

def test(actions):
    try:
        cart = replay(actions)  # runs the actions against a local test store
    except ReplayError:  # e.g. an address change before checkout starts
        return UNRESOLVED
    added = [a.removeprefix("add ") for a in actions if a.startswith("add ")]
    missing = set(added) - set(cart.items)  # added items the cart lost
    return FAIL if missing else PASS

print(ddmin(test, RECORDED))  # RECORDED holds the 8 recorded actions

The script prints the 1-minimal recording:

['add pine-table', 'start checkout', 'set address 12 Elm Street']

The result points at the agent's address change. This example is simplified. A real recording can hold hundreds of actions, and each run can take seconds.

What changes when a coding agent writes the code?

When a coding agent runs a reduction, it can write the test function too, and the result is only as exact as that function. A loose test function can return FAIL on any exception, not only on the reported failure. The reducer then keeps any cut that still raises one, e.g. a recording so short that the replay crashes. The fix that follows targets a bug that no customer hit.

Test reduction research calls this drift slippage. The Debugging Book's DeltaDebugger guards against it. It counts a run as failing only when the exception has the original type and message, and any other exception is unresolved. The Acme test function avoids the drift too, because it checks the cart rather than any error.

A practical adjustment is to write the test function from the bug report before the agent starts. Match the exact failure, keep the function in a file the agent does not edit, and rerun the full reproduction steps after the fix.

What are the limits of delta debugging?

Delta debugging depends on its test and on the shape of the input. Most other reducers share these limits:

• The test must repeat. If the same subset sometimes passes and sometimes fails, the algorithm keeps or drops parts by chance. The Debugging Book warns that such a test gives "random results."
• Cuts break structure. Removing lines from source code or JSON usually leaves text that does not parse. Those runs come back unresolved, so the search slows down and the result can stay large. Hierarchical delta debugging cuts along the input's syntax tree, and C-Reduce adds transformations for C and C++ code.
• Runs cost time. Each run may build the software or start a browser. In the worst case, when nearly every run is unresolved, the number of runs grows with the square of the input's size.
• Small is not the smallest. A 1-minimal case can still shrink when two parts are removed at once.
• A small case is not a cause. The reduced case shows what the failure needs, not which line of code is wrong.

How is delta debugging different from git bisect?

Git bisect searches an ordered history of commits for the first one where a check fails, and it cannot split a commit. Delta debugging searches an unordered set of parts, e.g. the hunks of one diff, for a small subset that still fails. Zeller and Hildebrandt's second algorithm, dd, is closer to bisect. Like bisect, it starts from a passing case and a failing one and narrows the difference between them.

The two work together. Bisect names the commit, and delta debugging can then test subsets of that commit's changes. Changes that depend on each other often do not build apart, so those subsets come back unresolved. The two kinds of test script read exit codes in opposite ways. In git bisect run, 0 marks a commit good, while C-Reduce's test script exits 0 when the reduced file still shows the bug.

FAQs

What is the ddmin algorithm?

The ddmin algorithm is the minimizing delta debugging algorithm that Zeller and Hildebrandt published. It splits a failing input into parts and reruns the test with each part removed. It keeps any smaller input that still fails and splits finer until no single part can be removed.

How is delta debugging different from shrinking?

Delta debugging and shrinking both look for a smaller input that still fails. Delta debugging cuts parts without knowing what they mean, so it works on any input that splits into parts, e.g. the lines of a file. Shrinking is the step in property-based testing that reduces a generated input with the framework's rules for its type or generator.

Which tools reduce failing test cases automatically?

Tools that reduce failing test cases include C-Reduce, which reduces C and C++ source files. Fuzzers, e.g. libFuzzer, can reduce the crashing inputs they find in a separate run, and property-based testing frameworks shrink failing inputs. The Debugging Book publishes ddmin as Python code for other inputs.

Can delta debugging find the change that caused a bug?

Delta debugging can find a small set of changes that causes a bug, when a script can test the old version with only some changes applied. Changes that depend on each other often fail to build apart, so the result can stay large. Git bisect usually names the commit first.