rmkRemark definitionDefinition pfProof potProof of Theorem LABEL:thm2

[1]

# Constrained Detecting Arrays: Mathematical Structures for Fault
Identification in Combinatorial Interaction Testing

Hao Jin<EMAIL_ADDRESS>Ce Shi<EMAIL_ADDRESS>Tatsuhiro
Tsuchiya<EMAIL_ADDRESS>Osaka University, Yamadaoka 1-5, Suita
City, Osaka, Japan  Shanghai Lixin University of Accounting and Finance, 2800
Wenxiang Road, Shanghai, China

###### Abstract

Context: Detecting arrays are mathematical structures aimed at fault
identification in combinatorial interaction testing. However, they cannot be
directly applied to systems that have constraints among test parameters. Such
constraints are prevalent in real-world systems.
Objectives: This paper proposes Constrained Detecting Arrays (CDAs), an
extension of detecting arrays, which can be used for systems with constraints.
Methods: The paper examines the properties and capabilities of CDAs with
rigorous arguments. The paper also proposes two algorithms for constructing
CDAs: One is aimed at generating minimum CDAs and the other is a heuristic
algorithm aimed at fast generation of CDAs. The algorithms are evaluated
through experiments using a benchmark dataset.
Results: Experimental results show that the first algorithm can generate
minimum CDAs if a sufficiently long generation time is allowed, and the second
algorithm can generate minimum or near-minimum CDAs in a reasonable time.
Conclusion: CDAs enhance detecting arrays to be applied to systems with
constraints. The two proposed algorithms have different advantages with
respect to the array size and generation time.

###### keywords:

Combinatorial interaction testing Detecting arrays Constraint handling Fault
Identification

##  1 Introduction

_Combinatorial Interaction Testing (CIT)_ is a testing approach that aims to
exercise interactions among test parameters. The basic strategy of CIT is to
test all interactions among a specified number (usually a small integer such
as 2 or 3) of parameters. Empirical results suggest that it is sufficient to
only test those interactions involving a small number of parameters to reveal
most of the latent faults [1, 2]. Using CIT can cut off testing cost
significantly when compared to exhaustive testing. The test suites used in CIT
are usually modeled as _arrays_ where each row represents a test case and each
column corresponds to each test parameter. The most typical class of arrays
used for CIT is $t$-way Covering Arrays ($t$-CAs). In a $t$-CA every
interaction involving $t$ parameters appears in at least one test case; thus
the use of a $t$-CA ensures exercising all $t$-way interactions.

There are many directions to expand the capability of CIT. One of the
directions is to add fault localization capability to test suites.
$(d,t)$-Locating Arrays (LAs) and $(d,t)$-Detecting Arrays (DAs) proposed in
[3] represent test suites that can not only detect but also identify faulty
interactions. The integers $d$ and $t$ are predefined parameters: $d$
represents the number of faulty interactions that can be identified and $t$
represents the number of parameters involved in the faulty interactions. LAs
and DAs add this capability to CAs at the cost of an increased number of test
cases.

Another direction of expanding CIT is to incorporate constraints. Real-world
systems usually have constraints on the input space. These constraints are
originated from, for example, user-defined requirements or running environment
restrictions. In order to test systems with constraints correctly, proper
handling of the constraints is necessary. For example, all test cases must
satisfy the constraints. In addition, constraints may make some interactions
no longer testable. These _invalid_ interactions require additional handling.
_Constrained Covering Arrays (CCAs)_ are an extension of CAs in which such
constraints are incorporated into the definition. Many previous studies on CIT
have tackled the problem of generating CCAs of small sizes [4, 5, 6].

In [7] we proposed the concept of _Constrained Locating Arrays (CLAs)_ which
extends LAs by incorporating constraints. CLAs inherit basic properties of LAs
and at the same time can be used as test suites for systems that have
constraints on the input space. In this paper, we further develop this line of
research: We propose a new mathematical structure called Constrained Detecting
Arrays (CDAs). As the name suggests, CDAs extend DAs by incorporating
constraints. Compared to LAs, DAs allow more accurate localization of faulty
interactions. Specifically, DAs prevent faulty interactions from being
erroneously identified as non-faulty, even when there are more faulty
interactions than assumed. CDAs extend DAs to adapt to constraints while
inheriting the good property of DAs.

The remainder of the paper is organized as follows. In Section 2 we explain
CAs, LAs, and DAs, and then describe CCAs and CLAs with examples. In Section 3
we introduce the notion of CDAs. We also provide some basic properties of
CDAs. In Section 4 we propose two algorithms for constructing CDAs: One
leverages a solver for satisfiability problems and the other is a fast
heuristic algorithm. The results of experiments using these algorithms are
shown in Section 5. In Section 6 we discuss threats to validity. In Section 7
we summarize related work. Finally, we conclude this paper in Section 8.

##  2 Preliminaries

###  2.1 SUT models and basic notions of CIT

A System Under Test (SUT) is modeled as a 3-tuple
$\mathcal{M}=\\{\mathcal{F},\mathcal{S},\phi\\}$.
$\mathcal{F}=\\{F_{1},F_{2},\dots,F_{k}\\}$ is a set of parameters in the
system where $k$ is the total number of these parameters.
$\mathcal{S}=\\{S_{1},S_{2},\dots,S_{k}\\}$ is a set of domains for all the
parameters in $\mathcal{F}$, where $S_{i}$ is the domain for the parameter
$F_{i}$. Each domain $S_{i}$ consists of two or more integers ranging from 0
to $|S_{i}|-1$, i.e., $S_{i}=\\{0,1,\dots,|S_{i}|-1\\}$. Different values of
$S_{i}$ represent different values for the parameter $F_{i}$.
$\phi:S_{1}\times S_{2}\times\dots\times S_{k}\rightarrow\\{true,false\\}$ is
a mapping representing the system constraints. We assume that
$\phi(\sigma)=true$ for some $\sigma$.

Table 1: SUT: an online shopping mobile application [8] $\mathcal{F}$ |  $F_{1}$ (Total Price) |  $F_{2}$ (Shipping Address) |  $F_{3}$ (Shipping Method) |  $F_{4}$ (Payment Method)
---|---|---|---|---
$\mathcal{S}$ | 0: $50 | 0: Domestic | 0: Same-Day Delivery | 0: Visa
1: $500 | 1: International | 1: 2-Day Delivery | 1: Mastercard
2: $1000 | – – | 2: 7-Day Delivery | 2: Paypal
– – | – – | – – | 3: Gift Card
$\phi$ | $\phi_{1}:\textrm{Shipping Address}=\textit{International}\Rightarrow\textrm{Shipping Method}\neq\textit{Same-Day Delivery}$
$\phi_{2}:\textrm{Payment}=\textit{Gift Card}\Rightarrow\textrm{Shipping
Address}=\textit{Domestic}\land\textrm{Shipping Method}=\textit{Same-Day
Delivery}$

A _test case_ is an element of $S_{1}\times S_{2}\times\dots\times S_{k}$;
that is, a test case is a $k$-tuple
$\langle\sigma_{1},\dots,\sigma_{i},\dots,\sigma_{k}\rangle$ such that
$\sigma_{i}\in S_{i}$. A _test suite_ is a set of test cases. We view a test
suite as an $N\times k$ _array_ where each row represents a test case and $N$
is the number of test cases. The _size_ of a test suite (i.e., array) is the
number of test cases (rows) in it.

An _interaction_ is a set of parameter-value pairs such that no parameters are
overlapped. The _strength_ of an interaction is the number of parameter-value
pairs in the interaction. That is,
$\\{(F_{i_{1}},\sigma_{1}),\dots,(F_{i_{t}},\sigma_{t})\\}$ is an interaction
of strength $t$ if and only if (iff) $F_{i_{j}}\neq F_{i_{k}}$ for any
$i_{j},i_{k}\ (i_{j}\neq i_{k})$ and $\sigma_{j}\in S_{i_{j}}$ for all
$i_{j}\in\\{i_{1},\dots,i_{t}\\}$. We let $\curlywedge$, instead of
$\emptyset$, denote the interaction of strength 0 which is an empty set. We
say that an interaction is $t$-way iff the strength is $t$.

An interaction $T_{1}$ _covers_ another interaction $T_{2}$ iff
$T_{2}\subseteq T_{1}$. We say that a set $\mathcal{T}$ of interactions are
_independent_ iff $T_{1}\not\subseteq T_{2}$ for any
$T_{1},T_{2}\in\mathcal{T},T_{1}\neq T_{2}$.

We also say that a test case covers an interaction iff the value matches
between the test case and the interaction on every parameter involved in the
interaction. Formally,
$\boldsymbol{\sigma}=\langle\sigma_{1},\dots,\sigma_{i},\dots,\sigma_{k}\rangle$
covers an interaction
$T=\\{(F_{i_{1}},\sigma^{\prime}_{1}),\dots,(F_{i_{t}},\sigma^{\prime}_{t})\\}$
iff $\sigma_{i_{j}}=\sigma^{\prime}_{j}$ for all
$j\in\\{i_{1},\dots,i_{t}\\}$. Given an array (i.e., test suite) $A$, we
express the set of rows (i.e., test cases) that cover the interaction $T$ as
$\rho_{A}(T)$. Also we let
$\rho_{A}(\mathcal{T})=\bigcup_{T\in\mathcal{T}}\rho_{A}(T)$. In words,
$\rho_{A}(\mathcal{T})$ is the set of rows that cover at least one interaction
in $\mathcal{T}$. Note that $\rho_{A}(\emptyset)=\emptyset$ and
$\rho_{A}(\curlywedge)=A$.

A test case $\boldsymbol{\sigma}$ is valid iff it satisfies the constraints
$\phi$, i.e., $\phi(\boldsymbol{\sigma})=true$; otherwise, invalid. The set of
all valid test cases is denoted as $\mathcal{R}\ (\subseteq S_{1}\times
S_{2}\times\dots\times S_{k})$. Hence $\mathcal{R}$ is also regarded as the
_exhaustive test suite_ which consists of all valid test cases.

The valid/invalid distinction also applies to interactions: Interactions that
no valid test cases can cover are invalid; the other interactions, i.e., those
that are covered by at least one valid test case are valid. We let
$\mathcal{I}_{t}$ and $\mathcal{VI}_{t}$ denote the set of all $t$-way
interactions and the set of all valid $t$-way interactions, respectively.
Similarly we let $\overline{\mathcal{I}_{t}}$ and
$\overline{\mathcal{VI}_{t}}$ be the set of all interactions of strength at
most $t$ and the set of all valid interactions of strength at most $t$.

A valid interaction is either _faulty_ or _non-faulty_. The outcome of
execution of a valid test case is either Pass or Fail. The outcome is Fail iff
the test case covers at least one faulty interaction; the outcome is Pass
otherwise. The test outcome of an array is the collection of the outcomes of
all rows.

Table 1 shows an SUT model which represents an online shopping mobile
application. This example, which is a modification of one in [8], serves as a
running example throughout the paper. This model is formally represented as
$\mathcal{M}=\\{\mathcal{F},\mathcal{S},\phi\\}$ where
$\mathcal{F}=\\{F_{1},F_{2},F_{3},F_{4}\\}$,
$\mathcal{S}=\\{S_{1},S_{2},S_{3},S_{4}\\}$, $S_{1}=S_{3}=\\{0,1,2\\}$,
$S_{2}=\\{0,1\\}$, $S_{4}=\\{0,1,2,3\\}$ and
$\phi=\phi_{1}\land\phi_{2}=(F_{2}=1\Rightarrow F_{3}\neq
0)\land(F_{4}=3\Rightarrow(F_{2}=0\land F_{3}=0))$. An example of a valid test
case is $\langle 0,0,0,0\rangle$, representing $\langle$$50, Domestic, Same-
Day Delivery, Visa$\rangle$. On the other hand, $\langle 0,1,0,0\rangle$
(i.e., $\langle$$50, International, Same-Day Delivery, Visa$\rangle$) is an
invalid test case. Invalid interactions include, for example,
$\\{(F_{2},1),(F_{3},0)\\}$, $\\{(F_{2},1),(F_{4},3)\\}$, etc.

###  2.2 Covering arrays, locating arrays, and detecting arrays

Covering arrays (CAs), locating arrays (LAs), and detecting arrays (DAs) are
mathematical structures that can be implemented as test suites. They are
usually used to detect or locate faulty interactions for unconstrained SUTs
(i.e., $\phi=\textit{true}$).

A $t$-way covering array, $t$-CA for short, is defined as follows:

$t\textrm{-CA}\qquad\forall T\in\mathcal{I}_{t}:\rho_{A}(T)\neq\emptyset$

The condition requires that all interactions $T$ in $\mathcal{I}_{t}$ be
covered by at least one row in the array. In other words, when the test cases
in $A$ are executed, all $t$-way interactions are examined or executed at
least once. This condition is sufficient to reveal the existence of a $t$-way
faulty interaction; but it is generally not possible to identify the faulty
interaction from the test outcome. Figure 1 shows a 2-CA for the running
example.

On the other hand, LAs and DAs can be used to not only detect the existence of
faulty interactions but also locate them. LAs and DAs were first proposed by
Colbourn and McClary in [3]. They introduced a total of six types for both LAs
and DAs according to fault locating capability. Two types of them exist only
in extreme cases. The rest four types, namely, $(d,t)$-, $(\overline{d},t)$-,
$(d,\overline{t})$-, $(\overline{d},\overline{t})$-LA (and DA), are as follows
($d\geq 0$, $0\leq t\leq k$).

$\displaystyle(d,t)\textrm{-LA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{I}_{t}\textrm{
such that }|\mathcal{T}_{1}|=|\mathcal{T}_{2}|=d:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})=\rho_{A}(\mathcal{T}_{2})\Leftrightarrow\mathcal{T}_{1}=\mathcal{T}_{2}$
$\displaystyle(\overline{d},t)\textrm{-LA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{I}_{t}\textrm{
such that }0\leq|\mathcal{T}_{1}|\leq d,0\leq|\mathcal{T}_{2}|\leq d:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})=\rho_{A}(\mathcal{T}_{2})\Leftrightarrow\mathcal{T}_{1}=\mathcal{T}_{2}$

$\displaystyle(d,\overline{t})\textrm{-LA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\overline{\mathcal{I}_{t}}\textrm{
such that }|\mathcal{T}_{1}|=|\mathcal{T}_{2}|=d\textrm{ and
}\mathcal{T}_{1},\mathcal{T}_{2}\textrm{ are independent}:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})=\rho_{A}(\mathcal{T}_{2})\Leftrightarrow\mathcal{T}_{1}=\mathcal{T}_{2}$
$\displaystyle(\overline{d},\overline{t})\textrm{-LA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\overline{\mathcal{I}_{t}}\textrm{
such that }0\leq|\mathcal{T}_{1}|\leq d,0\leq|\mathcal{T}_{2}|\leq d\textrm{
and }\mathcal{T}_{1},\mathcal{T}_{2}\textrm{ are independent}:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})=\rho_{A}(\mathcal{T}_{2})\Leftrightarrow\mathcal{T}_{1}=\mathcal{T}_{2}$

$\displaystyle(d,t)\textrm{-DA}$
$\displaystyle\forall\mathcal{T}\subseteq\mathcal{I}_{t}\textrm{ such that
}|\mathcal{T}|=d,\forall T\in\mathcal{I}_{t}:$
$\displaystyle\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})\Leftrightarrow
T\in\mathcal{T}$ $\displaystyle(\overline{d},t)\textrm{-DA}$
$\displaystyle\forall\mathcal{T}\subseteq\mathcal{I}_{t}\textrm{ such that
}0\leq|\mathcal{T}|\leq d,\forall T\in\mathcal{I}_{t}:$
$\displaystyle\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})\Leftrightarrow
T\in\mathcal{T}$

$\displaystyle(d,\overline{t})\textrm{-DA}$
$\displaystyle\forall\mathcal{T}\subseteq\overline{\mathcal{I}_{t}}\textrm{
such that }|\mathcal{T}|=d,\forall T\in\overline{\mathcal{I}_{t}}\textrm{ and
}\mathcal{T}\cup\\{T\\}\textrm{ is independent}:$
$\displaystyle\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})\Leftrightarrow
T\in\mathcal{T}$ $\displaystyle(\overline{d},\overline{t})\textrm{-DA}$
$\displaystyle\forall\mathcal{T}\subseteq\overline{\mathcal{I}_{t}}\textrm{
such that }0\leq|\mathcal{T}|\leq d,\forall
T\in\overline{\mathcal{I}_{t}}\textrm{ and }\mathcal{T}\cup\\{T\\}\textrm{ is
independent}:$
$\displaystyle\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})\Leftrightarrow
T\in\mathcal{T}$

