Design of Prioritized N -Wise Testing
Eun-Hye Choi, Takashi Kitamura, Cyrille Artho, and Yutaka Oiwa
Nat. Inst. of Advanced Industrial Science and Technology, Amagasaki, Japan{e.choi, t.kitamura, c.artho, y.oiwa}@aist.go.jp

Abstract. N -wise testing is a widely used technique for combinatorial interaction testing. Prioritizing testing reorders test cases by relevance, testing important aspects more thoroughly. We propose a novel
technique for N -wise test case generation to satisfy the three distinct
prioritization criteria of interaction coverage, weight coverage, and KL
divergence. The proposed technique generates small N -wise test cases,
where high-priority test cases appear early and frequently. Our early
evaluation confirms that the proposed technique improves on existing
techniques based on the three prioritization criteria.

Keywords: Combinatorial testing, N -wise testing, prioritized testing1

Introduction

N -wise testing (N = 1, 2, ...), e. g., pairwise testing when N = 2, is a widelyused technique for combinatorial interaction testing. It is based on a coverage
criterion called interaction coverage, which stipulates to test all N -tuples ofparameter values at least once, given a system under test (SUT) model as sets ofparameters, parameter values, and constraints to express parameter interactions.
Recently, techniques for prioritized N-wise testing, which covers prioritized
test aspects earlier and more thoroughly, have been proposed. This is motivatedby practical demand, as resources for testing are often limited in real-world
software development. Previous work on prioritized N -wise testing mainly falls
into two categories: (1) reordering of test cases based on coverage criteria such ascode coverage [2, 8], and (2) generating prioritized test cases given SUT models
with user-defined priorities assigned to parameters or values [1, 3, 5, 6]. (We callsuch models weighted SUT models.)
In this paper, we propose a novel approach to prioritizing N -wise testing,along the line of category (2). Our technique for prioritized N -wise test casegeneration, given weighted SUT models, satisfies the following criteria:– CO: Higher-priority test cases should appear earlier.
– CF: Higher-priority parameter values should appear more frequently.
– CS: The number of test cases should be as small as possible.
Our proposed technique provides a strategy to achieve a good balance between
the three criteria. By considering CO, CF, and CS together, our strategy obtains
important test cases early and frequently in a small test suite.

Table 1. An example SUT model with value pairs and weights.
(a) An example SUT model. N =2.
Parameter : Value(Weight)
CPU:
OS:
Browser:AMD(2), Intel(6)Mac(1), Ubuntu(1), Win(2)IE(3), Firefox(3), Chrome(3),Safari(3), Opera(3)(b) All value pairs and weights.
CO W
AM 3
AU 3
AW 4
IM 7
IU 7
IW 8

CB W CB W
AI 5 I I 9
AF 5 I F 9
AC 5 I C 9
AS 5 I S 9
AO 5 I O 9

OB W
MI 4
MF 4
MC 4
MS 4
MO 4
UI 4
UF 4
UC 4

OB W
US 4
UO 4
WI 5
WF 5
WC 5
WS 5
WO 5

The next section describes the state-of-the-art techniques for prioritized N wise test case generation. It shows that existing techniques only consider some of
the criteria. In Section 3, we explain the proposed technique in detail, together
with a comparison of our technique with the state-of-the-art techniques using
sample data. The last section concludes this paper and proposes future work.

2

Related Work

