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

HAL
open science

# A Comparative Study on Combinatorial and Random Testing for Highly Configurable Systems

Hao Jin, Takashi Kitamura, Eun-Hye Choi, Tatsuhiro Tsuchiya

► To cite this version:

Hao Jin, Takashi Kitamura, Eun-Hye Choi, Tatsuhiro Tsuchiya. A Comparative Study on Combinatorial and Random Testing for Highly Configurable Systems. 32nd IFIP International Conference on Testing Software and Systems (ICTSS), Dec 2020, Naples, Italy. pp.302-309, 10.1007/978-3-030-64881-7_20. hal-03239827

HAL Id: hal-03239827

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

Submitted on 27 May 2021

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Comparative Study on Combinatorial and Random Testing for Highly Configurable Systems

Hao Jin<fnref n="1" />[0000-0003-1392-0327], Takashi Kitamura<fnref n="2" />[0000-0002-8903-3161], Eun-Hye Choi<fnref n="2" />[0000-0001-9339-8107], and Tatsuhiro Tsuchiya<fnref n="1" />[0000-0002-3329-9235]

**Abstract.** Highly configurable systems (HCSs), such as software product lines, have complex configuration spaces. Combinatorial Testing and Random Testing are the main approaches to testing of HCSs. In this paper, we empirically compare their strengths with respect to scalability and diversity of sampled configurations (i.e., tests). We choose ICPLand QUICKSAMPLERto respectively represent Combinatorial Testing and Random Testing. Experiments are processed to evaluate the *t*-way coverage criterion of generated test suites for HCS benchmarks.

**Keywords:** combinatorial testing · random testing · software product line

## 1 Introduction

*Highly configurable systems (HCSs)*, such as software product lines (SPLs), have complex configuration spaces. The configuration spaces are often determined by *features* and *constraints*, which are modeled in some logical formalism over features, such as *feature models*. Figure 1 shows a simple feature model which describes the configuration space of Eclipse IDE [9]. A *configuration* (or a *test*) specifies which features are *de-/selected* in a given feature model. Table 1 shows a set of configurations of the feature model of Figure 1.

*Configuration testing* validates if systems run correctly at various configurations. However, testing all configurations in a given configuration space exhaustively is infeasible for any non-trivial HCS, since the number of configurations increases exponentially with the number of features (or parameters). Techniques to effectively sample configurations are needed to effectively test HCSs.

*Combinatorial Testing (CT)* [11] and *Random Testing (RT)* are main approaches to effective configuration sampling for testing of HCSs. Given a HCS and *strength t*, which is a small positive integer such as 2 or 3, CT requires all possible feature interactions of size *t* are tested by at least one test in a test suite. This condition is called the *t-way coverage criterion*. Note that the integer *t* is user-defined. The effectiveness of CT has been demonstrated empirically (e. g., [10,11]). Sampling algorithms for CT test suites (CT algorithms for short) are a central subject in the CT research. The 12 configurations in Table 1 meets the 2-way coverage criterion. We call such a set of test cases a *t*-way test suite.

<footnote n="1">¹ Osaka University, Suita, Japan {k-kou,t-tutiya}@ist.osaka-u.ac.jp</footnote>

<footnote n="2">² AIST, Ikeda, Japan {t.kitamura,e.choi}@aist.go.jp</footnote>
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** A feature model of Eclipse IDE (using the notation of [9])</figcaption></figure>

