Towards locating execution omission errors

ABSTRACT

Execution omission errors are known to be difficult to locate using dynamic analysis. These errors lead to a failure at runtime because of the omission of execution of some statements that would have been executed if the program had no errors. Since dynamic analysis is typically designed to focus on dynamic information arising from executed statements, and statements whose execution is omitted do not produce dynamic information, detection of execution omission errors becomes a challenging task. For example, while dynamic slices are very effective in capturing faulty code for other types of errors, they fail to capture faulty code in presence of execution omission errors. To address this issue relevant slices have been defined to consider certain static dependences (called potential dependences) in addition to dynamic dependences. However, due to the conservative nature of static analysis, overly large slices are produced. In this paper, we propose a fully dynamic solution to locating execution omission errors using dynamic slices. We introduce the notion of implicit dependences which are dependences that are normally invisible to dynamic slicing due to the omission of execution of some statements. We design a dynamic method that forces the execution of the omitted code by switching outcomes of relevant predicates such that those implicit dependences are exposed and become available for dynamic slicing. Dynamic slices can be computed and effectively pruned to produce fault candidate sets containing the execution omission errors. We solve two main problems: verifying the existence of a single implicit dependence through predicate switching, and recovering the implicit dependences in a demand driven manner such that a small number of verifications are required before the root cause is captured. Our experiments show that the proposed technique is highly effective in capturing execution omission errors.

REFERENCES

• 1: http://www.cse.unl.edu/~galileo/sir.
• 2: http://www.elis.ugent.be/diablo/.
• 3: 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
• 4: 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]
• 5: Mary Jean Harrold , Gregg Rothermel , Rui Wu , Liu Yi, An empirical investigation of program spectra, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.83-90, June 16-16, 1998, Montreal, Quebec, Canada
• 6: Matthias Hauswirth , Trishul M. Chilimbi, Low-overhead memory leak detection using adaptive statistical profiling, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 7: 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]
• 8: 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]
• 9: 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
• 10: Chao Liu , Xifeng Yan , Long Fei , Jiawei Han , Samuel P. Midkiff, SOBER: statistical model-based bug localization, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 11: Manos Renieris and Steven Reiss. Fault localization with nearest neighbor queries. In ASE '03: Proceedings of the IEEE/ACM International Conference on Automated Software Engineering, pages 30--39, Montreal, Canada, 2003.
• 12: Gregg Rothermel , Mary Jean Harrold, Empirical Studies of a Safe Regression Test Selection Technique, IEEE Transactions on Software Engineering, v.24 n.6, p.401-419, June 1998 [doi>10.1109/32.689399]
• 13: Joseph R. Ruthruff , Margaret Burnett , Gregg Rothermel, An empirical study of fault localization for end-user programmers, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062523]
• 14: J. Seward and N. Nethercote. Valgrind, an open-source memory debugger for x86-gnu/linux. In http://valgrind.kde.org/.
• 15: Tao Wang , Abhik Roychoudhury, Using Compressed Bytecode Traces for Slicing Java Programs, Proceedings of the 26th International Conference on Software Engineering, p.512-521, May 23-28, 2004
• 16: Tao Wang , Abhik Roychoudhury, Automated path generation for software fault localization, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101966]
• 17: 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]
• 18: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Locating faults through automated predicate switching, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134324]
• 19: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Pruning dynamic slices with confidence, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 20: 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]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers

General Terms:
Algorithms, Measurement, Reliability

Keywords:
debugging, execution omission, implicit dependence, potential dependence, predicate switching, relevant slicing