Two questions come up with almost every regression failure. Which change broke it? The test passed last week, and 64 commits have landed since. And which part of the test matters? The failing random test is 200 stimulus steps long, most of them irrelevant. Both questions can be answered without understanding anything, by searching, and searching is something a computer does well.

How do you find which change broke it, and which part of the test matters?

The obvious answer, and why it breaks

The obvious approach reads the 64 commits and guesses, or stares at all 200 steps in the waveform. Both depend on luck and on expertise in code someone else wrote. A good-and-bad pair (a passing commit and a failing one, or a full test and an empty one) is all a mechanical search needs.

The idea: two searches

Build it: ddmin on a failing test

A 200-step failing test whose failure needs three particular steps, as in a sleep-and-wake bug: a packet, a long idle gap, then traffic on input 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

"""Delta debugging: shrinking a failing test to the few steps that matter.

A failing random test is a list of 200 stimulus steps (illustrative). The failure needs three
particular steps to be present, in their original order: a packet to output 2 (step 37), a
long idle gap (step 118) and a packet on input 3 (step 161), as in a sleep-and-wake bug. The
ddmin algorithm (fact M8) repeatedly removes chunks of the test, keeping any smaller test that
still fails. The model counts test runs and prints the size of the failing test as it shrinks.
"""
NEEDED = {37, 118, 161}
runs = 0
def fails(steps):
    global runs
    runs += 1
    return NEEDED <= set(steps)

def ddmin(steps):
    n, trace = 2, [(runs, len(steps))]
    while len(steps) >= 2:
        size = len(steps) // n
        chunks = [steps[i:i + size] for i in range(0, len(steps), size)]
        reduced = False
        for i in range(len(chunks)):
            complement = [s for j, c in enumerate(chunks) if j != i for s in c]
            if fails(complement):
                steps, n, reduced = complement, max(n - 1, 2), True
                trace.append((runs, len(steps)))
                break
        if not reduced:
            if n >= len(steps):
                break
            n = min(2 * n, len(steps))
    return steps, trace

test = list(range(200))
assert fails(test)
minimal, trace = ddmin(test)
print("test runs  failing test size")
for r, size in trace:
    print(f"{r:9d}  {size:17d}")
print(f"minimal failing test: steps {minimal} after {runs} runs")
assert set(minimal) == NEEDED and runs < 200
print(f"PASS: {runs} runs shrink a 200-step failure to the 3 steps that cause it")

It prints:

test runs  failing test size
        1                200
        5                150
        9                125
       12                100
       16                 75
       20                 63
       22                 51
       25                 39
       28                 26
       32                 20
       34                 14
       38                 11
       41                  8
       45                  6
       50                  5
       53                  4
       56                  3
minimal failing test: steps [37, 118, 161] after 59 runs
PASS: 59 runs shrink a 200-step failure to the 3 steps that cause it

How to read it: early runs remove large chunks quickly (half the test is gone after 12 runs); later runs remove single steps more slowly. After 59 runs only steps 37, 118 and 161 remain, and removing any one of them makes the failure disappear. A three-step reproduction is a debug problem a person can see whole.

Using both well

• Bisection needs reproducibility: the same test, seed and environment at every commit (lesson 13.2).

• Skip commits that do not build, and beware of failures that are intermittent: a flaky test misleads bisection.

• ddmin needs a test that can run a subset of its stimulus: transaction lists, instruction sequences, packet lists.

• Keep the failure's signature as the oracle, not just "fails": a different failure in a reduced test is not the same bug.

• Automate both in the regression system: the bisected commit and the reduced test arrive with the bug report.

How real teams automate it

What breaks

A team (illustrative) ran automatic test reduction with "the test fails" as its only check. The reduced tests often failed for a different reason than the original: a missing configuration step that caused an unrelated error. Engineers debugged the wrong bug from tidy-looking reproductions. Using the failure's signature as the condition kept reductions honest.

Key takeaways

• Bisection finds the breaking change in about log2(n) runs.

• Delta debugging shrinks a failing test to the steps that matter: 200 to 3 in 59 runs here.

• Both need reproducible runs and the failure's signature as the oracle; automate them.

Related topics

• Part 13 overview: Debug