# Bi-criteria Test Suite Reduction by Cluster Analysis of Execution Profiles

Alireza Khalilian, Saeed Parsa

► To cite this version:

Alireza Khalilian, Saeed Parsa. Bi-criteria Test Suite Reduction by Cluster Analysis of Execution Profiles. 4th Central and East European Conference on Software Engineering Techniques (CEESET), Oct 2009, Krakow, Poland. pp.243-256, 10.1007/978-3-642-28038-2_19. hal-01527390

HAL Id: hal-01527390

https://inria.hal.science/hal-01527390

Submitted on 24 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Bi-Criteria Test Suite Reduction by Cluster Analysis of Execution Profiles

Alireza Khalilian and Saeed Parsa

Iran University of Science and Technology, Tehran, Iran

khalilian@comp.iust.ac.ir, parsa@iust.ac.ir

**Abstract.** The aim has been to minimize regression test suites while retaining fault detection capability of the test suite admissible. An appropriate minimized test suite should exercise different execution paths within a program. However, minimization of test suites may result in significant fault detection loss. To alleviate the loss, a new bi-criteria heuristic algorithm, using cluster analysis of test cases execution profiles is proposed in this paper. Cluster analysis of execution profiles categorizes test cases according to their similarity in terms of exercising a certain coverage criterion. Considering additional coverage criteria the proposed algorithm samples some test cases from each cluster. These additional criteria exercise execution paths, different from those covered by the main testing criteria. Experiments on the *Siemens* suite manifest the applicability of the proposed approach and present interesting insights into the use of cluster analysis to the bi-criteria test suite reduction.

**Keywords:** Software regression testing, testing criteria, test suite minimization, test suite reduction, fault detection effectiveness

## 1 Introduction

*Software regression testing* is a critical activity in the development and maintenance of evolving software. A major difficulty with the regression testing is the excessive number of test cases accumulated while generating new test cases to test any new or modified functionality within the program [1]. To resolve the difficulty and to reduce the excessive cost of regression testing, various *coverage-based* and *distribution-based* techniques have been proposed [2,3,4,5,6,7,8]. These techniques attempt to permanently discard redundant test cases and retain the most effective ones to reduce the excessive cost of regression testing [6]. An effective technique for regression testing is to find a minimal subset of test cases which satisfy all the test requirements as the original set does [9]. A suitable subset could be found during the test case generation or after creating the test suite. Apparently the less the number of test cases the less time it takes to test the program. This consequently improves the effectiveness of the test process. The technique is commonly known as *test suite reduction* or *test suite minimization* in the literature and the resulting suite is called *representative set* [3].

Almost all the previous test suite reduction techniques could significantly reduce the size of the test suites. But an important issue deals with how well these reduced suites can be compared with their corresponding un-reduced suites using criteria rather than the suite size criterion. Since the purpose of test case execution is to detect faults
in the software, one measure of the suite quality is its fault detection capability. In fact, a potential drawback observed in test suite reduction studies is that permanent removal of test cases from a test suite may highly decrease the fault detection effectiveness of the remaining suite. Thus, the tradeoff between the time required to execute and manage test suites and their fault detection effectiveness should be considered when applying test suite reduction techniques [2].

*Coverage-based* minimization techniques attempt to eliminate redundant test cases while maximizing the code coverage of a program in order to ensure that all different execution paths are exercised and the majority of the faults are revealed. However, test cases considered as redundant in respect with the main testing criterion may be considered as essential test cases with respect to the additional criteria. This is evidenced by the results of the empirical studies presented in [10]. These results suggest that using several coverage criteria, rather than a single criterion, during test suite reduction is indeed useful in determining test cases which are likely to expose different faults. However, code coverage solely is not a sufficient criterion for selecting representative test cases from the original test suite. This is because high code coverage may be achieved by selecting simple test cases that do not reflect the program execution in real situations [11] and the resultant reduced suite may not be efficient in detecting faults.

A number of recent papers have investigated techniques for test suite reduction using *execution profiles*, applied in *distribution-based* techniques [8]. An execution profile generated by a test case identifies the program elements covered by the test case. For example, a profile may indicate which branches or data flow relationships are exercised by a test case. Distribution-based techniques reflect additional information about test cases that can be helpful in determining effective test cases when reducing the original test suite. Distribution-based test suite reduction techniques are examples of *observation-based* testing [12]. Observation-based testing is potentially applicable in situations where it is desirable to filter a large amount of test cases identifying a promising subset of test cases for conformance to the requirements [13]. Despite the effectiveness in detecting failures, observation based methods do not necessarily provide full coverage [8]. Moreover, empirical studies [8] show that the functionality of these methods varies with the size of the test suite. These studies also indicate that coverage-based and distribution-based techniques often do not select similar test cases and are complementary because they find different faults.

To address the limitations of the coverage-based and distribution-based approaches, in this paper a bi-criteria heuristic algorithm is proposed. The algorithm is applied to each cluster of execution profiles of the test cases, iteratively. In each of its iteration, a representative test case enhancing the cumulative coverage of the reduced test suite is selected from each cluster. The selection is based on the two criteria to improve the fault detection effectiveness. In fact, by selecting a test case from each cluster, all test cases that are now redundant with respect to the first criterion, are re-verified. Among such test cases, those that cover the maximum number of unmarked requirements with respect to the second criterion are inserted into the reduced suite. At the end of this process, the reduced suite is verified to be coverage adequate with respect to the second criterion. If not, the described process is repeated considering the second criterion, yielding bi-criteria coverage adequacy of the reduced suite. In order to evaluate the ap-
plicability of the proposed approach, we conducted experiments on the Siemens suite. We also implemented the well-known *H* algorithm [3], to compare the results of *reducing* suites using our distribution-based heuristic algorithm with those of *minimizing* test suites using the *H* algorithm.

