A Safe, Efficient Regression Test Set Selection Technique
G. Rothermel and M. J. Harrold
ACM Transactions on Software Engineering and Methodology
V. 6, no. 2, April 1997, pages 173 - 210


Regression testing is an expensive but necessary maintenance activity performed on modified software to provide confidence that changes are correct and do not adversely affect other portions of the software. A regression test selection technique chooses, from an existing test set, tests that are deemed necessary to validate modified software. Most regression test selection techniques depend on a particular test adequacy criterion or require prior knowledge of where code has been modified. We present a new technique for regression test selection that is neither adequacy-based, nor requires prior knowledge of modifications. Our algorithms construct control flow graphs for a procedure or program and its modified version, and use these graphs to select tests, from the original test set, that execute changed code. We prove that under certain conditions, the set of tests our algorithms select includes every test, from the original test suite, that can expose faults in the modified procedure or program. Thus, under these conditions, the algorithms are safe. Moreover, although our algorithms may select some tests that cannot expose faults, they are at least as precise as other safe regression test selection algorithms. Unlike many other regression test selection algorithms, our algorithms handle all language constructs, and all types of program modifications. We have implemented our algorithms; initial empirical studies indicate that our technique can significantly reduce the cost of regression testing modified software.