Code Coverage Analysis of Combinatorial Testing
Eun-Hye Choi⇤ , Osamu Mizuno† , Yifan Hu†⇤ National Institute of Advanced Industrial Science and Technology (AIST), Ikeda, Japan

Email: e.choi@aist.go.jp† Kyoto Institute of Technology, Kyoto, Japan

Email: o-mizuno@kit.ac.jp, y-hu@se.is.kit.ac.jp

testing would be of big interest to practitioners who consider
applying t-way testing to their software testing.
Note that t-way testing is a black-box testing and thus isdifficult to achieve 100% code coverage and its code coveragedepends on the system under test (SUT) model, e. g. parameters
and their values, designed for t-way testing. Therefore, in orderto evaluate the code coverage e↵ectiveness of t-way testing,
we compare code coverage obtained by t-way testing with thatby exhaustive testing, similarly to [10].
In order to quantitatively analyze the code coverage e↵ecKeywords-Combinatorial testing; t-way testing; Exhaustive test- tiveness of t-way testing compared to exhaustive testing, we
ing; Code coverage; Line coverage; Branch coverage.
set up the following two research questions:• RQ1: How high code coverage can t-way testing achieve
compared to exhaustive testing? Can t-way testing obtain
I. Introduction
higher code coverage earlier compared to exhaustive
Combinatorial testing [15], [20] is a common black-box
testing? How large interaction strength t is necessary fortesting to detect failures caused by parameter interactions.
t-way testing to achieve the code coverage close to that
Modern software systems have a lot of parameters, and thus
by exhaustive testing?
their interactions are too numerous to be exhaustively tested.
• RQ2: With the same number of test cases, how di↵erent
Combinatorial t-way testing [15], [20], where t is called an
are t-way testing and exhaustive testing on code coverage?
interaction strength, addresses this problem by testing all value For evaluating the code coverage e↵ectiveness of t-way
combinations of t parameters with small t, instead of testing all testing, RQ1 compares t-way testing and exhaustive testing
parameter-value combinations exhaustively. t-way testing has in their original sizes, while RQ2 compares t-way testing andbeen applied to e. g. conformance testing for DOM (Document exhaustive testing in the same sizes.
Object Model) Events standard [19], rich web applications
To answer the above research questions, we perform a case[18], commercial MP3 players [25], and a ticket gate system study that analyzes t-way test suites with 1  t  4 on two kinds
for transportation companies [14].
of widely used code coverage; line coverage (i. e., statement
Kuhn et al. [16] investigated the fault detection e↵ectiveness coverage) and branch coverage (i. e., decision coverage). Forof t-way testing; their result showed that t-way testing with an empirical case study, we use seventeen versions of threesmall interaction strength t ( 4) can efficiently detect most C program projects, flex, grep, and make, from the Softwareinteraction failures while significantly reducing the number artifact Infrastructure Repository (SIR) [7]. To prepare t-way
of test cases compared to exhaustive testing, which tests all test suites, we first construct SUT models with constraints
parameter-value combinations. Other studies [2], [8], [25] also from test plans in Test Specification Language (TSL) [21]supported the result by Kuhn et al. [16].
of the repository. We next generate t-way test suites for the
On the other hand, as far as we know, the only work by SUT models using two state-of-the-art t-way test generation
Giannakopoulou et al. [10] reported the e↵ectiveness of t- tools, ACTS [3], [26] and PICT [6], [31]. We evaluate theway testing on code coverage. They compared code coverage code coverage e↵ectiveness of t-way testing by comparing the
between their model-checker based exhaustive testing and t-way test suites and exhaustive test suites on the examining
3-way testing with two program modules for a NASA air line coverage and branch coverage with test suite sizes.
transportation system.
Paper Organization: Section II-A explains combinatorial
Code coverage, which measures what percentage of source t-way testing and Section II-B describes related work oncode is executed by a test suite, has been considered as one of the e↵ectiveness evaluation of t-way testing. Section III
the most important coverage metrics for software testing and describes our experimental setting, and Section IV explainsis required by many industrial software development standards experimental results which answer the research questions.
(e. g. [1]). Therefore, the code coverage e↵ectiveness of t-way Section V concludes this paper.
Abstract—Combinatorial t-way testing with small t is known as
an efficient black-box testing technique to detect parameter interaction failures. So far, several empirical studies have reported thee↵ectiveness of t-way testing on fault detection abilities. However,few studies have investigated the e↵ectiveness of t-way testing
on code coverage, which is one of the most important coverage
criteria widely used for software testing. This paper presents aquantitative analysis to evaluate the code-coverage e↵ectivenessof t-way testing. Using three open source utility programs, we
compare t-way testing with exhaustive (all combination) testing
w. r. t. code coverage and test suite sizes.

