Subsumption of program entities for efficient coverage and monitoring

ABSTRACT

Program entities such as branches, def-use pairs, and call sequences are used in diverse software-development tasks. Reducing a set of entities to a small representative subset through subsumption saves monitoring overhead, focuses the developer's attention, and provides insights into the complexity of a program. Previous work has solved this problem for entities of the same type, and only for some types. In this paper we introduce a novel and general approach for subsumption of entities of any type based on predicate conditions. We discuss applications of this technique, and address future steps.

REFERENCES

• 1: 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]
• 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: 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]
• 4: 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]
• 5: Lori A. Clarke , Debra J. Richardson, Applications of symbolic evaluation, Journal of Systems and Software, v.5 n.1, p.15-35, Feb. 1985 [doi>10.1016/0164-1212(85)90004-4]
• 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: Michael Harder , Jeff Mellen , Michael D. Ernst, Improving test suites via operational abstraction, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 8: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 9: 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
• 10: 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]
• 11: 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
• 12: Torsten Robschink , Gregor Snelting, Efficient path conditions in dependence graphs, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581398]
• 13: Gregg Rothermel , Roland J. Untch , Chengyun Chu, Prioritizing Test Cases For Regression Testing, IEEE Transactions on Software Engineering, v.27 n.10, p.929-948, October 2001 [doi>10.1109/32.962562]
• 14: Srihari Sukumaran , Ashok Sreenivas, Identifying Test Conditions for Software Maintenance, Proceedings of the Ninth European Conference on Software Maintenance and Reengineering, p.304-313, March 21-23, 2005 [doi>10.1109/CSMR.2005.32]

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.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors

General Terms:
Algorithms, Experimentation, Performance

Keywords:
coverage criteria, entity hierarchies, predicate conditions, subsumption