Profile-guided program simplification for effective testing and analysis

ABSTRACT

Many testing and analysis techniques have been developed for inhouse use. Although they are effective at discovering defects before a program is deployed, these techniques are often limited due to the complexity of real-world code and thus miss program faults. It will be the users of the program who eventually experience failures caused by the undetected faults. To take advantage of the large number of program runs carried by the users, recent work has proposed techniques to collect execution profiles from the users for developers to perform post-deployment failure analysis. However, in order to protect users' privacy and to reduce run-time overhead, such profiles are usually not detailed enough for the developers to identify or fix the root causes of the failures.

In this paper, we propose a novel approach to utilize user execution profiles for more effective in-house testing and analysis. Our key insight is that execution profiles for program failures can be used to simplify a program, while preserving its erroneous behavior. By simplifying a program and scaling down its complexity according to its profiles, in-house testing and analysis techniques can be performed more accurately and efficiently, and pragmatically program defects that occur more often and are (arguably) more relevant to users will be given preference during failure analysis. Specifically, we adapt statistical debugging on execution profiles to predict likely failure-related code and use a syntax-directed algorithm to trim failure-irrelevant code from a program, while preserving its erroneous behavior as much as possible. We conducted case studies on a testing engine, CUTE, and a software model checker, BLAST, to evaluate our technique. We used subject programs from the Aristotle Analysis System and the Software-artifact Infrastructure Repository (SIR). Our empirical results show that using simplified programs, CUTE and BLAST find more bugs with improved accuracy and performance: they were able to detect 20 and 21 (out of 139) more bugs respectively in about half of the time as they took on the original test programs.

REFERENCES

• 1: H. Agrawal, J. R. Horgan, S. London, and W. E. Wong. Fault localization using execution slices and dataflow tests. In ISSRE, pages 143--151, 1995.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: 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]
• 4: Samuel Bates , Susan Horwitz, Incremental program testing using program dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.384-396, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158694]
• 5: Dirk Beyer , Adam J. Chlipala , Rupak Majumdar, Generating Tests from Counterexamples, Proceedings of the 26th International Conference on Software Engineering, p.326-335, May 23-28, 2004
• 6: D. Binkley and K. B. Gallagher. Program slicing. Advances in Computers, 43:1--50, 1996.
• 7: J. F. Bowring, M. J. Harrold, and J. M. Rehg. Improving the classification of software behaviors using ensembles of control-flow and data-flow classifiers. Technical Report GIT-CERCS-05-10, Georgia Institute of Technology, April 2005.
• 8: 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
• 9: 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
• 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: 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]
• 12: Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
• 13: Christoph Csallner , Yannis Smaragdakis, Check 'n' crash: combining static checking and testing, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062533]
• 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: 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]
• 16: 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
• 17: 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]
• 18: A. Groce and R. Joshi. Exploiting traces in program analysis. In TACAS, volume 3920 of LNCS, pages 379--393. Springer, 2006.
• 19: 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]
• 20: 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
• 21: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar , Grégoire Sutre, Lazy abstraction, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.58-70, January 16-18, 2002, Portland, Oregon
• 22: T. A. Henzinger, R. Jhala, R. Majumdar, and G. Sutre. Software verification with BLAST. In SPIN, volume 2648 of LNCS, pages 235--239, 2003.
• 23: 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
• 24: Lingxiao Jiang , Zhendong Su, Context-aware statistical debugging: from bug predictors to faulty control flow paths, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321660]
• 25: 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]
• 26: 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]
• 27: Neil D. Jones, An introduction to partial evaluation, ACM Computing Surveys (CSUR), v.28 n.3, p.480-503, Sept. 1996 [doi>10.1145/243439.243447]
• 28: 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]
• 29: A. Lal, J. Lim, M. Polishchuk, and B. Liblit. Path optimization in programs and its application to debugging. In ESOP, 2006.
• 30: B. Liblit. The Cooperative Bug Isolation Project. http://www.cs.wisc.edu/cbi/.
• 31: Ben Liblit , Alex Aiken, Building a Better Backtrace: Techniques for Postmortem Program Analysis, University of California at Berkeley, Berkeley, CA, 2002
• 32: 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
• 33: 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
• 34: 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]
• 35: 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
• 36: C. Liu, X. Zhang, J. Han, Y. Zhang, and B. K. Bhargava. Failure indexing: A dynamic slicing based approach. In ICSM, pages 382--393, 2007.
• 37: Shan Lu , Pin Zhou , Wei Liu , Yuanyuan Zhou , Josep Torrellas, PathExpander: Architectural Support for Increasing the Path Coverage of Dynamic Bug Detection, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.38-52, December 09-13, 2006 [doi>10.1109/MICRO.2006.40]
• 38: 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
• 39: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 40: Corina S. Pasareanu , Matthew B. Dwyer , Willem Visser, Finding Feasible Counter-examples when Model Checking Abstracted Java Programs, Proceedings of the 7th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, p.284-298, April 02-06, 2001
• 41: 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
• 42: M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In ASE, 2003.
• 43: 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
• 44: Siemens, M. J. Harrold, and G. Rothermel. Aristotle Analysis System -- Siemens Programs, HR Variants. http://www.cc.gatech.edu/aristotle/Tools/subjects/.
• 45: Willem Visser , Corina S. Pǎsǎreanu , Sarfraz Khurshid, Test input generation with java PathFinder, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 46: T. Xie, D. Marinov, W. Schulte, and D. Notkin. Symstra: A framework for generating object-oriented unit tests using symbolic execution. In TACAS, pages 365--381, 2005.
• 47: 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]
• 48: A. X. Zheng, M. I. Jordan, B. Liblit, and A. Aiken. Statistical debugging of sampled programs. In Advances in Neural Information Processing Systems 16. 2003.
• 49: 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: Reliability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Experimentation, Reliability

Keywords:
profiling, program simplification, statistical debugging, testing and analysis