# The MADAG Strategy for Fault Location Techniques
## 3 The Proposed MADAG Strategy
### An Example  
To understand how the MADAG strategy works, we use an example program _Mid(_) with the spectrum of test cases and suspiciousness metrics as shown in Figure 4. This program (adapted from [PERSON] et al. [18] and [PERSON] [28]) takes three input values, namely \(x,y,\) and \(z\), and then provides the median value as its output. Suppose that the program has 6 test cases \(t_{1}\), \(t_{2}\)..., \(t_{6}\) and 13 statements \(s_{1}\), \(s_{2}\)..., \(s_{13}\). For the program _Mid(_), a faulty statement is at \(s_{7}\) (\(m=y_{i}\)). A black dot for a statement in a test case implies that the corresponding statement is executed in the corresponding test case. The program spectra refer to obtaining such dots for the execution traces of each test case. The test result of each case is P (passed) or F (failed). Based on the spectrum and testing results, the SBFL technique can calculate the suspiciousness scores for each statement and further rank them at the top or bottom. In this example, the three well-known similarity coefficients of the SBFL technique, namely Jaccard [17], Tarantula [18], and Ochiai [9], rank the \(s_{7}\) statement as the most suspicious statement. However, when our strategy is applied, the above-mentioned similarity coefficients of the SBFL technique can achieve the same effectiveness with fewer test cases (\(t_{6}\), \(t_{3}\), \(t_{2}\), and \(t_{5}\)). The process of the MADAG strategy for selecting test cases is shown in Table 2. The first column shows the \(k\) level in the MADAG tree. The second column refers to the set  
Figure 4: An example program _Mid(_) with suspiciousness metrics. \(ST\) that consists of test cases that have been selected. The third and fourth column shows the groups and each group that consists of the statements. The fifth column lists select test cases. The sixth column lists the \(M_{i}(t_{i})\) value of each test case. First, we select an initial test case \(t_{6}\), which is a failed test with the covered maximum number of statements. Then, we define the set of execution trace of \(t_{6}\) as the initial group \(G_{1}\), which covers 7 statements \(\{s_{1},s_{2},s_{3},s_{4},s_{6},s_{7},s_{13}\}\) and put the \(t_{6}\) into the set \(ST\) on level 1. In our strategy, the principle of selecting the test case can divide the number of statements of the group evenly on each level. We calculate \(M_{i}(t_{i})\) value to find the \(t_{target}\) test case with the minimal value of \(M_{i}(t_{i})\) in this round, and then put the \(t_{target}\) into the set \(SK\). Examples of \(k=2\), the \(M_{i}(t_{i})\) value for \(t_{1}\), \(t_{2}\), \(t_{3}\), \(t_{4}\), and \(t_{5}\) is 7, 3, 1, 1, and 5, respectively. Therefore, we can choose \(t_{3}\) or \(t_{4}\) for the \(ST\) according to the \(M_{i}(t_{i})\) value on level 2. To ease the description, we show only the process of choosing the test input encountered earlier when more than one test has the same \(M_{i}(t_{i})\) value, as shown in Table 2. So, we select \(t_{3}\) on level 2. The procedure is continued until \(ST\) contains test cases \(\{t_{6},t_{3},t_{2},t_{5}\}\). As all of the selected test cases have the same \(M_{i}(t_{i})\) value on level 5, the procedure would not select any test case immediately, thereby implying a convergence condition. The procedure of the MADAG strategy generates the binary tree shown in Figure 5a. As the number of statements in the group was less than 2 (the left of colon denotes group id, and the right of the colon denotes the number of the group in Figure 5), the group cannot be divided into any subgroups (e.g., \(G_{5}\) and \(G_{6}\)), but we still keep the numbered for the subgroups. After applying our strategy, we collect the program spectra and test results from the selected test case \(\{t_{6},t_{3},t_{2},t_{5}\}\). [PERSON], [PERSON], and [PERSON] all assigned the \(\hat{s}_{7}\) statement a high suspiciousness score by using only four test cases and the suspiciousness scores of them are shown in Figure 5b.