Statistical debugging using compound boolean predicates

ABSTRACT

Statistical debugging uses dynamic instrumentation and machine learning to identify predicates on program state that are strongly predictive of program failure. Prior approaches have only considered simple, atomic predicates such as the directions of branches or the return values of function calls. We enrich the predicate vocabulary by adding complex Boolean formulae derived from these simple predicates. We draw upon three-valued logic, static program structure, and statistical estimation techniques to efficiently sift through large numbers of candidate Boolean predicate formulae. We present qualitative and quantitative evidence that complex predicates are practical, precise, and informative. Furthermore, we demonstrate that our approach is robust in the face of incomplete data provided by the sparse random sampling that typifies postdeployment statistical debugging.

REFERENCES

• 1: 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]
• 2: N. Dodoo, A. Donovan, L. Lin, and M. D. Ernst. Selecting predicates for implications in program analysis, March 16, 2002. Draft. http://pag.csail.mit.edu/~mernst/pubs/invariants-implications.ps.
• 3: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically discovering likely program invariants to support program evolution, Proceedings of the 21st international conference on Software engineering, p.213-224, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302467]
• 4: Hyunsook Do , Sebastian Elbaum , Gregg Rothermel, Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact, Empirical Software Engineering, v.10 n.4, p.405-435, October 2005 [doi>10.1007/s10664-005-3861-2]
• 5: 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]
• 6: Murali Haran , Alan Karr , Michael Last , Alessandro Orso , Adam A. Porter , Ashish Sanil , Sandro Fouche, Techniques for Classifying Executions of Deployed Software to Support Software Engineering Tasks, IEEE Transactions on Software Engineering, v.33 n.5, p.287-304, May 2007 [doi>10.1109/TSE.2007.1004]
• 7: 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
• 8: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 9: James A. Jones , Mary Jean Harrold, Empirical evaluation of the tarantula automatic fault-localization technique, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101949]
• 10: James A. Jones , Alessandro Orso , Mary Jean Harrold, GAMMATELLA: visualizing program-execution data for deployed software, Information Visualization, v.3 n.3, p.173-188, September 2004 [doi>10.1057/palgrave.ivs.9500077]
• 11: A. Lal, J. Lim, M. Polishchuk, and B. Liblit. Path optimization in programs and its application to debugging. In P. Sestoft, editor, 15th European Symposium on Programming, pages 246--263, Vienna, Austria, Mar. 2006. Springer.
• 12: 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
• 13: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 14: Benjamin Robert Liblit , Alexander Aiken, Cooperative bug isolation, University of California at Berkeley, Berkeley, CA, 2004
• 15: M. Litzkow, M. Livny, and M. Mutka. Condor - a hunter of idle workstations. In Proceedings of the 8th International Conference of Distributed Computing Systems, pages 104--111, June 1988.
• 16: 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
• 17: G. Rothermel, S. Elbaum, A. Kinneer, and H. Do. Software-artifact intrastructure repository. http://sir.unl.edu/portal/, Sept. 2006.
• 18: E. W. Weisstein. Boolean function. MathWorld-A Wolfram Web Resource, Dec.20 2006. http://mathworld.wolfram.com/BooleanFunction.html.
• 19: Alice X. Zheng , Michael I. Jordan , Ben Liblit , Mayur Naik , Alex Aiken, Statistical debugging: simultaneous identification of multiple bugs, Proceedings of the 23rd international conference on Machine learning, p.1105-1112, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143983]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Distributed debugging; Monitors; Tracing; Debugging aids

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Experimentation, Reliability

Keywords:
debugging effort metrics, dynamic feedback analysis, statistical bug isolation, three-valued logic