The parameter $d$ of these arrays stands for the number of faulty interactions
that the array can correctly locate, while $t$ represents the strength of the
target interactions. Writing $\overline{d}$ or $\overline{t}$ in place of $d$
or $t$ means that the array permits at most of $d$ faulty interactions or
strength at most $t$. For example, a $(1,2)$-LA (or DA) can locate one 2-way
faulty interaction, while a $(\overline{2},\overline{2})$-LA (or DA) can
locate at most two faulty interactions that have strength not greater than 2.
The reason why when dealing with $\overline{\mathcal{I}_{t}}$ it is required
that $\mathcal{T}_{1},\mathcal{T}_{2}$ or $\mathcal{T}\cup\\{T\\}$ be
independent is that if there are $T_{1},T_{2}\in\overline{\mathcal{I}_{t}}$
such that $T_{1}\subset T_{2}$, whether $T_{2}$ is faulty or not cannot be
determined when $T_{1}$ is faulty. Figure 1 and Figure 1 show a $(1,2)$-LA and
a $(1,2)$-DA for the running SUT.

In [3] it is proved that a $(d,t)$-DA is a $(d,t)$-LA and a
$(\overline{d},t)$-LA and that a $(\overline{d},t)$-LA is a $(d-1,t)$-DA
(Lemma 7.1). It is also proved that a $(d,t)$-DA is equivalent to a
$(\overline{d},t)$-DA and that a $(d,\overline{t})$-DA is equivalent to a
$(\overline{d},\overline{t})$-DA (Lemma 7.2). We will later provide theorems
for CDAs, namely Theorems 3.7 and 3.10, that are parallel to these lemmas.

Figure 1: CA, LA, and DA for the running example (constraint ignored)

(a) $2$-CA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 2 | 2
$\boldsymbol{\sigma}_{3}$ | 0 | 1 | 0 | 3
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 1 | 1
$\boldsymbol{\sigma}_{5}$ | 1 | 0 | 0 | 1
$\boldsymbol{\sigma}_{6}$ | 1 | 0 | 2 | 3
$\boldsymbol{\sigma}_{7}$ | 1 | 1 | 0 | 2
$\boldsymbol{\sigma}_{8}$ | 1 | 1 | 1 | 0
$\boldsymbol{\sigma}_{9}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{10}$ | 2 | 0 | 1 | 2
$\boldsymbol{\sigma}_{11}$ | 2 | 0 | 2 | 0
$\boldsymbol{\sigma}_{12}$ | 2 | 1 | 1 | 3
$\boldsymbol{\sigma}_{13}$ | 2 | 1 | 2 | 1

(b) (1,2)-LA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 1 | 1
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 1 | 2
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 0 | 3
$\boldsymbol{\sigma}_{5}$ | 0 | 1 | 2 | 0
$\boldsymbol{\sigma}_{6}$ | 0 | 1 | 2 | 2
$\boldsymbol{\sigma}_{7}$ | 1 | 0 | 0 | 1
$\boldsymbol{\sigma}_{8}$ | 1 | 0 | 1 | 0
$\boldsymbol{\sigma}_{9}$ | 1 | 0 | 2 | 1
$\boldsymbol{\sigma}_{10}$ | 1 | 1 | 0 | 0
$\boldsymbol{\sigma}_{11}$ | 1 | 1 | 0 | 2
$\boldsymbol{\sigma}_{12}$ | 1 | 1 | 1 | 1
$\boldsymbol{\sigma}_{13}$ | 1 | 1 | 2 | 3
$\boldsymbol{\sigma}_{14}$ | 2 | 0 | 0 | 2
$\boldsymbol{\sigma}_{15}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{16}$ | 2 | 0 | 1 | 1
$\boldsymbol{\sigma}_{17}$ | 2 | 0 | 2 | 3
$\boldsymbol{\sigma}_{18}$ | 2 | 1 | 0 | 0
$\boldsymbol{\sigma}_{19}$ | 2 | 1 | 1 | 3

(c) (1,2)-DA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 2
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 1 | 1
$\boldsymbol{\sigma}_{4}$ | 0 | 0 | 2 | 3
$\boldsymbol{\sigma}_{5}$ | 0 | 1 | 0 | 1
$\boldsymbol{\sigma}_{6}$ | 0 | 1 | 1 | 3
$\boldsymbol{\sigma}_{7}$ | 0 | 1 | 2 | 0
$\boldsymbol{\sigma}_{8}$ | 0 | 1 | 2 | 2
$\boldsymbol{\sigma}_{9}$ | 1 | 0 | 0 | 1
$\boldsymbol{\sigma}_{10}$ | 1 | 0 | 1 | 3
$\boldsymbol{\sigma}_{11}$ | 1 | 0 | 2 | 0
$\boldsymbol{\sigma}_{12}$ | 1 | 0 | 2 | 2
$\boldsymbol{\sigma}_{13}$ | 1 | 1 | 0 | 3
$\boldsymbol{\sigma}_{14}$ | 1 | 1 | 1 | 0
$\boldsymbol{\sigma}_{15}$ | 1 | 1 | 1 | 2
$\boldsymbol{\sigma}_{16}$ | 1 | 1 | 2 | 1
$\boldsymbol{\sigma}_{17}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{18}$ | 2 | 0 | 1 | 0
$\boldsymbol{\sigma}_{19}$ | 2 | 0 | 1 | 2
$\boldsymbol{\sigma}_{20}$ | 2 | 0 | 2 | 1
$\boldsymbol{\sigma}_{21}$ | 2 | 1 | 0 | 0
$\boldsymbol{\sigma}_{22}$ | 2 | 1 | 0 | 2
$\boldsymbol{\sigma}_{23}$ | 2 | 1 | 1 | 1
$\boldsymbol{\sigma}_{24}$ | 2 | 1 | 2 | 3

How to identify faulty interactions using these arrays is the same as their
constrained versions, namely, CLAs and CDAs.

###  2.3 Constrained versions of covering arrays and locating arrays

CAs, LAs, and DAs do not take constraints into account. However real-world
systems usually have complicated constraints that must be satisfied by all
test cases.

####  2.3.1 Constrained covering arrays

Constrained Covering Arrays (CCAs) are the constrained version of CAs. CCAs
are the most common form of test suites used in CIT: Most of test generation
tools for CIT are in effect generators of CCAs.

######  Definition 2.1 (CCA).

An array $A$ that consists of valid test cases is a $t$-CCA iff the following
condition holds.

$t\textrm{-CCA}\qquad\forall T\in\mathcal{VI}_{t}:\rho_{A}(T)\neq\emptyset$

The definition of CCAs requires that all valid $t$-way interactions be covered
by at least one test case in the test suite. This condition implies that every
valid interaction of strength $<t$ is covered by at least one test case. That
is, a $t$-CCA is also a $(t-1)$-CCA when $t>0$. Thus, a $t$-CCA can also be
defined as follows.

$t\textrm{-CCA}\qquad\forall
T\in\overline{\mathcal{VI}_{t}}:\rho_{A}(T)\neq\emptyset$

Figure 2 shows a 2-CCA for the running example. All four invalid 2-way
interactions which violate the constraints are listed as follows.

$\displaystyle\\{(F_{2},1),(F_{3},0)\\}\qquad\\{(F_{2},1),(F_{4},3)\\}$
$\displaystyle\\{(F_{3},2),(F_{4},3)\\}\qquad\\{(F_{3},1),(F_{4},3)\\}$

It is easy to observe that none of the invalid interactions appears in any
rows in Figure 2.

Figure 2: CCA and CLA for the running example

(a) $2$-CCA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 3
$\boldsymbol{\sigma}_{3}$ | 0 | 1 | 1 | 1
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 2 | 2
$\boldsymbol{\sigma}_{5}$ | 1 | 0 | 0 | 2
$\boldsymbol{\sigma}_{6}$ | 1 | 0 | 0 | 3
$\boldsymbol{\sigma}_{7}$ | 1 | 0 | 2 | 1
$\boldsymbol{\sigma}_{8}$ | 1 | 1 | 1 | 0
$\boldsymbol{\sigma}_{9}$ | 2 | 0 | 0 | 1
$\boldsymbol{\sigma}_{10}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{11}$ | 2 | 0 | 1 | 2
$\boldsymbol{\sigma}_{12}$ | 2 | 1 | 2 | 0

(b) (1,2)-CLA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 3
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 1 | 1
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 1 | 2
$\boldsymbol{\sigma}_{5}$ | 0 | 1 | 2 | 0
$\boldsymbol{\sigma}_{6}$ | 1 | 0 | 0 | 2
$\boldsymbol{\sigma}_{7}$ | 1 | 0 | 0 | 3
$\boldsymbol{\sigma}_{8}$ | 1 | 0 | 1 | 2
$\boldsymbol{\sigma}_{9}$ | 1 | 1 | 1 | 1
$\boldsymbol{\sigma}_{10}$ | 1 | 1 | 2 | 0
$\boldsymbol{\sigma}_{11}$ | 1 | 1 | 2 | 2
$\boldsymbol{\sigma}_{12}$ | 2 | 0 | 0 | 1
$\boldsymbol{\sigma}_{13}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{14}$ | 2 | 0 | 2 | 0
$\boldsymbol{\sigma}_{15}$ | 2 | 1 | 1 | 0
$\boldsymbol{\sigma}_{16}$ | 2 | 1 | 1 | 2
$\boldsymbol{\sigma}_{17}$ | 2 | 1 | 2 | 1

####  2.3.2 Constrained locating arrays

LAs allow us to identify the set of faulty interactions using the test
outcome. This becomes possible because for any LA $A$, $\rho_{A}(\cdot)$
injectively maps an interaction set to a test outcome (i.e.,
$\rho_{A}(\mathcal{T}_{1})=\rho_{A}(\mathcal{T}_{2})\Rightarrow\mathcal{T}_{1}=\mathcal{T}_{2}$).
Since a test outcome corresponds to at most one interaction set, the set of
faulty interactions can be uniquely inferred from the test outcome.

When incorporating constraints into LAs, it is necessary to handle the
situation where constraints may prevent some sets of faulty interactions from
being identified. For the running example, when either one of the two
interaction sets shown below is faulty, it is impossible to determine which is
indeed faulty.

$\mathcal{T}_{1}=\\{\\{(F_{2},0),(F_{4},3)\\}\\}\quad\mathcal{T}_{2}=\\{\\{(F_{3},0),(F_{4},3)\\}\\}$

This is because the two interactions always appear simultaneously in any valid
test case and thus no valid test case exists that yields different outcomes
for the two faulty interaction sets. We say that two sets of valid
interactions, $\mathcal{T}$ and $\mathcal{T}^{\prime}$, are not
_distinguishable_ or _indistinguishable_ iff
$\rho_{A}(\mathcal{T})=\rho_{A}(\mathcal{T}^{\prime})$ for any array $A$ that
consists of valid tests.

This situation is formally captured by the notion which we call
distinguishability.

######  Definition 2.2 (Distinguishability).

Two sets of valid interactions, $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$, are
distinguishable iff $\rho_{A}(\mathcal{T}_{1})\neq\rho_{A}(\mathcal{T}_{2})$
for some array $A$ consisting of valid tests; otherwise they are
_indistinguishable_.

If $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ are indistinguishable, we write
$\mathcal{T}_{1}\sim\mathcal{T}_{2}$; otherwise, we write
$\mathcal{T}_{1}\not\sim\mathcal{T}_{2}$. For the running example, the pair of
interaction sets shown below are indistinguishable.

$\mathcal{T}_{1}=\\{\\{(F_{2},0),(F_{4},3)\\}\\}\sim\mathcal{T}_{2}=\\{\\{(F_{3},0),(F_{4},3)\\}\\}$

It is not difficult to see that the pair of indistinguishable interaction sets
is caused by the constraint $\phi_{2}$.

The definition of CLAs adapts LAs to the presence of indistinguishable
interaction sets by exempting them from fault identification.

######  Definition 2.3 (CLA).

Let $d\geq 0$ and $0\leq t\leq k$. An array $A$ that consists of valid tests
is a $(d,t)$-, $(\overline{d},t)$-, $(d,\overline{t})$\- or
$(\overline{d},\overline{t})$-CLA iff the corresponding condition shown below
holds.

$\displaystyle(d,t)\textrm{-CLA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{VI}_{t}\textrm{
such that }|\mathcal{T}_{1}|=|\mathcal{T}_{2}|=d\textrm{ and
}\mathcal{T}_{1},\mathcal{T}_{2}\textrm{ are distinguishable}:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})\neq\rho_{A}(\mathcal{T}_{2})$
$\displaystyle(\overline{d},t)\textrm{-CLA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{VI}_{t}\textrm{
such that }0\leq|\mathcal{T}_{1}|\leq d,0\leq|\mathcal{T}_{2}|\leq d\textrm{
and }\mathcal{T}_{1},\mathcal{T}_{2}\textrm{ are distinguishable}:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})\neq\rho_{A}(\mathcal{T}_{2})$
$\displaystyle(d,\overline{t})\textrm{-CLA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\overline{\mathcal{VI}_{t}}\textrm{
such that }|\mathcal{T}_{1}|=|\mathcal{T}_{2}|=d\textrm{ and
}\mathcal{T}_{1},\mathcal{T}_{2}\textrm{ are independent and
distinguishable}:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})\neq\rho_{A}(\mathcal{T}_{2})$
$\displaystyle(\overline{d},\overline{t})\textrm{-CLA}$
$\displaystyle\forall\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\overline{\mathcal{VI}_{t}}\textrm{
such that }0\leq|\mathcal{T}_{1}|\leq d,0\leq|\mathcal{T}_{2}|\leq d\textrm{
and }\mathcal{T}_{1},\mathcal{T}_{2}\textrm{ are independent and
distinguishable}:$
$\displaystyle\rho_{A}(\mathcal{T}_{1})\neq\rho_{A}(\mathcal{T}_{2})$

A (1,2)-CLA for the running example is shown in Figure 2. From the array, one
can see that none of the invalid interactions shown above appears in any rows
of the CLA. In addition, for any pair of 2-way interactions except the above
indistinguishable pair, the rows that cover one of them are different from
those that cover the other. The exception is the rows where the
indistinguishable pair of interaction sets appear, namely
$\boldsymbol{\sigma}_{2}$, $\boldsymbol{\sigma}_{7}$ and
$\boldsymbol{\sigma}_{13}$. This occurs because of the second constraint
$\phi_{2}$ in the SUT. $\phi_{2}$ enforces all test cases that have
$(F_{4},3)$ to contain $(F_{2},0)$ and $(F_{3},0)$ at the same time. Thus, the
interaction sets $\mathcal{T}_{1}=\\{\\{(F_{2},0),(F_{4},3)\\}\\}$ and
$\mathcal{T}_{2}=\\{\\{(F_{3},0),(F_{4},3)\\}\\}$ appear in the same test
cases as long as the test cases are valid.

##  3 Constrained Detecting Arrays

In this section, we propose Constrained Detecting Arrays (CDAs). First we
present the definition of CDAs; then we show how one can identify faulty
interactions with CDAs. In addition, we provide some theorems that relate CDAs
to CCAs and CLAs.

###  3.1 Definition

For an array $A$ to be a DA, $A$ must satisfy
$\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})\Leftrightarrow T\in\mathcal{T}$ for
any pair of an interaction $T$ and an interaction set $\mathcal{T}$. However,
this may be impossible if $A$ consists only of valid test cases. Here we
introduce the concept of _masking_ to capture such a situation.

######  Definition 3.4 (Masking).

A set $\mathcal{T}$ of valid interactions _masks_ a valid interaction $T$ iff
$T\not\in\mathcal{T}$ and

$\forall\boldsymbol{\sigma}\in\mathcal{R}:T\subseteq\boldsymbol{\sigma}\Rightarrow(\exists
T^{\prime}\in\mathcal{T}:T^{\prime}\subseteq\boldsymbol{\sigma}).$

If $\mathcal{T}$ masks $T$, we write $\mathcal{T}\succ T$; otherwise we write
$\mathcal{T}\not\succ T$. By definition, $\mathcal{T}\not\succ T$ iff
$T\in\mathcal{T}$ or

$\exists\boldsymbol{\sigma}\in\mathcal{R}:T\subseteq\sigma\land(\forall
T^{\prime}\in\mathcal{T}:T^{\prime}\not\subseteq\sigma).$

In words, when $\mathcal{T}$ masks $T$, $T$ always appears together with some
interaction $T^{\prime}$ in $\mathcal{T}$ in any valid test case $\sigma$. In
this case, $T\not\in\mathcal{T}$ but
$\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$ always holds for any $A$ that
meets the constraints. In the running example, such $T$-$\mathcal{T}$ pairs
include:

