基于软件自动修复评估缺陷定位技术的工具:GenProg-FL

虽然缺陷定位技术和软件错误自动修复技术已经得到一定的发展,但是软件的修复工作仍然需要程序员投入大量的时间和精力。大多数开发者仍然使用传统调试技术(例如断点)来进行手工的调试,缺陷定位技术的研究成果并没有较好地运用到实际的修复工作中。近来,软件错误自动修复技术得到了快速的发展和广泛的关注。在软件错误自动修复工作中,利用缺陷定位技术自动定位错误代码是必需的,而定位的精度直接影响到补丁的生成,从而对修复的效果产生较大的影响。GenProg-FL工具可以接受不同的缺陷定位技术去自动修复故障程序。同样,使用GenProg-FL可以从软件自动修复的角度评估现有的基于程序谱的缺陷定位技术定位的有效性。     

基于程序频谱的动态缺陷定位方法研究

基于程序频谱的动态缺陷定位是软件自动化调试研究中的一个热点问题,通过搜集测试用例的程序频谱和执行结果,基于特定模型以定位缺陷语句在被测程序内的可能位置.对近些年来国内外学者在该研究领域取得的成果进行系统总结:首先,给出预备知识和基本假设;随后,提出缺陷定位研究框架并识别出框架内一系列可影响缺陷定位效果的内在影响因素,包括程序频谱构造方式、测试套件构成和维护、内在缺陷数量、测试用例预言设置、用户反馈和缺陷修复开销等;接着,对实证研究中采用的评测指标和评测程序进行总结和分析;然后,对缺陷定位方法在一些特定测试领域中的应用进行总结;最后,对该领域未来值得关注的研究方向进行了展望.     

基于指针神经网络的细粒度缺陷定位

软件缺陷定位是指找出与软件失效相关的程序元素. 当前的缺陷定位技术仅能产生函数级或语句级的定位结果. 这种粗粒度的定位结果会影响人工调试程序和软件缺陷自动修复的效率和效果. 专注于细粒度地识别导致软件缺陷的具体代码令牌, 为代码令牌建立抽象语法树路径, 提出基于指针神经网络的细粒度缺陷定位模型来预测出具体的缺陷代码令牌和修复该令牌的具体操作行为. 开源项目中的大量缺陷补丁数据集包含大量可供训练的数据, 且基于抽象语法树构建的路径可以有效捕获程序结构信息. 实验结果表明所训练出的模型能够准确预测缺陷代码令牌并显著优于基于统计的与基于机器学习的基线方法. 另外, 为了验证细粒度的缺陷定位结果可以贡献于缺陷自动修复, 基于细粒度的缺陷定位结果设计两种程序修复流程, 即代码补全工具去预测正确令牌的方法和启发式规则寻找合适代码修复元素的方法, 结果表明两种方法都能有效解决软件缺陷自动修复中的过拟合问题.     

面向自动修复并融合失效场景的缺陷定位方法

为了应对日益增长的软件修复开销,研究高效的软件自动修复技术成为学术界和工业界的共识。缺陷定位作为自动修复技术的前端,是实现快速准确自动修复的关键,其精度直接影响自动修复的性能。然而,初步研究表明,现有缺陷定位技术缺乏对自修复需求的考虑,对自修复算法支持有限。有必要研究面向自修复的高精度自动化缺陷定位技术,以提升自修复性能。因此,提出了失效场景的缺陷定位方法来应对该问题。提出的方法首先采用程序切片技术,构造出与失效相关的场景;然后对失效场景的各个元素实施可疑值度量;最后将可疑值度量化的场景交给自动修复技术实施修复。初步实验结果表明,本缺陷定位方法能有效提升自动修复性能。     

一种基于信息量的缺陷定位方法

缺陷定位是软件调试过程中的重要环节,它通过利用程序信息和测试信息来定位软件中的错误.借助于事件信息量,提出一种基于事件信息量的缺陷定位方法——SIQ(suspiciousness based on information quantity).SIQ方法根据测试信息中不同事件的类型及其发生的概率,结合语句的执行信息,动态计算和调整缺陷定位的结果.通过大量的实验分析和对比,SIQ方法在多个数据集上表现出了很好的稳定性,与几种现有的缺陷定位方法相比,SIQ方法的缺陷定位效果也更加准确.     

基于条件概率模型的缺陷定位方法

