# Design of Prioritized N-Wise Testing

Eun-Hye Choi, Takashi Kitamura, Cyrille Artho, Yutaka Oiwa

► To cite this version:

Eun-Hye Choi, Takashi Kitamura, Cyrille Artho, Yutaka Oiwa. Design of Prioritized N-Wise Testing. 26th IFIP International Conference on Testing Software and Systems (ICTSS), Sep 2014, Madrid, Spain. pp.186-191, 10.1007/978-3-662-44857-1_14 . hal-01405286

HAL Id: hal-01405286

https://inria.hal.science/hal-01405286

Submitted on 29 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# 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 testing

## 1 Introduction

N-wise testing ($N = 1, 2, ...$), e. g., pairwise testing when $N = 2$, is a widely used technique for combinatorial interaction testing. It is based on a coverage criterion called interaction coverage, which stipulates to test all N-tuples of parameter values at least once, given a system under test (SUT) model as sets of parameters, 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 motivated by 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 as code 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 call such 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 case generation, 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><caption>**Table 1.** An example SUT model with value pairs and weights.</caption><thead><tr><th colspan="2">(a) An example SUT model. N=2.</th><th colspan="2">(b) All value pairs and weights.</th></tr><tr><th colspan="2">Parameter: Value (Weight)</th><th colspan="2"></th></tr><tr><th></th><th></th><th>CO</th><th>W</th><th>CB</th><th>W</th><th>CB</th><th>W</th><th>OB</th><th>W</th><th>OB</th><th>W</th></tr></thead><tbody><tr><td>CPU:</td><td>AMD(2), Intel(6)</td><td>AM</td><td>3</td><td>AI</td><td>5</td><td>II</td><td>9</td><td>MI</td><td>4</td><td>US</td><td>4</td></tr><tr><td>OS:</td><td>Mac(1), Ubuntu(1), Win(2)</td><td>AU</td><td>3</td><td>AF</td><td>5</td><td>IF</td><td>9</td><td>MF</td><td>4</td><td>UO</td><td>4</td></tr><tr><td>Browser:</td><td>IE(3), Firefox(3), Chrome(3), Safari(3), Opera(3)</td><td>AW</td><td>4</td><td>AC</td><td>5</td><td>IC</td><td>9</td><td>MC</td><td>4</td><td>WI</td><td>5</td></tr><tr><td></td><td></td><td>IM</td><td>7</td><td>AS</td><td>5</td><td>IS</td><td>9</td><td>MS</td><td>4</td><td>WF</td><td>5</td></tr><tr><td></td><td></td><td>IU</td><td>7</td><td>AO</td><td>5</td><td>IO</td><td>9</td><td>MO</td><td>4</td><td>WC</td><td>5</td></tr><tr><td></td><td></td><td>IW</td><td>8</td><td></td><td></td><td></td><td></td><td>U I</td><td>4</td><td>WS</td><td>5</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>UF</td><td>4</td><td>WO</td><td>5</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>UC</td><td>4</td><td></td><td></td></tr></tbody></table>

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 three parameters: (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 set of value assignments for all parameters. A pairwise (*N*-wise) test suite is a set of 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 for ordering 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 by these 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 the other hand, Bryce's technique [1] aims to obtain test cases with better weight coverage, 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, CTE-XL 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.
<caption>**Algorithm 1 Prioritized N-wise test generation.**</caption>

**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* ≠ *Ø* **do**
4) 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 ratio of values in a test suite. To rigorously consider *CF*, we employ the notion of *KL Divergence* used in [5]. KL divergence, $D_{KL}(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 each value, 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 parameter values 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 (step 4-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 model in 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 that of *AMD*. Furthermore, *Ubuntu* occurs less often than *Mac* despite their weights

<footnote n="1">¹ The symbol `-` can take any value for *Browser* as all values have the same weight.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Comparison of the evaluation metrics.</figcaption></figure>

being the same. Thus, *Intel* and *Ubuntu* are assigned to the 11th test case to achieve 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*) are ordered 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.<fnref n="2" /> Fig. 1 shows the evaluation result on our example in Tab. 1-(a).<fnref n="3" /> The proposed algorithms are superior to the previous methods according to the three metrics. A1 and A2, respectively, provide the

<footnote n="2">² To search locally optimal test cases, our algorithm can incur a high computing cost with a high quality for large models. The cost will be evaluated in our next paper.</footnote>

<footnote n="3">³ See http://staff.aist.go.jp/e.choi/evaluationGraphs.html for larger sized graphs.</footnote>
best results for pairwise coverage and weight coverage, and thus we can obtain
a high coverage of higher-priority test cases even when only a small number of
test 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 high-priority test cases appear early and frequently. Our early evaluation has shown that the technique can outperform the state-of-the-art techniques on all the three 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, in case our technique is not scalable for practical sized SUT models. Future work also includes handling weights attached to both of parameters and values, and to structured SUT models [4].

**Acknowledgements.** The authors would like to thank Goro Hatayama and Tatsuhiro 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 coverage with seeding and constraints. *Information & Software Technology*, 48(10):960–970, 2006.

2. R. Bryce, S. Sampath, J. Pedersen, and S. Manchester. Test suite prioritization by cost-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 case generators. *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.