# The MADAG Strategy for Fault Location Techniques
## 3 The Proposed MADAG Strategy
### MADAG Strategy  
The statements covered by the initial failed test are divided into two coverage types: G\({}_{\text{cf}}\) and G\({}_{\text{uf}}\). G\({}_{\text{cf}}\) includes statements covered by the initial failed test, and Guf includes statements not covered by the initial failed test. Intuitively, the opportunity for faults in Guf is very low [18; 27]. Therefore, we do not consider that the G\({}_{\text{uf}}\) of the initial failed test in our study saves the cost of locating the fault. Furthermore, the statements of G\({}_{\text{cf}}\) can set the initial group in our strategy. We define the division operations as D\({}_{\text{0(1,1)}}\), D\({}_{\text{0(1,0)}}\), D\({}_{\text{0(0,1)}}\) \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Time** & **Name** & **Authors** & **Title 3** \\ \hline
2002 & [PERSON] & Chen et al. [17] & \(\frac{N_{sf}}{N_{sf}+N_{sf}+N_{sf}}\) \\
2005 & [PERSON] & Jones et al. [18] & \(\frac{\left(N_{sf}+N_{sf}\right)}{N_{sf}+N_{sf}/N}\) \\
2007 & [PERSON] et al. [1] & \(\frac{N_{sf}}{N_{sf}+N_{sf}}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Spectrum-based fault localization. and \(\mathrm{D}_{\mathrm{o(0,0)}}\) for the statement coverage condition. \(\mathrm{D}_{\mathrm{o(1,1)}}\) refers to both the current test case and the next selected test case that covers the statement. \(\mathrm{D}_{\mathrm{o(1,0)}}\) refers to the current test case that covers the statement and the next selected test case that does not. \(\mathrm{D}_{\mathrm{o(0,1)}}\) refers to the next selected test case that covers the statement and the current test case that does not. \(\mathrm{D}_{\mathrm{o(0,0)}}\) refers to both the current test case and the next selected test case, which do not cover the statement. We describe the division operation using an example in Figure 2.  
In this example, statements of the initial group \(G_{1}\) (\(G_{j}\), \(j\) denotes the group id) are covered by a failed test case, implying that the statements \(\{s_{1}\), \(s_{3}\), \(s_{4}\), \(s_{5}\), \(s_{6}\), \(s_{8}\), \(s_{10}\), \(s_{11}\), \(s_{12}\), \(s_{14}\), \(s_{16}\), \(s_{17}\), \(s_{19}\), \(s_{20}\)] may contain a fault. Further, we set the statements \(\{s_{1}\), \(s_{3}\), \(s_{4}\), \(s_{5}\), \(s_{6}\), \(s_{8}\), \(s_{10}\), \(s_{11}\), \(s_{12}\), \(s_{14}\), \(s_{16}\), \(s_{17}\), \(s_{19}\), \(s_{20}\)] as initial group \(G_{1}\). The trace of the 2 nd selected test case is different from the initial \(G_{1}\). The 2 nd selected test case would divide the initial group \(G_{1}\) into two subgroups, \(G_{2}\) [\(s_{1}\), \(s_{5}\), \(s_{8}\), \(s_{11}\), \(s_{12}\), \(s_{16}\), \(s_{19}\)] and \(G_{3}\) [\(s_{3}\), \(s_{4}\), \(s_{6}\), \(s_{10}\), \(s_{14}\), \(s_{17}\), \(s_{20}\)], which correspond to division operations \(D_{\mathrm{(1,1)}}\) and \(D_{\mathrm{(1,0)}}\), respectively. Further, the 3 rd selected test case may divide \(G_{2}\) and \(G_{3}\) into \(G_{4}\), \(G_{5}\), \(G_{6}\), and \(G_{7}\), which correspond to \(D_{\mathrm{(1,1)}}\), \(D_{\mathrm{o(1,0)}}\), \(D_{\mathrm{o(0,1)}}\), and \(D_{\mathrm{o(1,0)}}\), respectively. According to the previous coverage condition, we can learn of the next situation, in which \(D_{\mathrm{o(1,\cdot)}}\) can be divided into \(D_{\mathrm{(1,\cdot)}}\), and \(D_{\mathrm{(1,0)}}\), \(D_{\mathrm{o(0,\cdot)}}\) can be divided into \(D_{\mathrm{(0,1)}}\) and \(D_{\mathrm{o(0,0)}}\), and so on. Starting from group \(G_{1}\), the group can be divided into two subgroups: \(G_{2}\) and \(G_{3}\) when the 2 nd selected test case is input. Then, when the 3 rd selected test case is input, \(G_{2}\) may be divided into two subgroups: \(G_{4}\) and \(G_{5}\); \(G_{3}\) may be divided into two subgroups: \(G_{6}\) and \(G_{7}\), and so on. The procedure of the division group would generate a binary tree (called a MADAG tree), as shown in Figure 3. To facilitate the presentation of our strategy, we assigned each group a unique group id by level-order in the MADAG tree.