Identifying bug signatures using discriminative graph mining

ABSTRACT

Bug localization has attracted a lot of attention recently. Most existing methods focus on pinpointing a single statement or function call which is very likely to contain bugs. Although such methods could be very accurate, it is usually very hard for developers to understand the context of the bug, given each bug location in isolation. In this study, we propose to model software executions with graphs at two levels of granularity: methods and basic blocks. An individual node represents a method or basic block and an edge represents a method call, method return or transition (at the method or basic block granularity). Given a set of graphs of correct and faulty executions, we propose to extract the most discriminative subgraphs which contrast the program flow of correct and faulty executions. The extracted subgraphs not only pinpoint the bug, but also provide an informative context for understanding and fixing the bug. Different from traditional graph mining which mines a very large set of frequent subgraphs, we formulate subgraph mining as an optimization problem and directly generate the most discriminative subgraph with a recently proposed graph mining algorithm LEAP. We further extend it to generate a ranked list of top-k discriminative subgraphs representing distinct locations which may contain bugs. Experimental results and case studies show that our proposed method is both effective and efficient to mine discriminative subgraphs for bug localization and context identification.

REFERENCES

• 1: Rhino - JavaScript for Java. www.mozilla.org/rhino.
• 2: H. Agrawal, J. Horgan, S. London, and W. Wong. Fault localization using execution slices and dataflow tests. In ISSRE, 1995.
• 3: Christian Borgelt , Michael R. Berthold, Mining Molecular Fragments: Finding Relevant Substructures of Molecules, Proceedings of the 2002 IEEE International Conference on Data Mining, p.51, December 09-12, 2002
• 4: Mihai Christodorescu , Somesh Jha , Christopher Kruegel, Mining specifications of malicious behavior, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287628]
• 5: 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]
• 6: Richard A. DeMillo , Hsin Pan , Eugene H. Spafford, Critical slicing for software fault localization, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.121-134, January 08-10, 1996, San Diego, California, United States
• 7: H. Hsu, J. A. Jones, and A. Orso. RAPID: Identifying bug signatures to support debugging activities. In ASE, 2008.
• 8: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 9: 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
• 10: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 11: 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]
• 12: 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]
• 13: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 14: 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
• 15: 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
• 16: Siegfried Nijssen , Joost N. Kok, A quickstart in frequent structure mining can make a difference, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014134]
• 17: M. Renieris and S. Reiss. Fault localization with nearest neighbor queries. In ASE, 2003.
• 18: G. Tassey. The economic impacts of inadequate infrastructure for software testing. National Institute of Standards and Technology. Planning Report 02-3.2002, 2002.
• 19: R. M. H. Ting and J. Bailey. Mining minimal contrast subgraph patterns. In SDM, 2006.
• 20: N. Vanetik , E. Gudes , S. E. Shimony, Computing Frequent Graph Patterns from Semistructured Data, Proceedings of the 2002 IEEE International Conference on Data Mining, p.458, December 09-12, 2002
• 21: Jianyong Wang , Jiawei Han, BIDE: Efficient Mining of Frequent Closed Sequences, Proceedings of the 20th International Conference on Data Engineering, p.79, March 30-April 02, 2004
• 22: 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]
• 23: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining, p.721, December 09-12, 2002
• 24: Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]
• 25: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Pruning dynamic slices with confidence, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation

Keywords:
bug signature, discriminative subgraph mining