The rest of the paper is organized as follows: Section 2 discusses the background of the test suite reduction techniques. Section 3 contains the outline of the proposed approach. Section 4 describes the empirical studies and the obtained results. Finally, conclusions are mentioned in section 5.

## 2 Background and Related Work

In this section, first the formal definition of the Test Suite Reduction problem will be introduced. Then, some related studies in this context are described. Afterwards, two general approaches to this problem are presented.

### 2.1 Test Suite Reduction

The first formal definition of test suite reduction problem introduced in 1993 by Harrold et al. [3] as follows:

Given. {$t_1, t_2, ..., t_m$} is test suite *T* from *m* test cases and {$r_1, r_2, ..., r_n$} is set of test requirements that must be satisfied in order to provide desirable coverage of the program entities and each subsets {$T_1, T_2, ..., T_n$} from *T* are related to one of $r_i$s such that each test case $t_j$ belonging to $T_i$ satisfies $r_i$.

Problem. Find minimal test suite $T'$ from *T* which satisfies all $r_i$s covered by original suite *T*.

Generally the problem of finding the minimal subset $T'$, $T' \subseteq T$ which satisfies all requirements of *T*, is NP-complete [15], because we can reduce the *minimum setcover* problem to the problem of test suite minimization in polynomial time. Thus, researches use heuristic approaches to solve this problem. One heuristic method proposed by Harrold et al. [3], tries to find the smallest representative set that provides the same coverage as the entire test suite does.

Related work in the context of test suite reduction can be classified into two main categories: The works in which a new technique is presented [3,4,5,16,9,6,7], and empirical studies on the previous techniques [1,2,15,17]. The works which propose a new approach commonly include heuristic algorithms [14], genetic algorithm-based techniques [18] and approaches based on integer linear programming [19].

Testing criteria are defined in order to help the selection of subsets of the input domain to be covered during testing. For example, a code coverage criterion provides test suite adequacy with respect to coverage of the program entities and also provides a check on its quality. Assuming testing criterion *C* which satisfies by the test suite *T*, a test case, *t*, is *redundant* if the suite *T* - {$t$} also satisfies *C* [5]. Therefore, removing those test cases which are redundant with respect to some specific criteria preserves test suite's adequacy with respect to it. In previous empirical studies [15] researchers commonly apply various code coverage criteria in their reduction techniques. The results of empirical studies [2,17] show that the more percentage of the test suite size is reduced the more percentage of faults will be lost.
## 2.2 Coverage-based Techniques

The main purpose of traditional software testing is to achieve the maximum code coverage [8] and the main idea is that the test suite is capable of exercising the whole program under test. In other words, there must be some test cases per program element (including statement, branch, def-use pair and so on) which can cover it. This is due to unreliability of the uncovered parts of the program during testing. But as mentioned above, code coverage alone is not sufficient for selecting test cases. If the code coverage is the main factor in determining the quality of a test suite, then it is desirable to have the minimal subset of the test suite that covers the program elements the same as the original suite [8]. Even if the code coverage is not the main factor in test suite quality, it is possible to use it as the first step of other reduction approaches. The main purpose of executing test cases is to expose faults as far as possible. Thus fault detection effectiveness of a test suite is of great importance. On the other hand, due to large amount of test cases and time constraints for retesting the software every time it modifies, it is necessary to keep the size of the test suite manageable [2]. Therefore, there must be some tradeoff between the suite size and its fault detection effectiveness.

Usually a test suite reduction technique attempts to remove redundancy among test cases and retain the most *effective* ones into the test suite [6]. Effective test cases are those that are capable of satisfying the most requirements as well as exposing the most of the existing faults. Note that the more requirements are satisfied, the more execution paths within the program would be exercised which yields the all kinds of the faults to be exposed. When a reduction algorithm determines some test cases to be redundant, it uses a certain criterion to do this. But redundant test cases which are thrown away during test suite reduction may exercise unique situations in the software with respect to another criterion [10]. For example, a reduction algorithm may select test cases which cover the most number of branches of a program. During the reduction, some test cases may cover the same branches as covered by test cases in the reduced suite. Hence, such test cases are redundant and will be discarded. However, such test cases may not be redundant with respect to a second criterion such as def-use pair. So they will be preserved from discarding because they cover execution paths which may contain some kind of faults. These results are evidenced by empirical studies in [10]. Therefore, using multiple criteria during reduction is useful to select test cases that are more likely to expose faults.

## 2.3 Distribution-based Techniques

