Exploring the Characteristics of Spectra Distribution and Their
Impacts on Fault Localization
Xiao-Yi Zhang∗

Zheng Zheng

National Institute of Informatics
Tokyo, Japan
xiaoyi@nii.ac.jp

School of Automation Science and Electronic Engineering,
Beihang University, BUAA
Beijing, Chinazhengz@buaa.edu.cn

ABSTRACTSpectrum-Based Fault Localization (SBFL) follows the basic intuitions that the faulty parts are more likely to be covered by failurerevealing test cases and less likely to be covered by passed test cases.
However, due to the diversity of programs and faults, many othercharacteristics (related to program structure, test suites, and typeof faulty components) will influence the practical application of
SBFL. For example, a statement can be covered by numerous failurerevealing test cases, and also covered by numerous passed test cases.
To get more indicators about the faulty components towards a better application of SBFL, we extend the scope of spectrum-basedknowledge from the basic intuitions to the Characteristics of Spectra
Distribution (CSDs for short). That is, we explore the relationships
between different types of statements and their spectra. Firstly, we
introduce the concepts of Failure-Independent, Failure-Related, andFailure-Exclusionary to describe the relationships between different types of statements and their executions. Then, we propose
two probabilistic models, with and without the noise of fault interference, respectively, to identify various CSDs for each type ofstatements. As the analysis results, we introduce a visualization
technique to generalize the identified CSDs and provide an overall
picture of spectra distribution and its dynamics. Finally, based on
our analysis and also the observation of the program spectra ofcurrent benchmarks, we design a technique to filter the potential
non-faulty statements to improve the accuracy of SBFL.

CCS CONCEPTS• Software and its engineering → Software creation and management; Software verification and validation; Software defect analysis;
Software testing and debugging.

KEYWORDS
software fault localization, spectrum-based fault localization, probabilistic model, spectrum-based characteristics, visualization∗ Xiao-Yi Zhang is the corresponding author.

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
EASE’20, April 15–17, Trondheim, Norway© 2020 Association for Computing Machinery.
ACM ISBN 978-1-4503-7731-7/20/04. . . $15.00
https://doi.org/10.1145/3383219.3383230

ACM Reference Format:
Xiao-Yi Zhang and Zheng Zheng. 2020. Exploring the Characteristics ofSpectra Distribution and Their Impacts on Fault Localization. In Evaluation and Assessment in Software Engineering (EASE 2020), April 15–17, 2020,
Trondheim, Norway. ACM, New York, NY, USA, 10 pages. https://doi.org/10.
1145/3383219.3383230

1

INTRODUCTION

Software fault localization [22] aims to find the faulty componentsthat cause the program failures detected during testing. To date,various studies pointing to the automation of fault localization
process have been conducted [2, 13, 15]. One of the most famous
fault localization techniques is Spectrum-Based Fault Localization(SBFL) [23, 26, 28]. Here, a program spectrum refers to a collectionof information that provides the characteristics of a specific program component [23]. SBFL takes the program spectra information
derived during testing to find the suspicious faulty componentsof the subject program. To date, studies on SBFL have been conducted from various aspects, such as different component particles[2, 20, 29], suspiciousness metrics [16, 21, 23, 26], and SBFL-orient
testing techniques [7, 25]. Note that we take a program statement
as the basic unit of component in this paper.
Generally, SBFL is based on two intuitions [28]:(1) statements covered by more failure-revealing test cases are
more likely to be faulty, and(2) statements covered by more passed test cases are less likely
to be faulty.
The above intuitions consider the passed and failure-revealing test
cases separately. Nevertheless, in practice, the fault propagation
process is complicated. Only considering these intuitions could beinsufficient. For example, even if a test case is failure-revealing,
it may cover many non-faulty components. Also, even if a faulty
statement has been executed, it may not cause failures (i.e., thecoincidental correctness phenomenon [14]). Furthermore, if the
program has multiple faults interacting with each other, the spectrum of a specific faulty statement may become more difficult tobe identified (i.e., the multi-fault problem [5]). Although various
SBFL-orient techniques have been proposed [1, 16], the challengeof providing more knowledge of program spectra to evaluate thepractical application of SBFL always exists.
In fact, except for the basic intuitions, there are also various characteristics related to the distribution of program spectra and can be
useful to improve SBFL. For example, statements in the main function are likely to be covered by both passed and failure-revealing

EASE’20, April 15–17, Trondheim, Norway
test cases. Also, to meet the safety requirements, redundant modules are usually introduced [10]. Then for such modules, they are
rarely covered by both the passed and failure-revealing test cases.
However, exploring and generalizing such characteristics arechallenging. As SBFL involves various artifacts, including the test
suite, and different types of statements, the Characteristics of Spectra
Distribution (CSDs for short) could also be complicated and be
related to multiple and heterogeneous artifacts (e.g., the propertyof statements and the test coverage information). Moreover, theinteractions among these artifacts are also complicated.
To pave the way from basic intuitions towards comprehensive
spectrum-related knowledge and get a better understanding andevaluation of the practical application of SBFL, this paper proposes
an appraoch based on probabilistic modeling and data visualization
to conduct an overall analysis of CSDs beyond the basic intuitionsof SBFL. Specifically, we focus on which types of statements have
which shapes of spectra. Firstly, we identify the program statements
as three types: Failure-Related, Failure-Exclusionary, and FailureIndependent, referring to the statements whose executions are relevant, exclusionary and independent to the manifestation of program
failures, respectively. Then, we propose a probabilistic model toformalize the behaviors among different types of statements andprogram failures, and summarize them as specific CSDs.
Particularly, we further consider the influence of fault interference in our model, under the assumption that different faulty
elements are independent. Specifically, the influence of different
faults is described as the noise. As a result, we derive some common points about the influence of the noise on different types ofstatements and describe them as the dynamics of CSDs. This work
is our primary step to explore formal descriptions for the instances
involving more than one faulty elements.
To generalize the analysis results, we propose an approach basedon visualization that presents program statements in the entire
spectra space. Through visualization, we integrate various identified
CSDs belonging to different types of statements in an intuitive way,
and then evaluate their influences on the performance of SBFL.
Finally, as an example to put our analysis into practice, we propose
a technique that identifies the potential non-faulty statements basedon the identified CSDs and eliminates them during SBFL.
The remainder of this paper is organized as follows. The background of SBFL is introduced in Section 2. The modeling of different
types of statements, and the exploration of CSDs are presented in
Section 3. The visualization of the derived results is presented in
Section 4. Based on visualization, we design a filtering techniqueto improve SBFL in Section 5. An experimental study is conductedin Section 6. Related works are discussed in Section 7. In Section 8,
we make conclusions and discuss the future works.

2

BACKGROUND: SPECTRUM-BASED FAULTLOCALIZATION