$\displaystyle\mathcal{T}_{1}=\\{\\{(F_{1},0),(F_{2},0)\\}\\}\succ
T_{a}=\\{(F_{1},0),(F_{3},0)\\}\qquad\mathcal{T}_{1}=\\{\\{(F_{1},0),(F_{2},0)\\}\\}\succ
T_{b}=\\{(F_{1},0),(F_{4},3)\\}$
$\displaystyle\mathcal{T}_{2}=\\{\\{(F_{1},1),(F_{2},0)\\}\\}\succ
T_{c}=\\{(F_{1},1),(F_{3},0)\\}\qquad\mathcal{T}_{3}=\\{\\{(F_{2},0),(F_{3},0)\\}\\}\succ
T_{b}=\\{(F_{1},0),(F_{4},3)\\}$
$\displaystyle\mathcal{T}_{4}=\\{\\{(F_{3},0),(F_{4},3)\\}\\}\succ
T_{d}=\\{(F_{1},2),(F_{4},3)\\}\qquad\mathcal{T}_{4}=\\{\\{(F_{3},0),(F_{4},3)\\}\\}\succ
T_{e}=\\{(F_{2},0),(F_{4},3)\\}$ $\displaystyle\dots\dots(\textrm{31 pairs in
total})$

When $\mathcal{T}$ masks $T$, the failure caused by $T$ cannot be inherently
distinguished from that caused by $\mathcal{T}$. The idea at the core of CDAs
is to relax the condition of DAs by exempting $T$-$\mathcal{T}$ pairs such
that $\mathcal{T}\succ T$ from fault identification.

######  Definition 3.5 (CDA).

Let $d\geq 0$ and $0\leq t\leq k$. An array $A$ that consists of valid test
cases or no rows is a $(d,t)$-, $(\overline{d},t)$-, $(d,\overline{t})$\- or
$(\overline{d},\overline{t})$-CDA iff the corresponding condition shown below
holds.

$\displaystyle(d,t)\textrm{-CDA}$
$\displaystyle\forall\mathcal{T}\subseteq\mathcal{VI}_{t}\textrm{ such that
}|\mathcal{T}|=d,\forall T\in\mathcal{VI}_{t}:$
$\displaystyle\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
$\displaystyle(\overline{d},t)\textrm{-CDA}$
$\displaystyle\forall\mathcal{T}\subseteq\mathcal{VI}_{t}\textrm{ such that
}0\leq|\mathcal{T}|\leq d,\forall T\in\mathcal{VI}_{t}:$
$\displaystyle\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
$\displaystyle(d,\overline{t})\textrm{-CDA}$
$\displaystyle\forall\mathcal{T}\subseteq\overline{\mathcal{VI}_{t}}\textrm{
such that }|\mathcal{T}|=d,\forall T\in\overline{\mathcal{VI}_{t}}\textrm{ and
}\mathcal{T}\cup\\{T\\}\textrm{ is independent}:$
$\displaystyle\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
$\displaystyle(\overline{d},\overline{t})\textrm{-CDA}$
$\displaystyle\forall\mathcal{T}\subseteq\overline{\mathcal{VI}_{t}}\textrm{
such that }0\leq|\mathcal{T}|\leq d,\forall
T\in\overline{\mathcal{VI}_{t}}\textrm{ and }\mathcal{T}\cup\\{T\\}\textrm{ is
independent}:$ $\displaystyle\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$

Figure 3, Figure 3, and Figure 3 respectively show a (1,1)-CDA, a (2,1)-CDA,
and a (1,2)-CDA for the running example. Now let us take the (1,2)-CDA in
Figure 3 and the pair of $\mathcal{T}_{3}=\\{\\{(F_{2},0),(F_{3},0)\\}\\}$ and
$T_{b}=\\{(F_{1},0),(F_{4},3)\\}$ as examples. Let $A$ denote the (1,2)-CDA
for now; then $\rho_{A}(\mathcal{T}_{3})=\\{\boldsymbol{\sigma}_{1}$,
$\boldsymbol{\sigma}_{2}$, $\boldsymbol{\sigma}_{3}$,
$\boldsymbol{\sigma}_{9}$, $\boldsymbol{\sigma}_{10}$,
$\boldsymbol{\sigma}_{16}$, $\boldsymbol{\sigma}_{17}$,
$\boldsymbol{\sigma}_{18}$, $\boldsymbol{\sigma}_{19}\\}$, whereas
$\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{3}\\}$. Hence,
$T_{b}\in\mathcal{T}_{3}\Leftrightarrow\rho_{A}(T_{b})\subseteq\rho_{A}(\mathcal{T}_{3})$
does not hold. This is prohibited by the definition of DAs but is allowed by
CDAs, because $\mathcal{T}_{3}\succ T_{b}$, which means that no array can
satisfy it unless the constraints are violated.

Figure 3: CDAs for the running example

(a) (1,1)-CDA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 1 | 2 | 1
$\boldsymbol{\sigma}_{3}$ | 1 | 0 | 0 | 3
$\boldsymbol{\sigma}_{4}$ | 1 | 0 | 1 | 1
$\boldsymbol{\sigma}_{5}$ | 1 | 1 | 1 | 2
$\boldsymbol{\sigma}_{6}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{7}$ | 2 | 0 | 2 | 2
$\boldsymbol{\sigma}_{8}$ | 2 | 1 | 1 | 0

(b) (2,1)-CDA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 3
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 2 | 1
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 1 | 2
$\boldsymbol{\sigma}_{5}$ | 0 | 1 | 2 | 0
$\boldsymbol{\sigma}_{6}$ | 1 | 0 | 1 | 1
$\boldsymbol{\sigma}_{7}$ | 1 | 0 | 0 | 1
$\boldsymbol{\sigma}_{8}$ | 1 | 0 | 0 | 2
$\boldsymbol{\sigma}_{9}$ | 1 | 0 | 0 | 3
$\boldsymbol{\sigma}_{10}$ | 1 | 1 | 1 | 0
$\boldsymbol{\sigma}_{11}$ | 1 | 1 | 2 | 1
$\boldsymbol{\sigma}_{12}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{13}$ | 2 | 0 | 1 | 2
$\boldsymbol{\sigma}_{14}$ | 2 | 0 | 2 | 0
$\boldsymbol{\sigma}_{15}$ | 2 | 1 | 1 | 1
$\boldsymbol{\sigma}_{16}$ | 2 | 1 | 2 | 2

(c) (1,2)-CDA | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$
---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 1
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 0 | 3
$\boldsymbol{\sigma}_{4}$ | 0 | 0 | 1 | 1
$\boldsymbol{\sigma}_{5}$ | 0 | 0 | 2 | 2
$\boldsymbol{\sigma}_{6}$ | 0 | 1 | 1 | 2
$\boldsymbol{\sigma}_{7}$ | 0 | 1 | 2 | 0
$\boldsymbol{\sigma}_{8}$ | 0 | 1 | 2 | 1
$\boldsymbol{\sigma}_{9}$ | 1 | 0 | 0 | 2
$\boldsymbol{\sigma}_{10}$ | 1 | 0 | 0 | 3
$\boldsymbol{\sigma}_{11}$ | 1 | 0 | 1 | 0
$\boldsymbol{\sigma}_{12}$ | 1 | 0 | 2 | 1
$\boldsymbol{\sigma}_{13}$ | 1 | 1 | 1 | 1
$\boldsymbol{\sigma}_{14}$ | 1 | 1 | 2 | 0
$\boldsymbol{\sigma}_{15}$ | 1 | 1 | 2 | 2
$\boldsymbol{\sigma}_{16}$ | 2 | 0 | 0 | 0
$\boldsymbol{\sigma}_{17}$ | 2 | 0 | 0 | 1
$\boldsymbol{\sigma}_{18}$ | 2 | 0 | 0 | 2
$\boldsymbol{\sigma}_{19}$ | 2 | 0 | 0 | 3
$\boldsymbol{\sigma}_{20}$ | 2 | 0 | 1 | 2
$\boldsymbol{\sigma}_{21}$ | 2 | 0 | 2 | 0
$\boldsymbol{\sigma}_{22}$ | 2 | 1 | 1 | 0
$\boldsymbol{\sigma}_{23}$ | 2 | 1 | 1 | 1
$\boldsymbol{\sigma}_{24}$ | 2 | 1 | 2 | 2

By definition, it is straightforward to see that the following observations
hold.

###### Observation 1

A $(\overline{d},\overline{t})$-CDA is a $(\overline{d},t)$-CDA and a
$(d,\overline{t})$-CDA. A $(\overline{d},t)$-CDA and a $(d,\overline{t})$-CDA
are both a $(d,t)$-CDA. When $d>0$, a $(\overline{d},\overline{t})$-CDA and a
$(\overline{d},t)$-CDA are a $(\overline{d-1},\overline{t})$-CDA and a
$(\overline{d-1},t)$-CDA, respectively. When $t>0$, a
$(\overline{d},\overline{t})$-CDA and a $(d,\overline{t})$-CDA are a
$(\overline{d},\overline{t-1})$-CDA and a $(d,\overline{t-1})$-CDA,
respectively.

###### Observation 2

Suppose that the SUT has no constraints, i.e.,
$\phi(\boldsymbol{\sigma})=true$ for all
$\boldsymbol{\sigma}\in\mathcal{R}=V_{1}\times V_{2}\times\dots\times V_{k}$
and that a $(d,t)$-DA $A$ exists. Then $A$ is a $(d,t)$-CDA. This also applies
when $d$ or $t$ is replaced with $\overline{d}$ or $\overline{t}$,
respectively.

According to the above definition, if $|\mathcal{T}|$ is very large, then
$\rho_{A}(\mathcal{T})=A$ for any array $A$, in which case all interactions
are masked by $\mathcal{T}$. In order to avoid such cases of no practical
interest, here we introduce an upper bound, denoted $\tau_{t}$, on $d$. We let
$\tau_{t}\geq 0$ be the greatest integer that satisfies the condition as
follows:

$\forall\mathcal{T}\subseteq\mathcal{VI}_{t}\mathrm{~{}such~{}that~{}}|\mathcal{T}|\leq\tau_{t}:\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T})\neq\emptyset$

In words, given $\tau_{t}$ interactions of strength $t$, there is always a
test case in $\mathcal{R}$ in which none of the given interactions appears.
Note that $\tau_{0}=0$.

######  Theorem 3.6.

For $d\leq\tau_{t}$, a $(d,t)$-CDA is equivalent to a $(\overline{d},t)$-CDA.

Trivially a $(0,t)$-CDA is a $(\overline{0},t)$-CDA. Let $A$ be a $(d,t)$-CDA
such that $1\leq d\leq\tau_{t}$ and $t>0$. We will show that $A$ is a
$(d-1,t)$-CDA. Let $\mathcal{T}$ and $T$ be a set of $d-1$ valid interactions
of strength $t$ and a $t$-way valid interaction, respectively. If
$\mathcal{T}\succ T$ or $T\in\mathcal{T}$, then $\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
trivially holds. The rest of the proof considers the case where
$T\not\in\mathcal{T}$ and $\mathcal{T}\not\succ T$. In this case, there is
some $\sigma\in\mathcal{R}$ such that $T\subseteq\sigma$ and
$\sigma\not\in\rho_{\mathcal{R}}(\mathcal{T})$. Since
$|\mathcal{T}\cup\\{T\\}|\leq\tau_{t}$,
$\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T}\cup\\{T\\})$ is not empty. Let
$T^{\prime}$ be any $t$-way interaction that appears in a test case in
$\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T}\cup\\{T\\})$ and has exactly the
same $t$ parameters as $T$. Note that $T$ and $T^{\prime}$ cannot appear in
any test case simultaneously. Let
$\mathcal{T}^{\prime}=\mathcal{T}\cup\\{T^{\prime}\\}$.
$\mathcal{T}^{\prime}\not\succ T$ since $T\subseteq\sigma$,
$\sigma\not\in\rho_{\mathcal{R}}(\mathcal{T})$, and
$\sigma\not\in\rho_{\mathcal{R}}(T^{\prime})$. Because $A$ is a $(d,t)$-CDA
and $\mathcal{T}^{\prime}\not\succ T$,
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T}^{\prime})$. Hence
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$, which means
$\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$.
By induction, $A$ is a $(d^{\prime},t)$-CDA for any $0\leq d^{\prime}\leq d$
and thus is a $(\overline{d},t)$-CDA. ∎

A similar argument applies to $(d,\overline{t})$-CDAs and
$(\overline{d},\overline{t})$-CDAs.

######  Theorem 3.7.

For $d=t=0$ or $d\leq\tau_{1}$ and $t>0$, a $(d,\overline{t})$-CDA is
equivalent to a $(\overline{d},\overline{t})$-CDA.

Trivially $(0,\overline{t})$-CDA is a $(\overline{0},\overline{t})$-CDA. Let
$A$ be a $(d,\overline{t})$-CDA such that $1\leq d\leq\tau_{t}$ and $t>0$.
Below we will show that $A$ is a $(d-1,\overline{t})$-CDA. Let
$\mathcal{T}\subseteq\overline{\mathcal{VI}_{t}}$ such that $\mathcal{T}$ is
independent and $|\mathcal{T}|=d-1$. Let $T$ be a valid interaction of
strength at most $t$. If $\mathcal{T}\succ T$ or $T\in\mathcal{T}$, then
$\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
trivially holds.

Consider the remaining case where $\mathcal{T}\not\succ T$ and
$T\not\in\mathcal{T}$. In this case, there is some $\sigma\in\mathcal{R}$ such
that $T\subseteq\sigma$ and $\sigma\not\in\rho_{\mathcal{R}}(\mathcal{T})$.

Case $|T|>0$. Since $|\mathcal{T}\cup\\{T\\}|=d\leq\tau_{1}$ and every
interaction in $\mathcal{T}\cup\\{T\\}$ has strength at least one,
$\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T}\cup\\{T\\})$ is not empty. Let
$T^{\prime}$ be an interaction of strength $t$ that appears in a test case in
$\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T}\cup\\{T\\})$ and has a different
value on at least one parameter from $T$. Let
$\mathcal{T}^{\prime}=\mathcal{T}\cup\\{T^{\prime}\\}$. $\mathcal{T}^{\prime}$
is independent because $\mathcal{T}$ is independent and $\hat{T}\not\subset
T^{\prime}$ for any $\hat{T}\in\mathcal{T}$. (Note that if $\hat{T}\subset
T^{\prime}$, $\hat{T}$ would occur in the test case with $T^{\prime}$.) Also
$\mathcal{T}^{\prime}\not\succ T$ since $T\subseteq\sigma$,
$\sigma\not\in\rho_{\mathcal{R}}(\mathcal{T})$, and
$\sigma\not\in\rho_{\mathcal{R}}(T^{\prime})$. Because $A$ is a
$(d,\overline{t})$-CDA, $\mathcal{T}^{\prime}$ is independent, and
$\mathcal{T}^{\prime}\not\succ T$, we have
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T}^{\prime})$. Hence
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$.

Case $T=\curlywedge$ (i.e., $|T|=0$). As $\curlywedge\not\in\mathcal{T}$,
every interaction in $\mathcal{T}$ has strength at least one. Since
$|\mathcal{T}|=d-1<\tau_{1}$, $\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T})$ is
not empty. Let $T^{\prime}$ be any $t$-way interaction that appears in a test
case in $\mathcal{R}-\rho_{\mathcal{R}}(\mathcal{T})$. Let
$\mathcal{T}^{\prime}=\mathcal{T}\cup\\{T^{\prime}\\}$. Because of the same
argument as in the case $|T|>0$, $\mathcal{T}^{\prime}$ is independent and
$\mathcal{T}^{\prime}\not\succ T$ and thus
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T}^{\prime})$. Hence
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$.

As a result, $\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$.
By induction, $A$ is a $(d^{\prime},\overline{t})$-CDA for any $0\leq
d^{\prime}\leq d$ and thus is a $(\overline{d},\overline{t})$-CDA. ∎

Figure 4: The relationships among CDA variants (when marked with $+$, one requires that $d\leq\tau_{t}$; when marked with ${\dagger}$, $d\leq\tau_{1}$) $(d,\overline{t})\textrm{-CDA}$ | $\Rightarrow$ | $(d,t)\textrm{-CDA}$
---|---|---
$\Uparrow$$\Downarrow^{+}$ |  |  $\Uparrow$$\Downarrow^{\dagger}$
$(\overline{d},\overline{t})\textrm{-CDA}$ | $\Rightarrow$ | $(\overline{d},t)\textrm{-CDA}$

These theorems lead to the relationships illustrated in Figure 4. Because of
these results, we henceforth focus on $(\overline{d},t)$-CDAs and
$(\overline{d},\overline{t})$-CDAs.

######  Theorem 3.8.

A $(\overline{d},t)$-CDA is a $t$-CCA. A $(\overline{d},\overline{t})$-CDA is
a $t$-CCA.