缺陷定位是软件调试的重要阶段,依赖程序频谱信息实现软件缺陷定位,是当前比较行之有效的方法.基于频谱缺陷定位方法应用的前提是,程序频谱和执行结果之间存在的潜在关联.通过经验性分析两者之间的内在关联,借助于统计学的条件概率思想,构建了用以量化分析两者关系强弱的P模型,并基于此提出了基于条件概率的缺陷定位方法.以Siemens套件中的7个程序、Space程序和3个Unix工具程序为基准评测对象,与已有的15种经典缺陷定位方法进行了对比实验.实证研究结果表明,该方法总体上具有更好的缺陷定位效果.     

基于程序频谱的两阶段缺陷定位方法

缺陷定位是软件质量保证中关键且困难的一项工作,随着软件规模的增大,人工进行缺陷定位的成本越来越高,自动化缺陷定位技术成为研究热点。现有的基于程序频谱的缺陷定位技术可以将缺陷定位到程序语句,但对于大型复杂的软件系统,这种定位方法将带来较大的时间花销。针对此问题,提出一种基于程序频谱的两阶段缺陷定位方法,第一阶段为粗粒度定位,将缺陷定位到程序模块;第二阶段为细粒度定位,在定位的程序模块中再将缺陷定位到语句;最后输出可疑语句推荐列表,辅助开发人员的调试工作。实验结果表明,相比于传统的方法,该方案在保证定位效果的前提下平均减少了10.24%的定位时间。     

一种基于遗传算法的多缺陷定位方法

基于程序频谱的缺陷定位方法可以有效地辅助开发人员定位软件内部缺陷,但大部分已有自动化方法在解决多缺陷定位问题时表现不佳,部分效果尚可的方法因复杂度较高或需要开发人员较多交互而仍需进一步改善.为改善上述问题,提出一种基于遗传算法的多缺陷定位方法 GAMFal,具体来说:首先基于搜索的软件工程思想对多缺陷定位问题进行建模,构建了候选缺陷分布的染色体编码方式,并基于扩展的Ochiai系数计算个体的适应度值;随后使用遗传算法在解空间中搜索具有最高适应度值的候选缺陷分布,在终止条件被满足后返回最优解种群;最后根据这个种群对程序实体进行排序.这样开发人员可以依次对程序实体进行检查并最终确定多个缺陷的具体位置.实证研究以Siemens套件中的7个程序和Linux的3个程序(gzip、grep和sed)作为评测对象,并扩展传统的定位方法评测标准EXAM至EXAMF和EXAML,通过与其他经典的缺陷定位方法(Tarantula、Improved Tarantula及Ochiai)进行对比,并通过Friedman检测和最小显著性差异测试可得,提出的GAMFal方法在整体定位效率方面优于传统方法,且需要更少的人工交互.除此之外,GAMFal的执行时间也在可接受的范围之内.     

基于高斯过程的缺陷定位方法

在软件系统中,缺陷定位是缺陷修复的一个关键环节,如果能将缺陷自动定位到很小的范围,将会极大地降低缺陷修复的难度.基于高斯过程提出了一种缺陷定位方法（GPBL）,即针对每个缺陷,向开发人员推荐这个缺陷可能存在于哪些源文件中,从而帮助开发人员快速修复缺陷.为了验证方法的有效性,采集了开源软件Eclipse 和Argouml 中的数据,实验结果表明,高斯过程缺陷定位的查全率和查准率平均分别为87.16%和78.90%.与基于LDA的缺陷定位方法进行比较,表明高斯过程更能准确定位缺陷的位置.     

方法级别的细粒度软件缺陷定位方法

当软件缺陷报告在跟踪系统中被指派给开发人员进行缺陷修复之后,缺陷修复人员就需要根据提交的缺陷报告来进行软件缺陷定位,并做出相应的代码变更,以修复该软件缺陷.在缺陷修复的整个过程中,软件缺陷定位占用了开发人员大量的时间.提出了一种方法级别的细粒度软件缺陷定位方法MethodLocator,以提高软件修复人员的工作效率.MethodLocator首先对缺陷报告和源代码方法体利用词向量（word2vec）和TF-IDF结合的方法进行向量表示;然后,根据源代码文件中方法体之间的相似度对方法体进行扩充;最后,通过对扩充后的方法体和缺陷报告计算其余弦距离并排序,来定位为修复软件缺陷所需做出变更的方法.在4个开源软件项目ArgoUML、Ant、Maven和Kylin上的实验结果表明,MethodLocator方法优于现有的缺陷定位方法,它能够有效地将软件缺陷定位到源代码的方法级别上.     