Distribution-based techniques select test cases according to how their profiles are distributed by *dissimilarity metric* in the multi-dimension *profile space* [8]. Dissimilarity metric is a function that produces a real number for each pair of profiles which shows the degree of their dissimilarity. Distribution-based methods can be described using two closely related techniques: *cluster filtering* and *failure-pursuit*. Cluster filtering calls for using *automatic cluster analysis* to partition the test pool [8]. The purpose of cluster analysis is to partition the population such that objects with similar attributes are in the same cluster. After clustering, test cases are sampled from each cluster.
Distribution-based test suite reduction techniques are examples of *observation-based* testing [8]. It calls for first taking an existing set of test cases (possibly a large amount), and then executing them on an instrumented version of the program under test in order to obtain execution profiles that characterize the executions [13]. Next, it analyzes the profiles and selects a subset of test cases for conformance to requirements. The analysis of profiles can be achieved using *multivariate data analysis* like *clustering* [12]. Such kind of analysis can extract additional information from the profile data. In general, observation-based testing is applicable when it is desirable to identify a promising subset of test cases for conformance to requirements as well as filtering legacy test suites. An observation-based testing is defined by determining the following: (1) the type of the execution profile (2) a filtering or reduction technique to select a subset of executions and (3) an optional augmentation procedure. The type of the applied profiling should reflect the runtime events. Software testing research and practice suggest a variety of alternatives such as statement, basic block, branch, all-uses and so on [20].

The distribution-based techniques used for reducing test suites, determine some characteristics of the distribution profile that are likely to detect faults, and apply them during the selection of test cases. For example, clusters that have similar profiles contain redundant test cases and selecting one or a few representatives are sufficient. Also isolated profiles contain test cases that indicate unusual conditions and are likely to detect faults. Test case cluster filtering is defined by selecting *clustering algorithm*, *dissimilarity metric*, *number of clusters* and *sampling method* [8].

# 3 The Proposed Approach

Our approach to test suite reduction has been motivated by combining the two general techniques called distribution-based and coverage-based techniques. These techniques are fully described in the previous section. *Distribution-based* techniques are capable of determining similar test cases by means of clustering. These techniques cluster test cases within a test suite to determine test cases which exercise similar execution paths within the program. Since all the test cases within a same cluster have almost a same execution profile, most of them are likely to be redundant. Hence, sampling some representatives from each cluster may lead to a selection of distinguished test cases which test different execution paths within the program under test. Therefore, the major benefit of these techniques is to compose a reduced suite of distinct test cases with minimum redundancy. However, despite of covering rather non-overlapping execution paths, distribution based techniques do not necessarily provide full coverage of the execution paths. On the other hand, the coverage-based techniques insist on test suits with full coverage rather than non-overlapping test cases. Therefore, we combined these two techniques to provide a new bi-criteria technique to form full coverage reduced test suites with minimum overlap in the execution profiles of the including test cases.

The more the number of testing criteria the bigger the size of the test suite will be. However, experimental results show that two testing criteria can establish an appropriate tradeoff between the suite size and the fault detection capability of the reduced test suite. The general procedure of our approach is as follows: At the first step, the program is instrumented according to two different coverage criteria. Then, test cases in the test
suite are executed over the instrumented version of the program to collect execution profiles. Next, the collected profiles are clustered by means of a clustering algorithm. The clustered test cases and the testing requirements are applied as inputs to run our test suite reduction algorithm. After the reduction, the reduced suite will be coverage adequate with respect to the first criterion. The adequacy of the reduced suite is verified with respect to the second criterion. In the case of inadequacy, a similar algorithm using the second criterion can be applied to augment test cases providing coverage adequacy of the reduced suite with respect to the second criterion.

A detailed pseudocode description of the proposed algorithm is given in Fig. 1 and 2. Initially, all the testing requirements are unmarked and the number of unmarked requirements considering each of the two testing criteria is counted for each test case. Then, all the clusters of the test cases are sorted in ascending order of their number of test cases. In the next step, the algorithm keeps looking for representative test cases in each cluster of the sorted list of clusters until the selected representative test cases form a coverage adequate test suite with respect to the first criterion. In each of its iteration of the while-loop in Fig. 1, all the test cases within the next cluster of the test suite are added to a set called *list*. A function, *SelectTest*, selects a representative test case from the cluster and augments it to the reduced suite, *RS*. Each testing requirement satisfied by the selected representative test case is marked as satisfied in two arrays called *marked*₁ and *marked*₂. Each of these marked requirements may be satisfied by a number of test cases. If all the requirements satisfied by each of these test cases are marked with respect to one of the two test criteria, the test case number is augmented to the list of the redundant test cases, redundant, for the ith criterion. Finally, all those cases which are in the current cluster, *list*, and their numbers appear in the set {*redundant*₁ – *redundant*₂}, are augmented to a set, *redundant*. The function *SelectSomeMoreTest-Cases* is then invoked to select some test cases from the set, *redundant*, and add the selected test cases to the final reduced suite, *RS*.

The function *SelectTest* selects a test case from a certain cluster. This function attempts to find a test case with maximum number of unmarked requirements with respect to the first criterion. In case of a tie, the number of unmarked requirements for the second criterion is considered. If tie occurs again, sum of the satisfied requirements with respect to the both criteria is considered, and finally a test case is selected randomly. The function *SelectSomeMoreTestCases* attempts to find some test cases from *redundant* that satisfy the maximum number of unmarked requirements with respect to the second criterion. Each time a test case is selected those test cases that become redundant are removed from the *redundant* set.

# 4 Empirical Studies

To evaluate and compare the proposed approach with prior approaches in test suite reduction area, an experiment similar to previous studies has been conducted. This section describes the experiment.
define:
  requirement<sup>t</sup>: set of coverage requirements for minimization with respect to the <sup>i</sup>th criterion:
    r<sub>1</sub><sup>j</sup>, r<sub>2</sub><sup>j</sup>, ..., r<sub>n</sub><sup>j</sup>, i = 1, 2
