On-line anomaly detection of deployed software: a statistical machine learning approach

ABSTRACT

This paper presents a new machine-learning technique that performs anomaly detection as software is executing in the field. The technique uses a fully observable Markov model where each state in the model emits a number of distinct observations according to a probability distribution, and estimates the model parameters using the Baum-Welch algorithm. The trained model is then deployed with the software to perform anomaly detection. By performing the anomaly detection as the software is executing, faults associated with anomalies can be located and fixed before they cause critical failures in the system, and developers time to debug deployed software can be reduced. This paper also presents a prototype implementation of our technique, along with a case study that shows, for the subjects we studied, the effectiveness of the technique.

REFERENCES

• 1: 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
• 2: Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, p.342-351, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062522]
• 3: 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]
• 4: 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
• 5: 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]
• 6: 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]
• 7: 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
• 8: 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]
• 9: 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]
• 10: 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
• 11: C. Pasareanu, R. Pelanek, and W. Visser. Concrete model checking with abstract matching and refinement. In Proceedings of 17th international conference on computer-aided verification, July 2005.
• 12: 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
• 13: L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. In Proceedings of IEEE, volume 77, pages 257--286, February 1989.
• 14: John Steven , Pravir Chandra , Bob Fleck , Andy Podgurski, jRapture: A Capture/Replay tool for observation-based testing, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.158-167, August 21-24, 2000, Portland, Oregon, United States
• 15: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 16: Steven J. Zeil, Perturbation Techniques for Detecting Domain Errors, IEEE Transactions on Software Engineering, v.15 n.6, p.737-746, June 1989 [doi>10.1109/32.24727]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation

Keywords:
Markov models, anomaly detection, anomaly diagnosis, fault localization, machine learning