基于两个等级分布的平均随机TBFL方法

运用测试集对程序错误语句定位算法,现在被统称为TBFL(testing based fault localization)方法。目前通行的算法,一般都没有利用测试员、程序员关于测试用例和程序的先验知识,致使这些"资源"白白浪费掉。随机TBFL方法是一类新的TBFL方法,其精神就是在随机理论的框架下,把这些先验知识和实际测试活动结合起来,从而对程序错误语句更好地定位。随机TBFL算法也可以看成是这种类型算法的一般"模式",人们可以从这个一般性的模式里,开发出不同的算法。基于Santelices等人的思想,对随机TBFL算法作了改进。主要是从测试结果里,构造执行矩阵E和功效矩阵F两个工具,通过它们结合测试集和程序先验知识,对程序语句出错可能性引入两个级别的排序,然后对这两个排序进行"平均",得到程序语句出错可能性的平均等级排序,它可以作为程序员改正程序错误的导向。还提出两个有关不同TBFL算法比较标准,就这两个标准,在一些具体实例上,该算法和其他一般方法以及随机TBFL方法对比,效果令人满意。     

基于测试结果调整语句出错概率方法

运用测试集对程序错误语句定位的算法被统称为TBFL方法。目前通行的TBFL算法一般都没有利用测试员、程序员关于测试用例和程序的先验知识,致使这些“资源”白白浪费。随机TBFL就是一类新型TBFL方法,其精神就是在随机理论的框架下,把这些先验知识和实际测试活动结合起来,从而对程序错误语句更好地定位。随机TBFL算法可以看成是这种类型算法的一般“模式”,人们可以从这个一般的模式里开发出不同的算法。基于测试结果调整语句出错概率的方法就是将随机TBFL算法中关于程序、测试集的先验知识和具体测试活动分离开来,根据测试结果再先后注入人们对测试集和程序的先验知识,从而更好地定位错误语句。在一些实例上,通过把新算法和随机TBFL算法进行对比,发现新算法是可取的。提出了三个有关不同TBFL算法比较标准,从这三个标准考察,新算法在上述实例上也是良好的。     

等级平均随机TBFL方法

运用测试集对程序错误语句定位的算法,现在被统称为TBFL(testing based fault localization)方法。目前通行的算法一般都没有利用测试员、程序员关于测试用例和程序的先验知识,致使这些"资源"白白浪费掉。文献[12]引入了一类新的随机TBFL方法,其精神就是在随机理论的框架下,把这些先验知识和实际测试活动结合起来,从而对程序错误语句更好地定位。文献[12]提出的算法可以看成是这种类型算法的一般"模式",人们可以根据这个一般性的模式开发出不同的算法。基于文献[13]的思想,对文献[12]中的算法做了改进。主要是根据测试结果,构造执行矩阵E和功效矩阵F两个工具,并结合测试集和程序先验知识,对程序语句出错可能性引入两个级别的排序,然后对这两个排序进行"平均",得到程序语句出错可能性的平均等级排序,它可以作为程序员改正程序错误的导向。还提出两个有关不同TBFL算法的比较标准,根据这两个标准,在一些具体实例上,将所提算法和其他一般方法以及文献[12]中的方法进行了对比,结果显示所提算法的效果令人满意。     

TBFL和SAFL方法熵分析

为TBFL(testing-based fault localization)方法和SAFL(similarity-aware fault localization)方法构造了熵模型,并用该模型对Dicing方法、TARANTULA方法、SAFL方法在一个实例上进行分析比较。结果表明,熵模型可以为构造以及分析TBFL方法和SAFL方法提供一个原则性框架。     

组合认知复杂度的程序谱软件错误定位方法

基于程序谱的软件错误定位(spectrum-based fault localization,SBFL)技术收集测试用例结果和语句覆盖信息,用以计算每条语句的可疑度值.认知复杂度是软件复杂性度量工具,其值高的代码较易出错.为提升错误定位性能,提出一种语句级认知复杂度和SBFL相组合的方法对语句排序.当多条语句可疑度值相等时,新方法优先检查认知复杂度高的语句.测试数据集有925个错误版本,包含Java、C和C++项目.实验结果证实,加入认知复杂度后,传统的SBFL技术能减少待排查语句.     

面向众包软件开发的错误定位方法

在软件开发中,错误定位是修复软件缺陷的必要前提.为此,研究者们提出了一系列自动化的错误定位方法.这些方法利用了测试用例运行时的覆盖路径和运行结果等信息,大幅减少了定位错误代码的难度.在竞争性众包软件开发中,往往存在多个竞争性实现（解决方案）,提出一种专门面向众包软件工程的错误定位方法.主要思想是,在定位错误语句时,将其多个竞争性实现作为参考程序.针对程序中的各个语句,在参考程序中搜索参考语句,并利用参考语句计算其错误概率.给定一个错误程序和相应的测试用例,首先运行测试用例并使用广泛流行的基于频谱的错误定位方法计算其初始错误概率.然后,根据此语句与其参考语句的相似性调整错误概率.在118个真实的错误程序上进行实验,结果表明所提方法相比基于频谱的方法,定位错误的成本降低了25%以上.     

