Dies ist ein Archiv des alten Softwaretechnik Lehrstuhls der Universität des Saarlandes. Es ist nicht länger aktuell.

  

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 @ cs.uni-saarland.de
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).

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

Contents

  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

Download

See Also...

Impressum ● Datenschutzerklärung

<webmaster@st.cs.uni-saarland.de> · http://www.st.cs.uni-saarland.de//papers/fse2002/?lang=fr · Stand: 2018-04-05 13:41