Detecting object usage anomalies

ABSTRACT

Interacting with objects often requires following a protocol---for instance, a specific sequence of method calls. These protocols are not always documented, and violations can lead to subtle problems. Our approach takes code examples to automatically infer legal sequences of method calls. The resulting patterns can then be used to detect anomalies such as "Before calling next, one normally calls hasNext". To our knowledge, this is the first fully automatic defect detection approach that learns and checks methodcall sequences. Our JADET prototype has detected yet undiscovered defects and code smells in five popular open-source programs, including two new defects in AspectJ.

REFERENCES

• 1: Luca de Alfaro , Thomas A. Henzinger, Interface automata, 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
• 2: Rajeev Alur , Pavol Černý , P. Madhusudan , Wonhong Nam, Synthesis of interface specifications for Java classes, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-109, January 12-14, 2005, Long Beach, California, USA
• 3: 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
• 4: Sergio Antoy , Dick Hamlet, Automatically Checking an Implementation against Its Formal Specification, IEEE Transactions on Software Engineering, v.26 n.1, p.55-69, January 2000 [doi>10.1109/32.825766]
• 5: Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
• 6: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 7: Valentin Dallmeier , Christian Lindig , Andrzej Wasylkowski , Andreas Zeller, Mining object behavior with ADABU, Proceedings of the 2006 international workshop on Dynamic systems analysis, May 23-23, 2006, Shanghai, China [doi>10.1145/1138912.1138918]
• 8: V. Dallmeier, C. Lindig, and A. Zeller. Lightweight defect localization for Java. In A. Black, editor, ECOOP '05: European Conference on Object-Oriented Programming, 2005.
• 9: R. DeLine and M. Fahndrich. Typestates for objects. In M. Odersky, editor, ECOOP '04: European Conference on Object-Oriented Programming, volume 3086 of Lecture Notes in Computer Science. Springer, 2004.
• 10: 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
• 11: Thomas Eisenbarth , Rainer Koschke , Gunther Vogel, Static object trace extraction for programs with pointers, Journal of Systems and Software, v.77 n.3, p.263-284, September 2005 [doi>10.1016/j.jss.2004.04.028]
• 12: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 13: Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146254]
• 14: Martin Fowler, Refactoring: Improving the Design of Existing Code, Proceedings of the Second XP Universe and First Agile Universe Conference on Extreme Programming and Agile Methods - XP/Agile Universe 2002, p.256, August 04-07, 2002
• 15: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 16: T. A. Henzinger, R. Jhala, and R. Majumdar. Permissive interfaces. In Wermelinger and Gall {32}, pages 31--40.
• 17: David Hovemeyer , William Pugh, Finding bugs is easy, ACM SIGPLAN Notices, v.39 n.12, December 2004 [doi>10.1145/1052883.1052895]
• 18: Sunghun Kim , Kai Pan , E. E. James Whitehead, Jr., Memories of bug fixes, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181781]
• 19: Z. Li and Y. Zhou. PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code. In Wermelinger and Gall {32}, pages 306--315.
• 20: C. Lindig. Mining patterns and violations using concept analysis. Technical report, Saarland University, Software Engineering Chair, Germany, June 2007. Avaliable from http://www.st.cs.uni-sb.de/publications/; the software is available from http://code.google.com/p/colibri-ml/.
• 21: Chang Liu , En Ye , Debra J. Richardson, LtRules: an automated software library usage rule extraction tool, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134424]
• 22: B. Livshits and T. Zimmermann. DynaMine: finding common error patterns by mining software revision histories. In Wermelinger and Gall {32}, pages 296--305.
• 23: Davide Lorenzoli , Leonardo Mariani , Mauro Pezzè, Inferring state-based behavior models, Proceedings of the 2006 international workshop on Dynamic systems analysis, May 23-23, 2006, Shanghai, China [doi>10.1145/1138912.1138919]
• 24: David Mandelin , Lin Xu , Rastislav Bodík , Doug Kimelman, Jungloid mining: helping to navigate the API jungle, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 25: Oscar Nierstrasz, Regular types for active objects, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.1-15, September 26-October 01, 1993, Washington, D.C., United States
• 26: Jochen Quante , Rainer Koschke, Dynamic Object Process Graphs, Proceedings of the Conference on Software Maintenance and Reengineering, p.81-90, March 22-24, 2006
• 27: Murali Krishna Ramanathan , Ananth Grama , Suresh Jagannathan, Path-Sensitive Inference of Function Precedence Protocols, Proceedings of the 29th international conference on Software Engineering, p.240-250, May 20-26, 2007 [doi>10.1109/ICSE.2007.63]
• 28: Steven P. Reiss, Specifying and checking component usage, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.13-22, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085133]
• 29: Naiyana Sahavechaphan , Kajal Claypool, XSnippet: mining For sample code, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 30: R E Strom , S Yemini, Typestate: A programming language concept for enhancing software reliability, IEEE Transactions on Software Engineering, v.12 n.1, p.157-171, Jan. 1986
• 31: W. Weimer and G. C. Necula. Mining temporal specifications for error detection. In N. Halbwachs and L. D. Zuck, editors, TACAS '05: Proc. of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 461--476, 2005.
• 32: Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 2005
• 33: Chadd C. Williams , Jeffrey K. Hollingsworth, Recovering system specific rules from software repositories, Proceedings of the 2005 international workshop on Mining software repositories, p.1-5, May 17-17, 2005, St. Louis, Missouri
• 34: Tao Xie , Evan Martin , Hai Yuan, Automatic extraction of abstract-object-state machines from unit-test executions, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134427]
• 35: Tao Xie , Jian Pei, MAPO: mining API usages from open source repositories, Proceedings of the 2006 international workshop on Mining software repositories, May 22-23, 2006, Shanghai, China [doi>10.1145/1137983.1137997]
• 36: Jinlin Yang , David Evans , Deepali Bhardwaj , Thirumalesh Bhat , Manuvir Das, Perracotta: mining temporal API rules from imperfect traces, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134325]
• 37: Daniel M. Yellin , Robert E. Strom, Protocol specifications and component adaptors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.292-333, March 1997 [doi>10.1145/244795.244801]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis
      F.3.3 Studies of Program Constructs
          Subjects: Object-oriented constructs; Control primitives

General Terms:
Algorithms, Design, Reliability

Keywords:
automated defect detection, automated specification generation, data mining for software engineering, object usage anomalies, pattern recognition, programming rules, static analysis