基于搜索的高效变异程序自动修复方法

发布时间：2020-06-02 06:01

【摘要】：程序错误是在软件开发流程中难以避免的现象。当程序被检测到发生错误时,调试的过程实质上可以分为两个步骤:首先确定错误发生的位置和错误产生的原因,然后对其进行修复。第一步被称为“错误定位”,是软件开发过程中调试阶段代价消耗最高的活动之一。目前错误定位已有较多成熟的技术,存在的问题是即使检测到了错误的存在,对其的修复工作仍需开发者来完成,并且错误修复的难度与复杂程度远远高于错误定位,因此研究自动程序错误修复技术是一项具有重要意义的任务。结合变异技术与错误定位技术的自动程序修复方法,具有较好的程序错误修复能力,但这种方法不可避免的需要花费巨大的时间开销来执行变异体,尤其在应用于实际工业环境的大型程序时,其执行开销问题尤为严重。是否需要对程序生成所有可能的变异体以及从程序的何处开始产生变异体是这种方法面临的两个主要问题。应用错误定位技术,可以首先对怀疑度偏高的语句进行检查,以此避免较多无效变异体的产生,但在实际的应用中,错误定位并不足够精确,并且一些错误并不是发生在怀疑度较高的语句上,而是存在于与之有依赖关系的语句中,进而导致应用效果不理想。可以看出,这种使用贪心策略优先检查高怀疑度语句的思想并不能够高效的应对自动程序修复问题。寻找一个正确的变异体作为修复补丁可以被看作是持续寻找最优解的过程,因此应用全局最优方法可以有效提高寻找修复补丁的效率。此外,现有的修复策略大多面向单错误程序,而现实中程序的错误往往由多个位置引起。本文基于上述的问题,在采用错误定位优点的同时,针对贪心策略易陷入局部最优解的问题,提出了一种基于搜索的变异程序自动修复方法,不仅能够有效的解决变异体执行开销问题,同时对多错误程序具有一定的修复能力。为了应对全局最优搜索算法自身执行效率的缺陷,本文进一步提出了两种优化方法来缩小搜索空间和加速收敛速度,分别是搜索算法的非随机初始种群方法和混合式交叉策略。在搜索算法中,初始种群中的个体由怀疑度较高的语句构成,其怀疑度值由错误定位方法计算得到。这些个体具有较高的怀疑度值,被作为搜索初始的粗略解。在搜索过程中,通过混合式的交叉策略,采用固定位置的交叉方式来加速全局最优解的收敛,同时采用随机位置的交叉方式来加速对整个搜索空间的分布。为了进一步验证本文提出的自动程序修复方法的有效性、效率以及两种优化方法对搜索效率的影响,设计了一系列实验来研究和讨论相关问题。对西门子套件程序集的实验结果表明本文提出的基于搜索的变异程序自动修复方法相对于基于穷举的方法在寻找补丁时具有更高的效率并且能够保证修复能力,并且对于多错误版本程序具有一定的修复能力。同时非随机的初始种群方法和混合式交叉策略能够有效的缩小搜索空间,加速收敛。
【图文】：

正确的定位错误和获取更有效的测试用例集，是其关键的研究内容。逡逑通过有效利用修复策略对程序中的错误能够无需人工参与进行修复，极大地减轻软件逡逑开发人员对程序调试或维护的压力。目前大量的ＡＰＲ算法采用己有的错误定位技术，逡逑参考错误怀疑度给出语句序列，进而进行遍历尝试修复。逡逑在使用变异技术的自动程序修复中，由于变异所产生的候选变异体空间极为庞逡逑大，因此有效的使用错误定位技术能够在一定程度上避免无效变异体的产生，从而达逡逑到降低执行开销成本的目的。基于此，一种结合了错误定位和变异技术的自动程序修逡逑复方法被提出ｔ１９１。该方法首先采用一种错误定位方法，按照计算的测程序所有语句的逡逑怀疑度值降序排序，依次对每一条语句应用变异算子产生所有可能的变异体作为修复逡逑补丁，并通过测试集来验证每一个变异体是否为正确的修复，其流程如图２－１。逡逑假定一个错误可以通过一系列的变异操作进行修复，那么当错误语句排列在怀疑逡逑度序列前端时，就能够能快的修复。换句话说，错误定位的效果越好，修复的过程效逡逑率也越高；而当错误定位效果较差时，若错误语句在怀疑度序列排列较靠后，则对于逡逑前面遍历到的语句应用变异算子会产生指数增长的无效变异体。逡逑

图３－１基于搜索的变异程序自动修复方法流程逡逑Ｆｉｇ．３－１邋Ｏｖｅｒｖｉｅｗ邋ｏｆ邋ｓｅａｒｃｈ－ｂａｓｅｄ邋ａｕｔｏｍａｔｅｄ邋ｐｒｏｇｒａｍ邋ｒｅｐａｉｒ邋ｕｓｉｎｇ邋ｍｕｔａｔｉｏｎ邋ａｎｄ邋ｆａｕｌｔ邋ｌｏｃａｌｉｚａｔｉｏｎ逡逑图３－１描述了基于搜索的变异程序自动修复方法流程。首先，利用错误定位技术逡逑对错误程序进行预处理形成语句的怀疑度序列，根据怀疑度序列中高怀疑度的语句位逡逑置，结合可应用的变异算子生成初始种群，其中每一个初始种群中的个体代表？？个候逡逑选补丁。本课题的方法并没有采取传统上随机产生初始种群的方式，原因是采取错误逡逑定位的优点可以很容易的构造一些粗略的解，因此在一定程度上缩短了由随机产生的逡逑解收敛的过程。具体的描述将在后续初始种群部分进行详细讨论。然后，在ＧＡ的搜逡逑索过程中，种群根据不同的个体适应度值被分为了两部分，并在这两部分中应用不同逡逑的交叉算子，即本课题提出的混合式交叉策略。其余的流程，与一般的遗传算法类似，，逡逑１８逡逑
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.5;TP18

【相似文献】

相关期刊论文 前10条

1 刘旭亮;钟浩;;一种基于StackOverflow分析的程序自动修复方法[J];计算机工程;2018年10期

2 何九葛;;10kV带电线路绝缘导线自动修复装置的研制[J];科技资讯;2018年22期

3 李昂;毛晓光;雷晏;;面向自动修复并融合失效场景的缺陷定位方法[J];计算机科学;2015年12期

4 张春元;李贵乾;杨臻;常绪涛;;药型端面包覆层自动修复系统方案设计[J];装备环境工程;2018年03期

5 程德怿;乔健;;无线自组网络在应急通信中的研究与应用[J];电信工程技术与标准化;2018年08期

6 郭忠文;邵泽武;;FORMAT.COM源程序分析及其在软硬盘自动修复和反系统病毒技术中的应用[J];微型机与应用;1992年06期

7 曾庆跃;丁友东;;旧电影中基于Hough变换直线划痕的检测[J];计算机工程与设计;2010年04期

8 张军学;;绿色建筑材料裂缝自修复研究[J];住宅科技;2018年07期

9 陈小康;许畅;江磊;;Hybrid-Fixing:上下文一致性错误的正确修复[J];计算机研究与发展;2015年06期

10 张文富;王野;张铁轶;;基于RGB色系实现Auto-Repair的途径[J];科技创新与应用;2016年12期

相关博士学位论文 前1条

1 吴川;基于搜索的软件自动修复关键技术[D];中国矿业大学;2017年

相关硕士学位论文 前4条

1 孙树W

本文编号：2692719