Today’s AgendaQuick ReviewCombinatorial TestingMotivationCombinatorial ExplosionExample - sortCombinatorial DesignFault ModelExample – Pairwise FaultExample – 3-way FaultSlide 11All Combinations CoverageEach Choice CoveragePairwise CoverageT-Wise CoverageBase Choice CoverageMultiple Base Choices CoverageSubsumption RelationSlide 19Why Pairwise?Example (1)Example (2)The IPO StrategyAlgorithm IPO_H (T, pi)Algorithm IPO_V(T, )Example RevisitedSlide 27SummaryToday’s AgendaHW #1 DueQuick ReviewFinish Input Space PartitioningCombinatorial TestingSoftware Testing and Maintenance 1Quick ReviewWhat is equivalence partitioning? What are the two major approaches to equivalence partitioning?Software Testing and Maintenance 2Software Testing and Maintenance 3Combinatorial Testing Introduction Combinatorial Coverage Criteria Pairwise Test Generation SummarySoftware Testing and Maintenance 4Motivation The behavior of a software application may be affected by many factors, e.g., input parameters, environment configurations, and state variables. Techniques like equivalence partitioning and boundary-value analysis can be used to identify the possible values of each factor. It is impractical to test all possible combinations of values of all those factors. (Why?)Software Testing and Maintenance 5Combinatorial Explosion Assume that an application has 10 parameters, each of which can take 5 values. How many possible combinations?Software Testing and Maintenance 6Example - sort> man sortReformatting page. Wait... doneUser Commands sort(1)NAME sort - sort, merge, or sequence check text filesSYNOPSIS /usr/bin/sort [ -cmu ] [ -o output ] [ -T directory ] [ -y [ kmem ]] [ -z recsz ] [ -dfiMnr ] [ -b ] [ -t char ] [ -k keydef ] [ +pos1 [ -pos2 ]] [ file...] …Software Testing and Maintenance 7Combinatorial Design Instead of testing all possible combinations, a subset of combinations is generated to satisfy some well-defined combination strategies. A key observation is that not every factor contributes to every fault, and it is often the case that a fault is caused by interactions among a few factors. Combinatorial design can dramatically reduce the number of combinations to be covered but remains very effective in terms of fault detection.Software Testing and Maintenance 8Fault Model A t-way interaction fault is a fault that is triggered by a certain combination of t input values. A simple fault is a t-way fault where t = 1; a pairwise fault is a t-way fault where t = 2. In practice, the majority of faults in a software applications consist of simple and pairwise faults.Software Testing and Maintenance 9Example – Pairwise Faultbegin int x, y, z; input (x, y, z); if (x == x1 and y == y2) output (f(x, y, z)); else if (x == x2 and y == y1) output (g(x, y)); else output (f(x, y, z) + g(x, y))endExpected: x = x1 and y = y1 => f(x, y, z) – g(x, y); x = x2, y = y2 => f(x, y, z) + g(x, y)Software Testing and Maintenance 10Example – 3-way Faultbegin int x, y, z, p; input (x, y, z); p = (x + y) * z // should be p = (x – y) * z if (p >= 0) output (f(x, y, z)); else output (g(x, y));endSoftware Testing and Maintenance 11Combinatorial Testing Introduction Combination Strategies Criteria Pairwise Test Generation SummarySoftware Testing and Maintenance 12All Combinations Coverage Every possible combination of values of the parameters must be covered For example, if we have three parameters P1 = (A, B), P2 = (1, 2, 3), and P3 = (x, y), then all combinations coverage requires 12 tests: {(A, 1, x), (A, 1, y), (A, 2, x), (A, 2, y), (A, 3, x), (A, 3, y), (B, 1, x), (B, 1, y), (B, 2, x), (B, 2, y), (B, 3, x), (B, 3, y)}Software Testing and Maintenance 13Each Choice Coverage Each parameter value must be covered in at least one test case. Consider the previous example, a test set that satisfies each choice coverage is the following: {(A, 1, x), (B, 2, y), (A, 3, x)}Software Testing and Maintenance 14Pairwise Coverage Given any two parameters, every combination of values of these two parameters are covered in at least one test case. A pairwise test set of the previous example is the following:P1P2 P3A1 xA2 xA3 xA- yB1 yB2 yB3 yB- xSoftware Testing and Maintenance 15T-Wise Coverage Given any t parameters, every combination of values of these t parameters must be covered in at least one test case. For example, a 3-wise coverage requires every triple be covered in at least one test case. Note that all combinations, each choice, and pairwise coverage can be considered to be a special case of t-wise coverage.Software Testing and Maintenance 16Base Choice Coverage For each parameter, one of the possible values is designated as a base choice of the parameter A base test is formed by using the base choice for each parameter Subsequent tests are chosen by holding all base choices constant, except for one, which is replaced using a non-base choice of the corresponding parameter:P1P2 P3A1 xB1 xA2 xA3 xA1 ySoftware Testing and Maintenance 17Multiple Base Choices Coverage At least one, and possibly more, base choices are designated for each parameter. The notions of a base test and subsequent tests are defined in the same as Base Choice.Software Testing and Maintenance 18Subsumption RelationAll CombinationsT-WisePairwiseMultiple Base ChoicesBase ChoiceEach ChoiceSoftware Testing and Maintenance 19Combinatorial Testing Introduction Combination Strategies Criteria Pairwise Test Generation SummarySoftware Testing and Maintenance 20Why Pairwise? Many faults are caused by the interactions between two parameters Not practical to cover all the parameter interactionsSoftware Testing and Maintenance 21Example (1)Consider a system with the following parameters and values: parameter A has values A1 and A2 parameter B has values B1 and B2, and parameter C has values C1, C2, and C3Software Testing and Maintenance 22Example (2)A B CA1 B1 C1A1 B2 C2A2 B1 C3A2 B2 C1A2 B1 C2A1 B2 C3A B CA1 B1 C1A1 B2 C1A2 B1 C2A2 B2 C3A2 B1 C1A1 B2 C2A1 B1 C3A B CA1 B1 C1A1 B2 C1A2 B1 C2A2 B2 C2A2 B1 C1A1 B1 C2A1 B1 C3A2 B2 C3Software Testing and Maintenance 23The IPO Strategy First generate a pairwise test set for the first two parameters, then for the first three parameters, and so on A pairwise test set for the first n parameters is built by extending the