# Efficient Regression Testing of Software Product Lines by Reducing Redundant Test Executions
## 4 Test Execution Reduction Method for Efficient SPL Regression Testing
### Definitions, Assumption and Lemma  
Test execution is an application of a test case to the system under test (SUT). If \(tc\) is a test case and \(p\) is an SUT, then we will write _TE(p,tc)_ to denote the test execution of \(tc\) applied to \(p\). Test executions can become redundant for various reasons such as that they are unnecessarily repeated executions of a test case; that they are executions of duplicated test cases; and that they test already covered code, not contributing to test coverage increase. Redundant test executions are useless in finding faults of a software program and just increase the testing cost because they do not detect any faults other than the faults already detected by the previous test executions. Redundant test execution can be defined as follows:  
**Definition 5**. : (Redundant test execution) _For any test execution \(e\) in a set of test executions \(E\), let Faults(\(E\)) be the set of the faults that are detected by \(E\). If Faults(\(E-\{e\}\)) = Faults(\(E\)), then \(e\) is said to be a redundant test execution._  
In Figure 1, let us suppose that a fault is located in the constructor of the Search class and t1 detects the fault. In this case, when t1 is applied to P1', P2' and P3' sequentially, the test execution of t1 applied to P1' is not redundant because t1 detects the fault. However, the test executions of t1 applied to P2' and P3' are redundant because they do not detect any fault other than the fault already detected when t1 is applied to P1'. The test executions of t2 and t3 applied to P1', P2' and P3' are redundant, too, because they do not test the constructor of the Search class and so do not detect the fault. In this paper, we consider only the case of unnecessarily repeated executions of test cases selected for retest in the context of an SPL. To reduce such redundant test executions, our method utilizes the notion of equivalence of test executions. To define it precisely, we use the notion of code unit. **Definition 6**. : (Code unit) _A code unit is a section of code written in a programming language that can be executed._  
For example, in the case of object-oriented programming languages, code units are classes, methods and statements and in the case of procedural programming languages, code units are files, functions and statements. Now the equivalence of test executions is defined as follows. **Definition 7**. : (Equivalence of test executions) _Two test executions are equivalent if they cover exactly the same sequence of code units and produce the same testing result. Formally, when \(P_{1}\) and \(P_{2}\) are products, \(tc_{1}\) and \(tc_{2}\) are test cases, the coverage of a test execution \(e\) is denoted as \(Cov(e)\) and the test result of a text execution \(e\) is denoted as Res(\(e\)), if \(Cov(TE(P_{1}\),\(tc_{1}))=Cov(TE(\(P_{2}\),\(tc_{2}\))) and Res(TE(\(P_{1}\),\(tc_{1}\))) = Res(TE(\(P_{2}\),\(tc_{2}\))) then we say that the two test executions TE(\(P_{1}\),\(tc_{1}\)) and TE(\(P_{2}\),\(tc_{2}\)) are equivalent and write TE(\(P_{1}\),\(tc_{1}\)) \(\equiv\) TE(\(P_{2}\),\(tc_{2}\))._  
If one of two equivalent test executions detects a fault, the other will also detect the fault and if one does not detect a fault, the other will not detect the fault either. In Figure 1, the test executions of t1 applied to P1' and P2', respectively, are equivalent because they cover exactly the same sequence of code statements of the Search constructor and produce the same testing result. However, the test executions of t2 applied to P1' and P2', respectively, are not equivalent because the test execution of t1 applied to P1' covers the code of the function for the LinearSearch class but the test execution of t1 applied to P2' covers the code of the function for the BinarySearch class. A testing result can be affected by various factors such as operating system, network connection, hardware settings, etc. For example, if memory available for dynamic allocation is changed, then a test case that passed on a program can fail on the same program.