A framework of greedy methods for constructing interaction test suites

ABSTRACT

Greedy algorithms for the construction of software interaction test suites are studied. A framework is developed to evaluate a large class of greedy methods that build suites one test at a time. Within this framework are many instantiations of greedy methods generalizing those in the literature. Greedy algorithms are popular when the time for test suite construction is of paramount concern. We focus on the size of the test suite produced by each instantiation. Experiments are analyzed using statistical techniques to determine the importance of the implementation decisions within the framework. This framework provides a platform for optimizing the accuracy and speed of "one-test-at-a-time" greedy methods.

REFERENCES

• 1: K. Burr and W. Young. Combinatorial test techniques: Table-based automation, test generation, and code coverage. Proceedings of the Intl. Conf. on Software Testing Analysis and Review, pages 503--513, October 1998.
• 2: J. N. Cawse. Experimental design for combinatorial and high throughput materials development. GE Global Research Technical Report, 29(9):769--781, November 2002.
• 3: Christine Cheng , Adrian Dumitrescu , Patrick Schroeder, Generating Small Combinatorial Test Suites to Cover Input-Output Relationships, Proceedings of the Third International Conference on Quality Software, p.76, November 06-07, 2003
• 4: David M. Cohen , Siddhartha R. Dalal , Michael L. Fredman , Gardner C. Patton, The AETG System: An Approach to Testing Based on Combinatorial Design, IEEE Transactions on Software Engineering, v.23 n.7, p.437-444, July 1997 [doi>10.1109/32.605761]
• 5: D. M. Cohen, S. R. Dalal, M.L.Fredman, and G. Patton. Method and system for automatically generating efficient test cases for systems having interacting elements. United States Patent, Number 5,542,043, 1996.
• 6: David M. Cohen , Siddhartha R. Dalal , Jesse Parelius , Gardner C. Patton, The Combinatorial Design Approach to Automatic Test Generation, IEEE Software, v.13 n.5, p.83-88, September 1996 [doi>10.1109/52.536462]
• 7: M. B. Cohen. Designing test suites for software interaction testing. Ph.D. Thesis, The University of Auckland, Department of Computer Science, 2004.
• 8: Myra B. Cohen , Peter B. Gibbons , Warwick B. Mugridge , Charles J. Colbourn, Constructing test suites for interaction testing, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 9: M. B. Cohen, C. J. Colbourn, and A. C. H. Ling. Constructing strength three covering arrays with augmented annealing. Discrete Mathematics, to appear.
• 10: C. J. Colbourn. Combinatorial aspects of covering arrays. Le Matematiche (Catania), to appear.
• 11: C. J. Colbourn, M. B. Cohen, and R. C. Turban. A deterministic density algorithm for pairwise interaction coverage. Proc. of the IASTED Intl. Conference on Software Engineering, pages 242--252, February 2004.
• 12: J H Conway , N J A Sloane, Lexicographic codes: Error-correcting codes from game theory, IEEE Transactions on Information Theory, v.32 n.3, p.337-348, May 1986 [doi>10.1109/TIT.1986.1057187]
• 13: P. C. Denny and P. B. Gibbons. Case studies and new results in combinatorial enumeration. J. Combin. Des., 8:239--260, 2000.
• 14: A. Dumitrescu. Efficient algorithms for generation of combinatorial covering suites. Proc. 14-th Annual Intl. Symp. Algorithms and Computation (ISAAC '03), Lecture Notes in Computer Science, pages 300--308, 2003.
• 15: I. S. Dunietz , W. K. Ehrlich , B. D. Szablak , C. L. Mallows , A. Iannino, Applying design of experiments to software testing: experience report, Proceedings of the 19th international conference on Software engineering, p.205-215, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253271]
• 16: R. A. Fisher. The arrangement of field experiments. Journal of Ministry of Agriculture of Great Britain, 33(9):503--513, November 1926.
• 17: P. B. Gibbons, R. A. Mathon, and D. G. Corneil. Computing techniques for the construction and analysis of block designs. Utilitas Math., 11:161--192, 1977.
• 18: A. Hartman. Software and hardware testing using combinatorial covering suites. Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms, June 2002.
• 19: A. Hartman and L. Raskin. Problems and algorithms for covering arrays. Discrete Math., 284:149--156, 2004.
• 20: A. Hartman and Z. Yehudai. Greedesigns. Ars Combin., 29C:69--76, 1990.
• 21: Noritaka Kobayashi , Tatsuhiro Tsuchiya , Tohru Kikuno, A new method for constructing pair-wise covering designs for software testing, Information Processing Letters, v.81 n.2, p.85-91, 31 January 2002 [doi>10.1016/S0020-0190(01)00195-8]
• 22: D. Richard Kuhn , Michael J. Reilly, An Investigation of the Applicability of Design of Experiments to Software Testing, Proceedings of the 27th Annual NASA Goddard Software Engineering Workshop (SEW-27'02), p.91, December 05-06, 2002
• 23: Software Fault Interactions and Implications for Software Testing, IEEE Transactions on Software Engineering, v.30 n.6, p.418-421, June 2004 [doi>10.1109/TSE.2004.24]
• 24: D. Montgomery. Design and Analysis of Experiments 5th edition. John Wiley and Sons, New York NY, 2001.
• 25: Kari J. Nurmela, Upper bounds for covering arrays by tabu search, Discrete Applied Mathematics, v.138 n.1-2, p.143-152, 29 March 2004 [doi>10.1016/S0166-218X(03)00291-9]
• 26: D. Shasha, A. Kouranov, L. Lejay, M. Chou, and G. Coruzzi. Using combinatorial design to study regulation by multiple input signals. a tool for parsimony in the post-genomics era. Plant Physiology, 27:1590--1594, 2001.
• 27: K. C. Tai , Y. Lie, A Test Generation Strategy for Pairwise Testing, IEEE Transactions on Software Engineering, v.28 n.1, p.109-111, January 2002 [doi>10.1109/32.979992]
• 28: Y. Tung and W. Aldiwan. Automating test case generation for the new generation mission software system. IEEE Aerospace Conf., pages 431--37, 2000.
• 29: M. B. Wells. Elements of Combinatorial Computing. Pergamon Press, Oxford-New York-Toronto, 1971.
• 30: Alan W. Williams, Determination of Test Configurations for Pair-Wise Interaction Coverage, Proceedings of the IFIP TC6/WG6.1 13th International Conference on Testing Communicating Systems: Tools and Techniques, p.59-74, August 29-September 01, 2000
• 31: A. W. Williams , R. L. Probert, A practical strategy for testing pair-wise coverage of network interfaces, Proceedings of the The Seventh International Symposium on Software Reliability Engineering (ISSRE '96), p.246, October 30-November 02, 1996
• 32: Alan W. Williams , Robert L. Probert, A Measure for Component Interaction Test Coverage, Proceedings of the ACS/IEEE International Conference on Computer Systems and Applications, p.304, June 25-29, 2001
• 33: Cemal Yilmaz , Myra B. Cohen , Adam Porter, Covering arrays for efficient fault characterization in complex configuration spaces, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA

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)

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
covering arrays, greedy algorithm, mixed-level covering arrays, pair-wise interaction coverage, software interaction testing