DOI: 10.3724/SP.J.1001.2009.03497

Journal of Software (软件学报) 2009/20:6 PP.1393-1405

Combinatorial Testing: Principles and Methods

Combinatorial testing can use a small number of test cases to test systems while preserving fault detection ability. However, the complexity of test case generation problem for combinatorial testing is NP-complete. The efficiency and complexity of this testing method have attracted many researchers from the area of combinatorics and software engineering. This paper summarizes the research works on this topic in recent years. They include: various combinatorial test criteria, the relations between the test generation problem and other NP-complete problems, the mathematical methods for constructing test cases, the computer search techniques for test generation and fault localization techniques based on combinatorial testing.

Key words:combinatorial testing,covering array,test case generation

ReleaseDate:2014-07-21 14:40:59

Funds:Supported by the National Natural Science Foundation of China under Grant Nos.60673044, 60633010

[1] Kuhn DR, Reilly MJ. An investigation of the applicability of design of experiments to software testing. In: Caulfield M, ed. Proc. of the Annual NASA/IEEE Software Engineering Workshop (SEW). Los Alamitos: IEEE Press, 2002. 91-95.

[2] Godbole AP, Skipper DE, Sunley RA. t-Covering arrays: Upper bounds and Poisson approximations. Combinatorics, Probability and Computing, 1996,5:105-118.

[3] Kuhn R, Lei Y, Kacker R. Practical combinatorial testing: Beyond pairwise. IT Professional, 2008,10(3):19-23.

[4] Grindal M. Handling combinatorial explosion in software testing [Ph.D. Thesis]. Linköpings Universitet, 2007.

[5] Cohen MB, Gibbons PB, Mugridge WB, Colbourn CJ. Constructing test suites for interaction testing. In: Dillon L, Tichy W, eds. Proc. of the Int’l Conf. on Software Engineering (ICSE). Loa Alamitos: IEEE Press, 2003. 38-48.

[6] Nie CH, Xu BW, Shi L. A new pairwise covering test data generation algorithm for the system with many 2-level factors. Chinese Journal of Computers, 2006,29(6):841-848 (in Chinese with English abstract).聂长海,徐宝文,史亮.一种新的二水平多因素系统两两组合覆盖测试数据生成算法.计算机学报,2006,29(6):841-848.

[7] Colbourn CJ. CA tables for t= 2,3,4,5,6. 2009.

[8] Seroussi G, Bshouty NH. Vector sets for exhaustive testing of logical circuits. IEEE Trans. on Information Theory, 1988,34(3): 513-522.

[9] Lei Y, Tai KC. In-Parameter-Order: A test generation strategy for pairwise testing. In: Tsai J, Keefe T, Stewart D, eds. Proc. of the IEEE Int’l. Symp. on High Assurance Systems Engineering. Los Alamitos: IEEE Press, 1998. 254-261.

[10] Dalal SR, Jain A, Karunanithi N, Leaton JM, Lott CM, Patton GC, Horowitz BM. Model-Based testing in practice. In: Boehm B, Garlan D, Kramer J, eds. Proc. of the Int’l Conf. on Software Engineering (ICSE). New York: ACM Press, 1999. 285-294.

[11] Cohen DM, Dalal SR, Fredman ML, Patton G. The AETG system: An approach to testing based on combinatorial design. IEEE Trans. on Software Engineering, 1997,23(7):437-443.

[12] Czerwonka J. Pairwise testing in real world: Practical extensions to test case generators. In: Butt D, Gens C, eds. Proc. of the 24th Pacific Northwest Software Quality Conf. 2006.

[13] Cohen MB, Gibbons PB, Mugridge WB, Colbourn CJ. Variable strength interaction testing of components. In: Bae D, Voas J, eds. Proc. of the IEEE Annual Int’l Computer Software and Applications Conf. (COMPSAC). Los Alamitos: IEEE Press, 2003. 413-418.

[14] Schroeder PJ, Korel B. Black-Box test reduction using input-output analysis. In: Harold MJ, ed. Proc. of the Int’l Symp. on Software Testing and Analysis (ISSTA). New York: ACM Press, 2000. 173-177.