Let $T\in\mathcal{VI}_{t}$. Let $A$ be a $(\overline{d},t)$-CDA or a
$(\overline{d},\overline{t})$-CDA. Then $T\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
for any $\mathcal{T}\subseteq\mathcal{VI}_{t}$ such that $|\mathcal{T}|\leq
d$. If $|\mathcal{T}|=0$, then $\mathcal{T}=\emptyset$, in which case
$\mathcal{T}\not\succ T$, $T\not\in\mathcal{T}$, and
$\rho_{A}(\mathcal{T})=\emptyset$. Hence $\rho_{A}(T)\not=\emptyset$. ∎

###  3.2 Identification of faulty interactions

Figure 5: $2$-CCA, $(\overline{1},2)$-CLA, and test outcomes in Case 1 and
Case 2.

(a) Test outcomes of 2-CCA. | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$ |  | Case1 | Case2
---|---|---|---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0 |  | Fail | Fail
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 3 |  | Fail | Fail
$\boldsymbol{\sigma}_{3}$ | 0 | 1 | 1 | 1 |  | Pass | Fail
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 2 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{5}$ | 1 | 0 | 0 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{6}$ | 1 | 0 | 0 | 3 |  | Pass | Pass
$\boldsymbol{\sigma}_{7}$ | 1 | 0 | 2 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{8}$ | 1 | 1 | 1 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{9}$ | 2 | 0 | 0 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{10}$ | 2 | 0 | 0 | 3 |  | Pass | Pass
$\boldsymbol{\sigma}_{11}$ | 2 | 0 | 1 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{12}$ | 2 | 1 | 2 | 0 |  | Pass | Pass

(b) Test outcomes of $(\overline{1},2)$-CLA. | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$ |  | Case1 | Case2
---|---|---|---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0 |  | Fail | Fail
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 3 |  | Fail | Fail
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 1 | 1 |  | Fail | Fail
$\boldsymbol{\sigma}_{4}$ | 0 | 1 | 1 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{5}$ | 0 | 1 | 2 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{6}$ | 1 | 0 | 0 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{7}$ | 1 | 0 | 0 | 3 |  | Pass | Pass
$\boldsymbol{\sigma}_{8}$ | 1 | 0 | 1 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{9}$ | 1 | 1 | 1 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{10}$ | 1 | 1 | 2 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{11}$ | 1 | 1 | 2 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{12}$ | 2 | 0 | 0 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{13}$ | 2 | 0 | 0 | 3 |  | Pass | Pass
$\boldsymbol{\sigma}_{14}$ | 2 | 0 | 2 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{15}$ | 2 | 1 | 1 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{16}$ | 2 | 1 | 1 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{17}$ | 2 | 1 | 2 | 1 |  | Pass | Pass

Figure 6: $(\overline{1},2)$-CDA and test outcomes in Case 1 and Case 2. | $F_{1}$ | $F_{2}$ | $F_{3}$ | $F_{4}$ |  | Case1 | Case2
---|---|---|---|---|---|---|---
$\boldsymbol{\sigma}_{1}$ | 0 | 0 | 0 | 0 |  | Fail | Fail
$\boldsymbol{\sigma}_{2}$ | 0 | 0 | 0 | 1 |  | Fail | Fail
$\boldsymbol{\sigma}_{3}$ | 0 | 0 | 0 | 3 |  | Fail | Fail
$\boldsymbol{\sigma}_{4}$ | 0 | 0 | 1 | 1 |  | Fail | Fail
$\boldsymbol{\sigma}_{5}$ | 0 | 0 | 2 | 2 |  | Fail | Pass
$\boldsymbol{\sigma}_{6}$ | 0 | 1 | 1 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{7}$ | 0 | 1 | 2 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{8}$ | 0 | 1 | 2 | 1 |  | Pass | Fail
$\boldsymbol{\sigma}_{9}$ | 1 | 0 | 0 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{10}$ | 1 | 0 | 0 | 3 |  | Pass | Pass
$\boldsymbol{\sigma}_{11}$ | 1 | 0 | 1 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{12}$ | 1 | 0 | 2 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{13}$ | 1 | 1 | 1 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{14}$ | 1 | 1 | 2 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{15}$ | 1 | 1 | 2 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{16}$ | 2 | 0 | 0 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{17}$ | 2 | 0 | 0 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{18}$ | 2 | 0 | 0 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{19}$ | 2 | 0 | 0 | 3 |  | Pass | Pass
$\boldsymbol{\sigma}_{20}$ | 2 | 0 | 1 | 2 |  | Pass | Pass
$\boldsymbol{\sigma}_{21}$ | 2 | 0 | 2 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{22}$ | 2 | 1 | 1 | 0 |  | Pass | Pass
$\boldsymbol{\sigma}_{23}$ | 2 | 1 | 1 | 1 |  | Pass | Pass
$\boldsymbol{\sigma}_{24}$ | 2 | 1 | 2 | 2 |  | Pass | Pass

Using a CDA as a test suite, faulty interactions are identified as follows.
The execution of a test suite yields a test outcome which is a set of failed
test cases and a set of passing test cases. Every interaction of the target
strength is identified as faulty iff it appears in at least one of the failed
test cases but none of the passing ones. For a $(\overline{d},t)$-CDA or a
$(\overline{d},\overline{t})$-CDA, the target strength is $t$ or
$0,1,\dots,t$, respectively. Let $\mathcal{T}$ be the set of the faulty
interactions. In other words, for a CDA $A$ and an interaction $T$ of the
target strength, $T$ is identified as faulty iff
$\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$. Note that we do not know
$\mathcal{T}$ in advance but know the set of failed test cases
$\rho_{A}(\mathcal{T})$.

Suppose that a $(d,t)$-CDA $A$ is used as a test suite assuming that the
number of faulty interactions is at most $d$ and that they are all $t$-way.

First let us consider the case where the assumptions are indeed true. For an
interaction $T\in\mathcal{VI}_{t}$, if $\mathcal{T}\not\succ T$, then
$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$
holds; i.e., $T$ is faulty iff test cases in which $T$ appears all failed.
Hence $T$ is accurately determined to be faulty or not faulty, except when
$\mathcal{T}\succ T$, in which case $T$ is identified as faulty.

Next consider the case where the assumption on the number of faulty
interactions is false. That is, there are more than $d$ faulty interactions.
In this case, interactions $T$ can be falsely determined to be faulty even if
$\mathcal{T}\not\succ T$. However, all faulty interactions are correctly
identified as faulty, because all valid $t$-way interactions appear in $A$
(Theorem 3.8). When the assumption on the strength is false, it is not
possible to identify all faulty interactions. This is because in that case
some faulty interaction may not appear in any test case, unless an exhaustive
test suite is used.

The situation is similar when $A$ is a $(\overline{d},\overline{t})$-CDA. In
this case, the assumptions are: $|\mathcal{T}|\leq d$ and the strength of the
faulty interactions is at most $t$.

When these assumptions are true, $T(\in\overline{\mathcal{VI}_{t}})$ is
accurately determined to be faulty or not faulty unless $\mathcal{T}\succ T$
or $\mathcal{T}\cup\\{T\\}$ is not independent, since
$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$.

But even when $\mathcal{T}\cup\\{T\\}$ is not independent, accurate
identification is still possible if $\mathcal{T}$ contains neither proper
subsets nor proper supersets of $T$ and $\mathcal{T}\not\succ T$. In that
case, if we let
$\mathcal{T}_{\min}=\\{T^{\prime}\in\mathcal{T}:T^{\prime\prime}\not\subset
T^{\prime}\mathrm{~{}for~{}all~{}}T^{\prime\prime}\in\mathcal{T}\\}$ (i.e.,
$\mathcal{T}_{\min}(\subseteq\mathcal{T})$ is the set of minimal interactions
in $\mathcal{T}$), then $\mathcal{T}_{\min}\not\succ T$ and
$\mathcal{T}_{\min}\cup\\{T\\}$ becomes independent, and thus
$T\in\mathcal{T}_{\min}\Leftrightarrow\rho_{A}(T)\in\rho_{A}(\mathcal{T}_{\min})$.
Also $T\in\mathcal{T}\Leftrightarrow T\in\mathcal{T}_{\min}$ and
$\rho_{A}(\mathcal{T})=\rho_{A}(\mathcal{T}_{\min})$. Consequently
$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$.

In sum, faulty interactions are all identified as faulty and a non-faulty
interaction may be identified as faulty only if the set of the faulty
interactions masks the non-faulty interaction or contains its proper subsets
or supersets.

When $|\mathcal{T}|>d$, non-faulty interactions might be falsely identified as
faulty; but all faulty interactions are correctly identified as faulty. The
faulty interactions can be correctly identified because they only appear in
the failed test cases.

When the assumption on the strength is not false, it is not possible to
identify all faulty interactions.

####  3.2.1 Examples

Here using the running example, we illustrate how CCA, CLA and CDA arrays are
used to detect and locate faulty interactions. We consider the cases $d=1$ and
$t=2$. Suppose that the $2$-way CCA, the $(1,2)$-CLA, and the $(1,2)$-CDA
shown in Figures 2, 2, and Figure 3 are used as test suites. In fact the CLA
and the CDA are a $(\overline{1},2)$-CLA and a $(\overline{1},2)$-CDA. Figure
5 and Figure 6 summarize the results of test cases when executed in the two
cases below.

  1. [Case 1]

  2. 1.

The only faulty interaction is $T_{\alpha}=\\{(F_{1},0),(F_{2},0)\\}$.

  3. 2.

There are two faulty interactions $T_{\beta}=\\{(F_{1},0),(F_{3},0)\\}$ and
$T_{\gamma}=\\{(F_{1},0),(F_{4},1)\\}$.

##### CCA

In Case 1, within the test cases in the 2-CCA (Figure 2), only the test cases
$\boldsymbol{\sigma}_{1}$ and $\boldsymbol{\sigma}_{2}$ fail. The two-way
interactions that appear only in those failed test cases are as follows (the
faulty interaction is indicated by underline.)

$\displaystyle\underline{\\{(F_{1},0),(F_{2},0)\\}}\qquad\\{(F_{1},0),(F_{3},0)\\}\qquad\\{(F_{1},0),(F_{4},0)\\}$
$\displaystyle\\{(F_{2},0),(F_{4},0)\\}\qquad\\{(F_{3},0),(F_{4},0)\\}\qquad\\{(F_{1},0),(F_{4},3)\\}$

In Case 2, the failed test cases are $\sigma_{1}$, $\sigma_{2}$, and
$\sigma_{3}$; thus the candidates for faulty interactions are:

$\displaystyle\\{(F_{1},0),(F_{2},0)\\}\qquad\underline{\\{(F_{1},0),(F_{3},0)\\}}\qquad\\{(F_{1},0),(F_{4},0)\\}$
$\displaystyle\\{(F_{2},0),(F_{4},0)\\}\qquad\\{(F_{3},0),(F_{4},0)\\}\qquad\\{(F_{1},0),(F_{4},3)\\}$
$\displaystyle\\{(F_{1},0),(F_{3},1)\\}\qquad\underline{\\{(F_{1},0),(F_{4},1)\\}}\qquad\\{(F_{2},1),(F_{4},1)\\}$
$\displaystyle\\{(F_{3},1),(F_{4},1)\\}$

For both cases it is impossible to further reduce the candidates of faulty
interactions.

##### CLA

Suppose that the $(1,2)$-CLA ($\overline{1},2$-CLA) shown in Figure 2 is used.
In Case 1, the test cases $\boldsymbol{\sigma}_{1}$, $\boldsymbol{\sigma}_{2}$
and $\boldsymbol{\sigma}_{3}$ fail and all the other test cases pass. The
interactions that appear only in the failed test cases are as follows.

$\displaystyle\underline{\\{(F_{1},0),(F_{2},0)\\}}\qquad\\{(F_{1},0),(F_{3},0)\\}\qquad\\{(F_{3},0),(F_{4},0)\\}$
$\displaystyle\\{(F_{1},0),(F_{4},3)\\}\qquad\\{(F_{1},0),(F_{4},1)\\}$

The core idea of CLAs is that it allows a test outcome to be uniquely
associated with a set of faulty interactions, which is mathematically
represented as
$\mathcal{T}_{1}=\mathcal{T}_{2}\Leftrightarrow\rho_{A}(\mathcal{T}_{1})=\rho_{A}(\mathcal{T}_{2})$.
In this case,
$\rho_{A}(\mathcal{T})=\rho_{A}(\\{T_{\alpha}\\})=\\{\sigma_{1},\sigma_{2},\sigma_{3}\\}$
holds only for $\mathcal{T}=\\{\\{(F_{1},0),(F_{2},0)\\}\\}$, provided that
$\mathcal{T}\subseteq\mathcal{VI}_{2}$ and $|\mathcal{T}|\leq 1$. Thus, we
correctly locate the faulty interaction.

Now consider Case 2\. The failed test cases are the same as in Case 1, i.e.,
$\boldsymbol{\sigma}_{1}$, $\boldsymbol{\sigma}_{2}$ and
$\boldsymbol{\sigma}_{3}$. Hence the conclusion that $T_{\alpha}$ is the only
faulty interaction is also the same. This incorrect result is caused by that
the number of faulty interactions does not coincide with the assumption
(namely $d=1$). In general, if faulty interactions exceed the number assumed,
CLAs may identify non-faulty interactions as faulty but also identify faulty
interactions as non-faulty.

##### CDA

Suppose that the $(1,2)$-CDA ($(\overline{1},2)$-CDA) shown in Figure 3 is
used to locate faulty interactions. For Case 1, the failed test cases are
$\boldsymbol{\sigma}_{1}$, $\boldsymbol{\sigma}_{2}$,
$\boldsymbol{\sigma}_{3}$, $\boldsymbol{\sigma}_{4}$ and
$\boldsymbol{\sigma}_{5}$. The interactions occurring only in the failed test
cases are all identified as faulty. In this case these interactions are:

$\displaystyle\underline{\\{(F_{1},0),(F_{2},0)\\}}\qquad\\{(F_{1},0),(F_{3},0)\\}\qquad\\{(F_{1},0),(F_{4},3)\\}$

$T_{\alpha}$ is correctly identified as faulty, whereas
$\\{(F_{1},0),(F_{3},0)\\}$ and $\\{(F_{1},0),(F_{4},3)\\}$ are incorrectly
identified as faulty. Since $\\{T_{a}\\}$ masks $\\{(F_{1},0),(F_{3},0)\\}$
and $\\{(F_{1},0),(F_{4},3)\\}$
($\\{T_{\alpha}\\}\succ\\{(F_{1},0),(F_{3},0)\\}$ and
$\\{T_{\alpha}\\}\succ\\{(F_{1},0),(F_{4},3)\\}$), it is inherently impossible
to determine that $\\{(F_{1},0),(F_{3},0)\\}$ and $\\{(F_{1},0),(F_{4},3)\\}$
are not faulty when $T_{\alpha}$ is faulty. However, it should be noted that
if we relied on the assumption that the number of faulty interactions is
$d=1$, just as in the case of the CLA above, we could correctly identify only
$T_{\alpha}$ as faulty. In fact, we will show later that any CDA is a CLA.

ecause we assume that there are only one faulty interaction, if the faulty
interaction is $\\{(F_{1},0),(F_{4},3)\\}$, then the test cases
$\boldsymbol{\sigma}_{1}$, $\boldsymbol{\sigma}_{2}$,
$\boldsymbol{\sigma}_{4}$ and $\boldsymbol{\sigma}_{5}$ will not fail. Hence,
the faulty interaction can be found as $T_{a}=\\{(F_{1},0),(F_{2},0)\\}$.
Besides, we can find that $\\{T_{a}\\}$ masks $\\{(F_{1},0),(F_{4},3)\\}$ in
the SUT. Hence, the conclusion becomes “$T_{a}=\\{(F_{1},0),(F_{2},0)\\}$
should be the only faulty interaction. It is unable to determine the
correctness of $\\{(F_{1},0),(F_{4},3)\\}$”. It is impossible to clarify
whether $\\{(F_{1},0),(F_{4},3)\\}$ is faulty or not unless
$T_{a}=\\{(F_{1},0),(F_{2},0)\\}$ is revised. Because any test cases that
cover $\\{(F_{1},0),(F_{4},3)\\}$ will also cover $T_{a}$. Hence, the
correctness of $\\{(F_{1},0),(F_{4},3)\\}$ is masked by $T_{a}$.

For Case 2, the failed test cases are $\boldsymbol{\sigma}_{1}$,
$\boldsymbol{\sigma}_{2}$, $\boldsymbol{\sigma}_{3}$,
$\boldsymbol{\sigma}_{4}$, and $\boldsymbol{\sigma}_{8}$. The interactions
that are identified as faulty are:

$\displaystyle\underline{\\{(F_{1},0),(F_{3},0)\\}}\qquad\underline{\\{(F_{1},0),(F_{4},1)\\}}\qquad\\{(F_{1},0),(F_{4},3)\\}$

