Isolating Cause-Effect Chains
from Computer Programs
Software Engineering Chair (Prof. Zeller)
Saarland University – Computer Science
Campus E1 1
66123 Saarbrücken, Germany
E-mail: zeller @ cs.uni-saarland.de
Phone: +49 681 302-70970
Andreas Zeller. Isolating Cause-Effect
Chains from Computer Programs. Proc. ACM SIGSOFT
10th International Symposium on the Foundations of Software
Engineering (FSE-10), Charleston, South Carolina,
November 2002. Winner of the
ACM SIGSOFT Distinguished Paper Award.
"Cause-effect chains explain the causes of program failures automatically and effectively. All that is required is an automated test, two comparable program runs and a means to access the state of an executable program. Although relying on several test runs to prove causality, the isolation of cause-effect chains requires no manual interaction and thus saves valuable developer time." (Conclusion)
Get the paper in PDF format (580k, 10 pages).
AbstractConsider 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."
KeywordsAutomated debugging, program analysis, combinatorial testing, tracing
See Also...<email@example.com> · http://www.st.cs.uni-saarland.de/papers/fse2002/ · Updated: 2010-01-28 15:24