Isolating Cause-Effect Chains from Computer Programs
- SIGSOFT FSE 2002
by
Andreas Zeller
SIGSOFT '02/FSE-10: Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, Pages 1-10, ACM Press, New York, NY, USA, November 2002.
ISBN: 1581135149
Digital Library via DOI: 10.1145/587051.587053 - Local copy: Download as PDF file.
See also
More information is available at http://www.st.cs.uni-saarland.de/dd/.
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 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 narrowed down 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."
Keywords
- automated debugging
- program analysis
- combinatorial testing
- tracing
BibTeX Entry
@inproceedings{zeller-fse-2002, title = "Isolating Cause-Effect Chains from Computer Programs", author = "Andreas Zeller", year = "2002", month = nov, address = "New York, NY, USA", booktitle = "SIGSOFT '02/FSE-10: Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering", location = "Charleston, South Carolina, USA", pages = "1--10", publisher = "ACM Press", ISBN = "1581135149", doi = "10.1145/587051.587053", }