Locating faulty code using failure-inducing chops

ABSTRACT

Software debugging is the process of locating and correcting faulty code. Prior techniques to locate faulty code either use program analysis techniques such as backward dynamic program slicing or exclusively use delta debugging to analyze the state changes during program execution. In this paper, we present a new approach that integrates the potential of delta debugging algorithm with the benefit of forward and backward dynamic program slicing to narrow down the search for faulty code. Our approach is to use delta debugging algorithm to identify a minimal failure-inducing input, use this input to compute a forward dynamic slice and then intersect the statements in this forward dynamic slice with the statements in the backward dynamic slice of the erroneous output to compute a failure-inducing chop. We implemented our technique and conducted experiments with faulty versions of several programs from the Siemens suite to evaluate our technique. Our experiments show that failure-inducing chops can greatly reduce the size of search space compared to the dynamic slices without significantly compromising the capability to locate the faulty code. We also applied our technique to several programs with known memory related bugs such as buffer overflow bugs. The failure-inducing chop in several of these cases contained only 2 to 4 statements which included the code causing memory corruption.

REFERENCES

• 1: 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
• 2: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• 3: Hiralal Agrawal , Joseph R. Horgan , Edward W. Krauser , Saul London, Incremental Regression Testing, Proceedings of the Conference on Software Maintenance, p.348-357, September 01, 1993
• 4: H. Agrawal, J. Horgan, S. London, and W. Wong, "Fault localization using execution slices and dataflow tests," Sixth IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 143--151, 1995.
• 5: AskIgor, Automated Debugging Service. http://www.st.cs.uni-sb.de/askigor/
• 6: Árpád Beszedes , Tamás Gergely , Zsolt Mihály Szabó , Janos Csirik , Tibor Gyimothy, Dynamic Slicing Method for Maintenance of Large C Programs, Proceedings of the Fifth European Conference on Software Maintenance and Reengineering, p.105, March 14-16, 2001
• 7: Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062522]
• 8: Diablo Is A Better Link-time Optimizer. http://www.elis.ugent.be/diablo/
• 9: 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
• 10: 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]
• 11: M. J. Harrold,, G. Rothermel, K. Sayre, R. Wu, and L. Yi, "An empirical investigation of the relationship between spectra differences and regression faults,"Journal of Software Testing Verification and Reliability, 10(3):171--194, 2000.
• 12: H. He and N. Gupta, "Automated Debugging using Path-Based Weakest Preconditions," Fundamental Approaches to Software Engineering (FASE), ETAPS Joint Conference, Barcelona, Spain, March 29--31, 2004.
• 13: http://www.cse.unl.edu/~galileo/sir
• 14: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 15: Information Week, Issue on Software Quality, Jan 21, 2002.
• 16: 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]
• 17: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3 ]
• 18: B. Korel and J. Rilling, "Application of dynamic slicing in program debugging," 3rd International Workshop on Automatic Debugging (AADEBUG), Linkoping, 1997.
• 19: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 20: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 21: M. Renieris and S. Reiss, "Fault localization with nearest neighbor queries,"Automated Software Engineering (ASE), 2003.
• 22: The Unravel Project. http://hissa.nist.gov/unravel/
• 23: Valgrind. http://valgrind.org/
• 24: M. Weiser, "Program slicing," IEEE Transactions on Software Engineering (TSE), Vol. SE-10, No. 4, pages 352--357, 1982.
• 25: Yichen Xie , Dawson Engler, Using redundancies to find errors, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587060]
• 26: Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587053]
• 27: Andreas Zeller, Yesterday, my program worked. Today, it does not. Why?, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.253-267, September 06-10, 1999, Toulouse, France
• 28: 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 ]
• 29: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Precise dynamic slicing algorithms, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 30: Xiangyu Zhang , Rajiv Gupta , Youtao Zhang, Efficient Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams, Proceedings of the 26th International Conference on Software Engineering, p.502-511, May 23-28, 2004
• 31: Xiangyu Zhang , Haifeng He , Neelam Gupta , Rajiv Gupta, Experimental evaluation of using dynamic slices for fault location, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.33-42, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085135]
• 32: Xiangyu Zhang , Rajiv Gupta, Cost effective dynamic program slicing, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 33: Pin Zhou , Wei Liu , Long Fei , Shan Lu , Feng Qin , Yuanyuan Zhou , Samuel Midkiff , Josep Torrellas, AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.269-280, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.3]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing); Tracing; Debugging aids

General Terms:
Algorithms, Measurement, Reliability, Verification

Keywords:
automated debugging, backward dynamic, failure-inducing input, forward dynamic program slicing, program slicing