=Paper=
{{Paper
|id=None
|storemode=property
|title=Test Case Reduction Methods by Using CBR
|pdfUrl=https://ceur-ws.org/Vol-646/EMDT2010paper4.pdf
|volume=Vol-646
}}
==Test Case Reduction Methods by Using CBR==
https://ceur-ws.org/Vol-646/EMDT2010paper4.pdf
TEST CASE REDUCTION METHODS BY USING CBR
Siripong Roongruangsuwan and Jirapun Daengdej
Autonomous System Research Laboratory
Faculty of Science and Technology
Assumption University, Thailand
p4919742@au.edu, jirapun@scitech.au.edu
ABSTRACT Many researchers [10], [11], [12], [13], [14], [15],
[23], [24], [25], [26], [29], [36], [37], [39] have proven
It has been proven that software testing usually that these test case reduction methods can reserve the
consumes over 50% of the costs associated with the fault detection capability. There are many outstanding
development of commercial software systems. research issues in this area. In this paper, the research
Particularly, regression testing activities has been issues are: redundancy test cases are still remained, an
shown to be a critically important phase of software uncontrollable growth of test cases and existing
reduction methods consume a great deal of time and
testing. Many reduction techniques have been
cost during a reduction process. The literature review
proposed to reduce costs. Unfortunately, the cost is
[16] shows that there are many techniques to resolve
usually over budget and those methods are failed to those three issues. One of effective approaches is to
reasonably control costs. The primarily outstanding apply the concept of artificial intelligent. There are
issue is non-effective methods to remove redundancy many artificial intelligent concepts, such as neutral
tests while a bigger size of tests and a significant network, fuzzy logic, learning algorithms and case-
amount of time are still remaining. To resolve the based reasoning (CBR). CBR is one of the most
issue, this paper proposes an artificial intelligent popular and actively researched areas in the past. The
concept of case-based reasoning (CBR). CBR has an researches [4], [8], [16], [26] show that CBR has
uncontrollable costs issue as same as testing. There identical problems as same as software testing topic. In
are many effective algorithms researched over a long software testing field, particularly during regression
period of time. This study introduces three methods testing activities, the key research issues are: (a) too
combined between CBR’s deletion algorithm and many redundancy test cases after reduction process (b)
testing activities. Those methods aim to minimize size a decrease of test cases’ ability to reveal faults and (c)
of tests and time, while preserving fault detection. uncontrollable grow of test cases. Meanwhile, the key
research issues in CBR field are: (a) there are too
Index Terms - test case reduction, test reduction, many redundancy cases in the CBR system (b) a size
test reduction CBR, CBR for testing and test of CBR system is continuously growing all the time
and (c) existing CBR deletion algorithms take longer
reduction techniques
time to remove all redundancy cases in the CBR
system. Those issues in CBR field can be elaborated as
1. INTRODUCTION follows: Fundamentally, there are four steps in the
CBR system, which are: retrieve, reuse, revise and
Software Testing is an empirical investigation retain. These steps can lead to a serious problem of
conducted to provide stakeholders with information uncontrollably growing cases in the system. However,
about the quality of the product or service under test the study shows that there are many proposed
[7], with respect to the context in which it is intended techniques in order to control a number of cases in the
to operate. Software Testing also provides an CBR system, such as add algorithms, deletion
objective, independent view of the software to allow algorithms and maintenance approaches. CBR have
the business to appreciate and understand the risks of been investigated by CBR researchers in order to
implementation of the software. Test techniques ensure that only small amounts of efficient cases are
include the process of executing a program or stored in the case base. The previous work [28] shows
application with the intent of finding software bugs. It that deletion algorithms are the most popular and
can also be stated as the process of validating and effective approaches to maintain a size of the CBR
verifying that software meets the business and system. There are many researchers have proposed
technical requirements that guided its design and several deletion algorithms [4], [8], [31], such as
development, so that it works as expected. Software random method, utility approach and footprint
Testing can be implemented at any time in the algorithm. These algorithms aim to: (a) remove all
development process; however, the most test effort is redundancy or unnecessary cases (b) minimize size of
employed after the requirements have been defined system and reduction time and (c) preserve the ability
and coding process has been completed. of solving problems. Nevertheless, each technique has
strength and weakness. Some methods are suitable for
removing cases. Some methods are perfectly suitable techniques have many benefits, particularly during the
for reducing time. Some may be used for reserving the regression testing phase, and most of reduction
problem solving capability. Eventually, the previous techniques can maintain an acceptable rate of fault
work [28] discovered several effective methods (e.g. detection. The advantages of these techniques are: (a)
confidential case filtering method, coverage value to spend less time in executing test cases, particularly
algorithm and confidential coverage approach) to during the regression testing phase (b) to significantly
remove those cases, minimize size of CBR and reduce reduce time and cost of manually comparing test
amount of time, while preserving the ability of CBR
results and (c) to effectively manage the test data
system’s problem solving skill. Therefore, this paper
associated with test cases. This study proposes a new
applies those effective deletion techniques to resolve
the problems of software testing. In the light of “2C” classification of test case reduction techniques,
software testing, the proposed techniques focus on classified based on their characteristics, as follows:
how to maintain the test case or test data while the (a) coverage-based techniques and (b) concept
ability to reveal faults is still preserved. It is assumed analysis-based techniques.
that test cases or test data in this paper are treated as
cases in the CBR system. Also, there is an assumption 2.2. Case-Based Reasoning (CBR)
that a given set of test cases are generated by a path- Over the time, CBR is growing. When the
oriented test case generation technique. The path- uncontrollable case-based growth is occurred, the
oriented technique is widely used for a white-box performance of CBR is decreasing. Therefore, the
testing, which this paper does not address how to maintenance process is required in order to preserve
generate test cases with path-oriented methods. or improve the performance of the system. The
Section 2 discusses an overview of test case process of maintaining CBR is called CBM. David C.
reduction techniques and processes. Also, section 2 Wilson [8] presented the overall concepts of CBR and
discusses a concept of CBR. Section 3 provides a case based maintenance. This paper focused on the
definition of terminologies used in this paper. Section case based maintenance (CBM) approach in term of
4 lists the outstanding research issues motivated this the framework. In other words, this paper described
study. Section 5 proposes three new test case the type of data collection and how the case based
reduction methods. Section 6 describes an evaluation maintenance works. There were so many policies for
method and discusses a result. The last section CBM, for example, addition, deletion, and retain.
represents all source references used in this paper. “CBM was defined as the process of refining a CBR
system’s case-base to improve the system’s
2. LITERATURE REVIEW performance. It implements policies for revising the
organization or contents (representation, domain
This section describes an overview of test case content, accounting information, or implementation)
reduction techniques and the concept of CBR. The of the case-base in order to facilitate future reasoning
following describes those two areas in details. for a particular set of performance objectives.”
These studies [4], [5], [6], [8], [19], [20], [28]
reveal that several deletion algorithms have been
2.1. Test Case Reduction Techniques
proposed. For example, a random approach (RD),
This section discusses and organizes test case
utility deletion algorithm (UD), footprint deletion
reduction (or TCR) techniques researched in 1995-
algorithm (FD), footprint utility deletion algorithm
2006. This study shows that there are many
(FUD) and iterative case filtering algorithm (ICF).
researchers who proposed a method to reduce
RD is the simplest approach, which removes the
unnecessary test cases (also known as redundancy test
case randomly. UD deletes the case that has minimum
cases), like Offutt [5], Rothermel [12], McMaster [24]
utility value. Footprint algorithm uses the competence
and Sampth [27]. These techniques aim to remove and
model and removes the auxiliary case from the
minimize a size of test cases while maintaining the
system. FUD is a hybrid approach between Utility
ability to detect faults. The literature review [1], [10],
algorithm and Footprint algorithm, and is concerned
[11], [12], [13], [14], [15], [24], [25], [36], [37], [39]
with the competence model and the utility value.
shows that there are two types of reduction
Finally, ICF focuses on the case, which the
techniques, which are: (a) pre-process and (b) post-
reachability set is greater than the coverage set [19],
process. First, the pre-process is a process that
[28].
immediately reduces a size of test cases after
generating. Typically, it is occurred before regression
testing phase. Second, the post-process is a process 3. DEFINITION
that maintains and removes unnecessary test cases,
after running the first regression testing activities. This section describes a definition of terminologies.
Although these techniques can reduce the size of test Definition 1: Barry [4] defined the CBR, case base,
cases, but the ability to reveal faults seems slightly to auxiliary case and pivotal case as follows:
be dropped. However, Jefferson Offutt [5] and “Case-Based Reasoning is one of the Artificial
Rothermel [10], [11], [12], [13], [14], [15], [30], [31], Intelligence-based algorithms, which solve the
[33] has proven that these test case reduction problems by searching through the case storage for
the most similar cases. CBR has to store their solved while preserving the ability to defect faults. Last, this
cases back to their memory or storage in order to paper shows that uncontrollable grow of test cases can
learn from their experience.” be typically occurred during software testing process
“Case Base is a collection of cases in CBR, which and evolution. Even if there are many reduction
can be defined as the following: Given a case - base C methods proposed to control and limit growth of tests,
= {c1... cn}, for c ε C whereas C = CBR, c = case” unfortunately it appears that a number of test cases is
Definition 2: “Auxiliary Case is a case that does not still large. Obviously, the greater size of test cases
have a direct effect on the competence of a system takes longer time and cost to execute.
when it is deleted. The definition of auxiliary case can
be described as follows: 5. PROPOSED METHODS
Auxiliary cases do not affect competence at all. Their
deletion only reduces the efficiency of the system. A For evolving software, test cases are growing
case is an auxiliary case if the coverage it provides is dramatically. The more test cases software test
subsumed by the coverage of one of its reachable engineers have, the more time and cost software test
cases.” engineers consume. The literature review shows that
Definition 3: “Pivotal Case is the case that does regression testing activities consume a significant
have a direct effect on the competence of a system if it amount of time and cost. Although, a comprehensive
is deleted. set of regression selection techniques [10], [11], [12],
A case is a pivotal case if its deletion directly reduces [13] has been proposed to minimize time and cost,
the competence of a system (irrespective of the other there is an available room to minimize size of tests
cases in the case-base) [2], [3]. Using the above and clean up all unnecessary test cases. Thus,
estimates of coverage and reachability a case is removing all redundancy test cases is desirable. There
pivotal if it is reachable by no other case but itself.” are many approaches to reduce redundancy test cases
and applying an artificial intelligent concept in the
4. RESEARCH CHALLENGES test case reduction process is an innovated approach.
The literature review [16], [28] shows that there are
This section discusses the details of research issues many areas of artificial intelligent concept, such as
motivated this study. The literature review reveals artificial neutral network, fuzzy logic, learning
that [7], [22], [24], [25], [27], [38] those research algorithms and CBR concept. Also, it reveals that
issues are: (a) too many redundancy test cases after CBR has a same research issue as software testing
reduction process (b) a decrease of test cases’ ability has. The issue is that cases in the CBR system will be
to reveal faults and (c) uncontrollable grow of test consistency growing bigger and larger all the time.
cases. These research issues can be elaborated in There are four steps in CBR that can uncontrollably
details as follows: First, the literature review shows grow a size of the system: retrieve, reuse, revise and
that redundancy test cases are test cases tested by retain. Therefore, many CBR papers aim to reduce all
multiple test cases. Many test cases that are designed redundancy cases, known as “deletion algorithms”.
to test the same things (e.g. same functions, same line The smaller size of CBR system is better and
of code or same requirements) are duplicated. Those desirable. Due to the fact that CBR has the same
duplicated tests are typically occurred during testing problem as software testing and this paper focuses on
activities, particularly during regression testing reduction methods, therefore, this paper proposes to
activities [7], [22], [24], [25], [27], [38]. Those apply CBR deletion algorithms to the test case
duplicated tests can be eventually removed in order to reduction techniques. This paper introduces three
minimize time and cost to execute tests. The study reduction methods that apply CBR deletion
shows that there are many proposed methods to delete algorithms: TCCF, TCIF and PCF methods. Those
those duplicated test cases such as McMaster's work techniques aim to reduce a number of test cases
[24] [25], Jeff's method [7] and Khan's approach [22]. generated by path-oriented test case generation
Also, the study shows that one of the most interesting technique. This technique is used for white-box
research issues is to minimize those duplicated tests testing only. However, the generation methods are out
and reduce cost of executing tests. Although there are of the scope of this paper.
many proposed methods to resolve that issue, that
issue is still remaining. Thus, it is a challenge for 5.1. Example of Test Cases
researchers to continuously improve the ability to Given a set of test cases generated, this study
remove duplicated tests. Second, test cases are discusses the use of a number of case maintenance
designed to reveal faults during software testing techniques, which have been investigated by CBR
phase. The empirical studies [10], [11], [12], [23], researchers in ensuring that only small amount of
[30], [31], [33], [39] describe that reducing test cases cases are stored in the case base, thereby reducing
may impact to the ability of detect faults. Many number of test cases should be used in software
reduction methods decrease a capability of testing and testing. Similar to what happen to software testing, a
reveal those faults. Therefore, one of outstanding number of CBR researchers have focused on finding
research challenges for researchers is to remove tests approaches especially for reducing cases in the CBR
systems’ storages. This paper proposes to use the path The procedures of this method can be described
coverage criteria in order to reduce redundancy test briefly in the following steps.
cases. This is because path coverage has a huge The first step is to determine a coverage set. From
benefit of required very thorough testing activities. figure 1, each coverage set can be identified as
The following describes in details of the above path follows:
coverage using in the software testing field. Let S = Coverage (1) = {TC1} Coverage (7) = {TC1, TC4, TC7,
{s1, s2, s3, s4, s5} to be a set of stage in the control Coverage (2) = {TC2} TC9, TC10, TC11}
flow graph. The control flow graph can be derived Coverage (3) = {TC3} Coverage (8) = {TC3, TC6, TC8,
from the source-code or program. It is a white-box Coverage (4) = {TC1, TC11, TC12, TC13}
TC4, TC9} Coverage (9) = {TC9}
testing. Thus, each state represents a block of code. Coverage (5) = {TC2, Coverage (10) = {TC9, TC10,
The techniques that aim to generate and derive test TC5, TC11} TC11}
cases from the control flow graph are well-known as Coverage (6) = {TC3, Coverage (11) = {TC11}
path-oriented test case generation techniques. These TC6, TC12} Coverage (12) = {TC12}
techniques are widely used to generate test cases. Coverage (13) = {TC11, TC12,
There are many research papers on this area. TC13}
However, the test case generation techniques are out
of scope in this paper. The second step is also to determine a reachability
set. The reachability set can be figured out from the
above coverage set, based on the given definition in
this paper. Therefore, the reachability set can be
identified as follows:
Reachability (TC1) = {1, 4, Reachability (TC7) = {7}
7} Reachability (TC8) = {8}
Reachability (TC2) = {2, 5} Reachability (TC9) = {4, 7,
Reachability (TC3) = {3, 6, 9, 10}
Figure 1 An Example of Control Flow Graph 8} Reachability (TC10) = {7,
Reachability (TC4) = {4, 7} 10}
From the above figure, this paper assumes that Reachability (TC5) = {5} Reachability (TC11) = {5, 7,
each state can reveal a fault. Thus, an ability to reveal Reachability (TC6) = {6, 8} 8, 10, 11, 13}
Reachability (TC12) = {6, 8,
faults of five states is equal to 5. Also, it is assumed
12, 13}
that every single transaction must be tested. This Reachability (TC13) = {8,
example is used in the rest of paper. 13}
Let TCn = {s1, s2, …,sn} where TC is a test case Next, the step is to define an auxiliary set. The
and sn is a stage or node in the path-oriented graph given definition of auxiliary set is to find a test case
that is used to be tested. From the above figure, a set that does not have a direct effect on the ability to
of test cases can be derived as follows: reveal faults when it is removed. From figure 1,
TC1 = {s1, s2} TC7 = {s1, s2, s3, s5} therefore, the auxiliary set can be identified as
TC2 = {s1, s3} TC8 = {s1, s4, s3, s5}
follows:
TC3 = {s1, s4} TC9 = {s2, s3}
TC4 = {s1, s2, s3} TC10 = {s2, s3, s5} Auxiliary set = {TC1, TC2, TC3, TC4, TC5, TC6, TC9,
TC5 = {s1, s3, s5} TC11 = {s3, s5} TC10, TC11, TC12, TC13}
TC6 = {s1, s4, s3} TC12 = {s4, s3} Afterward, the method computes a complexity
TC13 = {s4, s3, s5} value for all test cases in the above auxiliary set. From
The following describes the proposed methods figure 1 and test suites that contain 13 test cases, the
that apply the concept of CBR in details: average number of states is equal to 3. Therefore, the
complexity value for each test case can be computed
5.2. Test Case Complexity for Filtering (TCCF) as follows:
A complexity of test case is the significant criteria in Cplx(TC1) = Low, Cplx(TC2) = Low, Cplx(TC3) =
this proposed method [2], [19]. In this paper, the Low, Cplx(TC4) = Medium, Cplx(TC5) = Medium,
complexity of test case measures a number of states Cplx(TC6) = Medium, Cplx(TC9) = Low, Cplx(TC10) =
included in each test case. Medium, Cplx(TC11) = Low, Cplx(TC12) = Low and
Let Cplx(TC) = {High, Medium, Low} where Cplx(TC13) = Medium
Cplx is a complexity of test case, TC is a test case and Finally, the last step removes test cases with
the complexity value can be measured as: minimum of complexity value from the auxiliary set.
• High when a number of states are greater than an Thus, TC1, TC2, TC3, TC9, TC11 and TC12 are
average number of states in the test suite. removed.
• Medium when a number of states are equal to an
average number of states in test suites. 5.3. Test Case Impact for Filtering (TCIF)
• Low when a number of states are less than an The study [21] shows that software is error-ridden in
average number of states in the test suites. part because of its growing complexity. Software is
growing more complex every day. The size of
software products is no longer measured in thousands taking into account possible pitfalls in the structure
of lines of code, but it measures in millions. Software and logic. Functional testing examines what the
developers already spend approximately 80 percent of program accomplishes, without regard to how it
development costs [21] on identifying and correcting works internally. Structural testing is also called path
defects, and yet few products of any type other than testing since you choose test cases that cause paths to
software are shipped with such high levels of errors. be taken through the structure of the program. The
Other factors contributing to quality problems include advantage of path cover is that it takes responsible for
marketing strategies, limited liability by software all statements as well as branches across a method. It
vendors, and decreasing returns on testing and requires very thorough testing. This is an effective
debugging, according to the study. At the core of substitute of other coverage criteria. The path
these issues is difficulty in defining and measuring coverage is used as coverage value in this technique.
software quality. Due to the fact that defining and The Coverage value is combined into the addition
measuring a quality of software is important and policy for adding significant case [17]. Within the
difficult, the impact of inadequate testing must not be adding algorithm along with the coverage weight
ignorance. The impact of inadequate testing could be value stated in the review, the concept of deletion
lead to the problem of poor quality, expensive costs algorithm and the coverage have been proposed. The
and huge time-to-market. In conclusion, software coverage value can specify how many nodes that the
testing engineers require identifying the impact of test case can cover. In other words, the coverage value
each test case in order to acknowledge and understand is an indicator to measure that each test case covers
clearly the impact of ignoring some test cases. In this nodes. It means that the higher coverage value is, the
paper, an impact value is an impact of test cases in more nodes can be contained and covered in the test
term of the ability to detect faults if those test cases case. Let Cov(n) = value where Cov is a coverage
are removed and not be tested. value, value is a number of test cases in each coverage
Let Imp(TC) = {High, Medium, Low} where Imp group and n is a coverage relationship.
is an impact if a test case is removed, TC is a test case The procedure of this method can be elaborated
and the impact value can be measured as: briefly as the following steps. From figure 1, the first
• High when the test case has revealed at least one step is to identify a coverage set, which has been
fault for many times. already identified in the previous method. The next
• Medium when the test case has revealed faults for step is to calculate a coverage value. This paper
only one time. proposes to calculate a coverage value based on a
• Low when the test case has never revealed faults. number of test cases in each coverage group.
The procedure of this method is similar to the Therefore, the coverage value can be computed as
previous method. The only different is that this follows:
method aims to use an impact value instead of Cov(1) = 1, Cov(2) = 1, Cov(3) = 3, Cov(4) = 3,
complexity value. Therefore, the fire three steps are Cov(5) = 3, Cov(6) = 4, Cov(7) = 6, Cov(8) = 6,
to: identify coverage set, define reachability set and Cov(9) = 1, Cov(10) = 3, Cov(11) = 1, Cov(12) = 1
determine an auxiliary set. Afterward, the next step is and Cov(13) = 3.
to compute and assign an impact value. The method The last step removes all test cases with minimum
computes the impact value for all test cases in the coverage value, in the potential removal set.
above auxiliary set. From figure 1, the impact value Therefore, TC1, TC2, TC9, TC11 and TC12 are removed.
for each test case can be computed as follows:
Imp(TC1) = Low, Imp(TC2) = High, Imp(TC3) = 6. EVALUATION
Medium, Imp(TC4) = Low, Imp(TC5) = High,
Imp(TC6) = Medium, Imp(TC9) = Low, Imp(TC10) = This section describes an experiments design,
Low, Imp(TC11) = Low, Imp(TC12) = Low and measurement metrics and results. This paragraph
Imp(TC13) = Low designs an experiment used to evaluate and determine
Finally, the last step removes test cases with the best reduction methods. This paper proposes the
minimum of impact value from the auxiliary set. following three steps. First, the experiment proposes
Thus, TC1, TC4, TC7, TC9, TC10, TC11, TC12 and TC13 to randomly generate 2,000 test data used in the
are removed. telecommunication industry. In this experiment, the
test data is represented as test case. Second, the
5.4. Path Coverage for Filtering (PCF) Method experiment executes reduction methods with the
Code coverage analysis is a structural testing generated test cases and compares among the
technique (also known as white box testing). following reduction methods: RD, UD, FD, FUD, ICF
Structural testing compares test program behaviour and three proposed methods (e.g. TCCF, TCIF and
against the apparent intention of the source code. This PCF). This step randomly simulates defects for each
contrasts with functional testing (also referred to test case in order to determine an ability to reveal
black-box testing), which compares test program faults. Third, the experiment aims to run the above
behaviour against a requirements specification. methods for 10 times in order to calculate the average
Structural testing examines how the program works, value for each metric. The metrics used in this
experiment are described in details in next section. Table 2 Approach to Generate Random Test Case
Afterward, the experiment compares the values and Attribute Approach
evaluates a result by generating a comparison graph in Test Id Generate randomly from the following
order to determine the most recommended reduction combination: t + Sequence Number. For
approach. example, t1, t2, t3, …, tn.
The following table lists the description of each Name Random from the following values: iPhone,
BlackBerry, Nokia, LG, Sony and Samsung.
test data that need to be generated randomly.
ImpValue Set as a zero (0) at the beginning
wCoverag Set as a one (1) at the beginning
Table 1 An Example Form of Test Cases eValue
Attribu Description Data Type A set of There are two elements needed to be
te states randomly generated: (a) a number of states
Test Id A unique index to reference Numeric that needed to be tested by each test case and
test data. The value is a be generated between 1 and 100. (b) states
sequence number, starting at themselves that described as follows:
1. Generate randomly from the following
Full A first and last name who String combination: s + Sequence Number. For
Name own the mobile phone. example, s1, s2, s3, …, sn.
Name A mobile brand name. The String Cplx Random from the following values: 1-100
value is a range of iPhone, Impact Random from the following values: 1-100
BlackBerry, Nokia, LG, Sony Coverage Compute a number of states from “a set of
Ericsson and Samsung. states” field
Covera A value of Coverage set, Numeric
ge which is defined by the user.
Value
The paragraph lists the measurement metrics used
Impact An impact value of each case, Numeric in the experiment. The first measurement is a number
Value in this work. This can be of test cases. The large number of test cases consumes
matched to the impact value. time, effort and cost more than the smaller size of test
wCover The weight value for coverage Numeric cases. Many reduction or minimization approaches
ageVal set [1], [10], [11], [12], [13], [14], [15], [24], [25], [36],
ue [37], [39] have been proposed to minimize size of test
A set of A set of states that required to Array cases. This has proven that size is one of important
states be tested. State is directly metrics in software testing area. The second is an
derived from control flow ability to reveal faults. It aims to measure the
graph. The control flow graph
percentage of faults detection. One of the goals of test
is a result of path-oriented test
case generation techniques. case with a set of data is to find defects. Thus, this
Comple An indicator to represent a Numeric metric is important criteria to measure and determine
xity complexity of test case. The which reduction methods can preserve the high ability
complexity of test cases to reveal faults. The last measurement is a total of
represents how difficult to reduction time: It is the total number of times running
execute each test case. the reduction methods in the experiment. This metric
Impact An indicator to represent an Numeric is related to time used during execution time and
impact value in case that test maintenance time of test case reduction methods.
case is ignored. Therefore, less time is desirable. This paragraph
Covera An indicator to represent how Numeric
discusses an evaluation result of the above
ge many states each test case
cover. experiment. This section presents the reduction
Status An indicator to represent that Boolean methods results in term of: (a) a number of test cases
test case can reveal faults or (b) ability to reveal faults and (c) total reduction time.
not. The status can be only The comparative methods are: RD, UD, FD, FUD,
either pass or fail. If the status ICF, TCCF, TCIF and PCF. Additionally, this section
is fail, it mean that fault is shows a graph format. There are two dimensions in
detected. the following graph: (a) horizontal and (b) vertical
axis. The horizontal represents three measurements
The following table describes an approach to whereas the vertical axis represents the percentage
generate random data using the above attributes value.
respectively.
path coverage. The path coverage may be not an
effective coverage factor for a huge system that
contains million lines of code. This is because it
requires an exhaustive time and cost of identify
coverage from a huge amount of codes. Thus, one of
the future works is to apply other coverage factors for
those approaches. Finally, this paper recommends
researchers to improve the ability to reduce duplicated
or unnecessary test cases from multiple test suites,
enhance the capability to reduce test cases in the large
Figure 2 A Graph Comparison of Deletion Methods commercial system and develop a systematic
approach to identify an impact and complexity of
The above graph presents that both of FD and PCF tests.
minimize a number of test cases by far better than
other reductions methods, approximately over 15%. 8. REFERENCES
Meanwhile, both of them are the worst methods for
preserving an ability to reveal faults. FUD, TCCF and [1] A. Jefferson Offutt, Jie Pan and Jeffery M. Voas,
“Procedures for Reducing the Size of Coverage-based Test
TCIF are best top three methods to reserve a Sets”, 1995.
capability to detect faults. They are greater than other [2] Barry Smyth & Keane. “Remembering To Forget: A
methods over 22%. Unfortunately, they are also the Competence Preserving Deletion Policy for Case-Based
worst three methods that require a lot of time during a Reasoning Systems” In Proceedings of the 14th
reduction process. In the mean time, both of RD and International Joint Conference on Artificial Intelligence,
PCF take the least total reduction time among other 377-382. Morgan-Kaufman, 1995.
methods. The evaluation result suggests that FD and [3] Barry Smyth Ph.D. Thesis. “Case Based Design”
PCF is perfectly suitable for a scenario that does not Department of Computer Science, Trinity College, Dublin
directly concern about an ability to reveal faults and Ireland, 1996.
[4] Barry W. Boehm, “A Spiral Model of Software
total reduction time. Both of FD and PCF are two of Development and Enhancement”, TRW Defense Systems
the most excellent methods to minimize a number of Group, 1998.
test cases. Meanwhile, FUD, TCCF and TCIF are the [5] Boris Beizer, “Software Testing Techniques, Van
most recommended methods to delete tests while Nostrand Reinhold”, Inc, New York NY, 2nd edition. ISBN
preserving the ability to detect faults. In addition, both 0-442-20672-0, 1990.
of RD and PCF are excellent in case that total time is [6] Bo Qu, Changhai Nie, Baowen Xu and Xiaofang Zhang,
matter. “Test Case Prioritization for Black Box Testing”, 31st
Annual International Computer Software and Applications
Conference (COMPSAC 2007), 2007.
7. CONCLUSION
[7] Cem Kaner, “Exploratory Testing”, Florida Institute of
Technology, Quality Assurance Institute Worldwide Annual
This paper reveals that there are many research Software Testing Conference, Orlando, FL, 2006.
challenges and gaps in the test case reduction area. [8] David C. Wilson. Ph.D. Thesis “A Case-Based
Those challenges and gaps can give the research Maintenance: The husbandry of experiences.” Department
direction in this field. However, the research issues of Computer Science, Indiana University, 2001.
that motivated this study are: (a) too many [9] E. Lehmann and J. Wegener, “Test case design by
redundancy test cases after reduction process (b) a means of the CTE XL”, In Proc. of the 8th European
decrease of test cases’ ability to reveal faults and (c) International Conf. on Software Testing, Analysis &
Review (EuroSTAR 2000), 2000.
uncontrollable grow of test cases. This paper
[10] Gregg Rothermel, Roland H. Untch, Chengyun Chu
combines the concept of software testing and CBR. and Mary Jean Harrold, “Prioritizing Test Cases for
Those two concepts could be used together on Regression Testing”, IEEE Transactions on Software
practical software development scenarios. The Engineering, 2001.
proposed maintenance algorithms are significant [11] Gregg Rothermel, R. H. Untch, C. Chu, and M. J.
approaches for removing unnecessary test cases and Harrold, “Test case prioritization: An empirical study”, In
are used for controlling the growth of test cases. Proceedings of the IEEE International Conference on
Those approaches are aimed at maintaining the large Software Maintenance, pages 179-188, Oxford, England,
test cases by minimizing the time consumed by UK, 1999.
[12] Gregg Rothermel, Mary Jean Harrold, Jeffery Ostrin
execution & maintenance and reducing the size of the
and Christie Hong, “An Empirical Study of the Effects of
test cases along with preserving the ability to reveal Minimization on the Fault Detection Capabilities of Test
faults as much as possible. Also, the evaluation Suites”, In Proceedings of IEEE International Test
reveals that they have been achieved by removing a Conference on Software Maintenance (ITCSM'98),
number of test cases, minimizing time for executing Washington D.C., pp. 34-43, 1998.
& maintenance and preserving the fault-detection [13] Gregg Rothermel, Mary Jean Harrold, Jeffery von
ability with sample of 2,000 test cases. However, the Ronne and Christie Hong, “Empirical Studies of Test-Suite
primarily limitation of those approaches is about the
Reduction”, In Journal of Software Testing, Verification, Proceedings of the International Symposium on Software
and Reliability, Vol. 12, No. 4, 2002. Testing and Analysis, pages 102-112, 2000.
[14] Gregg Rothermel and Mary Jean Harrold, “A Safe, [32] S. Elbaum, P. Kallakuri, A. G. Malishevsky, G.
Efficient Regression Test Selection Technique”, ACM Rothermel, and S. Kanduri, “Understanding the effects of
Transactions on Softw. Eng. And Methodology, 6(2): 173- changes on the cost-effectiveness of regression testing
210, 1997. techniques”, Journal of Software Testing, Verification, and
[15] Gregg Rothermel and Mary Jean Harrold, “Analyzing Reliability, 13(2):65-83, 2003.
Regression Test Selection Techniques”, IEEE Transactions [33] Todd L. Graves, Mary Jean Harrold, Jung-Min Kim,
on Software Engineering, 22(8):529-551, 1996. Adam Porter and Gregg Rothermel, “An Empirical Study of
[16] Jirapun Daengdej, Ph.D. Thesis, “Adaptable Case Base Regression Test Selection Techniques”, 2000.
Reasoning Techniques for Dealing with Highly Noise [34] W. Eric Wong, J. R. Horgan, Saul London and Hira
Cases” The University of New England, Australia, 1998. Agrawal, “A Study of Effective Regression Testing in
[17] Jun Zhu and Quiang Yang. “Remembering To Add Practice”, 8th IEEE International Symposium on Software
Competence-preserving Case Addition Policies for Case Reliability Engineering (ISSRE’97), 1997.
Base Maintenance.” In Proceedings of the 16th International [35] W. Eric Wong, Joseph R. Horgan, Saul London and
Joint Conference in Artificial Intelligence, 234-241. Aditya P. Mathur, “Effect of Test Set Minimization on the
Morgan-Kaufmann, 1999 Fault Detection Effectiveness of the All-Uses Criterion”, In
[18] Mary Jean Harrold, Rajiv Gupta and Mary Lou Soffa, Proceedings of the 17th International Conference on
“A Methodology for Controlling the Size of A Test Suite”, Software Engineering, pages 41-50, 1995.
ACM Transactions on Software Engineering and [36] Xiaofang Zhang, Baowen Xu, Changhai Nie and Liang
Methodology, 2(3):270-285, 1993. Shi, “An Approach for Optimizing Test Suite Based on
[19] Nicha Kosindrdecha and Jirapun Daengdej, “A Testing Requirement Reduction”, Journal of Software (in
Deletion Algorithm for Case-Based Maintenance Based on Chinese), 18(4): 821-831, 2007.
Accuracy and Competence”, Assumption University, [37] Xiaofang Zhang, Baowen Xu, Changhai Nie and Liang
Thailand, 2003 Shi, “Test Suite Optimization Based on Testing
[20] Nicha Kosindrdecha and Siripong Roongruangsuwan, Requirements Reduction”, International Journal of
“Reducing Test Case Created by Path Oriented Test Case Electronics & Computer Science, 7(1): 9-15, 2005.
Generation”, AIAA 2007 Conference and Exhibition, [38] Xue-ying MA, Bin-kui Sheng, Zhen-feng HE and
Rohnert Park, California, USA, 2007. Cheng-qing YE, “A Genetic Algorithm for Test-Suite
[21] NIST, “The economic impacts of inadequate Reduction”, IEEE, China, 2006.
infrastructure for software testing”, 2002. [39] Yanbing Yu, James A. Jones and Mary Jean Harrold,
[22] Saif-ur-Rebman Khan and Aamer Nadeem, “TestFilter: “An Empirical Study of the Effects of Test-Suite Reduction
A Statement-Coverage Based Test Case Reduction on Fault Localization”, Proceedings of ICSE’08, Germany,
Technique”, 2006. 2008.
[23] Sara Sprenkle, Sreedevi Sampath and Amie Souter,
“An Empirical Comparison of Test Suite Reduction
Techniques for User-session-based Testing of Web
Applications”, Journal of Software. Testing, Verification,
and Reliability, 4(2), 2002.
[24] Scott McMaster and Atif Memon, “Call Stack
Coverage for Test Suite Reduction”, Proceedings of the
21st IEEE International Conference on Software
Maintenance (ICSM’05), pages 539-548, Budapest,
Hungary, 2005.
[25] Scott McMaster and Atif Memon, “Call Stack
Coverage for GUI Test-Suite Reduction”, Proceedings of
the 17th IEEE International Symposium on Software
Reliability Engineering (ISSRE 2006), NC, USA, 2006.
[26] Scott McMaster and Atif Memon, “Fault Detection
Probability Analysis for Coverage-Based Test Suite
Reduction”, IEEE, 2007.
[27] Sreedevi Sampath, Sara Sprenkle, Emily Gibson and
Lori Pollock, “Web Application Testing with Customized
Test Requirements – An Experimental Comparison Study”,
17th International Symposium on Software Reliability
Engineering (ISSRE’06), 2006.
[28] Siripong Roongruangsuwan and Jirapun Daengdej,
“Techniques for improving case-based maintenance”,
Assumption University, Thailand, 2003
[29] Siripong Roongruangsuwan and Jirapun Daengdej,
“Test Case Reduction”, Technical Report 25521.
Assumption University, Thailand, 2009.
[30] S. Elbaum, A. Malishevsky, and G. Rothermel, “Test
Case Prioritization: A Family of Empirical Studies”, IEEE
Trans. on Software Engineering, vol. 28, 2002.
[31] S. Elbaum, A. G. Malishevsky and G. Rothermel,
“Prioritizing Test Cases for Regression Testing”, In