Given the subject program PG, with the set of statements S ={s 1, s 2, . . . , sn }. Assume PG has a faulty statement s f , then the basic
task of fault localization is to find s f in S. Here let s f ← s denotethat statement s is faulty. Now concerning Spectrum-Based Fault
Localization (SBFL), given a test suite T = {t 1, t 2, . . . , tm }, we let
C t denote the set of statements covered by t and ot ∈ {pass, f ail }Xiao-Yi Zhang and Zheng Zheng
denote the correctness of t. Thus, based on T , considering thecoverage of each s ∈ S, we can calculate the following quantities:• aef (s): the number of failure-revealing test cases that coverstatement s, i.e., |{t ∈ T |s ∈ C t , ot = f ail }|• aep (s): the number of passed test cases that cover statements, i.e., |{t ∈ T |s ∈ C t , ot = pass}|• anf (s): the number of failure-revealing test cases that do notcover statement s, i.e., |{t ∈ T |s < C t , ot = f ail }|• anp (s): the number of passed test cases that do not coverstatement s, i.e., |{t ∈ T |s < C t , ot = pass}|
In addition, let F and P denote the total number of the failurerevealing and passed test cases, respectively.
The basic idea of SBFL is to predict the likelihood of being faulty
for each s ∈ S. Specifically, the suspiciousness degree that s f ← s
can be calculated by a formula R composed of the above quantities.
In this sense, the basic intuition of SBFL can be interpreted as:(1) the larger aef (s) value that statement s has, the more suspicious it is, and(2) the smaller aep (s) value that statement s has, the more suspicious it is.
Currently, various metrics have been proposed following theabove two intuitions. Also, different metrics are based on their own
heuristics to arrange the composition of aef (s) and aep (s). Oneof the earliest metric, Tarantula [8], denoted by Rτ is designed asfollows:Rτ (s) =aef (s)/Faef (s)/F + aep (s)/P(1)

Subsequently, it has been observed that failure-revealing test
cases are more important to expose the faulty statements. Basedon this observation, Abreu et al., [1, 2] proposed the Ochiai metric,
denoted by R O , expressed as follows:
aef (s)R O (s) = q(aef (s) + anf (s))(aef (s) + aep (s))(2)

Furthermore, Naish et al. [16] proposed a famous metric called
Op, denoted by R O , which put the term aef (s) at a dominant position. The expression of R O is shown as follows:
R O (s) = aef (s) − aep (s)/(P + 1)

(3)

Note that although various metrics as been proposed, such as
the families of DStars[21] and GPs [26], current studies [30] andalso our ongoing works has observed that some metrics, although
they may not be equivalent, have similar performance (e.g., R O andDStars, and the family of continuous maximal metrics) [27]. Thus,
according to our knowledge, this paper will consider Rτ , R O , andR O as representative. After the calculation based on the selected
metric, SBFL ranks the statements according to their suspiciousness
degrees in descending order and provides the rank list as output.
If it is accurate, the faulty statement s f will be ranked ahead andthen can be found earlier by the testers.

Exploring the Characteristics of Spectra Distribution and Their Impacts on Fault Localization EASE’20, April 15–17, Trondheim, Norway

PROBABILISTIC MODEL FOR STATEMENTS’
SPECTRA AND PROGRAM FAILURES
3.1 Three Types of Statements

s0

3

3

1

s0

2

Definition 1. Failure-Independent Statement. If the execution of statement s is not correlated with the manifestation of program failures, s will be considered as Failure-Independent, denotedby s I ← s.
Example 3.1.
• If statement s is included in the main function of PG, then it
will be covered by all the test cases, whether these test cases
are failure-revealing or not.
Definition 2. Failure-Related Statements. If the executionof s is correlated with the manifestation of program failures, then swill be considered as Failure-Related, denoted by s R ← s.
Example 3.2.
(1) If statement s belongs to the function that triggers the executionof the faulty statement s f , then the execution of s may cause ahigher failure rate.
(2) If statement s belongs to the module that proceeds a specific
type of system exception caused by s f , then the execution of s
will lead to a higher failure rate.
Definition 3. Failure-Exclusionary Statement. If the execution of statement s leads to a lower probability of failure, then s isconsidered as Failure-Exclusionary, denoted by s E ← s.
Example 3.3.
• If modules A and B belong to different branches of program
PG, while module B contains the faulty statement s f , thenstatements in A could have a relatively lower failure rate.

3.2

Probabilistic Model without Noises

To analyze the relationship between the execution of each statements ∈ S and the manifestation of program failures, we make thefollowing assumptions.
Assumption 1. The faulty statement s f ∈ S exists.
Assumption 2. PG is deterministic. That is, a failure-revealing
test case t will definitely cause failures whenever it is executed.

Noise
2
3

1

In this section, we categorize the program statements into three
types according to how their spectra can be affected by program failures: the Failure-Independent statements, the Failure-Related Statements, and the Failure-Exclusionary Statements.

1

s
4
Pass

2

3

s

5
Fail

4
4

5

Pass

Fail

Figure 1: The basic modelfor the relationship beFigure 2: The model oftween the execution ofstatement-failure relationstatement s and the manship involving the noise.
ifestation of program
failures.

Fig. 1 presents the simplified transition model from the program
entrance to the final output, in which statement s is treated as anintermediate state2 . When executing a test case t, the execution
trace will start from the program entry s 0 and have a probability
to cover statement s. Finally, it produces an output with a certain
probability of failure. Specifically, for statement s and test case t,
the probability of each transitions in Fig. 1 is presented below.
• φ s1 : the probability that t does not cover statement s and gets
passed, i.e., P(s < C t , ot = pass)• φ s2 : the probability that t does not cover statement s andreveals a failure, i.e., P(s < C t , ot = f ail)
• φ s3 : the probability that t covers statement s, i.e., P(s ∈ C t )• φ s4 : the probability that t gets passed, under the condition
that t covers statement s, i.e., P(ot = pass |s ∈ C t )• φ s5 : the probability that t reveals a failure, under the condition
that t covers statement s, i.e., P(ot = f ail |s ∈ C t )Here P(·) represents the meaning of probability. In addition, thefollowing relations should be satisfied:
φ s1 + φ s2 + φ s3 = 1, φ s4 + φ s5 = 1
φ s1 + φ s2 = P(s < C t )φ s1 + φ s4 · φ s3 = P(ot = pass)
φ s2 + φ s5 · φ s3 = P(ot = f ail)(4)

Now suppose test suite T is executed based on this model, thenwe can calculate some expected spectrum values as follows:
E(P) = |T |(φ s1 + φ s4 · φ s3 )Assumption 3. The test suite T has already been given and weknow both its coverage and correctness information.

E(F ) = |T |(φ s2 + φ s5 · φ s3 )Assumption 4. The test cases in T are generated randomly following a common profile1 .

E(aep (s)) = |T |(φ s3 · φ s4 )E(aef (s)) = |T |(φ s3 · φ s5 )(5)Based on these assumptions, the relationship between the execution of a statement s and the manifestation of program failures
can be modeled as a discrete Markov Chain, illustrated in Fig. 1.

