Efficiently monitoring data-flow test coverage

ABSTRACT

Structural testing of software requires monitoring the software's execution to determine which program entities are executed by a test suite. Such monitoring can add considerable overhead to the execution of the program, adversely affecting the cost of running a test suite. Thus, minimizing the necessary monitoring activity lets testers reduce testing time or execute more test cases. A basic testing strategy is to cover all statements or branches but a more effective strategy is to cover all definition-use associations (DUAs).

In this paper, we present a novel technique to efficiently monitor DUAs, based on branch monitoring. We show how to infer from branch coverage the coverage of many DUAs, while remaining DUAs are predicted with high accuracy by the same information. Based on this analysis, testers can choose branch monitoring to approximate DUA coverage or instrument directly for DUA monitoring, which is precise but more expensive. In this paper, we also present a tool, called DUA-Forensics, that we implemented for this technique along with a set of empirical studies that we performed using the tool

REFERENCES

• 1: Hiralal Agrawal, On slicing programs with jump statements, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.302-312, June 20-24, 1994, Orlando, Florida, United States
• 2: Hira Agrawal, Efficient coverage testing using global dominator graphs, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.11-20, September 06-06, 1999, Toulouse, France
• 3: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 4: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 5: Antonia Bertolino, Unconstrained edges and their application to branch analysis and testing of programs, Journal of Systems and Software, v.20 n.2, p.125-133, Feb. 1993 [doi>10.1016/0164-1212(93)90004-H]
• 6: 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]
• 7: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 8: 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]
• 9: Mary Jean Harrold , Gregg Rothermel, Performing data flow testing on classes, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.154-163, December 06-09, 1994, New Orleans, Louisiana, United States
• 10: Mary Jean Harrold , Mary Lou Soffa, Efficient computation of interprocedural definition-use chains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.175-204, March 1994 [doi>10.1145/174662.174663]
• 11: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 12: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 13: J. W. Laski , B. Korel, A Data Flow Oriented Program Testing Strategy, IEEE Transactions on Software Engineering, v.9 n.3, p.347-354, May 1983 [doi>10.1109/TSE.1983.236871]
• 14: Martina Marré , Antonia Bertolino, Unconstrained duals and their use in achieving all-uses coverage, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.147-157, January 08-10, 1996, San Diego, California, United States
• 15: Martina Marré , Antonia Bertolino, Using Spanning Sets for Coverage Testing, IEEE Transactions on Software Engineering, v.29 n.11, p.974-984, November 2003 [doi>10.1109/TSE.2003.1245299]
• 16: Ettore M. Merlo , Giuliano Antoniol, A static measure of a subset of intra-procedural data flow testing coverage based on node coverage, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.7, November 08-11, 1999, Mississauga, Ontario, Canada
• 17: Jonathan Misurda , James A. Clause , Juliya L. Reed , Bruce R. Childers , Mary Lou Soffa, Demand-driven structural testing with dynamic instrumentation, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062496]
• 18: Ntafos, S. On required elements testing. IEEE Transactions on Software Engineering SE-10 (November 1984), 795--803.
• 19: H. D. Pande , W. A. Landi , B. G. Ryder, Interprocedural Def-Use Associations for C Systems with Single Level Pointers, IEEE Transactions on Software Engineering, v.20 n.5, p.385-403, May 1994 [doi>10.1109/32.286418]
• 20: Raul Santelices , Saurabh Sinha , Mary Jean Harrold, Subsumption of program entities for efficient coverage and monitoring, Proceedings of the 3rd international workshop on Software quality assurance, November 06-06, 2006, Portland, Oregon [doi>10.1145/1188895.1188899]
• 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
• 22: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
data-flow testing, definition-use association, inference, instrumentation, test coverage