Context-aware statistical debugging: from bug predictors to faulty control flow paths

ABSTRACT

Effective bug localization is important for realizing automated debugging. One attractive approach is to apply statistical techniques on a collection of evaluation profiles of program properties to help localize bugs. Previous research has proposed various specialized techniques to isolate certain program predicates as bug predictors. However, because many bugs may not be directly associated with these predicates, these techniques are often ineffective in localizing bugs. Relevant control flow paths that may contain bug locations are more informative than stand-alone predicates for discovering and understanding bugs. In this paper, we propose an approach to automatically generate such faulty control flow paths that link many bug predictors together for revealing bugs. Our approach combines feature selection (to accurately select failure-related predicates as bug predictors), clustering (to group correlated predicates), and control flow graph traversal in a novel way to help generate the paths. We have evaluated our approach on code including the Siemens test suite and rhythmbox (a large music management application for GNOME). Our experiments show that the faulty control flow paths are accurate, useful for localizing many bugs, and helped to discover previously unknown errors in rhythmbox

REFERENCES

• 1: H. Agrawal, J. R. Horgan, S. London, and W. E. Wong. Fault localization using execution slices and dataflow tests. In International Symposium on Software Reliability Engineering (ISSRE), pages 143--151, 1995.
• 2: Piramanayagam Arumuga Nainar , Ting Chen , Jake Rosin , Ben Liblit, Statistical debugging using compound boolean predicates, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273467]
• 3: Thomas Ball , Mayur Naik , Sriram K. Rajamani, From symptom to cause: localizing errors in counterexample traces, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.97-105, January 15-17, 2003, New Orleans, Louisiana, USA
• 4: P. Berkhin. Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, 2002.
• 5: J. F. Bowring, M. J. Harrold, and J. M. Rehg. Improving the classification of software behaviors using ensembles. Technical report, Georgia Institute of Technology, 2005.
• 6: James F. Bowring , James M. Rehg , Mary Jean Harrold, Active learning for automatic classification of software behavior, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 7: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 8: Yuriy Brun , Michael D. Ernst, Finding Latent Code Errors via Machine Learning over Program Executions, Proceedings of the 26th International Conference on Software Engineering, p.480-490, May 23-28, 2004
• 9: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 10: Cristian Cadar , Vijay Ganesh , Peter M. Pawlowski , David L. Dill , Dawson R. Engler, EXE: automatically generating inputs of death, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180445]
• 11: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 12: L. A. Clarke , A. Podgurski , D. J. Richardson , S. J. Zeil, A Formal Evaluation of Data Flow Path Selection Criteria, IEEE Transactions on Software Engineering, v.15 n.11, p.1318-1332, November 1989 [doi>10.1109/32.41326]
• 13: 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]
• 14: William Dickinson , David Leon , Andy Podgurski, Finding failures by cluster analysis of execution profiles, Proceedings of the 23rd International Conference on Software Engineering, p.339-348, May 12-19, 2001, Toronto, Ontario, Canada
• 15: N. Dodoo, L. Lin, and M. D. Ernst. Selecting, refining, and evaluating predicates for program analysis. Technical Report MIT-LCS-TR-914, MIT Laboratory for Computer Science, Cambridge, MA, July 21, 2003.
• 16: Michael D. Ernst , Adam Czeisler , William G. Griswold , David Notkin, Quickly detecting relevant program invariants, Proceedings of the 22nd international conference on Software engineering, p.449-458, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337240]
• 17: Patrice Godefroid , Nils Klarlund , Koushik Sen, DART: directed automated random testing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 18: Arnaud Gotlieb , Bernard Botella , Michel Rueher, Automatic test data generation using constraint solving techniques, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.53-62, March 02-04, 1998, Clearwater Beach, Florida, United States
• 19: Todd L. Graves , Mary Jean Harrold , Jung-Min Kim , Adam Porter , Gregg Rothermel, An empirical study of regression test selection techniques, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.2, p.184-208, April 2001 [doi>10.1145/367008.367020]
• 20: A. Groce and R. Joshi. Exploiting traces in program analysis. In Tools and Algorithms for Construction and Analysis of Systems (TACAS), volume 3920 of Lecture Notes in Computer Science (LNCS), pages 379--393. Springer, 2006.
• 21: Neelam Gupta , Haifeng He , Xiangyu Zhang , Rajiv Gupta, Locating faulty code using failure-inducing chops, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101948]
• 22: 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
• 23: Murali Haran , Alan Karr , Alessandro Orso , Adam Porter , Ashish Sanil, Applying classification techniques to remotely-collected program execution data, 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
• 24: M. J. Harrold and G. Rothermel. Aristotle Analysis System - Siemens Programs, HR Variants. http://www.cc.gatech.edu/aristotle/Tools/subjects/.
• 25: M. Heiler, D. Cremers, and C. Schnörr. Efficient feature subset selection for support vector machines. Technical Report 21/2001, Computer Science Series, University of Mannheim.
• 26: 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
• 27: Ranjit Jhala , Rupak Majumdar, Path slicing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 28: L. Jiang and Z. Su. Automatic isolation of cause-effect chains with machine learning. Technical Report CSE-2005-32, UC Davis, 2005.
• 29: James A. Jones , James F. Bowring , Mary Jean Harrold, Debugging in Parallel, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273468]
• 30: 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]
• 31: 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]
• 32: A. Lal, J. Lim, M. Polishchuk, and B. Liblit. Path optimization in programs and its application to debugging. In European Symposium on Programming (ESOP), volume 3924 of Lecture Notes in Computer Science (LNCS), pages 246--263. SpringerESE, 2006.
• 33: David Leon , Wes Masri , Andy Podgurski, An empirical evaluation of test case filtering techniques based on exercising complex information flows, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062531]
• 34: B. Liblit. Bug 137460: dangling timeout event source ID causes crashes. http://bugzilla.gnome.org/show_bug.cgi?id=137460.
• 35: B. Liblit. Bug 137834: dangling RBShellPlayer callbacks cause crashes. http://bugzilla.gnome.org/show_bug.cgi?id=137834.
• 36: B. Liblit. The Cooperative Bug Isolation Project. http://www.cs.wisc.edu/cbi/.
• 37: Ben Liblit , Alex Aiken, Building a Better Backtrace: Techniques for Postmortem Program Analysis, University of California at Berkeley, Berkeley, CA, 2002
• 38: 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
• 39: 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
• 40: Chao Liu , Jiawei Han, Failure proximity: a fault localization-based approach, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181782]
• 41: 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
• 42: Roman Manevich , Manu Sridharan , Stephen Adams , Manuvir Das , Zhe Yang, PSE: explaining program failures via postmortem static analysis, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 43: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 44: George C. Necula , Jeremy Condit , Matthew Harren , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy software, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.477-526, May 2005 [doi>10.1145/1065887.1065892]
• 45: Alessandro Orso , James Jones , Mary Jean Harrold, Visualization of program-execution data for deployed software, Proceedings of the 2003 ACM symposium on Software visualization, June 11-13, 2003, San Diego, California [doi>10.1145/774833.774843]
• 46: H. Pan and E. H. Spafford. Heuristics for automatic localization of software faults. Technical Report SERC-TR-116-P, Purdue University, 1992.
• 47: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 48: Andy Podgurski , David Leon , Patrick Francis , Wes Masri , Melinda Minch , Jiayang Sun , Bin Wang, Automated support for classifying software failure reports, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 49: M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In ASE, 2003.
• 50: Thomas Reps , Thomas Ball , Manuvir Das , James Larus, The use of program profiling for software maintenance with applications to the year 2000 problem, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.432-449, September 22-25, 1997, Zurich, Switzerland
• 51: Rhythmbox. Music management application for GNOME. http://www.rhythmbox.org.
• 52: Salford Systems Inc. RandomForestsTM. http://www.salford-systems.com/.
• 53: Koushik Sen , Darko Marinov , Gul Agha, CUTE: a concolic unit testing engine for C, 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
• 54: W. Eric Wong , Swapna S. Gokhale , Joseph R. Horgan, Measuring Distance between Program Features, Proceedings of the 26th International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment, p.307-312, August 26-19, 2002
• 55: Cliff Young , Michael D. Smith, Static correlated branch prediction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.1028-1075, Sept. 1999 [doi>10.1145/330249.330255]
• 56: 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]
• 57: 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]
• 58: 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]
• 59: A. X. Zheng, M. I. Jordan, B. Liblit, and A. Aiken. Statistical debugging of sampled programs. In Neural Information Processing Systems (NIPS). 2003.

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.4 Software/Program Verification
          Subjects: Reliability
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Experimentation, Reliability

Keywords:
bug localization, control flow analysis, machine learning, statistical debugging