In this way, this probabilistic model, can be regarded as a formal
description of the fault propagation process within the domain ofprogram spectra. Then, we make further exploration of each typeof statements identified in Section 3.1.

1 Here, we do not expect an entirely random testing. Instead, we assume that the

2 Although there could be other statements that influence the execution of s , from thegeneration of test cases follows a common rule of randomness (e.g., pure random
testing or proportional sampling) and does not rely on fault-based knowledge.

perspective of s , all these influences can be integrated into the transition from theentrance s 0 to s .

EASE’20, April 15–17, Trondheim, Norway

Xiao-Yi Zhang and Zheng Zheng(1) Failure-Independent Statement. Based on Definition 1, a
Failure-Independent Statement s I should have
sI

sI

sI

sI

φ 5 = φ 2 and φ 4 = φ 1

all the failure-revealing test cases should cover s f , i.e., we haveaef (s f )
aef (s f ) + aep (s f )

(6)

>

F
F +P

(13)

f

φ s2 = 0

Then we have

(14)

I
I
E(P) = φ s1 (1 + φ s3 )E(F ) = φ s2 (1 + φ s4 )
I

I

3.3

E(ae f (s I )) = |T |(φ s3 · φ s2 )I

E(aep (s I )) = |T |(φ s3 · φ s4 )
I

I

(7)

Thus we can deriveae f (s I ) + aep (s I )
=

φ s5

I

φ s4 + φ s5I

I

|T |(φ s3 · φ s5 )I
I
II
|T |(φ s3 · φ s4 ) + |T |(φ s3 · φ s5 )I

ae f (s I )

≈

≈

F
F +P

I

(8)

(2) Failure-Related Statements. Based on Definition 2, if astatement s R is Failure-Related, we should haveφ s5 > φ s2 and φ s4 < φ s1
R

R

R

R

(9)

and then we can derive thatae f (s R )ae f (s R ) + aep (s R )

>

F
F +P

(10)

(3) Failure-Exclusionary Statements. Based on Definition 3,
if a statement s E is Failure-Exclusionary, then we haveφ s5 < φ s2 and φ s4 > φ s1
E

E

E

E

(11)

and then we can derive thatae f (s E )ae f(s E ) + a

ep(s E )a(s)<

Probabilistic Model With Noises

I

F
F +P

(12)

ef
In summery, let qe (s) = a (s)+adenote the failure rate ofepe f (s)Fstatement s and let q = F +P denote the overall failure rate, thenwe have the following characteristic.

Characteristic 1. Based on the Assumption 1 to Assumption
4, the failure rate of the Failure-Independent, Failure-Related, andFailure-Exclusionary statements are equal, higher, and lower than theoverall failure rate, respectively.
Now assume the program failures are caused by the only faulty
statement s f and not affected by other factors. Then, s f is the root
cause of the detected failures. In this case, all the failure-revealing
test cases will cover s f . Otherwise, if a test case does not cover s f ,the program failures will not be detected. Then we can derive thefollowing characteristic.

Characteristic 2. Assume there is only one faulty statements f . Based on Assumptions 1 to 4, s f should be Failure-Related andOne of the basic assumptions behind the model in Section 3.2 isthat the subject program PG has only one faulty statement. That
is why we can derive Eq. (14). However, in many situations, thesubject program contains multiple faulty factors (e.g., incorrect
environmental settings or other faulty components). Different faults
interact with each other and influence the program spectra used in
SBFL. As a result, the accuracy of SBFL could be degraded. It has
been observed that, for some SBFL metrics, a slight degree of faultinterference can lead to a significant performance degradation.
In this work, we focus on improving the explainability of faultinterference. Then, we could get more guidances to solve to themulti-fault problems better. Specifically, we conduct a further analysis based on our probabilistic model to explain the occurrence offault interference and then find some meaningful characteristics.
Here, we model the mechanism of fault interference as a moduleof the noise, denoted by N , as shown in Fig. 2. In other words, we
use N to represent the complicated effects caused by system environmental factors or the other faulty statements3 . Here, we assume
that, during the execution of each test case t, the program has theprobability of being infected by N . Once the program is infected,
whether it fails or not will be entirely decided by N . Specifically, we
have P(ot = f ail |s ∈ C t , N ∈ C t ) = P(ot = f ail |s < C t , N ∈ C t ).
Modeling the fault interference as the noise under this assumption
makes our analysis explicit, and it is reasonable because of thefollowing reasons:(1) The analysis of the noise can provide a fundamental andquantitative evaluation of the robustness of SBFL.
(2) If the program has multiple faults, it is likely to exist a dominant faulty statement that causes the main characteristics
of spectra distribution. Then, other faults are likely to becorrelated with only a few statements, and their effects canbe eliminated [5].
(3) Although there are situations that multiple faults determine
the program failures together, such situations can be approximated to our model through the assignment of the valuesof ε 2 , ε 3 , and ε 4 in Fig. 2.
(4) Many other faulty statements have lower aef values (e.g.,faults in some remote modules) and do not have much influence on the target faulty statement. As a results, their
behaviors are similar to the noise.
Consequently, the probabilistic model considering the noise module is shown in Fig. 2. Compared with the basic model shown in
Fig. 1, concerning a test case t and statement s, additional notations
are listed below.
3 Although we may not have a “target” faulty statement in practice, the result of

SBFL will probably assign one faulty statement with higher priority. Then, this faulty
statement can be treated as “target” in fault localization.

Exploring the Characteristics of Spectra Distribution and Their Impacts on Fault Localization EASE’20, April 15–17, Trondheim, Norway
S (s)/a S (s).4 However, after considering the noise, such proporaef
ep

The "Noise" part:
The "Signal" part:the original proportion between the proportion of failure rates
concerning the noise module
local and overall failure ratetion becomes toa eSf (s)+a eNf (s), which is closer to the failure rate of

S (s)+a N (s)a ep
ep
N (s)/a N (s). On the other hand, the overall
the noise module, i.e, aef
epfailure rate has also changed from the original signal part F S /P S

Figure 3: The characteristics of spectra distribution in theprobabilistic model with the noise module.

• ε 1s : the probability that t covers N and does not cover s, i.e.,P(N ∈ C t , s < C t )• ε 2s : the probability that t covers N and also covers s, i.e.,P(N ∈ C t , s ∈ C t )• ε 3s : the probability that t covers N and gets passed, i.e., P(N ∈C t , ot = pass)• ε 4s : the probability that t covers N and reveals a failure, i.e.,P(N ∈ C t , ot = f ail)Obviously, due to the introduction of ε 1s to ε 4s , the probabilities
from φ s1 to φ s5 will decrease. Specifically, similar to Eq. (5), thequantities used by SBFL can be calculated as follows:P ≈ |T |(φ s1 + φ s4 · φ s3 + ε 1s · ε 3s + φ s3 · ε 2s · ε 3s )F ≈ |T |(φ s2 + φ s5 · φ s3 + ε 1s · ε 3s + φ s3 · ε 2s · ε 4s )ae f (s) ≈ |T |(φ s3 · φ s5 + φ s3 · ε 2s · ε 4s )aep (s) ≈ |T |(φ s3 · φ s4 + φ s3 · ε 2s · ε 3s )(15)Then, we can calculate the following ratios related to the failurerate:
aef (s) φ s3 · φ s5 + φ s3 · ε 2s · ε 4s≈
(16)
aep (s) φ s3 · φ s4 + φ s3 · ε 2s · ε 3s
φ s + φ s5 · φ s3 + ε 1s · ε 4s + φ s3 · ε 2s · ε 4sF
≈ s2P
φ 1 + φ s4 · φ s3 + ε 1s · ε 3s + φ s3 · ε 2s · ε 3s