input:
  t<sub>1</sub>, t<sub>2</sub>, ..., t<sub>m</sub>: test cases present in the unreduced test suite
  cv<sub>i</sub>[m, n]: coverage matrix representing the <sup>i</sup>th requirement coverage of each test case
  clusters<sub>i</sub>: array[1..k] of cluster instances for the <sup>i</sup>th requirement, each containing similar test cases
output:
  RS: a reduced suite of test cases from the original test suite.
algorithm TestSuiteReduction
begin
  currentClusterIndex := 0; redundant := redundant1 := redundant2 := {}; RS := {}; // initialization
  foreach criterion <i>and requirement j do marked<sub>i</sub>[j] := false;
    for each test case <t> and criterion <i>do
      numUnmarked<sup>t</sup>[t] := number of the elements in cv<sub>i</sub>[t, n] for which cv<sub>i</sub>[t, j] == true;
      Sort(clusters, ascending); // sorts the input array ascending or descending
    while there exists r<sub>j</sub><sup>i</sup> ∈ requirements<sup>t</sup> s.t. marked<sub>i</sub>[i] == false do
      if currentClusterIndex == k then currentClusterIndex := 0;
      list := all t<sub>j</sub> ∈ clusters<sub>i</sub>[currentClusterIndex];
      if Card(list) == 1 then
        test := t ∈ list;
        if exists r<sub>j</sub><sup>i</sup> ∈ requirements<sup>t</sup> s.t. cv<sub>i</sub>[test, r<sub>j</sub><sup>i</sup>] == true and marked<sub>i</sub>[j] == false then
          nextTest := test;
          else nextTest := 0;
        end if
      else nextTest := SelectTest(list);
      end if
      if nextTest ≠ 0 then
        RS := RS ∪ {nextTest};
      foreach criterion <c> do
        foreach r<sub>j</sub><sup>c</sup> ∈ requirements<sup>t</sup> s.t. cv<sub>i</sub>[nextTest, r<sub>j</sub><sup>c</sup>] == true and marked<sub>i</sub>[j] == false do
          marked<sub>i</sub>[j] := true;
        foreach test case <t> in the test suite s.t. cv<sub>c</sub>[t, r<sub>j</sub><sup>c</sup>] == true do
          numUnmarked<sup>t</sup>[t] := numUnmarked<sup>t</sup>[t] - 1;
          if numUnmarked<sup>t</sup>[t] == 0 and t ∉ RS then redundant<sub>c</sub> := redundant<sub>c</sub> ∪ t;
        end for
      end for
      end for
      end for
      currentClusterIndex := currentClusterIndex + 1;
      redundant := redundant1 - redundant2;
      if Card(redundant) != 0 then
        redundant := redundant ∩ list;
        SelectSomeMoreTestCases(redundant, RS);
        redundant := redundant1 := redundant2 := {};
      end if
      end while
      return RS;
end TestSuiteReduction

<caption>Fig. 1. Pseudocode description of our proposed heuristic algorithm for test suite reduction.</caption>

4.1 Subject Programs and Measures

We used the *Siemens suite* as subjects in our experiments. Siemens suite includes seven programs in C language developed by the researchers at Siemens Corporation for exper-
```python
function SelectTest(testCaseSet)
    begin
        foreach t_i in testCaseSet do compute numUnmarked'[i], the number of elements in cv_1[t_b, r_j^1] for which
            marked_1[j] == false;
        testList1 := all t_i from testCaseSet for which numUnmarked'[i] is the maximum;
        if Card(testList1) != 0 then
            if Card(testList1) == 1 then testCase := the test case in testList1;
            else
                foreach t_i in testList1 do compute numUnmarked^2[i], the number of elements in cv_2[t_b, r_j^2] for which
                    marked_2[j] == false;
                testList2 := all t_i from testList1 for which numCovered^2[i] is the maximum;
                if Card(testList2) == 0 then testList2 := testList1;
                if Card(testList2) == 1 then testCase := the test case in testList2;
                else
                    foreach t_i in testList2 do compute numCovered[i], sum of the number of elements for which
                        cv_1[t_b, r_j^1] == true or cv_2[t_b, r_j^2] == true;
                    testList3 := all t_i from testList2 for which numCovered[i] is the maximum;
                    if Card(testList3) == 0 then testList3 := testList2;
                    if Card(testList2) == 1 then testCase := the test case in testList3;
                    else testCase := any test case in testList3;
                endif
            endif
        endif
    endif
    return testCase;
end SelectTest
```

<caption>**Fig. 2.** Function *SelectTest* to select a test case from current cluster and function *SelectSomeMoreTestCases* to select some test cases from the *redundant* set into the *RS*.</caption>

iments with control-flow and data-flow test adequacy criteria [21]. These programs are associated with several faulty versions. Each faulty version of each program contains a single fault seeded in it. For each program there is a test pool which contains test cases developed for different black-box and white-box testing objectives.
To investigate the effectiveness of our approach, we measured the following from our experiments:

1. The percentage suite size reduction = $\frac{|T|-|T_{Red}|}{|T|} \times 100$, where $|T|$ is the number of test cases in the original test suite and $|T_{Red}|$ is the number of test cases in the reduced test suite.

