Efficient instrumentation for code coverage testing

ABSTRACT

Evaluation of Code Coverage is the problem of identifying the parts of a program that did not execute in one or more runs of a program. The traditional approach for code coverage tools is to use static code instrumentation. In this paper we present a new approach to dynamically insert and remove instrumentation code to reduce the runtime overhead of code coverage. We also explore the use of dominator tree information to reduce the number of instrumentation points needed. Our experiments show that our approach reduces runtime overhead by 38-90% compared with purecov, a commercial code coverage tool. Our tool is fully automated and available for download from the Internet.

REFERENCES

• 1: C-Cover Code Coverage Analyzer for C/C++, . http://www.bullseye.com/ccover.html, Bullseye Testing Technology.
• 2: Crashme Benchmark by MySQL Database System, . http://www.mysql.com/information/crash-me.php.
• 3: Rational PureCoverage for Unix, . http://www.rational.com/products/purecoverage/index.jtmpl, Rational Software Corporation.
• 4: SPEC newsletter, . September 1995, http://www.specbench.org/osg/cpu95/CINT95.
• 5: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 6: Hiralal Agrawal, Dominators, super blocks, and program coverage, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-34, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.175935]
• 7: Bryan Buck , Jeffrey K. Hollingsworth, An API for Runtime Code Patching, International Journal of High Performance Computing Applications, v.14 n.4, p.317-329, November 2000 [doi>10.1177/109434200001400404]
• 8: 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]
• 9: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• 10: J. Dean, C. A. Waldspurger, and W. E. Weihl, "Transparent, Low-Overhead Profiling on Modern Processors," Workshop on Profile and Feedback-Directed Compilation. October, Paris, France.
• 11: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 12: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 13: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 14: R. L. Probert, "Optimal Insertion of Software Probes in Well-Delimited Programs," IEEE Transactions on Software Engineering, January, 1981, pp. 34-42.
• 15: 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
• 16: W. E. Weihl, CPI: Continous Profiling Infrastructure, DIGITAL Forefront Magazine 1997.

INDEX TERMS

Keywords:
code coverage, dominator tree, dynamic code deletion, dynamic code patching, on-demand instrumentation, testing