Semantics guided regression test cost reduction

Software maintainers are faced with the task of regression testing: retesting a modified program on an often large number of test cases. The cost of regression testing can be reduced if the size of the program that must be retested is reduced and if old test cases and old test results can be reused. Two complimentary algorithms for reducing the cost of regression testing are presented. The first produces a program called differences that captures the semantic change between certified, a previously tested program, and modified, a changed version of certified. It is more efficient to test differences, because it omits unchanged computations. The program differences is computed using a combination of program slices. The second algorithm identifies test cases for which certified and modified will produce the same output and existing test cases that will test components new in modified. Not rerunning test cases that produce the same output avoids unproductive testing; testing new components with existing test cases avoids the costly construction of new test cases. The second algorithm is based on the notion of common execution patterns, which is the interprocedural extension of the notion introduced by Bates and Horwitz. Program components with common execution patterns have the same execution pattern during some call to their procedure. They are computed using a new type of interprocedural slice called a calling context slice. Whereas an interprocedural slice includes the program components necessary to capture all possible executions of a statement, a calling context slice includes only those program components necessary to capture the execution of a statement in a particular calling context (i.e., a particular call to the procedure). Together with differences, it is possible to test modi fled by running the smaller program differences on a smaller number of test cases. This is more efficient than running modified on a large number of test cases. A prototype implementation has been built to examine and illustrate these algorithms.