(17)

Finally, we can derive the equation shown in Fig.3.
The dashed boxes in Fig. 3 divide the equation into two parts.
The left part and the right part express the spectra characteristics
related to the signal and the noise, respectively. Specifically, theleft part enclosed by the red dashed box can be regarded as thesignal, denoted by S. It approximates to the proportion between theS (s) and the original
original failure rate of s, denoted by aeSf (s)/aep
overall failure rate, denoted by F S /P S , as identified in Section 3.2.
On the other hand, the right part enclosed by the blue dashed box
can be treated as the spectra of s only considering the noise module,
such that each term contains at least one properties from ε 1s to ε 4s .
Also, it just approximates to the proportion between the failure rate
N (s) and the overall failure rate, denotedof s, denoted by aeNf (s)/aep
by F N /P N , only considering the noise.
Now, suppose statement s is Failure-Independent, Failure-Related,
and Failure-Exclusionary, respectively. Then, without the noise, thecharacteristic of its spectrum can be reflected by its failure rateto (F S + F N )/(P S + P N ), getting closer to the overall failure rateof the noise module, i.e., F N /P N .
Moreover, from Fig. 3, we can also derive that
N (s)
aef

φ s3 · ε 2s · ε 4s
ε 1s · ε 4s + φ s3 · ε 2s · ε 4s
ε 4s
FN
≈
≈
=
≈
N (s)
φ s3 · ε 2s · ε 3s
ε 1s · ε 3s + φ s3 · ε 2s · ε 3s
ε 3s
PN
aep

(18)

In general, based on the model with the noise module, both thelocal failure rate of statement s and the overall failure rate, aregetting closer to the failure rate of the noise module, i.e., ε 4s /ε 3s .
Specifically, we have the following conclusions:Characteristic 3. After the introduction of the noise module,
the failure rate of statements, i.e., aef (s)/aep (s), changes towards thefailure rate of the noise module, i.e., ε 4s /ε 3s .
Characteristic 4. After the introduction of the noise, the overall failure rate, i.e., F /P, changes towards the overall failure rate of
the noise module, i.e., ε 4s /ε 3s .
Characteristic 5. The relationship between a statement s
and program failures (i.e., Failure-Independent, Failure-Related, andFailure-Exclusionary) may change after adding the noise. The direction of this change depends on both the failure rate of the noise module
N , i.e., ε 4s /ε 3s , and the relationship between s and N . Specifically,(1) Assume ε 4s /ε 3s ≈ F /P, i.e., the failure rate of the noise module
is approximate to the failure rate of the signal parts. Then,
F /P is approximate to the original F S /P S . Also, the originalcorrelation between s and program failures can become weak.
Specifically, the failure rates are getting lower, higher, andkeeping the same for the Failure-Related, Failure-Exclusionary,and Failure-Independent statements, respectively.
(2) If ε 4s /ε 3s , F S /P S , the situation is complicated. Specifically,
the initial failure rate that larger or smaller than ε 4s /ε 3s will
become smaller or larger, respectively. However, the change ofthe correlation between s and program failures, i.e., whether
it becomes more Failure-Related or Failure-Exclusionary also
depends on the change of F /P.
(3) Assume s has a low execution rate in the signal part, while
it has a high execution rate in the noise module. Then, theinfluence of the noise on the original correlation between s andprogram failures is obvious. On the contrary, the influence on
S (s f ) = F is likely
the faulty statement s with the spectrum aef
to be slighter than other statements with similar failure rates.

4

VISUALIZATION OF THE SPECTRA
DISTRIBUTION CHARACTERISTICS

In this section, we introduce a visualization approach to generalize
the results in Section 3 and provide an overall observation about
4 Here, we use a S (s)/a S (s) instead of the actual failure rate a S (s)/(a S (s) +
ep
ep
ef
ef
a eSf (s)) for the convenience of calculation. This operation will be applied in thefollowing parts of the paper.

EASE’20, April 15–17, Trondheim, Norway

Xiao-Yi Zhang and Zheng Zheng
The diagonal Liney = (P/F ) x

a ep

aep

Movement
Directionf y = 3Px/(2F) – P/2
l：

P

P

Filtered Area

Baseline ofSpectra Movementy = ( 4/ 3)xsf

Reserved Area

F a ef

F/3

Figure 5: Visualization of
Figure 4: The visualization
the dynamics of programof the characteristics ofspectra when concerning
spectra distribution
the noise.
spectra distribution and its dynamics after involving the noise. The
approach of visualization is based on the concept of Spectra Space(SS) [27], which is a coordination system in which the x-axis indicates the meaning of ae f , and the y-axis indicates the meaningof aep , as shown in Fig. 4. Then, the spectrum of each statements is presented as an image point in SS, denoted by ι(s), with thecoordination values of (ae f (s), aep (s)). Note that, because at eachs, we have ae f (s) < F and aep (s) < P, SS is actually a box enclosedby the lines x = F , y = P, x = 0, and y = 0. Now, given an SBFL
instance, we can obtain the value of F and P, and then visualize
all the statements in SS according to their spectra. Then, we canobserve the characteristics of the spectra distribution of each SBFL
instance (illustrated as the distribution of image points in Fig. 4).
Through summarizing different SBFL instances, we can get an intuitive image about the distribution patterns of program spectra,
which corresponds to the results found in Section 3.
Fig. 4 reflects the CSDs of each type of statements. Specifically,
the image points of Failure-Independent statements will be distributed around the diagonal line of SS, depicted as the blue area.
Meanwhile, the image points of the Failure-Related and FailureExclusionary statements are distributed below and above the diagonal line of SS, respectively (shown as the red and green areas).
Furthermore, Fig. 5 illustrates the visualization of the change of
the CSDs after suffering the noise caused by multi-fault interference, as discussed in Section 3.3. Here, the analytic expression of
the diagonal line, i.e., y = (P/F )x, denoted by l d , is treated as anindicator. Specifically, suppose the fault inference, caused by otherfaulty elements and modeled as the noise, exists. Then, the positionof all the artifacts in SS, including the image points of program
statements, the diagonal line, and the target faulty statement s f ,will change. According to Characteristics 3 to 5, the baseline ofsuch movement is the line with analytic expression of y = (ε 3 /ε 4 )x(i.e., the failure rate of the noise module N ), denoted by l b . All the
points of program statements including the faulty statement, andthe diagonal line l d will get closer to the baseline l b . Specifically,
we can have the following graphical CSD:
Characteristic 6.
(1) For statement s, if ι(s) is below both the lines of l b and l d , thenι(s) may take a left-top move, and its correlation with program
failures may become weak.
(2) For statement s, if ι(s) is above both l b and l d , then ι(s) may
take a right-bottom move, and its correlation with program
failures tends to be enhanced.

