Graph-based mining of multiple object usage patterns

ABSTRACT

The interplay of multiple objects in object-oriented programming often follows specific protocols, for example certain orders of method calls and/or control structure constraints among them that are parts of the intended object usages. Unfortunately, the information is not always documented. That creates long learning curve, and importantly, leads to subtle problems due to the misuse of objects.

In this paper, we propose GrouMiner, a novel graph-based approach for mining the usage patterns of one or multiple objects. GrouMiner approach includes a graph-based representation for multiple object usages, a pattern mining algorithm, and an anomaly detection technique that are efficient, accurate, and resilient to software changes. Our experiments on several real-world programs show that our prototype is able to find useful usage patterns with multiple objects and control structures, and to translate them into user-friendly code skeletons to assist developers in programming. It could also detect the usage anomalies that caused yet undiscovered defects and code smells in those programs.

REFERENCES

• 1: M. Acharya, T. Xie, J. Pei, and J. Xu. Mining API patterns as partial orders from source code: from usage scenarios to specifications. In ESEC-FSE'07, pages 25--34. ACM, 2007.
• 2: R. Alur, P. Cerny, P. Madhusudan, and W. Nam. Synthesis of interface specifications for java classes. In POPL, ACM, 2005.
• 3: G. Ammons, R. Bod1k, and J.R. Larus. Mining specifications. In POPL'02, pages 4--16. ACM, 2002.
• 4: A. Wasylkowski, A. Zeller, and C. Lindig. Detecting object usage anomalies. In ESEC/FSE'07, pages 35--44. ACM, 2007.
• 5: R.-Y. Chang, A. Podgurski, and J. Yang. Discovering neglected conditions in software by mining dependence graphs. IEEE Transactions on Software Engineering, 34(5):579--596, 2008.
• 6: V. Dallmeier, C. Lindig, and A. Zeller. Lightweight defect localization for Java. In ECOOP'05. Springer Verlag, 2005.
• 7: R. DeLine and M. Fahndrich. Typestates for objects. In ECOOP'04, LNCS 3086, pages 465--490. Springer Verlag, 2004.
• 8: G. Di Fatta, S. Leue, and E. Stegantova. Discriminative pattern mining in software fault detection. In SOQUA'06. ACM, 2006.
• 9: W. Dickinson, D. Leon, and A. Podgurski. Finding failures by cluster analysis of execution profiles. ICSE'01, IEEE, 2001.
• 10: D. Engler, D.Y. Chen, S. Hallem, A. Chou, and B. Chelf. Bugs as deviant behavior: a general approach to inferring errors in systems code. In SOSP'01, pages 57--72. ACM, 2001.
• 11: Fluid project. http://www.fluid.cs.cmu.edu:8080/Fluid.
• 12: M. Gabel and Z. Su. Javert: fully automatic mining of general temporal properties from dynamic traces. FSE'08, ACM, 2008.
• 13: T.A. Henzinger, R. Jhala, and R. Majumdar. Permissive interfaces. In ESEC/FSE'05, pages 31--40. ACM, 2005.
• 14: D. Hovemeyer and W. Pugh. Finding bugs is easy. SIGPLAN Not., 39(12):92--106, 2004.
• 15: S. Kim, K. Pan, and E.E.J. Whitehead, Jr. Memories of bug fixes. In FSE'06, pages 35--45. ACM, 2006.
• 16: T. Kremenek, P. Twohey, G. Back, A. Ng, and D. Engler. From uncertainty to belief: inferring the specification within. OSDI'06.
• 17: J. Krinke. Identifying similar code with program dependence graphs. In WCRE'01, pages 301--309. IEEE CS, 2001.
• 18: Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: Finding copy-paste and related bugs in large-scale software code. IEEE Transactions on Software Engineering, 32(3):176--192, 2006.
• 19: Z. Li and Y. Zhou. PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code. In ESEC/FSE'05, pages 306--315. ACM, 2005.
• 20: C. Liu, E. Ye, and D. Richardson. Softw. library usage pattern extraction using a softw. model checker. ASE'06, IEEE, 2006.
• 21: B. Livshits and T. Zimmermann. DynaMine: finding common error patterns by mining software revision histories. In ESEC/FSE'05, pages 296--305, ACM, 2005.
• 22: D. Mandelin, L. Xu, R. Bodík, D. Kimelman. Jungloid mining: helping to navigate the API jungle. PLDI'05, ACM, 2005.
• 23: A. Michail. Data mining library reuse patterns using generalized association rules. ICSE'00, pp 167--176. ACM, 2000.
• 24: H.A. Nguyen, T.T. Nguyen, N.H. Pham, J.M. Al-Kofahi, and T.N. Nguyen. Accurate and efficient structural characteristic feature extraction for clone detection. FASE'09, Springer, 2009.
• 25: M.K. Ramanathan, A. Grama, S. Jagannathan. Path-sensitive inference of function precedence protocols. ICSE'07, IEEE, 2007.
• 26: R. Read and D. Corneil. The graph isomorphism disease. Journal of Graph Theory 1 (1977) 339--363
• 27: N. Sahavechaphan and K. Claypool. XSnippet: mining for sample code. In OOPSLA'06, pages 413--430. ACM, 2006.
• 28: S. Shoham, E. Yahav, S. Fink, M. Pistoia. Static specification mining using automata-based abstractions. ISSTA, ACM, 2007.
• 29: S. Thummalapenta and T. Xie. ParseWeb: a programmer assistant for reusing source code on the Web. ASE, ACM, 2007.
• 30: W. Weimer and G.C. Necula. Mining temporal specifications for error detection. In TACAS, pages 461--476, 2005.
• 31: C.C. Williams and J.K. Hollingsworth. Automatic mining of source code repositories to improve bug finding techniques. IEEE Trans. on Software Engineering, 31(6):466--480, 2005.
• 32: T. Xie and J. Pei. MAPO: mining API usages from open source repositories. In MSR'06, pages 54--57. ACM, 2006.
• 33: J. Yang, D. Evans, D. Bhardwaj, T. Bhat, and M. Das. Perracotta: mining temporal API rules from imperfect traces. In ICSE'06, pages 282--291. ACM, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

General Terms:
Algorithms, Design, Reliability

Keywords:
anomaly, api usage, clone, graph mining, groum, object usage, pattern