Reducing the cost of regression testing by semantics guided test case selection

Software maintainers are faced with the task of regression testing: retesting a modified program on a (large) number of test cases. The cost of regression testing can be reduced if old test cases and old test results can be reused. Reuse avoids the costly construction of new test cases and the unproductive rerunning of existing test cases when it can be guaranteed that the modified and original programs will produce the same results. An algorithm that uses language semantics to provide such a guarantee is presented. This algorithm uses semantic (not syntactic) differences and similarities between the old and new programs. The algorithm is based on the notion of common execution patterns, which is the interprocedural extension of equivalent execution patterns. Program components with common execution patterns 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)