F aef

Figure 6: The filtered area in SS(3) For statement s, if ι(s) is between the lines of l b and l d , thenι(s) tends to move towards the line of l b . Nonetheless, becausel d also tends to move toward l b , the variation of its correlation
with the program failures should further depend on the relative
degrees of these movements.
Compared with the Characteristics in Section 3.3, Characteristic
6 is more intuitive and it presents a general picture of the program
spectra’s movement under the noise. Specifically, the results can beunderstood from two aspects:(1) Under the noise introduced from fault interference, all theimage points tend to move towards the baseline l b , including
the faulty statement s f . Thus, the property of s f may get
more implicit (i.e., ι(s f ) may not be at the boundary line
x = F ). In this sense, fault interference indeed takes negative
effects.
(2) On the other hand, the movements of the statements’ image
points follow explicit rules. If the noise is not strong (i.e., ε 1s
and ε 2s are not significant), the degree of movement will beslight. Furthermore, the faulty statement s f has the largest
original aef (s f ) value. Thus, the degree of movement of its
spectrum could be less than other statements with similar
failure rates. In this sense, SBFL is also reasonable under aslight degree of fault interference.

5

EXAMPLE FOR USAGE: A FILTER FOR
ELIMINATING NON-FAULTY STATEMENTS

From the above analysis, we find a series of CSDs. In this section,
we explore the usage of these CSDs to improve SBFL. Specifically,
as a first step, we design a filter that eliminates the statements
whose spectra are not fault-prone based on the derived CSDs. The
following strategies are adopted:(1) The Failure-Independent and Failure-Exclusionary statements
should be filtered. Intuitively, because the faulty statement
is the root cause of program failures, it should be FailureRelated. However, Failure-Independent and Failure-Exclusionary
statements may also have large values of aef or small valuesof aep , which may mislead the application of SBFL metrics.
Thus, we can eliminate them during the execution of SBFL.
(2) The negative effects cause by fault interference can be, tosome extent, filtered. According to Characteristic 5, becauseof the noise, the image point of the faulty statement s f , i.e.,ι(s f ), is likely to take a left-top move. This may cause thenegative effect that aef (s f ) < F . However, some SBFL metrics (e.g., Op) assign the term aef with a high weight. As

Exploring the Characteristics of Spectra Distribution and Their Impacts on Fault Localization EASE’20, April 15–17, Trondheim, Norway
a result, the statements whose image points are near theright-top area of SS may have higher suspiciousness values than s f . Thus, it is reasonable to filter such statements
which are likely to be Failure-Independent. On the other hand,as analyzed in Section 4, because the movement of ι(s f ) isslighter than other ι(s)s, ae f (s f ) should not be very small,even though the noise exists. Thus, it is reasonable to filter
statement s, if ι(s) is at the left part of SS.
Based on the above analysis, Fig. 6 illustrates the design of thestatement filter. Specifically, in SS, we introduce a filter line, denotedby l f , with the analytical expression of y = 3P
2F x − P/2. Statements
whose image points are above this line will be filtered. Concerningl f , it is near the diagonal line of SS. Thus, the eliminated statements
are more likely to be Failure-Independent or Failure-Exclusionary.
Also, l f is below the diagonal line. Thus, it also filtered the statements with image points near the original point (0, 0) and the righttop point (F, P). Generally, the SBFL technique integrated withstatement filter (SBFL-Filter for short) is presented in Algorithm 1.
Algorithm 1 SBFL with statement filter
Input: PG : the subject program with set of statements S ; T : the executed
test suite;
Output: L: the rank list of SBFL;
1: calculate the overall quantities F and P ;2: for each s in S do
3:calculate a e f (s) and a ep (s);4:calculate the suspiciousness value R(s) use conventional SBFL;
5: end for
6: present all the information in the Spectra Space;
7: draw the filter line l f ;8: Initialize S f il t e r ← ∅, S r e s e r v e ← ∅;9: for each s in S do
10:
if s is above l f then11:
Let S f il t er ← S f il t e r ∪ {s }
12:
else
13:
Let S r es er v e ← S r e s e r v e ∪ {s }14:
end if
15: end for
16: for each s in S f il t e r do R(s) ← R(s)−M , M is large enough satisfying
R(s) > M , ∀s ∈ S ;17: end for
18: Re-rank the statements according to their new suspiciousness values
and get L;

Note that, when filtering the negative effects caused by the noise,some Failure-Related statements will also be included. Thus wemay have threats to eliminate the real faulty statement. Therefore,
how to trade off the potential benefits and the threats should beconsidered. In our approach, the filter area (i.e., the green shadow
part in Fig. 6) is quite small at the top-right part of SS. This indicatesthat the filtering strategy on this part is quite moderate. Also, theshadow area contains only a small region of the left-bottom partof SS (i.e., near the original point). Specifically, l f intersects withthe x-axis at the point of (F /3, 0), which means only the aef (s f )value smaller than F /3 will be eliminated. Unless the program
has more than three completely exclusive faulty statements withsimilar failure rates, ι(s f ) cannot move to the right part of x =F /3. Furthermore, we try to improve the stability of our filter by
reserving the top ten statements in the rank list of SBFL. That is,for SBFL instances whose outputs are already accurate, our filter
does not take effects.

Table 1: Details of the benchmark programs and faults
Suite

Programs

Fault No.

LOC

Size of test suites

Unix

flex
grep
gzip
sed

53
17
17
26

10,45910,0685,680
14,427

567
809
217
370

Siemens

print_tokens
print_tokens2
replacetcas
scheduleschedule2
tot_info

5
9
29
41
5
9
23

472
399
512
141
292
301
440

1,608
2,650
2,710
1,052
4,130
4,115
5,542

Space

space

33

6,199

13,585

Defects4J

Chart
Closure
Math
Lang
Time

26
133
106
65
27

96k
90k
85k
22k
28k

2205
7927
3602
2245
4130

6 EMPIRICAL STUDY
6.1 Research Questions
In this section, we conduct an empirical study to show the effectiveness of the statement filter, and also examine the CSDs in real
SBFL instances. The following research questions are explored:
RQ1: Can the statement filter improve the accuracy of SBFL?
RQ2: Which factors (e.g., different subject programs and SBFL
metrics) can affect the performance of SBFL-Filter?
RQ3: Which CSDs cause the performance of SBFL-Filter decline/increase? Are they in accord with our analysis?

6.2

Empirical Setup

