# The MADAG Strategy for Fault Location Techniques
## 2 Preliminary
### Test Case Prioritization  
Suppose that a program P consists of n statements, s\({}_{1}\), s\({}_{2}\), s\({}_{3}\),..., s\({}_{n}\), and there are m test cases, t\({}_{1}\), t\({}_{2}\), t\({}_{3}\),..., t\({}_{m}\). A test case t\({}_{i}\) is a set that consists of the statements that would be executed when ti serves as the input to run P. For each ti, there is a corresponding test result denoted by ri whose value can be 1 (implying test case i results in failure) or 0 (implying test case i results in success). Then, it can create a binary m \(\times\) n matrix M to represent the program spectra and a vector R to record all the testing results, which are shown in Figure 1. SBFL can use the spectrum information and testing results to compute the suspiciousness value of each statement as being responsible for failures and sorting them in a ranking list. For SBFL techniques, several different similarity coefficients can be used [16], well known as Jaccard [17], Tarantula [18], and Ochiai [1] coefficient. Based on the spectra, a ranking metric will be used for calculating the suspicious program statements; faulty statements would have high suspiciousness scores, and non-faulty ones would have low suspiciousness scores. However, the above is not guaranteed. Test case prioritization finds the ideal permutation of the test cases in a test suite to enhance a special testing criterion, such as the rate of fault detection, code coverage, or some other units of measurement [19; 20]. This concept was first mentioned by [PERSON] et al. [15]. They combined minimization and prioritization approaches to erase the omitted test cases and sort the selected ones from a test suite. Subsequently, [PERSON] et al. [20] defined the test case prioritization (TCP) problem as follows:  
Given: (1) \(T\), a test suite, (2) \(PT\), the set of all permutations of \(T\), and (3) \(f\), a function from \(PT\) to real numbers, \(f\):\(PT\to R\). Problem: To find a permutation \(p\in PT\) such that \(\forall p\in PT\). \(f(p)\geq f(p\,)\). In this definition, the key for TCP techniques is to find a mapping function \(f\) that assigns an appropriate priority to the test cases. The following are the previous studies for TCP techniques that we compare with our approach. Total-Statement [20] strategy assigns higher priorities to a test case that executes more statements in a program. Add-Statement [20] strategy extends the total-statement strategy by selecting the next test case that covers more statements that have not been covered by the previously selected test cases. Adaptive Random Testing (ART) [21] strategy is a hybrid random/coverage-based approach that selects the next test case in two steps. First, ART selects the test cases randomly until one of them does not add additional coverage (e.g., until maximal coverage is achieved). Second, it selects test cases that maximized the Jaccard distance function with the already selected test cases. Experimental results show that of the above, ART-MIN is the best test case prioritization strategy. However, ART may be not effective when the failure  
Figure 1: Program spectra \(M\) and testing result vector \(R\). rate is low and the calculated Jaccard distance cost is higher than the cost of reducing the test execution times [22]. Fault-Exposing Potential (FEP): FEP is a coverage-based prioritization algorithm that guides the test case order. [PERSON] et al. [20] used a mutation analysis to obtain an approximation of the fault-exposing potential of a test case to reduce the test oracle. Such an approximation was obtained based on the PIE analysis (propagation, infection, and execution) [23]. Suppose we are given a program \(P\) and the test suite \(T\). First, they considered each test case \(t_{i}\) and each statement \(s_{j}\) in \(P\), and calculated the fault-exposing potential \(FEP(s\), \(t)\) of \(t_{i}\) on \(s_{j}\) as the ratio of mutations of \(s_{j}\) detected by \(t_{i}\) to the total number of mutations of \(s_{j}\). If \(t_{i}\) does not cover \(s_{j}\), this ratio is zero.