Classification of software behaviors for failure detection: a discriminative pattern mining approach

ABSTRACT

Software is a ubiquitous component of our daily life. We often depend on the correct working of software systems. Due to the difficulty and complexity of software systems, bugs and anomalies are prevalent. Bugs have caused billions of dollars loss, in addition to privacy and security threats. In this work, we address software reliability issues by proposing a novel method to classify software behaviors based on past history or runs. With the technique, it is possible to generalize past known errors and mistakes to capture failures and anomalies. Our technique first mines a set of discriminative features capturing repetitive series of events from program execution traces. It then performs feature selection to select the best features for classification. These features are then used to train a classifier to detect failures. Experiments and case studies on traces of several benchmark software systems and a real-life concurrency bug from MySQL server show the utility of the technique in capturing failures and anomalies. On average, our pattern-based classification technique outperforms the baseline approach by 24.68% in accuracy.

REFERENCES

• 1: ]]Mysql atomicity violation. http://bugs.mysql.com/bug.php?id=169.
• 2: ]]http://www.mysmu.edu/faculty/davidlo/kdd09.htm, 2009.
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 5: 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
• 6: Gustavo E. A. P. A. Batista , Ronaldo C. Prati , Maria Carolina Monard, A study of the behavior of several methods for balancing machine learning training data, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007735]
• 7: 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
• 8: ]]C-C. Chang and C-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 9: ]]H. Cheng, X. Yan, J. Han, and C. Hsu. Discriminative frequent pattern analysis for effective classification. In ICDE, pages 716--725, 2007.
• 10: Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005 [doi>10.1109/TKDE.2005.127]
• 11: 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
• 12: Thomas G. Dietterich, Ensemble Methods in Machine Learning, Proceedings of the First International Workshop on Multiple Classifier Systems, p.1-15, June 21-23, 2000
• 13: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 14: David Harel , Rami Marelly, Come, Let's Play: Scenario-Based Programming Using LSC's and the Play-Engine, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 15: 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
• 16: ]]ITU-T. ITU-T Recommendation Z.120: Message Sequence Chart (MSC). 1999.
• 17: Daniel Jurafsky , James H. Martin, Speech and Language Processing (2nd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2006
• 18: ]]C. Liu, X. Yan, H. Yu, J. Han, and P.S. Yu. Mining behavior graphs for "backtrace" of noncrashing bugs. In SDM, 2005.
• 19: David Lo , Siau-Cheng Khoo, QUARK: Empirical Assessment of Automaton-based Specification Miners, Proceedings of the 13th Working Conference on Reverse Engineering, p.51-60, October 23-27, 2006 [doi>10.1109/WCRE.2006.47]
• 20: David Lo , Siau-Cheng Khoo, SMArTIC: towards building an accurate, robust and scalable specification miner, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181808]
• 21: David Lo , Siau-Cheng Khoo , Chao Liu, Efficient mining of iterative patterns for software specification discovery, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281243]
• 22: Shan Lu , Soyeon Park , Eunsoo Seo , Yuanyuan Zhou, Learning from mistakes: a comprehensive study on real world concurrency bug characteristics, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 23: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 24: ]]Java Trans. API Spec. java.sun.com/products/jta/.
• 25: ]]G. Tassey. The economic impacts of inadequate infrastructure for software testing. National Institute of Standards and Technology. Planning Report, 2002.
• 26: ]]The Apache Software Foundation. Jakarta commons/net. http://jakarta.apache.org/commons/net/.
• 27: ]]C. Warrender, S. Forrest, and B. Pearlmutter. Detecting intrusions using system calls: Alternative data models. In IEEE Symp. on Security and Privacy, 1999.
• 28: ]]W. Weimer and G. Necula. Mining temporal specifications for error detection. In Proc. of Int. Conf. on Tools and Algo. for the Const. and Ana. of Sys., 2005.
• 29: Xifeng Yan , Hong Cheng , Jiawei Han , Philip S. Yu, Mining significant graph patterns by leap search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376662]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
closed unique patterns, failure detection, iterative patterns, pattern-based classification, sequential database, software behaviors