Empirical comparison of regression test selection algorithms

Abstract

In the maintenance phase, the regression test selection problem refers to selecting test cases from the initial suite of test cases used in the development phase. In this paper, we empirically compare five representative regression test selection algorithms, which include: Simulated Annealing, Reduction, Slicing, Dataflow, and Firewall algorithms. The comparison is based on eight quantitative and qualitative criteria. These criteria are: number of selected test cases, execution time, precision, inclusiveness, preprocessing requirements, type of maintenance, level of testing, and type of approach. The empirical results show that the five algorithms can be used for different requirements of regression testing. For example the Simulated Annealing algorithm can be used for emergency non-safety-critical maintenance situations with a large number of small modifications.

Introduction

Software maintenance involves modifying programs as a result of errors, or changes in the user requirements (Bennett, 1991). During such modifications, new errors may be introduced, causing unintended adverse side effects in the software. Regression testing aims to provide confidence that the modifications are correct and have not adversely affected other parts of the program. Regression testing can be progressive or corrective (Hartmann and Robson, 1988). The former involves retesting major changes to the program's specifications. The latter is performed on specifications that essentially remain unchanged, so that only minor modifications, which do not affect the overall program structure, require retesting.

For regression testing, it might be costly to repeat the whole set of test cases used in the initial development of the program and unreliable to choose a random subset of these test cases. Therefore, it may be useful to select a suitable subset of test cases that accomplishes the objectives of regression testing. This subproblem of regression testing is referred to as the regression test selection problem.

The selection of suitable test cases can be made in different ways, and a number of regression testing approaches and algorithms have been proposed. A strategy based on input partitioning and cause-effect graphing of the program specification has been described in Yau and Kishimoto (1987). Leung and White (1989) have suggested classifying the initial test cases as reusable, retestable, obsolete, and adding new-structural and new-specification test cases. Then test cases can be selected from some of or all five classes. They have also extended this approach to cover programs with global variables (Leung and White, 1990b) and proposed methods to limit integration regression testing to a small set of modules based on the “firewall” concept (Leung and White, 1990a, Leung and White, 1992). An analogous concept of class firewall has been proposed for regression testing object-oriented software systems (Hsia et al., 1997).

A slicing algorithm presented in Gallagher and Lyle (1988) decomposes a program and selects the test cases that detect “linkage” between the modified and unmodified code. Another slicing strategy, which is based on data flow testing and incremental data flow analysis, has been described in Harrold and Soffa (1988) and Gupta et al. (1996). A safe algorithm, which uses a module's dependence graph and selects test cases that will cause the modified module to produce different output than the original module, has been proposed in Rothermel and Harrold, 1997, Rothermel and Harrold, 1998. An incremental slicing algorithm has been proposed in Agrawal et al. (1993) which selects test cases whose outputs may be affected by the modifications made.

Path expressions are used in Benedusi et al. (1988) to represent the program and then algebraic operations are used to determine the paths affected by the modifications. This facilitates the selection of the initial test cases needed for retesting. A similar approach based on semantic differencing has been proposed in Binkley (1997). Also, textual differencing has been used in Vokolos and Frankl (1998). An optimal regression testing approach based on a 0–1 integer programming problem formulation has been proposed by Fischer et al. (1981) and extended in Hartmann and Robson (1990) and solved by natural optimization algorithms in Mansour and El-Fakih (1999). Further, some software tools that are based on regression testing techniques have been constructed (Chen et al., 1994; Vokolos and Frankl, 1997; White et al., 1993; von Mayrhauser and Zhang, 1999).

Despite this amount of research on regression testing algorithms, insufficient work has been done on effectiveness evaluation and comparison of these algorithms. A simple cost model has been suggested early in Leung and White (1991). Another coverage-based cost-effectiveness prediction model has been proposed in Rosenblum and Weyuker (1997). A theoretical analysis framework has been suggested in Rothermel and Harrold (1996). In particular, empirical work has been insufficient. We have reported some initial experimental comparative results in Baradhi and Mansour (1997). Wong et al. (1998) directly examines the costs and benefits of only minimizing the test suite size. Rothermel et al. (1998) compares the costs and benefits of minimizing the test suite to show that the fault-detection capabilities of the selected subset can be compromised by minimization. Graves et al. (1998) empirically compare three algorithms with random and retest-all techniques. The three algorithms are: edge-coverage-adequate minimization, safe, and dataflow-coverage-based. The comparison focuses on the abilities to reduce regression testing effort and uncover faults in modified programs.

In this paper, we describe a comparison framework and present an empirical comparative study of five representative regression test selection algorithms, which include: Simulated Annealing, Reduction, Slicing, Dataflow, and Firewall algorithms. The comparison framework is composed of the following eight criteria: the number of test cases selected for regression testing, execution time, precision, inclusiveness, preprocessing requirements, type of maintenance, level of testing, and type of approach. This study shows that the five algorithms have diverse properties for different criteria. This enables software engineers and project managers to make appropriate decisions and select the regression testing algorithm that best fits the requirements of their application and development process.

This paper is organized as follows. Section 2 describes the regression test selection problem and the program models used. Section 3 gives a brief description of the five implemented algorithms. Section 4 describes the comparison criteria. Section 5 presents and briefly discusses the experimental results. Section 6 summarizes these results and discusses the limitations of the empirical study. Section 7 contains conclusions.