Software Quality Journal
https://doi.org/10.1007/s11219-024-09677-1
RESEARCH

Two improving approaches for faulty interaction localization
using logistic regression analysis
Kinari Nishiura1 · Eun‑Hye Choi2 · Eunjong Choi1 · Osamu Mizuno1
Accepted: 6 February 2024
© The Author(s) 2024

Abstract
Faulty Interaction Localization (FIL) is a process to identify which combination of
input parameter values induced test failures in combinatorial testing. An accurate andfast FIL provides helpful information to fix defects causing the test failure. One typeof conventional FIL approach, which analyzes test results of whole test cases and estimates the suspiciousness of each combination, has two main concerns; (1) the accuracy is not enough, (2) the huge time cost is sometimes needed. In this paper, we propose two novel approaches to improve those concerns. FROGa attempts to estimate
suspiciousness more accurately using logistic regression analysis. FROGb attempts toestimate failure-inducing combinations at high speed by estimating the subsets of themusing logistic regression analysis and exploring just their supersets. Through evaluation experiments using a large number of artificial test results based on several real
software systems, we observed that FROGa has very high accuracy, and FROGb can
drastically reduce time cost for targets that have been difficult to complete by the conventional method.
Keywords Software testing · Combinatorial testing · Faulty interaction localization ·Logistic regression analysis* Kinari Nishiurak-nishiura@kit.ac.jp
Eun‑Hye Choie.choi@aist.go.jp
Eunjong Choi
echoi@kit.ac.jp
Osamu Mizuno
o-mizuno@kit.ac.jp
1

Kyoto Institute of Technology, Kyoto, Japan

2

National Institute of Advanced Industrial Science and Technology (AIST), Ikeda, Japan

13

Vol.:(0123456789)

Software Quality Journal

1 Introduction
Software testing plays an essential role in guaranteeing the behavior of software systems.
However, modern software systems are getting more and more large-scale and complicated. Testing them is tough work because the system behaviors are affected by many factors, e.g., various input parameters and settings. Even worse, defects are sometimes caused
by interactions between multiple factors rather than a single factor. However, testing allinteractions of factors is impractical, especially for modern industrial software.
Combinatorial testing (Nie & Leung, 2011; Kuhn et al., 2013) is known as an efficient
black-box testing techniques to detect test failures that occurred by interactions of multiple
factors. Combinatorial testing uses only the minimum number of test cases covering all
possible combinations of input values to satisfy a particular criterion. The cost of software
testing is reduced by focusing on finding defects due to a combination of only a certain
number of factors rather than all input patterns.
However, the combinatorial testing brings a problem about Faulty Interaction
Localization(FIL). The FIL is a process to identify which combination of input parametervalues induced the detected test failures. Identifying the minimum conditions that reproduce test failures will make it easier to identify and repair the defect in a source code.
However, it is not easy to identify such failure-inducing combinations from the combinatorial testing result. Test cases in combinatorial testing are prioritized to include many combinations but not to test specific behaviors. Therefore, it is essential to develop practical
FIL approaches for effective combinatorial testing, e. g., many works are studied (Nie &Leung, 2011; Zhang et al., 2012; Ghandehari et al., 2012; Zeller & Hildebrandt, 2002; Niu
et al., 2020).
BEN Ghandehari et al. (2012) is a powerful existing FIL method, which analyzes the
combinatorial testing results to estimate which combination is most likely to induce failure.
For this purpose, BEN calculates suspiciousness for each possible combination by their algorithm. However, BEN has two concerns: (1) The accuracy of suspiciousness estimation is
not enough. BEN compensates its accuracy with creating and running additional tests, but
increasing accuracy can reduce the cost of additional tests if possible. (2) Analyzing largesize combinations may need an unrealistic processing time due to a combinatorial explosion.
This paper proposes two approaches to improve for each concern in the existing FIL
approach, using logistic regression analysis. Our first approach FROGa focuses on theconcern (1), and our second approach FROGb focuses on the concern (2). The naming of
FROG means "FIL based on Regression coefficient of lOGistic regression."
FROGa aims to calculate the suspiciousness of combinations inducing test failures
more accurately by using logistic regression analysis. FROGa first extracts all possible
failure-inducing combinations of parameter values from test results, then encodes the inclusion relationship between the combinations and each test case. Finnaly, FROGa inputs theencoded data to logistic regression to obtain regression coefficients as the suspiciousnessof each combination.
To evaluate the performance of FROGa, we implemented FROGa and BEN, thenapplied them to the same experimental subjects. As the experimental subjects, we artificially generated many combinatorial testing results to ensure the validity of the evaluation
result. One hundred twenty-six thousand artificial testing results were generated using the
input parameter model of six real software systems and Pict, a combinatorial testing generation tool.

13

Software Quality Journal

According to our experiment, FROGa can identify the input values more accurately than
BEN. This experiment used the artificially generated combinatorial testing results on six realsystems. In the experiments, we obtained the results of the following two research questions(RQ).
RQ1	Does FROGa improve the accuracy of suspiciousness calculation compared to
BEN? Yes. In particular, FROGa can significantly improve the accuracy of ranking
the suspiciousness of combinations in the case of targeted testing results with highcoverage.
RQ2	How much is the difference in the time cost between FROGa and BEN? There islittle difference in time cost between FROGa and BEN.
Next, FROGb aims to directly estimate failure-inducing combinations by estimating the subsets of those combinations. FROGb uses logistic regression analysis to estimate suspicious input
parameter values as subsets of the failure-inducing combination and then explore the supersetof values step by step. Using FROGb, only the most suspicious combinations can be extracted
without dealing with all possible combinations, thus avoiding a combinatorial explosion.
According to our experiment with the same subjects as for FROGa, FROGb can significantly reduce the time cost to find the large size failure-inducing combinations with high accuracy. More specifically, we obtained the results of the following two research questions.
RQ3	How much does FROGb reduce the time of extracting highly suspicious combinations compared toBEN and FROGa? FROGb can significantly reduce the timecompared to BEN and FROGa in the case of targetting testing results with highcoverage.
RQ4	How accurately can FROGb extract failure-inducing combinations? FROGb can
extract all failure-inducing combinations in 63.3% of all and can extract at least
one of them in 95.6% of all.
The idea behind FROGb was introduced in our previous work Nishiura et al. (2017),
but this paper provides a more detailed modeling of the approach. Unlike earlier studies thatexamined only a small number of subjects, this paper explores new experimental results,
including trends due to subject characteristics and limitations of defect interaction extraction.
These results are novel contributions. Both FROGa and FROGb follow the same philosophyof using logistic regression analysis for fault localization, and we present them in parallel toenhance mutual understanding.
The rest of this paper is organized as follows: Section 2 gives backgrounds and definitions.
Section 3 introduces the first proposal FROGa, and Section 4 evaluates FROGa. Section 5
introduces the second proposal FROGb, and Section 6 evaluates FROGb. Section 7 discusses
threats for validities. Section 8 introduces related work. Finally, Section 9 concludes this paper.

2 Backgrounds
2.1 Combinatorial testing
Combinatorial testing is one of black-box testing that focuses on the combination of multiple input parameter values (Nie & Leung, 2011; Kuhn et al., 2013). The primary purpose

13

Software Quality Journalof combinatorial testing is to efficiently detect failures caused by the interaction of such
multiple input parameter values. For this purpose, the combinatorial testing methodology
designs a test suite with a few test cases as possible while covering all combinations of input
parameter values below a certain number. A test suite designed in this way is also referred
to as a covering array. A survey Kuhn and Reilly (2003) reported that the upper limit of thenumber of combinations of input values that can induce failures is between four and six.
Therefore, combinatorial testing that focuses on only a few combinations is practical.
The test that attempts to detect failures caused by the interaction of t or fewer input
values using a covering array that covers t or less input parameter values is referred to as at-way testing. In a t-way testing, all combinations of t or fewer parameter values are tested
at least once with a minimum number of test cases. The value of t in the t-way testing isreferred to as the combinatorial coverage in this paper.
We will formally define some issues related to combinatorial testing. First, the input
model of the System Under Test (SUT) for combinatorial testing is modeled in terms ofparameters, their possible values, and the constraints between the parameter values.

Definition 1 (SUT) An SUT model for combinatorial testing is ⟨P, V, 𝜙⟩, where– P is a set of parameters p1 , … , pn with n = |P|,
– V is a collection of Vi (1 ≤ i ≤ n) that is a set of values assigned to a parameter pi , and– 𝜙 is a set of constraints on combinations of parameter values.
A test case is a tuple assigned to each parameter a value that does not violate SUT
constraints.

Definition 2 (Test case) Given an SUT ⟨P, V, 𝜙⟩, a test case is a n-tuple (v1 , … , vn) withn = |P| and vi ∈ Vi (1 ≤ i ≤ n) that does not violate 𝜙. A test suite is a set of test cases.

A schema is a formal representation of a combination of input parameter values. Thisdefinition is initially defined in the previous study Nie and Leung (2011) and is used in the
recent study Niu et al. (2020) as well.

Definition 3 (Schema) For the SUT, the n-tuple (−, vn1 , ..., vnk , ...) is refered to as a
k-degree schema (0 < k ≤ n) when some k parameters have fixed values and other irrelevant parameters are represented as “−”.

Definition 4 (Sub-schema and Super-schema) Let cl be an l-degree schema, cm be an
m-degree schema in SUT and l < m. If all the fixed parameter values in cl are also cm, thencm subsumes cl . In this case, we can also say that cl is a sub-schema of cm, and cm is supershchema of cl , which can be denoted as cl ≺ cm. For example, a 2-degree schema (-, 4, 4, -)is a sub-schema of a 3-degree schema (-, 4, 4, 5), that is, (-, 4, 4, -) ≺ (-, 4, 4, 5).
Example 1 Table 1 shows an example SUT model. This system has five configurable
parameters: CPU, Network, DBMS, OS, and Browser. The first three parameters have
two possible values, and the remaining two parameters have three possible values. Thereis a constraint that we must use CPU ≠ AMD when OS = Mac, and OS = Win must be