[15] Cheng C, Dumitrescu A, Schroeder PJ. Generating small combinatorial test suites to cover input-output relationships. In: Lin H, Ehrich HD, eds. Proc. of the 3rd Int’l Conf. on Quality Software (QSIC). Los Alamitos: IEEE Press, 2003. 76-82.

[16] Wang ZY, Nie CH, Xu BW, Shi L. Optimal test suite generation methods for neighbor factors combinatorial testing. Chinese Journal of Computers, 2007,30(2):200-211 (in Chinese with English abstract).王子元,聂长海,徐宝文,史亮.相邻因素组合测试用例集的最优生成方法.计算机学报,2007,30(2):200-211.

[17] Wang ZY, Nie CH, Xu BW. Generating combinatorial test suite for interaction relationship. In: Pezzè M, ed. Proc. of the 4th Int’l Workshop on Software Quality Assurance (SOQUA 2007). New York: ACM Press, 2007. 55-61.

[18] Sloane NJA. A library of orthogonal arrays.

[19] Yan J, Zhang J. A backtracking search tool for constructing combinatorial test suites. The Journal of Systems and Software, 2008, 81(10):1681-1693.

[20] Ma F, Zhang J. Finding orthogonal arrays using satisfiability checkers and symmetry breaking constraints. In: Ho TB, Zhou ZH, eds. Proc. of the 10th Pacific Rim Int’l Conf. on Artificial Intelligence (PRICAI 2008). LNAI 5351, Berlin/Heidelberg: Springer-Verlag, 2008. 247-259.

[21] Chateauneuf M, Kreher D. On the state of strength-three covering arrays. Journal of Combinatorial Designs, 2002,10(4):217-238.

[22] Williams AW, Probert RL. A practical strategy for testing pair-wise coverage of network interfaces. In: Lyu MR, ed. Proc. of the 7th Int’l Symp. on Software Reliability Engineering (ISSRE). Los Alamitos: IEEE Press, 1996. 246-254.

[23] Bryce RC, Colbourn CJ. The density algorithm for pairwise interaction testing. Software Testing, Verification and Reliability, 2007. 17(3):159-182.

[24] Stevens B, Mendelsohn E. New recursive methods for transversal covers. Journal of Combinatorial Designs, 1999,7(3):185-203.

[25] Colbourn CJ, Dinitz JH. Handbook of combinatorial designs. 2nd ed., Discrete Mathematics and Its Applications Series, Boca Raton: Chapman & Hall/CRC, 2006.

[26] Colbourn CJ, Martirosyan SS, Mullen GL, Shasha D, Sherwood GB, Yucas JL. Products of mixed covering arrays of strength two. Journal of Combinatorial Designs, 2006,14(2):124-138.

[27] Martirosyan S, Trung TV. On t-covering arrays. Designs, Codes and Cryptography, 2004,32(1):323-339.

[28] Katona GOH. Two applications (for search theory and truth functions) of Sperner type theorems. Periodica Mathematica. Hungarica, 1973,3(1-2):19-26.

[29] Kleitman DJ, Spencer J. Families of k-independent sets. Discrete Mathematics, 1973,6:255-262.

[30] Chateauneuf MA, Colbourn CJ, Kreher DL. Covering arrays of strength three, Designs, Codes Cryptography, 1999,16(3):235-242.

[31] Sherwood G. On the construction of orthogonal arrays and covering arrays using permutation groups. gsherwood/cover.htm


[33] Williams AW. TConfig: Test configuration generator. 2009.

[34] IBM Intelligent Test Case Handler. 2009.

[35] Hartman A, Raskin L. Problems and algorithms for covering arrays. Discrete Mathematics, 2004,284(1-3):149-156.

[36] Zhang J. Deciding Satisfiability of Logic Formulae: Methods, Tools and Applications. Beijing: Science Press, 2000 (in Chinese).张健.逻辑公式的可满足性判定――方法、工具及应用.北京:科学出版社,2000.