2. The percentage fault detection loss = $\frac{|F|-|F_{Red}|}{|F|} \times 100$, where $|F|$ is the number of distinct faults exposed by original test suite and $|F_{Red}|$ is the number of distinct faults detected by the reduced suite.

## 4.2 Clustering and Analysis Tools

In order to cluster execution profiles of test cases, Weka 3.5.8 [22] has been used. Weka is a java-based tool that provides a uniform interface to many different learning algorithms along with methods for pre and post processing and for evaluating the results of learning schemas on any given dataset. It also provides implementations of the state-of-the-art learning algorithms and has been tested under Linux, Windows and Macintosh operating systems. Besides, we used SAS 9.1.3 [23] to create boxplots. Boxplot diagrams are commonly used to visualize the empirical results in test suite reduction studies.

Our experiments include a large number of test cases each of which covers a lot of requirements. Thus, a large number of high dimensional data should be clustered. However, fast and effective clustering of such data is extremely difficult because of their large volume and high dimensionality [24]. On the other hand, clustering algorithms need to set the number of clusters. Selecting the number of clusters affect the separation of test cases. The CLOPE algorithm [24] is a fast and efficient method for clustering large and high dimensional data. In this algorithm, a value called Repulsion is set which controls level of intra-cluster similarity. The number of clusters changes by varying this value. We felt that as a first step for exploration, using the CLOPE algorithm would lead to a good compromise between fast and effective clustering and a reasonable number of clusters.

## 4.3 Experiment Setup and Results

Our experiments follow a setup similar to that used by Rothermel et al [2]. For each program, we created branch coverage adequate test suites for six different suite ranges named as B, B1, B2, B3, B4 and B5. For each suite range, we first selected X* LOC test cases randomly from the test pool and added to the test suite, where X is 0, 0.1, 0.2, 0.3, 0.4 and 0.5 respectively and LOC is the number of lines of code for each program. Then, randomly-selected test cases are added into the test suite as necessary so long as each test case increased the cumulative branch coverage of the suite, until the test suite becomes adequate with respect to branch coverage. In this way, the developed test suites have various types and varying levels of redundancy exist between them. We created 1000 such branch coverage adequate test suites for each program. In order to gather branch coverage information of test cases, all programs were hand-instrumented.
In our experiments, we used all-uses coverage as the second criterion. We measured all-uses coverage using the ATAC tool [25].

In order to evaluate the effectiveness of our approach, we implemented our algorithm and applied it to the generated suites with branch coverage as first criterion and all-uses as the second criterion. We also implemented the *H* algorithm [3] and conducted similar experiments on the generated suites with respect to branch coverage. The results of this experiment are shown in the columns labeled *H* and *P* in Table 1 for the *H* algorithm and the proposed algorithm respectively. The values in each row of the table are average values for 1000 suites in each range. In this table, |*T*| indicates for the original suite size, |*F*| for the number of faults exposed by the original suite, |*T*<sub>Red</sub>| for the reduced suite size, |*F*<sub>Red</sub>| for the number of faults exposed by the reduced suite size, %Size Reduction for the percentage suite size reduction and %Fault Loss for the percentage fault detection loss.

The boxplot in the Fig. 3 shows the distribution of the percentage of size reduction (SR) and percentage fault detection loss (FL) in the largest suite size range (B5) for each program. In this figure, boxes are paired such that, white pair of boxes shows percentage of size reduction and gray pair of boxes shows the percentage of fault detection loss. In each pair, left side box indicates for our algorithm and the right side one indicates for the *H* algorithm. For all programs, it is observed that the percentage suite size reduction by the proposed algorithm is less than the respective suite size reduction using the *H* algorithm. This result is expected since our approach selects some additional test cases that are not *redundant* with respect to the second criterion though they are redundant with respect the first criterion. For all programs, the percentage fault detection loss of the suites reduced by the proposed algorithm is less than the respective suites reduced by the *H* algorithm. We reason that the reduced suites generated using the proposed algorithm, are more efficient due to two main causes. First, clustering results in partitioning the test cases such that those with different execution profiles are gathered into different clusters. This gives us the opportunity to select as much unique test cases as possible.

Second, using second criterion during reduction may cause to selecting redundant test cases with different coverage of execution path within the program. These are also evidenced by the results of empirical studies.

To determine whether the degradation in fault detection loss observed for the proposed algorithm over the *H* algorithm is statistically significant, we conducted a *hypothesis test for the difference of the two means* [26]. The samples are the number of distinct faults exposed by each of the 1000 reduced test suites for suite size range B5 using the *H* algorithm and the proposed algorithm. We considered the *null hypothesis* that there is no difference in the mean number of the exposed faults by the two algorithms. We used a reference table of critical values presented in [26]. Table 2 shows the resulting *z values* computed for the hypothesis test along with the percentage confidence with which we may reject the null hypothesis. Note that for *z* values greater than 4.0, we can reject the null hypothesis with the confidence over than 99.99 percent.

## 4.4 Threats to Validity