TABLE I
An example SUT model.
Parameter

ValuesDebug mode (= p1 )Bypass use (= p2 )Fast scanner (= p3 )on, o↵
on, o↵FastScan (= 1), FullScan (= 2), o↵

Constraint:(Fast scanner = FullScan) ! (Bypass use , on)
TABLE II
An example of all possible pairs of parameter-values.

Param. pairs

Parameter-value pairs(p1 , p2 )(p1 , p3 )(p2 , p3 )(on, on), (on, o↵), (o↵, on), (o↵, o↵)(on, 1), (on, 2), (on, o↵), (o↵, 1), (o↵, 2), (o↵, o↵)(on, 1), (on, o↵), (o↵, 1), (o↵, 2), (o↵, o↵)

TABLE IV
An exhaustive test suite T2 .

TABLE III
A 2-way test suite T1 .

1
2
3
4
5
6

p1

p2

p3

on
on
o↵
o↵
o↵
on

on
o↵
o↵
on
o↵
o↵

1
o↵
1
o↵
2
1

1
2
3
4
5
6
7
8
9
10

p1

p2

p3

on
on
on
on
on
o↵
o↵
o↵
o↵
o↵

on
on
o↵
o↵
o↵
on
on
o↵
o↵
o↵

1
o↵
1
2
o↵
1
o↵
1
2
o↵

TABLE V
Related work.
Metrics studied
Code coverage

II. Background and Related Work
A. Combinatorial t-way Testing

Kuhn et al. (2004) [16]Zhang et al. (2012) [25]Petke et al. (2015) [22]Henard et al. (2015) [11]Choi et al. (2016) [4]
Giannakopoulou et al. (2011) [10]This paper

Fault detection
X
X
X
X
X

