Introduction to Combinatorial Testing - Automatic Generation of Combinatorial Test Data - page 14

test case generator (AETG) [ 8 , 9 ]. This algorithm extends the CA one row at a time. It
will be described in detail in Chap. 3 .
Another important greedy approach to CA generation is the In Parameter Order (IPO)
algorithm [ 28 ]. It is different fromAETG in that it expands the array incrementally, both
horizontally and vertically. The IPO algorithm and its descendants will be described in
Chap. 4 .
The problem of generating small CAs can be regarded as a constraint solving and
optimization problem. In addition to problem-specific algorithms like AETG and IPO,
we may also use many general-purpose search methods from artificial intelligence,
operations research and evolutionary computation communities. Chapter 5 is devoted to
the application of evolutionary algorithms (like genetic algorithms, simulated annealing,
etc.) and tabu search to the generation of CAs. In Chap. 6 , we shall describe backtracking
search algorithms for finding CAs and OAs.
In Chap. 7 , we list some available test generation tools and some well-known bench-
marks. The reader can try these tools on the benchmarks, or use the tools to solve your
own problems. Finally, in Chap. 8 , we briefly touch some topics that are related to com-
binatorial test generation. They include, how to construct a CT model for the SUT, how
to select a subset of test cases from an existing test suite, how to generate special-purpose
test cases in the process of debugging, and so on.
References
1. Ammann, P., Offutt, J.: Introduction to Software Testing. Cambridge University Press, Cam-
bridge (2008)
2. Arcuri, A., Briand, L.: Formal analysis of the probability of interaction fault detection using
random testing. IEEE Trans. Softw. Eng. 38 (5), 1088-1099 (2012)
3. Bose, R.C., Bush, K.A.: Orthogonal arrays of strength two and three. Ann. Math. Stat. 23 (4),
508-524 (1952)
4. Brownlie, R., Prowse, J., Phadke, M.S.: Robust testing of AT&T PMX/StarMAIL using OATS.
AT&T Tech. J. 71 (3), 41-47 (1992)
5. Calvagna, A., Fornaia, A., Tramontana, E.: Combinatorial interaction testing of a Java Card
static verifier. In: Proceedings of the IEEE International Conference on Software Testing,
Verification and Validation Workshops (ICSTW'14), pp. 84-87 (2014)
6. Chen, B., Yan, J., Zhang, J.: Combinatorial testing with shielding parameters. In: Proceedings
of the 17th Asia Pacific Software Engineering Conference (APSEC), pp. 280-289 (2010)
7. Chen, B., Zhang, J.: Tuple density: a new metric for combinatorial test suites. In: Proceedings
of the 33rd International Conference on Software Engineering (ICSE), pp. 876-879 (2011)
8. Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The AETG system: An approach to
testing based on combinatorial design. IEEE Trans. Softw. Eng. 23 (7), 437-444 (1997)
9. Cohen, D.M., Dalal, S.R., Kajla, A., Patton, G.C.: The Automatic Efficient Test Generator
(AETG) system. In: Proceedings of the 5th International Symposium on Software Reliability
Engineering (ISSRE), pp. 303-309 (1994)
10. Cohen, D.M., Dalal, S.R., Parelius, J., Patton, G.C.: The combinatorial design approach to
automatic test generation. IEEE Softw. 13 (5), 83-89 (1996)
11. Cohen, M. B., Gibbons, P. B., Mugridge, W. B., Colbourn, C. J.: Constructing test suites for
interaction testing. In: Proceedings of the 25th International Conference on Software Engineer-
ing (ICSE), pp. 38-48 (2003)