Test Suite Reduction with Selective Redundancy

Abstract loss in fault detection effectiveness. However, the empir-

ical study conducted in [14] suggests that minimized test
Software testing is a critical part of software develop- suites can severely compromise the fault detection capabil-
ment. Test suite sizes may grow significantly with subse- ities of the test suites. There are two implications of this
quent modifications to the software over time. Due to conflict: first, there are situations where minimization can
time and resource constraints for testing, test suite achieve high suite size reduction without significantly de-
minimiza- tion techniques attempt to remove those test creasing fault detection effectiveness; second, there are
cases from the test suite that have become redundant over also situations where minimization can achieve high suite
time since the requirements covered by them are also size reduction at the expense of significant loss in fault
covered by other test cases in the test suite. Prior detec- tion effectiveness.
work has shown that test suite minimization techniques Intuitively, any time a test case is thrown away from a
can severely compromise the fault detection effectiveness suite, the suite loses an opportunity for detecting faults.
of test suites. In this pa- per, we present a novel approach Test suite reduction, therefore, ultimately involves a
to test suite reduction that attempts to selectively keep tradeoff be- tween the suite’s size and fault detection
redundant tests in the reduced suites. We implemented effectiveness. The focus of the approach for test suite
our technique by modifying an ex- isting heuristic for test reduction developed in this paper is to achieve high suite
suite minimization. Our experiments show that our size reduction while si- multaneously allowing for low
approach can significantly improve the fault detection fault detection effectiveness loss. The intuition driving our
effectiveness of reduced suites without severely af- fecting current work is that when a non-reduced suite contains lots
the extent of test suite size reduction. of redundancy with respect to a coverage criterion, it may
be helpful to selectively keep some of that redundancy in
the reduced test suite so as to re- tain more fault detection
1 Introduction effectiveness in the reduced suite, hopefully without
Software testing and retesting occurs continuously during significantly affecting the amount of suite size reduction.
the software development lifecycle. As software grows The test suite minimization problem [7] can be stated as
and evolves, so too do the accompanying test suites. Over follows.
time, some test cases in a test suite may become redundant Given: A test suite T , a set of testing requirements {r1
as the requirements executed by them are also executed by , r2 ,· · ·,rn }, that must be satisfied to provide the desired
other test cases in the test suite. Due to time and resource test coverage of the program, and subsets {T1 , T2 , · · · ,
con- straints for re-testing the software every time it is Tn } of T , one associated with each of the ri ’s such that
modified, it is important to develop techniques that keep any one of the test cases tj belonging to Ti covers ri .
the test suite size manageable by removing those test cases
that may have become redundant with respect to the Problem: Find a minimal cardinality subset of T that
coverage of program requirements. exer- cises all ri ’s exercised by the unminimized test suite
Since test suite minimization removes test cases, mini- T.
mized suites may be weaker at detecting faults in software For example, the desired coverage of the program may be
than their unminimized counterparts. Previous work on a set of test cases that cover all edges in the control flow
test suite minimization has shown some conflicting graph of the program. The test suite minimization problem
results. In [18], it was shown that minimizing test suites then is: given a test suite satisfying the all-edges adequacy
while keep- ing all-uses coverage constant could result criterion, find a minimal cardinality subset of the test suite
in little to no that covers all edges in the program. The existing
techniques for test
suite minimization do not consider keeping any mized suite and mark the requirements covered by the
redundancy with respect to the given coverage criterion selected test cases.
during the suite minimization process.
Any test suite minimization algorithm addressing the 3. Consider the unmarked requirements in increasing or-
above problem can be modified to incorporate our der of the cardinality of the set of test cases exercising
approach to generate reduced test suites that selectively a requirement. If several requirements are tied since
retain some of the test cases that are redundant with the sets of test cases exercising them have the same
respect to the given coverage criterion. An algorithm car- dinality, select the test case that would mark the
based on a heuristic (re- ferred to as the HGS algorithm high- est number of unmarked requirements tied for
from here onwards) to select a representative set of test this car- dinality. If multiple such test cases are tied,
cases from a test suite, providing the same coverage as break the tie in favor of the test case that would mark
the entire test suite, was developed by Harrold, Gupta the high- est number of requirements with testing sets
and Soffa [7]. In this paper, we specifi- cally consider this of suc- cessively higher cardinalities; if the highest
algorithm for test suite minimization and modify it to cardinality is reached and some test cases are still
implement our approach for test suite reduction with tied, arbitrarily select a test case among those tied.
selective redundancy. We present the results of our ex- Mark the require- ments exercised by the selected
periments to evaluate the effectiveness of our approach in test. Remove test cases that become redundant as they
generating better quality (in terms of their fault detection no longer cover any of the unmarked requirements.
capability) reduced suites for the Siemens suite programs 4. Repeat the above step until all testing requirements
[2, 11, 13]. The main contributions of this paper are as fol- are marked.
lows:
We first illustrate how the HGS algorithm will generate a
• A novel yet simple approach to test suite reduction minimized test suite that covers all the branches of the ex-
with selective redundancy. ample program in Figure 1. Branch B 1 T is executed only
• Our experimental results clearly show the potential of by test case t1 . Also, branch B 4 F is executed only by test
our new technique in selecting a small set of case t2 . Therefore, test cases t1 and t2 are added to the
redundant test cases which have a high chance of min- imized suite and the branches covered by these test
detecting new faults. cases, B 1 T , B 1 F , B 2 T , B 2 F , B 3 T , B 3 F and B 4 F , are
marked. This makes test case t3 redundant since all the
The remainder of the paper is organized as follows. In the
branches covered by t3 are marked. Now only branch
next section, we motivate our approach with an example.
Our algorithm for test suite reduction with selective redun- B 4 T is un- marked. Therefore, either t4 or t5 can be
dancy is described in section 3. In section 4, we present an selected to cover B 4 T . Since the tie in this case is broken
experimental study comparing an existing test suite mini- arbitrarily, let t4 be selected for adding to the minimized
mization technique with our modified version that takes re- suite. Thus, the minimized branch coverage suite
dundancy into account. In section 5, we discuss the related generated by the HGS al- gorithm for this example is {t1 ,
work. We present the conclusions and our future work in t2 , t4 }. Now, test case t5 is identified as redundant and
section 6. the algorithm terminates since all the branches are
marked. Note that unselected test case t3 - identified as
2 A Motivational Example redundant for branch coverage - exposes a divide-by-zero
We now present a simple example program to motivate error in this example.
our idea of selectively keeping redundant test cases in a Now we illustrate our approach for generating a
reduced test suite generated by a test suite minimization reduced branch coverage adequate test suite by selectively
algorithm. The example program and a corresponding keeping some redundant test cases in the reduced suite.
branch coverage adequate test suite T with some Let us col- lect the coverage information for a secondary
redundant test cases with respect to branch coverage are criterion, such as the all def-use pairs criterion, for all the
shown in Figure 1. test cases in the test suite T for the example program in
The branches covered by each test case are marked with Figure 1. This in- formation is shown in Table 2. Our
an X in the respective columns in Table 1. Since our im- approach is to mod- ify the step that identifies redundant
plementation of our approach to test suite reduction with test cases in the test suite minimization algorithm.
selective redundancy is based on the HGS test suite mini- Specifically, when the HGS algorithm identifies a test
mization algorithm [7], we next briefly present the steps of case as redundant since all the branches covered by this
the HGS algorithm. test case have been marked, we check if this test case is
1. Initially, all requirements are unmarked. also redundant with respect to the secondary criterion. If
this is the case, we identify the test case as redundant.
2. For each requirement that is exercised by only one Otherwise, we add the test case to the reduced test suite.
test case each, add each of these test cases to the
mini-
 In this example, after t1 and t2 are added to the x(4, 6), x(4, 8) and d(1, B4 ) which are respectively exe-