Our running example, the weighted SUT model shown in Tab. 1-(a), has threeparameters: (OS, CPU, Browser). Each parameter has two, three, and five values, respectively. Weights are assigned to values, as specified in parentheses, e. g.,value Win has weight 2. (For brevity, we do not consider constraints; N -wise
constraints can be managed in the initial enumeration phase of our algorithm.)
The weight of a value pair is the sum of the weights of its values. Tab. 1-(b)shows all the value pairs and their weights, W , in the model. A test case is a setof value assignments for all parameters. A pairwise (N -wise) test suite is a setof test cases that covers all pairs (N -tuples) of values in the model.
For prioritized N -wise test generation given a weighted SUT model, several techniques have been proposed [1, 3, 5, 6]. Some techniques use priority forordering test cases [1, 6], while others use it for balancing the occurrences (frequency) of test cases [3, 5, 7]. Tab. 2(c)−(f) show the test suites generated bythese techniques. They all generate test cases one at a time, until all value pairs
are covered. We briefly introduce the difference among these methods here. Prioritization criteria are considered when selecting a new test case as follows.
Order-focused prioritization: CTE-XL [6] aims to obtain test cases ordered
by weight. It focuses on the weight of values assigned to a new test case. On theother hand, Bryce’s technique [1] aims to obtain test cases with better weightcoverage, as defined in Fig. 1. To this aim, it provides an approximate algorithm
to maximize the weight of newly-covered pairs in a new test case.
Both techniques share the advantage that important test cases appear at an
earlier stage of a test suite, satisfying criterion CO. The disadvantage is that they
do not consider the frequency aspect (CF) at all (see Tab. 2). Furthermore, CTEXL generates a test suite that is larger than necessary for interaction coverage;
this is because it focuses on ordering test cases, rather than improving interaction
coverage. Actually, the size of CTE-XL’s test suite (18 test cases) is larger than
Bryce’s (15 test cases), which suffices for satisfying pairwise coverage.

Table 2. Generated test suites by the proposed and previous methods.
(a) A1. (CS>CO>CF)(b) A2. (CO>CS>CF)(c) Bryce’s.

COB
1 IWI
2 I MF
3 I UC
4 AWF
5 AU S
6 AM I
7 I WS
8 I WO
9 AWC
10 AMO
11 I U I
12 I M C
13 I U F
14 I M S
15 I U O

COB
1 IWI
2 I MF
3 I UC
4 AWF
5 I WS
6 I WO
7 AM I
8 AU S
9 AWC
10 AMO
11 I U I
12 I M C
13 I U F
14 I M S
15 I U O

COB
1 IWI
2 I MF
3 AWC
4 I WS
5 I WO
6 I UC
7 AWF
8 AM I
9 AU S
10 AMO
11 A U I
12 A U F
13 AM C
14 AM S
15 A U O

n w
3 22
3 20
3 20
3 14
3 12
3 12
2 14
2 14
2 10
2 9
1 4
1 4
1 4
1 4
1 4

p-cov w-cov
D
0.097 0.132 2.590
0.194 0.251 1.551
0.290 0.371 0.855
0.387 0.455 0.570
0.484 0.527 0.385
0.581 0.599 0.480
0.645 0.683 0.194
0.710 0.766 0.088
0.774 0.826 0.124
0.839 0.880 0.154
0.871 0.904 0.117
0.903 0.928 0.107
0.935 0.952 0.089
0.968 0.976 0.085
1
1
0.074

(d) CTE XL.
COB
1 IWI
2 I MF
3 AW I
4 AM F
5 AUC
6 AM S
7 AMO
8 I UC
9 I US
10 I U O
11 AM I
12 AM C
13 A U I
14 A U F
15 AWF
16 AWC
17 AW S
18 AWO

n w
3 22
3 20
2 9
2 8
3 12
2 9
2 9
2 16
2 13
2 13
1 4
1 4
1 4
1 4
1 5
1 5
1 5
1 5

n w
3 22
3 20
3 20
3 14
2 14
2 14
3 12
3 12
2 10
2 9
1 4
1 4
1 4
1 4
1 4

p-cov w-cov
D
0.097 0.132 2.590
0.194 0.251 1.551
0.290 0.371 0.855
0.387 0.455 0.570
0.452 0.539 0.304
0.516 0.623 0.126
0.613 0.695 0.097
0.710 0.766 0.088
0.774 0.826 0.124
0.839 0.880 0.154
0.871 0.904 0.117
0.903 0.928 0.107
0.935 0.952 0.089
0.968 0.976 0.085
1
1
0.074

(e) PictMaster.
p-cov w-cov
D
0.097 0.132 2.590
0.194 0.251 1.551
0.258 0.305 1.278
0.333 0.353 1.407
0.419 0.425 0.882
0.484 0.479 0.807
0.548 0.533 0.766
0.613 0.629 0.536
0.677 0.707 0.411
0.742 0.784 0.337
0.774 0.808 0.437
0.806 0.832 0.529
0.839 0.856 0.609
0.871 0.880 0.661
0.903 0.910 0.622
0.935 0.940 0.603
0.968 0.970 0.575
1
1
0.556

