# Empirical Study of the Effects of Different Similarity Measures on Test Case Prioritization

Authors: Rongcun Wang; Shujuan Jiang; Deng Chen; Yanmei Zhang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Similarity-based test case prioritization algorithms have been applied to regression testing. The common characteristic of these algorithms is to reschedule the execution order of test cases according to the distances between pair-wise test cases. The distance information can be calculated by different similarity measures. Since the topologies vary with similarity measures, the distances between pair-wise test cases calculated by different similarity measures are different. Similarity measures could significantly influence the effectiveness of test case prioritization. Therefore, we empirically evaluate the effects of six similarity measures on two similarity-based test case prioritization algorithms. The obtained results are statistically analyzed to recommend the best combination of similarity-based prioritization algorithms and similarity measures. The experimental results, confirmed by a statistical analysis, indicate that Euclidean distance is more efficient in finding defects than other similarity measures. The combination of the global similarity-based prioritization algorithm and Euclidean distance could be a better choice. It generates not only higher fault detection effectiveness but also smaller standard deviation. The goal of this study is to provide practical guides for picking the appropriate combination of similarity-based test case prioritization techniques and similarity measures.


---

## Body

## 1. Introduction

Regression testing executes an existing test suite on a changed program to assure that the changes cannot adversely impact the original components. With the continual evolution of software systems, the size of a test suite usually grows very large [1]. It may be infeasible to reexecute the whole test suite within limited time and resources. Regression testing can be time-consuming and expensive. It accounts for as much as half of the cost of software maintenance [2]. Many techniques, such as test case selection [3, 4], test case minimization [5, 6], and test case prioritization [7, 8], have been proposed to speed up regression testing. Test case selection and reduction improve the effectiveness of regression testing by executing a subset of the original test suite. Test case prioritization rearranges the execution order of test cases so that the test cases with higher priority are executed earlier. In this way bug fixing and debugging can start early so as to reduce the cost of software maintenance. Particularly, when the cost of executing the whole test suite is huge, regression testing can get significant benefits from test case prioritization [9].Actually, test case prioritization aims at finding an execution order which would detect faults fastest, that is, maximizing the rate of fault detection. The fault detection information cannot be known in advance before executing prioritized test suite. Therefore, test case prioritization techniques have to depend on surrogates, for example, code coverage information with different levels of granularity, expecting that early maximizing surrogate will result in increasing the rate of fault detection [10]. Test case prioritization can be applied to many scenarios, for example, general test case prioritization [11] and version specific prioritization [12]. General test case prioritization is not confined to the specific version of the software under test (SUT). Therefore, we only focus on general test case prioritization in regression testing.The studies on test case prioritization mainly develop along two directions: coverage-based prioritization and similarity-based prioritization. Most of coverage-based techniques resort to greedy [7, 11] or metaheuristic search algorithms [13, 14] to maximize the possible coverage. The underlying assumption of coverage-based prioritization techniques is that the execution order which achieves early more coverage is more likely to detect more faults. In general, greedy algorithms construct the optimal test case ordering according to the priority of each test case assigned by code coverage information. However, metaheuristic and evolutionary search algorithms utilize heuristics to seek solutions within the search space, that is, the set of all possible ordering of the original test suite. The original test suite often contains some test cases which are designed for exercising production features or exceptional behaviors, rather than for code coverage [15]. In this sense code coverage might be inadequate to ensure the achievement of higher rate of fault detection [16, 17].More recently, similarity-based test case prioritization techniques have been developed. As the most representative prioritization techniques, clustering-based [18–20], ART-based [21–23], and other similarity-based test case prioritization techniques [24, 25] have aroused wide interest. The underlying assumption of similarity-based prioritization techniques is that test case diversity can aid in detecting more faults. The test cases within the same cluster are similar, but not the same in terms of fault detection capability. In other words, clustering-based prioritization techniques cannot guarantee the diversity of selected test cases to the maximum extent. Furthermore, most of clustering-based approaches depend on an important parameter, that is, the number of clusters. The parameter value has a great influence on the quality of clustering. Similarly, ART-based test case prioritization cannot also guarantee the diversity of test cases to the maximum extent.Similarity measures have been widely applied to many applications, such as information retrieval and document clustering. More recently, similarity measures are also applied to software testing. Similarity-based test case prioritization techniques depend on similarity metrics. The topologies of different similarity metrics vary. The distances between pair-wise test cases may change with similarity metrics. However, previous studies on similarity-based test case prioritization techniques only use one of these similarity metrics to select or prioritize test cases. Few studies concern the effects of similarity metrics on regression test case prioritization. Moreover, the successful stories of similarity-based test case prioritization techniques inspire us to empirically evaluate more similarity measures. For this reason we take a deeper look into the effects of six similarity measures, including Jaccard Index (JI) [21], Gower-Legendre (GL), Sokal-Sneath (SS), Euclidean distance (ED) [18, 26, 27], cosine similarity (CS) [28], and proportional-binary distance metric (PD) [18, 19, 25], on similarity-based test case prioritization algorithms. Unlike clustering-based prioritization algorithms, the algorithms we investigated are nonparametric. This paper presents results from an empirical study that compares the effects of six similarity measures on two similarity-based test case prioritization algorithms applied to 8 C programs, ranging from 272 to 33545 lines of code. This study aims at providing practical guides for picking the appropriate combination of similarity-based test case prioritization algorithms and similarity measures.Over all, the contributions of this paper can be summarized as follows:(i)
This study proposes a global similarity-based test case prioritization algorithm based on the comparison of similarity measures between test cases in a given test case suite. Compared with the ART-based prioritization algorithm, the global similarity-based prioritization algorithm generates more robust and better results.
(ii)
This study empirically evaluates the effects of six similarity measures on two similarity-based test case prioritization algorithms. To the best of our knowledge, it is the first empirical study of the effects of different similarity measures on regression test case prioritization in the context of white-box testing.
(iii)
The experimental results illustrate that Euclidean distance is more efficient in finding faults than other measures. It generates not only higher fault detection capability, but also smaller standard deviation. The combination of the global similarity-based prioritization algorithm and Euclidean distance could be the best choice.The remainder of this paper is organized as follows. Section2 summarizes related work. Section 3 describes two similarity-based test case prioritization algorithms, while Section 4 introduces six similarity measures. Sections 5 and 6 present our empirical study as well as results analysis. The threat to validity is discussed in Section 7. The conclusion is drawn in Section 8, followed by our future work.


## 2. Related Work

In previous studies, researchers have proposed many test case prioritization techniques. Rothermel et al. [7] proposed several coverage-based techniques including statement coverage and branch coverage. Elbaum et al. [11] extended the techniques in [7] and presented coarse-granularity prioritization techniques, that is, function-coverage-based prioritization techniques. Most of coverage-based prioritization techniques primarily focused on two classical greedy algorithms: total greedy algorithm and additional greedy algorithm. Since the two greedy algorithms may produce suboptimal results, Li et al. [14] applied metaheuristic algorithms to code coverage-based prioritization. Their goal for test case prioritization is different from ours as we aim to increase fault detection rate, rather than code coverage. Additionally, Walcott et al. [13] proposed a time-aware prioritization technique based on a genetic algorithm to reorder test cases with given time constraints.Ledru et al. [24] used string distances for test case prioritization, incorporating Hamming, Levenshtein, Cartesian, and Manhattan distances. They empirically evaluated the effects of string edit distances on test case prioritization. All test cases were viewed as strings. Before executing test cases, test cases were ordered based on the similarity of strings. In that sense our study is very similar to their study; that is, both of them evaluated the effects of different distance measures on test case prioritization. The most distinctive difference is that their method is applied to black-box testing; that is, test case prioritization is performed before executing the test cases. On the contrary, test case prioritization in our study is performed after executing the test cases. Moreover, the distance measures we applied are different from theirs. Similarly, Hemmati et al. introduced a family of similarity-based test case selection techniques for model-based testing [29]. They also analyzed the impact of similarity functions on similarity-based test case selection [30]. In model-based testing, test cases generated from UML state machines are abstract rather than concrete. The method proposed by Hemmati et al. is applied to select a subset of the generated test suite without considering the order of selected test cases. Unlike the above two methods, our approach uses dynamic profile information generated by executing test cases to reschedule the execution order of test cases.As one of similarity-based prioritization techniques, clustering-based test case prioritization approaches have been also discussed. Yoo et al. [31] combined clustering with expert knowledge to achieve scalable prioritization. The process of prioritization depended on human efforts, which is different from our approach. Carlson et al. [20] implemented new prioritization techniques that incorporated a clustering approach and utilized three types of information, that is, code coverage, code complexity, and history data on real faults. The experimental results showed that test case prioritization that utilizes a clustering approach can improve the effectiveness of test case prioritization techniques. Dickinson et al. [18] presented distribution-based filtering and prioritizing techniques incorporating sampling methods.More recently, similarity-based algorithms have been applied to regression test case prioritization. Ramanathan et al. [32] used Levenshtein distance to similarity-based test prioritization. Jiang et al. [21] proposed a new family of coverage-based ART techniques, which were statistically superior to the RT-based techniques in detecting faults. Fang et al. [25] introduced several similarity-based test case prioritization techniques based on the edit distances of ordered sequences. The execution profiles of test cases were transformed into the ordered sequences of program entities (e.g., statement or branch). The distance of two test cases was defined as the edit distance of their ordered sequences calculated by the proportional distance. Differently from Jiang et al. [21], Fang et al. [25], and Ramanathan et al. [32], where only one similarity measure was used, we empirically evaluated six similarity measures.


## 3. Similarity-Based Test Case Prioritization

This section describes two similarity-based test case prioritization algorithms. As comparing baselines, coverage-based test case prioritization techniques are also discussed. Table1 lists test case prioritization techniques investigated in this paper.Table 1
Test case prioritization techniques investigated in this paper.
Label
Name
Description
T
1
Random
Random prioritization
T
2
Original
Original order of test cases generated
T
3
ART-bn
ART-based prioritization at branch coverage level
T
4
GSB-bn
Global similarity-based prioritization at branch coverage level
T
5
addtl-fn
Additional function coverage prioritization
T
6
addtl-st
Additional statement coverage prioritization
T
7
addtl-br
Additional branch coverage prioritization


### 3.1. Motivating Example

A simple example, based on branch coverage, is presented in Table2. Equation (1) shows the distance matrix calculated by Euclidean distance. Coverage-based test case prioritization techniques aim to achieve full branch coverage as soon as possible. The test case ordering generated by total branch coverage prioritization is S
1
:
〈
t
3
,
t
1
,
t
2
,
t
4
〉 or S
2
:
〈
t
3
,
t
1
,
t
4
,
t
2
〉. The test case ordering generated by additional branch coverage prioritization generates is S
3
:
〈
t
3
,
t
2
,
t
4
,
t
1
〉 or S
4
:
〈
t
3
,
t
4
,
t
2
,
t
1
〉. However, the optimal test case orderings for this example are S
5
:
〈
t
2
,
t
4
,
t
3
,
t
1
〉 and S
6
:
〈
t
4
,
t
2
,
t
3
,
t
1
〉. Although the above two coverage-based prioritization techniques are proposed from a coverage standpoint, they cannot cover all branches as soon as possible:(1)
t
1
t
2
t
3
t
4
t
1
t
2
t
3
t
4
0.0
2.2
1.0
1.7
0.0
2.0
2.8
0.0
2.0
0.0
.Table 2
Motivating example.
Test case
Branch
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
t
1
√
√
√
√
√
t
2
√
√
√
√
t
3
√
√
√
√
√
√
t
4
√
√
√
√


### 3.2. ART-Based Prioritization Algorithm

Adaptive Random Testing (ART) is proposed initially by Chen et al. [33] to substitute random testing for test case generation. Previous experimental studies have shown that ART can aid in further improving the fault detection effectiveness over random testing. The diversity of test cases in the input domain is the foundation of the improvement. Based on this, Jiang et al. [21] used the idea of ART to regression test case prioritization. Thus, they proposed an ART-based prioritization algorithm, which preserves the partial diversity of code coverage information. Its pseudocode is described in Algorithm 1.Algorithm 1:ART-based prioritization algorithm.
Input: A test suite T: t
1
,
t
2
,
…
,
t
n with n test cases
Output: A prioritized ordering P: 〈
p
1
,
p
2
,
…
,
p
n
〉 of test suite T
(1)
P
←
∅;
(2)randomly select one test case t from T;
(3)
P
←
〈
t
〉;
(4)
T
←
T∖t;
(5)
while  T
≠
∅  do
(6)   C
←
∅; //C represents a candidate set;
(7)   P
E
←
∅; //P
E saves the program entities covered by test cases belonging to C;
(8)   P
E
′
←
∅;
(9)   U
←
T; //U temporarily saves all test cases that are not prioritized;
(10)repeat
(11)    randomly select one testt
i from U;
(12)P
E
←
P
E
∪
P
E
′; //P
E
′ saves the program entities covered by t
i;
(13)C
←
C
∪
t
i;
(14)U
←
U∖t
i;
(15)until  (
P
E
′
∪
P
E
=
=
P
E
) or (
U
=
=
∅
);
(16)for test case c
i
∈
C  do
(17)    calculate the distance betweenc
i to P;
(18)end
(19)    select test casec
i that is the farthest away from P;
(20)p
←
〈
p
1
,
p
2
,
…
,
c
i
〉;
(21)T
←
T∖t;
(22)end
(23)return  PFirst, this algorithm randomly selects one test caset from the original test suite T as the first element of a prioritized ordering P and deletes t from T (Line (1)–Line (4)). And then, a candidate set of test cases C is constructed according to the code coverage of test cases in T. The process of constructing a candidate set (Line (10)–Line (15)) is repeated until the newly added test case does not increase program entities (e.g., function, statement, or branch) coverage. Finally, the test case in C that is the farthest away from the prioritized ordering P is preferentially selected and added to the tail of P (Line (16)–Line (20)). The prioritization process is repeated until all test cases in T have been prioritized (Line (5)–Line (22)).Determining the distance between a test caset and a set of test cases S is a key point of this algorithm. The distance is defined as follows:(2)
d
t
,
S
=
min
⁡
d
t
,
t
i
∣
t
∈
C
,
t
i
∈
S
.The distance is called the minimum set distance [34], that is, the minimum distance between pair-wise test cases. The distance can be calculated by a certain distance measure. Similarly, the average or maximum set distance can be also defined. We use the minimum set distance as previous studies have empirically verified that it shows good performance.Given a test suite withm test cases and a program with n statements, this algorithm requires times O
(
m
2
) and O
(
m
3
n
) in the best and worst cases, respectively.