<table><caption>**Table 1.** Twelve configurations, sampled from Eclipse IDE feature model in Figure 1. Each column represents a configuration, where ‘X’ and ‘-’ respectively mean selected and de-selected features of corresponding features in the rows.</caption><thead><tr><th>Feature \ Configurations</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th></tr></thead><tbody><tr><td>EclipseIDE</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td></tr><tr><td>Team</td><td>X</td><td>X</td><td>-</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>-</td><td>X</td></tr><tr><td>CVS</td><td>X</td><td>X</td><td>-</td><td>X</td><td>X</td><td>-</td><td>X</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td></tr><tr><td>CVS_Over_SSH</td><td>-</td><td>-</td><td>-</td><td>X</td><td>X</td><td>-</td><td>X</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td></tr><tr><td>CVS_Over_SSH2</td><td>-</td><td>-</td><td>-</td><td>X</td><td>X</td><td>-</td><td>X</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td></tr><tr><td>SVN</td><td>X</td><td>X</td><td>-</td><td>X</td><td>X</td><td>X</td><td>-</td><td>X</td><td>X</td><td>X</td><td>-</td><td>-</td></tr><tr><td>Subversive</td><td>X</td><td>-</td><td>-</td><td>X</td><td>-</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Subclipse</td><td>-</td><td>X</td><td>-</td><td>-</td><td>X</td><td>X</td><td>-</td><td>-</td><td>X</td><td>X</td><td>-</td><td>-</td></tr><tr><td>Subclipse_1.4.x</td><td>-</td><td>X</td><td>-</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Subclipse_1.6.x</td><td>-</td><td>-</td><td>-</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td><td>X</td><td>-</td><td>-</td><td>-</td></tr><tr><td>GIT</td><td>X</td><td>-</td><td>-</td><td>-</td><td>X</td><td>X</td><td>-</td><td>-</td><td>-</td><td>-</td><td>X</td><td>X</td></tr><tr><td>EclipseFileSystem</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td></tr><tr><td>Local</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td></tr><tr><td>Zip</td><td>-</td><td>X</td><td>X</td><td>-</td><td>-</td><td>-</td><td>X</td><td>X</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

RT for HCSs is addressed by, for example, Hirasaki et al. [8]. They developed an algorithm to randomly sample configurations from a test space specified by a logical formula. Solution sampling techniques have been actively investigated in the field of constraint solving (instead of testing), yielding several algorithms using such as SAT solvers [4,2] or Binary Decision Diagrams (BDDs) [15]. Although such sampling techniques are not originally developed for software testing, we can use them as configuration sampling algorithms because configuration spaces can be represented as Boolean formulas.

In this paper, we compare CT and RT in testing of large and complex HCSs, focusing on the following RQs:

**RQ1** How scalable are CT and RT sampling techniques?

**RQ2** How diverse are sampled configurations by RT in terms of *t*-way coverage criteria?

It is generally perceived that CT sampling is less scalable than RT sampling, since it spends computation resources to maximize *t*-way coverage criteria. With RQ1, we investigate scalability limits of the both approaches in the setting of HCSs in comparison. RQ2 is posed to evaluate the two approaches with respect to the quality of sampled configurations. Based on the definition of *t*-way coverage criterion, a test suite with smaller size that meets the *t*-way coverage criteria has better diversity as different tests in it are tending to test different *t*-way interactions. Hence, we choose *t*-way coverage criteria as the evaluation metric of the test suite diversity.

## 2 Related work

Several studies have compared RT and CT from different perspectives. Arcuri and Briand [1] theoretically analyzed the fault detecting ability of RT in terms of *t*-way coverage, showing that any *t*-way interaction can be detected with a
probability of 63% by an RT test suite whose size is the same as that of a theoretically-optimal CT test suite. Our work can be viewed as an empirical analogue to the theoretical analysis in the context of large HCS testing.

Wu et al. [16] empirically compared CT, RT, and Adaptive Random Test-
ing (ART) [3] for their fault detecting abilities, in different settings concern-
ing the proportion of parameters, constraints recognized by a tester, and fault
rate (degree of injected faults in a system). They concluded, e. g., that the de-
tecting ability of CT is high regardless of different settings and that the three
techniques perform equally when a tester knows little about constraints. Con-
trarily, we are interested in more foundational questions about CT and RT in the
context of HCS testing: e. g., scalability and diversity of sampled configurations.

3 Sampling techniques of CT and RT

A number of CT and RT algorithms have been proposed in the literature. How-
ever, their implementations are rarely publicly available. We thus select one
representative algorithm from each of the two approaches and compare imple-
mentations of the two selected algorithms in our experiments. This section briefly
reviews algorithms of the two approaches and present the selected algorithms.

**3.1 Sampling techniques of CT**

In this paper, we select the ICPL algorithm by Johansen et al. [9] as the repre-
sentative to be compared with an RT algorithm in the next section. We explain
the decision, by reviewing existing CT algorithms from three aspects.

