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

1.5 Pointers to the Literature
For the past three decades, many papers have been published in journals and confer-
ence proceedings in the fields of software engineering, theoretical computer science,
discrete mathematics, and computational intelligence. Started in 2012, the International
Workshop on Combinatorial Testing (IWCT) is held annually. The proceedings of the
first three workshops (2012-2014) are available as part of the proceedings of the IEEE
International Conference on Software Testing, Verification and Validation Workshops
(ICSTW).
There are also some good (survey) articles and topics in the literature, which provide
rich sources of information about CT.
Kuhn et al. published the first book on CT [ 23 ], with some emphasis on the practical
aspects of the technology. In addition to the basic concepts of CT, it covers many related
topics, including random test generation, test suite prioritization, assertion-based testing
and fault localization. The last chapter of the topic presents algorithms for constructing
CAs; but only two algorithms are described in detail: AETG and IPOG.
Mathur wrote a comprehensive topic on software testing [ 31 ]. One chapter in that
topic is devoted to testing based on combinatorial designs. Another recent topic on
software testing, written by Ammann and Offutt [ 1 ], also has a section on combination
strategies.
Grindal et al. published a survey [ 19 ], which presents 16 different combination strate-
gies. The paper explores some properties of combination strategies, including coverage
criteria and theoretical bounds on the size of test suites. It also attempts to relate the
various coverage criteria, via a kind of subsumption hierarchy.
A more recent survey of CT is written by Nie and Leung [ 32 ]. Lawrence et al. [ 27 ]
give a survey of binary CAs, including theorems about the existence of such arrays,
bounds on CANs, and methods of producing binary CAs.
1.6 Structure of This Topic
In software testing, a challenging task is to find a small test suite for a given SUT, which
meets certain coverage criteria. For CT, we are mostly concerned with finding a small
CA with a certain strength. It is shown [ 28 ] that the problem of generating a minimum
pairwise test set is NP-complete. Thus, the test data generation problem for CT is a
challenging problem. This topic will describe various methods for constructing small
combinatorial test suites satisfying certain requirements.
As mentioned earlier, CT is closely related to combinatorial design theory, which is a
part of discrete mathematics. Mathematicians have been working in this area for a long
time. Many results have been obtained, which may be useful in constructing CAs and
OAs. Some of these results will be presented in Chap. 2 .
Instead of using mathematical methods, which are usually applicable to some specific
cases, we can also use computational methods, i.e., computer algorithms. One of the
first influential computational method is the greedy algorithm of the automatic efficient