### 3.3. Global Similarity-Based Prioritization Algorithm

The diversity of test cases aids in improving their fault revealing power [29, 30]. ART-based prioritization algorithm selects a test case that is the farthest from the prioritized test suite from a candidate set. Since the candidate set is a subset of not yet prioritized test cases, this algorithm does not guarantee the diversity of test cases to a maximum extent. Inspired by Hemmati et al. [29], we propose a global similarity-based test case prioritization algorithm. This algorithm selects a test case from all not yet prioritized test cases, rather than a subset of them. Consequently, it can maximize the diversity of prioritized test cases. Its pseudocode is described in Algorithm 2.Algorithm 2:Global similarity-based prioritization algorithm.
Input: A test suite T: t
0
,
t
1
,
…
,
t
n
-
1 with n test cases
Output: A prioritized sequence P: 〈
p
0
,
p
1
,
…
,
p
n
-
1
〉 of test suite T
(1)calculate the distance between pair-wise test cases in T;
(2)
P
←
∅;
(3)
d
o
u
b
l
e  d
i
s
t
_
m
i
n
[
n
];
(4)
for  i
←
0 to n
-
1  do
(5) d
i
s
t
_
m
i
n
[
i
]
=
0.0;
(6)
end
(7)select test case t
k that has the maximum average distance from T;
(8)
m
a
x
←
k;
(9)
T
←
T∖t
m
a
x;
(10)P
←
〈
t
m
a
x
〉;
(11)for  i
←
0 to n
-
1  do
(12) d
i
s
t
_
m
i
n
[
i
]
=
d
i
s
t
(
t
i
,
t
m
a
x
);
(13)end
(14)repeat
(15) m
a
x
_
d
i
s
t
=
d
i
s
t
_
m
i
n
[
0
];
(16) for  i
←
0 to n
-
1  do
(17)
if  d
i
s
t
_
m
i
n
[
i
]
>
m
a
x
_
d
i
s
t  and  t
i
∈
T  then
(18)
m
a
x
_
d
i
s
t
=
d
i
s
t
_
m
i
n
[
i
];
(19)
m
a
x
←
i;
(20)
end
(21) end
(22) add t
m
a
x to the tail of P;
(23) T
←
T∖t
m
a
x;
(24) for  i
←
0 to n
-
1  do
(25)
if  d
i
s
t
_
min
⁡
i
>
d
i
s
t
(
t
i
,
t
m
a
x
)  and  t
i
∈
T  then
(26)
d
i
s
t
_
m
i
n
[
i
]
=
d
i
s
t
(
t
i
,
t
m
a
x
);
(27)
end
(28) end
(29)until  T is empty;
(30)return  PFirst, this algorithm selects test caset
k that has the maximum average distance and deletes it from T. Test case t
k is viewed as the most different from all other test cases. Test case t
k is added to the tail of prioritized ordering P. Then the distance from each test case t in T to t
k is viewed as the minimal set distance from t to P. The process of test case prioritization mainly includes two steps. The first step is to seek a test case t
i from T that is the farthest from the last test case in P (Line (16)–Line (21)). Test case t
i is added to the tail of P and deleted from T. The second step is to update the minimal set distance from each test t in T to P by comparing the distances from t to P before and after adding t
i to P (Line (24)–Line (28)). The process of prioritization is repeated until T is empty (Line (14)–Line (29)).The most expensive operation of this algorithm is the calculation of the distances between pair-wise test cases. Note that this algorithm only compares the distances between not yet prioritized test cases and prioritized test cases, rather than recalculating their distances in the process of test case prioritization. In this sense, this algorithm reduces the cost of prioritization. Given a test suite withm test cases and a program with n branches, this algorithm requires time O
(
m
2
n
). Compared with the ART-based prioritization algorithm, this algorithm significantly decreases the time complexity. Also, this algorithm is scalable; that is, once the new test cases are generated, the distances among the original test cases are not recalculated.From the above example, the average distance from test caset
1 to other test cases is (
2.2
+
1.0
+
1.7
)
/
3. The average distances of test casees t
2, t
3, and t
4 are (
2.2
+
2.0
+
2.8
)
/
3, (
1.0
+
2.0
+
2.0
)
/
3, and (
1.7
+
2.8
+
2.0
)
/
3, respectively. Since test case t
2 has the maximum average distance, it is the first element in prioritized ordering S. The distances from test cases t
1, t
3, and t
4 to t
2 are 2.2, 2.0, and 2.8, respectively. Since test case t
4 has the maximum distance to test case t
2, test case t
4 is the second element in prioritized ordering S. The distances from test cases t
1 and t
3 to test case t
4 are 1.7 and 2.0, respectively. Since 1.7 is less than 2.2, the minimum set distance from test case t
1 to prioritized ordering S is 1.7. The minimum set distance from test case t
3 to prioritized ordering S is 2.0. Since 1.7 is less than 2.0, test case t
3 is the third element. Finally, test case t
1 is added to the tail of S. The prioritized ordering generated by the global similarity-based test case prioritization technique is S
10
:
〈
t
2
,
t
4
,
t
3
,
t
1
〉; that is, it is the optimal test case ordering. Compared with other test case prioritization techniques we studied, the global similarity-based test case prioritization technique can cover all branches more quickly.


### 3.4. Coverage-Based Prioritization Techniques

Coverage-based prioritization techniques have been widely studied. These techniques can usually be implemented at three different coverage levels: function, statement, and branch.(i) Total Coverage Maximization Prioritization. Total coverage maximization prioritization techniques schedule test cases in descending order of total coverage achieved. When more than one test case has the same total coverage, the algorithm selects one at random. The prioritization process is repeated until all test cases have been prioritized.(ii) Additional Coverage Maximization Prioritization. Additional coverage maximization prioritization techniques work as follows: A test case that yields the greatest coverage is selected at first. And then, the next test case to be selected is the one that can cover the maximum program entities not yet covered by previously selected test cases. The process is repeated until all program entities have been covered by at least one test case.Having prioritized test cases in this manner, if remaining test cases cannot add the additional coverage, we schedule them in the same way. If more than one test case yields the same additional coverage in the process of prioritization, we randomly select one. Additional coverage maximization prioritization is based on feedback. In other words, previously selected test cases are used to provide guidance to select next test case. On the contrary, total coverage maximization prioritization is no feedback. For a test suite and program withm test cases and n statements, respectively, total coverage maximization prioritization requires time O
(
m
n
), while the cost of additional coverage maximization prioritization is O
(
m
2
n
).


### 3.5. Other Prioritization Techniques

(i) Random Prioritization. We apply random prioritization, that is, randomly scheduling all test cases in the original test suite, to facilitate our empirical study.(ii) No Prioritization. As a base comparison, the initial order of test cases generated is also considered.


## 3.1. Motivating Example

A simple example, based on branch coverage, is presented in Table2. Equation (1) shows the distance matrix calculated by Euclidean distance. Coverage-based test case prioritization techniques aim to achieve full branch coverage as soon as possible. The test case ordering generated by total branch coverage prioritization is S
1
:
〈
t
3
,
t
1
,
t
2
,
t
4
〉 or S
2
:
〈
t
3
,
t
1
,
t
4
,
t
2
〉. The test case ordering generated by additional branch coverage prioritization generates is S
3
:
〈
t
3
,
t
2
,
t
4
,
t
1
〉 or S
4
:
〈
t
3
,
t
4
,
t
2
,
t
1
〉. However, the optimal test case orderings for this example are S
5
:
〈
t
2
,
t
4
,
t
3
,
t
1
〉 and S
6
:
〈
t
4
,
t
2
,
t
3
,
t
1
〉. Although the above two coverage-based prioritization techniques are proposed from a coverage standpoint, they cannot cover all branches as soon as possible:(1)
t
1
t
2
t
3
t
4
t
1
t
2
t
3
t
4
0.0
2.2
1.0
1.7
0.0
2.0
2.8
0.0
2.0
0.0
.Table 2
Motivating example.
Test case
Branch
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
t
1
√
√
√
√
√
t
2
√
√
√
√
t
3
√
√
√
√
√
√
t
4
√
√
√
√


## 3.2. ART-Based Prioritization Algorithm

Adaptive Random Testing (ART) is proposed initially by Chen et al. [33] to substitute random testing for test case generation. Previous experimental studies have shown that ART can aid in further improving the fault detection effectiveness over random testing. The diversity of test cases in the input domain is the foundation of the improvement. Based on this, Jiang et al. [21] used the idea of ART to regression test case prioritization. Thus, they proposed an ART-based prioritization algorithm, which preserves the partial diversity of code coverage information. Its pseudocode is described in Algorithm 1.Algorithm 1:ART-based prioritization algorithm.
Input: A test suite T: t
1
,
t
2
,
…
,
t
n with n test cases
Output: A prioritized ordering P: 〈
p
1
,
p
2
,
…
,
p
n
〉 of test suite T
(1)
P
←
∅;
(2)randomly select one test case t from T;
(3)
P
←
〈
t
〉;
(4)
T
←
T∖t;
(5)
while  T
≠
∅  do
(6)   C
←
∅; //C represents a candidate set;
(7)   P
E
←
∅; //P
E saves the program entities covered by test cases belonging to C;
(8)   P
E
′
←
∅;
(9)   U
←
T; //U temporarily saves all test cases that are not prioritized;
(10)repeat
(11)    randomly select one testt
i from U;
(12)P
E
←
P
E
∪
P
E
′; //P
E
′ saves the program entities covered by t
i;
(13)C
←
C
∪
t
i;
(14)U
←
U∖t
i;
(15)until  (
P
E
′
∪
P
E
=
=
P
E
) or (
U
=
=
∅
);
(16)for test case c
i
∈
C  do
(17)    calculate the distance betweenc
i to P;
(18)end
(19)    select test casec
i that is the farthest away from P;
(20)p
←
〈
p
1
,
p
2
,
…
,
c
i
〉;
(21)T
←
T∖t;
(22)end
(23)return  PFirst, this algorithm randomly selects one test caset from the original test suite T as the first element of a prioritized ordering P and deletes t from T (Line (1)–Line (4)). And then, a candidate set of test cases C is constructed according to the code coverage of test cases in T. The process of constructing a candidate set (Line (10)–Line (15)) is repeated until the newly added test case does not increase program entities (e.g., function, statement, or branch) coverage. Finally, the test case in C that is the farthest away from the prioritized ordering P is preferentially selected and added to the tail of P (Line (16)–Line (20)). The prioritization process is repeated until all test cases in T have been prioritized (Line (5)–Line (22)).Determining the distance between a test caset and a set of test cases S is a key point of this algorithm. The distance is defined as follows:(2)
d
t
,
S
=
min
⁡
d
t
,
t
i
∣
t
∈
C
,
t
i
∈
S
.The distance is called the minimum set distance [34], that is, the minimum distance between pair-wise test cases. The distance can be calculated by a certain distance measure. Similarly, the average or maximum set distance can be also defined. We use the minimum set distance as previous studies have empirically verified that it shows good performance.Given a test suite withm test cases and a program with n statements, this algorithm requires times O
(
m
2
) and O
(
m
3
n
) in the best and worst cases, respectively.


## 3.3. Global Similarity-Based Prioritization Algorithm

The diversity of test cases aids in improving their fault revealing power [29, 30]. ART-based prioritization algorithm selects a test case that is the farthest from the prioritized test suite from a candidate set. Since the candidate set is a subset of not yet prioritized test cases, this algorithm does not guarantee the diversity of test cases to a maximum extent. Inspired by Hemmati et al. [29], we propose a global similarity-based test case prioritization algorithm. This algorithm selects a test case from all not yet prioritized test cases, rather than a subset of them. Consequently, it can maximize the diversity of prioritized test cases. Its pseudocode is described in Algorithm 2.Algorithm 2:Global similarity-based prioritization algorithm.
Input: A test suite T: t
0
,
t
1
,
…
,
t
n
-
1 with n test cases
Output: A prioritized sequence P: 〈
p
0
,
p
1
,
…
,
p
n
-
1
〉 of test suite T
(1)calculate the distance between pair-wise test cases in T;
(2)
P
←
∅;
(3)
d
o
u
b
l
e  d
i
s
t
_
m
i
n
[
n
];
(4)
for  i
←
0 to n
-
1  do
(5) d
i
s
t
_
m
i
n
[
i
]
=
0.0;
(6)
end
(7)select test case t
k that has the maximum average distance from T;
(8)
m
a
x
←
k;
(9)
T
←
T∖t
m
a
x;
(10)P
←
〈
t
m
a
x
〉;
(11)for  i
←
0 to n
-
1  do
(12) d
i
s
t
_
m
i
n
[
i
]
=
d
i
s
t
(
t
i
,
t
m
a
x
);
(13)end
(14)repeat
(15) m
a
x
_
d
i
s
t
=
d
i
s
t
_
m
i
n
[
0
];
(16) for  i
←
0 to n
-
1  do
(17)
if  d
i
s
t
_
m
i
n
[
i
]
>
m
a
x
_
d
i
s
t  and  t
i
∈
T  then
(18)
m
a
x
_
d
i
s
t
=
d
i
s
t
_
m
i
n
[
i
];
(19)
m
a
x
←
i;
(20)
end
(21) end
(22) add t
m
a
x to the tail of P;
(23) T
←
T∖t
m
a
x;
(24) for  i
←
0 to n
-
1  do
(25)
if  d
i
s
t
_
min
⁡
i
>
d
i
s
t
(
t
i
,
t
m
a
x
)  and  t
i
∈
T  then
(26)
d
i
s
t
_
m
i
n
[
i
]
=
d
i
s
t
(
t
i
,
t
m
a
x
);
(27)
end
(28) end
(29)until  T is empty;
(30)return  PFirst, this algorithm selects test caset
k that has the maximum average distance and deletes it from T. Test case t
k is viewed as the most different from all other test cases. Test case t
k is added to the tail of prioritized ordering P. Then the distance from each test case t in T to t
k is viewed as the minimal set distance from t to P. The process of test case prioritization mainly includes two steps. The first step is to seek a test case t
i from T that is the farthest from the last test case in P (Line (16)–Line (21)). Test case t
i is added to the tail of P and deleted from T. The second step is to update the minimal set distance from each test t in T to P by comparing the distances from t to P before and after adding t
i to P (Line (24)–Line (28)). The process of prioritization is repeated until T is empty (Line (14)–Line (29)).The most expensive operation of this algorithm is the calculation of the distances between pair-wise test cases. Note that this algorithm only compares the distances between not yet prioritized test cases and prioritized test cases, rather than recalculating their distances in the process of test case prioritization. In this sense, this algorithm reduces the cost of prioritization. Given a test suite withm test cases and a program with n branches, this algorithm requires time O
(
m
2
n
). Compared with the ART-based prioritization algorithm, this algorithm significantly decreases the time complexity. Also, this algorithm is scalable; that is, once the new test cases are generated, the distances among the original test cases are not recalculated.From the above example, the average distance from test caset
1 to other test cases is (
2.2
+
1.0
+
1.7
)
/
3. The average distances of test casees t
2, t
3, and t
4 are (
2.2
+
2.0
+
2.8
)
/
3, (
1.0
+
2.0
+
2.0
)
/
3, and (
1.7
+
2.8
+
2.0
)
/
3, respectively. Since test case t
2 has the maximum average distance, it is the first element in prioritized ordering S. The distances from test cases t
1, t
3, and t
4 to t
2 are 2.2, 2.0, and 2.8, respectively. Since test case t
4 has the maximum distance to test case t
2, test case t
4 is the second element in prioritized ordering S. The distances from test cases t
1 and t
3 to test case t
4 are 1.7 and 2.0, respectively. Since 1.7 is less than 2.2, the minimum set distance from test case t
1 to prioritized ordering S is 1.7. The minimum set distance from test case t
3 to prioritized ordering S is 2.0. Since 1.7 is less than 2.0, test case t
3 is the third element. Finally, test case t
1 is added to the tail of S. The prioritized ordering generated by the global similarity-based test case prioritization technique is S
10
:
〈
t
2
,
t
4
,
t
3
,
t
1
〉; that is, it is the optimal test case ordering. Compared with other test case prioritization techniques we studied, the global similarity-based test case prioritization technique can cover all branches more quickly.