Effective software fault localization using predicted execution results

Software has become ubiquitous in our daily lives, and with its increasing functionality and complexity comes a frequently tedious and prolonged debugging process. Of the three activities in program debugging (failure detection, fault localization, and bug fixing), the focus of this paper is on the first, failure detection, under the condition that there is no test oracle that can be used to automatically determine the success or failure of all the executions. More precisely, the outputs for many executions have to be verified manually, or the expected outputs are not even available. We want to determine whether there is a solution to help programmers predict the execution results. How good are these predicted results when they are used to help programmers find the locations of bugs? A framework is proposed to reduce the effort on output verification using a strategy based on the Hamming distance or K-Means clustering to predict results of test executions. Such data and the statement coverage of each test case are used to compute the suspiciousness of each statement according to a fault localization technique and produce a ranking for examination to locate bugs. Case studies using 22 programs and seven fault localization techniques were conducted to evaluate the fault localization effectiveness of the proposed framework on 1203 faulty versions, some of which have a single bug and others with multiple bugs. A discussion on factors that may affect the accuracy of execution result prediction and the resulting fault localization effectiveness is also presented. Our data suggests that, in general, with respect to fault localization techniques using execution results verified against the expected outputs, those using predicted execution results can be even more effective than (by examining a smaller number of statements to locate the first faulty statement) or as good as the former (the verified).     

面向软件错误定位与理解的测试执行离散特征筛选

软件错误定位与错误理解是软件调试过程中的重要步骤,然而调试人员利用基于覆盖分析的软件错误定位获取的可疑度,从高到低静态分析每条程序语句的检查方式,与实际软件调试过程并不相符。为了能够筛选更有助于理解错误根源的测试执行,尤其是致使程序失效的失效执行,帮助调试人员进行动态差异化分析,针对失效执行提出基于高可疑度覆盖率、揭示错误潜力和覆盖语句可疑度离散特征的3种优先级策略,针对成功执行提出加权余弦相似度匹配策略。通过将3种失效执行优先级策略与随机选择在常用错误定位技术中进行实验对比,验证了基于覆盖语句可疑度离散特征的失效执行筛选策略能够对筛选前后的错误理解工作量变化产生更强的积极影响和更弱的消极影响,并能够在相同工作量下理解更多的错误,进而更有助于将错误定位结果应用于错误根源的理解。     

示例演化驱动的学生程序自动修复

已有的程序自动化调试研究大多面向工业软件,而学生程序调试具有缺陷数多、类型复杂等特有难点问题,因此,针对学生程序设计应用背景,研究程序自动修复方法,利用模板示例程序指导补丁的演化.改进了遗传编程算法,包括适应度的计算、变异体的生成方式和变异位置及操作的选择方式,使其更加适合修复学生程序.提出了基于示例的静态错误定位方法,能够识别缺陷程序和参考程序差异和可能的变异操作,有效地缩小补丁的搜索空间以提高修复的准确性.提出了基于执行值序列的变量映射方法,以降低变异体的编译错误,提高修复的准确性.在此基础上,设计并实现了示例演化驱动的Java学生程序自动修复系统.实验结果表明,该方法可以修复含有多缺陷学生程序,对于所用的测试集,当学生程序只有1个~2个错误时,修复率将近100%;当含有3个缺陷时,修复率约为70%;当含有4个及以上缺陷时,修复率约为50%.     

Evaluating the usage of fault localization in automated program repair: an empirical study

Fault localization techniques are originally proposed to assist in manual debugging by generally producing a rank list of suspicious locations.With the increasing popularity of automated program repair,the fault localization techniques have been introduced to effectively reduce the search space of automated program repair.Unlike developers who mainly focus on the rank information,current automated program repair has two strategies to use the fault localization information:suspiciousness-first algorithm(SFA)based on the suspiciousness accuracy and rank-first algorithm(RFA)relying on the rank accuracy.However,despite the fact that the two different usages are widely adopted by current automated program repair and may result in different repair results,little is known about the impacts of the two strategies on automated program repair.In this paper we empirically compare the performance of SFA and RFA in the context of automated program repair.Specifically,we implement the two strategies and six well-studied fault localization techniques into four state-of-the-art automated program repair tools,and then use these tools to perform repair experiments on 60 real-world bugs from Defects4J.Our study presents a number of interesting findings:RFA outperforms SFA in 70.02%of cases when measured by the number of candidate patches generated before a valid patch is found(NCP),while SFA performs better in parallel repair and patch diversity;the performance of SFA can be improved by increasing the suspiciousness accuracy of fault localization techniques;finally,we use SimFix that deploys SFA to successfully repair four extra Defects4J bugs which cannot be repaired by SimFix originally using RFA.These observations provide a new perspective for future research on the usage and improvement of fault localization in automated program repair.     