In the empirical study, four UNIX utility programs (including flex,
grep, gzip, and sed), the Space program, and the Siemens suite (including seven subprograms: print_tokens, print_tokens2, replace, tcas,
schedule, schedule2, and tot_info) are selected as benchmarks. These
programs are derived from the Software Infrastructure Repository(SIR) [6]. In SIR, each program is attached to several benchmark
faults. This paper discusses the CSDs for both single-fault and faultinterference situations. Thus, we generate and examine both thesingle-fault and multi-fault versions. For single-fault instances, all
the benchmark faults are examined one by one. For multi-fault
instances, we combine different faulty statements such that theycan exist together in the same instance. Here, we check 2-fault and3-fault situations, respectively [5, 24].
In addition, we also use Defects4J[9] , a dataset including fivejava projects Chart, Closure, Lang, Math and Time. The projects arewith the scales from 28 KLOC to 96 KLOC and with real-life faults.
Here, we do not combine different faulty statements to form multifault instances, such that the property of real-life faults remains.
Specifically, we use the data derived in [18]. The details of thebenchmarks are shown in Table 1.
In the empirical study, we run conventional SBFL and SBFLFilter, respectively, and compare their performances. There aremany criteria to evaluate the performance of SBFL according todifferent requirements of practical applications. Because our work
mainly focuses on theoretical analysis, we intend to evaluate theEASE’20, April 15–17, Trondheim, Norway

Xiao-Yi Zhang and Zheng Zheng

accuracy of SBFL in a typical way. Therefore, we adopt a tradition
criterion Expense, defined as the percentage of statements that rank
above the faulty statement s f . Note that we use average ranking
as the tie-break strategy. During the execution, we also record theaef (s) and aep (s) values for each statement s such that the spectra
distribution of each SBFL instance can be observed. When dealing
with multi-fault versions, we set the faulty statement that ranks
above the other faulty statements as the target faulty statement,i.e., s f , and treat the other faulty statements as the noise.

6.3

Result and analysis

To answer RQ1, we conduct an overall comparison and present theresults in Table 2. The first column records the benchmark programs,
while the first row records the adopted SBFL metrics. At each metric,
the columns “better” and “worse” indicate the number of faulty
versions in which SBFL-Filter takes positive and negative effects(i.e., increases and decreases the SBFL accuracy), respectively.
Table 2: Comparison of conventional SBFL and SBFL-Filter.
Op
flex
grep
gzip
sed
SiemensSpace
Chart
Closure
Lang
Math
Times
Total

Ochiai

Tarantula

BetterWorse

BetterWorse

Better

Worse

32
8
9
38
52
15
1
7
0
1
0
163

0
0
3
0
0
0
0
1
0
0
0
4

39
26
3
2
89
33
1
1
1
0
0
195

14
13
4
0
30
18
0
0
0
0
0
79

741
269
154
114
637
322
3
11
4
6
1
2262

77
23
15
0
98
78
0
2
0
0
0
293

From Table 2, the filter designed based on the identified CSDs
can indeed improve SBFL. Concerning all the programs and metrics,
SBFL-Filter performs better than conventional SBFL on 2620 SBFL
instances, including both single-fault and multi-fault instances, overeight times than the number of instances that SBFL-Filter performs
worse. Note that we do not consider the instances with Expense
values larger than 0.3 (i.e., the outputs are entirely inaccurate).
Because if SBFL itself is not suitable for these instances, it does
not make much sense whether we adopt the filter or not (In fact,
SBFL-Filter can get improvement at most of these instances).
Furthermore, we try to answer RQ2. Specifically, we further
examine the performance of SBFL-Filter on different subject programs and SBFL metrics. Considering different subject programs,
SBFL-Filter has different performances. It has the most stable performance on sed, in which we have 154 better SBFL instances and 0
worse instances. The filter also performs well at Siemens programswith 778 better SBFL instances. However, we also have 128 worse
SBFL instances. We infer that the impacts of different subject programs are mainly due to the variety of program structures and fault
types, which leads to the diversity of spectra distribution. Some
programs are organized with the structure in which the executionof a component may not depend on the status of other components(e.g., the faulty statement). As a result, the SBFL instances based onthese programs may contain a large number of Failure-Independent

statements that may mislead some SBFL metrics (e.g., R O ). In thesesituations, our filter can effectively eliminate these statements. In
addition, for Defects4J programs, we only examine the real-lifefaulty versions (i.e., considering the fixing patches one by one).
Thus, the produced SBFL instances are likely to possess the property of single-fault scenarios (i.e., ae f (s f ) = F ), even if the numberof faulty statements is more than one, as shown in Fig. 8. Thus,
the improvement of SBFL-Filter is not significant. However, it isalso visible and stable, including 37 improved instances and only 3
degraded instances.
Moreover, the properties of faulty statements may also influence
the performance of SBFL-Filter. Suppose the program has multiple
faulty statements, that cause the movement of s f . Then, our filter
can eliminate some statements located in the right part of ι(s f )produced due to this movement. However, suppose both the degreeof fault interference and the degree of coincidental correctness arehigh5 . Then, ι(s f ) itself could move to the area that is eliminatedby the filter. In such situations, the filter may take adverse effects.
Nevertheless, as discussed in Section 5, the design of the filter isquite conservative and it does not take negative effects in most
instances. On the other hand, it is still valuable to further explore
more comprehensive knowledge of spectra distribution and thenrefine the SBFL-Filter.
Considering SBFL metrics, Fig. 7 presents the representative
instances in which SBFL-Filter performs well on the metrics of Op,
Ochiai, and Tarantula, respectively. Firstly, the SBFL-Filter has themost stable performance on metric Op, with 163 better instancesand only 4 worse instances. One of the main reasons is the extreme
strategy of Op, which puts aef (s) in the dominant position. Becauseof this, it has maximal performance for single-fault situations but
has lower robustness to fault interference [24]. Thus, the applicationof SBFL-filter could be useful (as shown in Fig. 7(a)).
Also, SBFL-filter performs well at Tarantula on 2262 better instances and 293 worse instances. Tarantula mainly considers thefailure rate of each statement, i.e., aef (s)/aef (s). Thus, it does notgood at identifying the statements that are Failure-Related but notfrequently covered by test suite T . The image points of such statements are likely to be close to the original point of SS, i.e., (0, 0),and will be eliminated by the filter (as shown in Fig. 7(c)).
Finally, for metric Ochiai, its expression is equivalent to the formula of aef (s)2 /(aef (s) + aep (s)), which considers both the statement’s failure rate aef (s)/(aef (s)+aep (s)) and the failure frequency
aef (s). Compared with the other two metrics, it is more robust.
However, the image points located between the diagonal line andthe right-bottom area are also misleading, and these statements canbe partially eliminated by our filter (as shown in Fig. 7(b)).
Table 3: Comparison of different SBFL metrics after applying statement filter.
MetricOp

Ochiai

TarantulaAll

Better No.
Worse No.

39
3

50
4

2004
217

11
0

5 Here, coincidental correctness refers to the phenomenon that test cases cover s f but

do not reveal failures. It is a critical issue to be considered in SBFL [14].

