基于变异的错误定位优化技术研究

发布时间：2020-06-15 00:14

【摘要】：识别软件系统中存在错误的代码位置是软件调试过程中最为困难和耗时的环节之一。最近提出的基于变异的错误定位(Mutation Based Fault Localization,MBFL)技术是目前定位精度最好的一种自动化错误定位技术,能有效减少开发人员查找错误所需要的时间消耗。MBFL技术源于变异测试,需要对被测程序生成变异体,执行测试用例,并利用执行信息来进行错误定位。通常变异体和测试用例数量都随程序规模增加而增大,而MBFL技术需要在每个变异体上执行所有测试用例,因此执行开销很大。以软件回归测试领域经典的基准被测程序space为例,该程序可执行的代码行数为5K～6K,程序自带1万多个测试用例,可生成的变异体接近4万个。如果使用MBFL技术定位该程序中的错误,需要执行约5亿次变异测试(Mutant-Test Pair,MTP),时间花费巨大。MBFL技术具有很高的错误定位精度,约减变异执行是改进MBFL技术的有效手段。所以在保证错误定位精度前提下,如何优化变异体执行,减少执行开销,是在实际中应用MBFL技术的关键研究问题。本文从多个角度研究MBFL优化问题,在保持原始MBFL技术错误定位高精度的前提下,提出变异测试执行的优化方法,进而降低MBFL执行开销,为MBFL技术从理论研究走向实际应用奠定基础。本文具体研究内容如下:(1)面向MBFL的变异体静态采样方法:变异体采样是一种约减变异执行的有效方法,但不可避免的带来定位精度损失的问题。为减少MBFL错误定位精度由于变异体约减带来的损耗,本文首先针对变异体采样研究相关因素与错误定位精度之间的关系,具体包括采样粒度、采样前后的变异体集合的语句分布、变异算子分布、错误分布等。在此基础上,提出了基于语句层面的细粒度变异体采样和面向错误分布的变异体采样两种策略。相比原始MBFL,这两种技术可以有效提高变异体的变异算子完整性和语句分布多样性。实验表明,应用这两种策略可以在错误定位精度损失很小的前提下,平均减少约80%的变异体,有效提高了 MBFL执行效率。(2)MBFL变异体执行动态优化方法:在MBFL变异体执行过程中,通过研究语句怀疑度、变异体怀疑度计算和变异体执行测试用例结果之间的相互关系,提出了面向变异体和面向测试用例的两种动态优化策略,在变异执行过程中,动态约减变异体和测试用例的执行。实验结果显示应用这两种动态优化策略的MBFL技术能在保留原始MBFL错误定位精度不变的前提下,平均减少约53.9%的变异体执行开销;(3)静态与动态相结合的MBFL优化技术:通过整合前面两个方面的研究成果,提出了一种结合变异体静态采样和变异体执行动态优化方法的MBFL整体优化技术框架。实验结果表明,应用该优化技术能在保留原始MBFL错误定位高精度的前提下,平均减少约87.9%的变异体执行开销,显著提升了 MBFL技术的执行效率。综上所述,本文针对MBFL变异体执行时间开销太大的问题,在变异体运行测试用例之前,研究两种变异体采样策略形成了一种能有效降低变异体规模同时保持原始MBFL错误定位高精度的变异体采样方法;在变异体执行测试用例过程中,提出了面向变异体约减和测试用例约减两种动态优化策略,形成了一种MBFL变异体执行动态优化技术,并通过理论分析了该方法可以保证不损失原MBFL技术的错误定位精度;最后,实现了静态与动态优化相结合的完整MBFL优化技术,在保留原始MBFL技术错误定位高精度的前提下,减少了约87.9%的变异体执行开销,大幅度提升了 MBFL的执行效率,为MBFL技术从理论研究走向实际应用奠定了基础。
【学位授予单位】：北京化工大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP311.53
【图文】：

技术框架,变异体,测试用例,测程

１．３．１研究内容逡逑本课题的研究内容由ＭＢＦＬ技术框架的各个步骤的优化方法组成。ＭＢＦＬ的技术逡逑框架如图１－２所示，首先通过变异算子对被测程序植入变异，生成规模庞大的变异体，逡逑然后每个变异体都需要执行测试用例集中所有测试用例，执行过程中ＭＢＦＬ收集动态逡逑信息求得被测程序的语句怀疑度，生成错误定位报告。逡逑变异算子逦逦逡逑ＯＰ＝｛0ｐｌ，0ｐ２．．．0Ｐｑ｝逡逑被测程序Ｐ＝｛ｓ丨，ｓ２．．ｓ？｝邋逦入变．逡逑测试用例集Ｔ＝｛ｔ丨，ｔ２．．ｔｙ｝逦变异体集合Ｍ＝｛ｍｉ，ｍ２．．ｍｋ｝逡逑次邋ＭＴＰ邋并收逡逑＾邋兵算语士怀疑虔逡逑逦圭成错误定位报ｔ逦＞逡逑图１－２邋ＭＢＦＬ技术框架逡逑Ｆｉｇ．邋１－２邋Ｔｈｅ邋ｆｒａｍｅｗｏｒｋ邋ｏｆ邋ＭＢＦＬ逡逑如图１－２所示，ＭＢＦＬ的关键步骤是变异体执行测试用例，每一次变异体－测试用逡逑１４逡逑

优化技术,变异体,方案,错误定位

图２－１邋ＭＢＦＬ优化技术研宄方案逡逑Ｆｉｇ．２－１邋Ｆｒａｍｅｗｏｒｋ邋ｏｆ邋ＭＢＦＬ邋ｏｐｔｉｍｉｚａｔｉｏｎ邋ｒｅｓｅａｒｃｈ逡逑如图２－１所示，本文采取的ＭＢＦＬ优化技术研宄方案包括变异体静态约减和变异逡逑执行动态优化两个部分。变异体静态约减是在对程序采用变异算子植入错误生成变异逡逑体集合之后，通过应用变异体采样策略选择部分变异体执行测试用例进行ＭＢＦＬ错误逡逑定位过程。相比使用变异体全集执行测试用例进行错误定位，变异体静态约减之后通逡逑常会带来变异体集合信息的丢失，影响错误定位精度，因此设计更好的变异体采样策逡逑略，尽量减少错误定位精度损失，是本方案的研宄的重点和难点之一；在变异体集合逡逑确定之后，ＭＢＦＬ需要在变异体上运行测试用例，并收集执行过程中的数据用于计算逡逑变异体和语句的怀疑度，完成错误定位。本文将在变异体执行测试用例过程中，从语逡逑句怀疑度和变异体怀疑度计算、变异体执行约减和测试用例执行约减等多个方面动态逡逑分析ＭＢＦＬ变异体执行过程，研宄ＭＢＦＬ错误定位精度和变异体执行测试用例之间逡逑１７逡逑

【相似文献】