In this section, we describe the potential threats to validity of our study.
<table><caption>**Table 1.** The results of the experiments comparing the *H* algorithm and the proposed algorithm.</caption><thead><tr><th rowspan="2">Program</th><th rowspan="2">Suite size range</th><th rowspan="2">|T|</th><th rowspan="2">|F|</th><th colspan="2">|T<sub>Red</sub>|</th><th colspan="2">|F<sub>Red</sub>|</th><th colspan="2">% Size Reduction</th><th colspan="2">% Fault Loss</th></tr><tr><th>H</th><th>P</th><th>H</th><th>P</th><th>H</th><th>P</th><th>H</th><th>P</th></tr></thead><tbody><tr><td rowspan="5">printtokens</td><td>B</td><td>17.79</td><td>3.85</td><td>8.19</td><td>8.48</td><td>3.26</td><td>3.56</td><td>52.86</td><td>51.13</td><td>9.21</td><td>6.39</td></tr><tr><td>B1</td><td>29.4</td><td>4.01</td><td>8.22</td><td>8.64</td><td>3.23</td><td>3.51</td><td>69.13</td><td>67.66</td><td>14.66</td><td>10.80</td></tr><tr><td>B2</td><td>46.45</td><td>4.29</td><td>8.15</td><td>8.73</td><td>3.16</td><td>3.56</td><td>77.48</td><td>76.17</td><td>19.31</td><td>15.04</td></tr><tr><td>B3</td><td>65.48</td><td>4.53</td><td>8.05</td><td>8.72</td><td>3.25</td><td>3.57</td><td>82.58</td><td>81.41</td><td>23.42</td><td>19.08</td></tr><tr><td>B4</td><td>84.96</td><td>4.68</td><td>7.97</td><td>8.80</td><td>3.03</td><td>3.53</td><td>85.63</td><td>84.51</td><td>28.99</td><td>22.00</td></tr><tr><td rowspan="5">printtokens2</td><td>B</td><td>13.41</td><td>8.47</td><td>8.01</td><td>8.99</td><td>8.17</td><td>8.27</td><td>39.08</td><td>31.62</td><td>4.46</td><td>2.28</td></tr><tr><td>B1</td><td>28.79</td><td>8.66</td><td>7.63</td><td>9.19</td><td>8.04</td><td>8.37</td><td>67.11</td><td>61.16</td><td>9.96</td><td>5.44</td></tr><tr><td>B2</td><td>51.68</td><td>9.24</td><td>7.13</td><td>9.40</td><td>8.10</td><td>8.57</td><td>79.47</td><td>74.57</td><td>12.88</td><td>6.99</td></tr><tr><td>B3</td><td>75.1</td><td>9.39</td><td>6.90</td><td>9.82</td><td>8.12</td><td>8.64</td><td>84.06</td><td>79.65</td><td>15.23</td><td>7.87</td></tr><tr><td>B4</td><td>99.73</td><td>9.53</td><td>6.64</td><td>10.07</td><td>8.19</td><td>8.75</td><td>87.74</td><td>83.69</td><td>16.78</td><td>8.04</td></tr><tr><td rowspan="5">replace</td><td>B</td><td>22.97</td><td>13.53</td><td>13.65</td><td>15.71</td><td>10.85</td><td>11.83</td><td>40.02</td><td>31.13</td><td>19.17</td><td>11.95</td></tr><tr><td>B1</td><td>38.36</td><td>15.49</td><td>13.52</td><td>16.11</td><td>11.01</td><td>12.23</td><td>61.15</td><td>53.99</td><td>29.92</td><td>20.22</td></tr><tr><td>B2</td><td>59.55</td><td>17.11</td><td>13.40</td><td>16.54</td><td>10.90</td><td>12.44</td><td>71.33</td><td>65.39</td><td>44.79</td><td>25.89</td></tr><tr><td>B3</td><td>84.94</td><td>18.64</td><td>13.18</td><td>16.84</td><td>9.97</td><td>12.83</td><td>78.28</td><td>73.24</td><td>49.69</td><td>29.94</td></tr><tr><td>B4</td><td>108.98</td><td>19.45</td><td>12.99</td><td>17.02</td><td>09.75</td><td>12.83</td><td>81.67</td><td>77.13</td><td>52.96</td><td>32.51</td></tr><tr><td rowspan="5">schedule</td><td>B</td><td>131.09</td><td>20.34</td><td>12.82</td><td>17.04</td><td>08.65</td><td>13.11</td><td>84.22</td><td>80.18</td><td>55.99</td><td>34.00</td></tr><tr><td>B1</td><td>8.73</td><td>3.54</td><td>6.30</td><td>6.8</td><td>2.97</td><td>3.20</td><td>26.65</td><td>21.09</td><td>14.22</td><td>8.39</td></tr><tr><td>B2</td><td>18.82</td><td>4.57</td><td>6.19</td><td>7.16</td><td>2.89</td><td>3.30</td><td>60.46</td><td>55.05</td><td>34.36</td><td>25.82</td></tr><tr><td>B3</td><td>33.19</td><td>5.33</td><td>6.01</td><td>7.23</td><td>2.96</td><td>3.39</td><td>74.66</td><td>70.46</td><td>43.03</td><td>35.04</td></tr><tr><td>B4</td><td>46.76</td><td>5.74</td><td>5.96</td><td>7.32</td><td>3.02</td><td>3.49</td><td>79.81</td><td>76.22</td><td>46.02</td><td>37.87</td></tr><tr><td rowspan="5">schedule2</td><td>B</td><td>7.96</td><td>2.39</td><td>5.35</td><td>5.66</td><td>2.09</td><td>2.15</td><td>31.18</td><td>27.37</td><td>12.65</td><td>9.53</td></tr><tr><td>B1</td><td>18.06</td><td>2.77</td><td>5.24</td><td>5.77</td><td>2.08</td><td>2.17</td><td>64.17</td><td>60.86</td><td>21.99</td><td>17.97</td></tr><tr><td>B2</td><td>32.08</td><td>3.44</td><td>5.09</td><td>5.73</td><td>2.10</td><td>2.27</td><td>77.03</td><td>74.46</td><td>35.49</td><td>29.68</td></tr><tr><td>B3</td><td>44.69</td><td>3.88</td><td>5.00</td><td>5.77</td><td>2.03</td><td>2.39</td><td>80.81</td><td>78.63</td><td>39.96</td><td>33.03</td></tr><tr><td>B4</td><td>59.86</td><td>4.36</td><td>4.88</td><td>5.68</td><td>2.12</td><td>2.40</td><td>85.24</td><td>83.46</td><td>45.78</td><td>39.71</td></tr><tr><td rowspan="5">tcas</td><td>B</td><td>74.77</td><td>4.86</td><td>4.72</td><td>5.61</td><td>2.06</td><td>2.51</td><td>87.77</td><td>86.04</td><td>51.94</td><td>43.38</td></tr><tr><td>B1</td><td>5.70</td><td>7.13</td><td>5.00</td><td>5.04</td><td>6.44</td><td>6.59</td><td>11.12</td><td>10.45</td><td>8.32</td><td>6.57</td></tr><tr><td>B2</td><td>9.22</td><td>8.70</td><td>5.00</td><td>5.10</td><td>6.09</td><td>6.52</td><td>39.53</td><td>38.56</td><td>26.04</td><td>21.48</td></tr><tr><td>B3</td><td>15.16</td><td>11.21</td><td>5.00</td><td>5.09</td><td>6.37</td><td>6.53</td><td>57.70</td><td>56.97</td><td>42.41</td><td>35.96</td></tr><tr><td>B4</td><td>28.29</td><td>15.54</td><td>5.00</td><td>5.08</td><td>6.58</td><td>6.68</td><td>66.06</td><td>65.50</td><td>52.95</td><td>43.98</td></tr><tr><td rowspan="5">totinfo</td><td>B</td><td>9.02</td><td>13.85</td><td>5.54</td><td>6.34</td><td>12.89</td><td>13.17</td><td>36.97</td><td>27.28</td><td>6.69</td><td>3.84</td></tr><tr><td>B1</td><td>20.62</td><td>14.78</td><td>5.46</td><td>6.49</td><td>11.83</td><td>13.62</td><td>68.07</td><td>60.52</td><td>17.71</td><td>10.59</td></tr><tr><td>B2</td><td>36.74</td><td>16.11</td><td>5.33</td><td>6.51</td><td>11.91</td><td>13.86</td><td>78.66</td><td>73.68</td><td>25.99</td><td>17.06</td></tr><tr><td>B3</td><td>52.50</td><td>17.04</td><td>5.25</td><td>6.37</td><td>11.17</td><td>13.97</td><td>83.43</td><td>80.64</td><td>31.38</td><td>21.40</td></tr><tr><td>B4</td><td>70.25</td><td>17.77</td><td>5.20</td><td>6.33</td><td>10.86</td><td>14.10</td><td>87.10</td><td>83.66</td><td>32.09</td><td>22.87</td></tr><tr><td rowspan="5">totinfo</td><td>B5</td><td>86.23</td><td>19.37</td><td>5.18</td><td>6.28</td><td>13.00</td><td>14.01</td><td>88.23</td><td>86.22</td><td>31.79</td><td>22.45</td></tr></tbody></table>
<table><caption>**Table 2.** Computed *z* value and the corresponding percentage of confidence for rejecting the null hypothesis for each program.</caption><thead><tr><th>Program Name</th><th>Computed z value</th><th>Percentage of confidence for rejecting the null hypothesis</th></tr></thead><tbody><tr><td>printtokens</td><td>15.46</td><td>&gt;99.99%</td></tr><tr><td>printtokens2</td><td>15.36</td><td>&gt;99.99%</td></tr><tr><td>replace</td><td>39.45</td><td>&gt;99.99%</td></tr><tr><td>schedule</td><td>8.82</td><td>&gt;99.99%</td></tr><tr><td>schedule2</td><td>8.20</td><td>&gt;99.99%</td></tr><tr><td>tcas</td><td>16.01</td><td>&gt;99.99%</td></tr><tr><td>totinfo</td><td>7.66</td><td>&gt;99.99%</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 3.** The boxplot for the percentage suite size reduction and percentage fault detection loss.</figcaption></figure>

