娄 琨,尚 颖,王海峰

(北京化工大学 信息科学与技术学院,北京 100029)

1 引言

错误定位是识别程序执行过程中导致程序失败的元素的过程[1].在软件调试的众多活动中,错误定位是其中最复杂耗时的活动之一,尤其在大规模复杂程序中.为了减小定位错误位置的人工成本,研究人员提出了众多错误定位方法,例如基于切片的方法[2],基于频谱的方法[3,4],基于变异的方法等[5].

在众多自动化错误定位方法中,基于频谱的错误定位(Spectrum-Based Fault Localization,SBFL)方法[3,4,6]是一种被广泛应用的方法.SBFL 考虑到程序元素的二元覆盖矩阵,但局限于其错误定位精度不高.目前的研究显示基于变异的错误定位方法比最新的基于频谱的方法有更高的错误定位精度[7,8].MBFL是一种基于变异测试[7]的方法[9].截止目前,MBFL 分为两种技术:Metallaxis-FL[5]和MUSE[9].研究表明[10,11],Metallaxis-FL的错误定位效率和效果都要优于MUSE,因此本文选择Metallaxis-FL 作为MBFL 原始方法.

在MBFL 中,将一个程序p通过简单的语法变化生成一系列错误程序p'(也就是变异体),生成变异体的规则被称为变异算子.根据变异算子使用的次数,变异体可以分成两类:一阶变异体(First-Order-Mutants,FOMs)和高阶变异体(Higher-Order-Mutants,HOMs),其中FOMs是只使用一次变异算子生成,HOMs 则是通过多次使用变异算子生成[12].

在之前的MBFL 研究中,只有FOMs 用于定位单错误程序[5,13].但Xue 等[14]发现定位多错误更有困难,耗时且成本巨大,同时多错误之间存在错误干扰现象,导致现有错误定位技术的定位效果较差.另一方面,Offutt 等[15]发现杀死HOMs是否能检测出复杂错误是不确定的.为填……