Mining object behavior with ADABU

ABSTRACT

To learn what constitutes correct program behavior, one can start with normal behavior. We observe actual program executions to construct state machines that summarize object behavior. These state machines, called object behavior models, capture the relationships between two kinds of methods: mutators that change the state (such as add()) and inspectors that keep the state unchanged (such as isEmpty()): "A Vector object initially is in isEmpty() state; after add(), it goes into ¬isEmpty() state". Our ADABU prototype for JAVA has successfully mined models of undocumented behavior from the AspectJ compiler and the Columba email client; the models tend to be small and easily understandable.

REFERENCES

• 1: 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
• 2: Shigeru Chiba , Muga Nishizawa, An easy-to-use toolkit for efficient Java bytecode translators, Proceedings of the 2nd international conference on Generative programming and component engineering, p.364-376, September 22-25, 2003, Erfurt, Germany
• 3: 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]
• 4: Valentin Dall-meier, Christian Lindig, and Andreas Zeller. Lightweight defect localization for Java. In Andrew Black, editor, European Conference on Object-Oriented Programming (ECOOP), pages 528--550, 2005.
• 5: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 6: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar, Permissive interfaces, 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
• 7: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 8: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 9: Martin Rinard. Flex. http://www.flex-compiler.lcs.mit.edu/, 2002. Compiler infrastructure.
• 10: Atanas Rountev, Precise Identification of Side-Effect-Free Methods in Java, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.82-91, September 11-14, 2004
• 11: Alexandru Salcianu and Martin Rinard. Purity and side effect analysis for Java programs. In Proceedings of the 6th International Conference on Verification, Model Checking and Abstract Interpretation, number 3385 in LNCS, pages 199--215, January 2005.
• 12: Timo Stich and Frederik Dietz. Columba. http://columbamail.org/, 2005. Open-source email client, implemented in Java.
• 13: Westley Weimer and George C. Necula. Mining temporal specifications for error detection. In Nicolas Halbwachs and Lenore D. Zuck, editors, Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2005), pages 461--476, Edinburgh, UK, April 4-8 2005.
• 14: John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
• 15: Tao Xie , Evan Martin , Hai Yuan, Automatic extraction of abstract-object-state machines from unit-test executions, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134427]
• 16: Tao Xie and David Notkin. Automatic extraction of object-oriented observer abstractions from unit-test executions. In Proceedings of the 6th International Conference on Formal Engineering Methods (ICFEM 2004), pages 290--305, November 2004.
• 17: Jinlin Yang , David Evans, Dynamically inferring temporal properties, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996832]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.m Miscellaneous

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Tools
      D.2.5 Testing and Debugging
          Subjects: Tracing

General Terms:
Documentation, Experimentation, Languages, Verification

Keywords:
automata, inspector method, java, mining, object behavior model, object state, observer method, program analysis, program instrumentation, purity analysis