# Performance Analysis of Maximal Risk Evaluation Formulas for Spectrum-Based Fault Localization
## 2 Background
### Risk Evaluation Formulas  
After constructing the program spectrum information, a risk evaluation formula is designed to compute a risk value which is used to indicate the likelihood of a program entity being faulty. The program entity that has a greater risk value will have a higher chance of being faulty. Many classical formulas have been proposed and widely used, such as Tarantula [23], Jaccard [24], Ochiai [7], Wong formulas [9; 25; 26], Naish formulas [13], and genetic programming (GP) formulas [14; 27]. The program entity used in these formulas are at the statement level. The program statement with greater risk value is more likely to contain fault. Debuggers then rank the program statements in descending order of their risk values. As a result, debuggers should inspect those program statements appearing on the top of the ranking list. Therefore, it is fundamental to choose the most effective formula to make faulty statements rank as high as possible. In order to analyze the effectiveness of various formulas, both empirical and theoretical studies have been conducted by many researchers. However, the empirical analysis strongly depends on the experimental setup, in which subject programs, fault types, and the size of test suite are the most effective threats to experimental results. Therefore, to solve the inaccuracy problem in empirical study, some theoretical analysis are proposed to investigate the performance of risk evaluation formulas. In [11; 14; 15], the investigation is on comparing two risk evaluation formulas and identifying maximal risk evaluation formula in a group of risk evaluation formulas. Please be reminded that the risk evaluation formula is used by the debugger to generate a ranking list of program spectra. If a formula can \"put\" the faulty spectrum in a higher position in the ranking list than that of another formula, the former formula is said to perform better than the latter formula. In the first aspect, the study of [PERSON] et al. [14] divides program statements in the program under test into three mutually exclusive subsets: the subset that contains all statements with risk values greater than (denoted as \(S_{B}^{R}\)), equal to (denoted as \(S_{F}^{R}\)), and smaller than (denoted as \(S_{A}^{R}\)) that of the faulty statement in the program, assuming the program only contains one faulty statement where \(R\) is the risk evaluation formula. Please note that the faulty statement must be in \(S_{F}^{R}\) because it contains all statements that have the same risk value as the faulty statement. Loosely speaking, these three subsets divide the ranking list into three parts: the top part being \(S_{B}^{R}\) because its statements appear \"before\" the faulty statement, since its risk values are greater than that of the faulty statement; the middle part being \(S_{F}^{R}\); and the bottom part being \(S_{A}^{R}\) because it appears \"after\" the faulty statement. Given any two formulas \(R_{1}\) and \(R_{2}\), a program with a faulty statement and a test suite, \(R_{1}\) is said to be equivalent to \(R_{2}\) (denoted by \(R_{1}\leftrightarrow R_{2}\)) when \(S_{B}^{R_{1}}=S_{B}^{R_{2}}\), \(S_{F}^{R_{1}}=S_{F}^{R_{2}}\) and \(S_{A}^{R_{1}}=S_{A}^{R_{2}}\). While in [12; 13], two equivalent risk evaluation formulas require strictly identical ranking lists. Furthermore, \(R_{1}\) is said to be better than \(R_{2}\) (denoted by \(R_{1}\to R_{2}\)) if \(S_{B}^{R_{1}}\subseteq S_{B}^{R_{2}}\) and \(S_{A}^{R_{2}}\subseteq S_{A}^{R_{1}}\). This is because \(R_{1}\) will place the faulty statement earlier in the ranking list than \(R_{2}\). As a result, debugger using the ranking list from \(R_{1}\) will get to reach the faulty statement earlier than using \(R_{2}\). As can be seen from the definition of \"better\", the set of all risk evaluation formulas equipped with the \"better\" relation becomes a partially ordered set (poset). As a result, the maximal elements in this poset will then be referred to as \"maximal risk evaluation formulas\"  
Figure 1: Essential information for SBFL.