The System Under Test (SUT) for combinatorial testingXis modeled from parameters, their associated values fromX
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 We say that a tuple of t (1  t  |P|) parameter-values isand the other has three possibilities. Constraints among possible i↵ it does not contradict the SUT constraint . A
parameter-values exist when some parameter-value combina- t-way test suite for the SUT model is a test suite that covers
tions cannot occur. The example SUT has a constraint such all possible t-tuples of parameter-values in the SUT model.
that p2 , on if p3 = 1, i. e., the combination of p2 = on and
Example 1. Consider the SUT model in Table I and t = 2.
p3 = 1 is not allowed.
There exist 15 possible t-tuples (pairs) of parameter-values, as
More formally, a model of an SUT is defined as follows:shown in Table II. The test suites T1 in Table III is a 2-way
Definition 1 (SUT model). An SUT model is a triple hP, V, i,(pairwise) test suite since it covers all the possible parameterwhere
value pairs in Table II. T2 in Table IV is a 3-way test suite• P is a finite set of parameters p1 , . . . , p|P| ,and corresponds to the exhaustive test suite since the number• V is a family that assigns a finite value domain Vi forof parameters in the example model is three .
each parameter pi (1  i  |P|), andMany algorithms to efficiently construct t-way test suites•
is a constraint on parameter-value combinations.
have been proposed so far. Approaches to generate t-way
A test case is a value assignment for the parameters that test suites for SUT models with constraints include greedy
satisfies the SUT constraint. For example, a 3-tuple (p1 =on, algorithms (e. g., AETG [5], PICT [6], [31], and ACTS [3],p2 =on, p3 =1) is a test case for our example SUT model. We [26]), heuristic search (e. g., CASA [9], HHSA [12], andcall a sequence of test cases a test suite.
TCA [17]), and SAT-based approaches (e. g., Calot [23], [24]).
An exhaustive test suite (i. e. all combination test suite) is
a sequence of all possible test cases, i. e., a test suite that B. Related Work: E↵ectiveness evaluation of t-way testing
covers all parameter-value combinations satisfying the SUT
The e↵ectiveness of t-way testing with small interaction
constraint. In general, exhaustive testing is impractical since itstrength t on fault detection have been reported by several
stipulates to test all possible test cases and thus its size (theempirical studies so far [13], [15], but the code coverage of
number of test cases) increases exponentially with the number
t-way testing has not been studied well. Table V summarizesof parameters.
the e↵ectiveness metrics studied in related work.
Combinatorial t-way testing (e. g., pairwise, when t = 2)
Kuhn et al. [16] investigated parameter interactions inducing
alternatively stipulates to test all t-way parameter-value combiactual failures of four systems; a software for medical devices,
nations satisfying the SUT constraint at least once. We call ta browser, a server, and a database system. As a result, 29–68%
an interaction strength. An exhaustive test suite correspondsof the faults involved a single parameter; 70–97% (89–99%)
to a t-way test suite with t = |P|.
of the faults involved up to two (three) parameter interactions;Definition 2 (t-way test suite). Let hP, V, i be an SUT model. 96–100% of the faults involved up to four and five parameterinteractions; no fault involved more than six parameters. From
the result, the authors concluded that most failures are triggeredby parameter interactions with small t (at most four to six)and thus t-way testing with 4  t  6 could provide the fault
detection ability of “pseudo-exhaustive” testing.
Zhang et al. [25] also explored that failures of actualcommercial MP3 players are triggered by t-way parameterinteractions with at most t = 4.
Petke et al. [22] more thoroughly studied the efficiency ofearly fault detection by t-way testing with 2  t  6. They
used six projects, flex, make, grep, gzip, nanoxml, and siena,
from the Software artifact Infrastructure Repository (SIR) andshowed the number of faults detected after 25%, 50%, 70%,
and 100% of test cases are executed.
Henard et al. [11] used five projects, grep, sed, flex, make,and gzip, also from SIR and compared the number of faults
detected by test suite prioritization with t-way coverage (2 t  4) and other black-box and white-box prioritization.
Choi et al. [4] used three projects, flex, grep, and make,from SIR and investigated a correlation of the fault detection effectiveness with two evaluation metrics, called weight coverageand KL divergence, for prioritized t (= 2)-way testing.
To our knowledge, the only work by Giannakopoulou etal. [10] reported code coverage of t-way testing. Their target
system is a component of the Tactical Separation Assisted
Flight Environment (TSAFE) of the Next Generation Air
Transportation System (NextGen) by the NASA Ames ResearchCenter. In their work, t (= 3)-way testing and their modelchecker (JPF [30]) based exhaustive testing are comparedw. r. t. code coverage; line coverage, branch coverage, loop
coverage, and strict condition coverage, which are computed
using CodeCover [28].
Giannakopoulou et al. reported that for two program modules, the di↵erences of code coverage by 3-way testing andexhaustive testing are 0–2% for the four coverage metrics theyused, while the numbers of test cases are 6,047 for 3-way
testing but 9.9 ⇥ 106 for exhaustive testing. In this paper, wemore thoroughly analyze the code coverage e↵ectiveness of
t-way testing with 1  t  4 using three open source utility
programs.

TABLE VI
Subject programs.
Proj.

Ver.

IdentifierYear of release

LoC

flex

v0
v1
v2
v3
v4
v5

2.4.3
2.4.7
2.5.1
2.5.2
2.5.3
2.5.4

1993
1994
1995
1996
1996
1997

10,163
10,546
13,00013,04813,142
13,144

grep

v0
v1
v2
v3
v4
v5

2.0
2.2
2.3
2.4
2.4.1
2.4.2

1996
1998
1999
1999
2000
2000

