Regression Test Selection for Distributed Software Histories

ABSTRACT. Regression test selection techniques follow the software development process and pick the subset of only those tests whose behavior may be affected by the latest changes in the code. By focusing on a small subset of all tests, the testing process runs faster and, therefore, can be more tightly integrated into the development process. Existing algorithms for regression test selection assume a development model in which changes to the code happen in a linear sequence. These algorithms consider two versions of the software, related by a single change, at a time, and compute the set of tests affected by this change.

Unfortunately, modern software development processes using distributed version control systems, are more complex. Software version histories are more realistically modeled as directed graphs of versions; in addition to the previous case of a single change, two versions can be related by other commands available in a version control system, e.g., branch, merge, rebase, cherry-pick, etc. We describe the first regression test selection algorithm for software developed using modern distributed version control systems. By modeling different branch or merge operations directly in our algorithm, we can compute safe test sets that are orders of magnitude smaller than naive extensions of previous algorithms (e.g., that take the union of selected tests at every merge point).

We performed an extensive evaluation of test selection on existing software histories of large popular open-source projects. Our results are extremely positive: our framework obtained 5x speedup (in terms of the number of tests executed) over naive extensions of the existing algorithms.