reduced suite by the HGS algorithm, t3 is identified as cuted by 2, 2 and 3 test cases. In the next step, we consider
redundant with respect to branch coverage since all the the requirements x(4, 6) and x(4, 8) since each of these is
branches cov- ered by t3 are already covered by t1 and t2 executed by test sets of cardinality 2. We now select test t4
. However, we now check if t3 is also redundant with since it executes both x(4, 6) and x(4, 8). At this point all
respect to the sec- ondary criterion. In this case we find the secondary requirements are marked and the HGS algo-
that t3 covers the def-use pair x(4, 6) that is not covered rithm terminates with the minimized test suite {t1 , t4 }.
by either t1 or t2 . Therefore, we do not identify t3 as Note that this minimized test suite is not branch cover-
redundant and we add it to the reduced test suite. Thus, in age adequate since it does not cover the branch B2F . Nor
our approach the reduced test suite at this point contains
does it expose the divide-by-zero error at line 13. This ex-
t1 , t2 , and t3 . Now, either
2
one of t4 or t5 can be chosen next to cover the branch B4T ample points out that some branches such as B F that do
.
Let t4 be added to the reduced test suite. Thus, the require- not define or use a variable may not be covered if the min-
ment B4T also gets marked. At this point the test case t5 imized test suite with respect to the secondary criterion is
becomes redundant with respect to branch coverage as generated. Note that if we applied the HGS algorithm to
well generate a minimized suite without redundancy for both
as with respect to the coverage of the secondary criterion. the branch coverage and the coverage of the secondary
Therefore, the reduced test suite generated by our crite- rion simultaneously, then the same minimized suite
approach for this example is {t1 , t2 , t3 , t4 }. Note that {t1 , t2 , t4 } as generated in minimizing with respect to
this reduced test suite will expose the divide-by-zero error the branch coverage would be generated. In this case
at line 13. again, the divide- by-zero error at line 13 would be missed.
1: read(a,b,c,d); Therefore, the above example suggests that our
B1 : if ( a > 0 approach to test suite reduction with retaining selective
) redundancy in the reduced test suite may be preferable to
2: x = 2; A Branch Coverage adequate Suite T either of the non-redundancy minimization approaches.
3: else
4: x = 5; t1 : (a = 1, b = 1, c = -1, d = 0) The above ex- ample also provides insight into why this is
5: endif t2 : (a = -1, b = -1, c = 1, d = so. The def-use pair x(4, 6) is exercised by both t3 and t4 .
-1) The test case t3 exercises a combination of branch
B2 : if ( b > 0) t3 : (a = -1, b = 1, c = -1, d =
0) outcomes not executed by the other test cases and this
6: y = 1 + x; t4 : (a = -1, b = 1, c = 1, d = combination of branch out- comes exposes the divide-by-
1) zero error. However, in both of the above test suite
7: endif t5 : (a = -1, b = -1, c = 1, d = minimization schemes without redun- dancy, t3 becomes
1)
B3 : if ( c > redundant due to the other test cases that are added to the
0) minimized test suite early on in the mini- mization
B4 : if ( d > 0) algorithm. However, in our approach as soon as a test case
8: output(x); becomes redundant according to branch coverage, we add
9: else
10: output(10); it to the reduced suite if it adds new def-use pair coverage.
11: endif Therefore, it allows t3 to be added to the reduced
12: else suite before t4 is added to the test
13: output(1/(y-6)); suite.
14: endif

