程序缺陷自动修复研究进展及关键问题

程序缺陷自动修复是指针对程序中存在的缺陷,自动生成相应的程序补丁,进而使程序恢复正常运行.首先,根据补丁生成方式的不同,将程序缺陷自动修复方法划分为4类,分别为基于搜索的、基于语义的、基于机器学习的以及基于错误报告驱动的程序缺陷自动修复方法.基于搜索的程序缺陷自动修复方法运用启发式算法在搜索空间内通过搜索生成程序补丁;基于语义的程序缺陷自动修复方法将修复约束作为合成程序补丁的规约,最后通过约束求解器生成程序补丁;基于机器学习的程序缺陷自动修复方法使用数据集训练并生成修复模型,通过修复模型生成程序补丁;基于错误报告驱动的程序缺陷自动修复方法通过利用程序执行以及用户反馈的错误信息生成程序补丁.本文对以上4类程序缺陷自动修复方法进行了详细阐述;其次,总结了检验程序缺陷自动修复方法及工具修复效果所用到的缺陷库;最后,分析了程序缺陷自动修复在工业界的应用现状并总结了该领域面临的关键问题及未来研究的方向.     

基于数据流分析的过拟合补丁识别

自动程序修复技术可实现对软件缺陷的自动修复, 并使用测试套件评估修复补丁. 然而因为测试套件不充分, 通过测试套件的补丁可能并未正确修复缺陷, 甚至引入新的缺陷并产生波及效应, 导致自动程序修复生成大量过拟合补丁. 针对这个问题, 本文提出了一种基于数据流分析的过拟合补丁识别方法, 首先将补丁对程序的修改分解为对变量的操作, 然后采用数据流分析方法识别补丁影响域, 并根据补丁影响域选择针对性覆盖准则来识别目标覆盖元素, 进而选取测试路径并生成测试用例实现对修复程序的充分测试, 避免修复副作用的影响. 本文在两个数据集上进行了评估, 实验结果表明, 基于数据流分析的过拟合补丁识别方法可有效提升自动程序修复的正确性.     

不正确程序修复补丁识别

程序自动修复技术是保证软件质量、提高开发效率的有效手段. 目前, 大多数自动修复工具使用测试用例作为补丁正确性验证的最终方法, 有限的测试用例难以对程序进行充分的测试, 因此自动修复工具生成的补丁集合包含大量的不正确补丁. 为了识别不正确补丁, 我们采用对比缺陷修复前后成功测试的执行路径以及生成测试用例的方法来识别修复补丁的有效性, 以解决自动修复工具精度低的问题. 我们的方法评估了来自6个经典的自动修复工具生成的132个补丁, 并成功地排除了80个不正确的补丁并且没有排除正确的补丁, 这表明我们的方法可以有效地排除不正确补丁, 并且提高自动修复工具的精度.     

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

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

基于Frame结构的测试代码自动生成研究

讨论了基于Frame结构的测试程序开发环境,该开发环境以自然语言描述测试需求,利用人工智能技术根据测试需求自动生成计算机语言代码.在实现途径上,给出了利用框架式结构描述测试需求的方法和利用语法自动分析原理分析测试流程、由推理机实现代码自动生成的方法,从而有效地提高了测试程序集的开发效率与开发质量.     

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

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

GUI回归测试的测试脚本修复技术研究

回归测试对修改后的软件重新进行测试,确认修改没有引入新的错误或导致其他代码产生错误。研究GUI回归测试脚本的自动化修复技术,采用有限状态机描述GUI的交互行为,并基于FSM产生测试用例集;使用自动化测试工具生成测试脚本,建立状态迁移和测试脚本的映射关系表;通过比较GUI新、旧版本的FSM得到GUI的变化信息,根据变化信息和映射表对原测试脚本自动修复。实例验证了脚本修复方法的可行性和有效性。     

一种覆盖测试中路径集的自动生成方法

覆盖测试是软件测试中的重要方法,路径覆盖测试中路径集的自动生成能提高测试效率。该文提出了一种描述程序分支情况的分支关系图,给出了基于分支关系图的路径集自动生成算法,实验证明了该方法的正确性,能有效地求出程序路径集。     