ecall that when we use a $(1,2)$-CLA to locate faulty interactions in Case 2,
the results of the CLA are as same as those in Case 1\. However, the results
of the CDA test cases indicate a different conclusion. The set of the failed
test cases does not match any single 2-way interaction in the SUT, i.e., does
not match
$\rho_{A}(T_{a})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3},\boldsymbol{\sigma}_{4},\boldsymbol{\sigma}_{5}\\}$
nor match
$\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{16}\\}$. In
other words, the results indicate that the actual number of faulty
interactions is larger than the parameter $d=1$. In conclusion, a $(d,t)$-CDA
can locate $d$ $t$-way interactions. In addition to that, if there are more
than $d$ faulty interactions, CDAs can return a unique failed test case set to
inform that there are more than $d$ faulty interactions. Although the last
interaction is in fact not faulty, all the faulty ones are correctly
identified. In general, when using a CDA, non-faulty interactions are never
wrongly identified as faulty even if the number of faulty interactions exceeds
the assumed number $d$.

###  3.3 Properties of CDAs

In the rest of the section we provide some theorems on the properties of CDAs.

######  Theorem 3.9.

$\mathcal{R}$, the exhaustive test suite, is a $(d,t)$-, $(d,\overline{t})$-,
$(\overline{d},t)$\- and $(\overline{d},\overline{t})$-CDA for any $d$ and
$t$.

Let $T$ be a valid interaction and $\mathcal{T}$ be a set of valid
interactions. Below we will show $\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{\mathcal{R}}(T)\subseteq\rho_{\mathcal{R}}(\mathcal{T}))$.
If $\mathcal{T}\not\succ T$ and $T\not\in\mathcal{T}$, then there is some
$\sigma\in\mathcal{R}$ such that $T\subseteq\sigma$ and $\forall
T^{\prime}\in\mathcal{T}:T^{\prime}\not\subseteq\sigma$, in which case
$\sigma\in\rho_{\mathcal{R}}(T)-\rho_{\mathcal{R}}(\mathcal{T})$. That is,
$\mathcal{T}\not\succ
T\Rightarrow(T\not\in\mathcal{T}\Rightarrow\rho_{\mathcal{R}}(T)\not\subseteq\rho_{\mathcal{R}}(\mathcal{T}))$.
In addition
$T\in\mathcal{T}\Rightarrow\rho_{\mathcal{R}}(T)\subseteq\rho_{\mathcal{R}}(\mathcal{T})$
trivially holds. As a result, the theorem follows. ∎

######  Theorem 3.10.

A $(d,t)$-CDA is also a $(d,t)$-CLA; a $(\overline{d},t)$-CDA is also a
$(\overline{d},t)$-CLA; A $(d,\overline{t})$-CDA is also a
$(d,\overline{t})$-CLA and a $(\overline{d},\overline{t})$-CDA is also a
$(\overline{d},\overline{t})$-CLA.

Let $A$ be a $(d,t)$-CDA. Let $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ be
different sets of $t$-way interactions of size $d$ and mutually
distinguishable.
$\rho_{\mathcal{R}}(\mathcal{T}_{1})\neq\rho_{\mathcal{R}}(\mathcal{T}_{2})$
by the definition of distinguishability. Without loss of generality, we assume
that $\mathcal{T}_{1}\not\subset\mathcal{T}_{2}$. Denote the test case that
exists in $\rho_{\mathcal{R}}(\mathcal{T}_{1})$ but not in
$\rho_{\mathcal{R}}(\mathcal{T}_{2})$ as $\boldsymbol{\sigma}_{e}$. There
exists at least one valid interaction $T$ in $\mathcal{T}_{1}$ that is covered
by $\boldsymbol{\sigma}_{e}$. $\mathcal{T}_{2}$ does not mask $T$ and
$T\not\in\mathcal{T}_{2}$ because
$\boldsymbol{\sigma}_{e}\in\rho_{\mathcal{R}}(T)\land\boldsymbol{\sigma}_{e}\not\in\rho_{\mathcal{R}}(\mathcal{T}_{2})$.
Since $A$ is a $(d,t)$-CDA, $\mathcal{T}_{2}\not\succ T$, and
$T\not\in\mathcal{T}_{2}$, we have
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T}_{2})$. Hence there exists a row
$\boldsymbol{\sigma}_{e}^{\prime}$ in $A$ such that
$\boldsymbol{\sigma}_{e}^{\prime}$ covers $T$ but does not cover any
interactions in $\mathcal{T}_{2}$, that is,
$\boldsymbol{\sigma}_{e}^{\prime}\in\rho_{A}(\mathcal{T}_{1})\land\boldsymbol{\sigma}_{e}^{\prime}\not\in\rho_{A}(\mathcal{T}_{2})$
holds. Thus $\rho_{A}(\mathcal{T}_{1})\neq\rho_{A}(\mathcal{T}_{2})$ holds;
hence $A$ is a $(d,t)$-CLA. The same argument holds when $|\mathcal{T}_{1}|$
and $|\mathcal{T}_{2}|$ are not exactly $d$ but at most $d$. Therefore it
follows that a $(\overline{d},t)$-CDA is a $(\overline{d},t)$-CLA.

Next let $A$ be a $(d,\overline{t})$-CDA or a
$(\overline{d},\overline{t})$-CDA. Let $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$
be different sets consisting of exactly $d$ interactions of strength at most
$t$ or at most $d$ interactions of strength at most $t$, respectively. Then
the same argument for the case of $(d,t)$-CDAs and $(\overline{d},t)$-CDAs
holds. As a result, the theorem follows. ∎

figure[h] The among between CDAs and CLAs
$(\overline{d},\overline{t})\textrm{-CDA}$ $\Rightarrow$
$(\overline{d},\overline{t})\textrm{-CLA}$ $(\overline{d},t)\textrm{-CDA}$
$\Rightarrow$ $(\overline{d},t)\textrm{-CLA}$ $(d,\overline{t})\textrm{-CDA}$
$\Rightarrow$ $(d,\overline{t})\textrm{-CLA}$ $(d,t)\textrm{-CDA}$
$\Rightarrow$ $(d,t)\textrm{-CLA}$

DAs are also closely related to CCAs.

######  Theorem 3.11.

A $(d,t)$-CDA is a $t$-CCA.

Let $A$ be a $(d,t)$-CDA. Let $T\in\mathcal{VI}_{t}$. Since $A$ is a
$(\overline{d},t)$-CDA, $T\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
for any $\mathcal{T}\subseteq\mathcal{VI}_{t}$ such that $|\mathcal{T}|\leq
d$. If $|\mathcal{T}|=0$, then $\mathcal{T}=\\{\\}$, in which case
$\mathcal{T}\not\succ T$, $T\not\in\mathcal{T}$, and
$\rho_{A}(\mathcal{T})=\emptyset$. Hence $\rho_{A}(T)\not=\emptyset$.

######  Theorem 3.12.

A $(t+d)$-CCA is a $(\overline{d},\overline{t})$-CDA.

Suppose that A is a $(t+d)$-CCA. The theorem holds if
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$ for any
$T\in\overline{\mathcal{VI}_{t}}$ and
$\mathcal{T}\subseteq\overline{\mathcal{VI}_{t}}$ such that
$0\leq|\mathcal{T}|\leq d$, $T\not\in\mathcal{T}$, $\mathcal{T}\not\succ T$,
and $\\{T\\}\cup\mathcal{T}$ is independent. We show this by constructing a
valid interaction $\hat{T}$ of strength $\leq d+t$ that covers $T$ but cannot
appear with any interaction in $\mathcal{T}$ in the same row. If such
$\hat{T}$ exists, some row of $A$ contains it because $A$ is a $(t+d)$-CCA.
This row is in $\rho_{A}(T)$ but not in $\rho_{A}(\mathcal{T})$; thus
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$.

Since $\mathcal{T}\not\succ T$, there must be a valid test case $\sigma$ that
covers $T$ but does not cover any $T^{\prime}\in\mathcal{T}$. Let
$\sigma=\langle s_{1},s_{2},\dots,s_{k}\rangle$. We regard $\sigma$ as $k$-way
interaction $\\{(F_{1},s_{1}),(F_{2},s_{2}),\dots,(F_{k},s_{k})\\}$. $\hat{T}$
is constructed by starting from $\hat{T}=T$ and gradually expanding it by
applying the following process for all $T^{\prime}\in\mathcal{T}$: Select any
$(F_{i},v)\in T^{\prime}$ such that $s_{i}\neq v$. This can be done because
$T^{\prime}$ is not covered by $\sigma$ (and thus
$\curlywedge\not\in\mathcal{T}$). Add $(F_{i},s_{i})$ to $\hat{T}$. Finally
$\hat{T}$ becomes the desired interaction. ∎

##  4 Generation Algorithms

In this section, we present two algorithms for generating CDAs: the
satisfiability-based algorithm and the two-step heuristic algorithm. In this
section we limit ourselves to $(d,t)$-CDAs because $(d,t)$-CDAs are
$(\overline{d},t)$-CDAs except in extreme cases (Theorem 3.7). Also it is
straightforward to adjust the algorithms to $(d,\overline{t})$-CDAs and
$(\overline{d},\overline{t})$-CDAs.

###  4.1 The satisfiability-based algorithm

The first algorithm leverages a satisfiability solver. We reduce the problem
of generating a CDA of a given size to the satisfiability problem of a logical
(i.e., Boolean-valued) expression. A logical expression is satisfiable iff it
evaluates to true for some _valuation_ , i.e., assignment of values to the
variables. The algorithm first estimates the upper bound on the minimum size
of a CDA and uses it as the initial size of a CDA. Then it creates a logical
expression that is satisfiable iff a CDA of the initial size exists. The
logical expression is in turn evaluated by a satisfiability solver. We design
the logical expression so that the valuation that satisfies it directly
represents a CDA. Satisfiability solvers can produce such a satisfying
valuation when the expression is satisfiable; hence a CDA can be obtained from
the output of the solver. Repeating the process while decreasing the CDA size,
the algorithm can obtain the smallest CDA.

####  4.1.1 The logic expression

To represent an array with a collection of variables, we adopt the naïve
matrix model which is used by Hnich et al. [9] in their study to find CAs. In
this model, an $N\times k$ array is represented as an $N\times k$ matrix of
integer variables as follows.

$A=\left(\begin{array}[]{ccc}p_{1}^{1}&\cdots&p_{k}^{1}\\\
\vdots&\ddots&\vdots\\\ p_{1}^{N}&\cdots&p_{k}^{N}\end{array}\right)$

The variable $p_{i}^{n}$ represents the value on the parameter $F_{i}$ in the
$n$-th test case. The domain of $p_{i}^{n}$ is
$S_{i}=\\{0,1,\dots,|S_{i}|-1\\}$.

In order for the array $A$ to become a $(d,t)$-CDA, we impose the following
conditions on $A$ using logical expressions.

  1. 1.

The rows of $A$ represent valid test cases.

  2. 2.

$\forall\mathcal{T}\subseteq\mathcal{VI}_{t}\textrm{ such that
}|\mathcal{T}|=d,\forall T\in\mathcal{VI}_{t}:$ $\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$

Below we present logical expressions that represent the above two conditions.
By conjuncting all the expressions, we obtain a single logical expression to
be checked for satisfiability.

##### Condition 1

In $A$, the $n$-th row is expressed as a tuple of $k$ variables
$(p_{1}^{n},p_{2}^{n},\dots,p_{k}^{n})$. As defined in Section 2, a test case
is valid iff it satisfies the constraints and the constraints are represented
by $\phi$, a Boolean-valued formula over parameters $F_{1},\dots,F_{k}$. We
let $\phi|_{p_{1}^{n},p_{2}^{n},\dots,p_{k}^{n}}$ denote $\phi$ with each
$F_{i}$ being replaced with $p_{i}^{n}$. Then, the following expression
enforces $A$ to only contain valid test cases.

$\textit{Valid}:=\bigwedge_{n=1}^{N}\phi|_{p_{1}^{n},p_{2}^{n},\dots,p_{k}^{n}}$

The second condition holds if and only if the definition of CDAs is true for
every $\mathcal{T}$-$T$ pair. That is,

$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$

or equivalently

$T\not\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$

holds unless $\mathcal{T}\succ T$. This condition can be simplified as

$T\not\in\mathcal{T}\Rightarrow\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$

because the other direction trivially holds.

##### Condition 2

It is important to note that $\mathcal{T}\not\succ
T\Rightarrow(T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T}))$
is equivalent to:

$(\mathcal{T}\not\succ T\land
T\not\in\mathcal{T})\Rightarrow\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$

because $T\in\mathcal{T}\Rightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$
trivially holds. Hence we can focus on the case where $\mathcal{T}\not\succ T$
and $T\not\in\mathcal{T}$. The right part of this formula, that is,
$\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$ holds iff there is a row in
$A$ that covers $T$ but none of the interactions in $\mathcal{T}$. This
condition is represented by a logical expression as follows:

$\textit{Locating}(\mathcal{T},T):=\bigvee_{n=1}^{N}\Big{(}\bigwedge_{j=1}^{t}{(p_{x_{j}}^{n}=v_{x_{j}})}\land\neg\Big{(}\bigvee_{L=1}^{d}\bigwedge_{l=1}^{t}{(p_{y_{L_{l}}}^{n}=v_{y_{L_{l}}})}\Big{)}\Big{)}$

where
$\mathcal{T}=\\{\\{(F_{y_{1_{1}}},v_{y_{1_{1}}}),\dots,(F_{y_{1_{t}}},v_{y_{1_{t}}})\\},\dots$,
$\\{(F_{y_{d_{1}}},v_{y_{d_{1}}})$, $\dots$,
$(F_{y_{d_{t}}},v_{y_{d_{t}}})\\}\\}$ and
$T=\\{(F_{x_{1}},v_{x_{1}}),\dots,(F_{x_{t}},v_{x_{t}})\\}$. For given
$\mathcal{T}$ and $T$, $\rho_{A}(T)\not\subseteq\rho_{A}(\mathcal{T})$ holds
iff $\textit{Locating}(\mathcal{T},T)$ is satisfiable.

Given a valid interaction $T$, the following expression describes that the
array $A$ includes at least one test case that covers $T$.

$Covering(T):=\bigvee_{n=1}^{N}\bigwedge_{j=1}^{t}(p_{i_{j}}^{n}=v_{i_{j}})$

The OR operator $\bigvee$ ensures $T$ to appear in at least one test case.

Let us define $\mathcal{U}$ as follows:

$\mathcal{U}:=\\{(\mathcal{T},T)\mid\mathcal{T}\subseteq\mathcal{VI}_{t},|\mathcal{T}|=d,T\in\mathcal{VI}_{t},\mathcal{T}\not\succ
T,T\not\in\mathcal{T}\\}$

By ANDing $\textit{Locating}(\mathcal{T},T)$ for all
$(\mathcal{T},T)\in\mathcal{U}$, we obtain an expression that represents the
second condition.

##### The whole expression

The whole expression that will be checked for satisfiability is obtained by
conjuncting the expressions defined above as follows:

$\textit{existCDA}:=\ \textit{Valid}\
\land\bigwedge_{(\mathcal{T},T)\in\mathcal{U}}\textit{Locating}(\mathcal{T},T)$

By checking the satisfiability of this expression, whether a $(d,t)$-CDA of
size $N$ exists or not can be determined. If it is satisfiable, then a CDA of
size $N$ exists. In this case, the satisfying valuation for the $N\times k$
variables $p_{i}^{n}$ represents all the entries of one such CDA. On the other
hand, if the expression is unsatisfiable, then it can be concluded that no
$(d,t)$-CDA of size $N$ exists.

The satisfiability of the above expression can be checked using Constraint
Satisfaction Problem (CSP) solvers, Satisfiability Modulo Theories (SMT)
solvers, or Boolean Satisfiability (SAT) solvers with a Boolean encoding of
integers.

####  4.1.2 Computing $\mathcal{U}$

In order to construct the above logical expression existCDA, we need to obtain
$\mathcal{U}$ (see the subscript of the $\bigwedge$ in the expression).
Computing $\mathcal{U}$ requires $\mathcal{VI}_{t}$. We will show how to
compute $\mathcal{VI}_{t}$ later. Here we describe how one can compute
$\mathcal{U}$ when $\mathcal{VI}_{t}$ is available.

We let integer variables $p_{1},p_{2},\dots,p_{k}$ to symbolically represent a
test case $\boldsymbol{\sigma}$; that is,

$\boldsymbol{\sigma}=(p_{1},p_{2},\dots,p_{k})$

The domain of $p_{i}$ is $\\{0,1,\dots,|S_{i}|-1\\}$. Note that $S_{i}$ is the
domain of parameter $F_{i}$.

##### Enumerating valid interactions