Figure 1. An example program with a branch

coverage adequate test suite T .
Test: B1T B1F BT2 B2F BT
3 B3F BT
4 B4F Thus, while our reduction with redundancy approach
Case
achieves slightly less suite size reduction, it is also likely
t1 : X X X
t2 : X X X X to retain test cases that execute different combinations of
t3 : X X X branch outcomes than those covered by the test cases al-
t4 : X X X X ready in the minimized suite, even though these test cases
t5 : X X X X have become redundant with respect to branch coverage.
Table 1. Branch coverage information for Thus, we see that there is something significant that may
test cases in T . be gained by approaching the test suite reduction problem
with the goal of adding some, rather than simply removing
For comparison with our approach explained above, let us
all, redundancy.
apply the HGS algorithm directly to Table 2 to compute
a minimized suite with respect to the secondary criterion 3 Test Suite Reduction With Selective Re-
without retaining redundancy. Test case t1 will be added
to the minimized suite since it covers the def-use pair x(2,
dundancy
6) that is executed only by t1 . Since t1 also covers y(6, Our proposed approach to test suite reduction is based on
13), a(1, B1 ), b(1, B2 ) and c(1, B3 ), these def-use the following key observation. Test suite minimization
pairs get marked. Now only 3 def-use pairs are tech- niques attempt to throw away test cases that are
unmarked, namely redun-
test case x(2,6) x(4,6) x(4,8) y(6,13) a(1, B1 ) b(1, B2 ) c(1, B3 ) d(1, B4 )
t1 : X X X X X
t2 : X X X X
t3 : X X X X X
t4 : X X X X X X
t5 : X X X X X