n: Number of new value pairs
w: Weight of new value pairs
p-cov : Pairwise coverage
w-cov : Weight coverage
D: KL DivergenceCOB
1 I WF
2 I WC
3 I UC
4 I WS
5 I MC
6 I MO
7 I US
8 I UF
9 AWC
10 AW S
11 I M I
12 I M S
13 A U F
14 I WO
15 I U O
16 I W I
17 A U I
18 I M F
19 AM F
20 AW I
21 AM C
22 I U I
23 AM S
24 AWO
25 A U C
26 AWF
27 AM I
28 AMO

n w
3 22
2 14
2 11
2 14
2 11
2 13
1 4
1 4
2 9
1 5
2 13
1 4
2 8
1 5
1 4
1 5
2 9
1 4
1 3
0 0
0 0
0 0
0 0
1 5
0 0
0 0
0 0
0 0

n w
3 22
3 20
3 14
2 14
2 14
3 20
2 10
3 12
3 12
2 9
1 4
1 4
1 4
1 4
1 4

p-cov w-cov
D
0.097 0.132 2.590
0.194 0.251 1.551
0.290 0.335 0.816
0.355 0.419 0.527
0.419 0.503 0.338
0.516 0.623 0.126
0.581 0.683 0.158
0.677 0.754 0.141
0.774 0.826 0.124
0.839 0.880 0.154
0.871 0.904 0.217
0.903 0.928 0.290
0.935 0.952 0.343
0.968 0.976 0.399
1
1
0.440

(f) PICT+Fujimoto’s.
p-cov w-cov
D
0.097 0.132 2.590
0.161 0.216 1.897
0.226 0.281 1.548
0.290 0.365 1.161
0.355 0.431 0.967
0.419 0.509 0.683
0.452 0.533 0.630
0.484 0.557 0.620
0.548 0.611 0.415
0.581 0.641 0.347
0.645 0.719 0.159
0.677 0.743 0.204
0.742 0.790 0.179
0.774 0.820 0.111
0.806 0.844 0.111
0.839 0.874 0.051
0.903 0.928 0.038
0.935 0.952 0.039
0.968 0.970 0.055
0.968 0.970 0.039
0.968 0.970 0.064
0.968 0.970 0.067
0.968 0.970 0.089
1
1
0.075
1
1
0.102
1
1
0.109
1
1
0.136
1
1
0.156

COB
1 AWC
2 AM I
3 I MF
4 IWI
5 I U I
6 I MC
7 AUC
8 AUO
9 I WO
10 I MO
11 A U F
12 AWF
13 A U S
14 I W S
15 AM S
16 I W I
17 I WF
18 I WC
19 I W S
20 I WO
21 I M I
22 I U F
23 I WC
24 I W S
25 I MO
26 I U I
27 I WF
28 I WC

n w
3 14
3 12
3 20
3 22
2 11
2 13
2 7
2 9
2 14
1 4
2 9
1 5
2 9
2 14
1 4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

p-cov w-cov
D
0.097 0.084 3.689
0.194 0.156 2.649
0.290 0.275 1.413
0.387 0.407 1.060
0.452 0.473 0.767
0.516 0.551 0.759
0.581 0.593 0.790
0.645 0.647 0.629
0.710 0.731 0.444
0.742 0.754 0.439
0.806 0.808 0.442
0.839 0.838 0.424
0.903 0.892 0.328
0.968 0.976 0.200
1
1
0.239
1
1
0.183
1
1
0.139
1
1
0.105
1
1
0.077
1
1
0.054
1
1
0.049
1
1
0.042
1
1
0.030
1
1
0.021
1
1
0.015
1
1
0.014
1
1
0.010
1
1
0.007

