Combinatorial Interaction Testing (CIT) approaches aim to reveal failures caused by the interactions of factors, such as input parameters and con guration options. Our ultimate goal in this line of research is to improve the practicality of CIT approaches. To this end, we have been working on developing what we call Uni ed Combinatorial Interaction Testing (U-CIT), which not only represents most (if not all) combinatorial objects that have been developed so far, but also allows testers to develop their own application-speci c combinatorial objects for testing. However, realizing U-CIT in practice requires us to solve an interesting constraint solving problem. In this work we informally de ne the problem and present a greedy algorithm to solve it. Our gaol is not so much to present a solution, but to introduce the problem, the solution of which (we believe) is of great practical importance.
Software systems frequently embody a wide spectrum of system variabilities that require testing,
such as software and hardware con guration options, user inputs, and thread interleavings.
However, exhaustively testing all possible variations in a timely manner (if not impossible at
all) is generally far beyond the available resources for testing [
CIT approaches work by rst de ning a model of the system's variability space. This model
typically includes a set of factors, each of which takes its value from a particular domain,
and a (possibly empty) set of inter-option constraints, each of which invalidates certain factor
value combinations, as not all possible combinations may be valid in practice. Based on this
model, CIT then generates a sample, meeting a speci ed coverage criterion. That is, the
sample contains some speci ed combinations of factors and their values. For instance, a t-way
covering array, which is a well-known and frequently-used CIT object, requires that each valid
combination of factor values for every combination of t factors, appears at least once in the
sample [
The basic justi cation for using CIT is that they can (under certain assumptions) e ectively and e ciently exercise all system behaviors caused by the interactions of t or fewer factors. The e ectiveness of CIT stems from the coverage properties it provides; e.g., all required t-way combinations of factor values are guaranteed to be covered at least once. The e ciency, on the other hand, stems from the fact that a test case can cover more than one required combination. For example, a con guration composed of n con guration options covers nt di erent t-way option setting combinations. That is, testing a single con guration has the potential of testing all nt combinations. Therefore, carefully generating test cases, such that a full coverage under the given coverage criterion is obtained using a minimum number of test cases can, for example, decrease the cost of testing.
The results of many empirical studies suggest that majority of factor-related failures in
practice are caused by the interactions of only a small number of factors. That is, t is small in
practice, typically 2 t 6 with t=2 (i.e., pairwise testing) being the most common case [
All these have so far been achieved by having researchers develop speci c models for de ning
variability spaces together with speci c coverage criteria to be used for testing, which in turn
led to the development of novel CIT objects for every unique testing scenario. However, when
the testing scenarios encountered in practice deviate from the ones addressed by researchers,
practitioners often have profound di culties in using these existing CIT objects [
We conjecture that the exibility, thus the applicability of CIT in practice, would greatly be improved, if there were better tools that allowed practitioners to de ne their own applicationspeci c variability spaces as well as their own application-speci c coverage criteria. That is, rather than we, as researchers, invent new CIT objects for testing and ask practitioners to use them, thus telling them what to test, we would like to enable practitioners to de ne their own space for testing as well as their own coverage criterion, thus enabling them to invent their own application-speci c CIT objects. Our goal as researchers is then to develop powerful tools to e ciently and e ectively sample the given space to obtain full coverage under the given criterion. Although such generic tools may not be as e cient as their specialized counterparts, they certainly can provide the exibility needed in practice. We call this approach Uni ed Combinatorial Interaction Testing (or U-CIT).
In this work we informally introduce U-CIT, which enables practitioners to de ne their own variability spaces and coverage criteria for testing, and present a uni ed construction approach to compute speci c instances of U-CIT objects. 2
Uni ed Combinatorial Interaction Testing (U-CIT) De nition 1. A U-CIT requirement is an entity that needs be covered. In U-CIT, requirements are expressed as constraints.
For example, for scenarios, in which standard covering arrays are used for testing highly con gurable systems, a U-CIT requirement corresponds to a t-tuple to be covered, where a t-tuple is a set of option-setting pairs for a combination of t distinct con guration options. De nition 2. A U-CIT test case is a collection of U-CIT test requirements that can be tested together, i.e., a set of constraints that can be satis ed together.
In our running scenario, for example, a U-CIT test case corresponds to a system con guration, which is indeed an n-tuple, where n is the number of con guration options. De nition 3. A U-CIT space model is a system of constraints that implicitly de ne the space of all valid U-CIT requirements as well as all valid U-CIT test cases, as not all possible combinations of U-CIT requirements may be valid in practice.
For our running scenario, a U-CIT space model speci es that 1) every con guration option must have a valid setting in a con guration, 2) a valid U-CIT requirement is a valid t-tuple that does not violate any inter-option constraints, and 3) a valid U-CIT test case is valid con guration that does not violate any inter-option constraints.
De nition 4. A U-CIT coverage criterion is a criterion that implicitly de nes all valid U-CIT requirements that need to be covered.
For example, the U-CIT coverage criterion for our running scenario states that all valid t-tuples must be covered at least once.
U-CIT takes as input a U-CIT space model and a U-CIT coverage criterion and as output
computes a U-CIT object, e.g., a set of valid U-CIT test cases, which achieves a full coverage
under the given criterion. Although it is possible to de ne additional constraints on the
emergent properties of the resulting objects, such as the objects must achieve a full coverage with
the \minimum" possible testing cost [
What makes a U-CIT approach a uni ed approach is that requirements to be covered, test cases, and the space from which the test cases will be drawn, are all expressed as constraints. Consequently, the problem of computing a U-CIT object turns into one big, interesting constraint solving problem. Note that we use the term \constraint" in the general sense; any restriction, independent of the logic in which it is speci ed, is considered to be a constraint. In other words, no matter whether the constraints are speci ed using Boolean logic, rst-order logic, temporal logic, etc., the proposed approach will work as long as an appropriate constraint solver is provided.
A U-CIT coverage criterion e ectively de nes a set of constraints to be satis ed (not necessarily all together, but in groups), each of which represents a U-CIT requirement. Given the requirements to be covered and a U-CIT space model further constraining the variability space from which the U-CIT test cases will be drawn, the constraint satisfaction problem we need to solve is to divide the requirements into a minimum number of non-overlapping sets of requirements, such that within each set, the constraints representing the requirements in the set as well as the model constraints are satis able together. In e ect, a solution for each set represents a valid U-CIT test case, i.e., a collection of U-CIT requirements that can be tested together. Therefore, the test cases generated for all the sets, represent a U-CIT object achieving full coverage under the given coverage criterion. In particular, by reducing the number of non-overlapping sets, thus the number of test cases, we attempt to reduce testing costs.
A Greedy Approach for Computing U-CIT Ob jects In this section we present a greedy algorithm (Algorithm 1) to compute U-CIT objects. Given a U-CIT space model M and a coverage criterion C, we rst determine all valid U-CIT requirements R (lines 2-7). To this end, we enumerate all the entities to be covered, convert each entity to a constraint r, and then determine whether r ^ M is satis able (line 4). If it is, then r is added in R (line 5). Otherwise, r is invalid.
Once the set of valid requirements R is determined, we divide it into non-overlapping satis able subsets S, covering all requirements (lines 9-23). To this end, we start with an empty pool of subsets (line 10). Then, for each requirement r in R, we attempt to accommodate it in an existing subset in the pool (line 14). If such a subset is found, we include r in the subset (line 15). If not, we populate the pool with an initially empty subset and then include r in the newly added subset (line 21). Note that a subset of requirements R0 in this context is speci ed as the logical conjunction of all the requirements included in the set, i.e., Vr02R0 r0. Consequently, to determine whether a new requirement r can be accommodated in an existing subset R0, we solve the respective constraints together with M , i.e., r ^ M ^ Vr02R0 r0 (line 14), if the resulting constraint is satis able then we include r in R0 (line 15).
After determining the subsets S, to compute the U-CIT object O, we generate a test case by solving the logical conjunction M ^ Vr2R0 r for each subset R0 (line 28). The set of test cases are then guaranteed to obtain full coverage under the coverage criterion C.
Not that we provide this algorithm as a proof-of-concept algorithm for computing U-CIT objects. That is, in the development of this algorithm, our major concern was correctness, not performance. Consequently, the proposed algorithm su ers from some drawbacks. One issue is that being a greedy algorithm, it may yield locally optimal solutions. Another issue is that the same constraints may end up being solved repeatedly, which may cause scalability issues. 5
An Example: Specifying and Computing Standard Covering Arrays as U-CIT Ob jects In this section, we illustrate U-CIT on a hypothetical system by providing details about how our running scenario, in which standard covering arrays are used for con guration testing, can be handled by U-CIT. The example is kept as simple as possible on purpose. In general, the complexity of encodings depends on the complexity of the system under test and/or complexity of the application domain.
Without losing the generality of the proposed approach, the system under test we use in our example has three binary con guration options (o1, o2, and o3), each of which takes the setting of true or f alse, together with two inter-option constraints: o2 = true ! o3 = true, invalidating the combination (o2 = true, o3 = f alse), and :(o1 = true ^ o3 = f alse), invalidating the combination (o1 = true, o3 = f alse). Furthermore, the system is to be tested using a 2-way covering array, i.e., all valid 2-tuples must be covered at least once.
For this example, the U-CIT space model M can be expressed in Boolean algebra as (:o2 _ o3) ^ (:o1 _ o3), where each con guration option is represented by a Boolean variable. In this encoding, each U-CIT requirement simply becomes a Boolean formula representing a 2-tuple. For example, the 2-tuple (o1 = f alse, o2 = true) is expressed as (:o1 ^ o2). To determine whether a U-CIT requirement is valid or not, it is checked whether the respective Boolean formula is satis able with the U-CIT space model M . For example, since (:o1 ^ o2) ^ M is (o1; o2) satis able, the 2-tuple (o1 = f alse, o2 = true) is a valid 2-tuple, thus a valid U-CIT requirement. For the same reason, (o2 = true, o3 = f alse) is not a valid U-CIT requirement.
The rst part of Algorithm 1 (lines 2-7), which determines all valid U-CIT requirements, would then generate the 10 U-CIT requirements r1; ; r10 given in Table 1.
S = fR10; R20; R30; R40g
Next, the set of valid requirements is divided into non-overlapping satis able subsets by the second part of Algorithm 2 (lines 10-23). Assuming that the requirements in Table 1 are processed in the order r1; ; r10, the rst requirement we process becomes r1 : (:o1 ^ :o2). Since the set S is initially empty, we create a new subset R10 = fr1g and populate S with R10, i.e., S = fR10g. For the second requirement r2 : (:o1 ^ o2), since r1 ^ r2 ^ M , i.e., (:o1 ^ :o2) ^ (:o1 ^ o2) ^ M , is not satis able, r2 cannot be placed in R10. So, we create a new subset R20 = fr2g and S becomes fR10; R20g. After processing r4, we would have four subsets R10, R20, R30, and R40 in S, containing requirements r1, r2, r3, and r4, respectively. For requirement r5 : (:o1 ^ :o3), as r1 ^ r5 ^ M , i.e., (:o1 ^ :o2) ^ (:o1 ^ :o3) ^ M , is satis able r5 is placed in R10 together with r1. After processing all the requirements, we would have the four subsets of satis able U-CIT requirements given in the left column of Table 2.
Finally, in the last part of Algorithm 1 (lines 26-30), for each subset of U-CIT requirements in S, we generate a U-CIT test case, which in this case corresponds to a valid con guration, by solving the requirements in the subset together with the U-CIT space model M . For example, for R10 (Table 2), solving r1 ^r5 ^r8 ^M produces the con guration (o1 = f alse; o2 = f alse; o3 = f alse). Solving all the subsets would then generate the U-CIT object given in the right column of Table 2, which is indeed a standard 2-way covering array { a set of con gurations that covers each valid 2-tuple at least once. 6
We believe that U-CIT can greatly improve the exibility of combinatorial interaction testing in practice. Therefore, e cient and a ective approaches for solving the constraint satisfaction problem we informally introduced in this paper, are of great practical importance. Therefore, we keep on developing languages and model-based tools for de ning variability spaces and coverage criteria in a generic manner as well as developing e cient and e ective approaches for computing U-CIT objects.