FIELD OF INVENTION
The present invention is related to the methods and system 5 for ordering software
tests to optimize regression testing; more particularly, the invention presents the
similarity-based approach to prioritize the test cases in a test suite which in turn
helps the testers to achieve certain testing objective earlier in the testing process.
BACKGROUND & PRIOR ART
10
Software testing is a most critical and important phase of any software
development process that ensures the implemented software is performed properly
as intended. The key objective of testing is to discover maximum faults as early as
possible prior to the next release of the software product. After the release
15 debugging process becomes very complex and costly as well. Therefore, it is
beneficial to identify faults and issues to rectify them accordingly before the final
delivery of any software product. Early detection of errors and bugs improves the
quality and reliability of any software product and develops healthy relations with
customers also.
20 Regression testing ensures that the new version of existing software working
properly without affecting the present features of previous one. For example, there
is a possibility of inconsistency after removal of existing features or addition of
new features in the modified software. Therefore, for effective regression testing,
(C) ADDRESS: RESEARCH SCHOLAR, DEPARTMENT OF INFORMATION
TECHNOLOGY, BABASAHEB BHIMRAO AMBEDKAR UNIVERSITY, VIDYA
VIHAR, RAEBARELI ROAD, LUCKNOW (226025), INDIA
3. PREAMBLE TO THE DESCRIPTION
COMPLETE SPECIFICATION
The following specification describes the invention
3
we must develop an optimal test suite to validate any software. Here optimal
signifies the representative test suite that contains essential or unique test cases
with maximum coverage capability and higher fault detection rate.
Regression testing also involves the addition of new test cases to examine the new
features of the modified software. Addition of new test cases 5 may progressively
increase the test suite size that makes the regression testing more complex in
terms of time and cost. It is quite impractical to execute the entire test suite that
may contain redundant or obsolete test cases due to the addition of new test cases
in the existing test suite. Consequently, it is quite useful to optimize the test suite
10 by removing the duplicate and obsolete test cases, in turn, can make the regression
testing more effective in the matter of required cost and effort. Previously three
approaches were proposed for optimizing the test suite i.e. test case selection,
minimization and prioritization. Where, test case selection and minimization
involve reducing the number of test cases that are to be executed. And the last
15 approach mentioned as prioritization orders the test cases based on some criterion
(fault revealing probability, coverage capability etc.) so that the highest priority
test cases are executed first then the test cases having the lowest priority. Test case
selection and minimization have some drawbacks in terms of fault detection rate.
Empirical studies reveal that in some cases fault exposing ability of test suites can
20 be severely compromised by reducing the test suite size. In conjunction with test
case prioritization, minimization performs better in terms of coverage as well as
fault detection effectiveness. Coverage-based regression techniques are widely
used in prior work to maximize the coverage, but they are not always given the
satisfactory result. In recent years, the similarity-based approach has gained wide
25 attention in the field of testing. The prime objective of that approach is to increase
the test case diversity by measuring the difference between a pair of test cases.
The similarity degree between a pair of test cases is evaluated by any of the
available distance measures i.e. Hamming Distance, Euclidean Distance, Jaccard
Index, Cosine Similarity etc. Consequently, this will increase the fault detection
30 rate if we increase the diversity of test cases. The distance measures require
certain criteria i.e. control flow, def-use, MC/DC, path coverage etc. to evaluate
4
the difference. However, only one or two of the coverage criteria have been used
in previous similarity-based approaches. But, no single coverage criteria can
expose maximum or all faults, different kinds of faults are best revealed by using
multiple coverage criteria.
Therefore, there is a need for an intelligent approach to select 5 preferred test cases
to analyze the software by exposing maximum faults as early as possible, by
considering multiple coverage criteria too. Thus, it would be advantageous to
schedule the order of test cases by applying a similarity-based approach that
increases the diversity, in turn, can improve the fault detection rate. It would also
10 be advantageous to deliver some proper guidelines and roadmap to testers which
surely benefit them in regression testing process.
OBJECTIVE OF THE INVENTION
The objective of present invention is to provide a method and a system for optimal
ordering of test cases based on multiple criteria using a similarity-based approach
15 such that higher priority test cases are executed first than lower ones. The
prioritization approach of the present invention helps the developers/testers to
reveal faults as early as possible in the testing process and thus, allows developers
to start debugging process sooner.
BRIEF DESCRIPTION OF DRAWINGS
20 The present invention is described by way of the accompanying drawings to be
easily understood, which, however, should not be considered to limit the scope of
the invention, but are for better clarification only. The feature of the present
invention will be illustrated with additional specificity and detail with reference to
the accompanying figures, in which:
25 FIG. 1 illustrates a block diagram of a system for similarity based prioritization of
software tests in accordance with the present invention.
FIG. 2A shows the flow diagram for evaluating the similarity level between each
pair of test cases, in accordance with the present invention.
FIG. 2B illustrates the flow diagram of prioritizing test cases, in accordance with
30 the present invention.
5
DETAIL DESCRIPTION
In the following description, various features and a thorough understanding of the
present invention are provided herein. The present invention includes an approach
or method for prioritizing test cases in regression testing. 5 Exhaustive testing
intended to be very complex and time-consuming. Therefore, it is advantageous to
generate an optimal test suite that is responsible for the early execution of
essential test cases to achieve some defined goals. The main purpose herein is to
schedule the order of test cases with the help of similarity based approach that
10 includes pair wise comparison based on multiple coverage criteria as well.
FIG. 1 is a block diagram illustrating one embodiment for test case prioritization
by applying similarity-based approach, in accordance with the present invention.
The depicted system includes an input unit (101) comprises of program source
code, test cases and multiple coverage criteria. The inputs are provided to the test
15 case comparator module (102) includes a coverage analyzer module (103) and a
similarity generator module (104). Where, the coverage analyzer module (103) is
responsible for collecting coverage details by executing the test cases on SUT.
With the help of generated coverage metrics, the similarity generator module
(104) cooperates to evaluate the difference between a pair of test cases in a
20 quantifiable manner. The prioritizer module (105) comprises of further three submodules.
Where pair-wise grouping of similar test cases is performed by (106)
module and (107) module is intended for selection of unique test cases from each
group. Afterwards, the ordering of test cases is executed by (108) module and then
output (109) i.e. prioritized test cases is obtained.
25 FIGS. 2A-2B illustrates an embodiment flow diagram for similarity-based test
case prioritization. FIG. 2A describes the process of generating similarity matrix
for prioritizing test cases. A test suite is a collection of test cases that are designed
to validate the software to be tested (201). In an embodiment, all the test cases of
a test suite are executed on the software code (202) and the coverage information
30 are captured (203) for each selected criterion. The selected criteria herein are
statement, branch, and MC/DC coverage through which the coverage matrix is
6
generated for each one of them (203). The present invention provides a freedom to
use other coverage criterions also, where the above criterions are selected based
on their importance and feasibility. To calculate the similarity degree between a
pair of test cases, it requires selection of any distance measure (204). There are
multiple distance measures (205) are available for comparing 5 test cases. Empirical
studies show that the Euclidean distance is very effective as compared to others.
But in some of the cases, other measures are also working efficiently. The
selection is totally depending on user requirements. With the help of any one of
the distance measure, the similarity values are calculated for each of the selected
10 criterions (206). Afterwards, we get three different coverage similarity matrices
i.e. Statement (207), Branch (208), and MC/DC similarity matrix (209). The
geometric mean is calculated (210) by taking each of the matrix values, first for
statement and branch and then for all the three matrices i.e. statement, branch and
MC/DC. The integrated similarity matrix (211) is finally ready to use for
15 prioritization process.
FIG. 2B depicts the flow diagram for pair-wise prioritization of test cases in an
embodiment. By using the integrated similarity matrix, more than one group of
similar test pairs are generated (301). Test pairs (302) of the same group have
similar similarity values. The created groups are arranged in descending order of
20 the similarity values (303) and then pick the test case pair from that group having
maximum similarity value (304). From that selected pair, pick any test case ‘T’ in
a random manner (305). Then all the pairs containing ‘T’ were selected from the
same group (306) and stored (310) consecutively for further processing. While
performing a selection of test pairs, we must check every test case has been
25 selected from that group or not (307). If not, then from step (306) onwards are
performed accordingly. Otherwise, a determination is made as to whether any
other groups are remained to be processed or not (308). If yes, the counter goes to
next group (309) and repeat the steps from (304) and so on until no further groups
are available to be processed. After the completion of the selection process from
30 each group, we get the group-wise selected pairs in the storage (310) that are
arranged in descending order of similarity values. In an embodiment at block
7
(311), each unique test case is selected from the ascending order of the group until
every unique test case has been selected. Afterwards, the test cases are prioritized
according to the First Come First basis (312). The result as representative ordered
test suite will be stored in optimal test suite storage (313).
5
10
15
Sign: -
Name: - SHREE, RAJ
Address: - DIT, BABASAHEB
BHIMRAO AMBEDKAR
UNIVERSITY, VIDYA VIHAR,
RAEBARELI ROAD,
LUCKNOW (226025), INDIA
Sign: -
Name: - SINGH, SHILPI
Address: - DIT, BABASAHEB
BHIMRAO AMBEDKAR
UNIVERSITY, VIDYA VIHAR,
RAEBARELI ROAD,
LUCKNOW (226025), INDIA
Sign: -
Name: - PANDEY, RAVI
PRAKASH
Address: - Address: 5/5/21A,
NEAR UDAYA PUBLIC
SCHOOL, ITI CHAURAHA,
PANCHKOSHI PARIKRAMA
MARG, FAIZABAD,
UP, INDIA-224001
Sign: -
Name: - SHUKLA, VIVEK
Address: - DIT, BABASAHEB
BHIMRAO AMBEDKAR
UNIVERSITY, VIDYA VIHAR,
RAEBARELI ROAD,
LUCKNOW (226025), INDIA
8
Abstract
SYSTEM AND METHOD FOR SIMILARITY BASED PRIORITIZATION
OF SOFTWARE TESTS 5
A system and method for ordering software tests for effective regression testing.
The similarity-based approach is applied to analyze and compare the pair of test
10 cases based on certain criteria. For each selected criterion the coverage matrix is
generated that is used to evaluate the integrated similarity matrix. Multiple groups
of test pairs having equal similarity value are generated on which the pair-wise
selection process has been performed.

Claim(s)
1. A method for generating an optimal ordered test suite, comprising test case
comparator module that compares and analyze the test cases and prioritizer
module that schedule the order of test cases for effective 5 regression testing
with higher fault detection rate.
2. To quantitively analyze the pair of test cases, three important coverage
criteria i.e. branch, statement, and MC/DC are used herein through certain
distance measure.
10 3. Geometric Mean is applied to get an integrated similarity value for each
pair of test cases by considering all three selected coverage criteria, and
through which multiple groups of similar similarity degree are generated.
4. The present invention provides a pair-wise selection feature to choose the
order of execution of test cases.
15 5. The present invention implements the similarity-based approach with pairwise
selection feature to prioritize the test cases, that consecutively
improve the coverage capability and fault detection rate of representative
ordered test suite.