Isolating Cause-Effect Chains from Computer Programs
Andreas Zeller

Lehrstuhl für Softwaretechnik (Prof. Zeller)
Universität des Saarlandes – Informatik
Informatik Campus des Saarlandes
Campus E9 1 (CISPA)
66123 Saarbrücken
E-mail: zeller @
Telefon: +49 681 302-70970

Deutschsprachige Startseite Page d'acceuil en franšais English home page
   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).


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."


Automated debugging, program analysis, combinatorial testing, tracing


  1. Introduction
  2. Isolating Relevant Input
    • A "Trial and Error" Approach
    • Delta Debugging
  3. Isolating Relevant States
    • Accessing and Comparing States
    • Memory Graphs
    • Isolating the GCC Cause-Effect Chain
      • At main
      • At combine_instructions
      • At if_then_else_cond
    • The GCC Cause-Effect Chain
  4. Isolating the Error
  5. Why does this work? And when does this work?
  6. Related Work
    • Program Slicing
    • Detecting Anomalies
    • The Debugging Process
    • Testing for Debugging
  7. Conclusion and Consequences
  8. References


See Also...

<> · · Stand: 2017-01-03 21:10