Exploring the Characteristics of Spectra Distribution and Their Impacts on Fault Localization EASE’20, April 15–17, Trondheim, Norway
derived Characteristics of Spectra Distribution beyond the basic intuitions of SBFL. Furthermore, the SBFL-Filter processes the spectra
information can be combined with other techniques (such as thetest case prioritization techniques [25]).

(a) Op(b) Ochiai(c) Tarantula

Figure 7: The spectra distribution of the instances with ourstrategy has good performance at each SBFL metric.

Figure 8: A representative
Figure 9: The areas in SS
instance of spectra distrithat could be misidentified
bution in Defect4J (Closure,by R O , R O , Rτ
faultID 76)(a) flex, v1, three-fault instance(b) Siemens, replace

Figure 10: The spectra distribution of the instances at with
our strategy has good performance on all the SBFL metrics.

To summarize the performance of SBFL-Filter on different SBFL
metrics and also to answer RQ3, we present the number of faulty
versions in which the filter can derive better/worse results at only
one SBFL metric (See the columns of Op, Ochiai, and Tarantula ofTable 3). In addition, Fig. 9 illustrates the areas in which each metriccan produce errors (i.e., ranking the statements belonging to theseareas ahead of the target faulty statement s f )6 . We can observe that,
all the metrics have their own “blind” area and each of them canbe partially eliminated by our filter. Also, there are situations that
SBFL-Filter can perform well on all SBFL metrics (shown in the Allcolumn of Table 3). Fig. 10, illustrates the spectra distribution of the
SBFL instances in which SBFL-Filter can improve the accuracy offault localization at all the metrics. We can observe that the spectra
distribution of these SBFL instances possess the characteristics thatmislead each SBFL metrics, respectively.
Generally speaking, the SBFL-Filter is an effective techniqueto refine the localization results. It indeed takes into account the
6 The figure is based on our analyses in answering RQ2 and also based on the analysisof the performance of each SBFL metric in the Spectra Space

7

RELATED WORKS

Spectrum-Based Fault Localization (SBFL) is one of the most typicalfault localization techniques [22]. The core of SBFL is the metrics
that calculate the fault proneness for each program component.
Jone et al. [8] developed the typical metric, named Tarantula. Since
then, various metrics have been proposed [1, 2]. Naish et al. [16]innovatively made a general theoretical comparison among various
metrics and grouped them into several equivalent categories. Xie etal. [23] further proved the performance among each equivalent categories and proposed the concept of maximal metrics. Furthermore,
Yoo et al. [26] proposed a generative approach to find new metrics.
To the best of our knowledge, studies on exploring the laws of theoverall program spectra distribution have not been well conducted.
In addition, studies on optimizing the SBFL process have also
been conducted from various aspects, such as the quality of test
information [4, 7, 25, 28] and coincidental correctness [14]. Parnin
et al. [17] discussed the challenge of how to make SBFL results
support the debugging process. Pearson et al. [18] made an overall
experimental study of different fault localization techniques using
various benchmarks. Perez et al. [19] analyzed the diagnosabilityof fault localization.
Recently, Deep Learning (DL) is a hot topic and tends to be concerned in software engineering [3, 12]. Li et al. [11] adapted deeplearning approaches to fault localization such that more featuresfrom different dimensions can be adopted. Nevertheless, we thinkthat it is still useful to explore the knowledge of spectra distribution
as well as other theories related to SBFL. Firstly, we can derive amore comprehensive understanding of fault localization. Moreover,The mining of spectra characteristics involving heterogeneous artifacts can help us identify more essential features. This will improvethe explainability of DL-based approaches and facilitate the construction of more reasonable deep networks for fault localization.

8

CONCLUSION AND FUTURE WORK

To pursue the basic intuitions of SBFL, this paper conducts a further
exploration of the Characteristics of Spectra Distribution (CSDs).
We mainly focus on how the relationship between the coverageof program statements and the manifestation of failures can bereflected in program spectra. In particular, our analysis is not limited
to single-fault scenarios. The effect of fault interference, model as
the noise module, is also discussed. As a result, we extend the baseof SBFL-related conclusions and present them as a series of CSDs.
Specifically, the contributions of this paper are listed below:(1) We proposed the concepts of Failure-Independent, FailureRelated, and Failure-Exclusionary to describe the relationships between program failures and the coverage of eachstatement within the scope of program spectra.
(2) We build a probabilistic model to derive the formal description of the characteristics of program spectra under theEASE’20, April 15–17, Trondheim, Norway
concepts of Failure-Independent, Failure-Related, and FailureExclusionary. This is our first trial to explore quantitative
conclusions beyond the basic intuitions of SBFL.
(3) We extend the probabilistic model by introducing the noise module based on the assumption of noise-style fault interference.
Then, we quantitatively analyze the spectrum movementof each type of statement and the change of Spectra Space.
This is our first trial to make a quantitative analysis for thecomplicated internal interactions in multi-fault instances.
(4) We summarize the derived CSDs using a visualization approach, which presents our analysis results in a general way.
(5) Several interesting results are found. For example, 1) different types of statements are distributed in different areasof the Spectra Space. 2) The noise will weaken the original
characteristics of each type of statements. 3) The statements
tend to move towards the diagonal lines of the Spectra Space
after suffering the noise.
(6) To demonstrate the usefulness of our analysis, we design
a statement filter to eliminate the Failure-Independent andFailure-Exclusionary statements. Our strategy is based on
visualization and utilizes both the single-fault and noiseinvolved CSDs.
In the future, we will extend our approach by establishing more
complicated probabilistic models and exploring more spectra distribution characteristics. Then we will use the derived spectra distribution rules to improve SBFL. Furthermore, the approach that
intuitively summarizes the identified CSDs will be evaluated bypractical use cases.

ACKNOWLEDGMENTS
Xiao-Yi Zhang is supported by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST. Funding
Reference number: 10.13039/501100009024 ERATO.

REFERENCES[1] Rui Abreu, Peter Zoeteweij, and Arjan JC Van Gemund. 2006. An evaluation ofsimilarity coefficients for software fault localization. In Proceedings of the 12th
Pacific Rim International Symposium on Dependable Computing (PRDC’06). IEEE,
39–46.
[2] Rui Abreu, Peter Zoeteweij, and Arjan JC Van Gemund. 2007. On the accuracy ofspectrum-based fault localization. In Testing: Academic and Industrial Conference
Practice and Research Techniques-MUTATION (TAICPART-MUTATION 2007). IEEE,
89–98.
[3] Tien-Duy B Le, David Lo, Claire Le Goues, and Lars Grunske. 2016. A learning-torank based fault localization approach using likely invariants. In Proceedings of the25th International Symposium on Software Testing and Analysis. ACM, 177–188.
[4] Benoit Baudry, Franck Fleurey, and Yves Le Traon. 2006. Improving test suites
for efficient fault localization. In Proceedings of the 28th international conference
on Software engineering. ACM, 82–91.
[5] Nicholas DiGiuseppe and James A Jones. 2015. Fault density, fault types, andspectra-based fault localization. Empirical Software Engineering 20, 4 (2015),
928–967.
[6] Hyunsook Do, Sebastian Elbaum, and Gregg Rothermel. 2005. Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact. Empirical Software Engineering 10, 4 (01 Oct 2005), 405–435.
https://doi.org/10.1007/s10664-005-3861-2[7] Bo Jiang, Ke Zhai, Wing Kwong Chan, TH Tse, and Zhenyu Zhang. 2013. On the
adoption of MC/DC and control-flow adequacy for a tight integration of program
testing and statistical fault localization. Information and Software Technology 55,
5 (2013), 897–917.
[8] James A Jones, Mary Jean Harrold, and John Stasko. 2002. Visualization of test
information to assist fault localization. In Proceedings of the 24th International
Conference on Software Engineering. ICSE 2002. IEEE, 467–477.