基于条件执行切片谱的多错误定位

基于程序谱的错误定位技术由于其较高的定位效率已成为当前软件调试领域研究热点之一.这种技术通常根据测试覆盖信息计算程序语句发生错误的可疑度来进行错误定位.然而,这种技术会随着程序中错误数目的增多效率不断下降.鉴于此,提出了一种基于条件执行切片谱的多错误定位技术(conditioned execution slicing spectrum-based multiple fault localization,CESS-MFL),以提高多错误定位的效率.CESS-MFL技术首先根据输入变量的谓词条件构建错误相关条件执行切片的谱矩阵,然后依次计算错误相关条件执行切片中的元素(语句或语句块)的可疑度,并生成可疑度报告.实验验证了CESS-MFL技术比当前流行的基于程序谱的Tarantula技术、基于程序切片的Intersection技术、Union技术有更高的多错误定位效率,并且可在有效的时间和空间复杂度内完成.     

一种基于单条程序执行路径的错误定位方法

当程序在测试中发生错误时,将形成一条错误的程序执行路径,程序员将会花费很多精力去检测程序代码和定位最终的程序错误．提出一种基于单条程序执行路径的错误定位方法,该方法通过对程序进行反向执行,计算出多个最弱前置条件及其相对应的疑似错误语句集,并生成错误定位树,来辅助程序员进行快速错误定位．对西门子测试数据集进行的实验表明了该方法具有良好的效果．     

基于关键谓词的程序错误定位方法

将程序切片技术应用于程序错误定位可以大量减少需要测试的语句数。提出一种基于关键谓词的程序错误定位方法,从程序中找出能影响输出结果的关键谓词,对该谓词和错误输出语句进行数据切片,并引入代码优先技术。该方法考虑了数据依赖和控制依赖,能实现准确快速的错误定位。     

针对基于变异错误定位的一种动态变异执行策略

在软件调试过程中,如何快速、精确地定位程序中的错误代码是软件开发人员普遍关注的问题。基于变异的错误定位方法是一种通过分析被测程序与程序变异体之间的行为相似性来估计语句出错概率、进行错误定位的方法。该方法有较高的错误定位精确度,但由于需对大量程序变异体执行测试用例集,因此其变异执行开销较大。为此提出了一种动态变异执行策略,它通过搜集测试用例执行信息,动态地调整变异体及测试用例的执行顺序,以减少其变异执行开销。实验结果表明,在6个程序包的127个错误版本上,应用提出的动态变异执行策略可在保证错误定位精确度的前提下,减少23%~78%的变异执行开销,显著提高了基于变异的错误定位方法的效率。     

On similarity-awareness in testing-based fault localization

In the process of software development and maintenance, software debugging is an inevitable and time-consuming task. To accelerate software debugging, various approaches have been proposed to automate fault localization. Among them, testing-based fault-localization approaches are most promising, which use the execution information of many test cases to localize the faults. However, these existing testing-based fault-localization approaches ignore the similarity between test cases, which may harm the effectiveness of these approaches according to our previous research. Therefore, in this paper we propose a similarity-aware fault-localization approach, which takes each test case as a fuzzy set to deal with the similarity between test cases and calculates statements’ suspicions based on the probability theory. To investigate whether SAFL can address the similarity issue effectively, we manually injected redundant test cases in a test suite and performed an experimental study on the original test suite and the test suite with redundancy, respectively. The experimental results demonstrate that in our experiments SAFL is an effective fault-localization approach, whether there is manually injected redundancy in the test suite. To compare SAFL with most existing testing-based fault-localization approaches, we performed another experimental study on Siemens program suite, which is extensively used in the evaluation of many other testing-based fault-localization approaches. This experimental study confirms the effectiveness of SAFL. Based on the two experimental studies, it seems that in our experiments SAFL cannot only deal with test suites containing much redundancy effectively but also perform effectively for test suites without much redundancy. A preliminary version of this paper appears in (Hao et al. 2005a).     

IPSETFUL: an iterative process of selecting test cases for effective fault localization by exploring concept lattice of program spectra

Fault localization is an important and challenging task during software testing. Among techniques studied in this field, program spectrum based fault localization is a promising approach. To perform spectrum based fault localization, a set of test oracles should be provided, and the effectiveness of fault localization depends highly on the quality of test oracles. Moreover, their effectiveness is usually affected when multiple simultaneous faults are present. Faced with multiple faults it is difficult for developers to determine when to stop the fault localization process. To address these issues, we propose an iterative fault localization process, i.e., an iterative process of selecting test cases for effective fault localization (IPSETFUL), to identify as many faults as possible in the program until the stopping criterion is satisfied. It is performed based on a concept lattice of program spectrum (CLPS) proposed in our previous work. Based on the labeling approach of CLPS, program statements are categorized as dangerous statements, safe statements, and sensitive statements. To identify the faults, developers need to check the dangerous statements. Meantime, developers need to select a set of test cases covering the dangerous or sensitive statements from the original test suite, and a new CLPS is generated for the next iteration. The same process is proceeded in the same way. This iterative process ends until there are no failing tests in the test suite and all statements on the CLPS become safe statements. We conduct an empirical study on several subject programs, and the results show that IPSETFUL can help identifymost of the faults in the program with the given test suite. Moreover, it can save much effort in inspecting unfaulty program statements compared with the existing spectrum based fault localization techniques and the relevant state of the art technique.     

