A survey of combinatorial testing

Abstract

Combinatorial Testing (CT) can detect failures triggered by interactions of parameters in the Software Under Test (SUT) with a covering array test suite generated by some sampling mechanisms. It has been an active field of research in the last twenty years. This article aims to review previous work on CT, highlights the evolution of CT, and identifies important issues, methods, and applications of CT, with the goal of supporting and directing future practice and research in this area. First, we present the basic concepts and notations of CT. Second, we classify the research on CT into the following categories: modeling for CT, test suite generation, constraints, failure diagnosis, prioritization, metric, evaluation, testing procedure and the application of CT. For each of the categories, we survey the motivation, key issues, solutions, and the current state of research. Then, we review the contribution from different research groups, and present the growing trend of CT research. Finally, we recommend directions for future CT research, including: (1) modeling for CT, (2) improving the existing test suite generation algorithm, (3) improving analysis of testing result, (4) exploring the application of CT to different levels of testing and additional types of systems, (5) conducting more empirical studies to fully understand limitations and strengths of CT, and (6) combining CT with other testing techniques.

References

1. Bach, J. and Schroeder, P. J. 2004. Pairwise testing - A best practice that isn't. In Proceedings of the 22nd Pacific Northwest Software Quality Conference. 180--196.
2. Berling, T. and Runeson, P. 2003. Efficient evaluation of multifactor dependent system performance using fractional factorial design. IEEE Trans. Softw. Engin. 29, 9, 769--781.
3. Blass, A. and Gurevich, Y. 2002. Pairwise testing. Bull. Euro. Assoc. Theor. Comput. Sci. 78, 100--132.
4. Brownlie, R., Prowse, J., and Phadke, M. S. 1992. Robust testing of at and t pmx/starmail using oats. AT and T Techn. 3, 71, 41--47.
5. Bryce, R. C. and Colbourn, C. J. 2005. Constructing interaction test suites with greedy algorithms. In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering (ASE'05). ACM, New York, 440--443.
6. Bryce, R. C. and Colbourn, C. J. 2006. Prioritized interaction testing for pair-wise coverage with seeding and constraints. Inform. Softw. Technol. 48, 10, 960--970.
7. Bryce, R. C. and Colbourn, C. J. 2007a. The density algorithm for pairwise interaction testing. Softw. Test. Verif. Reliab. 17, 3, 159--182.
8. Bryce, R. C. and Colbourn, C. J. 2007b. One-Test-at-a-Time heuristic search for interaction test suites. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO'07). ACM, New York, 1082--1089.
9. Bryce, R. C. and Colbourn, C. J. 2008. A density-based greedy algorithm for higher strength covering arrays. Softw. Test. Verif. Reliab. 17, 3, 1--17.
10. Bryce, R. C., Colbourn, C. J., and Cohen, M. B. 2005. A framework of greedy methods for constructing interaction test suites. In Proceedings of the 27th International Conference on Software Engineering (ICSE'05). ACM, New York, 146--155.
11. Bryce, R. C. 2005. Test prioritization for pairwise interaction coverage. In Proceedings of the 1st International Workshop on Advances in Model-Based Testing (A-MOST'05). ACM, New York, 1--7.
12. Bryce, R. C. and Memon, A. M. 2007. Test suite prioritization by interaction coverage. In Workshop on Domain Specific Approaches to Software Test Automation (DOSTA'07). ACM, New York, 1--7.
13. Burr, K. and Young, W. 1998. Combinatorial test techniques: Table-Based automation, test generation, and code coverage. In Proceedings of the International Conference on Software Testing Analysis and Review. 503--513.
14. Burroughs, K., Jain, A., and Erickson, R. 1994. Improved quality of protocol testing through techniques of experimental design. In Proceedings of the IEEE International Conference on Record, 'Serving Humanity Through Communications.' Vol. 2. 745--752.
15. Cheng, C., Dumitrescu, A., and Schroeder, P. 2003. Generating small combinatorial test suites to cover input-output relationships. In Proceedings of the 3rd International Conference on Quality Software (QSIC'03). IEEE Computer Society, Los Alamitos, CA, 76--82.
16. Cohen, D. M., Dalal, S. R., Fredman, M. L., and Patton, G. C. 1997. The aetg system: An approach to testing based on combinatorial design. IEEE Trans. Softw. Engin. 23, 7, 437--444.
17. Cohen, D. M., Dalal, S. R., Kajla, A., and Patton, G. C. 1994. The automatic efficient tests generator. In Proceedings of the 5th IEEE International Symposium Software Reliability Engineering. IEEE Press, 303--309.
18. Cohen, D. M., Dalal, S. R., Parelius, J., and Patton, G. C. 1996. The combinatorial design approach to automatic test generation. IEEE Softw. 13, 5, 83--88.
19. Cohen, D. M. and Fredman, M. L. 1998. New techniques for designing qualitatively independent systems. J. Combin. Des. 6, 6, 411--416.
20. Cohen, M., Gibbons, P., Mugridge, W., Colbourn, C., and Collofello, J. 2003a. Variable strength interaction testing of components. In Proceedings of the 27th Annual International Conference on Computer Software and Applications. 413--418.
21. Cohen, M. B. 2004. Designing test suites for software interaction testing. Ph.D. thesis, University of Auckland, New Zealand.
22. Cohen, M. B., Colbourn, C. J., and Ling, A. C. H. 2003b. Augmenting simulated annealing to build interaction test suites. In Proceedings of the 14th International Symposium on Software Reliability Engineering (ISSRE'03). IEEE Computer Society, Los Alamitos, CA, 394.
23. Cohen, M. B., Dwyer, M. B., and Shi, J. 2007a. Exploiting constraint solving history to construct interaction test suites. In Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques (TAICPART-MUTATION'07). IEEE Computer Society, 121--132.
24. Cohen, M. B., Dwyer, M. B., and Shi, J. 2007b. Interaction testing of highly-configurable systems in the presence of constraints. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA'07). ACM, New York, 129--139.
25. Cohen, M. B., Dwyer, M. B., and Shi, J. 2008. Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach. IEEE Trans. Softw. Engin. 34, 5, 633--650.
26. Cohen, M. B., Gibbons, P. B., Mugridge, W. B., and Colbourn, C. J. 2003c. Constructing test suites for interaction testing. In Proceedings of the 25th International Conference on Software Engineering (ICSE'03). IEEE Computer Society, Los Alamitos, CA, 38--48.
27. Cohen, M. B., Snyder, J., and Rothermel, G. 2006. Testing across configurations: Implications for combinatorial testing. SIGSOFT Softw. Engin. Notes 31, 6, 1--9.
28. Colbourn, C. J. 2006. Detecting and locating interaction faults. Electron. Not. Discr. Math. 27, 14, 17--18.
29. Colbourn, C. J., Martirosyan, S. S., Mullen, G. L., Shasha, D., Sherwood, G. B., and Yucas, J. L. 2005. Products of mixed covering arrays of strength two. J. Combin. Des. 2, 14, 124--138.
30. Colbourn, C. J. and McClary, D. W. 2008. Locating and detecting arrays for interaction faults. J. Combin. Optimiz. 15, 1, 17--48.
31. Czerwonka, J. 2006. Pairwise testing in the real world: Practical extensions to test-case scenarios. In Proceedings of the 24th Pacific Northwest Software Quality Conference.
32. Dalal, S., Jain, A., Karunanithi, N., Leaton, J., and Lott, C. 1998a. Model-based testing of a highly programmable system. In Proceedings of the 9th International Symposium on Software Reliability Engineering (ISSRE'98). IEEE Computer Society, Los Alamitos, CA, 174.
33. Dalal, S. R., Jain, A., Karunanithi, N., Leaton, J. M., Lott, C. M., Patton, G. C., and Horowitz, B. M. 1999. Model-based testing in practice. In Proceedings of the 21st International Conference on Software Engineering (ICSE'99). IEEE Computer Society Press, Los Alamitos, CA, 285--294.
34. Dalal, S. R., Jain, A., Patton, G., Rathi, M., and Seymour, P. 1998b. Aetgsm web: A web based service for automatic efficient test generation from functional requirements. In Proceedings of the 2nd Workshop on Industrial-Strength Formal Specification Techniques (WIFT'98). IEEE Computer Society, Los Alamitos, CA, 84--85.
35. Dalal, S. R. and Mallows, C. L. 1998. Factor-Covering designs for testing software. Technometrics 40, 3, 234--243.
36. Denny, P. C. and Gibbons, P. B. 2000. Case studies and new results in combinatorial enumeration. J. Combin. Des. 8, 239--260.
37. Dong, G., Nie, C., Xu, B., and Wang, L. 2007. An effective iterative metamorphic testing algorithm based on program path analysis. In Proceedings of the 7th International Conference on Quality Software (QSIC'07). IEEE Computer Society, Los Alamitos, CA, 292--297.
38. Dumitrescu, A. 2003. Efficient algorithms for generation of combinatorial covering suites. In Proceedings of the 14th Annual International Symposium Algorithms and Computation (ISAAC'03). Springer, 300--308.
39. Dunietz, I. S., Ehrlich, W. K., Szablak, B. D., Mallows, C. L., and Iannino, A. 1997. Applying design of experiments to software testing: experience report. In Proceedings of the 19th International Conference on Software Engineering (ICSE'97). ACM, New York, 205--215.
40. Fisher, R. 1926. The arrangement of field experiments. J. Ministry Agricult. Great Britain 33, 503--513.
41. Fouché, S., Cohen, M. B., and Porter, A. 2007. Towards incremental adaptive covering arrays. In Proceedings of the the 6th Joint Meeting on European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC-FSE Companion'07). ACM, New York, 557--560.
42. Ghazi, S.A. Ahmed, M. 2003. Pair-wise test coverage using genetic algorithms. In Proceedings of the Congress on Evolutionary Computation (CEC'03). IEEE Computer Society, Los Alamitos, CA, 1420--1424.
43. Harman, M. 2007. The current state and future of search based software engineering. In Proceedings of the Conference on Future of Software Engineering FOSE'07, 342--357.
44. Hartman, A. 2002. Software and hardware testing using combinatorial covering suitess. Graph Theory, Combin. Algor. 6, 3, 237--266.
45. Hartman, A. and Raskin, L. 2004. Problems and algorithms for covering arrays. Discr. Math. 284, 1-3, 149--156.
46. Hnich, B., Prestwich, S., and Selensky, E. 2005. Constraint-Based approaches to the covering test problem. In Proceedings of the Joint ERCIM/Co-LogNET International Workship on Constraint Solving and Constraint Logic Programming. Lecture Notes in Computer Science. Springer Berlin, 172--186.
47. Hnich, B., Prestwich, S. D., Selensky, E., and Smith, B. M. 2006. Constraint models for the covering test problem. Constraints 11, 2-3, 199--219.
48. Huller, J. 2000. Reducing time to market with combinatorial design method testing. In Proceedings of the the International Council on Systems Engineering (INCOSE) Conference.
49. Kahng, A. B. and Reda, S. 2004. Combinatorial group testing methods for the bist diagnosis problem. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'04). IEEE Press, 113--116.
50. Kobayashi, N. 2002. Design and evaluation of automatic test generation strategies for functional testing of software. Ph.D. thesis, Osaka University, Osaka, Japan.
51. Kobayashi, N., Tsuchiya, T., and Kikuno, T. 2002. A new method for constructing pair-wise covering designs for software testing. Inform. Process. Lett. 81, 2, 85--91.
52. Krishnan, R., Krishna, S. M., and Nandhan, P. S. 2007. Combinatorial testing: Learnings from our experience. SIGSOFT Softw. Engin. Notes 32, 3, 1--8.
53. Kuhn, D. R. and Reilly, M. J. 2002. An investigation of the applicability of design of experiments to software testing. In Proceedings of the 27th Annual NASA Goddard Software Engineering Workshop (SEW'02). IEEE Computer Society, Los Alamitos, CA, 91.
54. Kuhn, D. R. and Wallace, D. R. 2004. Software fault interactions and implications for software testing. IEEE Trans. Softw. Engin. 30, 6, 418--421.
55. Lei, Y., Carver, R. H., Kacker, R., and Kung, D. C. 2007a. A combinatorial testing strategy for concurrent programs. Softw. Test., Verif. Reliab. 17, 4, 207--225.
56. Lei, Y., Kacker, R., Kuhn, D. R., Okun, V., and Lawrence, J. 2007b. Ipog: A general strategy for t-way software testing. In Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS'07). IEEE Computer Society, Los Alamitos, CA, 549--556.
57. Lei, Y., Kacker, R., Kuhn, D. R., Okun, V., and Lawrence, J. 2008. Ipog/ipog-d: Efficient test generation for multi-way combinatorial testing. Softw. Test., Verif. Reliab. 18, 3, 125--148.
58. Lei, Y. and Tai, K. C. 2001. In-parameter-oder: A test generation strategy for pairwise testing. Tech. rep. TR 2001-03 5, 109--111.
59. Li, Z., Harman, M., and Hierons, R. M. 2007. Search algorithms for regression test case prioritization. IEEE Trans. Softw. Engin. 33, 4, 225--237.
60. Lott, C., Jain, A., and Dalal, S. 2005. Modeling requirements for combinatorial software testing. SIGSOFT Softw. Engin. Notes 30, 4, 1--7.
61. Maity, S. and Nayak, A. 2005. Improved test generation algorithms for pair-wise testing. In Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering (ISSRE'05). IEEE Computer Society, Los Alamitos, CA, 235--244.
62. Mandl, R. 1985. Orthogonal latin squares: An application of experiment design to compiler testing. Commu. ACM 28, 10, 1054--1058.
63. Marre, M. and Bertolino, A. 2003. Using spanning sets for coverage testing. IEEE Trans. Softw. Engin. 29, 11, 974--984.
64. Mats, G., Lindstr, B., Offutt, J., and Andler, S. F. 2006a. An evaluation of combination strategies for test case selection. Empir. Softw. Engin. 11, 4, 583--611.
65. Mats, G. and Offutt, J. 2007. Input parameter modeling for combination strategies. In Proceedings of the 25th Conference on IASTED International Multi-Conference (SE'07). ACTA Press, 255--260.
66. Mats, G., Offutt, J., and Andler, S. F. 2005. Combination testing strategies: A survey. Softw. Test. Verif. Reliab. 15, 3, 167--199.
67. Mats, G., Offutt, J., and Mellin, J. 2006b. Handling constraints in the input space when using combination strategies for software testing. Tech. rep. HS-IKI-TR-06-001 1, 1--39.
68. Nie, C., Xu, B., Shi, L., and Dong, G. 2005. Automatic test generation for n-way combinatorial testing. In Proceedings of the 2nd International Workshop on Software Quality (SOQUA). Springer Berlin, 203--211.
69. Nie, C., Xu, B., Shi, L., and Wang, Z. 2006a. A new heuristic for test suite generation for pair-wise testing. In Proceedings of the International Conference on Software Engineering and Knowledge Engineering, (SEKE'06), 517--521.
70. Nie, C., Xu, B., Wang, Z., and Shi, L. 2006b. Generating optimal test set for neighbor factors combinatorial testing. In Proceedings of the 6th International Conference on Quality Software (QSIC'06). IEEE Computer Society, Los Alamitos, CA, 259--265.
71. Nurmela, K. J. 2004. Upper bounds for covering arrays by tabu search. Discr. Appl. Math. 138, 1-2, 143--152.
72. Offutt, A. J. 1994. A practical system for mutation testing: Help for the common programmer. In Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years. IEEE Computer Society, Los Alamitos, CA, 824--830.
73. Qu, X., Cohen, M., and Woolf, K. 2007. Combinatorial interaction regression testing: A study of test case generation and prioritization. In Proceedings of the IEEE International Conferance on Software Maintenance (ICSM). IEEE Computer Society, 413--418.
74. Salem, A. M. 2001. A software testing model: Using design of experiments (doe) and logistic regression. Ph.D. thesis, Florida Institute of Technology, Melbourne, Florida.
75. Salem, A. M., Rekab, K., and Whittaker, J. A. 2004. Prediction of software failures through logistic regression. Inform. Softw. Technol. 46, 12, 781--789.
76. Sampath, S., Bryce, R., Viswanath, G., Kandimalla, V., and Koru, A. 2008. Prioritizing user-session-based test cases for web applications testing. In Proceedings of the 1st International Conference on Software Testing, Verification, and Validation, 141--150.
77. Schroeder, P. J. 2002. Black-Box test reduction using input-output analysis. Ph.D. thesis, Illinois Institute of Technology, Chicago, IL.
78. Schroeder, P. J., Bolaki, P., and Gopu, V. 2004. Comparing the fault detection effectiveness of n-way and random test suites. In Proceedings of the International Symposium on Empirical Software Engineering (ISESE). IEEE Computer Society, 49--59.
79. Schroeder, P. J., Faherty, P., and Korel, B. 2002. Generating expected results for automated black-box testing. In Proceedings of the IEEE International Conference on Automated Software Engineering (ASE). IEEE Computer Society, 139--148.
80. Schroeder, P. J. and Korel, B. 2000a. Black-box test reduction using input-output analysis. SIGSOFT Softw. Engin. Notes 25, 5, 173--177.
81. Schroeder, P. J. and Korel, B. 2000b. Constraint of model-based test generation using input-output analysis. In Proceedings of the Automated Software Engineering Doctoral Symposium. ACM, 35--43.
82. Seroussi, G. and Bshouty, N. 1988. Vector sets for exhaustive testing of logic circuits. IEEE Trans. Inf. Theory 34, 3, 513--522.
83. Sherwood, G. 1994. Effective testing of factor combinations. In Proceedings of the 3rd International Conference on Software Testing, Analysis, and Review(STAR94).
84. Sherwood, G. B., Martirosyan, S. S., and Colbourn, C. J. 2005. Covering arrays of higher strength from permutation vectors. J. Combin. Des. 3, 14, 202--213.
85. Shi, L., Nie, C., and Xu, B. 2005. A software debugging method based on pairwise testing. In Proceedings of the International Conferences on Computational Science (ICCS'05). Springer, 1088--1091.
86. Shiba, T., Tsuchiya, T., and Kikuno, T. 2004. Using artificial life techniques to generate test cases for combinatorial testing. In Proceedings of the 28th Annual International Computer Software and Applications Conference (COMPSAC'04). IEEE Computer Society, Los Alamitos, CA, 72--77.
87. Tai, K. C. and Lei, Y. 2002. A test generation strategy for pairwise testing. IEEE Trans. Softw. Engin. 28, 1, 109--111.
88. Tung, Y.-W. and Aldiwan, W. 2000. Automating test case generation for the new generation mission software system. In Proceedings of the IEEE Aerospace Conference. 431--437.
89. Turban, R. C. 2006. Algorithms for covering arrays. Ph.D. thesis, University of Ahzam Tempe, AZ.
90. Wang, Z., Nie, C., and Xu, B. 2007. Generating combinatorial test suite for interaction relationship. In Proceedings of the 4th International Workshop on Software Quality Assurance (SOQUA'07). ACM, New York, 55--61.
91. Wang, Z., Xu, B., and Nie, C. 2008. Greedy heuristic algorithms to generate variable strength combinatorial test suite. In Proceedings of the International Conference on Quality Software (QSIC). 155--160.
92. White, L. and Almezen, H. 2000. Generating test cases for gui responsibilities using complete interaction sequences. In Proceedings of the 11th International Symposium on Software Reliability Engineering (ISSRE'00). IEEE Computer Society, Los Alamtos, CA, 110.
93. Williams, A. W. 2000. Determination of test configurations for pair-wise interaction coverage. In Proceedings of the IFIP TC6/WG6.1 13th International Conference on Testing Communicating Systems (TestCom'00). Kluwer, 59--74.
94. Williams, A. W. 2002. Software component interaction testing: coverage measurement and generation of configurations. Ph.D. thesis, University of Ottawa, Canada.
95. Williams, A. W. and Probert, R. L. 2002. Formulation of the interaction test coverage problem as an integer program. In Proceedings of the IFIP 14th International Conference on Testing Communicating Systems XIV (TestCom'02). Kluwer, 283.
96. Williams, A. W. and Probert, R. L. 1996. A practical strategy for testing pair-wise coverage of network interfaces. In Proceedings of the 7th International Symposium on Software Reliability Engineering (ISSRE'96). IEEE Computer Society, Los Alamtos, CA, 246.
97. Williams, A. W. and Probert, R. L. 2001. A measure for component interaction test coverage. In Proceedings of the ACS/IEEE International Conference on Computer Systems and Applications (AICCSA'01). IEEE Computer Society, Los Alamitos, CA, 304.
98. Xu, B., Nie, C., Shi, L., Chu, W. C., Yang, H., and Chen, H. 2003a. Test plan design for software configuration testing. In Software Engineering Research and Practice, CSREA Press, 686--692.
99. Xu, L., Xu, B., Nie, C., Chen, H., and Yang, H. 2003b. A browser compatibility testing method based on combinatorial testing. In Proceedings of the International Conference on Web Engineering (ICWE. Springer, Berlin, 310--313.
100. Yan, J. and Zhang, J. 2006. Backtracking algorithms and search heuristics to generate test suites for combinatorial testing. In Proceedings of the 30th Annual International Conference on Computer Software and Applications (COMPSAC'06). 385--394.
101. Yilmaz, C., Cohen, M. B., and Porter, A. A. 2006. Covering arrays for efficient fault characterization in complex configuration spaces. IEEE Trans. Softw. Engin. 32, 1, 20--34.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Verification

• Software and its engineering

  • Software creation and management

    • Designing software

      • Software implementation planning

        • Software design techniques

    • Software development process management

    • Software verification and validation

      • Formal software verification

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Software functional properties

      • Formal methods

        • Software verification

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program verification