## 3.4. Coverage-Based Prioritization Techniques

Coverage-based prioritization techniques have been widely studied. These techniques can usually be implemented at three different coverage levels: function, statement, and branch.(i) Total Coverage Maximization Prioritization. Total coverage maximization prioritization techniques schedule test cases in descending order of total coverage achieved. When more than one test case has the same total coverage, the algorithm selects one at random. The prioritization process is repeated until all test cases have been prioritized.(ii) Additional Coverage Maximization Prioritization. Additional coverage maximization prioritization techniques work as follows: A test case that yields the greatest coverage is selected at first. And then, the next test case to be selected is the one that can cover the maximum program entities not yet covered by previously selected test cases. The process is repeated until all program entities have been covered by at least one test case.Having prioritized test cases in this manner, if remaining test cases cannot add the additional coverage, we schedule them in the same way. If more than one test case yields the same additional coverage in the process of prioritization, we randomly select one. Additional coverage maximization prioritization is based on feedback. In other words, previously selected test cases are used to provide guidance to select next test case. On the contrary, total coverage maximization prioritization is no feedback. For a test suite and program withm test cases and n statements, respectively, total coverage maximization prioritization requires time O
(
m
n
), while the cost of additional coverage maximization prioritization is O
(
m
2
n
).


## 3.5. Other Prioritization Techniques

(i) Random Prioritization. We apply random prioritization, that is, randomly scheduling all test cases in the original test suite, to facilitate our empirical study.(ii) No Prioritization. As a base comparison, the initial order of test cases generated is also considered.


## 4. Similarity Measures

In this section, we describe the similarity measures incorporating Jaccard Index, Gower-Legendre, Sokal-Sneath, Euclidean, cosine similarity, and proportional-binary distance metric. Moreover, we also give the semantic explanations for the application of these measures.


### 4.1. Profile Representation

LetE
:
e
1
;
e
2
;
…
;
e
n represent the set of all program entities in SUT, where e
i is the ith program entity. Profile information, that is, all program entities covered by a test case, can be represented as a binary coverage vector V
:
v
1
,
v
2
,
…
,
v
n. If e
i is covered, v
i is equal to 0, 1 otherwise. Similarly, the vector can also be implemented with numeric entries; that is, v
i represents the number of times that e
i is executed. Profile information of both numerical input and nonnumeric input can be represented into coverage vector. In this sense, the distance between pair-wise vectors is considered as the distance between the corresponding test cases.


### 4.2. Jaccard Index and Its Variants

Suppose that the set of program entities covered by test casest
1 and t
2 are E
t
1 and E
t
2, respectively. We define the similarity between test cases t
1 and t
2 based on Jaccard Index and its variants (i.e., Gower-Legendre and Sokal-Sneath) in the general formula as follows: (3)
s
t
1
,
t
2
=
E
t
1
∩
E
t
2
E
t
1
∩
E
t
2
+
w
E
t
1
∪
E
t
2
-
E
t
1
∩
E
t
2
,where |
E
t
1
∩
E
t
2
| is the number of matched program entities between E
t
1 and E
t
2, while the unmatched pairs between them is (|
E
t
1
∪
E
t
2
|
-
|
E
t
1
∩
E
t
2
|). Equation (3) computes the number of program entities covered by t
1 and t
2 directly, while the unmatched pairs between E
t
1 and E
t
2 are weighted based on their contribution to the similarity. When w is equal to 1, the above formula is called Jaccard Index. If w
=
2 and 1/2, this formula is called Sokal-Sneath measure and Gower-Legendre measure, respectively. For Jaccard Index and its variants, the corresponding distance is d
(
t
1
,
t
2
)
=
1
-
s
(
t
1
,
t
2
).


### 4.3. Euclidean Distance

LetV
1
:
v
11
,
v
12
,
…
,
v
1
n and V
2
:
v
21
,
v
22
,
…
,
v
2
n represent two binary coverage vectors generated by executing test cases t
1 and t
2. The Euclidean distance between test cases t
1 and t
2 can be defined as follows: (4)
d
t
1
,
t
2
=
∑
i
=
1
n
v
1
i
-
v
2
i
2
.


### 4.4. Proportional Distance

LetP
:
p
1
,
p
2
,
…
,
p
n and Q
:
q
1
,
q
2
,
…
,
q
n stand for two coverage vectors implemented with numeric entries by executing test cases t
1 and t
2. The number of times that each program entity was executed is normalized so as to eliminate the variation of absolute frequency. The proportional distance between test cases t
1 and t
2 can be defined as follows: (5)
d
t
1
,
t
2
=
∑
i
=
1
n
p
i
-
q
i
m
a
x
i
-
m
i
n
i
2
,where m
a
x
i and m
i
n
i represent the maximum and minimum numbers of times that the ith program entity is executed in all profiles, respectively. When the difference between m
a
x
i and m
i
n
i is equal to 0, that is, the ith program entity cannot be covered or the number of times that it is executed is the same, the corresponding item is also equal to 0.


### 4.5. Cosine Similarity

The binary coverage vectors covered by test casest
1 and t
2 are X
:
x
1
,
x
2
,
…
,
x
n and Y
:
y
1
,
y
2
,
…
,
y
n, respectively. The similarity between test cases t
1 and t
2 can be defined as follows: (6)
s
t
1
,
t
2
=
x
t
·
y
x
y
,where x
t is a transposition of vector x and x is the Euclidean norm of vector x. The Euclidean norm of vector x can be calculated according to x
1
2
+
x
2
2
+
⋯
+
x
n
n. Similarly, y is the Euclidean norm of vector y. In essence, s is the cosine of the angle between vectors x and y, which is a nonmetric measure [35]. For cosine similarity, the corresponding dissimilarity is defined as d
(
t
1
,
t
2
)
=
1
-
s
(
t
1
,
t
2
).


## 4.1. Profile Representation

LetE
:
e
1
;
e
2
;
…
;
e
n represent the set of all program entities in SUT, where e
i is the ith program entity. Profile information, that is, all program entities covered by a test case, can be represented as a binary coverage vector V
:
v
1
,
v
2
,
…
,
v
n. If e
i is covered, v
i is equal to 0, 1 otherwise. Similarly, the vector can also be implemented with numeric entries; that is, v
i represents the number of times that e
i is executed. Profile information of both numerical input and nonnumeric input can be represented into coverage vector. In this sense, the distance between pair-wise vectors is considered as the distance between the corresponding test cases.


## 4.2. Jaccard Index and Its Variants

Suppose that the set of program entities covered by test casest
1 and t
2 are E
t
1 and E
t
2, respectively. We define the similarity between test cases t
1 and t
2 based on Jaccard Index and its variants (i.e., Gower-Legendre and Sokal-Sneath) in the general formula as follows: (3)
s
t
1
,
t
2
=
E
t
1
∩
E
t
2
E
t
1
∩
E
t
2
+
w
E
t
1
∪
E
t
2
-
E
t
1
∩
E
t
2
,where |
E
t
1
∩
E
t
2
| is the number of matched program entities between E
t
1 and E
t
2, while the unmatched pairs between them is (|
E
t
1
∪
E
t
2
|
-
|
E
t
1
∩
E
t
2
|). Equation (3) computes the number of program entities covered by t
1 and t
2 directly, while the unmatched pairs between E
t
1 and E
t
2 are weighted based on their contribution to the similarity. When w is equal to 1, the above formula is called Jaccard Index. If w
=
2 and 1/2, this formula is called Sokal-Sneath measure and Gower-Legendre measure, respectively. For Jaccard Index and its variants, the corresponding distance is d
(
t
1
,
t
2
)
=
1
-
s
(
t
1
,
t
2
).


## 4.3. Euclidean Distance

LetV
1
:
v
11
,
v
12
,
…
,
v
1
n and V
2
:
v
21
,
v
22
,
…
,
v
2
n represent two binary coverage vectors generated by executing test cases t
1 and t
2. The Euclidean distance between test cases t
1 and t
2 can be defined as follows: (4)
d
t
1
,
t
2
=
∑
i
=
1
n
v
1
i
-
v
2
i
2
.


## 4.4. Proportional Distance

LetP
:
p
1
,
p
2
,
…
,
p
n and Q
:
q
1
,
q
2
,
…
,
q
n stand for two coverage vectors implemented with numeric entries by executing test cases t
1 and t
2. The number of times that each program entity was executed is normalized so as to eliminate the variation of absolute frequency. The proportional distance between test cases t
1 and t
2 can be defined as follows: (5)
d
t
1
,
t
2
=
∑
i
=
1
n
p
i
-
q
i
m
a
x
i
-
m
i
n
i
2
,where m
a
x
i and m
i
n
i represent the maximum and minimum numbers of times that the ith program entity is executed in all profiles, respectively. When the difference between m
a
x
i and m
i
n
i is equal to 0, that is, the ith program entity cannot be covered or the number of times that it is executed is the same, the corresponding item is also equal to 0.


## 4.5. Cosine Similarity

The binary coverage vectors covered by test casest
1 and t
2 are X
:
x
1
,
x
2
,
…
,
x
n and Y
:
y
1
,
y
2
,
…
,
y
n, respectively. The similarity between test cases t
1 and t
2 can be defined as follows: (6)
s
t
1
,
t
2
=
x
t
·
y
x
y
,where x
t is a transposition of vector x and x is the Euclidean norm of vector x. The Euclidean norm of vector x can be calculated according to x
1
2
+
x
2
2
+
⋯
+
x
n
n. Similarly, y is the Euclidean norm of vector y. In essence, s is the cosine of the angle between vectors x and y, which is a nonmetric measure [35]. For cosine similarity, the corresponding dissimilarity is defined as d
(
t
1
,
t
2
)
=
1
-
s
(
t
1
,
t
2
).


## 5. Empirical Study

Similarity-based test case prioritization techniques mainly rely on three variables: coverage criteria (e.g., function, statement, and branch), similarity functions, and prioritization algorithms. Previous studies have shown that fine-granularity coverage techniques can aid in improving rate of fault detection [6, 11]. Therefore, we only concerned similarity-based prioritization techniques at branch coverage level. We empirically investigated 12 variants (6 similarity measures × 2 prioritization algorithms) of similarity-based regression test case prioritization techniques over every subject program. Additionally, as comparison baselines, 3 variants of coverage-based prioritization techniques were also empirically studied. All algorithms are performed on a Ubuntu 11.10 system running on an Intel® Core™ i3 CPU 3.10 GHz with 4 GB main memory.


### 5.1. Overview

