基于高阶变异的多错误定位实证研究①

娄 琨,尚 颖,王海峰

(北京化工大学 信息科学与技术学院,北京 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是否能检测出复杂错误是不确定的.为填补这项研究内容,我们进行了一项大规模的实证研究,研究HOMs是否能提升错误定位的精度,同时分析不同类别的HOMs 与多错误之间的关系.

本文中,我们着力研究FOMs和HOMs 在多错误上的表现.然后我们将HOMs 分成三类研究不同HOMs分类的错误定位效果.在我们的实验设置中,首先应用Agrawal 等[16]提出的变异算子生成FOMs,然后根据FOMs 构建HOMs.特别地,针对多错误定位场景,我们组合63 个单错误程序生成100 个多错误程序,错误个数从2 个至5 个.最后,我们将HOMs 分成3 类用于比较不同类别HOMs的表现.

2 背景与动机

2.1 基于变异的错误定位技术

基于变异的错误定位技术是一种基于变异分析[8]的错误定位方法.变异分析通过对被测程序进行简单的语义改变,生成与原始程序不同的版本.这些人为植入错误的程序被称为变异体.生成变异体的规则被称为变异算子.本文采用Agrawal 等[16]提出的C 语言的变异算子.

在变异分析中,依据变异体和原始程序不同的输出,使用变异体来评估测试用例的质量.如果一个测试用例的执行结果不同于原始程序的结果,那么这个变异体就被杀死,记为killed 或detected,反之称这些变异体没有被杀死,即not killed 或live.

传统基于变异的错误定位技术主要包含以下4 个步骤:

(1)获得失败测试用例覆盖的语句:将测试用例T执行被测程序P,获得覆盖信息和执行结果(pass 或fail).然后测试用例就可以区分为通过测试用例集合Tp和失败测试用例集合Tf.被失败测试用例覆盖的语句集合记为covf.

(2)生成和执行变异体:采用不同变异算子,对失败测试用例覆盖的语句植入错误生成变异体.对某一条语句s生成的变异体集合记为M(s).然后将所有测试用例执行某一个变异体m,依据执行结果,Tk(m)为杀死变异体m的测试用例集合,Tn(m)为未杀死变异体m的测试用例集合.

(3)计算程序语句怀疑度:变异体的怀疑度可以用不同的MBFL 公式计算得到,这些公式都基于以下4 个参数:anp=|Tn∩Tp|,akp=|Tk∩Tp|,anf=|Tn∩Tf|,akf=|Tk∩Tf|.其中,anp表示通过测试用例中未杀死变异体的数量,akp表示通过测试用例中杀死变异体的数量,anf表示失败测试用例中未杀死变异体的数量,akf表示失败测试用例中杀死变异体的数量.表1列举了3 个研究人员常用的怀疑度计算公式(Ochiai[17],Tarantula[18],Dstar[19]).本文的实验中使用Ochiai 作为MBFL 公式,因为其在MBFL 研究中被广泛使用[5,9],且效果好于其他公式[13].计算完变异体的怀疑度,将某条语句对应的变异体集合的怀疑度最大值赋值为该条语句的怀疑度.

(4)生成错误定位报告:依据程序语句的怀疑度大小,降序排列生成程序语句排名表.开发人员可以根据排名表从上至下查找并修正程序错误.

表1 常用怀疑度公式

基于上述过程的描述,我们可以发现MBFL是基于“大部分失败测试用例杀死的变异体与程序错误有关”假设的研究工作,其理论基础是基于以下两类假设[20]:(1)将变异体视为是原被测程序的一种潜在修复;(2)将变异体视为原被测错误程序的近似版本.变异体执行测试用例后的状态有两种:杀死(killed)和未杀死(not killed).其中,杀死状态分为:被失败测试用例杀死(akf)和被通过测试用例杀死(akp).在被失败测试用例杀死的变异体,存在两种情况:(1)变异体的状态从失败变成通过,即程序被修复;(2)变异体仍然为失败,但输出与原始程序不同.这两种情况都有助于揭示错误位置,第一种程序修复的情况,可以依据变异的位置来确定程序错误的位置.第二种情况,变异体的输出与原始程序不同,其有可能是对错误位置变异而造成的输出不同,此变异体的行为特征与错误程序更加相似.另一方面,被通过测试用例杀死的变异体,其更可能是对正确语句进行变异,造成输出与原始程序不同.并且,Moon 等[9]的研究发现,错误语句生成的变异体在失败测试用例下更容易通过,而正确语句生成的变异体在通过测试用例下更容易失败.

同时,从表1变异体怀疑度公式中可以看出,变异体的怀疑度值与akf呈正相关关系,与akp呈负相关关系.本文通过计算变异体m在测试用例上akf与akp的差值来度量该变异体对错误定位的影响程度,即贡献度C(Contribution):

其中,T表示测试用例集,P表示被测程序.C(T,P,m)越高表示该变异体的贡献度越高.

同理,对变异体集合M的平均贡献度AC(Average Contribution)的计算公式为:

其中,|M|表示集合中变异体的数量.

目前研究人员对FOMs和HOMs 之间的关系进行了研究.如Gopinath 等[21]的研究表明许多HOMs 与它们组成的FOMs 在语义上是不同的.然而,Langdon等[22]的研究表明被测试用例杀死的HOMs 数量高于杀死FOMs的数量,因此HOMs 相对于FOMs,更容易被测试用例检出.

在早期的研究中,Offutt 等[15]指出:杀死n阶变异体是否意味着我们可以检出复杂错误还有待确定.为了回答这个问题,我们是第一个进行关于比较FOMs和HOMs 在定位程序错误上的控制实验的.

2.2 研究动机

在先前的研究中,大部分MBFL 技术基于单错误假设[5,9,13,23].然而,实证研究表明[24],单个程序失败往往是由系统中的多个故障触发的.Digiuseppe和Jones 发现,多个错误对错误定位的精度有负面影响[25].

此外,Offutt的研究结果认为,杀死n阶变异体是否可以检测到复杂的错误还有待确定[15].在Debory和Wong的研究中[26],他们发现他们所提出的策略不能修复同一个程序中的多个错误,是因为他们只考虑了FOMs.换句话说,采用HOMs 来定位或修复程序中的多个缺陷是一种潜在可行的方法.因此,本文主要通过实证研究HOMs 在单错误和多错误程序上的定位效果,并分析多错误与HOMs 之间的关系.

(1)HOMs 分类

依据变异体在程序中的不同变异位置,我们将HOMs分成3 类.为便于理解这3 类变异体,我们采用带有两个错误(f1和f2)的程序p作为例子.首先,我们HOMf1为变异了错误语句f1的HOMs 集合且HOMf1∈HOMs;HOMf2变异了错误语句f2的HOMs 集合且HOMf2∈HOMs.

其次,如图1所示,我们将HOMs 分为以下3 类:

类A:准确高阶变异体(Accurate HOMs).即,同时在错误语句f1和f2 上变异生成的HOMs.(HOMf1∩HOMf2).

类B:部分准确高阶变异体(Partially accurate HOMs).即,只在错误语句f1 或f2 上变异生成的HOMs.(HOMf1HOMf2)∪(HOMf2HOMf1)

类C:不准确高阶变异体(Inaccurate HOMs).即,在其他语句上变异生成的HOMs.(HOMs(HOMf1∪HOMf2)

上述3 种HOMs 反映出不同HOMs的生成方法.我们推测这3 类HOMs 在错误定位上有不同的表现.基于这种推测,我们进行了一次大规模的实证研究来分析3 类HOMs的特性.

(2)MBFL 例子

为进一步说明我们的研究动机,我们使用图2中的例子来说明FOMs和HOMs 如何在MBFL 上使用.

在图2中,从左到右,第1 列为被测程序的源代码,其中语句s4和s11为错误语句.第2 列为对应语句生成的变异体集合,第3 列划分为6 部分,分别是6 个测试用例在变异体上的执行信息,其中“1”表示测试用例杀死对应的变异体,“0”表示测试用例没有杀死对应的变异体,第4和第5 列表示计算得到的变异体怀疑度和语句怀疑度,最后一列表示对应语句的排名.在这个例子中,每一个变异体的怀疑度都是用Ochiai 公式计算的.在图2中有两个给出的结果,一个是FOMs的结果,另一个是HOMs的结果.

图1 HOMs 分类

图2 MBFL 例子

使用FOMs 进行错误定位.假设MBFL 技术在失败测试用例覆盖的每条语句只生成两个变异体,该程序下共生成14 个FOMs(列“FOMs”所示).MBFL 首先利用测试用例的杀死信息计算FOMs的怀疑度(列“FOMs 怀疑度”所示).接下来,同一语句生成的变异体中,取最大的怀疑度记为该语句的怀疑度.最后,在“排名”列中,MBFL 将错误语句s4和s11都排在第3 位.

使用HOMs 进行错误定位.我们首先利用来自不同语句的两个FOMs 构造HOMs,最后生成3 类共14 条HOMs(列“HOMs”所示).计算得到的HOMs 怀疑度如列“HOMs 怀疑度”所示.接着,为保证公平性,我们通过计算语句相关HOMs 怀疑度的均值作为该语句的怀疑度.以语句s1为例子,与s1相关的HOMs 有3 个(HOM6,HOM11和HOM13),其对应的怀疑度分别为1.00,0.41,和1.00.因此,计算得到的语句s1的怀疑度为Sus(s1)=(1.00+0.41+1.00)/3=0.80.最终,使用HOMs计算得到的语句怀疑度如列“语句怀疑度”所示.最终,HOMs 将错误语句s4和s11分别排在第3 名和第2 名.

基于上述的例子,我们可以发现FOMs 将两条错误语句排在前五名,然而HOMs 将错误语句排在前三名,表明HOMs 在这个例子中有更好的错误定位效果.更进一步,在高阶变异错误定位中,三类变异体对错误定位有不同的贡献,结合式(2),准确HOMs的平均贡献度为:

部分准确HOMs的平均贡献度为:

不准确HOMs的平均贡献度为：

从以上结果可以看出,准确HOMs的平均贡献度等于部分准确HOMs,不准确HOMs的平均贡献度最低.据我们所知,本文首次研究FOMs和HOMs 在多错误程序上的定位效果.更进一步,我们研究了三类HOMs的错误定位效果并分析其差异.

3 实验设计

本章讨论实验中使用的程序和实验设计流程,用以解决提出的研究问题.图3中显示了实验研究设计流程.下面将依次介绍设计流程的每个部分.

图3 实验设计流程

3.1 实验程序

本文选择了错误定位领域常用的软件基准程序库(Subject Infrastructure Repository,SIR)[27]中的5 个程序作为实验对象,分别为printtokens2,schedule2,totinfo,tcas和sed.这些程序均为开源的C 程序,其中前4 个程序来自西门子套件(Siemens Suite),sed是大型的真实错误程序.实验中使用的错误版本和测试用例均可在SIR 库中下载.这些程序在高阶变异测试领域中广泛使用[12,28-30],同时也经常应用在错误定位等相关的研究中[18,19,23,26].因此我们认为本文测试数据集所得出的结论具有一定的普适性.

表2列出了基准程序的具体信息,包括程序名称,程序所有的版本数量和实验中使用的数量,程序的平均代码行以及FOMs和HOMs的数量.其中,FOMs 列的“生成的数量”子列表示对应程序生成的FOMs 总数,而“使用”子列表示实验中实际运行的FOMs 总数.本文共选择了63 个单错误版本程序作为实验对象,部分版本因为错误语句无法生成有效变异体而导致测试用例无法检测出该版本的错误,或因为执行过程中出现异常,无法收集到完整的执行信息.

表2 实验基准程序及变异体信息

3.2 生成变异体

为了研究FOMs和HOMs 在单错误和多错误程序中的表现,实验首先需要生成FOMs和HOMs.在这个步骤中,我们收集被失败测试用例覆盖的程序语句,通过变异算子植入错误到这些语句,进而生成相应的变异体.表3列出了Agrawal 等[16]提出的10 种经典C 语言变异算子.

表3 经典C 语言变异算子

对于生成FOMs,我们对fail 测试用例覆盖的每条语句使用所有变异算子进行变异,每次只对一条语句变异,最终生成161 218 个FOMs.表2“FOMs”列的“(使用)”子列中列出了每个程序所使用的FOMs数量.

对于生成高阶变异体,在已有高阶变异测试的研究中,对变异体阶数的研究有所不同,有关注于阶数较低(2 至4 阶)的研究[15,28,29,31],也有关注阶数较高(2 至15 阶)的研究[12,32-35].本文首次考虑将高阶变异体应用于多错误定位,然而在实际程序中错误数量是不可知的,因此结合前人的研究成果,我们选择生成2 至7 阶的变异体来模拟多错误情况.在此基础上,为了进一步探究不同变异位置的高阶变异体与错误定位的关系,我们依据不同的变异位置对变异体进行了划分,并通过理论和实验分析发现错误语句处生成的变异体(如准确HOMs和部分准确HOMs)具有更优的错误定位效果.另一方面,考虑到MBFL 巨大的执行开销,我们选择生成每阶HOMs的数量与FOMs 数量相同来减少HOMs的数量.假设生成1000 个FOMs,然后2 阶变异体和3 阶变异体的数量也是1000;因此最终生成的HOMs为6000.在我们的实验中,采用一阶变异算子FOP 构建HOMs.具体来说,首先随机选择k条失败测试用例覆盖的语句,然后对每条选择的语句,随机选择一个与其相对应的一阶变异算子,最终生成一个k阶变异体.实验共生成967 308 个HOMs,其中实际使用的数量如表2所示(“HOMs”列的“(使用)”子列).

3.3 构建多错误定位场景

为了构建实验中的多错误定位场景,我们通过随机组合SIR 库中的原始单错误程序获得多错误程序.每个多错误程序中的错误数量是2 到5 个.最终生成100 个版本的多错误程序.最后,依据多错误程序生成的变异体,运行变异体收集测试结果用于效果分析.

3.4 评估MBFL的效果

为了评估FOMs和HOMs 在MBFL 中的定位效果,我们使用了3 种研究人员常用的评估指标[36-39].

(1)EXAM:EXAM[36,37]是错误定位领域广泛使用的评价指标之一,用于评估开发人员找到准确错误位置之前需要检查的程序实体的比例,因此EXAM值越小表明对应的错误定位效果越好[36,37].EXAM的公式定义如下:

式(6)中,分子是错误语句的排名,分母是需要检查的程序语句数量的总和.rank的计算公式为:

式(7)中,i表示怀疑度值大于错误语句的正确语句的数量,j表示怀疑度值等于错误语句的正确语句的数量.为更接近真实定位场景,我们选择第i+1 位排名与第i+j位排名的平均作为错误语句的排名.

(2)Top-N:Top-N 用于评估排名前N个程序候选元素中,能定位到真实错误的个数[38].在Kochhar 等的研究发现,73.58%的开发者只检查排名前5的程 序元素,并且几乎所有的开发者认为检查排名前10的程序元素是可接受的上限[39].因此,参考之前的研究[36,38],我们将N设定为1,3,5.同时,假设两条语句有相同的怀疑度,我们同样计算这些语句排名的平均值(如式(7)所示).Top-N 越大表明对应的错误定位技术越好.

(3)MAP:MAP (Mean Average Precision)是信息检索领域用于评估语句排序质量的指标,是所有错误平均精度的平均值[40].AP(Average Precision)的计算公式如下:

式(8)中,i是程序语句的排名,M是排名列表中语句的总数,pos(i)是布尔函数,pos(i)=1 表示第i条语句是错误的,反之pos(i)=0 表示第i条语句是正确的.P(i)是每个排名i的定位精度.

MAP是错误集合的AP的平均值,MAP 越大表明对应的错误定位技术越好.

4 实验结果

4.1 研究问题

为了评估HOMs是否能提高错误定位的精度,本文从错误定位精度角度出发,提出如下研究问题:

(1)RQ1:与FOMs 相比,不同阶数的HOMs的多错误定位精度如何？

(2)RQ2:与FOMs 相比,不同类型的HOMs的多错误定位精度如何？

4.2 实验结果

为探究RQ1,我们首先针对多错误程序生成一阶HOMs,然后运行这些变异体计算得到每个程序对应的EXAM,Top-N和MAP.本文使用Metallaxis-FL为原始MBFL 对照组,并生成2 阶到7 阶的HOMs.

图4中展示了MBFL 使用FOMs和不同阶的HOMs的错误检查比例.x轴表示代码检查比例,y轴表示不同程序所有错误版本查找到的累积错误比例,对应的曲线越接近y轴表明对应的变异体的检测错误数量越多,因此对应的变异体错误定位效果更好.

图4 FOMs 与不同阶 HOMs的代码检查比例比较

从图4(a)中可以看出,7-HOMs 检测20%的程序代码能检测到68%的错误,而FOMs 只能检测到55%的错误.同理,在schedule2,totinfo和sed 上可以看出,HOMs 检测更少的代码能检测到更多的错误,但在tcas 程序上FOMs的检测效果优于HOMs.

从Top-1,Top-3,Top-5 指标来看,FOMs 在2 错误程序上的定位效果比HOMs 更好,而HOMs 在3 错误和5 错误程序上的表现比FOMs 更好.表4中显示了FOMs和HOMs 在多错误程序定位场景下排在前1,3,5 位错误的数量.图中包括4 种错误数量的程序统计结果.对2 错误程序,FOMs和各阶高阶变异体都将19 个错误排在第一名.除了7-HOMs,FOMs 比其他阶数的HOMs的Top-3,Top-5 要更高.对3 错误程序,3-HOMs比FOMs和其他阶数的变异体在Top-3和Top-5 上更高.同时FOMs 在4 错误程序中,Top-3和Top-5 上的表现略优于HOMs.最后,在5 错误程序上,FOMs、6-HOMs和7-HOMs的Top-1 值最高,而6-HOMs和3-HOMs 分别在Top-3和Top-5 上表现最好.

从MAP 指标来看,FOMs 在4 错误程序上表现最优,在其他错误程序上与HOMs 有相近的表现.从表5可以看出,FOMs 在4 错误程序上的MAP 均值最高.在其他错误程序上与HOMs 有相近的表现,例如3 错误程序FOMs的MAP 均值与4 阶到7 阶的变异体的MAP 均值相同.

综上可以看出,HOMs 在一些程序上的检错能力优于FOMs.同时,FOMs 在2 错误和4 错误程序上的定位效果较好,而HOMs 在3 错误和5 错误程序上的效果更好.HOMs 在3 错误和4 错误程序上有更大的Top-N 值,并且在一些阶数的HOMs 下,计算的MAP均值都要高于FOMs.

表4 FOMs和不同阶HOMs的TOP-N 值比较

表5 FOMs和不同阶HOMs的平均MAP 值比较

由于FOMs 只使用一次变异算子生成而HOMs 使用多次变异算子生成.因此在对同一个程序变异生成等量变异体时,HOMs 有更大的概率变异到错误语句,从而增大变异体被杀死的概率,相应akf值也会更高,则变异体怀疑度也越高,最终计算的语句怀疑度也越高,其定位效果也更优(如图4(a),图4(c),图4(e);表4“3 错误”行,“5 错误”行;表5“3 错误”行,“5 错误”行).但如果HOMs 中更多变异体是对正确语句变异生成的,那么相应的akp值会更高,计算的语句怀疑度值也更高,错误定位效果将更差.(如图4(d);表4“2 错误”行,“4 错误”行;表5“2 错误”行,“4 错误”行).综合比较可以得出HOMs 在一定程度上能提高多错误定位的效果.

为探究RQ2,我们首先收集多错误程序所有版本下3 类HOMs的EXAM 值,然后分别计算Top-N和MAP 指标.为了便于展示,我们将3 类HOMs 分别表示为“Accurate”(准确HOMs),“Part-accurate”(部分准确HOMs)和“Inaccurate”(不准确HOMs).图5表示MBFL 使用FOMs和3 类HOMs 在不同程序上所有版本的错误检查比例.从图5(a)-图5(c)中可以看出Accurate HOMs 与FOMs 有相近的表现,并且Accurate HOMs的检测效果优于FOMs.而在tcas和sed (图5(d)、图5(e))程序上,Part-accurate的检测效果更好,检查更少量的代码而找到更多的错误.同时在所有程序上,Inaccurate的检测效果最差.

图5 FOMs 与不同类 HOMs 代码检查比例比较

从Top-N 指标来看,准确HOMs 比FOMs和另外两类变异体能将更多错误排在前1,3,5 名.表6中显示,在2 错误程序上,准确变异体与FOMs 能够排列相同数量的错误在Top-1,Top-3和Top-5,而在其他错误程序版本中,准确HOMs的Top-N 指标均为最大.同时可以发现,部分准确HOMs 在4 错误和5 错误程序上,有更高的Top-5 值.然而不准确HOMs的表现最差.

从MAP 指标来看,准确HOMs的表现同样优于FOMs,部分准确和不准确HOMs.表7中准确HOMs 与FOMs 在2 错误程序下有相同MAP 平均值,而在3,4,5错误程序下,准确HOMs 仍然比另外两类变异体的定位效果好,其MAP 平均值分别为0.0017,0.0009,和0.0008.

综上所述我们可以发现,准确HOMs的错误定位精度高于FOMs、部分准确HOMs和不准确HOMs.在一些情况下,部分准确HOMs 有更好的定位效果,但普遍情况下不准确HOMs的表现都很差.

表6 FOMs和不同类HOMs的Top-N 值比较

表7 FOMs和不同类HOMs的MAP 值比较

三类HOMs 由于其不同的生成机制,造成最终定位效果的差异.首先,准确HOMs 准确变异错误语句,并且对正确语句不作任何变异,几乎能够被所有的失败测试用例杀死而不被通过测试用例杀死,其akf值高且akp值低,因此最终计算的错误语句的怀疑度值会高,其定位效果也就更优(如图5,表6,表7).其次,部分准确HOMs 同时对错误语句和正确语句变异,会被部分失败测试用例和正确测试用例杀死.其定位效果取决于被失败测试用例杀死的比例,比例较高则定位精度高,比例较低则定位精度低.因此部分准确HOMs的定位效果存在波动(如图5,表6“5 错误”行,表7).最后,不准确HOMs 只变异正确语句,不对错误语句进行变异,那么其更容易被正确测试用例杀死且不易被失败测试用例杀死,计算的错误语句的怀疑度较低,定位效果也就最差(如图5,表6,表7).因此生成一些特定的HOMs,比如准确HOMs,能有效提升多错误定位的精度.

5 结论与展望

为探究HOMs是否能提升多错误程序定位,本文进行了大规模的实证研究.研究结果发现,HOMs 在3 错误和5 错误程序上,有更高的错误定位精度.根据不同的变异位置,我们将HOMs 分成3 类.我们发现准确HOMs 比FOMs和其他两类变异体有更好的多错误定位效果.因此,HOMs 在一定程序上能够提升多错误程序定位,并建议研究人员设计方法生成更有效的变异体,比如准确HOMs.在后续的研究中,作者将研究新的策略用于选择有效提升多错误定位精度的变异体.同时考虑扩大实验数据集来验证HOMs 对错误定位的影响.