Obtaining $\mathcal{VI}_{t}$ means enumerating all valid interactions of
strength $t$. This can be performed by checking every $t$-way interaction
against whether it is valid or not. Recall that an interaction is valid iff it
can be covered by a valid test case. The following expression can be used to
check the validity of a given interaction $T=\\{(F_{i_{1}},v_{i_{1}}),\dots$,
$(F_{i_{t}},v_{i_{t}})\\}$ $(1\leq i_{1}\leq i_{t}\leq k)$.

$checkValidity(T):=\bigwedge_{j=1}^{t}{(p_{i_{j}}=v_{i_{j}})}\land\phi|_{p_{1},p_{2},\dots,p_{k}}$

If this expression is satisfiable, then the interaction $T$ is valid;
otherwise, it is invalid. The set $\mathcal{VI}_{t}$ can be obtained by
checking the satisfiability of the above formula for all $t$-way interactions.

##### Enumerating $\mathcal{T}$-$T$ pairs

Now consider enumerating all $\mathcal{T}$-$T$ pairs such that
$T\in\mathcal{VI}_{t}$, $\mathcal{T}\subseteq\mathcal{VI}_{t}$,
$|\mathcal{T}|=d$, $T\not\in\mathcal{T}$, and $\mathcal{T}\not\succ T$. The
problem here is how to decide whether or not
$\mathcal{T}(\subseteq\mathcal{VI}_{t})$ masks $T(\in\mathcal{VI}_{t})$ when
$\mathcal{T}$ and $T\not\in\mathcal{T}$ are given. This too is possible by
making use of satisfiability solving. We let integer variables
$p_{1},p_{2},\dots,p_{k}$ to symbolically represent a test case
$\boldsymbol{\sigma}$; that is,

$\boldsymbol{\sigma}=(p_{1},p_{2},\dots,p_{k})$

The domain of $p_{i}$ is $\\{0,1,\dots,|S_{i}|-1\\}$. Note that $S_{i}$ is the
domain of parameter $F_{i}$.

By the definition of masking, given such a $\mathcal{T}$-$T$ pair,
$\mathcal{T}$ does not mask $T$ iff the following condition holds:

$\exists\boldsymbol{\sigma}\in\mathcal{R}:T\subseteq\boldsymbol{\sigma}\land\neg(\exists
T^{\prime}\in\mathcal{T}:T^{\prime}\subseteq\boldsymbol{\sigma})$

In words, the condition holds if there is a valid test case that covers the
interaction $T$ but does not cover any interactions in the interaction set
$\mathcal{T}$. Hence, given $\mathcal{T}$ and $T$, $\mathcal{T}\not\succ T$
holds iff the following expression evaluates to true.

$\displaystyle\textit{checkUnMasking}(\mathcal{T},T):=$
$\displaystyle\bigwedge_{j=1}^{t}{(p_{x_{j}}=v_{x_{j}})}\land\neg\Big{(}\bigvee_{L=1}^{d}\bigwedge_{l=1}^{t}{(p_{y_{L_{l}}}=v_{y_{L_{l}}})}\Big{)}\land\phi|_{p_{1},p_{2},\dots,p_{k}}$

where
$\mathcal{T}=\\{\\{(F_{y_{1_{1}}},v_{y_{1_{1}}}),\dots,(F_{y_{1_{t}}},v_{y_{1_{t}}})\\},\dots$,
$\\{(F_{y_{d_{1}}},v_{y_{d_{1}}})$, $\dots$,
$(F_{y_{d_{t}}},v_{y_{d_{t}}})\\}\\}$ and
$T=\\{(F_{x_{1}},v_{x_{1}}),\dots,(F_{x_{t}},v_{x_{t}})\\}$.

$\mathcal{U}$ is obtained by, for every $\mathcal{T}$-$T$ pair, checking the
satisfiability of $\textit{checkUnMasking}(\mathcal{T},T)$ and keeping the
pair in $\mathcal{U}$ if the expression is satisfiable.

####  4.1.3 The algorithm

Input: SUT $\mathcal{M}=\langle\mathcal{F},\mathcal{S},\phi\rangle$; integers
$d$, $t$

Output: ($d$,$t$)-CDA $A$

// construct a $(d+t)$-CCA for the input SUT

1 $S\leftarrow$generateCCA($\mathcal{M}$, $d+t$)

// get all valid $t$-way interactions from the $(d+t)$-CCA

2 ${\cal VI}_{t}\leftarrow\textit{getAllInteractions}(S,t)$

// get all non-masking pairs $\mathcal{U}$ of interaction sets and
interactions

3 $\mathcal{U}\leftarrow\mathit{getU}(\mathcal{VI}_{t},d,t)$

// get the initial size for the CDA to be generated

4 $N\leftarrow$ The size of $S-1$

5 $nextA\leftarrow S$

6 do

// reserve the current test suite instance

7 $A\leftarrow nextA$

// SAT checking; the solver returns an instance if satisfiable; an emptyset,
otherwise

8 $nextA\leftarrow$generateCDA($\mathcal{M},d,t,N,\mathcal{U}$)

// decrease the size by one

9 $N\leftarrow N-1$

10while  _$nextA\neq\perp$_

return _$A$_

Algorithm 1 The satisfiability-based algorithm

The CDA generation algorithm that uses satisfiability solving is shown as
Algorithm 1. The algorithm repeatedly solves the problem of finding a
$(d,t)$-CDA while varying the array size $N$. The array size $N$ starts with a
value large enough to ensure the existence of a CDA and is gradually decreased
until no existence of a CDA of size $N$ is proved. To obtain the initial value
of $N$, the algorithm creates a $(d+t)$-CCA using an off-the-shelf algorithm
(line 1), where the CCA generation algorithm is represented as function
generateCCA($\mathcal{M}$,x) which returns an $x$-CCA. Our algorithm uses the
size of the CCA minus one as the initial $N$, as any $(d+t)$-CCA is a
$(d,t)$-CDA. The $(d+t)$-CCA is also used for computing $\mathcal{VI}_{t}$,
since all valid $t$-way interactions appear in the CCA: The algorithm
enumerates all $t$-way interactions occurring in the array, thus obtaining
$\mathcal{VI}_{t}$.

**TODO*** This idea comes from a conjecture based on a new theorem about the
relations between CCAs and CDAs. The new theorem shows that a $(1+t)$-CCA is
already a $(1,t)$-CDA. (The proof is shown in the next subsection.) According
to the [3], when there is no constraint, a $(d+t)$-CA is a $(d,t)$-DA. Hence,
we can conclude a conjecture that a $(d+t)$-CCA is already a $(d,t)$-CDA.
*********

In the algorithm, generateCDA($\mathcal{M}$, $d$, $t$, $N$, $\mathcal{U}$) in
line 1 represents a function that produces a $(d,t)$-CDA of size $N$ by
checking the satisfiability of the expression existCDA. If the expression is
satisfiable, then the SMT solver returns the satisfying valuation, in which
case a $(d,t)$-CDA of size $N$ is obtained, since the valuation represents the
$(d,t)$-CDA. The size $N$ is decreased by one and the same process is
repeated. If the result of satisfiability check is UNSAT (unsatisfiable), no
CDA of size $N$ exists (denoted as $\perp$ in the algorithm). Then the
algorithm returns the CDA of size $N+1$ and stops its execution.

One might think that binary search could work better to vary $N$ than the
linear search adopted by the algorithm. In fact, this is not the case because
showing unsatisfiability, that is, the nonexistence of a CDA, usually takes
much longer time than showing satisfiability, that is, the existence of a CDA.
The linear search delays solving an unsatisfiable expression until all
possible sizes are checked, avoiding getting trapped in a long computation
required for the unsatisfiable problem instance.

The size of the expression existCDA increases polynomially in $k$ when
$t,d,|S_{i}|$, and $N$ are fixed. The expression can be expressed as a Boolean
formula with a polynomial size increase, as $|S_{i}|$ is fixed. The Boolean
satisfiability problem (SAT) is NP-complete in general and there is no reason
that SAT can be solved in polynomial-time for this particular case. Hence the
time complexity of the algorithm is likely to be exponential.

###  4.2 The two-step heuristic algorithm

In this subsection, we propose a two-step heuristic algorithm for the
generation of $(d,t)$-CDAs which aims to generate $(d,t)$-CDAs that are not
optimal but fairly small in reasonable time.

theorem Let $t$ be an integer such that $1\leq t<k$. If an $N\times k$ array
$A$ is a $(1+t)$-CCA, then $A$ is also a $(1,t)$-CDA.

Suppose that an $N\times k$ array $A$ is a $(1+t)$-CCA and that $1\leq t<k$.
Let $T$ be any valid $t$-way interaction, i.e., $T\in\mathcal{VI}_{t}$, and
$\mathcal{T}$ be any interaction set consisting of one valid $t$-way
interaction such that $\mathcal{T}\not\succ T$. Below we show the following
condition holds.

$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$

Since $|\mathcal{T}|=1$, the above condition is equivalent to:

$T=T^{\prime}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(T^{\prime})$

where $\mathcal{T}=\\{T^{\prime}\\}$. There are two cases to consider.

Case 1: ($T=T^{\prime}$) $\rho_{A}(T)=\rho_{A}(\mathcal{T})$ trivially holds.

Case 2: ($T\not=T^{\prime}$) Let $\mathcal{F}(T)$ ($\mathcal{F}(T^{\prime})$)
be the set of parameters in $T$ ($T^{\prime}$).

If $\mathcal{F}(T^{\prime})=\mathcal{F}(T)$, then $T$ and $T^{\prime}$ has
different values on at least one parameter. $A$ is a $t$-CCA by definition;
thus $T$ and $T^{\prime}$ appear in different rows of $A$. Hence
$\rho_{A}(T)\not\subseteq\rho_{A}(T^{\prime})$.

Now suppose that $\mathcal{F}(T^{\prime})\neq\mathcal{F}(T)$. Because
$\mathcal{T}\not\succ T$, some valid test case, say
$\boldsymbol{\sigma}\in\mathcal{R}$, exists that covers $T$ but not
$T^{\prime}$. Hence, there exists at least one parameter
$F_{e}\in\mathcal{F}(T^{\prime})$ on which $\boldsymbol{\sigma}$ has a
different value from $T^{\prime}$. If $F_{e}\not\in\mathcal{F}(T)$, let
$\boldsymbol{\sigma}(F_{e})$ be the value of $\boldsymbol{\sigma}$ on $F_{e}$
and let $T_{e}$ be the $(1+t)$-way interaction
$T_{e}:=T\cup\\{(F_{e},\boldsymbol{\sigma}(F_{e})\\}$. Because $T_{e}$ is
covered by the valid test case $\boldsymbol{\sigma}$, $T_{e}$ is a valid
$(1+t)$-way interaction. Since $A$ is a $(1+t)$-CCA, $A$ contains a test case,
say $\boldsymbol{\sigma}_{e}$, that covers $T_{e}$. Hence
$\boldsymbol{\sigma}_{e}$ covers $T$ but does not cover $T^{\prime}$; thus
$\boldsymbol{\sigma}_{e}\in\rho_{A}(T)$ and
$\boldsymbol{\sigma}_{e}\not\in\rho_{A}(T^{\prime})$. This implies that
$\rho_{A}(T)\not\subseteq\rho_{A}(T^{\prime})$. If $F_{e}\in\mathcal{F}(T)$,
it means $T$ and $T^{\prime}$ have different values on $F_{e}$. Since $A$ is a
$t$-CCA, $A$ contains a test case $\boldsymbol{\sigma}_{e}$ that covers $T$
but does not cover $T^{\prime}$. Hence,
$\rho_{A}(T)\not\subseteq\rho_{A}(T^{\prime})$.

######  Theorem 4.13.

Let $t$ be an integer such that $0\leq t<k$. If and array $A$ is a
$(t+1)$-CCA, then $A$ is also a $(\overline{1},\overline{t})$-CDA.

Suppose that an $N\times k$ array $A$ is a $(1+t)$-CCA and that $0\leq t<k$.
Let $\mathcal{R}$ be the set of all valid test cases. Let $T$ be any valid
$\overline{t}$-way interaction, i.e., $T\in\overline{\mathcal{VI}_{t}}$ and
$\mathcal{T}$ be any interaction set consisting of at most one valid
$\overline{t}$-way interaction $T^{\prime}$ such that $\mathcal{T}\not\succ
T$. Below we show that the following condition holds in $A$.

$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$

If $T=\emptyset$, $T\subset\mathcal{T}$ for any $\mathcal{T}$. $T$ is masked
by $\mathcal{T}$ in any arrays. Also, if $\mathcal{T}=\\{\emptyset\\}$,
$\rho_{\mathcal{R}}(\mathcal{T})=\mathcal{R}$. $\mathcal{T}$ masks all other
$\overline{t}$-way interactions.

Now, there are two situations to consider.

Situation 1: $T\not=\emptyset\land\mathcal{T}=\emptyset$. By definition,
$\rho_{\mathcal{R}}(T)\neq\emptyset$ and
$\rho_{\mathcal{R}}(\mathcal{T})=\emptyset$. Hence, $T$ is not masked by
$\mathcal{T}$. Because $A$ is a $(t+1)$-CCA, $A$ is also a
$(\overline{t+1})$-CCA according to the definition. There is at least one test
case in $A$ that covers $T$, i.e., $\rho_{A}(T)\neq\emptyset$ and
$\rho_{A}(\mathcal{T})=\emptyset$. Therefore, $T$ is not masked by
$\mathcal{T}$ in $A$.
$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$
holds in $A$.

Situation 2: $T\neq\emptyset\land\mathcal{T}\neq\emptyset$. Now we let
$\mathcal{F}(T)$ denote the parameter set of the interaction $T$.
$0<|\mathcal{F}(T)|,|\mathcal{F}(T^{\prime})|\leq t$. Based on the parameter
set of interactions $\mathcal{F}$, the situation can be divided into three
cases.

Case 1: $\mathcal{F}(T^{\prime})\subset\mathcal{F}(T)$. Some parameters are
assigned different values in $T$ and $T^{\prime}$. Otherwise
$\mathcal{T}=\\{T^{\prime}\\}\succ T$. Both $T$ and $T^{\prime}$ are
interactions with strength not larger than $t$, and $A$ is a $(t+1)$-CCA,
$\rho_{A}(T),\rho_{A}(T^{\prime})\neq\emptyset$ and
$\forall\boldsymbol{\sigma}\in A:T^{\prime}\not\subset\boldsymbol{\sigma}$.
Therefore,
$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$
holds in $A$.

Case 2: $\mathcal{F}(T^{\prime})\not\subset\mathcal{F}(T)$. There are at least
one parameter $F_{e}$ in $T^{\prime}$ that $F_{e}\not\in T$. Because
$\mathcal{T}\not\succ T$,
$\exists\boldsymbol{\sigma}\in\mathcal{R}:T\subset\boldsymbol{\sigma}\land
T^{\prime}\not\subset\boldsymbol{\sigma}$. Clearly, the assigned value of
$F_{e}$ in $\boldsymbol{\sigma}$ is different from the assigned value in
$T^{\prime}$. Also because $\boldsymbol{\sigma}$ is a valid test case, all its
covering interactions with strength from 0 to $k$ are valid. Now we attach the
parameter $F_{e}$ and its value in $\boldsymbol{\sigma}$,
$\boldsymbol{\sigma}(F_{e})$, to $T$ to construct a $(t+1)$-way interaction,
$T_{e}$. $T_{e}$ is a valid interaction because it is covered by
$\boldsymbol{\sigma}$. $A$ is a $(1+t)$-CCA. There are at least one test case
$\boldsymbol{\sigma}_{e}$ in $A$ that covers $T_{e}$. Hence,
$\boldsymbol{\sigma}_{e}\in\rho_{A}(T)\land\boldsymbol{\sigma}_{e}\not\in\rho_{A}(T^{\prime})=\rho_{A}(\mathcal{T})$.
Therefore,
$T\in\mathcal{T}\Leftrightarrow\rho_{A}(T)\subseteq\rho_{A}(\mathcal{T})$
holds in $A$.

####  4.2.1 The CDA generation algorithm

Theorem 3.12 shows that a $(d+t)$-CCA is already a $(d,t)$-CDA. Based on the
theorem, we devise a two-step heuristic algorithm (Algorithm 2). The algorithm
generates a $(d+t)$-CCA first. Then it repeatedly chooses a test case in it at
random and checks whether it is removable. Here we say that a test case is
removable from an array if a new array with the test case being removed would
still be a $(d,t)$-CDA. If the test case is removable, then it is removed from
the current array. Otherwise, a new test case is chosen and the check is
performed again. This process is repeated until no test case is removable
anymore. algorithm[tb] The two-step heuristic generation method  Input: SUT
${\cal M}$

Output: A ($d,t$)-CDA $A$

// construct a (d+t)-CCA for the input SUT
$S\leftarrow\textit{CCAGenerator}({\cal M},d+t)$ // get all t-way interactions
from the $(d+t)$-CCA ${\cal VI}_{t}\leftarrow\textit{getAllInteractions}(A,t)$
${\cal VI}map\leftarrow\textit{mapInteractionsToTestcases}({\cal VI}_{t},A)$
${\cal P}\leftarrow\textit{getPairs}({\cal VI}map)$ $A\leftarrow\emptyset$
while  _$S\not=\emptyset$_ do

11 $\boldsymbol{\sigma}$ $\leftarrow$ getRandomTestcase($S$) $S\leftarrow
S-\boldsymbol{\sigma}$ ${\cal
VI}map^{\prime}\leftarrow\textit{getNewMapping}({\cal
VI}map,\boldsymbol{\sigma})$
${\cal{P}}^{\prime}\leftarrow\textit{getPairs}({\cal VI}map^{\prime})$ if
_${\cal{P}}\not={\cal{P}}^{\prime}$_ then

// the test case $\boldsymbol{\sigma}$ is unremovable $A\leftarrow
A+\boldsymbol{\sigma}$

12 else

// the test case $\boldsymbol{\sigma}$ is removable ${\cal
VI}map\leftarrow{\cal VI}map^{\prime}$

