A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization

By Xiaoyuan Xie, Tsong Yueh Chen, Fei-Ching Kuo, Baowen Xu. TSEM, 2013

362 citations recorded by the source corpus.

An important research area of Spectrum-Based Fault Localization (SBFL) is the effectiveness of risk evaluation formulas. Most previous studies have adopted an empirical approach, which can hardly be considered as sufficiently comprehensive because of the huge number of combinations of various factors in SBFL. Though some studies aimed at overcoming the limitations of the empirical approach, none of them has provided a completely satisfactory solution. Therefore, we provide a theoretical investigation on the effectiveness of risk evaluation formulas. We define two types of relations between formulas, namely, equivalent and better. To identify the relations between formulas, we develop an innovative framework for the theoretical investigation. Our framework is based on the concept that the determinant for the effectiveness of a formula is the number of statements with risk values higher than the risk value of the faulty statement. We group all program statements into three disjoint sets with risk values higher than, equal to, and lower than the risk value of the faulty statement, respectively. For different formulas, the sizes of their sets are compared using the notion of subset. We use this framework to identify the maximal formulas which should be the only formulas to be used in SBFL.

Subfields: Computer Networks and Communications, Software

View Paper: https://www.semanticscholar.org/paper/5dabb0f044e7818a4ccc3b0f018afccd5341f5a6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Yihao Li
2. Shin Yoo
3. David Lo
4. Ruizhi Gao
5. W. E. Wong
6. Yingfei Xiong

In Software

1. Yingfei Xiong
2. Xin Xia
3. Pavneet Singh Kochhar
4. Yihao Li
5. Shin Yoo
6. David Lo
7. Dongsun Kim
8. Lu Zhang

Citations in the corpus

• TBar: revisiting template-based automated program repair (2019, background): “GZoltar [9] and Ochiai have been widely integrated into APR systems since their effectiveness has been demonstrated in several empirical studies [56, 65, 73, 78].”
• Ask the Mutants: Mutating Faulty Programs for Fault Localization (2014, methodology): “Since mutation operators vary significantly in their nature, mutation-based approaches such as MUSE may not yield itself to theoretical analysis as naturally as the spectrum-based ones, for which hierarchy and equivalence relations have been shown with proofs [28].”
• The DStar Method for Effective Software Fault Localization (2014, methodology): “To overcome this problem, authors of [47] impose an additional constraint such that and must be examined in the same order.”
• Precise Condition Synthesis for Program Repair (2016, result): “existing empirical and theoretical studies [27], [28], [29].”
• Practitioners' expectations on automated fault localization (2016, background): “…papers on automatic repair (e.g., [18,25]), empirical study on debugging (e.g., [36]), theoretical analysis of existing debugging techniques (e.g., [53]), failure reproduction (e.g., [14]), debugging comprehension (e.g., [18, 39]), failure clustering (e.g., [12]), bug prediction (e.g., [37]), and…”
• The strength of random search on automated program repair (2014, methodology): “Generally, automated program repair consists of three steps: fault localization [42, 17], patch generation, and patch validation.”