[37] SAT Live! 2009,

[38] Hnich B, Prestwich S, Selensky E. Constraint-Based approaches to the covering test problem. In: Faltings B, Petcu A, Fages F, Rossi F, eds. Proc. of the Joint Annual Workshop of ERCIM/CoLogNet on Constraint Solving and Constraint Logic Programming (CSCLP). Berlin/Heidelberg: Springer-Verlag, 2004. 172-186.

[39] Yan J, Zhang J. Backtracking algorithms and search heuristics to generate test suites for combinatorial testing. In: Wong J, ed. Proc. of the IEEE Annual Int’l Computer Software and Applications Conf. (COMPSAC). Los Alamitos: IEEE Press, 2006. 385-394.

[40] Williams AW, Probert RL. Formulation of the interaction test coverage problem as an integer program. In: Schieferdecker I, König H, Wolisz A, eds. Proc. of the 14th Int’l Conf. on the Testing of Communicating Systems (TestCom). Berlin: Kluwer, 2002. 283-298.

[41] Meagher K, Stevens B. Covering arrays on graphs. Journal of Combinatorial Theory (Series B), 2005,95(1):134-151.

[42] Meagher K, Moura L, Zekaoui L. Mixed covering arrays on graphs. Journal of Combinatorial Designs, 2007,15(5):393-404.

[43] Zekaoui L. Mixed covering arrays on graphs and tabu search algorithms [MS. Thesis]. Ottawa-Carleton Institute for Computer Science, University of Ottawa, 2006.

[44] Czerwonka J. Pairwise Testing. 2009.

[45] Tung YW, Aldiwan WS. Automating test case generation for the new generation mission software system. In: Proc. of the IEEE Aerospace Conf. 2000. 431-437.

[46] Shi L, Nie CH, Xu BW. Pairwise test data generation based on solution space tree. Chinese Journal of Computers, 2006,29(6): 849-857 (in Chinese with English abstract).史亮,聂长海,徐宝文.基于解空间树的组合测试数据生成.计算机学报,2006,29(6):849-857.

[47] Lei Y, Kacker R, Kuhn DR, Okun V, Lawrence J. IPOG: A general strategy for t-way software testing. In: Leaney J, O’Neill T, Peng J, eds. Proc. of the Annual IEEE Int’l Conf. and Workshops on the Engineering of Computer-Based Systems (ECBS). Los Alamitos: IEEE Press, 2007. 549-556.

[48] Kuhn R. An algorithm for generating very large covering arrays. Technical Report, NISTIR7308, 2006.

[49] Shiba T, Tsuchiya T, Kikuno T. Using artificial life techniques to generate test cases for combinatorial testing. In: Wong WE, Kanoun K, eds. Proc. of the IEEE Annual Int’l Computer Software and Applications Conf. (COMPSAC). Alamitos: IEEE Press, 2004. 72-77.

[50] Nurmela KJ. Upper bounds for covering arrays by tabu search. Discrete Applied Mathematics, 2004,138(9):143-152.

[51] Yilmaz C, Cohen MB, Porter MB. Covering arrays for efficient fault characterization in complex configuration spaces. IEEE Trans. on Software Engineering, 2006,32(1):20-34.

[52] Xu BW, Nie CH, Shi L, Chen HW. A software failure debugging method based on combinatorial design approach for testing. Chinese Journal of Computers, 2006,29(1):132-138 (in Chinese with English abstract).徐宝文,聂长海,史亮,陈火旺.一种基于组合测试的软件故障调试方法.计算机学报,2006,29(1):132-138.

[53] Schroeder PJ, Bolaki P, Gopu V. Comparing the fault detection effectiveness of n-way and random test suites. In: Juristo N, Shull F, eds. Proc. of the Int’l Symp. on Empirical Software Engineering (ISESE). Alamitos: IEEE Press, 2004. 49-59.

[54] Bach J, Shroeder P. Pairwise testing—A best practice that isn’t. In: Butt D, Derby E, eds. Proc. of the 22nd Pacific Northwest Software Quality Conf. 2004. 180-196.