Table 2. Definition-use pair coverage information for test cases in T .

dant with respect to the coverage criterion for minimiza- requirement ri . Similarly, T ′ , T ′ , ..., are the testing sets
T′ 1 2 m
tion. However, in the absence of an ideal coverage crite- corresponding to secondary requirements such that T ′
rion, throwing away test cases can result in significant loss con- i
of fault detection capability [14]. Therefore, we believe tains the set of test cases that cover the secondary require-
that the test suite reduction problem should be viewed ment ri ′ . Now we describe the steps in the main
from the perspective of keeping redundant test cases that algorithm in Figure 3.
may exer- cise different situations in program execution
even though they are redundant with respect to the Step 1: Initialization. This step simply initializes the vari-
coverage criterion for test suite minimization. For making ables and data structures that will be maintained
a distinction between the primary coverage criterion used throughout the execution of the algorithm. After
for test suite reduction and additional requirements whose initialization, the main program loop begins which
coverage determines if a redundant test case should be attempts to select test cases that cover the primary
added to the reduced suite, we respectively refer to them as requirements that are currently uncovered by the reduced
primary and secondary criteria. Our approach is very suite (initially empty). The uncovered pri- mary
general and even some requirements derived from black- requirements are considered in increasing order of as-
box testing could be used as secondary requirements in sociated testing set cardinality.
conjunction with the statement or branch coverage criteria
that may be used as a primary criterion in this approach. Step 2: Select the Next Test Case According to the Pri-
We developed a specific implementation of our test mary Requirement. The algorithm first collects together
suite reduction with redundancy algorithm by adding a all the test cases comprising the testing sets of the current
new step to the HGS heuristic algorithm [7]. Instead of cardinality that are associated with uncovered primary re-
throwing away test cases that are redundant with respect quirements. This is the pool from which the next selected
to the pri- mary requirement coverage criterion for test test case (with respect to the primary requirements) will be
suite mini- mization in the original HGS algorithm, our selected. The algorithm next decides which of the tests in
new step exam- ines the redundant test cases with respect the pool to select by giving preference to the test case that
to the coverage of some additional secondary requirements covers the most uncovered requirements whose testing sets
and uses this infor- mation to decide whether to add the are of the current cardinality. In the event of a tie, the al-
test case to the reduced suite. Figures 2, 3 and 4 show our gorithm recursively gives preference to the test case
implementation of our approach based on the HGS test among the tied elements that covers the most uncovered
suite minimization algo- rithm. require- ments whose testing sets are of successively
higher cardi- nalities. If the cardinality reaches the
Set of primary testing requirements: r1 , r2 , ..., rn maximum cardinality and there are still ties, an arbitrary
. Set of secondary requirements: r ′ , r ′ , ..., r ′ . test case is selected from among the ties. The selected test
case is then added to the reduced suite.
1 2 m
Test cases in unreduced test suite: t1 , t2 , ..., tnt .
Step 3: Mark Newly-Covered Requirements and Update
Input: T1 , T2 , ..., Tn : test sets for r1 , r2 , ..., rn Coverage Information. At this point, we have added a
respectively. new test case to the reduced suite. This test case covers
T1 , T2 , ..., Tm : test sets for r1 , r2 , ..., rm
respectively.
′ ′ ′ ′ ′ ′ certain primary requirements, so the algorithm updates its
Output: RS: a reduced subset of t1 , t2 , ..., tnt
data structures to reflect the current primary coverage
Figure 2. Input/output for our algorithm.
infor- mation of the reduced suite. Additionally, if any test
The input and output of our algorithm are shown above in case is discovered to become redundant with respect to the
Figure 2. The main algorithm for test suite reduction with primary requirements in this step, then that test case is
selective redundancy is shown in Figure 3, and Figure 4 added to a set of currently-redundant test cases, which will
shows a function SelectTests that is used by the main al- later be exam- ined and from which redundant test cases
gorithm. As shown in Figure 2, our algorithm takes as may possibly be selected for inclusion in the reduced suite.
input two collections of associated testing sets. T1 , T2 , ..., Similarly for the secondary requirements, the algorithm
Tn are the testing sets corresponding to primary needs to update its data structures to reflect the current
requirements such that Ti contains the set of test cases secondary coverage in- formation of the reduced suite.
that cover the primary
Function ReduceWithSelRed(T1 ... Tn , T ′ ′ Function SelectTest(size, list, maxC ard)
 1 ... Tm
Step1: Unmark all ri and ri ) for each test case t in list do
′ count[t] := number of unmarked Ti ’s of
redundant:= {};
maxC ard := maximum cardinality of all Ti ’s; cardinality size containing t;
curC ard := 0; testList := test cases t in list s.t. count[t] is maximum.
for each test case t do if the cardinality of testList == 1 then
numU nmarked[t] := number of Ti ’s containing return the test case in testList;
t;
numU nmarked ′ [t] := number of T′i ’s containing t; else if size == maxC ard then
endfor return any test case in testList;
Step2: loop else
return SelectTest(size+1, testList, maxC ard);
curC ard := curC ard + 1;
while there is a Ti of curC ard s.t. ri is unmarked do endif
list := all tests in Ti ’s of curC ard s.t. ri is end SelectTest
unmarked; nextT est := SelectTest(curC ard, list, Figure 4. A function to select the next test
maxC ard); case.
RS := RS ∪ {nextT est};
mayReduce := FALSE;
Step3: for each Ti containing nextT est s.t. ri is unmarked do Step 4: Select Redundant Test Cases. This step is where
Mark ri . redundancy may be added to the reduced suite. For each
for each test case t in Ti do test case currently known to be redundant with respect to
numU nmarked[t] := numU nmarked[t] - 1; the primary criterion, the number of additional secondary
if numU nmarked[t] == 0 AND t ∈/ RS then requirements that each test case could add to the coverage
redundant := redundant ∪ {t}; of the reduced suite is computed. If some redundant test
endfor case adds to the cumulative secondary requirement cover-
if the cardinality of Ti == maxC ard then age of the reduced suite, then the test case adding the most
mayReduce := TRUE; secondary requirement coverage is selected (ties are
endfor broken
for each T ′ containing nextT est s.t. r ′ is unmarked
do i i
Mark r ′i . arbitrarily). The additional secondary requirement coverage
for each test case t in Ti ′ do of the remaining redundant test cases is recomputed, and
numU nmarked ′[t] := numU nmarked′ [t] - 1; this
re- process repeats until either (1) we’ve selected all the
endfor dundant test cases, or (2) no redundant test case adds to the
Step 4: initialize count[t] := 0 for all test cases t. cumulative secondary coverage. At this point, the
for each test case t in redundant do algorithm has completed processing the current set of
count[t] := numU nmarked′ [t];
redundant test cases. The main algorithm loop iterates
while there is a t in redundant s.t. count[t] > 0 do
toAdd := any t in redundant with max. count[t];
again (back to Step
RS := RS ∪ {toAdd}; 2) until all primary requirements are covered by the
for each T ′ containing toAdd s.t. r ′ is unmarked reduced suite.
do
i
Mark r ′i .
i 4 Experimental Study
for each test case t in Ti ′ do
′ 4.1 Subject Programs, Faulty Versions, and Test
numU nmarked [t] := numU nmarked′ [t] - 1; Case Pools
endfor
initialize count[t] := 0 for all test cases t. We followed an experimental set up similar to that used
redundant := redundant - {toAdd}; by Rothermel et. al [14]. We used the Siemens programs
for each test case t in redundant do described in Table 3 as the subject programs. All
count[t] := numU nmarked′ [t]; programs, faulty versions, and test pools used in our
endwhile experiments were assembled [2, 11, 13] by researchers
redundant := {}; from Siemens Cor- poration. We obtained these
if mayReduce then programs, their faulty ver- sions and the associated test
maxC ard := maximum cardinality among all Ti
pools from [10]. We exam- ined the types of errors
such that ri is unmarked;
introduced in the faulty versions of each subject program
endwhile
and identified six distinct categories of seeded errors: (1)
until curC ard = maxC
ard; changing the operator in an expression, (2) changing an
end ReduceWithSelRed operand in an expression, (3) changing the value of a
constant, (4) removing code, (5) adding code, and (6)
Figure 3. Algorithm for reduction with selec- changing the logical behavior of the code (usually
tive redundancy. involving a few of the other categories of error types si-
multaneously in one faulty version). Thus, the faulty ver-
sions used in our experiments cover a wide variety of fault technique in Java. We conducted the following experiment
types. To obtain edge-coverage adequate test suites for using the 1000 branch coverage adequate test suites gen-
each erated for each of the 6 size ranges described above. We
minimized each of the above branch coverage adequate test
Name Lines Version Description
of Code Count
suites by applying the original HGS algorithm for remov-
tcas 138 41 altitude separation ing the test cases redundant with respect to branch cover-
totinfo 346 23 info accumulator age. We also reduced the above branch coverage adequate
schedule 299 9 priority scheduler suites using our technique by adding branch coverage re-
schedule2 297 10 priority scheduler
printtokens 402 7 lexical analyzer
dundant test cases to the reduced suites if they contributed
printtokens2 483 10 lexical analyzer additional def-use pair coverage. The results of our experi-
replace 516 32 pattern substitutor ments with the above techniques are respectively shown in
the columns labeled “HGSBr” (for “branch minimization”)
Table 3. Siemens suite subject programs. and “RSR” (for “reduction with selective redundancy”) in
Table 4. The table shows the results for each suite size
program, we randomly selected some number of tests
range for each subject program: average original suite size
cases from the pool to add to the suite, then added any
(|T|), average number of faults detected by original suite (|
additional test cases, so long as they increased the
F|), average reduced suite size (|Tmin|), average number
cumulative edge coverage, until 100% edge-coverage was
of faults detected by reduced suite (|Fmin|), average per-
obtained. Similar to the experimental set up in [14], the
centage suite size reduction and average percentage fault
random number of test cases we initially added to each
detection loss for each of the above techniques. The results
suite varied over sizes ranging from 0 to 0.5 times the
for the printtokens and printtokens2
number of lines of code in the program. We constructed
programs are respectively shown in the rows labeled
1000 such highly redun- dant branch coverage adequate
printtok and printtok2. The values reported in the
test suites for each program. In addition, for each subject
program, we also created four more collections of 1000 table are the av- erages computed across all 1000 suites for
suites each, where each collection had suite sizes ranging each given suite size range for each subject program. For
from 0 to 0.4, 0 to 0.3, 0 to 0.2, and 0 to 0.1 times the comparison with the above two techniques, we also
number of lines of code. Finally, we created one more set applied the original HGS algorithm to minimize the above
branch coverage adequate suites with respect to their def-
of 1000 suites where we simply started with 0 test cases
use coverage. The results of this experiment are shown in
and then added cases as necessary (so long as each
the columns labeled “HGSdu” (for “def-use
increased the cumulative branch coverage) until 100%
minimization”) in Table 4.
cov- erage was obtained. Altogether, therefore, we created
6000 branch coverage adequate test suites for each Further, to show that our new RSR technique selects the
program com- prising 6 different size ranges additional redundant test cases that are effective at
corresponding to six rows for each program shown in detecting new faults, we conducted the following
Table 4. experiment: min- imize each suite as done in HGSBr, with
For experiments with our new reduction technique, for one difference: when a minimized suite is computed by
each test case we also needed information about the sec- the HGSBr tech- nique, we then check whether the
ondary requirements covered by the test case. We chose to corresponding reduced suite computed by RSR is larger or
use all-uses coverage information for each test case com- not. If so, we randomly add additional tests to the HGSBr-
puted by the ATAC tool [9] as our secondary criterion. minimized suite until the size matches that of the
Thus, for each test case, we recorded all the def-use pairs corresponding RSR-reduced suite. Thus, this experiment
that were covered by the test case (identified as being computes minimized suites of the same sizes as for
either computation uses or predicate uses by ATAC). Our technique RSR, but the additional tests selected here are
motiva- tion for choosing the def-use pair coverage as our selected randomly, rather than by anal- ysis of the
secondary criterion is that in general def-use coverage is a secondary coverage information as is done by RSR. These
stronger cri- terion than the branch coverage. Therefore, a results are shown for the suites in suite size range 0-0.5
test case that is redundant with respect to branch for each program in Table 5. To analyze our
1
coverage may not be
redundant with respect to def-use coverage. However, if a
weaker criterion such as the statement coverage is selected results, we present the boxplots in Figures 5 and 6. The
as the secondary criterion, a test case that is redundant
with respect to branch coverage will also be redundant 1
The height of each box in a box plot represents the range of y-
with re- spect to statement coverage. However, as values for the middle 50% of the values. The horizontal line within
each box represents the median value. The bottom of each box represents
mentioned before any other criterion that is not subsumed the lower quartile, and the top of each box represents the upper quartile.
by the primary cri- terion can also be used as a secondary The vertical line stretching below each box ends at the minimum value,
criterion. and represents the range of the lowest 25% of the values. The
We implemented both the original HGS algorithm and vertical line stretching above each box ends at the maximum value, and
represents the range of the highest 25% of the values. The average value
our test suite reduction with selective redundancy (RSR) is depicted by a small x.
 Program & |Tmin||
