Isolating cause-effect chains from computer programs
Andreas Zeller · 2002
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 passing 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 program 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 addition operator in the intermediate RTL representation; this caused a cycle in the RTL tree---and this caused the compiler to crash."
Cited by 530 works. doi:10.1145/587051.587053
Authors
References
- Algorithm 457: finding all cliques of an undirected graph
- Algorithmic Program Debugging
- Programmers use slices when debugging
- Dynamically discovering likely program invariants to support program evolution
- Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria
- Dynamic program slicing
- Simplifying and isolating failure-inducing input
- A Survey of Program Slicing Techniques.
- A safe, efficient regression test selection technique
- Tracking down software bugs using automatic anomaly detection