# Efficient Regression Testing of Software Product Lines by Reducing Redundant Test Executions
## 4 Test Execution Reduction Method for Efficient SPL Regression Testing
### Step 2-2. Selective Test Execution  
This step applies the test cases selected in Step 1A to the instrumented products created in Step 2-1, collecting their execution traces. To reduce redundant test executions and reduce redundancy in the test execution traces, our method selects a set of products on which each test case can be executed with no repetition of equivalent test executions, based on Lemma 1. As shown in the SelectiveTestExecution function of Algorithm 2, for each test case (\(t\)) that is selected from Step 1A, the function first obtains an execution trace (\(tr\)) by applying \(t\) to a certain product (\(p\)) out of the products (P) that reuse \(t\) (lines 2-5). Next, it obtains a list (_chksumListA_) of checksum values of the code units in \(tr\) (line 6). Finally, if another product (\(q\)) in P has code units whose list of checksum values is the same as _chksumListA_, then the algorithm excludes \(q\) from the set of products to which \(t\) would be applied (line 8-15) because, by Lemma 1, executions of \(t\) applied to \(p\) and \(q\) would be equivalent. ```
1:\(IMPF\): instrumented modified product family
2:\(TCs\): test cases selected from the A phase
3:\(chksumMatrix\): checksum matrix for a product family
4:execute(\(t\), \(p\)): input a test case \(t\) and an instrumented product \(p\), and return the execution trace of \(t\) for \(p\)
5:functionSelectiveTestExecution(\(IMPF\), \(TCs\), \(chksumMatrix\))
6:foreach\(t\in TCs\)do:
7:P \(\leftarrow\) products of \(IMPF\) for which \(t\) is reused
8:foreach\(p\in P\)do:
9:\(\mathrm{tr}\leftarrow\mathrm{apply}(t,p)\)
10: chksumList \(\leftarrow\) chksumMatrix.lookup(\(p\), \(\mathrm{tr}\).CodeUnits)
11:\(\mathrm{Q}\leftarrow\mathrm{P}-\{p\}\)
12:foreach\(q\in Q\)do:
13: chksumListB \(\leftarrow\) chksumMatrix.lookup(\(q\), \(\mathrm{tr}\).CodeUnits)
14:if chksumListA equals chksumListB then:
15:\(\mathrm{P}\leftarrow\mathrm{P}-\{q\}\)
16:endif
17:endfor
18:endfor
19:endfunction
```  
**Algorithm 2** Selective Test Execution  
Table 2 shows examples of selective execution for the three test cases listed in the first column. The second column presents products that use the test cases. The third and fourth columns present the products to which the test case is applied and the test execution traces for the products, respectively. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Class A** & **Class B** & **Class C** \\ \hline \(\mathrm{P_{1}}^{\prime}\) & a & b & - \\ \(\mathrm{P_{2}}^{\prime}\) & a & - & c \\ \(\mathrm{P_{3}}^{\prime}\) & a & b & d \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Example of checksum matrix. The checksum matrix presented in Table 1 is used in this example. As shown in Table 2, t1 is reused for P1', P2', and P3'. So, first, t1 is applied to certain one (and exactly one) product out of the products and its execution trace is obtained. We assume that P1' was selected for the first test execution and t1 traversed only Class A on P1'. Next, the algorithm obtains the checksum values of Class A for P1' and the other products that reused t1. As shown in Table 1, their checksum values are the same, i.e., \"a\". In this case, the algorithm does not apply t1 to P2' and P3' because, by Lemma 1, executions of t1 applied to P1', P2' and P3' would be equivalent. t2 is reused for P2' and P3'. We assume that P2' was selected for the first test execution and t2 traversed only Class C on P2'. In this case, t2 is applied to P3' too because Class C of P3' is not identical to Class C of P2', as shown in Table 1. t3 is used for P1' only. In this case, t3 must be applied to P1' because there are no equivalent test executions. Units of code changes, code units in test execution traces and code units in the checksum matrix can have various granularities such as file, class, method, statement, etc. However, if their granularities are different, test cases affected by a change cannot be determined directly from the test execution traces and the equivalence of test executions cannot be determined directly from the checksum matrix.