Figure1 summarizes the implementation process of similarity-based test case prioritization techniques, which mainly includes four steps.Figure 1
Overview of similarity-based test case prioritization.(1) Instrumentation. With the dynamic instrumentation toolgcov (https://gcc.gnu.org/), we collect execution profiles and construct branch coverage vectors. Compared to static instrumentation, dynamic instrumentation only needs to write a small amount of code, so it significantly improves the flexibility of testing. The flexibility is improved at the expense of a small increase of the time overhead.(2) Distance Calculation. The distance between pair-wise test cases is calculated by a certain distance measure.(3) Test Case Prioritization. Test cases are prioritized based on the distance between pair-wise test cases by different prioritization strategies.(4) Evaluation. The fault detection matrix is constructed based on the relation between faults and test cases for every subject program. A column and row indicate one fault and test case, respectively. If a fault can be detected by a test case, the corresponding element to the test case and fault in the matrix is equal to 1, 0 otherwise. The fault detection effectiveness of a prioritized test suite is evaluated according to its corresponding fault detection matrix.


### 5.2. Research Questions

In the empirical study, we address the following four specific research questions.RQ1. Do different similarity measures have significant effects on the ART-based test case prioritization technique? The question helps us to seek which similarity measures are the most effective in the context of the ART-based test case prioritization technique.RQ2. Do different similarity measures have significant effects on the global similarity-based test case prioritization technique? Similar toRQ1, the question helps us to identify which similarity measures are the most effective in the context of the global similarity-based test case prioritization technique.RQ3. Does the global similarity-based test case prioritization outperform the ART-based test prioritization in terms of normalized average percentage of fault detection (NAPFD)? The answer to this question helps us to make a choice of test case prioritization techniques when only a part of test suite prioritized is executed. In other words, we empirically determine which combinations are the most effective test case prioritization with reduction in terms of NAPFD.RQ4. Can the most effective similarity-based prioritization techniques be as effective as coverage-based prioritization techniques? Coverage-based test case prioritization has been empirically verified to be a promising technique. We can determine which variant of test case prioritization is more effective in terms of NAPFD.


### 5.3. Experiment Programs

Our experiments were conducted over eight subject programs from the Software Infrastructure Repository (SIR) [36]. All the eight programs are written in the C language. These programs contain 5 small-sized Siemens programs and 3 medium-sized UNIX programs with real and seeded faults. Descriptive information about the selected programs is presented in Table 3, where the lines of code are calculated by the tool “SLOCCount” (http://www.dwheeler.com/sloccount/).Table 3
Descriptive information for subject programs.
Program name
Number of version
Lines of code
Test suite size
gzip
14
3883–5096
217
make
33
12609–17153
1043
sed
18
4711–9204
370
totinfo
23
272-273
1052
schedule
8
290–294
2650
schedule2
10
261–263
2710
print_tokens
7
341–343
4130
print_tokens2
10
350–355
4115sed, gzip, andmake are all UNIX utilities (http://directory.fsf.org/wiki/GNU).sed is a stream-oriented noninteractive text editor. It consists of a base version and 5 modified versions. Only 18 faults are selected from 32 seeded faults.make is used to compile and link programs to generate executables. It consists of a base version and 4 modified versions. We select 33 faults in all.gzip is used to compress and decompress files. Some faults, such as f
1 and f
6 in version v
2, are eliminated as these faults can be detected by more than 20% of test cases. Only 14 faults are selected from 59 faults from the programgzip in total. In a word, we eliminate the fault versions whose faults cannot be detected by any test case. Likewise, if a fault can be detected by more than 20% of test cases, the fault is also excluded.The other 5 subject programs are the Siemens programs:schedule andschedule2 are priority schedulers,printtokens andprinttokens2 are lexical analyzers, andtotinfo computes statistics given input data. The number of versions, that is, the number of faults selected for every subject program, is presented in the second column of Table 3.


### 5.4. Evaluation Metrics

The average percentage of faults detected (APFD) [37] is commonly used to evaluate the effectiveness of a prioritization technique implemented on a whole test suite. Let T be a test suite containing n test cases and let F be a set of m faults exposed by T. Let T
F
i be the first test case in a prioritized test suite that detects fault i. APFD is defined as follows: (7)
A
P
F
D
=
1
-
T
F
1
+
T
F
2
+
⋯
+
T
F
m
n
m
+
1
2
n
.The value of APFD ranges from 0 to 1. The larger the value of APFD, the higher the effectiveness of prioritized technique. The application of APFD assumes that the whole test suite can be run and find all of the faults. Only a part of test suite is often executed in regression testing under limited resources [6, 38]. The reduced test suite could reduce the capability of fault detection. In this sense, APFD is unsuitable for measuring the effectiveness of a prioritization technique implemented on a part of test suite. Therefore, we use a metric, called Normalized APFD [39], which includes information on both fault finding and time of detection. Let T
F
i be the first test case in the prioritized and reduced test suite T
′ of T that detects fault i. Let n
′ be the size of T
′. Normalized APFD is defined as follows:(8)
N
A
P
F
D
=
p
-
T
F
1
+
T
F
2
+
⋯
+
T
F
m
n
′
m
+
p
2
n
′
,where p represents the quotient of the number of faults detected by the prioritized and reduced test suite divided by the number of faults detected by the whole test suite. If a fault i is never detected by T
′, T
F
i is set to 0. If n
′
=
n, that is, all test cases can be executed and S
′ can detect all faults in F, A
P
F
D and N
A
P
F
D are equivalent.We give a simple example so as to intuitively understand the difference betweenA
P
F
D and N
A
P
F
D. Table 4 shows the relation between test suite T and fault set F.Table 4
An example of the fault detection capability of test suiteT.
Test case
Fault
f
1
f
2
f
3
f
4
t
1
t
2
√
√
t
3
√
t
4
√
t
5
√
√
√There are two test case prioritization methodsM
1 and M
2, respectively. Test case orderings M
1 and M
2 generated are S
M
1
:
〈
t
3
,
t
4
,
t
1
,
t
2
,
t
5
〉 and S
M
2
:
〈
t
3
,
t
1
,
t
5
,
t
4
,
t
2
〉, respectively. The A
P
F
D values are S
M
1
(
A
P
F
D
)
=
1
-
1
+
2
+
4
+
5
/
4
×
5
+
1
/
(
2
×
5
) and S
M
2
(
A
P
F
D
)
=
1
-
(
1
+
3
+
3
+
3
)
/
(
4
×
5
)
+
1
/
(
2
×
5
), that is, 0.5 and 0.6. If only two test cases can be executed under limited resources, the N
A
P
F
D values of them are S
M
1
(
N
A
P
F
D
)
=
2
/
4
-
1
+
2
/
2
×
4
+
(
2
/
4
)
/
(
2
×
2
) and S
M
2
(
N
A
P
F
D
)
=
1
/
4
-
1
/
2
×
4
+
1
/
4
/
2
×
2, that is, 0.25 and 0.1875. If the whole test suite can be excused, M
2 is better than M
1. When only two test cases are excused, we get the opposite results. From the above example, the application of N
A
P
F
D may be more suitable for evaluating test case prioritization than that of A
P
F
D.Since all prioritization algorithms in this study have the nature of randomness, we repeated 100 times for every prioritization algorithm with different random seeds. The mean value of normalized average percentage of fault detection for every sample was calculated.


## 5.1. Overview

Figure1 summarizes the implementation process of similarity-based test case prioritization techniques, which mainly includes four steps.Figure 1
Overview of similarity-based test case prioritization.(1) Instrumentation. With the dynamic instrumentation toolgcov (https://gcc.gnu.org/), we collect execution profiles and construct branch coverage vectors. Compared to static instrumentation, dynamic instrumentation only needs to write a small amount of code, so it significantly improves the flexibility of testing. The flexibility is improved at the expense of a small increase of the time overhead.(2) Distance Calculation. The distance between pair-wise test cases is calculated by a certain distance measure.(3) Test Case Prioritization. Test cases are prioritized based on the distance between pair-wise test cases by different prioritization strategies.(4) Evaluation. The fault detection matrix is constructed based on the relation between faults and test cases for every subject program. A column and row indicate one fault and test case, respectively. If a fault can be detected by a test case, the corresponding element to the test case and fault in the matrix is equal to 1, 0 otherwise. The fault detection effectiveness of a prioritized test suite is evaluated according to its corresponding fault detection matrix.


## 5.2. Research Questions

In the empirical study, we address the following four specific research questions.RQ1. Do different similarity measures have significant effects on the ART-based test case prioritization technique? The question helps us to seek which similarity measures are the most effective in the context of the ART-based test case prioritization technique.RQ2. Do different similarity measures have significant effects on the global similarity-based test case prioritization technique? Similar toRQ1, the question helps us to identify which similarity measures are the most effective in the context of the global similarity-based test case prioritization technique.RQ3. Does the global similarity-based test case prioritization outperform the ART-based test prioritization in terms of normalized average percentage of fault detection (NAPFD)? The answer to this question helps us to make a choice of test case prioritization techniques when only a part of test suite prioritized is executed. In other words, we empirically determine which combinations are the most effective test case prioritization with reduction in terms of NAPFD.RQ4. Can the most effective similarity-based prioritization techniques be as effective as coverage-based prioritization techniques? Coverage-based test case prioritization has been empirically verified to be a promising technique. We can determine which variant of test case prioritization is more effective in terms of NAPFD.


## 5.3. Experiment Programs

Our experiments were conducted over eight subject programs from the Software Infrastructure Repository (SIR) [36]. All the eight programs are written in the C language. These programs contain 5 small-sized Siemens programs and 3 medium-sized UNIX programs with real and seeded faults. Descriptive information about the selected programs is presented in Table 3, where the lines of code are calculated by the tool “SLOCCount” (http://www.dwheeler.com/sloccount/).Table 3
Descriptive information for subject programs.
Program name
Number of version
Lines of code
Test suite size
gzip
14
3883–5096
217
make
33
12609–17153
1043
sed
18
4711–9204
370
totinfo
23
272-273
1052
schedule
8
290–294
2650
schedule2
10
261–263
2710
print_tokens
7
341–343
4130
print_tokens2
10
350–355
4115sed, gzip, andmake are all UNIX utilities (http://directory.fsf.org/wiki/GNU).sed is a stream-oriented noninteractive text editor. It consists of a base version and 5 modified versions. Only 18 faults are selected from 32 seeded faults.make is used to compile and link programs to generate executables. It consists of a base version and 4 modified versions. We select 33 faults in all.gzip is used to compress and decompress files. Some faults, such as f
1 and f
6 in version v
2, are eliminated as these faults can be detected by more than 20% of test cases. Only 14 faults are selected from 59 faults from the programgzip in total. In a word, we eliminate the fault versions whose faults cannot be detected by any test case. Likewise, if a fault can be detected by more than 20% of test cases, the fault is also excluded.The other 5 subject programs are the Siemens programs:schedule andschedule2 are priority schedulers,printtokens andprinttokens2 are lexical analyzers, andtotinfo computes statistics given input data. The number of versions, that is, the number of faults selected for every subject program, is presented in the second column of Table 3.


## 5.4. Evaluation Metrics

The average percentage of faults detected (APFD) [37] is commonly used to evaluate the effectiveness of a prioritization technique implemented on a whole test suite. Let T be a test suite containing n test cases and let F be a set of m faults exposed by T. Let T
F
i be the first test case in a prioritized test suite that detects fault i. APFD is defined as follows: (7)
A
P
F
D
=
1
-
T
F
1
+
T
F
2
+
⋯
+
T
F
m
n
m
+
1
2
n
.The value of APFD ranges from 0 to 1. The larger the value of APFD, the higher the effectiveness of prioritized technique. The application of APFD assumes that the whole test suite can be run and find all of the faults. Only a part of test suite is often executed in regression testing under limited resources [6, 38]. The reduced test suite could reduce the capability of fault detection. In this sense, APFD is unsuitable for measuring the effectiveness of a prioritization technique implemented on a part of test suite. Therefore, we use a metric, called Normalized APFD [39], which includes information on both fault finding and time of detection. Let T
F
i be the first test case in the prioritized and reduced test suite T
′ of T that detects fault i. Let n
′ be the size of T
′. Normalized APFD is defined as follows:(8)
N
A
P
F
D
=
p
-
T
F
1
+
T
F
2
+
⋯
+
T
F
m
n
′
m
+
p
2
n
′
,where p represents the quotient of the number of faults detected by the prioritized and reduced test suite divided by the number of faults detected by the whole test suite. If a fault i is never detected by T
′, T
F
i is set to 0. If n
′
=
n, that is, all test cases can be executed and S
′ can detect all faults in F, A
P
F
D and N
A
P
F
D are equivalent.We give a simple example so as to intuitively understand the difference betweenA
P
F
D and N
A
P
F
D. Table 4 shows the relation between test suite T and fault set F.Table 4
An example of the fault detection capability of test suiteT.
Test case
Fault
f
1
f
2
f
3
f
4
t
1
t
2
√
√
t
3
√
t
4
√
t
5
√
√
√There are two test case prioritization methodsM
1 and M
2, respectively. Test case orderings M
1 and M
2 generated are S
M
1
:
〈
t
3
,
t
4
,
t
1
,
t
2
,
t
5
〉 and S
M
2
:
〈
t
3
,
t
1
,
t
5
,
t
4
,
t
2
〉, respectively. The A
P
F
D values are S
M
1
(
A
P
F
D
)
=
1
-
1
+
2
+
4
+
5
/
4
×
5
+
1
/
(
2
×
5
) and S
M
2
(
A
P
F
D
)
=
1
-
(
1
+
3
+
3
+
3
)
/
(
4
×
5
)
+
1
/
(
2
×
5
), that is, 0.5 and 0.6. If only two test cases can be executed under limited resources, the N
A
P
F
D values of them are S
M
1
(
N
A
P
F
D
)
=
2
/
4
-
1
+
2
/
2
×
4
+
(
2
/
4
)
/
(
2
×
2
) and S
M
2
(
N
A
P
F
D
)
=
1
/
4
-
1
/
2
×
4
+
1
/
4
/
2
×
2, that is, 0.25 and 0.1875. If the whole test suite can be excused, M
2 is better than M
1. When only two test cases are excused, we get the opposite results. From the above example, the application of N
A
P
F
D may be more suitable for evaluating test case prioritization than that of A
P
F
D.Since all prioritization algorithms in this study have the nature of randomness, we repeated 100 times for every prioritization algorithm with different random seeds. The mean value of normalized average percentage of fault detection for every sample was calculated.


## 6. Experimental Results

We focus on test case prioritization with reduction. The main reasons include two aspects: one is that regression testing is usually executed under constrained resources; that is, only parts of test cases are executed; the other is that only evaluating the effectiveness of a whole test suite may hide important information on test case prioritization techniques. For example, the top 400 test cases generated by ART-based test case prioritization can detect all faults over the programprint_tokens. The size of the original test suite in the programprint_tokens is 4130. The number of faults seeded is only 7. When we evaluated the NAPFD of the original test suite, the NAPFD is very close to 1. Similarly, the NAPFD generated by other prioritization techniques is also close to 1. In other words, there is no statistically significant difference between different prioritization techniques. Therefore, we took 6 samples starting from 5% to 30% with the increment of 5% for every program in order to look deeper into the statistical difference between different prioritization techniques.


### 6.1. Experiment 1: Evaluating the Effects of Six Similarity Measures on the ART-Based Prioritization Algorithm

Figure2 shows our experimental results on the ART-based test case prioritization algorithm using six similarity measures. In Figure 2, each figure shows the mean values in NAPFD for six similarity measures. The x-axis of each graph indicates the number of tests selected, while the y-axis indicates the mean value in NAPFD.Figure 2
NAPFDs of the ART-based prioritization algorithm using different distance measures.
(a)
gzip
(b)
sed
(c)
make
(d)
totinfo
(e)
printtokens
(f)
printtokens2
(g)
schedule
(h)
schedule2From Figure2, we find that Euclidean distance performs better than other similarity measures in terms of the ART-based prioritization algorithm. Cosine similarity, Gower-Legendre, and Sokal-Sneath are comparable to Jaccard Index with respect to NAPFD. Compared with other similarity distances, the proportion distance produced lower NAPFDs with the same sampling proportion.Having seen Figure2, we further conducted one-way analysis of variances (ANOVAs) [40] to verify whether the mean values of NAPFD distributions for different similarity measures differ significantly. For each subject programs, a null hypothesis is defined to state that there is no statistically significant difference between different similarity measures at 5% significance level. If the p value is less than 0.05, we successfully reject the null hypothesis. In other words, there is statistically significant difference between different similarity measures. By ANOVAs, we find that the p value was less than 0.05 for every sample over every subject program; that is, different measures have significant effects on the ART-based test case prioritization algorithm.We calculated the standard deviation of every sample to observe which measures can generate more stable results. The standard deviations are shown in Table5. From Table 5, we find that Euclidean distance generated smaller standard deviation than other similarity measures with the same sampling proportion. Jaccard Index generated smaller standard deviations than its variants. Cosine similarity was better than Jaccard Index over medium-sized programs, while they are very close over small-sized programs. In general, the standard deviation decreases gradually with the increase of the sampling proportion. The possible explanation is that the higher the sampling proportion, the more the detected faults.Table 5
The standard deviations of different measures generated by the ART-based prioritization algorithm.
Program
Measure
Standard deviation
N
=
1
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
gzip
JI
0.11
0.10
0.09
0.08
0.07
0.07
CS
0.07
0.07
0.06
0.04
0.04
0.03
ED
0.06
0.06
0.04
0.05
0.04
0.03
GL
0.12
0.10
0.11
0.09
0.08
0.09
PD
0.11
0.13
0.13
0.12
0.13
0.10
SS
0.13
0.11
0.10
0.10
0.09
0.08
sed
JI
0.04
0.04
0.03
0.02
0.02
0.02
CS
0.04
0.04
0.03
0.02
0.02
0.01
ED
0.04
0.04
0.03
0.03
0.03
0.01
GL
0.05
0.04
0.03
0.03
0.03
0.02
PD
0.04
0.03
0.03
0.03
0.02
0.02
SS
0.05
0.04
0.03
0.02
0.02
0.02
make
JI
0.20
0.12
0.07
0.09
0.05
0.04
CS
0.06
0.05
0.03
0.02
0.02
0.01
ED
0.07
0.03
0.02
0.02
0.01
0.00
GL
0.29
0.16
0.05
0.05
0.06
0.04
PD
0.19
0.11
0.07
0.07
0.06
0.05
SS
0.25
0.18
0.12
0.05
0.06
0.05
totinfo
JI
0.07
0.04
0.03
0.03
0.03
0.03
CS
0.06
0.03
0.02
0.02
0.02
0.02
ED
0.07
0.06
0.05
0.05
0.04
0.03
GL
0.06
0.04
0.03
0.02
0.02
0.02
PD
0.13
0.09
0.08
0.08
0.07
0.06
SS
0.06
0.04
0.03
0.02
0.02
0.03
schedule
JI
0.11
0.09
0.10
0.10
0.08
0.09
CS
0.11
0.10
0.10
0.08
0.09
0.09
ED
0.07
0.04
0.03
0.03
0.01
0.01
GL
0.15
0.12
0.09
0.10
0.09
0.09
PD
0.11
0.15
0.15
0.14
0.13
0.11
SS
0.13
0.12
0.09
0.10
0.09
0.09
schedule2
JI
0.16
0.14
0.12
0.10
0.07
0.07
CS
0.16
0.14
0.11
0.10
0.08
0.06
ED
0.11
0.08
0.08
0.07
0.08
0.07
GL
0.15
0.14
0.12
0.09
0.08
0.08
PD
0.18
0.20
0.18
0.18
0.16
0.16
SS
0.18
0.14
0.12
0.10
0.09
0.07
print_tokens
JI
0.11
0.09
0.08
0.08
0.07
0.05
CS
0.12
0.10
0.08
0.07
0.06
0.05
ED
0.07
0.05
0.04
0.03
0.03
0.02
GL
0.13
0.10
0.08
0.07
0.07
0.05
PD
0.12
0.10
0.07
0.07
0.07
0.05
SS
0.13
0.10
0.07
0.07
0.06
0.05
print_tokens2
JI
0.05
0.04
0.03
0.02
0.02
0.01
CS
0.07
0.04
0.02
0.02
0.02
0.01
ED
0.03
0.02
0.01
0.01
0.01
0.00
GL
0.07
0.04
0.02
0.02
0.02
0.02
PD
0.06
0.04
0.04
0.03
0.02
0.01
SS
0.06
0.04
0.03
0.02
0.02
0.01In addition, we further conducted the nonparametric Mann-WhitneyU test [41, 42] to qualitatively compare the statistical differences between each pair of similarity measures at 5% significance level. For the nonparametric Mann-Whitney U test, the null hypothesis is defined to state that there is no difference between the results generated by each pair of similarity measures. When we reject the null hypothesis at a significance level α
=
0.05, we say that two similarity measures are statistically different. Table 6 summarizes the statistical significance of differences between each pair of similarity measures, where each element (m
,
n) denotes the “win/tie/loss” (win: the number of times that the mth row measure performs significantly better than nth column measure; tie: the number of times that there is no significant difference between the mth row measure and the nth column measure in terms of NAPFD; loss: the number of times that the mth row measure performs significantly worse than the nth column measure) value.Table 6
A summary of the statistical significance of differences between each pair of similarity measures over 48 different experimental settings (8 programs× 6 sampling rates based on the ART prioritization algorithm).
CS
ED
GL
JI
PD
ED
(27/13/8)
—
—
—
—
GL
(3/29/16)
(6/15/27)
—
—
—
JI
(8/12/28)
(5/14/29)
(2/38/8)
—
—
PD
(12/15/21)
(13/9/26)
(17/12/19)
(18/11/19)
—
SS
(2/33/13)
(5/10/33)
(25/20/3)
(2/39/7)
(19/11/18)From Table6, Euclidean distance performed better than other similarity measures based on the ART prioritization algorithm. For example, in the best case, Euclidean distance outperformed Sokal-Sneath on 33 settings, while Sokal-Sneath outperformed Euclidean distance only on 5 setting. In the worst case, Euclidean distance outperformed proportional distance on 26 settings, while the proportional distance outperformed Euclidean distance only on 13 settings.By the nonparametric Mann-WhitneyU test, we find that Euclidean distance performed very well over all subject programs. For the most of samples, there is statistically significant difference between Euclidean distance and other similarity measures we studied at 5% significance level. Moreover, Euclidean distance produced smaller standard deviation than other similarity measures with the same sampling proportion. This means that it can produce more stable and reliable results in practice. Using Euclidean distance reduces the risk of missing faults.Cosine similarity produced comparable results to Jaccard Index over the most of subject programs. Also, cosine similarity generated smaller standard deviations than Jaccard Index over medium-sized programs. For small-sized programs, the standard deviation of cosine similarity was roughly equal to that of Jaccard Index. The NAPFD and the standard deviation of Jaccard Index were roughly equal to those of its variants with the same sampling proportion. Furthermore, there was no statistically significant difference between Jaccard Index and its variants. The proportional distance generated smaller NAPFD than other similarity measures with the same sampling proportion except the programsed. Moreover, the difference of NAPFD between the proportional distance and other similarity measures was statistically significant at 5% significance level.


### 6.2. Experiment 2: Evaluating the Effects of Six Similarity Measures on the Global Similarity-Based Prioritization Algorithm

Similar to Experiment 1, we also took 6 samples for every subject program so as to look deeper into the effects of different similarity measures on the globe similarity-based prioritization algorithm. The experimental results are shown in Figure3, where the x-axis of each graph indicates the number of tests selected, while the y-axis shows the mean value of each similarity measure in NAPFD.Figure 3
NAPFDs of the global similarity-based prioritization algorithm using different distance measures for every subject program.
(a)
gzip
(b)
sed
(c)
make
(d)
totinfo
(e)
printtokens
(f)
printtokens2
(g)
schedule
(h)
schedule2From Figure3, cosine similarity performed better than or as good as Jaccard Index. For instance, cosine similarity improved more than 15% compared to Jaccard Index with respect to NAPFD over the program g
z
i
p. Likewise, Euclidean distance also performed consistently better than Jaccard Index for smaller samples. In most cases, the results of Jaccard Index were very close to those of its variants. The proportional distance measure showed inferior results over most of programs.We conducted ANOVAs to verify whether different similarity measures generate the significant effects on the global similarity-based prioritization algorithm at 5% significance level. Having executed ANOVAs, we find that thep value was significantly less than 0.05 for every sample across every subject program. In other words, different measures have significant effects on the global similarity-based prioritization algorithm. We calculated the standard deviation generated by the global similarity-based prioritization algorithm. The standard deviations are shown in Table 7.Table 7
The standard deviations of different measures generated by the global similarity-based prioritization algorithm.
Program
Measure
Standard deviation
N
=
1
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
gzip
JI
0.11
0.10
0.09
0.08
0.07
0.07
CS
0.04
0.02
0.02
0.01
0.01
0.01
ED
0.04
0.02
0.03
0.01
0.02
0.02
GL
0.09
0.09
0.10
0.09
0.08
0.08
PD
0.03
0.03
0.03
0.02
0.02
0.01
SS
0.12
0.10
0.10
0.09
0.09
0.07
sed
JI
0.03
0.03
0.02
0.02
0.01
0.01
CS
0.03
0.02
0.01
0.01
0.01
0.01
ED
0.03
0.02
0.01
0.01
0.01
0.01
GL
0.03
0.03
0.02
0.01
0.01
0.02
PD
0.03
0.01
0.01
0.01
0.01
0.00
SS
0.04
0.03
0.02
0.02
0.02
0.02
make
JI
0.15
0.08
0.08
0.04
0.03
0.03
CS
0.06
0.03
0.02
0.02
0.01
0.01
ED
0.03
0.02
0.01
0.00
0.00
0.00
GL
0.08
0.09
0.05
0.05
0.03
0.02
PD
0.01
0.00
0.00
0.00
0.00
0.00
SS
0.18
0.13
0.04
0.03
0.03
0.02
totinfo
JI
0.06
0.03
0.03
0.03
0.01
0.02
CS
0.06
0.03
0.02
0.02
0.02
0.02
ED
0.06
0.05
0.05
0.04
0.03
0.03
GL
0.05
0.04
0.03
0.02
0.02
0.02
PD
0.03
0.03
0.02
0.03
0.02
0.02
SS
0.05
0.03
0.03
0.02
0.03
0.02
schedule
JI
0.11
0.09
0.10
0.10
0.06
0.07
CS
0.09
0.10
0.10
0.08
0.09
0.09
ED
0.04
0.04
0.01
0.01
0.01
0.01
GL
0.10
0.11
0.09
0.09
0.09
0.09
PD
0.05
0.07
0.05
0.07
0.06
0.04
SS
0.10
0.12
0.09
0.10
0.09
0.09
schedule2
JI
0.13
0.12
0.10
0.09
0.07
0.06
CS
0.14
0.14
0.11
0.09
0.08
0.05
ED
0.04
0.04
0.07
0.03
0.05
0.04
GL
0.13
0.14
0.12
0.09
0.07
0.06
PD
0.08
0.03
0.06
0.03
0.04
0.05
SS
0.15
0.11
0.12
0.10
0.08
0.06
print_tokens
JI
0.10
0.09
0.08
0.08
0.06
0.05
CS
0.10
0.10
0.08
0.06
0.05
0.05
ED
0.02
0.02
0.01
0.00
0.00
0.00
GL
0.13
0.09
0.07
0.06
0.06
0.05
PD
0.03
0.02
0.01
0.00
0.00
0.00
SS
0.10
0.09
0.07
0.06
0.06
0.05
print_tokens2
JI
0.05
0.04
0.02
0.01
0.01
0.01
CS
0.06
0.04
0.02
0.01
0.02
0.01
ED
0.02
0.01
0.01
0.00
0.00
0.00
GL
0.06
0.04
0.02
0.02
0.02
0.01
PD
0.03
0.05
0.04
0.02
0.02
0.02
SS
0.06
0.03
0.03
0.02
0.02
0.01Like Experiment 1, we further conducted the nonparametric Mann-WhitneyU test to qualitatively compare the statistical significance of differences between each pair of similarity measures. Table 8 summarizes the statistical results. From Table 8, we can draw the same conclusion as Experiment 1, that is, Euclidean distance outperformed other similarity measures based on the global similarity prioritization algorithm. In the best case, Euclidean distance outperformed the proportional distance on 42 settings. In the worse case, Euclidean distance outperformed cosine similarity on 23 settings, while cosine similarity outperformed it only on 9 settings.Table 8
A summary of the statistical significance of differences between each pair of similarity measures over 48 different experimental settings (8 programs× 6 sampling rates based on the global similarity prioritization algorithm).
CS
ED
GL
JI
PD
ED
(23/16/9)
—
—
—
—
GL
(1/35/12)
(9/11/28)
—
—
—
JI
(2/36/10)
(8/11/29)
(3/45/0)
—
—
PD
(5/7/36)
(4/2/42)
(5/8/35)
(6/9/33)
—
SS
(2/33/13)
(6/14/28)
(4/39/5)
(3/41/4)
(32/10/6)By the nonparametric Mann-WhitneyU test, we find that cosine similarity performed very well over the medium-sized programs as it has higher NAPFD than other similarity measures. Moreover, there was statistically significant difference between cosine similarity and other similarity measures except Euclidean distance in most cases. Also, cosine similarity can generate smaller standard deviation than Jaccard Index. For small-sized programs, the means of Jaccard Index were slightly higher than those of cosine similarity. But there was no statistically significant difference between Jaccard Index and cosine similarity. In other words, cosine similarity performs well similar to Jaccard Index over small-sized programs at least.For small-sized programs, Euclidean distance performed better than Jaccard Index in terms of NAPFD. The means of Euclidean distance statistically differed from those of Jaccard Index. Moreover, Euclidean distance had smaller standard deviation than Jaccard Index. This means that Euclidean distance can generate more stable results than Jaccard Index. In a word, the application of Euclidean distance reduces the risk of missing faults in terms of the global similarity-based test case prioritization algorithm.Although Jaccard Index and its variants emphasize different aspects, there were no statistically significant differences between them. The standard deviations of Jaccard Index were slightly smaller than those of its variants, that is, Sokal-Sneath and Gower-Legendre. By the nonparametric Mann-WhitneyU test, we also find that proportion distance generated lower NAPFDs than other similarity measures over all subject programs except for the programtotinfo. The differences between the proportion distance and other similarity measures were statistically significant. Compared with other similarity measures, the proportion distance had a larger standard deviation. Although it considers more information, that is, the frequency of executed branch, than Euclidean distance, it cannot perform better.


### 6.3. ART-Based Prioritization Algorithm versus Global Similarity-Based Prioritization Algorithm

There are numerous ART-based techniques. The techniques used are both white-box-based regression test case prioritization [21] and black-box-based regression test case prioritization [22]. We conducted the empirical study in the context of white-box-based regression testing. In this sense, we only empirically compared our approach with the ART-based prioritization algorithm [21]. The ART-based prioritization algorithm is similar to the global similarity-based prioritization algorithm; that is, the next test case to be selected is the one that has the maximal distance to the prioritized test cases. However, the candidate sets of the two algorithms are different in the process of prioritization. The ART-based prioritization algorithm requires the construction of a candidate set that is used to save the test cases to be prioritized temporarily. The candidate set is a subset of all remaining test cases that are not yet prioritized. On the contrary, the global similarity-based prioritization algorithm does not require the construction of a candidate set. In this sense, the global similarity-based prioritization algorithm can assure the global diversity of prioritized test cases while the ART-based prioritization only keeps the local diversity.This experiment aids in validating whether the global diversity can detect faults earlier than the local diversity. Since Euclidean distance shows good performance under the two prioritization algorithms, we only compared the two algorithms using Euclidean distance. Like Experiments 1 and 2, we conducted the nonparametric Mann-WhitneyU test at 5% significance level to observe the statistically significant difference between the two prioritization algorithms using Euclidean distance. The goal of t-test is to determine which prioritization algorithm is more effective. The “win/tie/lose” of the global similarity-based prioritization versus the ART-based prioritization algorithm is (25/20/3). The result shows that the global similarity-based prioritization algorithm was significantly better than the ART-based prioritization algorithm. Among the 48 different experimental settings, the global similarity-based prioritization algorithm performed better than the ART-based prioritization on 25 settings. Nevertheless, the ART-based prioritization only outperformed the global similarity-based prioritization on 3 settings. The result suggests that the global diversity aids in detecting faults earlier than the local diversity. Also, the global similarity-based prioritization algorithm reduces the effect of randomness generated by the ART-based prioritization algorithm on regression test case prioritization.


### 6.4. Global Similarity-Based Prioritization and Other Comparison Baselines

The additional prioritization techniques were empirically compared with the global similarity-based prioritization algorithm using Euclidean distance, as well as random prioritization and no prioritization. We calculated the mean values of NAPFD and the standard deviations across all techniques for every subject program. Table9 presents the experimental results of different prioritization techniques, where T
8 denotes the global similarity-based prioritization algorithm using Euclidean distance.Table 9
The mean value of NAPFD and the standard deviation. Columns “NV” and “SD” show the NAPFD and the standard deviation, respectively.
Program
TCP
N
=
1
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
NV
SD
NV
SD
NV
SD
NV
SD
NV
SD
NV
SD
gzip
T
1
0.293
0.10
0.419
0.09
0.506
0.09
0.540
0.09
0.596
0.10
0.680
0.08
T
2
0.426
0.00
0.626
0.00
0.751
0.00
0.813
0.00
0.851
0.00
0.875
0.00
T
5
0.581
0.05
0.674
0.04
0.701
0.04
0.735
0.04
0.764
0.04
0.787
0.04
T
6
0.553
0.06
0.639
0.04
0.685
0.04
0.720
0.04
0.753
0.05
0.773
0.04
T
7
0.537
0.04
0.635
0.04
0.682
0.04
0.712
0.04
0.741
0.04
0.760
0.04
T
8
0.432
0.04
0.505
0.02
0.527
0.02
0.565
0.01
0.615
0.01
0.669
0.01
sed
T
1
0.607
0.07
0.686
0.06
0.720
0.06
0.806
0.03
0.824
0.03
0.860
0.03
T
2
0.423
0.00
0.631
0.00
0.707
0.00
0.761
0.00
0.798
0.00
0.823
0.00
T
5
0.646
0.05
0.697
0.04
0.755
0.04
0.803
0.04
0.846
0.03
0.859
0.04
T
6
0.641
0.06
0.702
0.02
0.781
0.02
0.833
0.02
0.877
0.02
0.883
0.03
T
7
0.655
0.01
0.718
0.02
0.794
0.02
0.856
0.02
0.881
0.02
0.904
0.02
T
8
0.647
0.03
0.721
0.02
0.780
0.01
0.829
0.01
0.869
0.01
0.888
0.01
make
T
1
0.726
0.23
0.801
0.16
0.871
0.12
0.904
0.08
0.924
0.07
0.942
0.05
T
2
0.139
0.00
0.143
0.00
0.144
0.00
0.145
0.00
0.145
0.00
0.146
0.00
T
5
0.678
0.26
0.827
0.17
0.880
0.09
0.929
0.06
0.943
0.05
0.942
0.06
T
6
0.920
0.03
0.980
0.00
0.993
0.00
0.996
0.00
0.997
0.00
0.998
0.00
T
7
0.923
0.04
0.980
0.00
0.993
0.00
0.996
0.00
0.997
0.00
0.998
0.00
T
8
0.917
0.03
0.971
0.02
0.984
0.01
0.980
0.00
0.990
0.00
0.986
0.00
totinfo
T
1
0.601
0.09
0.702
0.05
0.741
0.04
0.769
0.04
0.796
0.03
0.814
0.03
T
2
0.758
0.00
0.827
0.00
0.855
0.00
0.870
0.00
0.878
0.00
0.884
0.00
T
5
0.634
0.07
0.712
0.05
0.749
0.04
0.774
0.03
0.815
0.04
0.829
0.03
T
6
0.653
0.04
0.734
0.03
0.771
0.03
0.789
0.03
0.853
0.03
0.882
0.03
T
7
0.660
0.05
0.749
0.04
0.784
0.03
0.802
0.03
0.875
0.03
0.908
0.03
T
8
0.649
0.06
0.725
0.05
0.774
0.05
0.813
0.04
0.825
0.03
0.845
0.03
schedule
T
1
0.444
0.10
0.593
0.10
0.670
0.12
0.707
0.10
0.732
0.10
0.747
0.09
T
2
0.355
0.00
0.400
0.00
0.414
0.00
0.422
0.00
0.427
0.00
0.430
0.00
T
5
0.455
0.11
0.595
0.10
0.680
0.10
0.717
0.10
0.748
0.10
0.765
0.09
T
6
0.546
0.13
0.672
0.12
0.719
0.12
0.746
0.09
0.791
0.10
0.817
0.09
T
7
0.582
0.12
0.689
0.12
0.733
0.11
0.782
0.11
0.841
0.10
0.882
0.08
T
8
0.612
0.04
0.693
0.04
0.724
0.01
0.737
0.01
0.746
0.01
0.751
0.01
schedule2
T
1
0.417
0.18
0.615
0.13
0.695
0.13
0.752
0.11
0.780
0.08
0.810
0.06
T
2
0.186
0.00
0.193
0.00
0.195
0.00
0.197
0.00
0.197
0.00
0.198
0.00
T
5
0.429
0.17
0.587
0.15
0.721
0.12
0.776
0.09
0.797
0.09
0.822
0.07
T
6
0.515
0.15
0.698
0.12
0.758
0.10
0.807
0.09
0.813
0.05
0.848
0.06
T
7
0.506
0.15
0.675
0.13
0.767
0.12
0.818
0.09
0.830
0.07
0.876
0.06
T
8
0.576
0.04
0.699
0.04
0.749
0.07
0.789
0.03
0.807
0.05
0.827
0.04
print_tokens
T
1
0.552
0.12
0.690
0.10
0.788
0.08
0.818
0.07
0.852
0.06
0.864
0.05
T
2
0.182
0.00
0.280
0.00
0.329
0.00
0.354
0.00
0.398
0.00
0.427
0.00
T
5
0.589
0.12
0.733
0.09
0.795
0.08
0.821
0.07
0.857
0.06
0.879
0.05
T
6
0.716
0.08
0.803
0.07
0.840
0.07
0.867
0.06
0.888
0.05
0.906
0.06
T
7
0.695
0.06
0.813
0.08
0.834
0.07
0.856
0.06
0.889
0.05
0.900
0.05
T
8
0.785
0.02
0.877
0.02
0.915
0.01
0.940
0.00
0.950
0.00
0.952
0.00
print_tokens2
T
1
0.857
0.06
0.919
0.03
0.961
0.02
0.963
0.02
0.967
0.01
0.976
0.01
T
2
0.000
0.00
0.000
0.00
0.000
0.00
0.000
0.00
0.000
0.00
0.030
0.00
T
5
0.852
0.06
0.920
0.03
0.968
0.02
0.969
0.02
0.971
0.01
0.977
0.01
T
6
0.926
0.03
0.965
0.02
0.986
0.01
0.987
0.01
0.991
0.01
0.992
0.01
T
7
0.933
0.03
0.969
0.01
0.986
0.01
0.988
0.01
0.990
0.01
0.992
0.01
T
8
0.924
0.02
0.962
0.01
0.982
0.01
0.983
0.00
0.985
0.00
0.990
0.00We conducted the nonparametric Mann-WhitneyU test based on the results six prioritization techniques generated. The statistical results are shown in Table 10. From Table 10, we find that T
8 and the additional prioritization algorithms performed significantly better than random prioritization and the order of test case generated. Similarly, T
8 also performed significantly better than the additional function-coverage prioritization. In general, T
8 and the additional statement coverage prioritization were equal to each other. Likewise, T
8 was comparable to the best coverage-based prioritization algorithm, that is, the additional branch coverage prioritization.Table 10
A summary of the statistical significance of differences between each pair of test case prioritization algorithms over 48 different experimental settings (8 programs× 6 sampling rates based on 6 prioritization algorithms).
T
1
T
2
T
5
T
6
T
7
T
2
(12/1/35)
—
—
—
—
T
5
(23/24/1)
(38/0/10)
—
—
—
T
6
(48/0/0)
(37/3/8)
(40/4/4)
—
—
T
7
(48/0/0)
(37/3/8)
(41/1/6)
(17/30/1)
—
T
8
(48/0/0)
(36/3/9)
(36/6/6)
(11/27/10)
(9/21/18)In terms of the standard deviation,T
8 was superior to other prioritization techniques. This means that it can yield more reliable results. In this sense, T
8 is very promising as a candidate for regression test case prioritization techniques. With respect to the additional coverage-based prioritization techniques, we find that the best technique is the additional branch coverage prioritization, followed by the additional statement coverage prioritization and finally the additional function-coverage prioritization. The result suggests that coverage granularity has an important impact on the additional coverage prioritization techniques.


### 6.5. Discussion

The main motivation for similarity-based techniques is to provide a scalable testing approach [29]. The input of the global similarity-based prioritization algorithm is a set of branches covered which represent test cases. The more the test cases in the original test suite, the larger the scale of the inputs. The input is also related to the number of branches in software under testing. The more the number of branches, the larger the average cost of calculating the distance between pair-wise test cases. In short, the scalability of our proposed approaches increases with the size of test suite and the number of branches. Additionally, the prioritized test case ordering is relevant to the topologies of similarity measures. Jaccard Index and its variants generate the close results as the three measures have similar topologies.


## 6.1. Experiment 1: Evaluating the Effects of Six Similarity Measures on the ART-Based Prioritization Algorithm

Figure2 shows our experimental results on the ART-based test case prioritization algorithm using six similarity measures. In Figure 2, each figure shows the mean values in NAPFD for six similarity measures. The x-axis of each graph indicates the number of tests selected, while the y-axis indicates the mean value in NAPFD.Figure 2
NAPFDs of the ART-based prioritization algorithm using different distance measures.
(a)
gzip
(b)
sed
(c)
make
(d)
totinfo
(e)
printtokens
(f)
printtokens2
(g)
schedule
(h)
schedule2From Figure2, we find that Euclidean distance performs better than other similarity measures in terms of the ART-based prioritization algorithm. Cosine similarity, Gower-Legendre, and Sokal-Sneath are comparable to Jaccard Index with respect to NAPFD. Compared with other similarity distances, the proportion distance produced lower NAPFDs with the same sampling proportion.Having seen Figure2, we further conducted one-way analysis of variances (ANOVAs) [40] to verify whether the mean values of NAPFD distributions for different similarity measures differ significantly. For each subject programs, a null hypothesis is defined to state that there is no statistically significant difference between different similarity measures at 5% significance level. If the p value is less than 0.05, we successfully reject the null hypothesis. In other words, there is statistically significant difference between different similarity measures. By ANOVAs, we find that the p value was less than 0.05 for every sample over every subject program; that is, different measures have significant effects on the ART-based test case prioritization algorithm.We calculated the standard deviation of every sample to observe which measures can generate more stable results. The standard deviations are shown in Table5. From Table 5, we find that Euclidean distance generated smaller standard deviation than other similarity measures with the same sampling proportion. Jaccard Index generated smaller standard deviations than its variants. Cosine similarity was better than Jaccard Index over medium-sized programs, while they are very close over small-sized programs. In general, the standard deviation decreases gradually with the increase of the sampling proportion. The possible explanation is that the higher the sampling proportion, the more the detected faults.Table 5
The standard deviations of different measures generated by the ART-based prioritization algorithm.
Program
Measure
Standard deviation
N
=
1
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
gzip
JI
0.11
0.10
0.09
0.08
0.07
0.07
CS
0.07
0.07
0.06
0.04
0.04
0.03
ED
0.06
0.06
0.04
0.05
0.04
0.03
GL
0.12
0.10
0.11
0.09
0.08
0.09
PD
0.11
0.13
0.13
0.12
0.13
0.10
SS
0.13
0.11
0.10
0.10
0.09
0.08
sed
JI
0.04
0.04
0.03
0.02
0.02
0.02
CS
0.04
0.04
0.03
0.02
0.02
0.01
ED
0.04
0.04
0.03
0.03
0.03
0.01
GL
0.05
0.04
0.03
0.03
0.03
0.02
PD
0.04
0.03
0.03
0.03
0.02
0.02
SS
0.05
0.04
0.03
0.02
0.02
0.02
make
JI
0.20
0.12
0.07
0.09
0.05
0.04
CS
0.06
0.05
0.03
0.02
0.02
0.01
ED
0.07
0.03
0.02
0.02
0.01
0.00
GL
0.29
0.16
0.05
0.05
0.06
0.04
PD
0.19
0.11
0.07
0.07
0.06
0.05
SS
0.25
0.18
0.12
0.05
0.06
0.05
totinfo
JI
0.07
0.04
0.03
0.03
0.03
0.03
CS
0.06
0.03
0.02
0.02
0.02
0.02
ED
0.07
0.06
0.05
0.05
0.04
0.03
GL
0.06
0.04
0.03
0.02
0.02
0.02
PD
0.13
0.09
0.08
0.08
0.07
0.06
SS
0.06
0.04
0.03
0.02
0.02
0.03
schedule
JI
0.11
0.09
0.10
0.10
0.08
0.09
CS
0.11
0.10
0.10
0.08
0.09
0.09
ED
0.07
0.04
0.03
0.03
0.01
0.01
GL
0.15
0.12
0.09
0.10
0.09
0.09
PD
0.11
0.15
0.15
0.14
0.13
0.11
SS
0.13
0.12
0.09
0.10
0.09
0.09
schedule2
JI
0.16
0.14
0.12
0.10
0.07
0.07
CS
0.16
0.14
0.11
0.10
0.08
0.06
ED
0.11
0.08
0.08
0.07
0.08
0.07
GL
0.15
0.14
0.12
0.09
0.08
0.08
PD
0.18
0.20
0.18
0.18
0.16
0.16
SS
0.18
0.14
0.12
0.10
0.09
0.07
print_tokens
JI
0.11
0.09
0.08
0.08
0.07
0.05
CS
0.12
0.10
0.08
0.07
0.06
0.05
ED
0.07
0.05
0.04
0.03
0.03
0.02
GL
0.13
0.10
0.08
0.07
0.07
0.05
PD
0.12
0.10
0.07
0.07
0.07
0.05
SS
0.13
0.10
0.07
0.07
0.06
0.05
print_tokens2
JI
0.05
0.04
0.03
0.02
0.02
0.01
CS
0.07
0.04
0.02
0.02
0.02
0.01
ED
0.03
0.02
0.01
0.01
0.01
0.00
GL
0.07
0.04
0.02
0.02
0.02
0.02
PD
0.06
0.04
0.04
0.03
0.02
0.01
SS
0.06
0.04
0.03
0.02
0.02
0.01In addition, we further conducted the nonparametric Mann-WhitneyU test [41, 42] to qualitatively compare the statistical differences between each pair of similarity measures at 5% significance level. For the nonparametric Mann-Whitney U test, the null hypothesis is defined to state that there is no difference between the results generated by each pair of similarity measures. When we reject the null hypothesis at a significance level α
=
0.05, we say that two similarity measures are statistically different. Table 6 summarizes the statistical significance of differences between each pair of similarity measures, where each element (m
,
n) denotes the “win/tie/loss” (win: the number of times that the mth row measure performs significantly better than nth column measure; tie: the number of times that there is no significant difference between the mth row measure and the nth column measure in terms of NAPFD; loss: the number of times that the mth row measure performs significantly worse than the nth column measure) value.Table 6
A summary of the statistical significance of differences between each pair of similarity measures over 48 different experimental settings (8 programs× 6 sampling rates based on the ART prioritization algorithm).
CS
ED
GL
JI
PD
ED
(27/13/8)
—
—
—
—
GL
(3/29/16)
(6/15/27)
—
—
—
JI
(8/12/28)
(5/14/29)
(2/38/8)
—
—
PD
(12/15/21)
(13/9/26)
(17/12/19)
(18/11/19)
—
SS
(2/33/13)
(5/10/33)
(25/20/3)
(2/39/7)
(19/11/18)From Table6, Euclidean distance performed better than other similarity measures based on the ART prioritization algorithm. For example, in the best case, Euclidean distance outperformed Sokal-Sneath on 33 settings, while Sokal-Sneath outperformed Euclidean distance only on 5 setting. In the worst case, Euclidean distance outperformed proportional distance on 26 settings, while the proportional distance outperformed Euclidean distance only on 13 settings.By the nonparametric Mann-WhitneyU test, we find that Euclidean distance performed very well over all subject programs. For the most of samples, there is statistically significant difference between Euclidean distance and other similarity measures we studied at 5% significance level. Moreover, Euclidean distance produced smaller standard deviation than other similarity measures with the same sampling proportion. This means that it can produce more stable and reliable results in practice. Using Euclidean distance reduces the risk of missing faults.Cosine similarity produced comparable results to Jaccard Index over the most of subject programs. Also, cosine similarity generated smaller standard deviations than Jaccard Index over medium-sized programs. For small-sized programs, the standard deviation of cosine similarity was roughly equal to that of Jaccard Index. The NAPFD and the standard deviation of Jaccard Index were roughly equal to those of its variants with the same sampling proportion. Furthermore, there was no statistically significant difference between Jaccard Index and its variants. The proportional distance generated smaller NAPFD than other similarity measures with the same sampling proportion except the programsed. Moreover, the difference of NAPFD between the proportional distance and other similarity measures was statistically significant at 5% significance level.


## 6.2. Experiment 2: Evaluating the Effects of Six Similarity Measures on the Global Similarity-Based Prioritization Algorithm

Similar to Experiment 1, we also took 6 samples for every subject program so as to look deeper into the effects of different similarity measures on the globe similarity-based prioritization algorithm. The experimental results are shown in Figure3, where the x-axis of each graph indicates the number of tests selected, while the y-axis shows the mean value of each similarity measure in NAPFD.Figure 3
NAPFDs of the global similarity-based prioritization algorithm using different distance measures for every subject program.
(a)
gzip
(b)
sed
(c)
make
(d)
totinfo
(e)
printtokens
(f)
printtokens2
(g)
schedule
(h)
schedule2From Figure3, cosine similarity performed better than or as good as Jaccard Index. For instance, cosine similarity improved more than 15% compared to Jaccard Index with respect to NAPFD over the program g
z
i
p. Likewise, Euclidean distance also performed consistently better than Jaccard Index for smaller samples. In most cases, the results of Jaccard Index were very close to those of its variants. The proportional distance measure showed inferior results over most of programs.We conducted ANOVAs to verify whether different similarity measures generate the significant effects on the global similarity-based prioritization algorithm at 5% significance level. Having executed ANOVAs, we find that thep value was significantly less than 0.05 for every sample across every subject program. In other words, different measures have significant effects on the global similarity-based prioritization algorithm. We calculated the standard deviation generated by the global similarity-based prioritization algorithm. The standard deviations are shown in Table 7.Table 7
The standard deviations of different measures generated by the global similarity-based prioritization algorithm.
Program
Measure
Standard deviation
N
=
1
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
gzip
JI
0.11
0.10
0.09
0.08
0.07
0.07
CS
0.04
0.02
0.02
0.01
0.01
0.01
ED
0.04
0.02
0.03
0.01
0.02
0.02
GL
0.09
0.09
0.10
0.09
0.08
0.08
PD
0.03
0.03
0.03
0.02
0.02
0.01
SS
0.12
0.10
0.10
0.09
0.09
0.07
sed
JI
0.03
0.03
0.02
0.02
0.01
0.01
CS
0.03
0.02
0.01
0.01
0.01
0.01
ED
0.03
0.02
0.01
0.01
0.01
0.01
GL
0.03
0.03
0.02
0.01
0.01
0.02
PD
0.03
0.01
0.01
0.01
0.01
0.00
SS
0.04
0.03
0.02
0.02
0.02
0.02
make
JI
0.15
0.08
0.08
0.04
0.03
0.03
CS
0.06
0.03
0.02
0.02
0.01
0.01
ED
0.03
0.02
0.01
0.00
0.00
0.00
GL
0.08
0.09
0.05
0.05
0.03
0.02
PD
0.01
0.00
0.00
0.00
0.00
0.00
SS
0.18
0.13
0.04
0.03
0.03
0.02
totinfo
JI
0.06
0.03
0.03
0.03
0.01
0.02
CS
0.06
0.03
0.02
0.02
0.02
0.02
ED
0.06
0.05
0.05
0.04
0.03
0.03
GL
0.05
0.04
0.03
0.02
0.02
0.02
PD
0.03
0.03
0.02
0.03
0.02
0.02
SS
0.05
0.03
0.03
0.02
0.03
0.02
schedule
JI
0.11
0.09
0.10
0.10
0.06
0.07
CS
0.09
0.10
0.10
0.08
0.09
0.09
ED
0.04
0.04
0.01
0.01
0.01
0.01
GL
0.10
0.11
0.09
0.09
0.09
0.09
PD
0.05
0.07
0.05
0.07
0.06
0.04
SS
0.10
0.12
0.09
0.10
0.09
0.09
schedule2
JI
0.13
0.12
0.10
0.09
0.07
0.06
CS
0.14
0.14
0.11
0.09
0.08
0.05
ED
0.04
0.04
0.07
0.03
0.05
0.04
GL
0.13
0.14
0.12
0.09
0.07
0.06
PD
0.08
0.03
0.06
0.03
0.04
0.05
SS
0.15
0.11
0.12
0.10
0.08
0.06
print_tokens
JI
0.10
0.09
0.08
0.08
0.06
0.05
CS
0.10
0.10
0.08
0.06
0.05
0.05
ED
0.02
0.02
0.01
0.00
0.00
0.00
GL
0.13
0.09
0.07
0.06
0.06
0.05
PD
0.03
0.02
0.01
0.00
0.00
0.00
SS
0.10
0.09
0.07
0.06
0.06
0.05
print_tokens2
JI
0.05
0.04
0.02
0.01
0.01
0.01
CS
0.06
0.04
0.02
0.01
0.02
0.01
ED
0.02
0.01
0.01
0.00
0.00
0.00
GL
0.06
0.04
0.02
0.02
0.02
0.01
PD
0.03
0.05
0.04
0.02
0.02
0.02
SS
0.06
0.03
0.03
0.02
0.02
0.01Like Experiment 1, we further conducted the nonparametric Mann-WhitneyU test to qualitatively compare the statistical significance of differences between each pair of similarity measures. Table 8 summarizes the statistical results. From Table 8, we can draw the same conclusion as Experiment 1, that is, Euclidean distance outperformed other similarity measures based on the global similarity prioritization algorithm. In the best case, Euclidean distance outperformed the proportional distance on 42 settings. In the worse case, Euclidean distance outperformed cosine similarity on 23 settings, while cosine similarity outperformed it only on 9 settings.Table 8
A summary of the statistical significance of differences between each pair of similarity measures over 48 different experimental settings (8 programs× 6 sampling rates based on the global similarity prioritization algorithm).
CS
ED
GL
JI
PD
ED
(23/16/9)
—
—
—
—
GL
(1/35/12)
(9/11/28)
—
—
—
JI
(2/36/10)
(8/11/29)
(3/45/0)
—
—
PD
(5/7/36)
(4/2/42)
(5/8/35)
(6/9/33)
—
SS
(2/33/13)
(6/14/28)
(4/39/5)
(3/41/4)
(32/10/6)By the nonparametric Mann-WhitneyU test, we find that cosine similarity performed very well over the medium-sized programs as it has higher NAPFD than other similarity measures. Moreover, there was statistically significant difference between cosine similarity and other similarity measures except Euclidean distance in most cases. Also, cosine similarity can generate smaller standard deviation than Jaccard Index. For small-sized programs, the means of Jaccard Index were slightly higher than those of cosine similarity. But there was no statistically significant difference between Jaccard Index and cosine similarity. In other words, cosine similarity performs well similar to Jaccard Index over small-sized programs at least.For small-sized programs, Euclidean distance performed better than Jaccard Index in terms of NAPFD. The means of Euclidean distance statistically differed from those of Jaccard Index. Moreover, Euclidean distance had smaller standard deviation than Jaccard Index. This means that Euclidean distance can generate more stable results than Jaccard Index. In a word, the application of Euclidean distance reduces the risk of missing faults in terms of the global similarity-based test case prioritization algorithm.Although Jaccard Index and its variants emphasize different aspects, there were no statistically significant differences between them. The standard deviations of Jaccard Index were slightly smaller than those of its variants, that is, Sokal-Sneath and Gower-Legendre. By the nonparametric Mann-WhitneyU test, we also find that proportion distance generated lower NAPFDs than other similarity measures over all subject programs except for the programtotinfo. The differences between the proportion distance and other similarity measures were statistically significant. Compared with other similarity measures, the proportion distance had a larger standard deviation. Although it considers more information, that is, the frequency of executed branch, than Euclidean distance, it cannot perform better.


## 6.3. ART-Based Prioritization Algorithm versus Global Similarity-Based Prioritization Algorithm

There are numerous ART-based techniques. The techniques used are both white-box-based regression test case prioritization [21] and black-box-based regression test case prioritization [22]. We conducted the empirical study in the context of white-box-based regression testing. In this sense, we only empirically compared our approach with the ART-based prioritization algorithm [21]. The ART-based prioritization algorithm is similar to the global similarity-based prioritization algorithm; that is, the next test case to be selected is the one that has the maximal distance to the prioritized test cases. However, the candidate sets of the two algorithms are different in the process of prioritization. The ART-based prioritization algorithm requires the construction of a candidate set that is used to save the test cases to be prioritized temporarily. The candidate set is a subset of all remaining test cases that are not yet prioritized. On the contrary, the global similarity-based prioritization algorithm does not require the construction of a candidate set. In this sense, the global similarity-based prioritization algorithm can assure the global diversity of prioritized test cases while the ART-based prioritization only keeps the local diversity.This experiment aids in validating whether the global diversity can detect faults earlier than the local diversity. Since Euclidean distance shows good performance under the two prioritization algorithms, we only compared the two algorithms using Euclidean distance. Like Experiments 1 and 2, we conducted the nonparametric Mann-WhitneyU test at 5% significance level to observe the statistically significant difference between the two prioritization algorithms using Euclidean distance. The goal of t-test is to determine which prioritization algorithm is more effective. The “win/tie/lose” of the global similarity-based prioritization versus the ART-based prioritization algorithm is (25/20/3). The result shows that the global similarity-based prioritization algorithm was significantly better than the ART-based prioritization algorithm. Among the 48 different experimental settings, the global similarity-based prioritization algorithm performed better than the ART-based prioritization on 25 settings. Nevertheless, the ART-based prioritization only outperformed the global similarity-based prioritization on 3 settings. The result suggests that the global diversity aids in detecting faults earlier than the local diversity. Also, the global similarity-based prioritization algorithm reduces the effect of randomness generated by the ART-based prioritization algorithm on regression test case prioritization.


## 6.4. Global Similarity-Based Prioritization and Other Comparison Baselines

The additional prioritization techniques were empirically compared with the global similarity-based prioritization algorithm using Euclidean distance, as well as random prioritization and no prioritization. We calculated the mean values of NAPFD and the standard deviations across all techniques for every subject program. Table9 presents the experimental results of different prioritization techniques, where T
8 denotes the global similarity-based prioritization algorithm using Euclidean distance.Table 9
The mean value of NAPFD and the standard deviation. Columns “NV” and “SD” show the NAPFD and the standard deviation, respectively.
Program
TCP
N
=
1
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
NV
SD
NV
SD
NV
SD
NV
SD
NV
SD
NV
SD
gzip
T
1
0.293
0.10
0.419
0.09
0.506
0.09
0.540
0.09
0.596
0.10
0.680
0.08
T
2
0.426
0.00
0.626
0.00
0.751
0.00
0.813
0.00
0.851
0.00
0.875
0.00
T
5
0.581
0.05
0.674
0.04
0.701
0.04
0.735
0.04
0.764
0.04
0.787
0.04
T
6
0.553
0.06
0.639
0.04
0.685
0.04
0.720
0.04
0.753
0.05
0.773
0.04
T
7
0.537
0.04
0.635
0.04
0.682
0.04
0.712
0.04
0.741
0.04
0.760
0.04
T
8
0.432
0.04
0.505
0.02
0.527
0.02
0.565
0.01
0.615
0.01
0.669
0.01
sed
T
1
0.607
0.07
0.686
0.06
0.720
0.06
0.806
0.03
0.824
0.03
0.860
0.03
T
2
0.423
0.00
0.631
0.00
0.707
0.00
0.761
0.00
0.798
0.00
0.823
0.00
T
5
0.646
0.05
0.697
0.04
0.755
0.04
0.803
0.04
0.846
0.03
0.859
0.04
T
6
0.641
0.06
0.702
0.02
0.781
0.02
0.833
0.02
0.877
0.02
0.883
0.03
T
7
0.655
0.01
0.718
0.02
0.794
0.02
0.856
0.02
0.881
0.02
0.904
0.02
T
8
0.647
0.03
0.721
0.02
0.780
0.01
0.829
0.01
0.869
0.01
0.888
0.01
make
T
1
0.726
0.23
0.801
0.16
0.871
0.12
0.904
0.08
0.924
0.07
0.942
0.05
T
2
0.139
0.00
0.143
0.00
0.144
0.00
0.145
0.00
0.145
0.00
0.146
0.00
T
5
0.678
0.26
0.827
0.17
0.880
0.09
0.929
0.06
0.943
0.05
0.942
0.06
T
6
0.920
0.03
0.980
0.00
0.993
0.00
0.996
0.00
0.997
0.00
0.998
0.00
T
7
0.923
0.04
0.980
0.00
0.993
0.00
0.996
0.00
0.997
0.00
0.998
0.00
T
8
0.917
0.03
0.971
0.02
0.984
0.01
0.980
0.00
0.990
0.00
0.986
0.00
totinfo
T
1
0.601
0.09
0.702
0.05
0.741
0.04
0.769
0.04
0.796
0.03
0.814
0.03
T
2
0.758
0.00
0.827
0.00
0.855
0.00
0.870
0.00
0.878
0.00
0.884
0.00
T
5
0.634
0.07
0.712
0.05
0.749
0.04
0.774
0.03
0.815
0.04
0.829
0.03
T
6
0.653
0.04
0.734
0.03
0.771
0.03
0.789
0.03
0.853
0.03
0.882
0.03
T
7
0.660
0.05
0.749
0.04
0.784
0.03
0.802
0.03
0.875
0.03
0.908
0.03
T
8
0.649
0.06
0.725
0.05
0.774
0.05
0.813
0.04
0.825
0.03
0.845
0.03
schedule
T
1
0.444
0.10
0.593
0.10
0.670
0.12
0.707
0.10
0.732
0.10
0.747
0.09
T
2
0.355
0.00
0.400
0.00
0.414
0.00
0.422
0.00
0.427
0.00
0.430
0.00
T
5
0.455
0.11
0.595
0.10
0.680
0.10
0.717
0.10
0.748
0.10
0.765
0.09
T
6
0.546
0.13
0.672
0.12
0.719
0.12
0.746
0.09
0.791
0.10
0.817
0.09
T
7
0.582
0.12
0.689
0.12
0.733
0.11
0.782
0.11
0.841
0.10
0.882
0.08
T
8
0.612
0.04
0.693
0.04
0.724
0.01
0.737
0.01
0.746
0.01
0.751
0.01
schedule2
T
1
0.417
0.18
0.615
0.13
0.695
0.13
0.752
0.11
0.780
0.08
0.810
0.06
T
2
0.186
0.00
0.193
0.00
0.195
0.00
0.197
0.00
0.197
0.00
0.198
0.00
T
5
0.429
0.17
0.587
0.15
0.721
0.12
0.776
0.09
0.797
0.09
0.822
0.07
T
6
0.515
0.15
0.698
0.12
0.758
0.10
0.807
0.09
0.813
0.05
0.848
0.06
T
7
0.506
0.15
0.675
0.13
0.767
0.12
0.818
0.09
0.830
0.07
0.876
0.06
T
8
0.576
0.04
0.699
0.04
0.749
0.07
0.789
0.03
0.807
0.05
0.827
0.04
print_tokens
T
1
0.552
0.12
0.690
0.10
0.788
0.08
0.818
0.07
0.852
0.06
0.864
0.05
T
2
0.182
0.00
0.280
0.00
0.329
0.00
0.354
0.00
0.398
0.00
0.427
0.00
T
5
0.589
0.12
0.733
0.09
0.795
0.08
0.821
0.07
0.857
0.06
0.879
0.05
T
6
0.716
0.08
0.803
0.07
0.840
0.07
0.867
0.06
0.888
0.05
0.906
0.06
T
7
0.695
0.06
0.813
0.08
0.834
0.07
0.856
0.06
0.889
0.05
0.900
0.05
T
8
0.785
0.02
0.877
0.02
0.915
0.01
0.940
0.00
0.950
0.00
0.952
0.00
print_tokens2
T
1
0.857
0.06
0.919
0.03
0.961
0.02
0.963
0.02
0.967
0.01
0.976
0.01
T
2
0.000
0.00
0.000
0.00
0.000
0.00
0.000
0.00
0.000
0.00
0.030
0.00
T
5
0.852
0.06
0.920
0.03
0.968
0.02
0.969
0.02
0.971
0.01
0.977
0.01
T
6
0.926
0.03
0.965
0.02
0.986
0.01
0.987
0.01
0.991
0.01
0.992
0.01
T
7
0.933
0.03
0.969
0.01
0.986
0.01
0.988
0.01
0.990
0.01
0.992
0.01
T
8
0.924
0.02
0.962
0.01
0.982
0.01
0.983
0.00
0.985
0.00
0.990
0.00We conducted the nonparametric Mann-WhitneyU test based on the results six prioritization techniques generated. The statistical results are shown in Table 10. From Table 10, we find that T
8 and the additional prioritization algorithms performed significantly better than random prioritization and the order of test case generated. Similarly, T
8 also performed significantly better than the additional function-coverage prioritization. In general, T
8 and the additional statement coverage prioritization were equal to each other. Likewise, T
8 was comparable to the best coverage-based prioritization algorithm, that is, the additional branch coverage prioritization.Table 10
A summary of the statistical significance of differences between each pair of test case prioritization algorithms over 48 different experimental settings (8 programs× 6 sampling rates based on 6 prioritization algorithms).
T
1
T
2
T
5
T
6
T
7
T
2
(12/1/35)
—
—
—
—
T
5
(23/24/1)
(38/0/10)
—
—
—
T
6
(48/0/0)
(37/3/8)
(40/4/4)
—
—
T
7
(48/0/0)
(37/3/8)
(41/1/6)
(17/30/1)
—
T
8
(48/0/0)
(36/3/9)
(36/6/6)
(11/27/10)
(9/21/18)In terms of the standard deviation,T
8 was superior to other prioritization techniques. This means that it can yield more reliable results. In this sense, T
8 is very promising as a candidate for regression test case prioritization techniques. With respect to the additional coverage-based prioritization techniques, we find that the best technique is the additional branch coverage prioritization, followed by the additional statement coverage prioritization and finally the additional function-coverage prioritization. The result suggests that coverage granularity has an important impact on the additional coverage prioritization techniques.


## 6.5. Discussion

The main motivation for similarity-based techniques is to provide a scalable testing approach [29]. The input of the global similarity-based prioritization algorithm is a set of branches covered which represent test cases. The more the test cases in the original test suite, the larger the scale of the inputs. The input is also related to the number of branches in software under testing. The more the number of branches, the larger the average cost of calculating the distance between pair-wise test cases. In short, the scalability of our proposed approaches increases with the size of test suite and the number of branches. Additionally, the prioritized test case ordering is relevant to the topologies of similarity measures. Jaccard Index and its variants generate the close results as the three measures have similar topologies.


## 7. Threats to Validity

Although the experiments were carefully designed and implemented, this study is not free from threats to its validity. These potential threats are summarized as follows.(i) Internal Validity. We empirically compared the effects of six similarity measures on two prioritization algorithms by sampling different rates of test cases. The conclusion of this study could be affected by the sampling rates. Therefore, we took 6 samples for every subject program and reported the mean value and the standard deviation of every sample. Another potential threat to internal validity lies on potential instrumentation inaccuracy. To mitigate this threat, widely used and tested open source toolgcov has been adopted. If there is a fault in the original programs, the validity of the collected profiles may be threatened by the fault. To avoid any bias, the subject programs were chosen from a well-managed software repository [36].(ii) External Validity. Our results only rely on eight subject programs written in the C language including three medium-sized programs and five small-sized programs. Threats to external validity are revolved around the representativeness of the subject programs. To alleviate, we conducted experiments on the eight programs which are from different domains with different characteristics, for example, different number of faults, different line of code, and different sizes of test suites. Further empirical studies will be conducted on larger scale and more representative industrial programs in future work.(iii) Construct Validity. As previous studies, the measure (i.e., normalized average percentage of fault detection) is adopted to evaluate the effectiveness of different prioritization techniques. This may be insufficient for evaluating the effectiveness of different combinations as different combinations have different execution costs. There may be other metrics which are more relevant to this study. Also, as previous studies, we did not distinguish the severities of different faults. The severities of faults might influence the effectiveness of different combinations.


## 8. Conclusion and Future Work

Regression testing is usually executed under constrained resources and time. Test case prioritization has been proposed to improve the effectiveness of regression testing. It aims to reschedule an execution order of test cases so that the faults can be detected as early as possible. Previous studies have verified that ART-based test case prioritization algorithm is very promising. However, the algorithm significantly depends on similarity measures. Moreover, the algorithm cannot assure the global diversity of test cases.In this context, we proposed a global similarity-based test case prioritization algorithm based on the comparison of similarity measures between test cases in a given suite. We empirically evaluated the effects of different similarity measures on the effectiveness of test cases prioritization over 8 programs written in the C language. By ANOVAs, we find that different measures have significant effects on the two test case prioritization algorithms. Particularly, Euclidean distance performs better than other five similarity measures in terms of NAPFD and standard deviation. Therefore, we recommend Euclidean distance. On the contrary, the proportional distance performs worse than other similarity measures we studied. In other words, we do not recommend the proportional distance. The experimental results also show that there is no statistically significant difference between Jaccard Index and its variants.The ART-based prioritization algorithm was empirically compared with the global similarity-based prioritization algorithm. By conducting pair-wiset-test, we find that the global similarity-based prioritization algorithm outperforms the ART-based prioritization algorithm when both of them use Euclidean distance for the calculation of the distance between pair-wise test cases. The result suggests that test case diversity can aid in detecting faults as early as possible. This study is aimed at providing practical guides for picking the approximate combination of test case prioritization algorithms and similarity measures.For future work, our study will be extended to large scale industrial projects to validate the effectiveness of our approach. Furthermore, much more similarity measures will be empirically evaluated. Last but not least, we will collect more coverage information test cases exercised and construct different structural profiles, for example, function execution sequence, function call sequence, and function call tree. The effects of different structural profiles on test case prioritization will also be empirically evaluated in regression testing.



---

*Source: 8343910-2016-05-04.xml*