一种覆盖测试中路径集的自动生成方法

覆盖测试是软件测试中的重要方法,路径覆盖测试中路径集的自动生成能提高测试效率。该文提出了一种描述程序分支情况的分支关系图,给出了基于分支关系图的路径集自动生成算法,实验证明了该方法的正确性,能有效地求出程序路径集。     

基于一致性测试理论的Statechart描述的测试用例自动生成

本文研究Statechart描述的测试语义和测试用例的自动生成.基于Tretmans的从标记转换系统描述自动生成测试用例的方法,我们研究如何从Statechart描述自动生成测试用例.本文的主要贡献在于建立了基于Statechart描述的一致性测试和测试用例生成的形式化基础.为Statechart描述建立了形式化测试语...     

A test-suite reduction approach to improving fault-localization effectiveness

In order to improve the effectiveness of fault localization, researchers are interested in test-suite reduction to provide suitable test-suite inputs. Different test-suite reduction approaches have been proposed. However, the results are usually not ideal. Reducing the test-suite improperly or excessively can even negatively affect fault-localization effectiveness. In this paper, we propose a two-step test-suite reduction approach to remove the test cases which have little or no effect on fault localization, and improve the distribution evenness of concrete execution paths of test cases. This approach consists of coverage matrix based reduction and path vector based reduction, so it analyzes not only the test cases coverage but also the concrete path information. We design and implement experiments to verify the effect of our approach. The experimental results show that our reduced test-suite can improve fault-localization effectiveness. On average, our approach can reduce the size of a test-suite in 47.87% (for Siemens programs) and 23.03% (for space program). At the same time, on average our approach can improve the fault-localization effectiveness, 2.12 on Siemens programs and 0.13 on space program by Tarantula approach.     

A correlation study between automated program repair and test-suite metrics

Automated program repair is increasingly gaining traction, due to its potential to reduce debugging cost greatly. The feasibility of automated program repair has been shown in a number of works, and the research focus is gradually shifting toward the quality of generated patches. One promising direction is to control the quality of generated patches by controlling the quality of test-suites used for automated program repair. In this paper, we ask the following research question: “Can traditional test-suite metrics proposed for the purpose of software testing also be used for the purpose of automated program repair?” We empirically investigate whether traditional test-suite metrics such as statement/branch coverage and mutation score are effective in controlling the reliability of generated repairs (the likelihood that repairs cause regression errors). We conduct the largest-scale experiments of this kind to date with real-world software, and for the first time perform a correlation study between various test-suite metrics and the reliability of generated repairs. Our results show that in general, with the increase of traditional test suite metrics, the reliability of repairs tend to increase. In particular, such a trend is most strongly observed in statement coverage. Our results imply that the traditional test suite metrics proposed for software testing can also be used for automated program repair to improve the reliability of repairs.     

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

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

Plain random test generation with PRTest

Automatic test-suite generation tools are often complex and their behavior is not predictable. To provide a minimum baseline that test-suite generators should be able to surpass, we present PRTest, a random black-box test-suite generator for C programs: To create a test, PRTest natively executes the program under test and creates a new, random test value whenever an input value is required. After execution, PRTest checks whether any new program branches were covered and, if this is the case, the created test is added to the test suite. This way, tests are rapidly created either until a crash is found, or until the user aborts the creation. While this naive mechanism is not competitive with more sophisticated, state-of-the-art test-suite generation tools, it is able to provide a good baseline for Test-Comp and a fast alternative for automatic test-suite generation for programs with simple control flow. PRTest is publicly available and open source.

     

用遗传算法的测试用例最小化