13Software Quality Journal
Table 1  Example SUT: An
example SUT modelParameter

ValuesCPU (= p1)

Intel (=1), AMD (=2)

Network (= p2)
DBMS (= p3)
OS (= p4)
Browser (= p5)
Constraint:(OS = Mac) → (CPU ≠ AMD)(Browser = IE) → (OS = Win)

Wifi (=1), LAN (=2)
MySQL (=1), Sybase (=2)
Win (=1), Linux (=2), Mac (=3)
IE (=1), Firefox (=2), Chrome (=3)

used when Browser = IE. In other words, the combinations of the parameter values (Mac,AMD), (Linux, IE), and (Mac, IE) are not allowed.
Table 2 shows the covering array that realizes the 3-way test of the SUT shown in
Table 1 (not including the "result" column). This test suite consists of 20 test cases andincludes all possible 115 3-degree schemas (Intel, Wifi, MySQL, -, -), …, (-, -, Sybase,
Mac, Chrome) at least once in the test cases while satisfying the constraints. On the other
hand, there are 54 possible combinations between these parameter values based on the constraints, and a total of 54 test cases are needed to cover all of them. Therefore, combinatorial testing can significantly reduce the number of test cases as a tradeoff against the coverage criteria.
Table 2  Example Test Result: An
example of 3-way test suite andits testing result of Example SUT

Test case

p1

p2

p3

p4

p5

Result

#1

2

2

1

2

3

pass

#2
#3
#4
#5
#6
#7
#8
#9
#10
#11
#12
#13
#14
#15
#16
#17
#18
#19
#20

1
2
1
2
1
2
1
1
1
1
1
2
1
2
1
1
2
2
2

2
1
2
1
1
2
2
1
2
1
2
2
1
1
1
2
1
2
2

2
1
2
2
2
2
1
1
1
2
1
2
1
2
1
1
1
2
1

1
1
3
1
3
1
1
3
3
2
2
1
1
2
1
1
2
2
1

1
2
2
1
3
2
1
2
3
2
3
3
3
3
1
2
2
2
1

pass
pass
pass
pass
pass
pass
fail
pass
pass
fail
fail
pass
pass
pass
pass
pass
pass
pass
fail

13

Software Quality Journal

2.2 Faulty interaction localization
Faulty Interaction Localization (FIL) is the process of identifying combinations of input
parameter values that induce faulty behavior based on the results of combinatorial tests.
Developers can quickly identify and fix faulty components by identifying the testing input
values that are the minimum requirements to reproduce the faulty behavior.
The purpose of FIL is to identify minimal schemas which induce failures from given combinatorial testing results. We refer to this schema as a failure-inducing schema.

Definition 5 (Failure-inducing schema) A schema s is referred to as a Minimal Failureinducing Schema if all test cases including the schema s always cause a particular failureand none of the sub-schemas of s cause the failure. In this paper, we refer to it as justfailure-inducing schema.
Furthermore, some FIL methods extract all possible failure-inducing schemas from thetotal combinatorial testing result at first and then narrow down the failure-inducing schemas
from these schemas. Such a schema that may be failure-inducing is defined as a candidate
schema.

Definition 6 (Candidate schema) Given test suite T and test oracle R ∶ tc ⊆ T →{𝗉𝖺𝗌𝗌, 𝖿 𝖺𝗂𝗅}, a candidate schema is a schema s such that– there is a test case tc in T such that tc ⊇ s, and– for every test case tc in T such that tc ⊇ s, R(tc) = 𝖿 𝖺𝗂𝗅.
Example 2 In the example system shown in Table 1, a failure occurs when CPU = Inteland OS = Linux. Also, another failure occurs when CPU = AMD, Network = Wifi
and DBMS = Sybase. Therefore, two schemas, the 2-degree schema (1, -, -, 2, -) and the3-degree schema (-, 2, 1, -, 1), are failure-inducing schemas.
Executing the series of test cases shown in Table 2, the four test cases #8, #11, #12, and#20 that include either failure-inducing schema failed. Therefore, the test results as shownin the Result column of Table 2 are obtained. According to the definition of candidate
Table 3  Example Candidate
Schemas: The candidate schemas
extracted from the Example Test
Result13

No.

Candidate schemas1(1, -, -, 2, -)

s2
s3
s4
s5
s6
s7
s8
s9
s10
s11

(1, 1, -, 2, -)(1, 2, -, 2, -)(1, -, 1, 2, -)(1, -, 2, 2, -)(1, -, -, 2, 2)(1, -, -, 2, 3)(2, 2, -, -, 1)(2, -, 1, -, 1)(-, 1, 2, -, 2)(-, 2, 1, -, 1)

Software Quality Journal

schema, extracting all candidate schemas with three degrees or less, there are 11 candidate
schemas, as shown in Table 3. Every candidate schema is numbered from s1 to s11 for later
explanation. The underlined candidate schemas are failure-inducing schemas.

2.3 Logistic regression analysis
Logistic regression is a well-known statistical model for the regression of a binary dependent variable and is mainly used as a supervised machine learning method Cramer (2002). In
the field of software engineering, this model is often used for classifying fault-prone modules
with software metrics (Basili et al., 1996; Briand et al., 2002; Kamei et al., 2016).
The logistic model is represented by the following equation:

Pr(Y = 1|x1 , ⋯ , xn ) =1
1 + e−(b0 +b1 x1 +⋯+bn xn )where x1 , … , xn are the independent variables, b1 , … , bn are their coefficients, b0 is theintercept, Y is the binomial dependent variable that takes 0 or 1, and Pr is the conditional probability that Y = 1 given the values of x1 , … , xn . In the logistic regression, theregression equation is obtained by calculating the values of b1 , … , bn , i.e. regression
coefficients, from the training data so that the error between the conditional probability
and the correct answer value is the smallest. In using this model as a classifier, the test
data is substituted into the regression equation, the conditional probability that the binomial dependent variable is positive is calculated, and the classification result is presented
according to the threshold.
Logistic regression is also used as an analytical data method. In this study, we use theanalytical method. Logistic regression analysis is based on that the regression coefficient
can be viewed as the degree to which the probability Pr is affected by a unit increase in thecorresponding independent variable Peng et al. (2002). A significant regression coefficientindicates that a change in the value of that independent variable has a significant impact on
the variation of the probability Pr. Therefore, a regression coefficient can be regarded as theimportance of the independent variable for that the binary dependent variable is positive.

3 Improved FIL method using logistic regression
3.1 Concept of FROGa
In this section, we propose FROGa as an improved FIL method. FROG is based on the existing FIL method, BEN. BEN calculates and then ranks the suspiciousness of candidate schemas using the original algorithm with several software metrics. On the other hand, FROGa
attempts to rank candidate schemas more accurately by using logistic regression analysis.
We explain the logic that logistic regression analysis can calculate the suspiciousness ofa candidate schema. Remember that a regression coefficient can be regarded as the importance of the independent variable for that the binary dependent variable is positive. Let theindependent variable be binary (1 = included, 0 = not included), representing the inclusion relationship with a test case in a candidate schema. The dependent variable is binary(1 = failed, 0 = passed), representing the test result. In this case, the regression coefficientmeans the impact level that changing the corresponding independent variable change

13Software Quality Journal

from 0 to 1 affected the probability of the test case fails. This independent variable changemeans not including the schema in the test case to including. Therefore, a large regression
coefficient schema is likely to be a failure-inducing schema. Thus, a regression coefficientis expected to determine the magnitude of suspiciousness.