13

return _$A$_

Input: SUT $\mathcal{M}=\langle\mathcal{F},\mathcal{S},\phi\rangle$; integers
$d$, $t$

Output: ($d,t$)-CDA $A$

// construct a $(d+t)$-CCA for the input SUT

1 $S\leftarrow\textit{generateCCA}({\cal M},d+t)$

// get all t-way interactions from the $(d+t)$-CCA

2 ${\cal VI}_{t}\leftarrow\textit{getAllInteractions}(S,t)$

// $Rows[T]=\rho_{S}(T)$ for $T\in VI_{t}$

3 $\textit{Rows}[]\leftarrow\textit{mapInteractionToRows}({\cal VI}_{t},S)$

// $\textit{DiffRows}[{\cal T}][T]=\rho_{S}(T)-\rho_{S}(\mathcal{T})$ for
$\mathcal{T}\subseteq\mathcal{VI}_{t},|\mathcal{T}|=d$

4 $\textit{DiffRows}[][]\leftarrow\textit{getDiffRows}({\cal VI}_{t},S,d)$

5 $A\leftarrow S$

6 while  _$A\not=\emptyset$_ do

7 $\boldsymbol{\sigma}$ $\leftarrow$ getRandomTestcase($S$)

8 $S\leftarrow S-\\{\boldsymbol{\sigma}\\}$

9 $A\leftarrow A-\\{\boldsymbol{\sigma}\\}$

10
$\textit{DiffRows}^{\prime}[][]\leftarrow\textit{update}(\textit{DiffRows}[][],\boldsymbol{\sigma})$

11 if  _$\exists\mathcal{T},T:\textit{DiffRows}[\mathcal{T}][T]\neq\emptyset$
and $\textit{DiffRows}^{\prime}[\mathcal{T}][T]=\emptyset$_ then

// the test case $\boldsymbol{\sigma}$ is unremovable

12 $S\leftarrow S+\\{\boldsymbol{\sigma}\\}$

13

14 else

// the test case $\boldsymbol{\sigma}$ is removable

15 $\textit{DiffRows}[][]\leftarrow\textit{DiffRows}^{\prime}[][]$

16

17

return _$A$_

Algorithm 2 The two-step heuristic generation algorithm  The algorithm works
in detail as follows. In line 1 the algorithm generates a $(d+t)$-CCA $S$. At
this point, $S$ is already a $(d,t)$-CDA but contains many redundant test
cases. Then the algorithm collects all valid $t$-way interactions and maps
each interaction $T$ to its covering test cases $\rho_{S}(T)$ in $S$ (line 2).
The map obtained here, denoted by $Rows[]$, is used to compute another map,
$\textit{DiffRows}[][]$, that associates each pair of an interaction set
$\mathcal{T}$ and a valid interaction $T$ with
$\rho_{S}(T)-\rho_{S}(\mathcal{T})$. Note that
$\rho_{S}(T)-\rho_{S}(\mathcal{T})=\emptyset$ iff
$\rho_{S}(T)\subseteq\rho_{S}(\mathcal{T})$. Since $S$ is a CDA,
$\textit{DiffRows}[\mathcal{T}][T]=\emptyset$ if $\mathcal{T}\succ T$;
$\textit{DiffRows}[\mathcal{T}][T]\not=\emptyset$ otherwise. Then the
algorithm repeatedly chooses a test case at random and checks whether it is
removable or not. To perform the check, the algorithm constructs a new
interaction-to-row map $\textit{DiffRows}[][]$ that would hold after the test
case was removed (line 9). This can be done by simply removing
$\mathbf{\sigma}$ from all $\textit{DiffRows}[\mathcal{T}][T]$. Subsequently,
the algorithm compares the two maps (line 10). If
$\textit{DiffRows}[\mathcal{T}][T]\not=\emptyset$ but
$\textit{DiffRows}^{\prime}[\mathcal{T}][T]=\emptyset$, then
$\rho_{S}(T)\subseteq\rho_{S}(\mathcal{T})$ and thus $S$ is no longer a CDA.
In this case, the algorithm reserves the test case (line 12). Otherwise, it
deletes the test case and accordingly updates
$\textit{DiffRows}[\mathcal{T}][T]$ (line 14). When all test cases in the CCA
are checked, the algorithm will terminate, yielding the resulting $S$. Let
$s=\max_{1\leq i\leq k}{|S_{i}|}$. Outside the while loop, line 4 has the
highest time complexity. It is $O((s^{t}k^{t})^{d}s^{t}k^{t}n)$, since
$|\mathcal{VI}_{t}|\leq s^{t}k^{t}$, $|\rho_{S}()|\leq n$. Inside the while
loop, line 10 and line 11 has the highest complexity
$O((s^{t}k^{t})^{d}s^{t}k^{t}n)$ for the same reason. And let $n$ be the size
of the initial CCA. As a result, the algorithm’s time complexity is
$O((s^{t}k^{t})^{d}s^{t}k^{t}n^{2})$. When $s,t$, and $d$ are fixed, the
complexity is polynomial in $k$ and $n$.

##  5 Experiments

In this section we show the results of experiments to evaluate the two
proposed algorithms presented in the previous section. We focus on generation
of $(1,2)$-CDAs ($d=1$, $t=2$) for the following reasons. First, by nature of
CDAs no interactions can be erroneously identified as non-faulty even when
more than $d$ interactions are faulty; thus it is natural to set a small value
to $d$ in practice. Second, the most common form of CIT targets two-way
interactions (this form of CIT is called _pair-wise testing_.)

###  5.1 Experiment settings

Table 2: Benchmark Information ID | SUT | $|\mathcal{F}|$ | $|\phi|$ | $|\mathcal{VI}_{2}|$ | $|\mathcal{I}_{2}\backslash\mathcal{VI}_{2}|$ | $|\mathcal{T}\succ T|$
---|---|---|---|---|---|---
1 | car | 9 | 15 | 102 | 42 | 1,487
2 | graph_product_line | 20 | 45 | 499 | 261 | 37,212
3 | real_fm | 14 | 23 | 275 | 89 | 5,368
4 | aircraft_fm | 13 | 19 | 239 | 73 | 2,647
5 | connector_fm | 20 | 37 | 537 | 223 | 49,038
6 | movies_app_fm | 13 | 23 | 211 | 101 | 4,968
7 | stack_fm | 17 | 28 | 465 | 79 | 6,399
8 | banking1 | 5 | 112 | 102 | 0 | 0
9 | banking2 | 15 | 3 | 473 | 3 | 208
10 | comm_protocol | 11 | 128 | 285 | 35 | 2,177
11 | concurrency | 5 | 7 | 36 | 4 | 130
12 | healthcare1 | 10 | 21 | 361 | 8 | 512
13 | healthcare2 | 12 | 25 | 466 | 1 | 124
14 | healthcare3 | 29 | 31 | 3,092 | 59 | 8,700
15 | healthcare4 | 35 | 22 | 5,707 | 38 | 3,359
16 | insurance | 14 | 0 | 4,573 | 0 | 0
17 | network_mgmt | 9 | 20 | 1,228 | 20 | 189
18 | processor_comm1 | 15 | 13 | 1,058 | 13 | 1,510
19 | processor_comm2 | 25 | 125 | 2,525 | 854 | 35,156
20 | services | 13 | 388 | 1,819 | 16 | 1,088
21 | storage1 | 4 | 95 | 53 | 18 | 112
22 | storage2 | 5 | 0 | 126 | 0 | 0
23 | storage3 | 15 | 48 | 1,020 | 120 | 3,400
24 | storage4 | 20 | 24 | 3,491 | 24 | 0
25 | storage5 | 23 | 151 | 5,342 | 246 | 10,095
26 | system_mgmt | 10 | 17 | 310 | 14 | 825
27 | telecom | 10 | 21 | 440 | 11 | 151

We wrote C++ programs that implement the two algorithms. Our implementation
[10] of the IPOG algorithm [6] was used as a CCA generator for both
algorithms, while the Z3 solver (version 4.8.1) was used in the
satisfiability-based algorithms. We performed experiments with a total of 27
benchmark instances, numbered from 1 to 27. Benchmarks No. 1 to 7 are taken
from [11] which are provided as part of the CitLab tool. Benchmarks No. 8 to
27 can be found in [12]. The detailed information of these benchmark instances
is shown in Table 2. In Table 2, the columns labeled with $|\mathcal{F}|$ and
$|\phi|$ show the number of parameters and the number of constraints ($\phi$
is the conjunction of the constraints). Columns $|\mathcal{VI}_{2}|$ and
$|\mathcal{I}_{2}\backslash\mathcal{VI}_{2}|$ show respectively the number of
valid interactions and the number of invalid interactions. The last column
labeled $|\mathcal{T}\succ T|$ shows the number of pairs of an interaction set
$\mathcal{T}$ and an interaction $T$ such that $\mathcal{T}$ masks $T$. For
instance, the first line in the table shows that the benchmark car has 9
parameters with 15 constraints. In the test space there are 102 valid
interactions and 42 invalid interactions. Among the valid interactions, there
are 1,487 pairs of an interaction set and an interaction such that the
interaction set masks the interaction. All experiments were conducted on a
machine with Intel Core i7-8700 CPU, 64 GB memory and Ubuntu 18.04 LTS OS. For
each benchmark instance, the two generation algorithms were executed five
times. The timeout period for each run was set to 1800 seconds.

###  5.2 Experimental results

Table 3: Experimental results. Numbers with $*$ indicate that the algorithm
did not terminate within the time limit, in which case the CDAs obtained are
not necessarily minimum.

ID Time (second) Size SMT Two-step SMT Two-step avg. max. min. avg. avg. max.
min. avg. 1 2.58 0.12 0.07 0.08 12 12 12 12 2 – 0.18 0.13 0.15 – 26 26 26 3
806.21* 0.16 0.11 0.13 28* 31 30 30.40 4 268.75* 0.10 0.09 0.10 14* 18 18 18 5
88.06* 0.17 0.12 0.14 18* 18 18 18 6 6.41 0.12 0.09 0.10 9 10 10 10 7 357.50*
0.18 0.13 0.15 34* 33 33 33 8 1557.89* 0.15 0.10 0.13 25* 37 36 36.40 9 – 0.12
0.09 0.11 – 42 42 42 10 – 0.21 0.15 0.17 – 50 47 48.60 11 0.364 0.10 0.07 0.08
8 8 8 8 12 – 0.17 0.12 0.14 – 95 92 94 13 – 0.20 0.16 0.18 – 60 57 58.20 14 –
3.14 2.79 2.95 – 179 173 176 15 – 19.87 18.73 19.23 – 234 220 227.60 16 –
145.14 130.48 134.31 – 1997 1959 1971.40 17 – 1.56 1.48 1.52 – 405 394 399.40
18 – 0.67 0.59 0.61 – 114 111 112 19 – 3.16 2.94 3.03 – 122 118 120.20 20 –
4.82 4.76 4.79 – 430 413 422.40 21 2.53* 0.12 0.10 0.10 25* 25 25 25 22 – 0.08
0.07 0.07 – 51 45 47.60 23 – 0.64 0.58 0.61 – 189 185 187.60 24 – 16.28 15.61
15.88 – 517 500 506.20 25 – 130.25 120.02 124.86 – 860 843 851.60 26 – 0.12
0.09 0.11 – 53 49 51.80 27 – 0.19 0.14 0.16 – 102 98 99.8

The results of the experiments are summarized in Table 3. The leftmost column
shows the benchmark IDs. The rest of the table is divided into two parts
representing the results of generation time and the results of sizes of the
generated CDAs. Both parts have two sections describing the experiment results
of the two proposed algorithms respectively. For each problem instance, the
average value is reported for the satisfiability-based algorithm as it is
deterministic, while the maximum, minimum, and average values are reported for
the two-step heuristic generation algorithm.

The numbers with asterisk (*) in the satisfiability-based algorithm’s columns
show that the generation did not terminate within the time limit. Because the
algorithm repeatedly generates CDAs with sizes varying until the minimum one
is found, CDAs that are not optimal are constructed during the course of
execution. The values with asterisk (*) correspond to the smallest (not
necessarily optimal) CDAs that were obtained within the time limit. For
example, for benchmark No. 3, the algorithm took 806.21 seconds to generate a
CDA of size 28. However, when it was trying to generate a CDA of size 27, the
run of the algorithm exceeded the 1800 second time limit. There are also some
benchmark instances that the algorithm did not find even one CDA within the
time limit. We use the symbol “–” to indicate such a case. To compare the
average consumed time of the two algorithms, the better results (i.e., the
shorter time) are denoted in bold font. The smaller average sizes of generated
CDAs are also denoted in bold font.

The satisfiability-based algorithm completed the generation process for three
instances, namely, No. 1, 6, and 11. The CDAs obtained for these instances are
all optimal. The algorithm was able to find small CDAs for some remaining
instances (though it timed out), whereas it failed to find even a single CDA
for others. In contrast, the two-step algorithms successfully generated CDAs
for all benchmark instances. In addition, the execution time of the
satisfiability-based algorithm was always much longer than the other
algorithm, sometimes three orders of magnitude longer. There are two main
reasons why the satisfiability-based algorithm is so slow. One reason is that
the algorithm generates multiple CDAs in a single run. As stated in Section 4,
it generates $(d,t)$-CDAs with sizes varying from the size of a $(d+t)$-CCA.
The CCA’s size simply serves as the upper bound on the minimum CDA size: As it
is not tight bound in general, to obtain an optimal $(d,t)$-CDA, the
satisfiability solver is executed multiple times. The other reason, which is
more obvious, is that satisfiability check may be time-consuming. The time
required for the check becomes very long especially when the algorithm tries
to find a CDA of minimum size minus 1, in which case the answer of the check
is UNSAT (unsatisfiable). In the field of satisfiability, it is well known
that UNSAT instances are usually more difficult than SAT instances.

The satisfiability-based algorithm is deterministic. As stated above, the CCA
size affects the algorithm’s execution time and, if timeout occurs, the
resulting CDA size. In contrast, the two-step heuristic algorithm is
inherently nondeterministic: it generates different CDAs for different runs.
The algorithm decreases the array size by repeatedly removing from the current
array a test case selected at random (line 7, Algorithm 2). A test case can be
removed only if the array remains to be a CDA after its removal; thus which
test case is removed depends strongly on earlier selections. or example,
suppose that there are two unmasking pairs, $\mathcal{T}_{1}\not\succ T_{a}$
and $\mathcal{T}_{2}\not\succ T_{b}$ whose covering test cases in the current
array $A$ are as follows.

$\displaystyle\rho_{A}(\mathcal{T}_{1})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3}\\}\qquad\rho_{A}(T_{a})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{5}\\}$
$\displaystyle\rho_{A}(\mathcal{T}_{2})=\\{\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3},\boldsymbol{\sigma}_{5}\\}\qquad\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{5},\boldsymbol{\sigma}_{6}\\}$

If the test cases that are chosen to delete are in the order of
$\boldsymbol{\sigma}_{1}\rightarrow\boldsymbol{\sigma}_{2}$, the judgements on
deletion are as follows.

$\displaystyle\textrm{delete
}\boldsymbol{\sigma}_{1}\rightarrow\textrm{deletable}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{1})=\\{\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3}\\},\rho_{A}(T_{a})=\\{\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{5}\\}:\boldsymbol{\sigma}_{5}\textrm{
reserves the unmasking relation}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{2})=\\{\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3},\boldsymbol{\sigma}_{5}\\},\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{5},\boldsymbol{\sigma}_{6}\\}:\boldsymbol{\sigma}_{6}\textrm{
reserves the unmasking relation}$ $\displaystyle\textrm{delete
}\boldsymbol{\sigma}_{2}\rightarrow\textrm{deletable}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{1})=\\{\boldsymbol{\sigma}_{3}\\},\rho_{A}(T_{a})=\\{\boldsymbol{\sigma}_{5}\\}:\boldsymbol{\sigma}_{5}\textrm{
reserves the unmasking relation}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{2})=\\{\boldsymbol{\sigma}_{3},\boldsymbol{\sigma}_{5}\\},\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{5},\boldsymbol{\sigma}_{6}\\}:\boldsymbol{\sigma}_{6}\textrm{
reserves the unmasking relation}$

