Unconstrained duals and their use in achieving all-uses coverage

ABSTRACT

Testing takes a considerable amount of the time and resources spent on producing software. It would therefore be useful to have ways 1) to reduce the cost of testing and 2) to estimate this cost. In particular, the number of tests to be executed is an important and useful attribute of the entity "testing effort". All-uses coverage is a data flow testing strategy widely researched in recent years. In this paper we present spanning sets of duas for the all-uses coverage criterion. A spanning set of duas is a minimum set of duas (definition-use associations) such that a set of test paths covering them covers every dua in the program. We give a method to find a spanning set of duas using the relation of subsumption between duas. Intuitively, there exists a natural ordering between the duas in a program: some duas are covered more easily than others, since coverage of the former is automatically guaranteed whenever the latter are covered. Those duas that are the most difficult to be covered according to this ordering are called unconstrained. A spanning set of duas is composed of unconstrained duas. Our results are useful for reducing the cost of testing, since the generation of test paths can be targeted to cover the smaller spanning set of duas, rather than all those in a program. On the other hand, assuming that a different path is taken to cover each dua in a spanning set, the cardinality of spanning sets can be used to estimate the cost of testing. Other interesting uses of spanning sets of duas are also discussed.

REFERENCES

• 1: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 2: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 3: Antonia Bertolino , Martina Marré, How many paths are needed for branch testing?, Journal of Systems and Software, v.35 n.2, p.95-106, Nov. 1996 [doi>10.1016/0164-1212(95)00089-5]
• 4: Antonia Bertolino , Martina Marré, Automatic Generation of Path Covers Based on the Control Flow Analysis of Computer Programs, IEEE Transactions on Software Engineering, v.20 n.12, p.885-899, December 1994 [doi>10.1109/32.368137]
• 5: A. Bertolino, R. Mirandola, and E. Peciola. A case study in branch testing automation. In Proc. of the 3rd Int. Conf. on Achieving Quality in Software (.4 QulS'96). To appear.
• 6: P. G. Frankl , S. N. Weiss, An Experimental Comparison of the Effectiveness of Branch Testing and Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.8, p.774-787, August 1993 [doi>10.1109/32.238581]
• 7: 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]
• 8: R. Gupta and M. L. Sofia. Employing static information in the generation of test cases. Software Testing, Verification and Reliability, 3(1):29-48, 1993.
• 9: M. Jean Harrold , Rajiv Gupta , Mary Lou Soffa, A methodology for controlling the size of a test suite, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.270-285, July 1993 [doi>10.1145/152388.152391]
• 10: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 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: B. Korel, Automated Software Test Data Generation, IEEE Transactions on Software Engineering, v.16 n.8, p.870-879, August 1990 [doi>10.1109/32.57624]
• 13: 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]
• 14: M. MarrY. Program Flow Analysis for Reducing and Estimating the Cost of Test Coverage Criteria. PhD thesis, Dep. Computer Science, FCEyN, Universidad de Buenos Aires, 1996.
• 15: E. F. Miller. Software testing technology: An overview. In C. R. Vick and C. V. Ramamoorthy, editors, Handbook of Software Engineering. Van Nostrand Reinhold, New York, 1984.
• 16: 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]
• 17: Elaine J. Weyuker, The Cost of Data Flow Testing: An Empirical Study, IEEE Transactions on Software Engineering, v.16 n.2, p.121-128, February 1990 [doi>10.1109/32.44376]
• 18: Elaine J. Weyuker, The complexity of data flow criteria for test data selection, Information Processing Letters, v.19 n.2, p.103-109, August 1984 [doi>10.1016/0020-0190(84)90106-6]
• 19: W. Eric Wong , Joseph R. Horgan , Saul London , Aditya P. Mathur, Effect of test set minimization on fault detection effectiveness, Proceedings of the 17th international conference on Software engineering, p.41-50, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225018]
• 20: D. Yates , N. Malevris, Reducing the effects of infeasible paths in branch testing, ACM SIGSOFT Software Engineering Notes, v.14 n.8, p.48-54, Dec. 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.9 Management
          Subjects: Cost estimation

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Management, Theory