Xiao-Yi Zhang and Zheng Zheng[9] René Just, Darioush Jalali, and Michael D Ernst. 2014. Defects4J: A database ofexisting faults to enable controlled testing studies for Java programs. In Proceedings of the 2014 International Symposium on Software Testing and Analysis. ACM,
437–440.
[10] G Latif-Shabgahi, Julian M Bass, and Stuart Bennett. 2004. A taxonomy forsoftware voting algorithms used in safety-critical systems. IEEE Transactions on
Reliability 53, 3 (2004), 319–328.
[11] Xia Li, Wei Li, Yuqun Zhang, and Lingming Zhang. 2019. DeepFL: integrating
multiple fault diagnosis dimensions for deep fault localization. In Proceedings ofthe 28th ACM SIGSOFT International Symposium on Software Testing and Analysis.
ACM, 169–180.
[12] Lei Ma, Felix Juefei-Xu, Fuyuan Zhang, Jiyuan Sun, Minhui Xue, Bo Li, Chunyang Chen, Ting Su, Li Li, Yang Liu, et al. 2018. Deepgauge: Multi-granularity
testing criteria for deep learning systems. In Proceedings of the 33rd ACM/IEEEInternational Conference on Automated Software Engineering. ACM, 120–131.
[13] Wes Masri, Rawad Abou-Assi, Marwa El-Ghali, and Nour Al-Fatairi. 2009. An
empirical study of the factors that reduce the effectiveness of coverage-based
fault localization. In Proceedings of the 2nd International Workshop on Defects in
Large Software Systems: Held in conjunction with the ACM SIGSOFT International
Symposium on Software Testing and Analysis (ISSTA 2009). ACM, 1–5.
[14] Wes Masri and Rawad Abou Assi. 2014. Prevalence of coincidental correctness
and mitigation of its impact on fault localization. ACM transactions on software
engineering and methodology (TOSEM) 23, 1 (2014), 8.
[15] Wolfgang Mayer and Markus Stumptner. 2008. Evaluating models for modelbased debugging. In Proceedings of the 23rd IEEE/ACM International Conference
on Automated Software Engineering. IEEE Computer Society, 128–137.
[16] Lee Naish, Hua Jie Lee, and Kotagiri Ramamohanarao. 2011. A model for spectrabased software diagnosis. ACM Transactions on software engineering and methodology (TOSEM) 20, 3 (2011), 11.
[17] Chris Parnin and Alessandro Orso. 2011. Are automated debugging techniques
actually helping programmers?. In Proceedings of the 2011 international symposium
on software testing and analysis. ACM, 199–209.
[18] Spencer Pearson, José Campos, René Just, Gordon Fraser, Rui Abreu, Michael D
Ernst, Deric Pang, and Benjamin Keller. 2017. Evaluating and improving fault
localization. In Proceedings of the 39th International Conference on Software Engineering. IEEE Press, 609–620.
[19] Alexandre Perez, Rui Abreu, and Arie Van Deursen. 2019. A Theoretical andEmpirical Analysis of Program Spectra Diagnosability. IEEE Transactions on
Software Engineering (2019).
[20] Mehrdad Saadatmand, Detlef Scholle, Cheuk Wing Leung, Sebastian Ullström,
and Joanna Fredriksson Larsson. 2014. Runtime verification of state machinesand defect localization applying model-based testing. In Proceedings of the WICSA2014 Companion Volume. ACM, 6.
[21] W Eric Wong, Vidroha Debroy, Ruizhi Gao, and Yihao Li. 2013. The DStar method
for effective software fault localization. IEEE Transactions on Reliability 63, 1(2013), 290–308.
[22] W Eric Wong, Ruizhi Gao, Yihao Li, Rui Abreu, and Franz Wotawa. 2016. A
survey on software fault localization. IEEE Transactions on Software Engineering
42, 8 (2016), 707–740.
[23] Xiaoyuan Xie, Tsong Yueh Chen, Fei-Ching Kuo, and Baowen Xu. 2013. A
theoretical analysis of the risk evaluation formulas for spectrum-based fault
localization. ACM Transactions on Software Engineering and Methodology (TOSEM)
22, 4 (2013), 31.
[24] Yanhong Xu, Beibei Yin, Zheng Zheng, Xiaoyi Zhang, Chenglong Li, and Shunkun
Yang. 2019. Robustness of spectrum-based fault localisation in environments withlabelling perturbations. Journal of Systems and Software 147 (2019), 172–214.
[25] Shin Yoo, Mark Harman, and David Clark. 2013. Fault localization prioritization: Comparing information-theoretic and coverage-based approaches. ACM
Transactions on Software Engineering and Methodology (TOSEM) 22, 3 (2013), 19.
[26] Shin Yoo, Xiaoyuan Xie, Fei-Ching Kuo, Tsong Yueh Chen, and Mark Harman.
2017. Human competitiveness of genetic programming in spectrum-based fault
localisation: Theoretical and empirical analysis. ACM Transactions on Software
Engineering and Methodology (TOSEM) 26, 1 (2017), 4.
[27] Xiao-Yi Zhang and Zheng Zheng. 2019. A Visualization Analytical Framework
for Software Fault Localization Metrics. In 2019 IEEE 24th Pacific Rim International
Symposium on Dependable Computing (PRDC). IEEE, 148–14809.
[28] Xiao-Yi Zhang, Zheng Zheng, and Kai-Yuan Cai. 2018. Exploring the usefulnessof unlabelled test cases in software fault localization. Journal of Systems andSoftware 136 (2018), 278–290.
[29] Zhenyu Zhang, Wing Kwong Chan, TH Tse, Bo Jiang, and Xinming Wang. 2009.
Capturing propagation of infected program states. In Proceedings of the 7th joint
meeting of the European software engineering conference and the ACM SIGSOFT
symposium on The foundations of software engineering. ACM, 43–52.
[30] Daming Zou, Jingjing Liang, Yingfei Xiong, Michael D Ernst, and Lu Zhang. 2019.
An empirical study of fault localization families and their combinations. IEEE
Transactions on Software Engineering (2019).