Frequency-focused prioritization: PICT [3], PictMaster [7], and Fujimoto’s
method [5] obtain higher-priority values more frequently; in our example, forparameter OS, value Win with weight 2 should appear twice as frequently as
values Mac and Ubuntu with weight 1. In PICT, given weights are considered
only if two value choices are identical, and thus the frequency is reflected only approximately. To improve this, PictMaster constructs a test suite to redundantly
cover pairs according to their weights, and thus the size is unnecessary large asshown in Tab. 2-(e). On the other hand, Fujimoto developed a method to add
test cases to an existing test suite that more accurately reflect given weights forvalue frequency. The test suite generated by Fujimoto’s method in Tab. 2 showsthat Win appears 14 times, twice as frequently as Mac (7 times), but the test
suites by PICT and PictMaster contains the same numbers of Win and Mac.
In the example, PictMaster generates 28 test cases, while Fujimoto’s method
uses 15 test cases by PICT plus 13 optional test cases (to more accurately reflect
given weights for value frequency); see Tab. 2-(e),(f). The strength of theseapproaches is that more important values appear more frequently; however, theorder of important test cases is completely disregarded.

Algorithm 1 Prioritized N -wise test generation.
Input: A weighted SUT model, Combinatorial strength N .
Output: A N -wise test suite.
1) For each parameter, order all parameter values by weight.
2) Enumerate all N -tuples of parameter values and their weights.
3) Set a set of uncovered combinations, UC , as the set of all the value N -tuples.
while UC 6= ∅ do4) List test case candidates to cover the max. number of combinations in UC . [CS]4-1) If there is one candidate, choose it as t.
4-2) If there are several candidates, list candidates with the max. weight of new combinations. [CO]4-2-1) If there is one candidate, choose it as t.
4-2-2) If there are several candidates, choose any candidate with min. KL divergence as t. [CF]5) Set t as the next test case and add it to the test suite.
6) Remove the value N -tuples covered by t from UC .
end while

3

Proposed approach to prioritized test generation

We propose a novel approach to prioritized N -wise test generation, which integrates the three prioritization criteria of order, CO, frequency, CF, and size, CS.
For CS, we select a new test case to cover as many uncovered value N -tuples as
possible. For CO, we select a new test case to cover value N -tuples with the highest weight. For CF, a new test case is selected according to the occurrence ratioof values in a test suite. To rigorously consider CF, we employ the notion of KL
Divergence used in [5]. KL divergence, DKL (P ||Q) defined in Fig. 1, expresses
the distance between the current value occurrence distribution, P , and an ideal
distribution, Q, according to given weights. In the ideal distribution, for eachvalue, the number of occurrences is proportional to its weight. By integrating
the three criteria CO, CF, and CS, our approach obtains small test suites where
high-priority test cases appear early and frequently.
Algorithm 1 shows the pseudo code of the algorithm with priority order
CS>CO>CF. Given a weighted SUT model, the algorithm generates test cases
one by one until all N -tuples of parameter values are covered. For a new test
case, we choose the best one w. r. t. CS, i. e., the test case that covers the most
new N -tuples of parameter values (step 4). If there are several candidates, choose
the best one for CO, i. e., the test case that covers the new N -tuples of parametervalues with the highest weight (step 4-2). If there are still several candidates,choose the best one for CF; i. e., the test case with min. KL divergence (step4-2-2) to ensure that the value frequency distribution is closest to the ideal state.
Tab. 2-(a) shows the pairwise test suite generated from the example modelin Tab. 1-(a), by Algorithm 1 (A1). For the first test case, all the test cases
in which the number of newly-covered value pairs (n) is 3 become candidates,
since this is the max. number at this stage. Among them, (Intel, Win, −1 ) is
selected as it has the max. value of w, 22. For the 11th test case, test cases 11–15
have the same n and w. In the first ten test cases, AMD and Intel are assigned
equally often to parameter CPU, even though the weight of Intel is twice of thatof AMD. Furthermore, Ubuntu occurs less often than Mac despite their weights
1

The symbol − can take any value for Browser as all values have the same weight.

1.0

1.0

0.9

0.9

0.8

0.8

0.7

0.7

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1
0.0
0

0.1
2

4

6

8

10 12 14 16 18 20 22 24 26 28

0

2

4

6

8

10 12 14 16 18 20 22 24 26 28

3.6
3.2

Pairwise coverage
Number of covered value pairs=
Number of all value pairs

2.8
2.4

Weight coverage
Sum of weights of covered value pairs=
Sum of weights of all value pairs

2.0
1.6
1.2