回归测试就是验证对程序的修改是否迭到了预期的目的，同时检查修改是否损害了程序原有的正常功能。随着程序新版本的不断推出，测试用例集不断扩大，回归测试成本越来越高。测试用例最小化就是从已有的用例集中，找到一个测试运行代价最小的用例子集用于回归测试，并保持原来的测试覆盖率。本文主要研究用遗传算法解决测试用例最小化问题：基于测试历史数据，设计基因编码并构建初始种群；利用测试覆盖率和测试运行代价设计适应度函数；通过遗传算子完成进化过程并找到最优或近似最优解。最后本文给出了对算法进行实例研究的结果。结果表明，本文提出的用例最小化技术能有效缩减回归测试用例集，大幅度降低回归测试费用。     

引入错误级别的测试集压缩模型研究

开发者每一次对软件的修改都会导致测试集的增长。在进行回归测试时，如果重新运行所有的测试案例，成本将是极其昂贵的。于是，一些压缩测试集的算法被提出。这些算法能够找出一个与原测试集有相同覆盖度的压缩测试集，但这些压缩后的测试集在查错方面的性能不十分令人满意。引入错误级别的概念可以对测试案例的查错能力进行更为为细致的划分。本文通过引入错误级别，改进了一个双标准测试集压缩模型，并提出了一个新的测试集压缩算法。改进后的双标准测试集压缩模型能提供关于测试案例查错能力的更具体的信息。新算法有一个重要的特点：在任何时候中断算法，仍然能得到一个满足覆盖度的压缩测试集。     

测试用例最小化研究*

给出了测试用例最小化问题的形式化描述,提出并实现了两个新的用于用例最小化的算法.与现有其他最小化算法不同,这两个算法在考虑了每个用例测试覆盖度的同时,还考虑了用例的测试运行代价,目的是提高最小化效率.最后给出了对这两个算法进行实例研究的实验结果.结果表明,用例最小化技术能有效缩减回归测试用例集的尺寸,大幅度降低回归测试费用,提高最小化效率.     

C/C++程序缺陷自动修复与确认方法

在计算机软件中,程序缺陷不可避免且极有可能造成重大损失.因此,尽早发现并排除程序中潜在的缺陷,是学术界和工业界的普遍共识.目前的程序缺陷自动修复方法大都遵循缺陷定位、修复候选项生成、选择及验证的流程,但在修复实际程序时存在修复率低、无法保证修复结果的正确性等问题.提出了一种基于程序合成的C/C++程序缺陷自动修复方法.首先,从满足相同规约的程序集中,通过人工整理的方式总结错误模式及其对应的修复方法,使用重写规则表达错误模式,在此基础上实现了基于重写规则和基于程序频谱的缺陷定位方法,得到程序中可能的缺陷位置;其次,基于重写规则,使用修复选项生成方法得到缺陷的修复选项,同时,通过深度学习的方式学习正确程序的书写结构,帮助预测错误程序错误点应有的语句结构,通过这两种方式提高候选项质量,进而提高修复率;最后,在选择验证过程中,使用程序合成的方法将样例程序作为约束,保证合成后代码的正确性.基于上述方法实现了原型工具AutoGrader,并在容易出错、缺陷典型的学生作业程序上进行了实验,结果显示,该方法对学生作业程序中的缺陷有着较高的修复率,同时也能保证修复后代码的正确性.     

程序自动修复:关键问题及技术

程序自动修复技术能够有效地降低软件维护成本,是近年来学术研究的热点问题.待修复程序规约的刻画,对自动修复过程具有至关重要的作用.从规约的角度对程序自动修复问题和技术进行了分析梳理.从待修复程序是否具有完整的程序规约,将现有修复问题分为不完全规约、完全规约和半完全规约这3大类待修复问题.以3类抽象问题为线索,梳理了不同前提假设下修复技术面临的核心问题、问题之间的联系和技术体系中的逻辑关系.分析了不完全规约程序修复问题中高精度补丁生成、规约补全和补丁择优等问题,梳理了完全规约程序修复问题中内存泄漏、资源泄露、并发错误中的数据竞争、原子性违背、顺序违背和死锁,配置错误以及特定性能错误等具体问题及研究进展,整理了半完全规约程序修复问题中多种形式的修复具体问题及研究进展.最后分析了程序自动修复面临的机遇和挑战.