A Unifying Framework Supporting the Analysis and Development of Safe Regression Test Selection Techniques

Safe regression test selection (RTS) techniques let software testers reduce the number of test cases that need to be rerun to revalidate new versions of software, while ensuring that no fault-revealing test case (in the existing test suite) is excluded. Most previous work on safe regression test selection has focused on specific safe RTS algorithms, rather than addressing the theoretical foundations of safe RTS techniques in general. In this paper, we present a unifying framework for safe RTS that supports the analysis and development of safe RTS techniques. We show that every safe RTS technique is founded on a regression bias, and we show how one can prove an RTS technique safe for a set of programs and testing processes by eliciting the bias from the technique and then proving that the bias holds or does not hold for that set of programs and processes. We provide two general models for safe RTS techniques that can be used as templates in proofs of safety. The fist model actually contains two formulations, both defined in terms of finite automata. This fist model is inefficient; it does, however, provide the most general, powerful, safe RTS algorithm possible, given some simple assumptions. We then define a generalized safe RTS algorithm that is only marginally less powerful than the finite automata method, and that provides a template that simplifies the development of safe RTS algorithms. Finally, to illustrate the application of our framework, we use it to analyze several existing safe RTS algorithms and their biases, and to develop a new safe RTS algorithm for programs written in spreadsheet languages