基于传播链的缺陷定位及修复技术研究

发布时间：2018-04-21 02:24

本文选题：缺陷定位 + 自动程序修复　；参考：《国防科学技术大学》2016年博士论文

【摘要】：缺陷作为软件系统设计和维护过程中不可避免的产物,随着软件系统的规模和复杂程度的增加也在不断增加。将软件缺陷的定位与修复工作进行自动化,对于提升软件调试效率以及软件质量有着重要意义。多年来学术界和工业界一直致力于高效的、准确的缺陷定位和自动修复技术的研究,取得了不少进展。然而由于软件缺陷作用机理的复杂性,目前的缺陷定位和自动修复技术仍然面临很大挑战。本文基于软件执行过程中错误的传播过程,对现有的缺陷定位技术以及基于缺陷定位的自动修复技术修复效果进行研究分析,并针对缺陷定位、补丁生成以及补丁验证三个方面,研究基于测试用例聚类的缺陷定位优化技术、基于可疑代码集过滤的程序自动修复技术以及基于测试用例分组的迭代修复技术,提出了一系列提高缺陷定位能力和自动修复能力的优化技术,并通过对大型开源软件真实历史错误进行缺陷定位和修复实验,依据科学统计和度量方法验证了这些优化技术的效能。论文的主要研究工作及创新点如下:1)从缺陷容忍和缺陷排除的角度出发,对现有的程序自动修复工具的修复效果进行分析在研究领域,缺陷容忍和缺陷排除是两类主流的提升软件可靠性和安全性的方式。现有的程序自动修复工具均专注于通过补丁生成的方式来修复目标程序暴露出来的故障,却忽略了对修复效果的分析研究。本文通过收集两种主流的软件自动修复工具:Genprog以及CETI所生成的修复补丁,分析各个修复补丁中所修改的代码与目标程序中的软件缺陷之间的关联性,研究现有修复工具的修复效果是倾向于实现缺陷容忍还是缺陷排除。此外,本文还提出了缺陷复杂程度和错误深度的概念,通过缺陷所涉及的代码数来简单表示缺陷的复杂程度,以及通过从缺陷到失效所经过的传播链的长度和缺陷所影响的错误传播链的数量来定义程序中所包含错误的深度,并分析统计了缺陷的复杂程度、错误深度与最终修复效果(生成补丁是属于缺陷容忍还是缺陷排除?)之间的关联程度。分析结果表明,现有程序自动化修复工具更多地是以缺陷容忍方式而不是缺陷排除方式来修复目标程序,缺陷的复杂程度越低、错误深度越小,就越可能通过缺陷排除的方式进行修复,反之,则只能通过缺陷容忍的方式进行修复。2)提出了基于测试用例聚类的缺陷定位技术优化方法基于程序谱的缺陷定位技术(SFL)是目前最为流行的一种缺陷定位技术,然而由于其是根据测试用例集来进行统计定位缺陷的,它的定位精度必然受到巧合正确性现象(coincidental correctness)的影响。巧合正确性是指在测试用例执行过程中,缺陷所在代码被执行,但缺陷并未被激活或错误的传播并未导致失效的情况,由于sfl是根据执行测试用例所覆盖的代码以及执行结果来统计得到各个程序代码为缺陷所在的可疑度,巧合正确的测试用例越多,其定位缺陷的精度就越受影响。本文通过对部分缺陷程序进行缺陷定位实验,观察到在巧合正确的测试用例之间,测试用例执行过程中的错误的传播链之间具有很高的相似性,基于这个观测结果,假设在执行所有巧合正确的测试用例时,其行为之间均具有很高的相似度,并提出了一种基于聚类分析的缺陷定位优化方法tsar(testcaseselectionandreconsitution),通过将测试用例进行聚类,并基于聚类来构建新的覆盖矩阵来进行缺陷定位的可疑度计算,从而尽可能地削弱巧合正确性现象对sfl的定位精度的影响。实验结果表明,在大部分情况下,通过tsar能有效提高sfl的定位精度。3)提出了基于可疑代码集过滤的程序自动修复技术优化方法目前,自动化的程序修复技术往往是通过修改一处或多处的代码来产生修复补丁,这些可进行修改的代码集合通常是通过缺陷定位技术来得到的,且被称为可疑代码集。然而,现有的可疑代码集中往往包含大量与成功修复无关的代码,这些代码影响了自动修复的效率。本文提出了一种过滤可疑代码集中无用代码的方法sfcsf(suspiciousfaultycodesnippetfiltering),在保证修复成功率的同时可以有效地减少可疑代码集的大小。sfcsf依托于基于程序谱的缺陷定位(sbfl)技术来获得各个代码的可疑值。基于错误的传播链,sfcsf只从可疑代码集中过滤出在错误传播链上那些可疑值即将发生变化的节点处代码作为过滤后的可疑代码集进行自动修复。实验结果表明了sfcsf在大多数情况下能够大大提高了自动修复工具的修复效率,但同时,sfcsf的有效性也受到了测试用例集的制约:程序谱过于相似的测试用例集将使得sfcsf失效。4)提出了基于测试用例分组的迭代修复技术在补丁验证阶段,自动化的程序修复技术往往使用测试用例集来验证所生成补丁的有效性:只有使得所有测试用例的执行结果均正确的补丁才是正确的修复补丁。这种验证方式表明现有的自动化的程序修复技术仍是基于缺陷排除的思想来生成并验证补丁的,而忽略了部分修复的可能性。而本文之前的研究表明,修复结果大部分是缺陷容忍的。自动修复技术的目标与结果之间的矛盾性使得修复的成功率和效率受到很大影响,特别是针对复杂缺陷,现有的自动修复技术的修复效果并不理想。本文从实现缺陷容忍的角度出发,提出了一种基于测试用例分组的迭代修复方法,该方法根据测试用例的代码执行信息将测试用例进行分组,并基于迭代的方式对程序进行修复:每次迭代的目标在于生成能够满足一组或多组测试用例的中间补丁,通过多次迭代,最终获得满足所有测试用例的修复补丁。实验结果显示,本文方法能够大大提高对程序缺陷特别是复杂缺陷的修复能力。
[Abstract]:As an inevitable product in the process of software system design and maintenance, defects are increasing with the scale and complexity of the software system. It is important to automate the positioning and repair work of software defects to improve the efficiency of software debugging and the quality of software. A lot of progress has been made in the research of high efficiency, accurate defect location and automatic repair technology. However, due to the complexity of the mechanism of software defects, the current defect location and automatic repair technology still faces great challenges. Based on the error propagation process in the software execution process, the existing defect positioning technology is used in this paper. And the repair effect of automatic repair technology based on defect location is studied and analyzed, and aiming at three aspects of defect location, patch generation and patch validation, the defect location optimization technology based on test case clustering is studied, the automatic repair technique based on the suspicious code set filtering and the iterative repair technique based on the test case grouping are also studied. A series of optimization techniques to improve the ability of defect location and automatic repair are proposed, and the effectiveness of these optimization techniques is verified by scientific statistics and measurement methods. The main research work and innovation points of this paper are as follows: 1) tolerance from defect tolerance. From the point of view of the defect elimination, the restoration effect of the existing automatic program repair tools is analyzed in the research field. Defect tolerance and defect elimination are the two main types of ways to improve the reliability and security of the software. The existing automatic program repair tools are focused on the repair of the target program by the patch generated. By collecting two mainstream software auto repair tools: Genprog and CETI repair patches, this paper analyzes the relationship between the code modified in the repair patches and the software defects in the target program, and studies the repair effect of the existing repair tools. In addition, the concept of defect complexity and error depth is also proposed, the complexity of the defect is simply expressed by the code number involved in the defect, and the number of error propagation chains influenced by the length and defect of the propagation chain passed from the defect to the failure. The depth of the error is included in the program, and the degree of correlation between the complexity of the defect, the error depth and the final repair effect (the patch is a defect tolerance or the defect exclusion?). The analysis results show that the existing program automation repair tools are more in the way of defect tolerance rather than defect exclusion. To repair the target program, the lower the complexity of the defect and the smaller the error depth, the more likely it is to repair the defect through the method of defect exclusion. On the contrary, the defect location technology can only be repaired.2). The defect location technology based on the program spectrum based defect location technology (SFL) is the most important method based on the test case clustering. A popular defect location technique, however, because it is based on a test case set to make a statistical location defect, its positioning accuracy is bound to be affected by the coincidence correctness (coincidental correctness). The error propagation does not lead to the failure situation, because SFL is based on the code covered by the execution test case and the execution result to count the doubtful degree of the defects in each program code. The more the correct test cases are coincidental, the more the accuracy of the location defect is affected. In a bit experiment, a high similarity between the error propagation chains in the execution of a test case is observed between the coincidentally correct test cases. Based on this observation result, it is assumed that when all the coincidental test cases are executed, their behavior has a very high similarity, and a lack of clustering analysis is proposed. The settlement optimization method Tsar (testcaseselectionandreconsitution), by clustering the test cases and constructing a new coverage matrix based on clustering to calculate the doubtful degree of the defect location, so as to weaken the effect of the coincidence accuracy to the positioning accuracy of the SFL as much as possible. Tsar can improve the positioning accuracy of SFL effectively.3.) a new method of automatic repair technology optimization based on suspicious code set filtering is proposed. The automated program repair technology is often created by modifying one or more codes to produce repair patches. It is known as a suspicious code set. However, the existing suspicious code sets often contain a large number of codes unrelated to successful repair. These codes affect the efficiency of automatic repair. This paper proposes a method sfcsf (suspiciousfaultycodesnippetfiltering) for filtering suspicious code centralized useless code, which ensures the success rate of repair. At the same time, the size of the suspicious code set can be effectively reduced by.Sfcsf based on the program spectrum based defect location (sbfl) technology to obtain the suspicious values of each code. Based on the error propagation chain, the sfcsf only filters out the code of the nodes that are about to change on the wrong propagation chain from the suspicious code set as a filter. The experimental results show that sfcsf can greatly improve the repair efficiency of the auto repair tool in most cases, but at the same time, the effectiveness of the sfcsf is also restricted by the test case set: the test case set which is too similar to the program spectrum will make the sfcsf failure.4) put forward the iterations based on the test case grouping. In the patch validation phase, the automated program repair technology often uses a test case set to verify the validity of the generated patch: only the patch that makes all the test cases correctly executed is the correct fix patch. This validation means that some automated program repair techniques are still based on the existing automated repair techniques. The idea of defect exclusion to generate and verify patches and ignore the possibility of partial repair. The previous study shows that most of the restoration results are tolerable. The contradiction between the target and the result of the automatic repair technology makes the success rate and efficiency of the repair greatly affected, especially for the complex defects. In this paper, an iterative repair method based on test case grouping is proposed from the point of view of defect tolerance. This method is based on the code execution information of the test case to group the test cases and repair the program based on the iterative method: the target of each iteration is at the end of each iteration. Yu Shengcheng is able to meet a set of intermediate patches for a group of test cases or multiple sets of test cases, and through multiple iterations, the final patch that meets all test cases is finally obtained. The experimental results show that this method can greatly improve the ability to repair program defects, especially complex defects.

【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP311.53

【相似文献】