论文部分内容阅读
错误定位是软件调试中关键且耗时的环节。自动化错误定位技术,旨在自动识别程序中潜在出错的实体,有助于快速定位程序中发生错误的位置。但随着软件的更新迭代,程序中的错误变得更加复杂,传统错误定位技术主要关注单错误,即对程序语句进行单次修改后可修复的错误,针对需在多个位置修改才可修复的多错误,难以实现准确的错误定位。基于变异的错误定位技术(Mutation Based Fault Localization,MBFL)是近年来提出的一种精度最高的错误定位技术。MBFL通过对被测程序植入人工错误生成程序变异体,依据植入错误数量的多少可分为一阶变异体和高阶变异体。高阶变异体在被测程序中植入多个错误,可模拟多错误,理论上可用于软件多错误定位。但现有高阶变异体生成只是采用一阶变异体的组合,未考虑组成多错误中单错误之间的关联性。研究一种可模拟真实多错误的高阶变异体生成方法是本课题面临的第一个挑战。另一方面,语句怀疑度度量方法是错误定位的核心技术,直接决定出错程序实体在检查列表中的位置。在MBFL技术中,现有度量方法是基于一阶变异体执行信息计算,研究适合于高阶变异体的语句怀疑度度量方法是本课题面临的另一个挑战。本文针对软件多错误定位技术开展研究,提出基于高阶变异的多错误定位技术,具体研究了面向多错误的高阶变异体生成方法和面向多错误的高阶变异语句怀疑度度量方法,并针对高阶变异错误定位技术开销大的问题提出了约减方法。本文的主要研究内容包括:(1)面向多错误的高阶变异体生成方法多错误可以认为是由单错误组成,这些单错误之间可能具有关联性。本文基于程序中错误的存在形式,系统化分析单错误之间的关联性和分布特性,提出相应的高阶变异体生成方法。首先假定这些单错误之间无关但错误具有相似性,提出基于聚类的高阶变异体生成方法,生成具有代表性的高阶变异体。其次,假定单错误之间存在逻辑相关,本文考虑单错误的发生位置,分别提出基于分布的高阶变异体生成方法和基于密度的高阶变异体生成方法。在两个数据集共237个多错误程序上的实验结果表明,相比较于基于分布的生成方法和基于密度的生成方法,基于聚类的高阶变异体生成方法组合表征无关错误的一阶变异体来生成高阶变异体,更能模拟真实多错误。本文进一步在高阶变异错误定位技术中应用提出的高阶变异体的生成方法,错误定位精度显著提高。(2)面向多错误的高阶变异语句怀疑度度量方法由于传统MBFL度量语句怀疑度时未考虑多错误的情况,本文依据多错误位置与高阶变异体的执行特征,通过构建高阶变异体与程序语句的映射关系,提出两种语句怀疑度度量方法。首先,考虑到多错误位置与高阶变异体怀疑度的分布存在密切关系,提出基于多错误怀疑度分布的度量方法,包括基于高阶变异体怀疑度最值、均值和权重的度量方法。其次,进一步分析测试用例在多错误上的执行特征,提出基于多错误测试状态变化的度量方法。在237个多错误程序上的实验结果表明,基于高阶变异体怀疑度权重的度量方法,考虑程序语句间的差异性,可更准确定位错误语句的位置。本文进一步在高阶变异错误定位技术中应用提出的高阶变异语句怀疑度度量方法,错误定位精度显著提高。(3)面向多错误的高阶变异体约减方法由于高阶变异错误定位技术应用高阶变异体面临执行成本巨大的问题,本文依据多错误和高阶变异体特性,从高阶变异体与语句的映射关系和高阶变异体对错误的定位价值出发,提出两种高阶变异体约减方法。首先,为保证程序语句变异的多样性,提出基于语句粒度采样的约减方法。其次,考虑到高阶变异体在错误定位中的定位价值,提出基于变异测试评估的约减方法。在237个多错误程序的实验结果表明,两种方法中基于语句粒度采样的约减方法有较高的错误定位精度。本文进一步在高阶变异错误定位技术中应用基于语句粒度采样的约减方法,在采样率为20%时,错误定位精度与原始未采样时相近,且显著优于传统错误定位技术,并有效降低了80.0%的变异执行成本,变异执行效率提升了约4倍。综上所述,本文针对程序多错误定位的问题,系统化研究了面向多错误的高阶变异错误定位技术。首先,从高阶变异体的生成角度,研究了三种面向多错误的高阶变异体生成方法。其次,从高阶变异语句怀疑度度量角度,提出了两种面向多错误的高阶变异语句怀疑度度量方法。最后,从高阶变异错误定位技术的开销约减角度,实现了两种面向多错误的高阶变异体约减方法,错误定位精度与原始未采样时相近,且显著优于传统错误定位技术,减少了约80.0%高阶变异执行开销,提升了高阶变异错误定位技术的执行效率,为高阶变异错误定位技术的实际应用奠定了基础。