Active learning for automatic classification of software behavior

ABSTRACT

A program's behavior is ultimately the collection of all its executions. This collection is diverse, unpredictable, and generally unbounded. Thus it is especially suited to statistical analysis and machine learning techniques. The primary focus of this paper is on the automatic classification of program behavior using execution data. Prior work on classifiers for software engineering adopts a classical batch-learning approach. In contrast, we explore an active-learning paradigm for behavior classification. In active learning, the classifier is trained incrementally on a series of labeled data elements. Secondly, we explore the thesis that certain features of program behavior are stochastic processes that exhibit the Markov property, and that the resultant Markov models of individual program executions can be automatically clustered into effective predictors of program behavior. We present a technique that models program executions as Markov models, and a clustering method for Markov models that aggregates multiple program executions into effective behavior classifiers. We evaluate an application of active learning to the efficient refinement of our classifiers by conducting three empirical studies that explore a scenario illustrating automated test plan augmentation.

REFERENCES

• 1: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 2: Aristotle Research Group. Aristotle: Software engineering tools, 2002. http://www.cc.gatech.edu/aristotle/.
• 3: Grady Booch , James Rumbaugh , Ivar Jacobson, The Unified Modeling Language user guide, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1999
• 4: 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
• 5: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 6: Jonathan E. Cook , Alexander L. Wolf, Automating process discovery through event-data analysis, Proceedings of the 17th international conference on Software engineering, p.73-82, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225021]
• 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: Thomas G. Dietterich, Machine Learning for Sequential Data: A Review, Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, p.15-30, August 06-09, 2002
• 9: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 10: M. Girolami and A. Kaban. Simplicial mixtures of markov chains: Distributed modelling of dynamic user profiles. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.
• 11: K. C. Gross, S. McMaster, A. Porter, A. Urmanov, and L. Votta. Proactive system maintenance using software telemetry. In Proceedings of the 1st International Conference on Remote Analysis and Measurement of Software Systems (RAMSS'03), pages 24--26, May 2003.
• 12: Michael Harder , Jeff Mellen , Michael D. Ernst, Improving test suites via operational abstraction, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 13: M. J. Harrold, G. Rothermel, K. Sayre, R. Wu, and L. Yi. An empirical investigation of the relationship between fault-revealing test behavior and differences in program spectra. Journal of Software Testing, Verifications, and Reliability, 10(3), September 2000.
• 14: Koral Ilgun , R. A. Kemmerer , Phillip A. Porras, State Transition Analysis: A Rule-Based Intrusion Detection Approach, IEEE Transactions on Software Engineering, v.21 n.3, p.181-199, March 1995 [doi>10.1109/32.372146]
• 15: S. Jha , K. Tan , R. A. Maxion, Markov Chains, Classifiers, and Intrusion Detection, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.206, June 11-13, 2001
• 16: James A. Kowal, Behavior Models Specifying Users Expectations, Prentice Hall Professional Technical Reference, 1991
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: John C. Munson , Sebastian Elbaum, Software Reliability as a Function of User Execution Patterns, Proceedings of the Thirty-second Annual Hawaii International Conference on System Sciences-Volume 8, p.8004, January 05-08, 1999
• 19: John D. Musa, Software Reliability Engineering: More Reliable Software Faster and Cheaper, Authorhouse, 2004
• 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: Stacy J. Prowell , Carmen J. Trammell , Richard C. Linger , Jesse H. Poore, Cleanroom software engineering: technology and process, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 22: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 23: Thomas Reps , Thomas Ball , Manuvir Das , James Larus, The use of program profiling for software maintenance with applications to the year 2000 problem, ACM SIGSOFT Software Engineering Notes, v.22 n.6, p.432-449, Nov. 1997
• 24: James A. Whittaker , J. H. Poore, Markov analysis of software specifications, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.1, p.93-106, Jan. 1993 [doi>10.1145/151299.151326]

INDEX TERMS

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

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Experimentation, Measurement, Reliability, Verification

Keywords:
Markov models, machine learning, software behavior, software testing