A Hardware Memory Race Recorder for Deterministic Replay

As hardware vendors transition to multicore chips, software vendors face increased software reliability challenges. To effectively debug software in this new world, developers must be able to replay executions that exhibit a bug so that they can zero in on concurrency bugs - especially intermittent ones. Such deterministic replay also aids fault detection and recovery, intrusion detection, and the like. Deterministic replay requires both a recorder and a replayer. The recorder logs information during multithreaded program execution that is sufficient to enable deterministic replay. In the postmortem analysis, the replayer uses the logged information, together with the program binary, to faithfully replay the original execution. The replay will always exercise the same bugs and produce the same outputs. Clearly, an investment in modest chip resources has great potential to ease the challenges of debugging the multithreaded software that both users and vendors will continue to demand     

WAS: A weighted attribute-based strategy for cluster test selection

In past decades, many techniques have been proposed to generate and execute test cases automatically. However, when a test oracle does not exist, execution results have to be examined manually. With increasing functionality and complexity of today's software, this process can be extremely time-consuming and mistake-prone. A CTS-based (cluster test selection) strategy provides a feasible solution to mitigate such deficiency by examining the execution results only with respect to a small number of selected test cases. It groups test cases with similar execution profiles into the same cluster and selects them from each cluster. Some well-known CTS-based strategies are one per cluster, n (a predefined value which is greater than 1) per cluster, adaptive sampling, and execution-spectra-based sampling (ESBS). The ultimate goal is to reduce testing cost by quickly identifying the executions that are likely to fail. However, improperly grouping the test cases will significantly diminish the effectiveness of these strategies (by examining results of more successful executions and fewer failed executions). To overcome this problem, we propose a weighted attribute-based strategy (WAS). Instead of clustering test cases based on the similarity of their execution profiles only once like the aforementioned CTS-based strategies, WAS will conduct more than one iteration of clustering using weighted execution profiles by also considering the suspiciousness of each program element (statement, basic block, decision, etc.), where the suspiciousness in terms of the likelihood of containing bugs can be computed by using various software fault localization techniques. Case studies using seven programs (make, ant, sed, flex, grep, gzip, and space) and four CTS-based strategies (one per cluster sampling, n per cluster sampling, adaptive sampling, and ESBS) were conducted to evaluate the effectiveness of WAS on 184 faulty versions containing either single or multiple bugs. Experimental results suggest that the proposed WAS strategy outperforms other four CTS-based strategies with respect to both recall and precision such that output verification is focused more strongly on failed executions.     

软件故障定位技术进展

故障定位是调试过程中一项耗时费力的工作。为了降低调试成本,并辅助开发人员定位和修复软件故障,软件故障定位技术通过审查源代码、分析测试过程的软件行为和测试结果来定位包含故障的代码片段。综述了近期故障定位领域相关成就,分类介绍了各种代表性的故障定位方法的基本原理和建模技术,讨论了这些故障定位技术的贡献以及它们之间的主要区别,给出了常用的故障定位效果基准测试集和度量方法,展望了故障定位技术的研究方向。     

并发环境中渐增式追踪重演机制

在基于消息传递的并发程序中,由于进程的调度顺序以及消息延时等特性,使得同样输入的不同执行呈现不同的结果,这种并发程序行为的不确定性直接导致了程序错误的不可再现性,即后续的执行无法再现前次执行的错误。以反复执行程序、重复再现故障为核心的循环调试方法变得不再可用。因此,对于并发程序的调试问题,我们将传统的循环调试方法加以扩充,引入追踪和重演的机制,重放程序的某次执行,以消除并发程序的错误不可再现性。     

基于确定性重演的并发程序调试

并发程序执行的不确定性导致了程序错误的不可再现性,后续的执行无法再现前次执行的错误,这使得以反复执行程序,重复再现故障为核心的循环调试方法变得不再可用。本文提出了一种基于确定性重演的并发程序的调试方法,确定化并发程序的执行轨迹,重现程序初始运行的错误状态。