Isolating cause-effect chains from computer programs

Abstract—Consider the execution of a failing program as a sequence of program states. Each state induces the following state, up to the failure. Which variables and values of a program state are relevant for the failure? We show how the Delta Debugging algorithm isolates the relevant variables and values by systematically narrowing the state difference between a pass-ing run and a failing run—by assessing the outcome of altered executions to determine wether a change in the program state makes a difference in the test outcome. Applying Delta Debugging to multiple states of the pro-gram automatically reveals the cause-effect chain of the failure—that is, the variables and values that caused the failure. In a case study, our prototype implementation successfully isolated the cause-effect chain for a failure of the GNU C compiler: “Initially, the C program to be compiled contained an addition of 1.0; this caused an addi-tion operator in the intermediate RTL representation; this caused a cycle in the RTL tree—and this caused the compiler to crash. ” The prototype im-plementation is available as a public Web service, where anyone can submit programs to be debugged automatically. Index Terms—automated debugging, program analysis, testing tools, combinatorial testing, diagnostics, tracing. I