deltas[i])
if test(next_c_fail) == FAIL and n == 2:
c_fail = next_c_fail
n = 2; offset = 0; break
elif test(next_c_fail) == PASS:
c_pass = next_c_fail
n = 2; offset = 0; break
elif test(next_c_pass) == FAIL:
c_fail = next_c_pass
n = 2; offset = 0; break
elif test(next_c_fail) == FAIL:
c_fail = next_c_fail
n = max(n - 1, 2); offset = i; break
elif test(next_c_pass) == PASS:
c_pass = next_c_pass
n = max(n - 1, 2); offset = i; break
else:
j = j + 1
if j >= n:
if n >= len(delta):
return (delta, c_pass, c_fail)
else:
n = min(len(delta), n * 2)
Beautiful Debugging > Minimizing Input
28.6. Minimizing Input
The interesting thing about delta debugging (or any other automation of the scientific method) is that it is very general. Rather than search for causes in a set of changes, you can also search for causes in other search spaces. For instance, you can easily apply delta debugging to search for failure causes in program input, which Ralf Hildebrandt and I did in 2002.
When searching for causes in program input, the program code stays the same: no application of changes, no reconstruction, just execution. Instead, it is the input that changes. Think of a program that works on most inputs, but fails on one specific input. One can easily have delta debugging isolate the failure-inducing difference between the two inputs: "The cause of the web browser crashing is the tag in line 40."One can also modify the algorithm so that it returns a minimized input: "To have the web browser crash, just feed it a web page containing ." In minimized input, every single remaining character is relevant for the failure to occur. Minimized inputs can be very valuable for debuggers because they make things simple: they lead to shorter executions and smaller states to be examined. As an important (and perhaps beautiful) side effect, they capture the essence of the failure.I once met some programmers who were dealing with bugs in a third-party database. They had very complex, machine-generated SQL queries that sometimes would cause the database to fail. The vendor did not categorize these bugs as high priority because "you are our only customer dealing with such complex queries." Then the programmers simplified a one-page SQL query to a single line that still triggered the failure. Faced with this single line, the vendor immediately gave the bug the highest priority and fixed it.
How does one achieve minimization? The easiest way is to feed dd() with an empty c_pass, and to have a passing test return "pass" only if the input is empty, and "unresolved" otherwise. c_pass remains unchanged while c_fail becomes smaller and smaller with each failing test.
Again, all that is required to isolate such failure causes is an automated test and a means to split the input into smaller pieces—that is, a splitting function that has some basic knowledge about the syntax of the input.
Beautiful Debugging > Hunting the Defect
28.7. Hunting the Defect
In principle, delta debugging could also minimize an entire program code so as to keep only what is relevant. Suppose your web browser crashes while printing a HTML page. Applying delta debugging on the program code means that only the bare code required to reproduce the failure would remain. Doesn't this sound neat? Unfortunately, it would hardly work in practice. The reason is that the elements of program code are heavily dependent on each other. Remove one piece, and everything breaks apart. The chances of getting something meaningful by randomly removing parts are very slim. Therefore, delta debugging would almost certainly require a quadratic number of tests. Even for a 1,000-line program, this would already mean a million tests—and years and years of waiting. We never had that much time, so we never implemented that feat.
Nonetheless, we still wanted to hunt down failure causes not only in the input or the set of changes, but in the actual source code—in other words, we wanted to have the statements that caused the program to fail. (And, of course, we wanted