KL Divergence P
DKL (P ||Q) =P (i)log(P (i)/Q(i))

0.8

i

0.4
0.0
0

2

4

6

8

10

12

14

16

18

20

22

24

26

28

Fig. 1. Comparison of the evaluation metrics.

being the same. Thus, Intel and Ubuntu are assigned to the 11th test case toachieve a better KL divergence.
We can construct variants of the algorithm with different orders of prioritization criteria CO, CF, and CS, by swapping the conditions in steps 4, 4-2,
and 4-2-2 in Algorithm 1. For example, we can construct another algorithm A2
with CO>CS>CF. Tab. 2-(b) shows the pairwise test suite generated by A2.
Note that test cases by A1 (resp., A2) are ordered by n (w), since CO (CW)
is the first priority criterion. Test cases with the same value of n (resp., w) areordered by w (n) for A1 (A2), since CW (CO) is the second priority criterion.
Furthermore, the test suites generated by A1 and A2 require only 15 test cases,
which is fewer than those computed by most previous methods.
We compared our method with the previous methods from the three metrics
of interaction coverage, weight coverage, and KL divergence, using several examples of weighted SUT models. As a result, we confirmed that our proposed
method can improve on all the metrics.2 Fig. 1 shows the evaluation result on
our example in Tab. 1-(a).3 The proposed algorithms are superior to the previous
methods according to the three metrics. A1 and A2, respectively, provide the2

To search locally optimal test cases, our algorithm can incur a high computing costwith a high quality for large models. The cost will be evaluated in our next paper.
3
See http://staff.aist.go.jp/e.choi/evaluationGraphs.html for larger sized graphs.

best results for pairwise coverage and weight coverage, and thus we can obtaina high coverage of higher-priority test cases even when only a small number oftest cases is selected. When considering KL divergence, A2 (resp., A1) provides
the best result when the number of test cases is higher than 4 (7). Our method
provides a good balance of value occurrences, even in a small test suite.

4

Conclusion and Future Work

We have proposed a novel technique for prioritized N -wise test generation, which
integrates the three prioritization criteria of order, CO, frequency, CF, and size,
CS. Our technique is designed to generate small N -wise test suites, where highpriority test cases appear early and frequently. Our early evaluation has shownthat the technique can outperform the state-of-the-art techniques on all thethree metrics. The technique is currently under implementation, and will be
evaluated including computing cost on practical-sized SUT models. We are also
considering to develop approximate algorithms with a lower computing cost, incase our technique is not scalable for practical sized SUT models. Future work
also includes handling weights attached to both of parameters and values, andto structured SUT models [4].
Acknowledgements. The authors would like to thank Goro Hatayama andTatsuhiro Tsuchiya for their helpful comments. This work is supported by JST
ASTEP grant (No. AS2524001H).

References
1. R. Bryce and C. Colbourn. Prioritized interaction testing for pair-wise coveragewith seeding and constraints. Information & Software Technology, 48(10):960–970,
2006.
2. R. Bryce, S. Sampath, J. Pedersen, and S. Manchester. Test suite prioritization bycost-based combinatorial interaction coverage. Int. J. Systems Assurance Engineering and Management, 2(2):126–134, 2011.
3. J. Czerwonka. Pairwise testing in the real world: Practical extensions to test casegenerators. Microsoft Corporation, Software Testing Technical Articles, 2008.
4. N. Do, T. Kitamura, N. Tang, G. Hatayama, S. Sakuragi, and H. Ohsaki. Constructing test cases for N-wise testing from tree-based test models. In Proc. of SoICT
2013. ACM ICPS, 2013.
5. S. Fujimoto, H. Kojima, and T. Tsuchiya. A value weighting method for pair-wise
testing. In Proc. of APSEC 2013, pages 99–105, 2013.
6. P. Kruse and M. Luniak. Automated test case generation using classification trees.
Software Quality Professional, pages 4–12, 2010.
7. PictMaster. http://sourceforge.jp/projects/pictmaster/.
8. Q. Xiao, M. Cohen, and K. Woolf. Combinatorial interaction regression testing: A
study of test case generation and prioritization. In Proc. ICSM’07, pages 255–264.
IEEE, 2007.