Most of the existing CT algorithms can be characterized according to algo-
rithm paradigms, into the two categories: greedy and global optimization algo-
rithms. The main advantage of greedy algorithms is that they run fast while
maintaining the generated test suites to be reasonably small. Algorithms/tools
such as [19], including ICPL [9], belong to this algorithm paradigm. Global op-
timization algorithms put emphasis on minimizing test suites and use computa-
tionally costly search techniques such as constraint solving [14] or meta-heuristic
search [7,12]. They generally can find smaller test suites than greedy algorithms;
however, they suffer more from scalability. In this work, we do not consider
global optimization algorithms hereafter, because it is already clear that these
algorithms cannot compete with RT algorithms in terms of scalability.

ICPL is especially tailored to handle large and complex HCSs, i. e., HCSs
with thousands of features and hundred thousands of clauses to specify complex
configuration spaces. Some other greedy algorithms employ constraint handling
mechanisms (e. g., [18]). The work [19] elaborates a constraint handling tech-
nique based on *Minimum Invalid Tuples (MITs)*. However, computing MITs is
so costly that it cannot scale to large HCSs. Algorithm by [17] has a refined
constraint handling mechanism using the notion of *un-satisfiability cores* [13];
but its implementation is not publicly available.
## 3.2 Sampling techniques of RT

Random sampling techniques from configuration spaces specified by logical formulas have been studied in the field of constraint solving. Such random sampling techniques can be classified into two types: clausal-SAT-based and BDD-based. Techniques of the former approach, such as QUICKSAMPLER [4], UNIGEN [2], and SEARCHTREESAMPLER (STSAMPLER, for short) [5], take constraints in CNF as input and sample configurations. These techniques all use repetitive calls of SAT solvers to sample configurations but differ at detailed levels. The BDD-based technique by [15] performs sampling by building a BDD from the input logical formula (not necessarily in CNF) and traversing it. The technique by Hirasaki et al. [8] uses BDDs for constraint solving.

We adopt QUICKSAMPLER, a technique with the clausal-SAT-based approach, as the representative of RT sampling techniques. The clausal-SAT-based approach is superior to the BDD-based approach in terms of scalability. Among clausal-SAT-based techniques, QUICKSAMPLER is one of the most recently developed techniques, shown to be competitive with other random sampling techniques such as UNIGEN and STSAMPLER[4] in efficiency and randomness.

# 4 Experiments

In this section, we conduct experiments to investigate the RQs raised in Section 1.

## 4.1 Experiment Settings

Our experiments compare ICPL and QUICKSAMPLER as the representative algorithms of CT and RT generation techniques, using publicly available implementations. As benchmark data we collected models of 11 HCSs from different sources as summarized in Table 2. For the HCS benchmarks, all features have exactly two values (binary domains) and their configuration spaces are specified in CNF, which is the format both of ICPL and QUICKSAMPLER can process.

We measure the computation time (for RQ1), and sizes of generated *t*-way test suites by ICPL for *t* = 2 and *t* = 3 (for RQ2) for the HCS benchmarks. We also let QUICKSAMPLER sample as many configurations as those generated by ICPL to meet the 2-way and 3-way coverage criteria. We measure the computation time of QUICKSAMPLER and the *t*-way coverage of the sampled configurations. We set timeout for sampling to 1 hour and timeout for measuring coverage of sampled configurations to 4 hours. For benchmarks for which ICPL failed to generate test suites within the time limit, we let QUICKSAMPLER sample 1000 and 2000 configurations for 2-way and 3-way coverage, respectively, as a enough large number to confirm its scalability.

All the experiments are conducted on a machine with 3 GHz 8 Core Intel Xeon E5 1680v2 CPU and 64 GB memory, running MacOS Sierra. QUICKSAMPLER can only run on a single thread, while ICPL internally runs on eight threads in the experiments. Both are allowed to use 64 GB memory.