Fmin|
Reduction
% Size
% Fault
4.2 Analysis of
Loss
Results
Suite Size |T| |F|
Range HGSBr RSR HGSdu HGSB Reduction in Size of Branch Coverage
tcas 0 5.71 7.47 5.00 5.16 5.02 6.78 Adequate Test Suites: We observe from Table 4
tcas 0-0.1 9.56 9.15 5.00 6.20 5.68 6.84 that the average sizes of reduced test suites with
tcas 0-0.2 15.20 11.73 5.00 6.94 6.08 6.73
tcas 0-0.3 21.39 14.02 5.00 7.32 6.27 6.85 redundancy generated by RSR were always slightly
tcas 0-0.4 29.07 16.29 5.00 7.71 6.48 6.80 higher than the average sizes of minimized suites
tcas 0-0.5 35.63 17.76 5.00 7.91 6.56 6.67
printtok2 0-0.5 121.73 8.60 5.49 13.51 9.88 7.13 generated with HGSdu, which in turn were slightly
higher than the sizes of minimized suites generated
with HGSBr. These results are as expected. Neither
boxplots give a statistical view of the data HGSdu nor HGSBr attempt to retain some test cases
presented in the Table 4. Figure 5 shows the that may be redun- dant with respect to branch
percentage suite size reduc- tion and coverage or def-use coverage. However, RSR
percentage fault detection loss of the RSR and selectively adds those test cases that provide
HGSBr-minimized suites for suite size range 0- additional def-use coverage at the time they become
0.5. Fig- ure 6 shows the additional-faults-to- redun- dant with respect to branch coverage.
additional-test ratio val- ues for those suites in Therefore, RSR reduced suites have their test
suite size range 0-0.5 where the RSR- reduced cases se- lected in a different order than what is
suites were larger than the corresponding achieved by HGSdu. Therefore, it is expected that
HGSBr- minimized suites. This ratio is a the sizes of reduced test suites generated by RSR
measure of, for each ad- ditional test case in would be larger than those generated by HGSBr and
the RSR-reduced suite over the cor- responding HGSdu. The white boxes in Figure 5 also show
HGSBr-minimized suite, the number of addi-
tional faults detected by the RSR-reduced suite. Program |Fmin| % Fault Loss tcas 0-
A value of 0.5 8.45 46.55 totinfo 0-
1, for instance, would mean that for each 0.5 11.96 36.32 schedule
0-0.5 3.26 44.60 schedule2
additional test in 0-0.5 2.15 49.02
the RSR-reduced suite, 1 more fault is printtokens 0-0.5 2.94 35.12
detected. A nega- tive value may occur if the printtokens2 0-0.5 7.58 11.62 replace 0-
0.5 12.13 41.66
RSR-reduced suite is larger but detects fewer
RSR vs HGSBr: Additional-Faults-to-Additional-Tests Ratio
faults than its HGSBr-minimized counterpart. 10

