Applying classification techniques to remotely-collected program execution data

ABSTRACT

There is an increasing interest in techniques that support measurement and analysis of fielded software systems. One of the main goals of these techniques is to better understand how software actually behaves in the field. In particular, many of these techniques require a way to distinguish, in the field, failing from passing executions. So far, researchers and practitioners have only partially addressed this problem: they have simply assumed that program failure status is either obvious (i.e., the program crashes) or provided by an external source (e.g., the users). In this paper, we propose a technique for automatically classifying execution data, collected in the field, as coming from either passing or failing program runs. (Failing program runs are executions that terminate with a failure, such as a wrong outcome.) We use statistical learning algorithms to build the classification models. Our approach builds the models by analyzing executions performed in a controlled environment (e.g., test cases run in-house) and then uses the models to predict whether execution data produced by a fielded instance were generated by a passing or failing program execution. We also present results from an initial feasibility study, based on multiple versions of a software subject, in which we investigate several issues vital to the applicability of the technique. Finally, we present some lessons learned regarding the interplay between the reliability of classification models and the amount and type of data collected.

REFERENCES

• 1: Jim Bowring , Alessandro Orso , Mary Jean Harrold, Monitoring deployed software using software tomography, Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, November 18-19, 2002, Charleston, South Carolina, USA
• 2: 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
• 3: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 4: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
• 5: 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
• 6: William Dickinson , David Leon , Andy Podgurski, Pursuing failure: the distribution of program failures in a profile space, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 7: 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
• 8: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 9: Patrick Francis , David Leon , Melinda Minch , Andy Podgurski, Tree-Based Methods for Classifying Software Failures, Proceedings of the 15th International Symposium on Software Reliability Engineering (ISSRE'04), p.451-462, November 02-05, 2004 [doi>10.1109/ISSRE.2004.43]
• 10: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer, 2001.
• 11: David M. Hilbert , David F. Redmiles, Extracting usability information from user interface events, ACM Computing Surveys (CSUR), v.32 n.4, p.384-421, Dec. 2000 [doi>10.1145/371578.371593]
• 12: David Leon , Andy Podgurski , Lee J. White, Multivariate visualization in observation-based testing, Proceedings of the 22nd international conference on Software engineering, p.116-125, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337195]
• 13: 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
• 14: 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
• 15: Microsoft online crash analysis, 2004. http://oca.microsoft.com.
• 16: Alessandro Orso , Taweesup Apiwattanapong , Mary Jean Harrold, Leveraging field data for impact analysis and regression testing, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 17: 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]
• 18: Alessandro Orso , Bryan Kennedy, Selective capture and replay of program executions, Proceedings of the third international workshop on Dynamic analysis, p.1-7, May 17-17, 2005, St. Louis, Missouri
• 19: Christina Pavlopoulou , Michal Young, Residual test coverage monitoring, Proceedings of the 21st international conference on Software engineering, p.277-284, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302637]
• 20: 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
• 21: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 22: Cemal Yilmaz , Myra B. Cohen , Adam Porter, Covering arrays for efficient fault characterization in complex configuration spaces, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Experimentation, Reliability

Keywords:
classification, machine learning, software behavior