3.2 Model
FROGa needs three inputs: a test suite, the test results for each test case, and k, whichis the assumed maximum degree of failure-inducing schema. It is necessary that the test
results are classified into pass, or fail by some test oracle. Moreover, k is the degree ofschema that a given combinatorial test suite covers.
First, FROGa extracts all candidate schemas whose degree is less than or equal to kfrom the test suite and the results. Let Sk be the set of these candidate schemas.
Next, FROGa creates a data table Φ, representing the inclusion relationship between
every candidate schema in Sk and every test case. Define a function inc(sc, tc) which represents the inclusion of a candidate schema sc in a test case schema st as follows.
{
1 (sc ≺ st)inc(sc, st) =0 (sc ⊀ st).
With the function inc(sc, st), the data table Φ is expressed as follows,⎡ inc(sc1 , st1 ) … inc(scm , st1 ) ⎤
⎥
⋮
⋱
⋮
Φ=⎢
⎥
⎢
⎣ inc(sc1 , stn ) … inc(scm , stn ) ⎦where m is the number of extracted candidate schemas i. e. |Sk |, and n is the number of test
cases in the test suite. The columns of Φ correspond to each candidate schema, and therows correspond to each test case, and it is can be said that Φ is the encoded inclusion relations of them.
Moreover, FROGa creates a pseudo-Boolean vector R that represents the test resultsfor each test case. When the test suite consists of n test cases st1 , … , stn , with the function result(st) → {0, 1} which encodes the test result of st as pass = 0 and fail = 1, R isexpressed as follows.
[]T
R = result(st1 ), … , result(stn )Then, FROGa runs a logistic regression with every column vector of Φ as the independent variable and R as the dependent variable. As a result, the regression coefficients for each corresponding candidate schema are obtained.
Finally, FROGa ranks the candidate schemas by the obtained regression coefficientas the magnitude of suspiciousness. The larger the regression coefficient, the higher the
possibility that a candidate schema is failure-inducing.

3.3 Simplification
Next, we will write the simplification of the encoding in FROGa. In summary, the row
vectors inf Φ and R corresponding to the passed test cases can be omitted.

13

Software Quality Journal

According to the definition of the candidate schema, candidate schemas are notincluded in any passed test cases. Therefore, the row vectors in Φ and R that corresponds to the passed test cases are always all-zero vectors. Thus, all those row vectors
are the same. In logistic regression, the same duplicate data does not affect the updateof the regression equation. This characteristic allows the row vector corresponding to
the passed test case to be deleted except only one row. Therefore, FROGa can use simplified Φ� and R′ instead of Φ and R as follows.

⎡ inc(sc1 , st1 ) … inc(scm , st1 ) ⎤
⎥
⎢
⋮
⋱
⋮
Φ =⎢
inc(sc1 , stf ) … inc(scm , stf ) ⎥
⎥
⎢
⎦
⎣
0
…
0
�

R� = [1, … , 1, 0]T

where F is the set of failed test cases, and f = |F|. Φ� is a data table with m columns andf + 1 rows, and R′ is a column vector with f + 1 dimensions.

3.4 Application example of FROGa
For a better understanding of FROGa, we show an example application. Table 4 represents the Φ and R created from the Example Test Result (Table 2) and the Example
Canididate Schemas (Table 3). In addition, Table 5 represents Φ� and R′ as simplificatedthem. Table 6 shows the values of regression coefficient and the ranks of these candidate schemas that are obtained by running logistic regression inputted Φ� and R′ . In
this example, we used the logistic regression implemented in scikit-learn (scikit-learn)with all defaulted optional parameters. In this example, both underlined failure-inducing
schemas have the highest regression coefficients, and they are at the top of the ranking.
This result shows that FROGa is working well.

4 Evaluation of FROGa
4.1 Research questions
We set the following research questions to evaluate the efficacy of FROGa.
RQ1.	Does FROGa improve the accuracy of suspiciousness calculation in FIL compared to BEN?
RQ2.	How much is the difference in the time cost between FROGa and BEN?
In order to answer these research questions, we applied FROGa and BEN to several
combinatorial testing results and compared their accuracy and processing time.

4.2 Experimental subjects
We used artificially created combinatorial testing results for the experiments rather thanactual reported combinatorial testing results. We could not find any bug reports with both13Software Quality Journal
Table 4  Example Φ and R: The Φ which represents the inclusion relationship of each Example Candidate
Schema (s1 ∼ s11) in each test case (1 = included , 0 = not included), and The R which represents the test
results of each test case (1 = fail, 0 = pass), created from Example Test Result
Test case

R

Φ
s1

s2

s3

s4

s5

s6

s7

s8

s9

s10

s11

#1

0

0

0

0

0

0

0

0

0

0

0

0

#2
#3
#4
#5
#6
#7
#8
#9
#10
#11
#12
#13
#14
#15
#16
#17
#18
#19
#20

0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1

0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1

0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
1

defects detected by combinatorial testing and the used test suites. Furthermore, we believedthat using a few experimental subjects does not bring valid results even though the subjects
are real ones. Therefore, we used a lot of artificially generated test results by assuming
several defects induced by several failure-inducing schemas in real software systems. We
believe that the use of artificially generated test results in experiments has a shallow impact
on validity because real-world failure-inducing schemas are included in the theoretical failure-inducing schemas we used.
Six real SUTs were used in the experiment as combinatorial testing targets. The
parameter and constraint sizes of each SUT are given in Table 7. The parameter size
Table 5  Example Φ� and R′: The simplified Example Φ and R
Test case

Φ�

R′

s1

s2

s3

s4

s5

s6

s7

s8

s9

s10

s11

#8

0

0

0

0

0

0

0

0

0

0

1

1

#11
#12
#20
#Others

1
1
0
0

1
0
0
0

0
1
0
0

0
1
0
0

1
0
0
0

1
0
0
0

0
1
0
0

0
0
1
0

0
0
1
0

1
0
0
0

0
0
1
0

1
1
1
0

13

Software Quality Journal
Table 6  The logistic regression
coefficients of each Example
Candidate Schema and theirranks calculated from ExampleΦ� and R′

No.

Candidate schema

Regression
coefficient

Rank

s11

(-, 2, 1, -, 1)

1.001

1

s1
s9
s8
s4
s3
s7
s6
s5
s2
s10

(1, -, -, 2, -)(2, -, 1, -, 1)(2, 2, -, -, 1)(1, -, 1, 2, -)(1, 2, -, 2, -)(1, -, -, 2, 3)(1, -, -, 2, 2)(1, -, 2, 2, -)(1, 1, -, 2, -)(-, 1, 2, -, 2)

0.724
0.402
0.402
0.385
0.385
0.385
0.339
0.339
0.339
0.339

2
3
3
5
5
5
8
8
8
8

of a SUT is expressed as |P|;gk1 gk2 … gkn , where ki parameters with gi values and |P| isthe number of parameters. The size of the constraint is expressed as a series of standard
forms l;hl1 hl2 … hlm , where m variables and hj clauses with lj literals for each j. The four
SUTs, SystemMgmt, Storage3, ProcesserComm2, Healthcare4 are specific versions of IBM product programs. Moreover, SPINS and SPINV is the simulator and theverifier in SPIN, which is an open-source model checking tool. These SUT models wererandomly selected from several models published in Cohen et al. (2008) with a broad
range of input sizes.
In addition, we used Pict (Pict) to design test suites. Pict is a well-known covering
array generation tool provided by Microsoft. The inputs of Pict are the SUT model andthe value of combinatorial coverage.
The artificial combinatorial testing results were generated through the following
three steps.
1. Test suites generation We created t-way test suite (t = 2, 3, 4) of each SUT with Pict.
As a result, a total of 18 test suite was generated from the combination of six SUTs andthree combinatorial coverages. Table 8 shows the number of test cases included in eachtest suite.
2. Failure-inducing schemas generation We randomly determined failure-inducing
schema patterns that are assumed in each test suite. First, the number of each failureinducing schema is randomly determined between 1 and 3. Then, the degree of each
Table 7  benchmark SUT models

SUT

Parameter size

Constraint size

SystemMgmt (SM)10; 25 34 51

27; 213Strage3 (ST3)

15; 29 31 53 61 81

48; 238 310

25;

23 312 48 52

81; 14 2121

35;

213 312 46 52 61 71

48; 238 310

SPINS

18;

213 4538; 213

SPINV

55;

242 32 411

133; 247 32

ProcessorComm2 (PC2)
Healthcare4 (HC4)13

Software Quality Journal
Table 8  The number of test cases
consisting of t-way test suite
generated by PICT

SUT

2-way test

3-way test

4-way test

SM

19

58

155

ST3
PC2
HC4
SPINS
SPINV

55
34
53
28
67

243
170
321
116
332

749
782
1,811
420
1,493

failure-inducing schema is randomly determined between 2 and t (for t-way tests). The
reason for this upper limit is to be tested every failure-inducing schemas. Next, theparameter values assigned to the failure-inducing schemas are determined randomly.
We prepared 10,000 patterns of failure-inducing schemas for each test suite by iterating
the above operations without duplication.
3. Testing results generation The combinatorial testing results are obtained according
to these failure-inducing schemas; the result of a test case including even one of thedetermined failure-inducing schemas is fail, otherwise pass. Finally, 10,000 cases ofcombinatorial testing results were obtained for each test suite for 2-way and 3-way testing. However, only 1,000 cases were obtained for the 4-way testing. This limitation was
due to the time constraint of the experiment.
A previous research Kuhn and Reilly (2003) suggests that almost all bugs can be foundin combination testing with strengths from 4 to 6. Thus, it’s common to set the maximum
strength between 4 and 6, and in our experiment, we chose 4. Setting the strength to 5 or
higher would create too many test cases, so we skipped it this time due to time constraints.

4.3 Experimental environment
The algorithms for BEN and FROGa were implemented in Python 3.5.1 and run on a
MacBook Pro 2017. To implement logistic regression in FROGa, we used scikit-learn(scikit-learn) which is an open-source Python library for machine learning, and we used
all optional parameters of logistic regression with default parameters. The timeout criterionof the FIL process for a single combinatorial testing result is 3,600 seconds. Encoding in
FROGa with Φ� and R′ instead of Φ and R.

4.4 Evaluation metrics
In order to answer RQ1, we used two rank-based accuracy evaluation metrics, MAP and
top-k% accuracy. In order to answer RQ2, we measured processing time.
The Mean Average Precision (MAP) is a metric that evaluates the accuracy of a system’s ranking ability Manning et al. (2008). The value of MAP takes the value from 0 to 1.
The higher the value, the more accurate the ranking is. This metric is often used to evaluate
a query information retrieval system, which is expected to return search results arranged inorder of relevance to a given query, such as search keywords. In this experiment, an input
combinatorial testing result is treated as a query, and the ranked candidate schemas are

13Software Quality Journal

treated as search results. To compute the MAP, AvePq (Average Prediction) is first calculated for single query q out of the query set Q by the following formula:

AvePq =|Rq |1 ∑prec@nqi ,|Rp | i=1

where |Rq | is the number of the search results correctly related to the query q, i. e. the number of failure-inducing schema. In addition, prec@nq is a percentage of the search resultscorrectly related to q in top n results. After that, MAP is calculated from the mean of AveP
of all queries q ∈ Q as follows:

MAP =

|Q|

1 ∑
AvePqi|Q| i=1

Note that MAP is calculated for the ranking ability of a FIL method, while AveP is calculated for the accuracy of a single ranking result.
Next, top-k% accuracy is our defined rank-based metric based on top-k accuracy. The
top-k accuracy means the success rate at the cutoff rank k in multiple trials when it is successful if all failure-inducing schemas are included in the top k of all ranked candidate
schemas. However, we cannot simply use this metric because the number of candidate
schemas is different in each trial in this experiment. Therefore, we defined and used top-k%
accuracy using top-k% instead of top-k. This can be formulated as follows:

top−k% accuracy =

|Q|

1 ∑
InTopKp(k, qi ),|Q| i=1

where InTopKp(k, q) is a function that returns 1 if all relevant results are included in the
top k% of search results for a query q, otherwise 0.

4.5 Results
In this section, we show the experimental results for evaluating FROGa. The processes did
not complete within the timeout criterion in both BEN and FROGa. Therefore, the resultsof the 4-way test of Healthcare4 and SPINV are missing values(NA). Although we could
not confirm all inputs, we have confirmed that all five randomly selected inputs in Healthcare4 and SPINV did not complete within the timeout criteria. Furthermore, we also confirmed that none of them had completed extracting candidate schemas from all schemas at
a timeout by checking the execution logs.

4.5.1 Results for RQ1Table 9 shows MAP of BEN and FROGa for each test suite. The mean value of MAP
for FROGa in the 16 test suites excluding missing values is 0.76, and the mean value of
MAP for BEN is 0.31. As a result, we can observe that the MAP of FROGa is well above
BEN. Moreover, Fig. 1 shows a comparison of the distribution of the AveP as a box plot.
The upper graph compares each SUT, and the lower graph compares each combinatorial
coverage. Note that these graphs do not include missing values; the 4-way tests of Healthcare4 and SPINV. There is little difference between the SUTs, while there is a significant

13

Software Quality Journal
Table 9  MAP of BEN and
FROGa

2-way
SUT

BEN

3-way
FROGa

BEN

4-way
FROGa

BEN

FROGa

SM

0.36

0.60

0.33

0.69

0.23

0.76

ST3
PC2
HC4
SPINS
SPINV
ALL

0.56
0.41
0.59
0.39
0.52
0.46

0.85
0.64
0.81
0.66
0.81
0.73

0.23
0.34
0.30
0.09
0.24
0.25

0.85
0.80
0.90
0.74
0.70
0.78

0.11
0.20
NA
0.05
NA
0.15

0.79
0.76
NA
0.76
NA
0.77

difference between the combinatorial coverage. BEN loss accuracy as the combinatorial
coverage increases, but FROGa can keep high accuracy even as the coverage increases.
In addition, Table 10 shows a comparison of the percentage of samples that resulted in
AveP = 1 out of all samples. The " AveP = 1" means that all failure-inducing schemas areat the top of the ranking for an input. The result shows that FROGa is much more capableof ranking accurately than BEN. Therefore, FROGa can make a perfect ranking of suspiciousness with high accuracy. This result leads that FROGa can suggest that the most
suspicious candidate schemas.
For a more detailed analysis, Table 11 shows the MAPs separately calculated for eachthe number of assumed failure-inducing schema (#FS). We can see that FROGa is always
superior to BEN. Moreover, both BEN and FROGa decrease accuracy when several failure-inducing schemas exist. In particular, when there is only one failure-inducing schema,
unlike BEN, FROGa succeeds in placing the failure-inducing schema at the top of the
ranking in almost all cases. In addition, it is a significant difference in accuracy that the
MAP for BEN is 0.07 and that the MAP for FROGa is 0.57 in the most challenging situation in this experiment; for the 4-way testing results with three failure-inducing schemas.
As reported in the previous study Niu et al. (2020), the quality of the FIL decreases with
the increase of failure-inducing schemas for the three adaptive methods, and our results
confirm this trend.
The graph in Fig. 2 shows the top-k% accuracy for each SUT. The graph’s horizontal
axis represents the value of k, and the vertical axis represents the value of top-k% accuracies. Reaching the graph to 1 in fast means that developers can find all failure-inducing schemas by checking the candidate schemas in order from the top of the ranking in
fast. Note that the graphs cannot be compared between different combinatorial coverage
because the populations of candidate schemas are different. We can observe that the topk% accuracy of FROGa reaches 1 faster than BEN in every SUTs. In comparing FROGa
and BEN, the higher the combinatorial coverage, the faster the top-k% accuracy reaches 1.
This trend is similar to MAP.
How FROGa handles false positives depends on the operation. If the computation of
the suspiciousness score in the BEN framework is replaced by FROGa, false positives
in FROGa should be eliminated by an iterative process that determines what is truly
causing the test failure. If one begins debugging by trusting only the suspiciousness
score calculated by FROGa, false positives in FROGa will cause delays in the debugging process.

13Software Quality Journal

Fig. 1  Comparison of AveP distribution of BEN and FROGa for each SUT (top) and combinatorial coverage (bottom)

From these results, the answer to RQ1 "Does FROGa improve the accuracy of ranking suspiciousness as a failure-inducing schema compared to BEN?" can be obtained asfollows.

Answer to RQ1 Compared to BEN, FROGa can significantly improve the accuracy ofranking the suspiciousness of candidate schemas. In particular, when there is only one
failure-inducing schema, FROGa can almost certainly place that schema at the top of the13Software Quality Journal
Table 10  Persentages of casesthat AveP=1

2-way
SUT

BEN

3-way
FROGa

BEN

4-way
FROGa

BEN

FROGa

SM

3.2%

8.3%

16.5%

43.3%

8.1%

41.5%

ST3
PC2
HC4
SPINS
SPINV
ALL

14.0%
12.9%
26.2%
7.5%
22.4%
14.4%

45.1%
22.7%
44.6%
19.4%
45.6%
30.9%

5.2%
14.5%
16.1%
2.8%
12.3%
11.2%

49.8%
42.7%
61.1%
33.7%
40.0%
45.1%

2.3%
9.3%
NA
6.0%
NA
5.1%

45.7%
42.2%
NA
37.9%
NA
41.8%

ranking. In addition, although BEN haves low accuracy, FROGa keeps high accuracy
when targeting results with large SUT and high combinatorial coverage.

4.5.2 Results for RQ2Table 12 shows the comparison of the average processing times for BEN and FROGa.
Moreover, Fig. 3 shows the comparison of processing time distribution by boxplots.
The upper graph compares each SUT, and the lower graph compares each combinatorial coverage. Note that these graphs do not include missing values; for the 4-way testing
Table 11  MAP calculated foreach the number of failureinducing schema (#FS)

2-way
SUT

4-way

#FS

BEN

FROGa

BEN

FROGa

BEN

FROGa

1

0.72

0.99

0.67

1.00

0.41

1.00

2
3
1
ST3
2
3
1
PC2
2
3
1
HC4
2
3
1
SPINS 23
1
SPINV 2
3
1
ALL
2
3

0.42
0.28
0.72
0.54
0.44
0.72
0.41
0.26
0.88
0.59
0.41
0.67
0.43
0.30
0.71
0.53
0.36
0.73
0.49
0.341

0.67
0.50
1.00
0.88
0.78
1.00
0.63
0.47
1.00
0.81
0.66
1.00
0.73
0.53
1.00
0.81
0.65
1.00
0.76
0.60

0.31
0.21
0.29
0.23
0.19
0.57
0.27
0.18
0.44
0.27
0.18
0.16
0.07
0.05
0.39
0.21
0.13
0.42
0.23
0.16

0.70
0.56
1.00
0.85
0.76
1.00
0.76
0.65
1.00
0.88
0.82
1.00
0.73
0.57
1.00
0.62
0.49
1.00
0.76
0.64

0.16
0.10
0.13
0.11
0.08
0.37
0.13
0.07
NA
NA
NA
0.04
0.05
0.04
NA
NA
NA
0.24
0.11
0.07

0.69
0.54
1.00
0.73
0.62
1.00
0.67
0.56
NA
NA
NA
1.00
0.70
0.59
NA
NA
NA
1.00
0.70
0.56

SM

13

3-way

Software Quality Journal

Fig. 2  Top-k% accuracy of BEN and FROGa

of Healthcare4 and SPINV. As a result, we can confirm that there is little difference intime cost between BEN and FROGa. Therefore, we can conclude that FROGa is a bettermethod than BEN overall because FROGa can more accurately calculate suspiciousness
even though there is little difference in time cost between BEN and FROGa.
From the results, the answer to RQ2 "How much is the difference in the time cost
between FROGa and BEN?" can be obtained as follows.

Answer to RQ2 There is little difference in time cost between BEN and FROGa.

13

Software Quality Journal
Table 12  The average ofprocessing time (s)

2-way

3-way

4-way

SUT

BEN

FROGa

BEN

FROGa

BEN

FROGa

SM

0.01

0.01

0.04

0.05

0.20

0.37

ST3
PC2
HC4
SPINS
SPINV
ALL

0.02
0.03
0.07
0.02
0.15
0.05

0.02
0.02
0.05
0.01
0.09
0.03

0.23
0.44
2.42
0.19
8.82
2.02

0.35
0.53
2.72
0.22
8.69
2.09

3.19
13.61
NA
3.03
NA
5.01

6.18
19.56
NA
4.59
NA
7.77

5 Further improvement for cost effectiveness5.1 Concept of FROGb
The approaches treating all candidate schemas, i. e. BEN and FROGa, are thorough andstraightforward way. However, the step to extract all candidate schemas from all possible
schemas may occur a combinatorial explosion and require a substantial computational costwhen targeting extensive testing results. For example, in the experiment in Section 4, both
BEN and FROGa did not complete to extract all candidate schemas within 3,600 seconds
when targeting the test result of 4-way tests of Healthcare4 and SPINV. This unrealistic
time cost should make lost efficiency in bug repair, which is the primary purpose of FIL.
We believe that combinatorial explosion can be avoided by directly extracting only themost suspicious candidate schemas without dealing with all schemas. We have an idea thatlogistic regression analysis can solve this problem.
It is a natural idea that test cases that include sub-schemas of a failure-inducing
schema are more likely to include the failure-inducing schema than test cases that donot. Furthermore, test cases including sub-schemas of failure-inducing schemas are
more likely to fail than test cases that do not. Therefore, the regression coefficient of the
sub-schemas of failure-inducing schemas can be high. On the contrary, if the regression
coefficient of a schema sx is high, sx is expected to be a failure-inducing schema or its
sub-schemas. Since sx must be a candidate schema to be a failure-inducing schema, if sx
is not a candidate schema but has a high regression coefficient, we can expect sx to be a
sub-schema of a failure-inducing schema.
There, we built the following hypothesis:

Hypothesis All sub-schemas of failure-inducing schemas have logistic regression coefficients higher than 0.
The logistic regression coefficients in this hypothesis are obtained the same way asin FROGa. We set the threshold as 0 to get the widest sensitivity. A positive regression
coefficient means that a unit increase in that independent variable will positively impact
the probability of a positive value for the dependent variable. If this hypothesis is correct,
there will be a minimal number of super-schemas that can include all the limited sub-schemas. Therefore, we believe in efficiently reaching failure-inducing schemas while significantly reducing the search space by successively obtaining super-schemas that satisfy the13Software Quality Journal

Fig. 3  Comparison of processing time distribution of BEN and FROGa for each SUT (top) and combinatorial coverage (bottom)

inclusion relation from the 1-degree schema obtained as a sub-schema. Based on this idea,
we propose FROGb. FROGb obtains a small number of candidate schemas that are highly
suspicious as failure-inducing schemas (after this referred to as high-suspicious candidate
schemas) without extracting all candidate schemas from all possible schemas.

5.2 Model
FROGb needs three inputs as same as FROGa: a test suite, the test results for each test
case, and k, which is assumed maximum degree of failure-inducing schema. FROGb runs
the following steps for each t-degree schema of 1 ≤ t ≤ k step by step.

13

Software Quality Journal

Initial Status	 Let be t = 1. There are three empty sets: S, C, SubS; S means the set ofschemas that are currently in focus. C means the set of high-suspicious
candidate schemas. Moreover, SubS means the set of schemas that areconsidered to be sub-schemas of failure-inducing schemas.
Step 1 (t = 1)	 Extract all 1-degree schemas in the failed test cases and add them to S.
Step 2	 For each schema in S, check if it is a candidate schema according to thedefinition. If it is a candidate schema, delete it from S and add it to C.
Step 3	 For each schema left in S, calculate the logistic regression coefficientsand the FROGa procedure, and add the schemas with positive regression
coefficients to SubS.
Step 4	 Increment t by one and initialize S to be empty. Then, go to Step 1.
Step 1 (t ≥ 2)	 Find all t-order schema such that their all (t − 1)-degree sub-schemas
are included in the set SubS, and add them to S. Then, initialize SubS to
empty and go to Step 2.
There are two termination conditions for this algorithm:
1. Terminate when the variable t exceeds the given maximum schema order k, i.e., t > k . To
be more precise, there is no need to check whether a k-degree schema is a sub-schemaof ( k + 1)-degree high-suspicious candidate schemas, so immediately terminate afterStep 2 (t = k).
2. Terminate when S is empty at the end of Step 1, or SubS is empty at Step 3, despite t ≤ k .
It is because there is no schema to pass to the next step.
FROGb outputs C at the end of the algorithm as a set of high-suspicious candidate schemas with k-degree or less.

5.3 Application example of FROGb
For a better understanding of FROGb, we show an example application using the example test results shown in Table 2. Table 13 shows the schemas handled in each iterationand their logistic regression coefficients and several judgment results in this application
example. In this table, " s ∈ S " indicates each schema included in S, "to C" indicates
whether be judged a candidate schema or not. Moreover, "to SubS" indicates whether be
judged as a sub-schema or not.
As input, we give the example test suite and the result shown in Table 2, and the
maximum degree of schema, k = 3.

t = 1	 First, FROGb extracts all the 1-degree schemas included in the failed test caseand adds them to S. In this example, all possible 1-degree schemas except (-, -, -,3, -) have been added to S. Next, FROGb checked that all the 1-degree schemasin S are not candidate schemas since they are also included in some passed test
cases. Then, we encode the inclusion relations between each schema in S and eachtest case and run logistic regression to obtain the regression coefficients. Here, thefive 1-degree schemas; (1, -, -, -, -), (-, 2, -, -, -), (-, -, 1, -, -), (-, -, -, 2, -), (-, -, -,-, 1) were added to SubS as 1-degree sub-schemas of the failure-inducing schemas
because their regression coefficients were higher than 0. Now, let S be empty.

13

Software Quality Journal
Table 13  The handled schemas
and their various judgment
results in each iteration in
FROGb with Example Test
Resultiteration

s∈S

to C

Coefficientto SubS✓

t=1(1, -, -, -, -)

0.049

t=2

(2, -, -, -, -)(-, 1, -, -, -)(-, 2, -, -, -)(-, -, 1, -, -)(-, -, 2, -, -)(-, -, -, 1, -)(-, -, -, 2, -)(-, -, -, -, 1)(-, -, -, -, 2)(-, -, -, -, 3)(1, 2, -, -, -)(1, -, 1, -, -)(1, -, -, 2, -)(1, -, -, -, 1)(-, 2, 1, -, -)(-, 2, -, 2, -)(-, 2, -, -, 1)(-, -, 1, 2, -)(-, -, 3, -, 1)(-, 2, 1, 2, -)(-, 2, 1, -, 1)-0.542-0.5340.042
0.016-0.508-0.2480.571
0.450-0.448-0.4950.032-0.107-0.106
0.585
0.095
0.571
0.095
0.594
-

t=3

✓

✓

✓
✓

✓
✓

✓

✓
✓
✓
✓
✓

t = 2	 FROGb extracts all the 2-degree schemas included in some failed test cases
and whose 1-degree sub-schemas are all included in SubS, then adds themto the empty S. As a result, the nine 2-degree schemas shown in the t = 2 ofTable 13 were added to S. As an example, the 2-degree schema (1, 2, -, -, -)is included in (1, 2, 1, 1, 1), which is the failed test case #8 in Table 2, and allof its 1-degree sub-schemas (1, -, -, -, -) and (-, 2, -, -, -) are included in SubS.
Therefore, it was added to S. Now, let SubS be empty. Next, FROGb checks
whether every s ∈ S is a candidate schema. As a result, only (1, -, -, 2, -) is acandidate schema, so it is removed from S and added to C. We compute theregression coefficients for the left schema in S, and six 2-degree schemas areadded to SubS. Now, let S be empty.
t = 3	 FROGb extracts all 3-degree schemas that are included in some failed test cases
and whose all 2-degree sub-schemas are included in SubS, and add them to theempty S. There are only two such schemas, (-, 2, 1, 2, -) and (-, 2, 1, -, 1). Only(-, 2, 1, -, 1) is judged as a candidate schema, so remove it from S and add it to C.
Here, FROGb finishes because the first termination condition is satisfied.
Only two high-suspicious candidate schemas (1, -, -, 2, -) and (-, 2, 1, -, 1) were obtainedat the end of the algorithm. We can confirm that these are indeed failure-inducing schemas.

13Software Quality Journal

6 Evaluation of FROGb
6.1 Research questions
In order to evaluate FROGb, we set the following research questions.
RQ3.	How much does FROGb reduce the cost of extracting high-suspicious candidate
schemas compared to BEN and FROGa?
RQ4.	How accurate does FROGb extract failure-inducing schemas as high-suspicious
candidate schemas?

6.2 Setting
We reused the results in Section 4.5 to compare FROGb with BEN and FROGa. Therefore, the experimental subjects are the same as written in Section 4.2 and the experimental
environment is the same as written in Section 4.3
We newly implemented and executed FROGb, and measured several metrics, and compared them with the results of BEN and FROGa had been already obtained.
To answer RQ3, we measure the processing time till FROGb finishes. The FROGb’s purpose that extracts high-suspicious candidate schemas can achieve by picking up
some candidate schemas from the top of the suspiciousness ranking created by BEN and
FROGa. Therefore, we correctly compare the measured processing time of FROGb withthe processing time of BEN and FROGa. In addition, we also counted the number of highsuspicious candidate schemas extracted by FROGb in order to check whether FROGb can
extract only a few high-suspicious candidate schemas or not.
To answer RQ4, we investigated the number of the artificially generated failure-inducing schemas included in the high-suspicious candidate schemas extracted by FROGb.

6.3 Results
6.3.1 Results for RQ3
Table 14 shows the average processing time and two indexes for comparison of BEN,
FROGa, and FROGb. The index %red represents the average reduction rate of processing
time of FROGb, and the index %short represents the percentage of cases where FROGb
was able to save time. These indexes compare FROGb with the shorter processing timesof BEN and FROGa. In addition, Fig. 4 shows a boxplot comparing the distributions ofprocessing time.
As a result, the difference in the reduction of processing time depends on the combinatorial coverage. First, there was a slight time reduction by FROGb when targeting 2-way
tests. In particular, for 2-way tests of Healthcare4 and SPINV, the average time reduction
rate was less than zero, and the processing time increased in more than half of the cases.
The reason may be that the processing time overhead by FROGb exceeded the reduction
time by FROGb. Next, for the 3-way tests, the time reduction rate was about 50%, andabout 96% of all cases reduced the processing time. For the 4-way tests, the time reduction
rate was even more pronounced. In particular, for 4-way tests of Healthcare4 and SPINV,
FROGb could complete extracting high-suspicious candidate schemas in a few seconds.

13

Software Quality Journal
Table 14  The average ofprocessing time, the reduction
rate (%red), and the shortenedcases rate (%short)processing time (s)
SUT
SM

ST3

PC2

HC4

SPINS

SPINV

ALL

t-way

BEN

FROGa

FROGb

2

0.01

0.01

3
4
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4

0.04
0.20
0.02
0.23
3.19
0.03
0.44
13.61
0.07
2.42
NA
0.02
0.19
3.03
0.15
8.82
NA

0.05
0.37
0.02
0.35
6.18
0.02
0.53
19.56
0.05
2.72
NA
0.01
0.22
4.59
0.09
8.69
NA

0.00

0.02
0.05
0.01
0.10
0.33
0.02
0.14
0.56
0.05
0.85
3.75
0.01
0.08
0.24
0.10
2.51
31.37

%red

%short

11.9%

71.5%

34.6%
62.7%
15.2%
47.9%
84.0%
18.1%
63.9%
94.1%
-0.3%
65.2%
NA
2.9%
47.8%
89.7%
-14.7%
70.1%
NA
5.5%
54.9%
82.6%

83.4%
96.2%
74.9%
98.3%
100.0%
84.0%
99.9%
100.0%
51.4%
100.0%
NA
60.5%
95.3%
100.0%
29.2%
99.4%
NA
61.9%
96.0%
99.1%

This result is a remarkable improvement considering that BEN and FROGa could notcomplete the process within 3,600 seconds.
For the sake of simplicity, we refer to BEN and FROGa collectively as the all-extraction method (All-ex) because these methods extract all candidate schemas at first, unlike
FROGb. The left side of Table 15 (#Candidate row) shows the average number of candidate schemas extracted by the all-extraction method and the average number of highsuspicious candidate schemas extracted by FROGb, and the reduction rates. The rightside of Table 15 (#Check row) shows the average number of checking operations whethera schema is a candidate schema or not by the all-extraction method and FROGb, and the
reduction rates. Furthermore, the upper part of Fig. 5 illustrates the comparison of the
distribution of the number of extracted candidate schemas, and the lower part illustrates
the comparison of the distribution of the times of the checking operation.
As a result, high-suspicious candidate schemas extracted by FROGb are fewer thanthose extracted in the first step of the all-extraction method. For each t-way test, the reduction rates are 50.6%(t = 2), 91.5%(t = 3), and 99.0%(t = 4). The higher the combinatorial
coverage, the fewer high-suspicious candidate schemas were output by FROGb. On theother hand, there was no difference in SUT.
The number of checking operations in FROGb decreased as the combinatorial coverage increased. This result is the opposite trend of the one of the all-extraction method. The
reason is that the higher the maximum number of iterations k of the FROGb algorithm,
the tighter the constraints on the sub-schemas that the output candidate schema must satisfy. For most SUTs with k = 4, the average number of high-suspicious candidate schemas

13Software Quality Journal

Fig. 4  Comparison of processing time distribution of BEN, FROGa and FROGb

was around five. This result shows that FROGb can output only high-suspicious candidate
schemas with minimum checking operations.
From the results, the answer to RQ3 "How much does FROGb reduce the cost of
extracting high-suspicious candidate schemas compared to BEN and FROGa?" can beobtained as follows.

Answer to RQ3 FROGb can extract only a tiny number of high-suspicious candidate schemas and significantly reduce the processing time compared to BEN and FROGa, especially when targeting testing results with the high combinatorial coverage.

13

Software Quality Journal
Table 15  The average number of extracted candidate schemas (#Candidate) and checking opperations to
extract candidate schemas (#Check) for each All-ex (i.e., BEN and FROGa) and FROGb, and their reduction rates of FROGb against All-ex (%red)#Candidate
SUT
SM

ST3

PC2

HC4

SPINS

SPINV

ALL

#Checkt-way

All-ex

FROGb

%red

All-ex

FROGb

%red

2

52.4

178.2

92.0%
98.3%
51.6%
91.4%
99.0%
55.6%
92.0%
99.3%
50.6%
92.6%
NA
48.0%
90.3%
99.26%
49.0%
90.8%
NA
50.9%
91.5%
99.0%

1,086.7
3,636.5
650.0
7,116.5
47,122.2
1,109.5
21,231.4
280,509.3
3,674.7
127,433.2
NA
706.8
9,082.6
78,524.0
7,438.3
321,912.1
NA

73.5

59.0%

204.8
634.3
93.5
433.1
2,305.7
147.6
765.5
5,494.4
211.9
1,401.1
NA
106.4
482.1
2,506.0
268.2
2,227.0
NA

26.0

50.4%

3
4
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4

12.5
4.7
43.2
21.6
5.1
64.1
45.6
5.7
98.7
80.5
5.7
54.2
29.0
4.9
134.3
135.6
26.3

76.4
54.8
224.4
229.9
146.1
346.5
513.8
258.2
1,003.3
1,828.0
764.0
231.8
301.1
168.0
1,890.5
5,102.2
3,032.1

92.7%
98.1%
65.9%
96.7%
99.6%
68.6%
97.4%
99.9%
72.6%
98.6%
NA
67.6%
96.6%
99.8%
74.9%
98.4%
NA
68.1%
96.8%
99.3%

6.3.2 Results for RQ4Table 16 shows the result of investigating whether the failure-inducing schemas were
included in high-suspicious candidate schemas extracted by FROGb. The investigating
results are aggregated into three categories: All, Partly, and No. This result shows that
FROGb did not always extract all failure-inducing schemas. On average, 63.3% cases
extracted all failure-inducing schemas, 32.2% cases extracted only some of the failureinducing schemas, and only 4.4% cases did not extract any failure-inducing schemas.
Moreover, there was little different depending on the combinatorial coverage. On the other
hand, the larger SUT, the higher the percentage of all failure-inducing schemas extracted as
high-suspicious candidate schemas.
Next, Table 17 shows the percentage of case that all failure-inducing schemas were
included in high-suspicious candidate schemas extracted by FROGb, aggregated by
the number of failure-inducing schemas. From the result, we can see that the fewer
failure-inducing schemas, the higher the percentage. For example, for the 2-way testing results of SPINV with only one failure-inducing schema, FROGb could extract all
failure-inducing schemas with very high accuracy, 99.9%. However, for the results withthree failure-inducing schemas, the accuracy sharply drops to 68.7%. This fact leads tomultiple failure-inducing schemas impacting the failure of the extraction of each other.

13

Software Quality Journal

Fig. 5  Comparison of distribution of #Chandidate (top) and #Check (bottom)

In addition, this difference in accuracy is also emphasized by the size of SUT. For
example, the accuracies of extracting all failure-inducing schemas are 50-70% for HC4
and SPINV, which have many input parameters. On the other hand, the accuracies are
only 9-27% for SM, which has the fewest input parameters.
From the results, the answer to RQ4 "How accurate does FROGb extract failureinducing schemas as high-suspicious candidate schemas" can be obtained as follows.

Answer to RQ4 FROGb can extract all failure-inducing combinations in 63.3% of all andcan extract at least one of them in 95.6% of all. This accuracy tends to increase as the sizeof SUT increases and the number of failure-inducing schemas decreases.

13

Software Quality Journal
Table 16  The classification rates of how many failure-inducing schemas were included in the highsuspicious candidate schemas extracted by FROGb
2-way
SUT

All

3-way
Partly

No

All

4-way
PartlyNo

All

Partly

No

SM

37.5%

54.7%

7.8%

31.1%

52.8%

16.1%

39.6%

40.1%

20.3%

ST3
PC2
HC4
SPINS
SPINV
ALL

63.5%
62.3%
82.3%
61.8%
84.7%
65.3%

34.8%
35.3%
17.4%
36.9%
15.3%
32.4%

1.7%
2.4%
3.0%
1.3%
0.1%
2.6%

56.1%
68.5%
85.6%
63.2%
83.9%
64.7%

39.5%
29.6%
14.1%
35.1%
15.9%
31.2%

4.4%
2.0%
3.0%
1.8%
0.3%
4.1%

46.4%
62.6%
78.1%
53.3%
79.7%
60.0%

43.9%
34.9%
21.2%
41.1%
18.2%
33.2%

9.7%
2.5%
0.7%
5.6%
2.1%
6.8%

6.4 Discussion
6.4.1 Overall evaluation
Contrary to our hypothesis, the answer to RQ4 reveals that not all sub-schemas of failure-inducing schemas always have positive logistic regression coefficients. Therefore,
the FROGb does not necessarily lead to accurate results. However, in our experiments,
all failure-inducing schemas were extracted as high-suspicious candidate schemas in
about 63.3% of the cases. This accuracy is not low. On the contrary, it is a good tradeoff for reducing the processing time for some targets where the BEN and FROGa takeunrealistic processing time.
In addition, the identification of only single defect-inducing schemas can be valuable. For example, if multiple failure-inducing schemas induce the same defect, identifying one of the schemas will help to identify all the defects.
Moreover, consider the case where partial defects could be repaired by identifying someof the failure-inducing schemas. It may be possible to identify all defects by rerunningcombinatorial testing and obtaining different test results, step by step. Therefore, we cansee that FROGb can obtain effective localization results with 95.6% accuracy in actual.
Table 17  The percentages of all n failure-inducing schemas were included in the high-suspicious candidate
schemas extracted by FROGb for each n
2-way

3-way

4-way

SUT

n=1

n=2

n=3

n=1

n=2

n=3

n=1

n=2

n=3

SM

88.6%

46.5%

26.8%

71.3%

32.4%

13.6%

77.8%

23.3%

9.3%

ST3
PC2
HC4
SPINS
SPINV
ALL

96.6%
94.3%
99.5%
97.7%
99.9%
96.1%

70.4%
66.9%
86.9%
71.1%
88.1%
71.6%

49.0%
42.5%
65.3%
45.1%
68.7%
49.6%

92.4%
96.7%
99.5%
99.4%
99.8%
93.2%

55.9%
70.4%
90.8%
67.2%
90.3%
67.8%

30.4%
39.9%
66.7%
34.8%
61.7%
41.2%

88.6%
98.3%
99.4%
93.0%
94.7%
92.0%

32.1%
58.9%
80.9%
49.2%
84.2%
54.8%

12.9%
23.1%
50.8%
22.9%
60.1%
29.8%

13

Software Quality Journal

Based on these considerations, we conclude that FROGb is a very efficient, fast, but
approximate FIL approach.

6.4.2 Causes of failure of FROGb
We identified two causes of failure by checking several processing logs where FROGb
failed to extract all the failure-inducing schemas.
The first cause is due to the collision of multiple failure-inducing schemas. This collision refers to the situation where there are multiple failure-inducing schemas, and all
the primary schemas corresponding to all possible values of a parameter are included
in different failure-inducing schemas. FROGb expects the regression coefficients of all
the 1-degree sub-schemas of the failure-inducing schema to be positive. However, due
to the relativity of regression coefficients, only some of these 1-degree schemas canhave positive values. Therefore, FROGb could extract all correct 1-degree schemas as
sub-schemas of the high-suspicious candidate schemas and could successfully obtain
either of the failure-inducing schemas. For example, consider the pn , n-th parameter of
the SUT, and the pn can take two different values, pn1 and pn2 . In this case, the regression coefficients of either pn1 or pn2 will always be greater than zero, and the rest will beless than zero.
In our posterior study, there are the collisions in 12,319 cases, out of 44,368 cases where
FROGb could not extract all failure-inducing schemas. In addition, all cases involving
multiple failure-inducing schemas with the collision failed. This cause of failure explainsthat the smaller the size of SUT and the larger the number of failure-inducing schemas, thelower the accuracy of extracting all failure-inducing schemas in our experiments. Since theassignment of failure-inducing schemas is determined randomly in our experiment, it isnatural that the possibility of the collision increases as the number of failure-inducing schemas increases. In addition, when the number of input parameters of the SUT is large andcan take various values, the possibility of the collision decreases.
The second cause is due to just an accident. This accident refers to which input values were assigned by chance to each test case of the designed test suite. We have confirmed the following two cases of accidental failures of identification.
1. There are multiple failure-inducing schemas. Consider the pn , n-th parameter of the
SUT. The pn can take two different values, pn1 and pn2 . One failure-inducing schema,
f1, contains pn1 as a sub-schema. However, all the test cases failed by failure-inducing
schemas other than f1 happen to contain pn2 . In this case, the value of the parameter pn
appears to be irrelevant to the test failure. Therefore, pn1 is not estimated as a sub-schemaof f1, and the wrong result is output.
2. There are multiple failure-inducing schemas. Consider the pn , n-th parameter of the
SUT. The pn can take two different values, pn1 and pn2. One failure-inducing schema, f1,
contains pn1 as a sub-schema. However, the regression coefficient for pn1 will be lower
than zero if the test fails by chance more often due to other failure-inducing schemas
when pn2 is included than when pn1 is included in the test case. Therefore, pn1 is not
estimated as a sub-schema of f1, and the wrong result is output.
Since we could not find any other causes of failure, all 32,049 failures that the first cause
cannot explain must be due to the second cause.

13Software Quality Journal

6.4.3 Limitation of FROGb
FROGb should not be used to combinatorial testing results where only one test case failed.
This limitation is because FROGb ’s algorithm always predicts all the 1-degree schemas
in the failed test case to be sub-schemas of the failure-inducing schema in this case. Therefore, all the candidate schemas are extracted as high-suspicious ones by FROGb, so theresult no longer provides helpful information. In such cases, we recommend using an alternative FIL method based on the modification and re-running of a single failure test case,such as the OFOT Nie and Leung (2011).
As we saw, FROGb can not obtain all candidate schemas. Therefore, we cannot establish that a gotten high-suspicious candidate schema is indeed a failure-inducing schemain such a way to run a test case without any other candidate schemas and check the test
case to fail. However, if necessary, it is possible to increase confidence by testing several
random test cases that include high-suspicious candidate schemas, such as the checking
mechanism used in ICT Niu et al. (2020).

7 Threats to validity
We used Python to implement BEN, FROGa, and FROGb. Python is slower than a compiled language, and our implementation and environment may not be optimized. Therefore,
the processing time for each method measured in our experiments may be more redundant
than the ideal time. However, considering all methods have the same affection on processing speed, the comparison results must be correct.
We calculated the suspicious score in BEN based on the formulas provided in the original paper Ghandehari et al. (2012) and confirmed its accuracy through examples from thesame source. However, we didn’t conduct a detailed operational check, posing a potential
threat to the validity of our results. Future studies should include thorough validation processes to ensure the reliability of the implemented algorithm.
We used only one type of machine learning package, scikit-learn, and its default parameter values to implement the logistic regression because we had no significant problems
with the behavior and results of FROGa and FROGb in this case. On the other hand,
we have not yet tested the behavior with other packages and parameters. A more detailed
investigation is required to see how changing and optimizing these packages and parameters will change the experimental results and improve the accuracy.
In evaluating FROGa, we didn’t conduct experiments involving iterative identification,
as shown in the original BEN paper. Instead, we kept it simple by comparing the accuracyof suspicious scores. This decision was due to the absence of programs with actual bugs as
experimental subjects, making adjustments difficult, and being constrained by time during the experiments. Still, because the BEN framework improves suspicion score accuracy
over time through iteration, we believe that FROGa ’s high initial accuracy effectively
enhances fault localization efficiency. However, it’s important to note that an evaluationaligned with the BEN framework may hold the potential for unknown discoveries, making
it a crucial task for future research.

13

Software Quality Journal

8 Related work
Several FIL approaches have been proposed. These approaches are categorized into adaptive and non-adaptive by involving adaptive generation and execution of additional test
cases. Recent survey work about FIL is in Jayaram and Krishnan (2015).

8.1 Adaptive FIL approaches
The adaptive approach mainly identify defect-inducing schemas by designing and executing
new test cases based on the execution results of the test cases (Nie & Leung, 2011; Zeller& Hildebrandt, 2002; Wang et al., 2010; Li et al., 2012; Zhang & Zhang, 2011). Somemethods use a single failed test case as input, generate and execute additional test cases bychanging the value of one of the parameters in the test case, and identify the fault-inducing
schema in the original test case based on the changes in the execution results. Many of thesemethods are known to work only when the number of fault-inducing schemas is one. For
example, the OFOT Nie and Leung (2011), and the method using Delta Debugging (Zeller &Hildebrandt, 2002; Wang et al., 2010; Li et al., 2012) do not give correct results in many cases
unless the number of fault-inducing schemas is one. In order to address these problems, Zhang
and Zhang (2011) proposed an FIC that partially supports the localization of multiple faultinducing schemas. In addition, Niu et al. (2020) proposed an ICT that performs localization
more effectively by dynamically running the processes of single test case design and execution
and input value localization in succession. ICT further checks whether the identified failureinducing schemas lead to test failures by using a checking mechanism that extends the OFOT
method, preventing false identifications that occur when there are multiple fault-inducing
input value pairs. These methods assume a cycle that; (1) interrupts the sequential executionof test when a failure occurs, (2) identify the failure-inducing schemas, (3) correct the defectcomponents using the identification result, (4) and then test again.
On the other hand, there is also a method that executes all the test cases of a normal
covering array and then performs input value localization based on the results of all those
executions. Due to the recent development of automated testing techniques through continuous integration, etc., obtaining the test results of the entire covering array has become
sufficiently realistic to be considered a promising method. As the most primitive method,
Yilmaz et al. (2006) proposed a method to estimate the failure-inducing schema using classification trees. While this estimation does not require additional test cases, it is not guaranteed to be accurate. It is also known that the effectiveness of this approach is highly
dependent on the characteristics of the covering array and does not work well if, for example, the majority of the covering array consisting of a small number of test cases fails.
Fouché et al. (2009) and Shakya et al. (2012) have proposed an extension of Yilmaz et al.’s
work with some improvements. Yilmaz et al. (2014) also devised a framework to feed backestimation results to test case generation.
Another approaches are first to extract all candidate schemas that may be failureinducing and then generate additional test cases to verify that they are indeed failureinducing schemas (Shi et al., 2005; Wang et al., 2010; Zhang et al., 2012; Zheng
et al., 2016; Niu et al., 2013; Ghandehari et al., 2012, 2015, 2020). The AIFL by Shi et al.
(2005) attempts to find a single failure-inducing schema, and the InterAIFL extended
by Wang et al. (2010) can find multiple failure-inducing schemas. ComFIL, proposedby Zheng et al. (2016), can find multiple failure-inducing schemas by elimination andgenerates test cases from all candidate schemas to reduce the most candidates in a single

13

Software Quality Journal

test. In addition, Niu et al.Niu et al. (2013) attempt to optimize the design of additional
test cases by constructing a tuple relationship tree to describe the relationship between
each candidate schema. The BEN proposed by Gandihari et al. (2015, 2020) also performs
efficient input value localization by ranking the candidate schemas based on the calculated
suspicious values Ghandehari et al. (2012, 2015, 2020). Several studies seem BEN as astrong candidate for FIL methods (Gargantini et al., 2017; Bonn et al., 2019).
The proposed FROGa is an extension of the existing adaptive method BEN and thus
belongs to the adaptive methods. On the other hand, FROGb is a predictive method, so
these classifications are not necessarily applicable. The idea of FROGb is based on our earlier work Nishiura et al. (2017). However, in this paper, we give a more strict and detailed
model definition, and we also treat a new variety of experimental subjects in the evaluation
experiments and make new discussion.

8.2 Non‑adaptive FIL approaches
In contrast to the adaptive approach, the non-adoptive approach does not require the creation and execution of additional test cases. The non-adaptive methods mainly generate a
Locating Array with a particular input value localization capability when designing a covering array. For example, Colbourn and McClary (2008) proposed a (d, t)-Locating Array.
(d, t)-Locating Array can uniquely identify d defect-inducing t-degree schemas or lessby using a covering array covering all (d + t)-degree schemas. As a similar mathematicalobject, Martínez et al. (2009) proposed the Error Locating Array. This is based on assuming the structure of the input parameters related to the failure-inducing schemas. In addition, several developments of the Locating Array have been proposed. Hagar et al. (2015)
proposed a partial covering array method that uses the known safe input values of the target
software in the design. Nagamoto et al. (2014) focused on pairwise testing and proposeda method to effectively generate a (1, 2)-Locating Array from a given test suite. Jin et al.
(2018) also proposed the Constrained Locating Array, which is an extension of the Locating Array to deal with constrained input models. A recent survey of such Locating Array
research and their applications is also summarized in Colbourn and Syrotiuk (2018).
The advantage of using non-adaptive methods is that the design and execution of the test
suite can be wholly separated. On the other hand, the disadvantages are as follows. The developers need to know the number and the degree of failure-inducing schemas to design a locating array. Alternatively, the developers must assume these numbers, and successful localization is successful only if the assumptions are correct. In addition, the number of test cases ina Locating Array is much larger than in a naive covering array, and thus the execution cost ismuch higher. These limitations are not very attractive in practical use, and these limitations
have not been fundamentaly resolved now.

9 Conclution
This paper proposed two novel faulty interaction localization approaches using logistic
regression analysis: FROGa and FROGb. FROGa improves the accuracy of computing
suspiciousness of combinations of parameter values by using that logistic regression. In
addition, FROGb avoids a combinatorial explosion by estimating the subsets of failureinducing combinations and exploring their supersets. The estimation of subsets also uses
the logistic regression coefficients. Through evaluation experiments using a large number

13Software Quality Journalof artificial test results based on several real systems, we observed that: FROGa has very
high accuracy, and FROGb can drastically reduce computing cost for targets that havebeen difficult to complete to identify by the conventional method.
Our research leaves several challenges. One of them is to improve the accuracy by various logistic regression implementation methods. Another is to quantitatively evaluate theaccuracy improvement and cost increase by using additional test designs and reruns. We
would also like to evaluate it by applying it to faults detected by combinatorial tests, which
are not artificially generated but reported.
Author contributions Kinari Nishiura did most of the experiments and collected the data, and wrote themain manuscript text. Eun-Hye Choi and Osamu Mizuno substantially contributed to the study conceptualization, data analysis and interpretation. Eunjong Choi supported discussions and manuscript writing withenthusiasm.
Funding This work was supported in part by JSPS KAKENHI Grant number JP18H04094, JP19K20240,
and 21H03416.
Availability of data and materials The datasets generated and/or analyzed during the current study are available from the corresponding author on reasonable request.

Declarations
Competing interests The authors declare that they have no competing interests.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License,
which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as longas you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article
are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to thematerial. If material is not included in the article’s Creative Commons licence and your intended use is not
permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directlyfrom the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/..

References
Basili, V. R., Briand, L. C., & Melo, W. L. (1996). A validation of object oriented metrics as quality indicators. IEEE Trans. on Software Engineering, 22(10), 751–761.
Bonn, J., Foegen, K., & Lichter, H. (2019). A framework for automated combinatorial test generation, execution, and fault characterization. In: Pros. of 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp. 224–233.
Briand, L. C., Melo, W. L., & Wust, J. (2002). Assessing the applicability of fault-proneness models acrossobject-oriented software projects. IEEE Trans. on Software Engineering, 28(7), 706–720.
Cohen, M. B., Dwyer, M. B., & Shi, J. (2008). Constructing interaction test suites for highly-configurable
systems in the presence of constraints: A greedy approach. IEEE Transactions on Software Engineering, 34(5), 633–650.
Colbourn, C. J., & McClary, D. W. (2008). Locating and detecting arrays for interaction faults. Journal of
combinatorial optimization, 15(1), 17–48.
Colbourn, C. J., & Syrotiuk, V. R. (2018). On a combinatorial framework for fault characterization. Mathematics in Computer Science, 12(4), 429–451.
Cramer, J. (2002). The origins of logistic regression. Tinbergen Institute Discussion Papers: Tinbergen
Institute.
Fouché, S., Cohen, M. B., & Porter, A. (2009). Incremental covering array failure characterization in large
configuration spaces. In: Proceeding of the 18th International Symposium on Software Testing andAnalysis, ser. ISSTA ’09, pp. 177–188.

13

Software Quality Journal
Gargantini, A., Petke, J., & Radavelli, M. (2017). Combinatorial interaction testing for automated constraint
repair. In: Pros. of the 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pp. 239–248.
Ghandehari, L. S., Chandrasekaran, J., Lei, Y., Kacker, R., & Kuhn, D. R. (2015). Ben: A combinatorial
testing-based fault localization tool. In: Proceeding of IEEE 8th International Conference on Software
Testing, Verification and Validation Workshops (ICSTW), pp. 1–4.
Ghandehari, L. S. G., Lei, Y., Xie, T., Kuhn, R., & Kacker, R. (2012). Identifying failure-inducing combinations in a combinatorial test set. In: Proceeding of IEEE 5th International Conference on Software
Testing, Verification and Validation (ICST), pp. 370–379.
Ghandehari, LSh., Lei, Y., Kacker, R., Kuhn, R., Xie, T., & Kung, D. (2020). A combinatorial testing-based
approach to fault localization. IEEE Transactions on Software Engineering, 46(6), 616–645.
Hagar, J. D., Wissink, T. L., Kuhn, D. R., & Kacker, R. N. (2015). Introducing combinatorial testing in alarge organization. Computer, 48(4), 64–72.
Jayaram, R., & Krishnan, R., Approaches to fault localization in combinatorial testing: A survey. In: Smart
Computing and Informatics, pp. 533–540.
Jin, H., Kitamura, T., Choi, E., & Tsuchiya, T. (2018). A satisfiability-based approach to generation of constrained locating arrays. Proceeding of 2018 IEEE International Conference on Software Testing (pp.
285–294). ICST Workshops: Verification and Validation Workshops.
Kamei, Y., Fukushima, T., McIntosh, S., Yamashita, K., Ubayashi, N., & Hassan, A. E. (2016). Studying
just-in-time defect prediction using cross-project models. Empirical Software Engineering, 21(5),2072–2106.
Kuhn, D., & Reilly, M. (2003). An investigation of the applicability of design of experiments to software testing. In: Proceeding of 27th Annual NASA Goddard/IEEE Software Engineering Workshop, pp. 91–95.
Kuhn, D. R., Kacker, R. N., & Lei, Y. (2013). Introduction to combinatorial testing. CRC Press.
Li, J., Nie, C., & Lei, Y. Improved delta debugging based on combinatorial testing. In: Proceeding of 12th
International Conference on Quality Software, pp. 102–105.
Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge
University Press.
Martínez, C., Moura, L., Panario, D., & Stevens, B. (2009). Locating errors using elas, covering arrays, andadaptive testing algorithms. SIAM Journal on Discrete Mathematics, 23(4), 1776–1799.
Nagamoto, T., Kojima, H., Nakagawa, H., & Tsuchiya, T. (2014). Locating a faulty interaction in pair-wise
testing. In: Proceeding of IEEE 20th Pacific Rim International Symposium on Dependable Computing,pp. 155–156.
Nie, C., & Leung, H. (2011). A survey of combinatorial testing. ACM Computing Surveys, 43(2), 11.
Nie, C., & Leung, H. (2011). The minimal failure-causing schema of combinatorial testing. IEEE Trans. on
Software Engineering, 20(4), 1–38.
Nishiura, K., Choi, E. -H., & Mizuno, O. (2017). Improving faulty interaction localization using logistic
regression. In: Proceeding of 2017 IEEE International Conference on Software Quality, Reliability
and Security (QRS), pp. 138–149.
Niu, X., Nie, C., Lei, Y., & Chan, A. T. (2013). Identifying failure-inducing combinations in a combinatorial
test set. In: Proceeding of IEEE 6th International Conference on Software Testing, Verification andValidation Workshops (ICSTW), pp. 271–280.
Niu, X., Nie, C., Leung, H., Lei, Y., Wang, X., Xu, J., & Wang, Y. (2020). An interleaving approach to combinatorial testing and failure-inducing interaction identification. IEEE Trans. on Software Engineering,46(6), 584–615.
Peng, C. -Y. J., Lee, K. L., & Ingersoll, G. M. (2002). An introduction to logistic regression analysis andreporting. The Journal of Educational Research, 96(1), 3–14.
Pict: Pairwise independent combinatorial tool. http://​github.​com/​Micro​soft/​pict
scikit-learn. http://​scikit-​learn.​org/
Shakya, K., Xie, T., Li, N., Lei, Y., Kacker, R., & Kuhn, R. (2012). Isolating failure-inducing combinations
in combinatorial testing using test augmentation and classification. In: Proceeding of IEEE 5th International Conference on Software Testing, Verification and Validation, pp. 620–623.
Shi, L., Nie, C., & Xu, B. (2005). A software debugging method based on pairwise testing. In: Proceedingof 2005 International Conference on Computational Science (ICCS), pp. 55–81.
Wang, Z., Xu, B., Chen, L., & Xu, L. (2010). Adaptive interaction fault location based on combinatorial testing. In: Proceeding of IEEE 10th International Conference on Quality Software (QSIC), pp. 495–502.
Yilmaz, C., Cohen, M. B., & Porter, A. A. (2006). Covering arrays for efficient fault characterization incomplex configuration spaces. IEEE Transactions on Software Engineering, 32(1), 20–34.

13Software Quality Journal
Yilmaz, C., Dumlu, E., Cohen, M. B., & Porter, A. (2014). Reducing masking effects in combinatorialinteraction testing: A feedback drivenadaptive approach. IEEE Transactions on Software Engineering,40(1), 43–66.
Zeller, A., & Hildebrandt, R. (2002). Simplifying and isolating failure-inducing input. IEEE Transactions on
Software Engineering, 28(2), 183–200.
Zhang, Z., & Zhang, J. (2011). Characterizing failure-causing parameter interactions by adaptive testing.
In: Proceeding of ACM 20th International Symposium on Software Testing and Analysis (ISSTA), pp.
331–341.
Zhang, J., Ma F., & Zhang, Z. (2012). Faulty interaction identification via constraint solving and optimization. In: Proceeding of International Conference on Theory and Applications of Satisfiability Testing(SAT), pp. 186–199.
Zheng, W., Wu, X., Hu, D., & Zhu, Q. (2016). Locating minimal fault interaction in combinatorial testing.
Advances in Software Engineering, 2016, 10.
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps andinstitutional affiliations.

Kinari Nishiura received M.E. and Ph.D. degrees from Kyoto Instituteof Technology in 2018 and 2021, respectively. Currently, he is an
Assistant Professor at the Faculty of Information and Human Sciences,
Kyoto Institute of Technology, Japan. He was an assistant professor at
Okayama University from 2021 to 2024. His current research interests
include software testing, software repository mining, and fault-prone
module prediction.

Eun‑Hye Choi received M.E. and Ph.D. degrees from Osaka University in 1999 and 2002, respectively. She was a senior researcher at the
National Institute of Advanced Industrial Science and Technology.
Her research interests include software testing, verification and validation, and fault localization.

13

Software Quality Journal
Eunjong Choi is an assistant professor at Faculty of Information and
Human Sciences in Kyoto Institute of Technology, Japan since March
2019. Before joining Kyoto Institute of Technology, She was an assistant professor at Nara Institute of Science and Technology from April
2016 to March 2019 and at Osaka School of International, Osaka University from April 2015 to March 2016. Her research interests are in
the areas of software engineering, in particular, reused code management/detection and refactoring support.

Osamu Mizuno received M.E. and Ph.D. degrees from Osaka University in 1998 and 2001, respectively. Currently, he is a Professor at theFaculty of Information and Human Sciences, Kyoto Institute of Technology, Japan. His current research interests include software repository mining, fault-prone module prediction, software process improvement, and risk evaluation and prediction of software development. He
is a member of IEEE, IPSJ, and IEICE.

13