Demand-driven structural testing with dynamic instrumentation

ABSTRACT

Producing reliable and robust software has become one of the most important software development concerns in recent years. Testing is a process by which software quality can be assured through the collection of information. While testing can improve software reliability, current tools typically are inflexible and have high over-heads, making it challenging to test large software projects. In this paper, we describe a new scalable and flexible framework for testing programs with a novel demand-driven approach based on execution paths to implement test coverage. This technique uses dynamic instrumentation on the binary code that can be inserted and removed on-the-fly to keep performance and memory overheads low. We describe and evaluate implementations of the framework for branch, node and defuse testing of Java programs. Experimental results for branch testing show that our approach has, on average, a 1.6 speed up over static instrumentation and also uses less memory.

REFERENCES

• 1: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 2: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 3: B. Childers , M. L. Soffa , Jonathan Beaver , L. Ber , K. Cammarata , T. Kane , J. Litman , J. Misurda, SoftTest: a framework for software testing of Java programs, Proceedings of the 2003 OOPSLA workshop on eclipse technology eXchange, p.79-83, October 27-27, 2003, Anaheim, California [doi>10.1145/965660.965677]
• 4: Clover, http://www.cenqua.com/clover/.
• 5: Eclipse Integrated Development Environment, http://www.eclipse.org
• 6: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 7: P. G. Frankl, S. N. Weiss, and E. J. Weyuker, "ASSET: A system to select and evaluate tests", Proceedings of the IEEE Conference on Software Tools, 1985.
• 8: M. Harrold , M. Soffa, Interprocedual data flow testing, Proceedings of the ACM SIGSOFT '89 third symposium on Software testing, analysis, and verification, p.158-167, December 13-15, 1989, Key West, Florida, United States
• 9: J. K. Hollingsworth , O. Niam , B. P. Miller , Zhichen Xu , M. J. R. Goncalves , Ling Zheng, MDL: A Language And Compiler For Dynamic Program Instrumentation, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.201, November 11-15, 1997
• 10: IBM, Rational PurifyPlus, http://www.ibm.com/rational.
• 11: JCover, http://www.codework.com/JCover/
• 12: Peter B. Kessler, Fast breakpoints: design and implementation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.78-84, June 1990, White Plains, New York, United States
• 13: Barton P. Miller , Mark D. Callaghan , Jonathan M. Cargille , Jeffrey K. Hollingsworth , R. Bruce Irvin , Karen L. Karavanic , Krishna Kunchithapadam , Tia Newhall, The Paradyn Parallel Performance Measurement Tool, Computer, v.28 n.11, p.37-46, November 1995 [doi>10.1109/2.471178]
• 14: J. Misurda, J. Clause, J. Reed, B. R. Childers, and M. L. Soffa, "Jazz: A Tool for Demand-Driven Structural Testing", International Conference on Compiler Construction, 2005.
• 15: Leon Osterweil, Strategic directions in software quality, ACM Computing Surveys (CSUR), v.28 n.4, p.738-750, Dec. 1996 [doi>10.1145/242223.242288]
• 16: Christina Pavlopoulou , Michal Young, Residual test coverage monitoring, Proceedings of the 21st international conference on Software engineering, p.277-284, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302637]
• 17: William Perry, Effective methods for software testing, Wiley-QED Publishing, Somerset, NJ, 1995
• 18: Pin, http://rogue.colorado.edu/Pin/
• 19: Sandra Rapps , Elaine J. Weyuker, Selecting software test data using data flow information, IEEE Transactions on Software Engineering, v.11 n.4, p.367-375, April 1985 [doi>10.1109/TSE.1985.232226]
• 20: Standard Performance Evaluation Corporation, http://www.spec.org/jvm98
• 21: Mustafa M. Tikir , Jeffrey K. Hollingsworth, Efficient instrumentation for code coverage testing, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Experimentation, Measurement, Verification

Keywords:
Java programming language, code coverage, demand-driven instrumentation, structural testing, testing