Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Algorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples associated with higher strength hinders the efficacy of interaction testing. Test suites are inherently large, so testers may not run entire test suites. To address these problems, we combine a simple greedy algorithmallwith heuristic search to construct and dispense one test at a time. Our algorithm attempts to maximize the number of t-tuples covered by the earliest tests so that if a tester only runs a partial test suite, they test as many t-tuples as possible.allHeuristic search is shown to provide effective methods for achieving such coverage.

REFERENCES

• 1: R. C. Bryce, Y. Chen, and C. J. Colbourn. Biased covering arrays for progressive ranking and composition of web services. International Journal of Simulation and Process Modeling, to appear.
• 2: R. C. Bryce and C. J. Colbourn. Prioritized interaction testing for pairwise coverage with seeding and avoids. Information and Software Technology Journal (IST, Elsevier), 40(10):960--970, Oct. 2006.
• 3: R. C. Bryce and C. J. Colbourn. A density-based greedy algorithm for higher strength covering arrays. submitted for review.
• 4: R. C. Bryce and C. J. Colbourn. The density algorithm for pairwise interaction testing. Journal of Software Testing, Verification, and Reliability, to appear.
• 5: Renée C. Bryce , Charles J. Colbourn , Myra B. Cohen, A framework of greedy methods for constructing interaction test suites, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062495]
• 6: K. Burr and W. Young. Combinatorial test techniques: Table-based automation, test generation, and code coverage. In Intl. Conference on Software Testing Analysis and Review, pages 503--513, Oct. 1998.
• 7: M. Chateauneuf and D. L. Kreher. On the state of strength-three covering arrays. J. Combin. Des., 10(4):217--238, 2002.
• 8: 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
• 9: 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]
• 10: 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]
• 11: 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
• 12: M. B. Cohen, C. J. Colbourn, and A. C. H. Ling. Constructing strength three covering arrays with augmented annealing. Discrete Mathematics, to appear.
• 13: C. J. Colbourn. Combinatorial aspects of covering arrays. Le Matematiche (Catania), 58:121--167, 2004.
• 14: C. J. Colbourn. Covering array tables, July 2006. public.asu.edu/<ccolbou/src/tabby/catable.html, accessed on January 15, 2007.
• 15: S. R. Dalal , A. Jain , N. Karunanithi , J. M. Leaton , C. M. Lott , G. C. Patton , B. M. Horowitz, Model-based testing in practice, Proceedings of the 21st international conference on Software engineering, p.285-294, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302640]
• 16: Gunter Dueck, New optimization heuristics, Journal of Computational Physics, v.104 n.1, p.86-92, Jan. 1993 [doi>10.1006/jcph.1993.1010]
• 17: 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]
• 18: A. Hartman and L. Raskin. Problems and algorithms for covering arrays. Discrete Math., 284(1--3):149--156, Jul. 2004.
• 19: B. Hnich, S. Prestwich, and E. Selensky. Constraint-based approaches to the covering test problem. Lecture Notes in Computer Science, 3419(1):172--186, Mar. 2005.
• 20: 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
• 21: 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]
• 22: 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]
• 23: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 24: Toshiaki Shiba , Tatsuhiro Tsuchiya , Tohru Kikuno, Using Artificial Life Techniques to Generate Test Cases for Combinatorial Testing, Proceedings of the 28th Annual International Computer Software and Applications Conference (COMPSAC'04), p.72-77, September 28-30, 2004
• 25: J. Stardom. Metaheuristics and the search for covering and packing arrays. Masters thesis, Simon Fraser University, 2001.
• 26: 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]
• 27: Y.W. Tung and W.S. Aldiwan. Automating test case generation for the new generation mission software system. In IEEE Aerospace Conference, pages 431--37, Mar. 2000.
• 28: Renee Cathryn Turban , Charles Colbourn, Algorithms for covering arrays, Arizona State University, Tempe, AZ, 2006
• 29: 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
• 30: Cemal Yilmaz , Myra B. Cohen , Adam A. Porter, Covering Arrays for Efficient Fault Characterization in Complex Configuration Spaces, IEEE Transactions on Software Engineering, v.32 n.1, p.20-34, January 2006 [doi>10.1109/TSE.2006.8]

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, great flood, heuristic search, hill climbing, simulated annealing, software interaction testing, t-way interaction testing, tabu search, test suite prioritization