The IPO Family - Automatic Generation of Combinatorial Test Data - page 47

to the row. They also provided an optimization to reduce the computation cost
to determine the number of newly-covered target combinations when selecting
values for each row.

• Enumeration of value combinations . Since the IPOG strategy explicitly enumer-

ates all target combinations, and the number of target combinations may grow
exponentially as the covering strength t increases, the cost will be extremely large
when k , t and s are large. The IPOG-D algorithm [ 5 ] combines the IPOG algo-
rithm with a mathematical construction method called “D-construction”, which
can double the number of parameters in a three-way covering array [ 1 ]. IPOG-
D divides the parameters into two groups. It constructs a t -way covering array
for the first group and a -way covering array for the second group; then

it uses D-construction to construct a larger array of all the parameters. If t

( t − 1 )

3,
IPOG-Dwill use the vertical growth of the IPOG algorithm to cover the uncovered
target combinations. By using D-construction, the number of enumerated target
combinations can be greatly reduced.

>

References

1. Chateauneuf, M.A., Colbourn, C.J., Kreher, D.L.: Covering arrays of strength three. Des. Codes
Cryptogr. 16 (3), 235-242 (1999)
2. Forbes, M., Lawrence, J., Lei, Y., Kacker, R.N., Kuhn, D.R.: Refining the in-parameter-order
strategy for constructing covering arrays. J. Res. Natl. Inst. Stand. Technol. 113 (5), 287-297
(2008)
3. Lei, Y., Tai, K.C.: In-parameter-order: a test generation strategy for pair-wise testing. In: Pro-
ceedings of the 3rd IEEE International Symposium on High-Assurance Systems Engineering
(HASE'98), IEEE Computer Society, pp. 254-261 (1998)
4. Lei, Y., Kacker, R., Kuhn, D.R., Okun, V., Lawrence, J.: 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, pp. 549-
556 (2007)
5. Lei, Y., Kacker, R., Kuhn, D.R., Okun, V., Lawrence, J.: IPOG/IPOG-D: efficient test generation
for multi-way combinatorial testing. Softw. Test. Verification Reliab. 18 (3), 125-148 (2008)
6. Nie, C., Xu, B., Shi, L., Dong, G.: Automatic test generation for n-way combinatorial testing.
In: Quality of Software Architectures and Software Quality (QoSA-SOQUA), Springer LNCS
3712, pp. 203-211 (2005)
7. Tai, K.C., Lei, Y.: A test generation strategy for pairwise testing. IEEE Trans. Softw. Eng.
28 (1), 109-111 (2002)
8. Wang, Z., Nie, C., Xu, B.: Generating combinatorial test suite for interaction relationship. In:
Proceedings of the Fourth International Workshop on Software Quality Assurance (SOQUA
2007), ACM, pp. 55-61 (2007)
9. Wang, Z., Xu, B., Nie, C.: Greedy heuristic algorithms to generate variable strength combina-
torial test suite. In: Proceedings of the Eighth International Conference on Quality Software
(QSIC'08), IEEE, pp. 155-160 (2008)
10. Yu, L., Lei, Y., Nourozborazjany, M., Kacker, R. N., Kuhn, D. R.: An efficient algorithm for
constraint handling in combinatorial test generation. In: Proceedings of the Sixth International
Conference on Software Testing, Verification and Validation (ICST'13), IEEE, pp. 242-251
(2013)