ContextAug: model-domain failing test augmentation with contextual information

In the process of software development, the ability to localize faults is crucial for improving the efficiency of debugging. Generally speaking, detecting and repairing errant behavior at an early stage of the development cycle considerably reduces costs and development time. Researchers have tried to utilize various methods to locate the faulty codes. However, failing test cases usually account for a small portion of the test suite, which inevitably leads to the class-imbalance phenomenon and hampers the effectiveness of fault localization. Accordingly, in this work, we propose a new fault localization approach named ContextAug. After obtaining dynamic execution through test cases, ContextAug traces these executions to build an information model; subsequently, it constructs a failure context with propagation dependencies to intersect with new model-domain failing test samples synthesized by the minimum variability of the minority feature space. In contrast to traditional test generation directly from the input domain, ContextAug seeks a new perspective to synthesize failing test samples from the model domain, which is much easier to augment test suites. Through conducting empirical research on real large-sized programs with 13 state-of-the-art fault localization approaches, ContextAug could significantly improve fault localization effectiveness with up to 54.53%. Thus, ContextAug is verified as able to improve fault localization effectiveness.     

Experimental Evaluation of Program Slicing for Fault Localization

Debugging large and complex software systems requires significant effort since it is very difficult to localize and identify faults. Program slicing has been proposed to efficiently localize faults in the program. Despite the fact that a number of debug systems using program slicing, have been developed, the usefulness of this method to fault localization has not been sufficiently evaluated. This paper aims to experimentally evaluate the usefulness of the program slicing method to fault localization. In order to conduct the experiment, we first developed a debug tool based on program slicing, after which two experimental projects were conducted, in which subjects (debuggers) were divided into two groups. A program that includes several faults is given to each subject of the group. Each subject in Group 1 localizes the faults by using the slicing-based method, whereas in Group 2 each subject localizes the faults by using the conventional debugger-based method. Finally, the effectiveness of program slicing is analyzed by comparing the data collected from both groups. As the results of these experiments, we confirm that the program slicing method is indeed useful to localize program faults.     

Test input reduction for result inspection to facilitate fault localization

Testing-based fault-localization (TBFL) approaches often require the availability of high-statement-coverage test suites that sufficiently exercise the areas around the faults. However, in practice, fault localization often starts with a test suite whose quality may not be sufficient to apply TBFL approaches. Recent capture/replay or traditional test-generation tools can be used to acquire a high-statement-coverage test collection (i.e., test inputs only) without expected outputs. But it is expensive or even infeasible for developers to manually inspect the results of so many test inputs. To enable practical application of TBFL approaches, we propose three strategies to reduce the test inputs in an existing test collection for result inspection. These three strategies are based on the execution traces of test runs using the test inputs. With the three strategies, developers can select only a representative subset of the test inputs for result inspection and fault localization. We implemented and applied the three test-input-reduction strategies to a series of benchmarks: the Siemens programs, DC, and TCC. The experimental results show that our approach can help developers inspect the results of a smaller subset (less than 10%) of test inputs, whose fault-localization effectiveness is close to that of the whole test collection.     

一种场景敏感的高效错误检测方法

定值-引用类错误是一类非常重要且常见的错误.当前,对这类错误的检测很难同时达到高精度和高可扩展性.通过合理组合敏感和不敏感的检测方法并控制两类方法的实施范围,可以同时达到高检测精度和高可扩展性.提出一种新颖的场景敏感的检测方法,该方法根据触发状态对潜在错误语句分类,识别不同类别语句的触发场景并实施不同开销的检测,在不降低精度的同时最小化检测开销.设计了一个多项式时间复杂度的流敏感、域敏感和上下文敏感的场景分析以进行分类,并基于程序依赖信息识别触发场景,仅对必要的触发场景实施路径敏感的检测.为上述方法实现了一种原型系统——Minerva.通过使用空指针引用错误检测为实例研究以及总代码规模超过290万行,最大单个应用超过200万行的应用验证,用例实验结果表明,Minerva的平均检测时间比当前先进水平的路径敏感检测工具Clang-sa和Saturn分别快3倍和46倍.而Minerva的误报率仅为24%,是Clang-sa和Saturn误报率的1/3左右,并且Minerva未发现漏报已知错误.上述数据表明,所提出的场景敏感的错误检测方法可同时获得高可扩展性和高检测精度.