*Threats to construct validity.* In our study, the measurement for the percent of fault loss assumes simple model for cost which treats all faults as equally severe. But in practice, faults have wide range of severity from less critical to more critical.

*Threats to internal validity.* The most important issue deals with hand-instrumentation of code which we have done for obtaining branch coverage of test cases. To validate the correctness of this process, the instrumentation was re-verified. Another issue is composition of the test suites. However, we utilized the process of creating suites which was employed in previous studies [2].

*Threats to external validity.* Siemens programs are widely used in software testing studies. However, these programs are limited and their faults are known. Moreover, they are not real programs and the faults are hand-seeded. Space program is a big and real one, used to our case study. But it is one of such a program we used.
# 5 Conclusions

We have presented a new approach for test suite reduction that attempts to identify effective test cases in terms of their fault detection effectiveness. This approach is based on the intuition that *clustering* of the test cases *execution profiles*, can partition the test suite such that similar test cases in terms of exercising a certain coverage criterion, would be in the same clusters. Hence, determining redundant test cases from essential ones could be done effectively and simply. In order to improve the fault detection effectiveness of the reduced suite, we used two coverage criteria during the reduction process. The results of empirical studies demonstrate the effectiveness of the proposed approach by generating reduced test suites with less fault detection loss.

# References

1. Rothermel, G., Harrold, M.J., von Ronne, J., Hong, C.: Empirical Studies of Test-Suite Reduction. Journal of Software Testing, Verification, and Reliability 12(4), 219-249 (2002)