8,163
11,945
12,681
12,78013,28013,275

make

v0
v1
v2
v3
v4

3.75
3.76.1
3.77
3.78.1
3.79.1

1996
1997
1998
1999
2000

17,424
18,525
19,61020,401
23,188Parameters:...
Debug mode:
Debug_on.
Debug_off.

# -dBypass use:
Bypass_on.
Bypass_off.

# -Cr[property Bypass]

Fast scanner:
FastScan.
FullScan.
off.
...

# -f, -Cf[property FastScan][if !Bypass][property FullScan][property f&Cfoff]

Fig. 1.

A part of the test plan for flex in TSL.

B. Subject Test Suites

1) SUT Models: For each project, flex, grep, and make, weconstruct an SUT model for t-way testing whose parameters,
values, and constraints are fully extracted from the test plan in
TSL (Test Specification Language), which is included in SIR.
For example, Figure 1 shows a part of the test plan in TSL for
project flex. From the TSL specification, we construct the SUT
III. Experiments
model for flex whose parameters include Debug mode(= p1 ),Bypass use(= p2 ) and Fast scanner(= p3 ), p2 has two values
A. Subject Programs
including Bypass on(= on), p3 has three values including
To investigate code coverage of t-way testing, we use three FullScan(= 2), and constraints include (p3 = 2) ! (p2 , on).
open source projects of C programs, flex, grep, and make, Table I corresponds to a part of the SUT model for flex, whichfrom the Software artifact Infrastructure Repository (SIR) [32]. is constructed from the part of the test plan in Figure 1.
flex is a lexical analysis generator. grep is a program to search
Table VII shows the size of the SUT model constructed
for text matching regular expressions. make is a program to for each project. In the table, the size of parameter-values iscontrol the compile and build process. The programs have expressed as k; gk11 gk22 . . . gknn , which indicates that the number ofbeen widely used to evaluate testing techniques by researchers parameters is k and for each i there are ki parameters that havehm
in studies including [4], [11], [22]. Table VI shows for each gi values. The size of constraints is expressed as l; l1h1 l2h2 . . . lm,
version of programs we use, the version identifier, the year which indicates that the constraint is described in conjunctive
released, and the lines of code (LoC) calculated using cloc [27]. normal form (CNF) with l variables whose Boolean value

TABLE VII
Constructed SUT models.

Line
1.00

Proj.

29; 323 44 62
97; 2712 221 242 2517 269

grep

Parameter-values
Constraints

14; 24 31 43 51 61 91 111 131 201
87; 2433 327 48 75 161 241 271 281 3110

0.98

make

Parameter-values
Constraints

22; 22 312 44 52 61 71
79; 2526 211 221 231 243 257 269

0.97

525

grep

470

make

793

●

0.99

TABLE VIII
Sizes and code coverage of exhaustive test suites.

flex

●

●
●

Parameter-values
Constraints

Size

●
●

flex

Proj.

●

●

Model size

BranchLine coverage

Branch coverage

Avg.
Min.
Max.

0.79680.77890.83120.85440.81510.9316

Avg.
Min.
Max.

0.49610.47260.59000.49480.4746
0.5826

Avg.
Min.
Max.

0.45430.42340.4726

0.53730.5126
0.5494●●

0.96
1−way 2−way 3−way 4−way

1−way 2−way 3−way 4−way

Fig. 2. Ratio of code coverage of t-way testing (1  t  4) over that ofexhaustive testing for all versions of projects.
Line

Branch0.5

0.4