<footnote n="3">³ https://zenodo.org/record/265808#.X08JB9P7RGA</footnote>
<table><caption>**Table 2.** HCS Benchmark information. The columns for `#F`, `#C`, `#Intr. (t=2)`, and `#Intr. (t=3)` respectively show the number of features, of clauses, of 2-way interactions, and of 3-way interactions of features.</caption><thead><tr><th>No.</th><th>HCS</th><th>#F</th><th>#C</th><th>#Intr. (t=2)</th><th>#Intr. (t=3)</th></tr></thead><tbody><tr><td>1</td><td>Arcade Game Maker Pedagogical Product Line [6]</td><td>61</td><td>122</td><td>7,320</td><td>287,920</td></tr><tr><td>2</td><td>Berkeley DB [6]</td><td>78</td><td>151</td><td>12,012</td><td>608,608</td></tr><tr><td>3</td><td>Violet [6]</td><td>101</td><td>203</td><td>20,200</td><td>1,333,200</td></tr><tr><td>4</td><td>toybox <sup>3</sup></td><td>544</td><td>1,020</td><td>590,784</td><td>213,469,952</td></tr><tr><td>5</td><td>axTLS <sup>3</sup></td><td>684</td><td>2,155</td><td>934,344</td><td>424,815,072</td></tr><tr><td>6</td><td>eCos 3.0 i386pc [6]</td><td>1,244</td><td>3,146</td><td>3,092,584</td><td>2,560,659,552</td></tr><tr><td>7</td><td>FreeBSD Kernel [6]</td><td>1,396</td><td>62,183</td><td>3,894,840</td><td>3,619,604,640</td></tr><tr><td>8</td><td>Fiasco <sup>3</sup></td><td>1,638</td><td>5,228</td><td>5,362,812</td><td>5,849,040,288</td></tr><tr><td>9</td><td>uClinux <sup>3</sup></td><td>1,850</td><td>2,468</td><td>6,841,300</td><td>8,428,481,600</td></tr><tr><td>10</td><td>BusyBox <sup>4</sup></td><td>6,796</td><td>17,836</td><td>92,357,640</td><td>418,318,537,440</td></tr><tr><td>11</td><td>X86 Linux Kernel 2.6.28.6 <sup>5</sup></td><td>6,888</td><td>343,944</td><td>94,875,312</td><td>435,540,932,288</td></tr></tbody></table>

<table><caption>**Table 3.** Experimental results. The columns for `time` and `size` in `ICPL (2-way)` respectively show the generation times (in seconds in wall time) and sizes of generated 2-way test suites, where `T.O.` means `ICPL` failed in generation within the time limit. The columns for in `ICPL (3-way)` show the same for 3-way test suites. The columns for `QUICKSAMPLER` show (1) the computation time (`time`) to sample configurations of the specified sizes (`size`), where `T.O.` means measuring coverages does not finish within the time limit, and (2) the coverage scores of the sampled configurations for the 2-way coverage criterion (`cov. (%)`). The columns for `QUICKSAMPLER` show the same items but include columns `t=2 cov. (%)` and `t=3 cov. (%)` for the scores of 2-way and 3-way coverage criteria.</caption><thead><tr><th rowspan="2">No.</th><th colspan="2">ICPL (2-way)</th><th colspan="2">ICPL (3-way)</th><th colspan="3">QUICKSAMPLER</th><th colspan="3">QUICKSAMPLER</th></tr><tr><th>size</th><th>time(s)</th><th>size</th><th>time(s)</th><th>size</th><th>time(s)</th><th>cov. (%)</th><th>size</th><th>time(s)</th><th>t=2 cov.(%)</th><th>t=3 cov.(%)</th></tr></thead><tbody><tr><td>1</td><td>22</td><td>0.33</td><td>75</td><td>7.10</td><td>22</td><td>0.01</td><td>42.33</td><td>75</td><td>0.04</td><td>44.85</td><td>30.80</td></tr><tr><td>2</td><td>26</td><td>0.35</td><td>122</td><td>7.03</td><td>26</td><td>0.02</td><td>35.55</td><td>122</td><td>0.05</td><td>51.42</td><td>37.78</td></tr><tr><td>3</td><td>31</td><td>0.49</td><td>153</td><td>593.03</td><td>31</td><td>0.02</td><td>30.10</td><td>153</td><td>0.05</td><td>32.93</td><td>19.67</td></tr><tr><td>4</td><td>23</td><td>2.89</td><td>T.O.</td><td></td><td>23</td><td>0.09</td><td>61.43</td><td>(2000)</td><td>0.66</td><td>70.39</td><td>T.O.</td></tr><tr><td>5</td><td>25</td><td>7.99</td><td>T.O.</td><td></td><td>25</td><td>0.26</td><td>57.14</td><td>(2000)</td><td>1.04</td><td>59.32</td><td>T.O.</td></tr><tr><td>6</td><td>72</td><td>107.04</td><td>T.O.</td><td></td><td>72</td><td>0.73</td><td>30.71</td><td>(2000)</td><td>3.15</td><td>31.85</td><td>T.O.</td></tr><tr><td>7</td><td>82</td><td>134.73</td><td>T.O.</td><td></td><td>82</td><td>3.20</td><td>28.71</td><td>(2000)</td><td>9.24</td><td>31.79</td><td>T.O.</td></tr><tr><td>8</td><td>155</td><td>124.31</td><td>T.O.</td><td></td><td>155</td><td>1.96</td><td>77.76</td><td>(2000)</td><td>3.37</td><td>80.22</td><td>T.O.</td></tr><tr><td>9</td><td>32</td><td>91.23</td><td>T.O.</td><td></td><td>32</td><td>0.18</td><td>57.49</td><td>(2000)</td><td>1.55</td><td>58.24</td><td>T.O.</td></tr><tr><td>10</td><td></td><td></td><td>T.O.</td><td></td><td>(1000)</td><td>8.92*</td><td>T.O.</td><td>(2000)</td><td>13.25*</td><td>T.O.</td><td>T.O.</td></tr><tr><td>11</td><td></td><td></td><td>T.O.</td><td></td><td>(1000)</td><td>47.83*</td><td>T.O.</td><td>(2000)</td><td>78.24*</td><td>T.O.</td><td>T.O.</td></tr><tr><td>avg.</td><td></td><td></td><td></td><td></td><td></td><td></td><td>46.80</td><td></td><td></td><td>51.22</td><td>29.41</td></tr></tbody></table>