Both of the chosen test cases are deleted. However, if the test cases that are
chosen to delete are in the order of
$\boldsymbol{\sigma}_{6}\rightarrow\boldsymbol{\sigma}_{5}$, the judgements
are as follows.

$\displaystyle\textrm{delete
}\boldsymbol{\sigma}_{6}\rightarrow\textrm{deletable}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{1})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3}\\},\rho_{A}(T_{a})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{5}\\}:\boldsymbol{\sigma}_{5}\textrm{
reserves the unmasking relation}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{2})=\\{\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3},\boldsymbol{\sigma}_{5}\\},\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{5}\\}:\boldsymbol{\sigma}_{1}\textrm{
reserves the unmasking relation}$ $\displaystyle\textrm{delete
}\boldsymbol{\sigma}_{5}\rightarrow\textrm{undeletable}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{1})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3}\\},\rho_{A}(T_{a})=\\{\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2}\\}:T_{a}\textrm{
becomes masked by }\mathcal{T}_{1}$
$\displaystyle\qquad\rho_{A}(\mathcal{T}_{2})=\\{\boldsymbol{\sigma}_{2},\boldsymbol{\sigma}_{3}\\},\rho_{A}(T_{b})=\\{\boldsymbol{\sigma}_{1}\\}:\boldsymbol{\sigma}_{1}\textrm{
reserves the unmasking relation}$

Only one test case is deleted in this case. Hence, different orders in which
test cases are deleted lead to different CDAs.

Another observation is that the two-step heuristic algorithm generated smaller
CDAs than the satisfiability-based algorithm for No. 7. For the case, the
satisfiability-based algorithm ran out of time before searching for minimum or
near minimum CDAs. In view of these, we conclude that the two-step heuristic
algorithm has balanced capabilities with respect to running time and CDA sizes
it generates.

##  6 Threats to Validity

The experimental results about the two CDA generation algorithms showed that
the scalability of the satisfiability-based algorithm is substantially
limited, especially when comparing to the heuristic algorithm. This conclusion
heavily relies on the performance of the satisfiability solver used in the
implementation. Although Z3, which we adopted in our implementation, is one of
the best known and fastest SMT solvers, solvers of SMT or similar problems,
such as SAT, have seen constant progress. Hence the difference between the two
algorithms might narrow in near future.

The problem instances used in the experiments are well-known and have been
used in many other studies; However, they do not necessarily capture the
characteristics of all real-world problems. Although we believe that the
algorithms’ qualitative properties observed in the experiments are likely to
hold in general, there can be new problems for which they do not hold.

##  7 Related Work

CIT has been widely used for many years. In the practice of CIT, constraint
handling has always been a vital issue. Surveys about constraint handling for
CIT include [13, 14, 15].

DAs, as well as LAs, were first introduced by Colbourn and McClary in [3].
They analyzed the mathematical properties of these arrays. As [3], most of the
studies on DAs and LAs focus on their mathematical aspects [16, 17, 18, 19,
20, 21]. The application to screening experiments for TCP throughput in a
mobile wireless network was reported in [22, 23]. Other types of arrays that
are intended for fault location include _Error Locating Arrays_ [24] and
_Consecutive Detecting Arrays_ [25].

The concept of CLAs was first introduced in [26]. Later a computational
construction algorithm was proposed in [27]. In [7] the results of applying
CLAs to fault localization for real-world programs were reported.

The present paper extends our earlier works: [28] and [29]. In [28] we
introduced $(d,t)$-CDAs for the first time, together with a construction
algorithm using an SMT-solver. The present paper introduces the other variants
of CDAs, clarifies their relations, and refines the algorithm. The two-step
heuristic algorithm was first proposed in [29]. In the current paper, we
improved the implementation of the algorithm and conducted a new set of
experiments to compare the two different algorithms with the new
implementations.

There are many other approaches to faulty interaction localization without
using CDAs or other related arrays. One of such approaches is the use of
adaptive testing [30, 31, 32, 33, 34, 35, 36, 37]. In adaptive testing, when a
failure is encountered, new test cases are adaptively generated and executed
to narrow down possible causes. On the other hand, testing using CDAs is
nonadaptive in the sense that test outcomes do not alter future test plans. A
clear benefit of using nonadaptive testing is the execution of test suites,
which is often the most time-consuming part of the whole testing process, can
be parallelized.

CDAs and other arrays of similar kinds are intended to provide sufficient test
outcomes to uniquely identify faulty interactions. On the other hand, some
studies attempt to infer faulty interactions from insufficient information
with, for example, machine learning. The studies in this line include [38, 39,
40].

For other approaches to identification of faulty interactions, readers are
referred to a recent survey [41].

##  8 Conclusion

In this paper, we introduced the notion of Constrained Detecting Arrays
(CDAs), which incorporates constraints among test parameters into Detecting
Arrays (DAs). CDAs generalize DAs so that localization of faulty interactions
can be performed for systems with constraints. We proved several properties of
CDAs as well as those that relate CDAs with other array structures, such as
Constrained Covering Arrays (CCAs) and Constrained Locating Arrays (CLAs). We
then proposed two generation algorithms. The first algorithm generates optimal
CDAs using an off-the-shelf satisfiability solver. The second algorithm is
heuristic and generates near-optimal CDAs in a reasonable time. The
experimental results of both algorithms indicated that the heuristic algorithm
can scale to problems of practical sizes.

There are several possible directions for future work. One direction is to
apply CDAs to the testing of real-world programs to identify faulty
interactions. The development of new algorithms for CDA construction also
deserves further study. We believe that both meta-heuristic search and greedy
heuristics may be promising because they have proved to be useful for the
construction of CCAs. A recent study attempts to provide a systematic
framework to compare CCA generators [42]. Applying such a framework to compare
different CDA construction algorithms is also of interest.

## References

  * Kuhn et al. [2013] D. R. Kuhn, R. N. Kacker, Y. Lei, Introduction to combinatorial testing, CRC Press, 2013.
  * Kuhn and Wallace [2004] D. R. Kuhn, D. R. Wallace,  Software fault interactions and implications for software testing,  IEEE Transactions on Software Engineering 30 (2004) 418–421.
  * Colbourn and McClary [2008] C. J. Colbourn, D. W. McClary,  Locating and detecting arrays for interaction faults,  Journal of Combinatorial Optimization 15 (2008) 17–48.
  * Lin et al. [2015] J. Lin, C. Luo, S. Cai, K. Su, D. Hao, 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), ACM/IEEE, 2015, pp. 494–505.
  * Shiba et al. [2004] T. Shiba, T. Tsuchiya, T. Kikuno,  Using artificial life techniques to generate test cases for combinatorial testing,  in: Proc. of 28th Annual International Computer Software and Applications Conference (COMPSAC ’04), 2004, pp. 71–77.
  * Lei et al. [2008] Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, J. Lawrence,  Ipog/ipog-d: efficient test generation for multi-way combinatorial testing,  Software Testing, Verification and Reliability 18 (2008) 125–148.
  * Jin and Tsuchiya [2020] H. Jin, T. Tsuchiya,  Constrained locating arrays for combinatorial interaction testing,  Journal of Systems and Software 170 (2020) 110771.
  * Hu et al. [2020] L. Hu, W. E. Wong, D. R. Kuhn, R. N. Kacker,  How does combinatorial testing perform in the real world: an empirical study,  Empirical Software Engineering 25 (2020) 2661–2693.
  * Hnich et al. [2006] B. Hnich, S. D. Prestwich, E. Selensky, B. M. Smith,  Constraint models for the covering test problem,  Constraints 11 (2006) 199–219.
  * Tsuchiya [2019] T. Tsuchiya,  Using binary decision diagrams for constraint handling in combinatorial interaction testing,  CoRR abs/1907.01779 (2019).
  * Gargantini and Vavassori [2012] A. Gargantini, P. Vavassori,  CitLab: A laboratory for combinatorial interaction testing,  in: 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation, 2012, pp. 559–568. doi:10.1109/ICST.2012.141.
  * Segall et al. [2011] I. Segall, R. Tzoref-Brill, E. Farchi,  Using binary decision diagrams for combinatorial test design,  in: Proc. of the 2011 International Symposium on Software Testing and Analysis (ISSTA), ACM, 2011, pp. 254–264.
  * Ahmed et al. [2017] B. S. Ahmed, K. Z. Zamli, W. Afzal, M. Bures,  Constrained interaction testing: A systematic literature study,  IEEE Access 5 (2017) 1–1.
  * Wu et al. [2019a] H. Wu, C. Nie, J. Petke, Y. Jia, M. Harman, A survey of constrained combinatorial testing, 2019a. arXiv:1908.02480.
  * Wu et al. [2019b] H. Wu, N. Changhai, J. Petke, Y. Jia, M. Harman,  Comparative analysis of constraint handling techniques for constrained combinatorial testing,  IEEE Transactions on Software Engineering (2019b) 1--1.
  * Colbourn and Syrotiuk [2018] C. J. Colbourn, V. R. Syrotiuk,  On a combinatorial framework for fault characterization,  Mathematics in Computer Science 12 (2018) 429--451.
  * Compton et al. [2016] R. Compton, M. T. Mehari, C. J. Colbourn, E. De Poorter, V. R. Syrotiuk,  Screening interacting factors in a wireless network testbed using locating arrays,  in: 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2016, pp. 650--655. doi:10.1109/INFCOMW.2016.7562157.
  * Seidel et al. [2018] S. A. Seidel, K. Sarkar, C. J. Colbourn, V. R. Syrotiuk,  Separating interaction effects using locating and detecting arrays,  in: C. Iliopoulos, H. W. Leong, W.-K. Sung (Eds.), Combinatorial Algorithms, Springer International Publishing, Cham, 2018, pp. 349--360.
  * Shi et al. [2012a] C. Shi, Y. Tang, J. Yin,  Optimal locating arrays for at most two faults,  Science China Mathematics 55 (2012a) 197--206.
  * Shi et al. [2012b] C. Shi, Y. Tang, J. Yin,  The equivalence between optimal detecting arrays and super-simple OAs,  Designs, Codes and Cryptography 62 (2012b) 131--142.
  * Lu and Jimbo [2019] X.-N. Lu, M. Jimbo,  Arrays for combinatorial interaction testing: a review on constructive approaches,  Japanese Journal of Statistics and Data Science 2 (2019) 641--667.
  * Aldaco et al. [2015] A. N. Aldaco, C. J. Colbourn, V. R. Syrotiuk,  Locating arrays: A new experimental design for screening complex engineered systems,  SIGOPS Oper. Syst. Rev. 49 (2015) 31--40.
  * Colbourn and Syrotiuk [2016] C. J. Colbourn, V. R. Syrotiuk,  Coverage, location, detection, and measurement,  in: 2016 IEEE Ninth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2016, pp. 19--25. doi:10.1109/ICSTW.2016.38.
  * Martínez et al. [2010] C. Martínez, L. Moura, D. Panario, B. Stevens,  Locating errors using ELAs, covering arrays, and adaptive testing algorithms,  SIAM Journal on Discrete Mathematics 23 (2010) 1776--1799.
  * Shi et al. [2020] C. Shi, L. Jiang, A. Tao,  Consecutive detecting arrays for interaction faults,  Graphs and Combinatorics 36 (2020) 1203--1218.
  * Jin et al. [2018] H. Jin, T. Kitamura, E.-H. Choi, T. Tsuchiya,  A satisfiability-based approach to generation of constrained locating arrays,  in: 2018 IEEE International Conference on Software Testing, Verification and Validation Workshops, 2018, pp. 285--294. doi:10.1109/ICSTW.2018.00062.
  * Jin and Tsuchiya [2018] H. Jin, T. Tsuchiya,  Deriving fault locating test cases from constrained covering arrays,  in: 2018 IEEE 23rd Pacific Rim International Symposium on Dependable Computing (PRDC), 2018, pp. 233--240. doi:10.1109/PRDC.2018.00044.
  * Jin et al. [2020] H. Jin, C. Shi, T. Tsuchiya,  Constrained detecting arrays for fault localization in combinatorial testing,  in: Proceedings of the 35th Annual ACM Symposium on Applied Computing, SAC ’20, Association for Computing Machinery, New York, NY, USA, 2020, p. 1971–1978. URL: https://doi.org/10.1145/3341105.3373952. doi:10.1145/3341105.3373952.
  * Jin and Tsuchiya [2020] H. Jin, T. Tsuchiya,  A two-step heuristic algorithm for generating constrained detecting arrays for combinatorial interaction testing,  in: 2020 IEEE 29th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2020, pp. 219--224. doi:10.1109/WETICE49692.2020.00050.
  * Wang et al. [2010] Z. Wang, B. Xu, L. Chen, L. Xu,  Adaptive interaction fault location based on combinatorial testing,  in: 2010 10th International Conference on Quality Software, 2010, pp. 495--502. doi:10.1109/QSIC.2010.36.
  * Zhang and Zhang [2011] Z. Zhang, J. Zhang,  Characterizing failure-causing parameter interactions by adaptive testing,  in: Proceedings of the 20th International Symposium on Software Testing and Analysis, ISSTA 2011, Toronto, ON, Canada, July 17-21, 2011, 2011, pp. 331--341. URL: https://doi.org/10.1145/2001420.2001460. doi:10.1145/2001420.2001460.
  * Li et al. [2012] J. Li, C. Nie, Y. Lei,  Improved delta debugging based on combinatorial testing,  in: 2012 12th International Conference on Quality Software, Xi’an, Shaanxi, China, August 27-29, 2012, 2012, pp. 102--105. URL: https://doi.org/10.1109/QSIC.2012.28. doi:10.1109/QSIC.2012.28.
  * Arcaini et al. [2019] P. Arcaini, A. Gargantini, M. Radavelli,  Efficient and guaranteed detection of t-way failure-inducing combinations,  in: 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2019, pp. 200--209. doi:10.1109/ICSTW.2019.00054.
  * Bonn et al. [2019] J. Bonn, K. Foegen, H. Lichter,  A framework for automated combinatorial test generation, execution, and fault characterization,  in: 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2019, pp. 224--233. doi:10.1109/ICSTW.2019.00057.
  * Niu et al. [2020] X. Niu, C. Nie, H. Leung, Y. Lei, X. Wang, J. Xu, Y. Wang,  An interleaving approach to combinatorial testing and failure-inducing interaction identification,  IEEE Trans. Softw. Eng. 46 (2020) 584–615.
  * Niu et al. [2013] X. Niu, C. Nie, Y. Lei, A. T. S. Chan,  Identifying failure-inducing combinations using tuple relationship,  in: 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation Workshops, 2013, pp. 271--280. doi:10.1109/ICSTW.2013.38.
  * Niu et al. [2021] X. Niu, H. Wu, N. Changhai, Y. Lei, X. Wang,  A theory of pending schemas in combinatorial testing,  IEEE Transactions on Software Engineering (2021) 1--1.
  * Yilmaz et al. [2006] C. Yilmaz, M. B. Cohen, A. A. Porter,  Covering arrays for efficient fault characterization in complex configuration spaces,  IEEE Trans. Software Eng. 32 (2006) 20--34.
  * Shakya et al. [2012] K. Shakya, T. Xie, N. Li, Y. Lei, R. Kacker, D. R. Kuhn,  Isolating failure-inducing combinations in combinatorial testing using test augmentation and classification,  in: Fifth IEEE International Conference on Software Testing, Verification and Validation, ICST 2012, Montreal, QC, Canada, April 17-21, 2012, 2012, pp. 620--623. URL: https://doi.org/10.1109/ICST.2012.149. doi:10.1109/ICST.2012.149.
  * Nishiura et al. [2017] K. Nishiura, E. Choi, O. Mizuno,  Improving faulty interaction localization using logistic regression,  in: 2017 IEEE International Conference on Software Quality, Reliability and Security (QRS), 2017, pp. 138--149. doi:10.1109/QRS.2017.24.
  * Friedrichs et al. [2020] T. Friedrichs, K. Fögen, H. Lichter,  A comparison infrastructure for fault characterization algorithms,  in: 2020 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2020, pp. 201--210. doi:10.1109/ICSTW50294.2020.00042.
  * Bombarda et al. [2021] A. Bombarda, E. Crippa, A. Gargantini,  An environment for benchmarking combinatorial test suite generators,  in: 2021 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2021, pp. 48--56. doi:10.1109/ICSTW52544.2021.00021.