represents an assignment of a value to a parameter and for
1−way
0.3
each j there are h j clauses that have l j literals. For the example
2−way
3−way
SUT model in Figure 1, the size of parameter-values is 3; 22 31
4−way
and the size of constraints is 2; 21 .
Exhaustive
0.22) Test Suites: We use t-way test suites with 1  t  4 thatare generated by ACTS [3], [26] and PICT [6], [31] for our0
100 200 300 400
0100 200 300 400
constructed SUT models with constraints. The tools ACTS and
Test cases
PICT are state-of-the-art open source t-way test generation
tools developed by NIST (National Institute of Standards and Fig. 3. Example code coverage growths of t-way testing (1  t  4) andTechnology) and Microsoft, respectively. For comparison, we exhaustive testing for one version (v1) of grep.
also use exhaustive test suites each of which obtains all possible
test cases. The exhaustive test suite for the test plan of each
In Table VIII and Table X, we show the average, minimum,
project is included in SIR.
3) Evaluation Metrics: To evaluate code coverage of each and maximum values of code coverage for versions of eachtest suite, we analyze the following two kinds of code coverage, project.
For example, for project flex, the sizes of 2-way test suites
which are computed using gcov [29]:(52 by ACTS and 51 by PICT) are less than 10% of the size
• Line coverage: the percentage of program lines executed.
of the exhaustive test suite (525) from Table VIII and Table IX.
• Branch coverage: the percentage of branches of conditional
On the other hand, for flex, line coverage and branch coveragestatements executed.
of 2-way test suites (the exhaustive test suite) are on average
gcov is a source code analysis tool, which is a standard utility
0.7927 (0.7968) and 0.8522 (0.8544) from Table VIII anddelivered with the GNU C/C++ Compiler and reports how Table X.
many lines and branches are executed.
A. RQ1: t-way testing vs. exhaustive testing
IV. Results
To compare the code coverage between t-way testing andTable VIII shows the size, i. e. the number of test cases,
exhaustive
testing, we investigate the following metricand the code coverage (line coverage and branch coverage) of
the exhaustive test suite for each project, while Table IX andRCov (T t , EX) = Cov(T t ) / Cov(EX),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 which denotes the ratio of code coverage of t-way test suite
subject t-way test suites with the ratio of them over the sizes of T t over that of exhaustive test suite EX.
exhaustive test suites. Table X summarizes line coverage andTable XI summarizes the values of RCov (T t , EX) with 1  t branch coverage of the subject t-way test suites for each project. 4 for line coverage and branch coverage for each project andTABLE IX
Sizes of t-way test suites (1  t  4).
# of test cases (ratio over # of the exhaustive test cases)

Proj.

1-way

2-way

3-way

4-way

flex

ACTS
PICT

30
30

(5.71 %)
(5.71 %)

52
51

(9.90 %)
(9.71 %)

9190

(17.33 %)(17.14 %)155
154(29.52 %)(29.33 %)

grep

ACTS
PICT

40
40

(8.51 %)
(8.51 %)

76
77

(16.17 %)(16.38 %)183
180(38.94 %)(38.30 %)328
326(69.79 %)(69.36 %)

make

ACTS
PICT

27
27

(3.40 %)
(3.40 %)

34
34

(4.29 %)
(4.29 %)

44
45

(5.55 %)
(5.67 %)

68
69

(8.58 %)
(8.70 %)TABLE X
Code coverage of t-way test suites (1  t  4).
Line coverage

Proj.

Branch coverage

1-way

2-way

3-way

4-way

1-way

2-way

3-way

4-way

flex

Avg.
Min.
Max.

0.76830.74810.81450.79270.77550.8264

0.79340.77630.82670.79310.77550.82670.84070.80180.92250.85220.8136
0.92810.85220.8136
0.92810.85220.8136
0.9281

grep

Avg.
Min.
Max.

0.4917
0.46680.58750.49590.47230.58970.49610.47260.59000.49610.47260.59000.47690.45490.5726

0.48800.4676
0.5786

0.49330.47120.58450.49480.4746
0.5826

make

Avg.
Min.
Max.

0.44510.41680.46280.45390.42300.47240.45400.42300.47240.45400.42300.4726

0.53210.50530.5442

0.53640.51170.5484

0.5366
0.51170.5484

0.5366
0.51170.5484

TABLE XI
Comparison of code coverage between t-way testing (1  t  4) and exhaustive testing.
Proj.

Line coverage

Branch coverage

1-way

2-way

3-way

4-way

1-way

2-way

3-way

4-way

Avg. of RCov (T t , EX)(R = Cov(T t )/Cov(EX))

flex
grep
make