The ratio is computed as the number of 8

additional faults de- tected by the RSR-reduced 6

suite, divided by the number of additional tests

in the RSR-reduced suite.
4

2
 0

-6

-8

that while RSR generally achieves less size reduction than -10
tcas totinfo schedule schedule2 printtokens printtokens2 replace

HGSBr, both RSR and HGSBr still generally achieve very Subject Program

high levels of suite size reduction.

 20

generally achieves the least suite size reduction with the possible points of discussion regarding our approach.
benefit of yielding the least fault detection loss. HGSdu “Fault detection effectiveness loss is still very large
achieves a middle-ground between RSR and HGSBr. Con- across all reduction techniques, even in the new
sidering that even RSR is still able to achieve relatively approach
high suite size reduction, the benefit of RSR in retaining - the technique of test suite reduction itself is a lost
more fault detection effectiveness in our experiments is cause.”
evident. Figure 6 shows the benefit of RSR in selecting There are many factors at work which influence the fault
additional test cases that are likely to expose new faults. detection effectiveness loss of suites. For instance, the
From the fig- ure, notice that for every subject program, test cases used in our experiments were selected from
the average ratio value is above 0. For tcas, totinfo, pools as- sembled by Siemens researchers, and the test
printtokens2, cases were generated with respect to various kinds of
Fault Detection Loss of Reduced Test Suites: We black-box and white-box approaches. Therefore, many of
ob- serve from the Table 4 that there is a strong the test cases in our suites are intentionally meant to test
tendency for RSR reduced suites to detect more entities within the subject programs that we do not know,
faults than HGSBr and HGSdu-minimized suites. nor that we have ac- counted for during reduction.
This is expected since both RSR and HGSdu- Therefore, any such test cases could be exercising
reduced suites retain the same all-uses cover- age as something special about the subject pro- gram that we do
their non-reduced counterparts, but RSR reduced not realize (such as special boundary con- ditions or
suites contain some redundancy with respect to test combinations of input values), and thus throwing them
cases that provide additional def-use coverage by away could result in fault detection loss. However, it is
exercising al- ready covered branches in a different quite remarkable that for all the techniques discussed in
order. From our ex- periments it appears that this this paper, much higher percentage suite size reduction is
form of redundancy is effec- tive at retaining test achieved as compared to the corresponding percentage
cases that are likely to expose faults. The gray boxes fault detection loss.
in Figure 5 also show that the fault detec- tion losses mary criterion but also with respect to the secondary
experienced by RSR are considerably less than that crite- rion because of the order in which they were added
experienced by HGSBr, and overall, the fault loss to the reduced suite. The fundamental difference is that
val- ues for both RSR and HGSBr are considerably our new algorithm specifically seeks to include
less than the corresponding suite size reduction redundancy in the reduced suites while the minimization
values. techniques seek to eliminate as much redundancy as
Test Suite Reduction vs. Fault Detection Loss: HGSBr possible.
generally achieves the most suite size reduction at the ex-
pense of yielding the most fault detection loss, while RSR 6 Conclusions and Future
the median value is at 0 with a lower quartile also at 0, in- Work
dicating that over half of the ratio values are greater than
or equal to 0, the average value is more than 0. For tcas, We have presented a new approach to test suite
reduction that attempts to selectively keep redundant test
the upper quartile is over 1 (more than 25% of suites have
cases with the goal of decreasing the loss of fault
ratio value greater than 1), and for totinfo, the upper
detection effective- ness due to reduction in suite size. Our
quartile is over 2 (more than 25% of suites have ratio
approach is general and can be integrated into any existing
value greater than 2!). For replace, even the lower
test suite minimiza- tion algorithm. In our experimental
quartile is greater than 0 (over 75% of suites have a
study, our approach consistently performed better than
positive ratio value).
test suite minimization without redundancy by generating
It is reasonable to ask whether or not the increased fault
reduced test suites with less fault detection loss at the
detection retention of RSR is due merely to the fact that
expense of a small increase in the size of the reduced
the RSR-reduced suites are larger than the other
suite. In the near future, we plan to evaluate the
minimized suites. It turns out this is not the case. As
effectiveness of our technique for test suite reduction with
indicated by the results in Table 5 compared to the RSR
selective redundancy for a combination of white-box and
results in Table 4, in all cases, the average number of
black-box coverage requirements.
faults detected by the randomly-added suites is less than
the average number of faults detected by the
corresponding RSR-reduced suites. Accordingly, the
average percentage fault detection loss of the randomly-
added suites is always more than the average fault
detection loss of the RSR-reduced suites. Our exper-
imental results clearly show the potential of our new tech-
nique in selecting a small set of redundant test cases which
have a high chance of detecting new faults.
We would now like to elaborate on the following