Isolating cause-effect chains from computer programs

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

REFERENCES

• 1: AskIgor web site. http://www.askigor.org/.
• 2: Delta debugging web site. http://www.st.cs.uni-sb.de/dd/.
• 3: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 4: H. G. Barrow and R. M. Burstall. Subgraph isomorphism, matching relational structures and maximal cliques. Information Processing Letters, 4(4):83-84, 1976.
• 5: Coen Bron , Joep Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, v.16 n.9, p.575-577, Sept. 1973 [doi>10.1145/362342.362367]
• 6: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 7: Tibor Gyimóthy , Árpád Beszédes , Istán Forgács, An efficient relevant slicing method for debugging, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.303-321, September 06-10, 1999, Toulouse, France
• 8: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 9: Michael Hind , Anthony Pioli, Which pointer analysis should I use?, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.113-123, August 21-24, 2000, Portland, Oregon, United States
• 10: Proc. International Conference on Software Engineering (ICSE), Orlando, Florida, May 2002.
• 11: Daniel Jackson , Eugene J. Rollins, A new model of program dependences for reverse engineering, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.2-10, December 06-09, 1994, New Orleans, Louisiana, United States
• 12: James A. Jones , Mary Jean Harrold , John Stasko, Visualization of test information to assist fault localization, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581397]
• 13: Bogdan Korel , Janusz Laski, Dynamic slicing of computer programs, Journal of Systems and Software, v.13 n.3, p.187-195, Nov. 1990 [doi>10.1016/0164-1212(90)90094-3]
• 14: J. R. Lyle and M. Weiser. Automatic program bug location by program slicing. In 2nd International Conference on Computers and Applications, pages 877-882, Peking, 1987. IEEE Computer Society Press, Los Alamitos, California.
• 15: Barbara G. Ryder , Frank Tip, Change impact analysis for object-oriented programs, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.46-53, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379661]
• 16: Ehud Yehuda Shapiro, Algorithmic program debugging, 1982
• 17: F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3):121-189, Sept. 1995.
• 18: Mark Weiser, Programmers use slices when debugging, Communications of the ACM, v.25 n.7, p.446-452, July 1982 [doi>10.1145/358557.358577]
• 19: David B. Whalley, Automatic isolation of compiler errors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1648-1659, Sept. 1994 [doi>10.1145/186025.186103]
• 20: A. Zeller. Automated Debugging. Morgan Kaufmann Publishers, Aug. 2003. To appear (ISBN 1-55860-866-4).
• 21: Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]
• 22: Thomas Zimmermann , Andreas Zeller, Visualizing Memory Graphs, Revised Lectures on Software Visualization, International Seminar, p.191-204, May 20-25, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Algorithms, Experimentation, Reliability, Verification

Keywords:
automated debugging, program comprehension, testing, tracing