## 4.2 Experimental results, and answers for RQs

Table 3 shows the experimental results, based on which we answer the RQs.

**Answer to RQ1: “How scalable are CT and RT sampling techniques?”**

Observing Table 3, we can conclude the answer as follows: `ICPL` can scale for 2-way test suites for HCSs to up to 1850 features, and for 3-way test suites to up to 101 features. Considering also Table 2, several billions of interactions may be scalability limit of CT in our computing environment. On the other hand, `QUICKSAMPLER` can sample (even 2000 configurations) for all the HCSs including those with 6888 features and hundred thousands clauses.

<footnote n="4">⁴ http://www.busybox.net/</footnote>

<footnote n="5">⁵ https://www.kernel.org</footnote>
**Answer to RQ2: "How diverse are sampled configurations by RT in terms of t-way coverage criteria?"** Table 3 shows that when the number of sampled configurations is equal to the 2-way and 3-way test suites generated by ICPL, QUICKSAMPLER achieves only 46.8% and 29.4% for 2-way and 3-way coverage respectively. We thus conclude that the diversity of configurations sampled by CT is 2 to 3 times higher than those sampled by RT. It is also interesting to see the following: (1) Even sampled configurations are as many as the 3-way test suite generated by ICPL, QUICKSAMPLER achieves only 51.22% with respect to 2-way coverage. (2) The measured t-way coverages of RT test suites are much less than the theoretical bound (63%) provided by [1]; this can be explained by that the theoretical analysis assumes unconstrained configuration spaces, though.

# 5 Threats to Validity

A possible threat to the validity of this comparative study is the representative-ness of the HCS benchmarks used in the experiments. In the HCS models, all features are modeled as binary values. Coverage results might be qualitatively different, when features are modeled with more than two values. Such models can be handled by many CT algorithms such as [17,18]. It is, however, worth noting that recent CT algorithms, including ICPL, are optimized to deal with binary features for acceleration [9,19]. To reflect such recent advances of CT algorithms, our experiments focused on HCSs with binary features.

The validity may be also threatened by the selection for representative algorithms of CT and RT, i. e., ICPL and QUICKSAMPLER. Although we have explained rationale of the selection, experiments using different algorithms may show different results. This paper reports the first step toward comparison of CT and RT in the setting of HCSs, and thus we plan to extend the study to include other algorithms from both CT and RT in experiments in our future work.

# 6 Conclusion and Future Work

Sampling techniques from logical formula have been an active research subject in the fields of system testing and constraint solving, and various algorithms have been proposed recently from the fields. On the other hand, relatively little attention has been paid to comparing their strengths. This situation causes a problem in testing practice such as testers have confidence in choosing right testing techniques. In this paper, we take the first step toward this problem, investigating strengths of CT and RT in testing of large HCSs.