96.41 %
99.11 %
97.97 %
97.82 %

99.49 %
99.95 %
99.91 %
99.77 %

99.58 %
100.00 %99.93 %
99.83 %

99.54 %
100.00 %99.92 %
99.81 %

98.40 %
96.32 %
99.03 %
97.85 %

99.74 %
98.58 %
99.84 %
99.36 %

99.74 %
99.67 %
99.88 %
99.76 %

99.74 %
100.00 %99.87 %
99.87 %# (R 99.5 %)/ # all cases

flex
grep
make

0 / 124 / 120 / 104 / 348 / 12
12 / 1210 / 1030 / 34

8 / 12
12 / 1210 / 1030 / 34

8 / 12
12 / 1210 / 1030 / 34

0 / 120 / 120 / 100 / 3412 / 120 / 1210 / 1022 / 34

12 / 127 / 1210 / 1029 / 34

12 / 1212 / 1210 / 1034 / 34

Avg.

Total

all projects. In the table, we also show the numbers of cases avg. 97.85% (99.36%) of branch coverage of exhaustive testing.
where RCov (T t , EX) 99.5%, i. e. t-way testing achieves more With 3-way (4-way) testing, line coverage is avg. 99.83%
than 99.5% of the coverage obtained by exhaustive testing, (99.81%) and branch coverage is avg. 99.76% (99.87%) of theover the numbers of all cases (versions) for projects.
coverage of exhaustive testing.
Figure 2 presents the box plots for the results of RCov (T t , EX)• Can t-way testing obtain higher code coverage earlier
for all projects. Each box plot shows the mean (circle in thecompared to exhaustive testing?
box), median (thick horizontal line), the first/third quartiles
Figure 3 shows example line coverage growths and branch(hinges), and highest/lowest values within 1.5 ⇥ the inter- coverage growths of t-way test suites (1  t  4) and thequartile range of the hinge (whiskers).
exhaustive test suites for one version (v1) of project grep. (The• How high code coverage can t-way testing achieve
coverage growths represent the typical cases of our experimentcompared to exhaustive testing?
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 testingwith even small t can achieve high values of RCov (T t , EX), and t-way testing with larger t.
i. e. high ratios of code coverage over the code coverage of
For the example case in Figure 3, to obtain 48% line coverage
exhaustive testing.
(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.

Line

Branch

1.3

1.2

●

1.1

●

●

●
●

●

●

●

1.0
1−way

2−way

3−way

4−way

1−way

2−way

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 branchcoverage compared to exhaustive test suites in the same sizes.
Especially, t-way testing with smaller t obtains higher valuesof RCov (T t , EX⇤), i. e. higher ratios of code coverage over thatof 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, thenumbers of cases that achieve more than 105% of line (branch)coverage of exhaustive testing with the same sizes are 24 and20 (24 and 16) cases among all 34 cases.
•

3−way

4−way

Fig. 4. Ratios of code coverage of t-way testing (1  t  4) over that ofexhaustive testing with the same sizes for all versions of projects.

How large t is necessary for t-way testing to achieve thecode 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 coverageof exhaustive test suites. Especially, for project grep, 4-way
test suites obtain the same line coverage and branch coveragewith 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 efficiently obtain code coverage close to that byexhaustive 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 andexhaustive testing with the same sizes, we investigate thefollowing metricRCov (T t , EX⇤) = Cov(T t ) / Cov(EX⇤),which denotes the ratio of code coverage of t-way test suite T tover that of a subset, hereafter denoted by EX⇤, of exhaustive
test suite EX whose size is same with T t . In our experiments,
we constructed EX⇤ 100 times by randomly selecting |T t | test
cases from exhaustive test suite EX and use the average valueof the code coverage for the 100 EX⇤.
Table XII summarizes the values of RCov (T t , 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 ofcases where RCov (T t , EX⇤) 105%, i. e. t-way testing achieves
more than 105% of the coverage obtained by exhaustive testingwith the same size, over the numbers of all cases for projects.
Figure 4 presents the box plots for the results of RCov (T t , EX⇤)for all projects.

From the results, t-way testing with smaller t can obtainhigher code coverage compared to exhaustive testing withthe same number of test cases.
V. Conclusion
This paper analyzes the code coverage e↵ectiveness of
combinatorial t-way testing with small t. As a result of ourempirical evaluation using a collection of open source utility
programs, t-way testing with small t (1  t  4) efficiently
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 withsmaller t obtains higher ratio of code coverage over that byexhaustive 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 detectione↵ectiveness of t-way testing and analyze the relation between
them on real software projects.
Acknowledgments
The authors would like to thank anonymous referees fortheir helpful comments and suggestions to improve this paper.
This work was partly supported by JSPS KAKENHI Grant
Number 16K12415.
References[1] International Standardization Organization, ISO26262: Road vehicles Functional safety, November 2011.
[2] K. Z. Bell and M. A. Vouk. On e↵ectiveness of pairwise methodology
for testing network-centric software. In Proc. of International Conferenceon Information and Communication Technology, pages 221–235. IEEE,2005.
[3] M. N. Borazjany, L. Yu, Y. Lei, R. Kacker, and R. Kuhn. Combinatorial
testing of ACTS: A case study. In Proc. of the 5th International
Conference on Software Testing, Verification and Validation (ICST),
pages 591–600. IEEE, 2012.
[4] E. Choi, S. Kawabata, O. Mizuno, C. Artho, and T. Kitamura. Teste↵ectiveness evaluation of prioritized combinatorial testing: a case study.
In Proc. of the International Conference on Software Quality, Reliability& Security (QRS), pages 61–68. IEEE, 2016.

TABLE XII
Comparison of code coverage between t-way testing (1  t  4) and exhaustive testing with the same sizes.
Proj.

Line coverage

Branch coverage

1-way

2-way

3-way

4-way

1-way

2-way

3-way

4-way

Avg. of RCov (T t , EX⇤)(R⇤ = Cov(T t )/Cov(EX⇤))

flex
grep
make

116.45 %109.93 %106.63 %111.26 %117.26 %108.39 %106.45 %110.95 %114.45 %105.36 %106.11 %108.79 %111.04 %103.31 %105.36 %106.64 %116.65 %111.26 %105.99 %111.61 %116.12 %110.44 %105.80 %111.08 %113.65 %107.36 %105.51 %109.04 %110.57 %104.94 %104.85 %106.90 %# (R⇤ 105 %)/ # all cases

flex
grep
make

12 / 1212 / 1210 / 1034 / 34

12 / 1212 / 1210 / 1034 / 34

12 / 122 / 1210 / 1024 / 34

12 / 122 / 12
6 / 1020 / 34

12 / 1212 / 1210 / 1034 / 34

12 / 1212 / 1210 / 1034 / 34

12 / 122 / 1210 / 1024 / 34

12 / 122 / 122 / 1016 / 34

Avg.

Total

[5] M. B. Cohen, M. B. Dwyer, and J. Shi. Constructing interaction test
suites for highly-configurable systems in the presence of constraints: A
greedy approach. IEEE Trans. Software Eng., 34(5):633–650, 2008.
[6] J. Czerwonka. Pairwise testing in the real world: Practical extensions
to test-case senarios. In Proc. of the 24th Pacific Northwest Software
Quality Conference, pages 419–430. Citeseer, 2006.
[7] H. Do, S. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact.
Empirical Software Engineering, 10(4):405–435, 2005.
[8] G. B. Finelli. NASA software failure characterization experiments.
Reliability Engineering & System Safety, 32(1):155–169, 1991.
[9] B. J. Garvin, M. B. Cohen, and M. B. Dwyer. Evaluating improvements
to a meta-heuristic search for constrained interaction testing. Empirical
Software Engineering, 16(1):61–102, 2011.
[10] D. Giannakopoulou, D. Bushnell, J. Schumann, H. Erzberger, and
K. Heere. Formal testing for separation assurance. Annals of Mathematics
and Artificial Intelligence, 63(1):5–30, 2011.
[11] C. Henard, M. Papadakis, M. Harman, Y. Jia, and Y. Le Traon. Comparing
white-box and black-box test prioritization. In Proc. of the 38th
International Conference on Software Engineering (ICSE), pages 523–
534. ACM, 2016.
[12] Y. Jia, M. B. Cohen, M. Harman, and J. Petke. Learning combinatorialinteraction testing strategies using hyperheuristic search. In Proc. of the37th International Conference on Software Engineering (ICSE), pages
540–550. IEEE/ACM, 2015.
[13] R. N. Kacker, D. R. Kuhn, Y. Lei, and J. F. Lawrence. Combinatorial testing for software: An adaptation of design of experiments. Measurement,
46(9):3745–3752, 2013.
[14] T. Kitamura, A. Yamada, G. Hatayama, C. Artho, E. Choi, N. T. B. Do,
Y. Oiwa, and S. Sakuragi. Combinatorial testing for tree-structured test
models with constraints. In Proc. of the International Conference on
Software Quality, Reliability & Security (QRS), pages 141–150. IEEE,
2015.
[15] D. R. Kuhn, R. N. Kacker, and Y. Lei. Introduction to combinatorial
testing. CRC Press, 2013.
[16] D. R. Kuhn, D. R. Wallace, and A. M. Gallo. Software fault interactions
and implications for software testing. IEEE Trans. Software Eng.,30(6):418–421, 2004.
[17] J. Lin, C. Luo, S. Cai, K. Su, D. Hao, and L. Zhang. TCA: An efficient
two-mode meta-heuristic algorithm for combinatorial test generation.
In Proc. of the 30th International Conference on Automated Software
Engineering (ASE), pages 494–505. ACM/IEEE, 2015.
[18] C. Maughan. Test case generation using combinatorial based coveragefor rich web applications. PhD Thesis. Utah State University, 2012.
[19] C. Montanez, D. R. Kuhn, M. Brady, R. M. Rivello, J. Reyes, and M. K.
Powers. An application of combinatorial methods to conformance testingfor document object model events. NISTIR-7773, 2010.
[20] C. Nie and H. Leung. A survey of combinatorial testing. ACM Computing
Surveys, 43(2):11, 2011.
[21] T. J. Ostrand and M. J. Balcer. The category-partition method forspecifying and generating functional tests. Commun. ACM, 31(6):676–
686, 1988.
[22] J. Petke, M. Cohen, M. Harman, and S. Yoo. Practical combinatorialinteraction testing: Empirical findings on efficiency and early fault
detection. IEEE Trans. Software Eng., 41(9):901–924, 2015.

[23] A. Yamada, A. Biere, C. Artho, T. Kitamura, and E. Choi. Greedy
combinatorial test case generation using unsatisfiable cores. In Proc. ofthe 31st International Conference on Automated Software Engineering(ASE), pages 614–624. IEEE/ACM, 2016.
[24] A. Yamada, T. Kitamura, C. Artho, E. Choi, Y. Oiwa, and A. Biere.
Optimization of combinatorial testing by incremental SAT solving. In
Proc. of the 8th International Conference on Software Testing, Verification
and Validation (ICST), pages 1–10. IEEE, 2015.
[25] Z. Zhang, X. Liu, and J. Zhang. Combinatorial testing on id3v2 tagsof mp3 files. In Proc. of the 5th International Conference on Software
Testing, Verification and Validation (ICST), pages 587–590. IEEE, 2012.
[26] ACTS, Available: http://csrc.nist.gov/groups/SNS/acts/.
[27] cloc – Count Lines of Code, Available: http://cloc.sourceforge.net.
[28] CodeCover – an open-source glass-box testing tool, Available:
http://codecover.org.
[29] gcov–atest
coverageprogram,Available:
http://gcc.gnu.org/onlinedocs/gcc/Gcov.html.
[30] JavaPathfinder, Available: http://babelfish.arc.nasa.gov/trac/jpf.
[31] Pairwise
Independent
Combinatorial
Tool,
Available:
http://github.com/Microsoft/pict.
[32] Software-artifact Infrastructure Repository, Available: http://sir.unl.edu/.