2. Rothermel, G., Harrold, M.J., Ostrin, J., Hong, C.: An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites. In: Proceedings of the International Conference on Software Maintenance. IEEE Computer Society (1998)

3. Harrold, M.J., Gupta, R., Soffa, M.L.: A methodology for Controlling the Size of a Test Suite. ACM Transactions on Software Engineering and Methodology 2, 270-285 (1993)

4. Chen, T.Y., Lau, M.F.: Heuristics Toward the Optimization of the Size of a Test Suite. In: Proc. of the 3rd International Conference on Software Quality Management, vol. 2, pp. 415-424. Seville, Spain (1995)

5. Jones, J.A., Harrold, M.J.: Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage. IEEE Transactions on Software Engineering 29, 195-209 (2003)

6. McMaster, S., Memon, A.: Call-Stack Coverage for GUI Test Suite Reduction. IEEE Transactions on Software Engineering 34, 99-115 (2008)

7. Tallam, S., Gupta, N.: A Concept Analysis Inspired Greedy Algorithm for Test Suite Minimization. In: Proc. of the 6th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. ACM, Lisbon, Portugal (2005)

8. Leon, D., Podgurski, A.: A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases. In: Proc. of the 14th International Symposium on Software Reliability Engineering. IEEE Computer Society (2003)

9. Chen, Z., Xu, B., Zhang, X., Nie, C.: A Novel Approach for Test Suite Reduction Based on Requirement Relation Contraction. In: Proc. of the 2008 ACM Symposium on Applied computing. ACM, Fortaleza, Ceara, Brazil (2008)

10. Jeffrey, D., Gupta, N.: Improving Fault Detection Capability by Selectively Retaining Test Cases during Test Suite Reduction. IEEE Transactions on Software Engineering 33, 108-123 (2007)

11. Marick, B.: The Craft of Software Testing: Subsystem Testing. Prentice Hall, Englewood Cliffs, NJ (1995)

12. Leon, D., Podgurski, A., White, L.J.: Multivariate Visualization in Observation-based Testing. In: Proc. of the 22nd International Conference on Software Engineering. ACM, Limerick, Ireland (2000)

13. Dickinson, W., Leon, D., Podgurski, A.: Finding Failures by Cluster Analysis of Execution Profiles. In: Proc. of the 23rd International Conference on Software Engineering. IEEE Computer Society, Toronto, Ontario, Canada (2001)
14. Dickinson, W., Leon, D., Podgurski, A.: Pursuing Failure: the Distribution of Program Failures in a Profile Space. In: Proceedings of the 8th European Software Engineering Conference Held Jointly with 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, Vienna, Austria (2001)

15. Zhong, H., Zhang, L., Mei, H.: An Experimental Study of Four Typical Test Suite Reduction Techniques. Information and Software Technology 50, 534–546 (2008)

16. Chen, T.Y., Lau, M.: A New Heuristic for Test Suite Reduction. Information and Software Technology 40 (5-6) (1998)

17. Wong, W.E., Horgan, J.R., London, S., Mathur, A.P.: Effect of Test Set Minimization on Fault Detection Effectiveness. Software-Practice and Experience 28, 347-369 (1998)

18. Mansour, N., El-Fakih, K.: Simulated Annealing and Genetic Algorithms for Optimal Regression Testing. Journal of Software Maintenance 11, 19-34 (1999)

19. Black, J., Melachrinoudis, E., Kaeli, D.: Bi-Criteria Models for All-Uses Test Suite Reduction. In: Proc. of the 26th International Conference on Software Engineering. IEEE Computer Society (2004)

20. Harrold, M.J., Rothermel, G., Wu, R., Yi, L.: An Empirical Investigation of Program Spectra. In: Proc. of the 1998 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. ACM, Montreal, Quebec, Canada (1998)

21. Rothermel, G., Elbaum, S., Kinneer, A., Do, H.: Software-artifact Infrastructure Repository, http://www.cse.unl.edu/galileo/sir

22. Witten, H. Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques. 2nd ed., Morgan Kaufmann series in Data Management Systems (2005)

23. SAS 9.1.3 Documentation, SAS/GRAPH 9.1 Reference, http://support.sas.com/documentation/onlinedoc/91pdf/index_913.html

24. Yang, Y., Guan, X., You, J.: CLOPE: a Fast and Effective Clustering Algorithm for Transactional Data. In: Proc. of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, Edmonton, Alberta, Canada (2002)

25. Horgan, J R., London, S.A.: ATAC: A Data Flow Coverage Testing Tool for C. In: Proc. Symp. Assessment of Quality Software Development Tools, pp. 2-10 (1992)

26. Freund, J.E.: Mathematical Statistics. 5th ed. Prentice-Hall (1992)