Automatic extraction of abstract-object-state machines from unit-test executions

ABSTRACT

An automatic test-generation tool can produce a large number of test inputs to exercise the class under test. However, without specifications, developers cannot inspect the execution of each automatically generated test input practically. To address the problem, we have developed an automatic test abstraction tool, called Abstra, to extract high level object-state-transition information from unit-test executions, without requiring a priori specifications. Given a class and a set of its generated test inputs, our tool extracts object state machines (OSM): a state in an OSM represents an object state of the class and a transition in an OSM represents method calls of the class. When an object state in an OSM is concrete (being represented by the values of all fields reachable from the object), the size of the OSM could be too large to be useful for inspection. To address this issue, we have developed techniques in the tool to abstract object states based on returns of observer methods, branch coverage of methods, and individual object fields, respectively. The tool provides useful object-state-transition information for programmers to inspect unit-test executions effectively. In particular, the tool helps facilitate correctness inspection, program understanding, fault isolation, and test characterization.

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: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 3: Chandrasekhar Boyapati , Sarfraz Khurshid , Darko Marinov, Korat: automated testing based on Java predicates, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 4: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Shawn Laubach , Corina S. Păsăreanu , Robby , Hongjun Zheng, Bandera: extracting finite-state models from Java source code, Proceedings of the 22nd international conference on Software engineering, p.439-448, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337234]
• 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: E. Gamma and K. Beck. JUnit, 2003. http://www.junit.org.
• 7: Emden R. Gansner , Stephen C. North, An open graph visualization system and its applications to software engineering, Software—Practice & Experience, v.30 n.11, p.1203-1233, Sept. 2000 [doi>10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.3.CO;2-E]
• 8: Wolfgang Grieskamp , Yuri Gurevich , Wolfram Schulte , Margus Veanes, Generating finite state machines from abstract state machines, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 9: J. Henkel and A. Diwan. Discovering algebraic specifications from Java classes. In Proc. 17th European Conference on Object-Oriented Programming, pages 431--456, 2003.
• 10: Barbara Liskov , John Guttag, Program Development in Java: Abstraction, Specification, and Object-Oriented Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 11: P. David Stotts , Mark Lindsey , Angus Antley, An Informal Formal Method for Systematic JUnit Test Case Generation, Proceedings of the Second XP Universe and First Agile Universe Conference on Extreme Programming and Agile Methods - XP/Agile Universe 2002, p.131-143, August 04-07, 2002
• 12: Sun Microsystems. Java 2 Platform, Standard Edition, v 1.4.2, API Specification. Online documentation, Nov. 2003. http://java.sun.com/j2se/1.4.2/docs/api/.
• 13: John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 14: Tao Xie , Darko Marinov , David Notkin, Rostra: A Framework for Detecting Redundant Object-Oriented Unit Tests, Proceedings of the 19th IEEE international conference on Automated software engineering, p.196-205, September 20-24, 2004 [doi>10.1109/ASE.2004.61]
• 15: T. Xie and D. Notkin. Automatic extraction of object-oriented observer abstractions from unit-test executions. In Proc. 6th International Conference on Formal Engineering Methods, Nov. 2004.
• 16: T. Xie and D. Notkin. Automatic extraction of sliced object state machines for component interfaces. In Proc. 3rd Workshop on Specification and Verification of Component-Based Systems at ACM SIGSOFT 2004/FSE-12 (SAVCBS 2004), pages 39--46, October 2004.
• 17: Tao Xie , David Notkin, Automatically Identifying Special and Common Unit Tests for Object-Oriented Programs, Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering, p.277-287, November 08-11, 2005 [doi>10.1109/ISSRE.2005.12]
• 18: 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]
• 19: H. Yuan and T. Xie. Automatic extraction of abstract-object-state machines based on branch coverage. In Proc. 1st International Workshop on Reverse Engineering To Requirements at WCRE 2005 (RETR 2005), pages 5--11, November 2005.

INDEX TERMS

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

General Terms:
Experimentation, Reliability, Verification

Keywords:
debugging, program understanding, software testing