Jeff Lei
Jeff Lei is an assistant professor of Computer Science at the University of Texas, Arlington. He can be contacted at [email protected].
DDJ:Pairwise testing is considered the traditional approach to testing. Can you tell us what pairwise testing is?
JL: Assume that a software object has n input parameters, each parameter having d possible values. One straightforward approach to testing this object is to test every possible n-way combination of values; for instance, every combination of values of the n parameters. This approach covers the entire input space, but is nearly always impractical for real-world software due to the well-known combinatorial explosion problem.
Pairwise testing is an alternative approach that only tries to test every possible two-way combination of values; that is, every combination of values of any two parameters. Testing all two-way combinations, instead of all n-way combinations, does not cover the entire input space. However, empirical studies show that many software faults are caused by interactions between only two parameters. Testing all two-way combinations can effectively detect these faults, while substantially reducing the number of tests.
DDJ: Where does pairwise testing come up short or in what ways does it reach its limits?
JL: Pairwise testing primarily targets faults caused by interactions between two parameters. However, some faults can be caused by interactions involving more than two parameters. Those faults cannot effectively be detected by pairwise testing.
DDJ: Combinatorial testing, which is the focus of much of your current research, seems to address these shortcomings. Can you tell us what combinatorial testing is?
JL: Combinatorial testing is a more general type of testing than pairwise testing. Instead of focusing on two-way combinations, combinatorial testing tests all t-way combinations, where t is referred to as the strength of testing and can be chosen by the user.
DDJ: Are there situations where combinatorial testing doesn't make sense?
JL: Combinatorial testing does not make sense when only a few of the input parameters interact with each other. A group of parameters interact if their values jointly affect the runtime behavior of the object under test. Note that for combinatorial testing to be effective, the input parameters and the values those parameters can take need to be identified. Approaches such as category partitioning can be used to identify the parameters and their possible values.
DDJ: Can you share a real-world scenario/example of how combinatorial testing solved a problem?
JL: A recent study of actual faults by D. R. Kuhn et al. at NIST examined several open-source software applications and reported that all of the known faults are caused by interactions involving no more than six parameters. This study is, however, in retrospect. We are currently collaborating with several groups to apply combinatorial testing to real-world applications.
DDJ: Can you tell us about the unique algorithms that form the foundations for combinatorial testing?
JL: The main challenge for combinatorial testing is to generate a test set that guarantees the test coverage chosen by the user and that is as small as possible. Existing algorithms for pairwise testing can be extended for general combinatorial testing. However, because of the higher strength of testing, general combinatorial testing has higher space and time requirements than pairwise testing. Therefore, general combinatorial testing algorithms must strike a balance between the size of the test sets that they generate and the amount of time and space that they require.
DDJ: What about source code implementations of the concept? Have you or anyone else implemented combinatorial testing in working programs?
JL: A combinatorial testing tool called "FireEye" has been developed by NIST and the University of Texas at Arlington (UTA). FireEye implements several combinatorial testing algorithms developed by the Automated Combinatorial Testing for Software group (csrc.nist.gov/groups/SNS/acts/index.html), which involves NIST, UTA, and several other universities. FireEye can quickly generate t-way test sets up to six-way testing.
DDJ: What about scalability? Does combinatorial testing scale well?
JL: As a black-box testing technique, combinatorial testing does not examine the source code. The main factor to be considered for scalability is the size of the input space, which is determined by the number of parameters and number of possible values each parameter can take. With appropriate abstractions, the newly developed algorithms for combinatorial testing can quickly generate test sets for up to six-way testing, which we believe will be effective for real-world applications.
