-Combinatorial t-way testing with small t is known as testing would be of big interest to practitioners who consider an ecient black-box testing technique to detect parameter inter- applying t-way testing to their software testing. action failures. So far, several empirical studies have reported the Note that t-way testing is a black-box testing and thus is fee↵ewctivsteundeisessohfavte-wianyvetsetsitginatgedonthfaeulet↵edcteitveecntieosns aobfilitti-ews.aHyotwesetvinegr, dicult to achieve 100% code coverage and its code coverage on code coverage, which is one of the most important coverage depends on the system under test (SUT) model, e. g. parameters criteria widely used for software testing. This paper presents a and their values, designed for t-way testing. Therefore, in order quantitative analysis to evaluate the code-coverage e↵ectiveness to evaluate the code coverage e↵ectiveness of t-way testing, of t-way testing. Using three open source utility programs, we we compare code coverage obtained by t-way testing with that wco. mr. pt.acroedte-wcaoyvetreasgtienagnwditthestexshuaituestsiivzees(.all combination) testing by exhaustive testing, similarly to [10]. In order to quantitatively analyze the code coverage e↵ec-
The System Under Test (SUT) for combinatorial testing is modeled from parameters, their associated values from finite sets, and constraints between parameter-values. For instance, the SUT model shown in Table I, has three parameters (p1, p2, p3); the first two parameters have two possible values and the other has three possibilities. Constraints among parameter-values exist when some parameter-value combinations cannot occur. The example SUT has a constraint such that p2 , on if p3 = 1, i. e., the combination of p2 = on and p3 = 1 is not allowed.
More formally, a model of an SUT is defined as follows: Definition 1 (SUT model). An SUT model is a triple hP, V, i, where • P is a finite set of parameters p1, . . . , p|P|, • V is a family that assigns a finite value domain Vi for each parameter pi (1 i | P|), and • is a constraint on parameter-value combinations.
A test case is a value assignment for the parameters that satisfies the SUT constraint. For example, a 3-tuple (p1 =on, p2 =on, p3 =1) is a test case for our example SUT model. We call a sequence of test cases a test suite.
An exhaustive test suite (i. e. all combination test suite) is a sequence of all possible test cases, i. e., a test suite that covers all parameter-value combinations satisfying the SUT constraint. In general, exhaustive testing is impractical since it stipulates to test all possible test cases and thus its size (the number of test cases) increases exponentially with the number of parameters.
Combinatorial t-way testing (e. g., pairwise, when t = 2) alternatively stipulates to test all t-way parameter-value combinations satisfying the SUT constraint at least once. We call t an interaction strength. An exhaustive test suite corresponds to a t-way test suite with t = |P|.
Definition 2 (t-way test suite). Let hP, V, i be an SUT model. We say that a tuple of t (1 t | P|) parameter-values is possible i↵ it does not contradict the SUT constraint . A t-way test suite for the SUT model is a test suite that covers all possible t-tuples of parameter-values in the SUT model. Example 1. Consider the SUT model in Table I and t = 2. There exist 15 possible t-tuples (pairs) of parameter-values, as shown in Table II. The test suites T1 in Table III is a 2-way (pairwise) test suite since it covers all the possible parametervalue pairs in Table II. T2 in Table IV is a 3-way test suite and corresponds to the exhaustive test suite since the number of parameters in the example model is three .
Many algorithms to eciently construct t-way test suites
have been proposed so far. Approaches to generate t-way
test suites for SUT models with constraints include greedy
algorithms (e. g., AETG [
The e↵ectiveness of t-way testing with small interaction
strength t on fault detection have been reported by several
empirical studies so far [
Kuhn et al. [
Zhang et al. [
Petke et al. [
Henard et al. [
Choi et al. [
To our knowledge, the only work by Giannakopoulou et
al. [
Giannakopoulou et al. reported that for two program modules, the di↵erences of code coverage by 3-way testing and exhaustive testing are 0–2% for the four coverage metrics they used, while the numbers of test cases are 6,047 for 3-way testing but 9.9 ⇥ 106 for exhaustive testing. In this paper, we more thoroughly analyze the code coverage e↵ectiveness of t-way testing with 1 t 4 using three open source utility programs. Proj. flex grep make
Proj. flex grep make
0.7968 0.7789 0.8312 represents an assignment of a value to a parameter and for each j there are h j clauses that have l j literals. For the example SUT model in Figure 1, the size of parameter-values is 3; 2231 and the size of constraints is 2; 21.
2) Test Suites: We use t-way test suites with 1 t 4 that
are generated by ACTS [
3) Evaluation Metrics: To evaluate code coverage of each
test suite, we analyze the following two kinds of code coverage,
which are computed using gcov [
Table VIII shows the size, i. e. the number of test cases, and the code coverage (line coverage and branch coverage) of the exhaustive test suite for each project, while Table IX and Table X show those of the subject t-way test suites (1 t 4) generated by ACTS and PICT. Table IX shows the sizes of the subject t-way test suites with the ratio of them over the sizes of exhaustive test suites. Table X summarizes line coverage and branch coverage of the subject t-way test suites for each project. 1.00 0.99
In Table VIII and Table X, we show the average, minimum, and maximum values of code coverage for versions of each project.
For example, for project flex, the sizes of 2-way test suites (52 by ACTS and 51 by PICT) are less than 10% of the size of the exhaustive test suite (525) from Table VIII and Table IX. On the other hand, for flex, line coverage and branch coverage of 2-way test suites (the exhaustive test suite) are on average 0.7927 (0.7968) and 0.8522 (0.8544) from Table VIII and Table X.
A. RQ1: t-way testing vs. exhaustive testing
To compare the code coverage between t-way testing and exhaustive testing, we investigate the following metric
RCov(Tt, EX) = Cov(Tt) / Cov(EX), which denotes the ratio of code coverage of t-way test suite Tt over that of exhaustive test suite EX.
Table XI summarizes the values of RCov(Tt, EX) with 1 t 4 for line coverage and branch coverage for each project and
Proj. (hinges), and highest/lowest values within 1.5 ⇥ the inter• How high code coverage can t-way testing achieve compared to exhaustive testing? coverage of exhaustive testing.
• Can t-way testing obtain higher code coverage earlier compared to exhaustive testing?
Figure 3 shows example line coverage growths and branch coverage growths of t-way test suites (1 t 4) and the exhaustive test suites for one version (v1) of project grep. (The coverage growths represent the typical cases of our experiment results.) We can see that t-way testing with smaller t obtains From Table XI and Figure 2, we can see that t-way testing higher code coverage earlier compared to exhaustive testing with even small t can achieve high values of RCov(Tt, EX), i. e. high ratios of code coverage over the code coverage of exhaustive testing. and t-way testing with larger t.
For the example case in Figure 3, to obtain 48% line coverage (46% branch coverage), 1-way, 2-way, 3-way, and 4-way testing In the result of our case study, 1-way (2-way) testing covers respectively require 35, 42, 56, and 56 (36, 47, 71, and 71) test avg. 97.82% (99.77%) of line coverage of exhaustive testing and cases, while exhaustive testing requires 219 (265) test cases. 1.3 1.2 Fig. 4. Ratios of code coverage of t-way testing (1 t 4) over that of exhaustive testing with the same sizes for all versions of projects. • How large t is necessary for t-way testing to achieve the code coverage close to that by exhaustive testing? Surprisingly, as the result of our case study, all t-way test suites with 1 t 4 obtain more than 95% of code coverage of exhaustive test suites. Especially, for project grep, 4-way test suites obtain the same line coverage and branch coverage with the exhaustive test suite. As described in Table XI, in 30 cases of all 34 cases, 2-way, 3-way, and 4-way test suites achieve more than 99.5% of line coverage of exhaustive test suites. For branch coverage, in all cases, 4-way test suites achieve more than 99.5% of coverage of exhaustive test suites.
From the results, t-way testing with small t (1 t 4) can eciently obtain code coverage close to that by exhaustive testing while requiring smaller test cases. B. RQ2: t-way testing vs. exhaustive testing in the same sizes
To compare the code coverage between t-way testing and exhaustive testing with the same sizes, we investigate the following metric
RCov(Tt, EX⇤) = Cov(Tt) / Cov(EX⇤), which denotes the ratio of code coverage of t-way test suite Tt over that of a subset, hereafter denoted by EX⇤ , of exhaustive test suite EX whose size is same with Tt. In our experiments, we constructed EX⇤ 100 times by randomly selecting |Tt| test cases from exhaustive test suite EX and use the average value of the code coverage for the 100 EX⇤.
Table XII summarizes the values of RCov(Tt, EX⇤ ) with 1 t 4 for line coverage and branch coverage for each project and all projects. In the table, we also show the numbers of cases where RCov(Tt, EX⇤ ) 105%, i. e. t-way testing achieves more than 105% of the coverage obtained by exhaustive testing with the same size, over the numbers of all cases for projects. Figure 4 presents the box plots for the results of RCov(Tt, EX⇤ ) for all projects. • With the same number of test cases, how di↵erent are t-way testing and exhaustive testing on code coverage? From Table XII and Figure 4, we can see that t-way test suites with 1 t 4 achieve higher line coverage and branch coverage compared to exhaustive test suites in the same sizes. Especially, t-way testing with smaller t obtains higher values of RCov(Tt, EX⇤ ), i. e. higher ratios of code coverage over that of exhaustive testing in the same size.
As described in Table XII, for all cases, 1-way and 2-way testing achieve more than 105% of code coverage of exhaustive testing with the same size. For 3-way and 4-way testing, the numbers of cases that achieve more than 105% of line (branch) coverage of exhaustive testing with the same sizes are 24 and 20 (24 and 16) cases among all 34 cases.
From the results, t-way testing with smaller t can obtain higher code coverage compared to exhaustive testing with the same number of test cases.
This paper analyzes the code coverage e↵ectiveness of combinatorial t-way testing with small t. As a result of our empirical evaluation using a collection of open source utility programs, t-way testing with small t (1 t 4) eciently covers more than 95% of code coverage achieved by exhaustive testing, while requiring much smaller test cases. In addition, comparing in the same test suite sizes, t-way testing with smaller t obtains higher ratio of code coverage over that by exhaustive testing.
In this paper, we evaluate two kinds of widely used code coverage metrics, line coverage and branch coverage. Further work includes evaluating other metrics such as loop coverage, condition coverage, etc. Another further work is to investigate both the code coverage e↵ectiveness and the fault detection e↵ectiveness of t-way testing and analyze the relation between them on real software projects.
The authors would like to thank anonymous referees for their helpful comments and suggestions to improve this paper. This work was partly supported by JSPS KAKENHI Grant Number 16K12415.
Avg. of RCov(Tt, EX⇤) (R⇤ = Cov(Tt)/Cov(EX⇤))