# Efficient Regression Testing of Software Product Lines by Reducing Redundant Test Executions
## 3 A Motivating Example  
In this section, we describe our key insight using the example in Figure 1. Let us suppose that by some changes to features 2 and 3 in the product line code base, the modified product family, P\({}_{1}\)', P\({}_{2}\)' and P\({}_{3}\)' has been produced and the test cases t1, t2 and t3 were selected for regression testing of the modified product family. In this case, the selected test cases should be rerun on the product family to check whether the current revision still works well. If the selected test cases are executed exhaustively (i.e., t1 and t2 are run on all the products and t3 is run on P\({}_{2}\)' and P\({}_{3}\)'), the total number of test executions is 8.  
A naive approach that reduces the number of test executions is to run all the test cases selected for retest on only one product of a product family. For example, if t1, t2 and t3 are run only on P\({}_{2}\)' or P\({}_{3}\)', then five test executions are reduced and so the total number of test executions is three. However, this approach can miss faults that would be detected by the exhaustive execution of test cases because a test case can be designed to have variability that allows testing of different parts depending on the product to be tested or because, by modifications of a product family, an existing test case may provide different code coverage for the modified products of the product family. In the case of our example, when t2 is applied to P\({}_{1}\)', it covers the LinearSearch class and when t2 is applied to P\({}_{2}\)' and P\({}_{3}\)', it covers the BinarySearch class. In this case, if t2 is applied only to P\({}_{1}\)', the faults contained in the BinarySearch are not exposed and if t2 is applied only to P\({}_{2}\)' or P\({}_{3}\)', the faults contained in the LinearSearch class are not exposed.  
To overcome this problem, the execution trace of a test case can be used. When t1 is applied to P\({}_{1}\)', P\({}_{2}\)' and P\({}_{3}\)', it covers the same sequence of classes (in this case, Search class only) and the code of the class is identical for the products. So, it suffices to apply t1 to just one of P\({}_{1}\)', P\({}_{2}\)' and P\({}_{3}\)'. Likewise, it suffices to apply t2 to P\({}_{1}\)' and one of P\({}_{2}\)' and P\({}_{3}\)'. Because t3 is not executable on P\({}_{1}\)', it suffices to apply t3 to just one of P\({}_{2}\)' and P\({}_{3}\)'. Therefore, four redundant test executions can be eliminated and the reduced number of test executions is four. This approach is more efficient than the exhaustive execution and will not miss faults that the exhaustive execution detects. Although a simple example was shown here to introduce our approach clearly, the problem exhibited through this example arises very frequently in the testing of product families.  
To develop our approach, two problems should be handled. The first one is how to identify redundancy of test executions. The second one is how to select a set of products on which each test case selected for retest can be executed with no loss in fault detection. In Section 4, we explain our method that solves these two problems.