Dominators, super blocks, and program coverage

ABSTRACT

In this paper we present techniques to find subsets of nodes of a flowgraph that satisfy the following property: A test set that exercises all nodes in a subset exercises all nodes in the flowgraph. Analogous techniques to find subsets of edges are also proposed. These techniques may be used to significantly reduce the cost of coverage testing of programs. A notion of a super block consisting of one or more basic blocks in that super block must be exercised by the same input. Dominator relationships among super blocks are used to identify a subset of the super blocks whose coverage implies that of all super blocks and, in turn, that of all basic blocks. Experiments with eight systems in the range of 1-75K lines of code show that, on the average, test cases targeted to cover just 29% of the basic blocks and 32% of the branches ensure 100% block and branch coverage, respectively.

REFERENCES

• 1: Hiralal Agrawal , Richard A. Demillo , Eugene H. Spafford, Debugging with dynamic slicing and backtracking, Software—Practice & Experience, v.23 n.6, p.589-616, June 1993 [doi>10.1002/spe.4380230603]
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 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: Richard A. DeMillo , W. Michael McCracken , R. J. Martin , John F. Passafiume, Software testing and evaluation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1987
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: S. L. Graham, P. B. Kessler, and M. K. McKusick. An execution profiler for modular programs. Software Practice and Experience, 13:671-685, 1983.
• 8: Rajiv Gupta, Generalized dominators and post-dominators, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.246-257, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143216]
• 9: D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22166]
• 10: J. R. Horgan and S. L. London. ATAC: A data flow coverage testing tool for C. In Proceedings of the Symposium on Assessment of Quality Software Development Tools, pages 2-10. IEEE Computer Society Press, May 1992.
• 11: D. E. Knuth and F. R. Stevenson. Optimal measurement points for program frequency counts. BIT, 13:313-322, 1973.
• 12: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 13: Dennis M. Moyles , Gerald L. Thompson, An Algorithm for Finding a Minimum Equivalent Graph of a Digraph, Journal of the ACM (JACM), v.16 n.3, p.455-460, July 1969 [doi>10.1145/321526.321534]
• 14: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 15: R. L. Probert. Optimal insertion of software probes in well-delimited programs. IEEE Transactions on Software Engineering, SE-8(1):34-42, Jan. 1982.
• 16: Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
• 17: C. V. Ramamoorthy, K. H. Kim, and W. T. Chert. Optimal placement of software monitors aiding systematic testing. IEEE Transactions on Software Engineering, SE-1(4):403-411, Dec. 1975.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Algorithms, Experimentation, Measurement, Verification