We consider several directions for future work. First, we plan to extend this comparative study to include other representative algorithms from CT, RT, and constraint solving techniques. In addition to QUICKSAMPLER and ICPL, we plan to include other clausal-SAT-based sampling techniques (e. g., UNIGEN [2] and STSAMPLER [5]), BDD-based techniques (e. g., [8,15]), and other CT greedy algorithms (e. g., [17]) in the comparative study. We also plan to extend the study to investigate fault detection capabilities of CT and RT, as done by [16].
References

1. Arcuri, A., Briand, L.C.: Formal analysis of the probability of interaction fault detection using random testing. IEEE Trans. Software Eng. 38(5), 1088–1099 (2012)

2. Chakraborty, S., Fremont, D.J., Meel, K.S., Seshia, S.A., Vardi, M.Y.: On parallel scalable uniform SAT witness generation. In: Proc. of TACAS 2015. pp. 304–319. Springer (2015)

3. Chen, T.Y., Leung, H., Mak, I.K.: Adaptive random testing. In: Proc. of ASIAN 2004. pp. 320–329 (2004)

4. Dutra, R., Laeufer, K., Bachrach, J., Sen, K.: Efficient sampling of SAT solutions for testing. In: Proc. ICSE 2018. pp. 549–559 (2018)

5. Ermon, S., Gomes, C., Selman, B.: Uniform solution sampling using a constraint solver as an oracle. In: Proc. of UAI 2012. p. 255–264 (2012)

6. Gargantini, A., Radavelli, M.: Migrating combinatorial interaction test modeling and generation to the web. In: 2018 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW). pp. 308–317 (April 2018). https://doi.org/10.1109/ICSTW.2018.00066

7. Garvin, B.J., Cohen, M.B., Dwyer, M.B.: Evaluating improvements to a meta-heuristic search for constrained interaction testing. Empirical Software Engineering 16(1), 61–102 (2011)

8. Hirasaki, Y., Kojima, H., Tsuchiya, T.: Applying random testing to constrained interaction testing. In: Proc. of SEKE 2013. pp. 193–198 (2014)

9. Johansen, M.F., Haugen, O., Fleurey, F.: An algorithm for generating t-wise covering arrays from large feature models. In: Proc. of SPLC 2012. pp. 46–55 (2012)

10. Kuhn, D.R., Bryce, R., Duan, F., Ghandehari, L.S., Lei, Y., Kacker, R.N.: Chapter one - combinatorial testing: Theory and practice. Advances in Computers, vol. 99, pp. 1–66. Elsevier (2015)

11. Kuhn, D.R., Kacker, R.N., Lei, Y.: Introduction to combinatorial testing. CRC Press (2013)

12. Lin, J., Cai, S., Luo, C., Lin, Q., Zhang, H.: Towards more efficient meta-heuristic algorithms for combinatorial test generation. In: Proc. of ESEC/FSE 2019. pp. 212–222 (2019)

13. Lynce, I., Silva, J.P.M.: On computing minimum unsatisfiable cores. In: Proc. of SAT 2004 (2004)

14. Nanba, T., Tsuchiya, T., Kikuno, T.: Using satisfiability solving for pairwise testing in the presence of constraints. IEICE Transactions 95-A(9), 1501–1505 (2012)

15. Oh, J., Batory, D.S., Myers, M., Siegmund, N.: Finding near-optimal configurations in product lines by random sampling. In: Proc. of ESEC/FSE 2017. pp. 61–71 (2017)

16. Wu, H., Nie, C., Petke, J., Jia, Y., Harman, M.: An empirical comparison of combinatorial testing, random testing and adaptive random testing. IEEE Transactions on Software Engineering (2018)

17. Yamada, A., Biere, A., Artho, C., Kitamura, T., Choi, E.: Greedy combinatorial test case generation using unsatisfiable cores. In: Proc. of ASE 2016. pp. 614–624 (2016)

18. Yu, L., Lei, Y., Kacker, R.N., Kuhn, D.R.: ACTS: A combinatorial test generation tool. In: Proc. of ICST 2013. pp. 370–375 (2013)

19. Yu, L., Duan, F., Lei, Y., Kacker, R., Kuhn, D.R.: Combinatorial test generation for software product lines using minimum invalid tuples. In: Proc. of HASE 2014. pp. 65–72 (2014)