2014, Vol. 25
随着软件规模越来越大,逻辑越来越复杂,对软件可靠性的要求也越来越高.影响软件可靠性的一个主要因素是软件中潜在的错误,这些潜在的软件错误不仅给计算机应用系统带来不利影响,甚至可能造成巨大的经济损失和灾难性的后果.传统的软件错误定位方法大多采用设置断点等人工分析的方法,人工定位错误不仅难度大,而且极其耗时.因此,如何有效检测并快速准确地定位和消除软件错误,得到了研究人员的广泛关注.
错误定位[ 1,2,3,4 ]的精度高度依赖于使用的测试用例,测试用例的数量和质量是决定错误定位的成本和有效性的关键因素.因此,为错误定位提供有效的测试用例,不仅有助于分析软件错误产生的原因,还能极大地提高软件错误定位的效率.目前,测试用例约简的研究大多用于软件测试,而用于错误定位的测试用例约简方法的研究较少.如:Abreu等人[ 5 ]研究了正确测试用例和错误测试用例的数目对错误定位的影响;Baudry等人[ 6 ]将相同测试用例所覆盖的语句定义为动态基本块,研究表明,增加动态基本块的数量有助于提高错误定位精度;Zhang等人[ 7 ]将相对冗余的思想用于错误定位约简方法中,并指出,均衡语句覆盖有助于错误定位;Chen等人[ 8 ]指出软件错误之间存在着相互联系,在此基础上提出了一种轻量级测试用例约简方法,以定位更多的软件错误; Renieris等人[ 9 ]提出“近邻模型”,该模型的主要思想是,在失效测试用例的邻域附近选择成功测试用例,利用失效测试用例和成功测试用例的测试信息进行差异分析以定位故障,但选择的方法是通过对比两条路径所执行的基本语句块的集合来实现的,未考虑在循环分支条件下语句块的执行序列;Wang等人[ 10 ]提出根据错误路径生成最相似的正确路径,但算法的复杂度很高并只能生成一条成功路径,且对赋值错误的定位不太敏感;北京大学的郝丹等人[ 11,12 ]主要研究基于语句覆盖的测试用例约简方法,提出了不同的测试用例约简策略,为基于测试用例的故障定位提供高语句覆盖的测试集合,并指出测试用例的冗余或相似降低了错误定位的精度,但它只考虑了语句覆盖,没有考虑路径覆盖;Yu等人[ 13 ]将相对冗余思想用于测试用例约简,提出基于向量的测试用例约简方法,通过实验证明,与基于语句覆盖的测试用例约简方法相比,基于向量的测试用例约简方法更有利于错误定位.目前的测试用例约简方法都只研究了程序运行时的覆盖情况,忽略了程序运行时的路径信息以及错误测试用例对错误定位的影响,因此,约简后的测试用例对错误定位的精度没有明显提高.
软件错误定位近年来已成为一个热点研究问题,主要方法有程序切片、程序谱、统计分析、状态变更、模型检验等.程序切片方法[ 14,15,16 ]所需测试用例较少,但不提供语句的可疑程度描述,并且切片规模仍然可能很大,在切片中观察程序的行为代价较大.程序谱方法[ 17,18,19,20,21,22,23,24 ]提供语句的可疑程度描述,但缺少对错误行为的分析,仍需开发人员确定应用程序的期望行为,以确认和修正错误,主要方法包括Tarantula[ 17 ],WHITHER[ 18 ],Zoltar[ 19 ]等.状态变更方法[ 25, 26, 27, 28 ]和模型检验方法[ 29, 30, 31 ]提供了错误行为信息,可以辅助开发人员理解软件错误.但是对于复杂系统而言,这两种方法的开销很大,限制了它们的有效性.统计分析方法[ 32, 33, 34, 35, 36, 37, 38, 39, 40 ]具有计算复杂度低、准确性较高的优点,是一种很有发展前景的方法,例如SBI[ 32 ],Holmes[ 33 ],SOBER[ 34 ]等.然而,统计分析的方法缺少对程序元素间的相互影响的分析,对测试用例的数量和质量要求高.CP[ 38 ]方法分析了程序的控制依赖关系,通过分析程序的执行状态定位语句错误.在以前的工作中,我们提出了基于状态依赖概率的错误定位方法(后面将其简称为SF).该方法在控制依赖图的基础上分析了语句的状态依赖关系,进而定位错误语句.Jiang等人[ 39 ]提出结合特征选择、聚类、控制流图遍历来辅助查找生成错误路径,辅助诊断潜在的错误.RankCP[ 40 ]方法分析了程序的控制依赖以及数据依赖信息,通过分析元素间的条件依赖关系定位错误语句.
尽管在软件错误自动定位领域已有很多研究,但仍存在以下关键问题没有得到良好的解决:
(1) 如何将软件测试与错误定位有机结合,为错误定位提供有效的测试用例,以提高错误定位的精度;
(2) 如何提供一种自动的软件错误定位方法,使其充分分析程序元素间的相互影响,以有效地定位软件错误.
针对以上问题,本文提出结合测试用例约简和联合依赖概率建模的软件错误自动定位方法,将测试用例约简、错误定位有机地统一为一个整体.首先,针对软件错误定位自身的特点,提出面向错误定位需求的测试用例约简方法,为错误定位提供有效的测试用例,降低错误定位的复杂度,并且提高错误定位的精度;然后,定义一种新的统计分析模型——联合依赖概率模型;在此基础上,提出可疑语句的定位和排序方法,以有效定位错误语句.
1 结合测试用例约简与联合依赖概率建模的软件错误自动定位模型如图 1所示,本文将测试用例约简与软件错误定位有机结合,提出面向错误定位需求的测试用例约简方法,同时提出结合测试用例约简和联合依赖概率建模的软件错误自动定位方法.
 | Fig. 1 Model of automatic fault localization approach combining test cases reduction and joint dependency probabilistic model图 1 结合测试用例约简与联合依赖概率建模的软件错误自动定位模型 |
(1) 采用面向错误定位需求的测试用例约简方法,为错误定位提供合适的测试用例,降低错误定位的复杂度,并且提高错误定位的精度;
(2) 通过运行精简的测试用例,获取节点的控制依赖信息和数据依赖信息.结合程序的控制流图和数据依赖图,分析节点在不同状态下的联合依赖关系,进而建立联合依赖概率模型;
(3) 采用基于联合依赖概率模型的错误定位方法,对程序语句按可疑度进行降序排列.
2 面向错误定位需求的测试用例约简 2.1 面向错误定位需求的测试用例约简模型
本文提出的面向错误定位需求的测试用例约简模型如图 2所示.该模型主要分为3个模块:数据预处理模块、基于语句覆盖和错误定位需求向量约简模块、基于执行路径信息约简模块.
 | Fig. 2 Model of test cases reduction approach oriented to fault localization requirement图 2 面向错误定位需求的测试用例约简模型 |
(1) 数据预处理:利用插装器向程序中插入探针,通过动态执行测试用例,捕获插装信息(主要包括语句覆盖信息和具体的执行路径信息);
(2) 基于语句覆盖和错误定位需求向量的测试用例约简:面向错误定位的需求,通过执行错误测试用例并计算错误定位需求向量,删除与错误测试用例无关和关系较小的正确测试用例;
(3) 基于执行路径信息的测试用例约简:对具有相同语句覆盖的测试用例,分析其对应的执行路径信息,删除其中执行路径完全相同的冗余的测试用例.对剩余的路径进行循环标准化,删除冗余路径对应的测试用例.
为了更好地理解语句覆盖向量和路径向量,下面加以举例说明.程序如图 3所示,此函数的功能是求n个数的最大数和最小数,执行测试用例t:n=3,a[×]={11,13,12},动态执行得到的语句覆盖向量是{1,1,1,1,1,1,1,0,1,1},路径向量是{0,1,2,3,4,6,8,3,4,5,6,8,3,4,6,8,3,9}.
 | Fig. 3 Example program max_min()图 3 程序实例max_min() |
2.2 基于语句覆盖和错误定位需求向量的测试用例约简
与未被错误测试用例执行的语句相比,被错误测试用例执行的语句更有可能是错误的.而所有正确测试用例和错误测试用例都执行的语句(如函数入口等),出错的可能性比较小.基于这一思想,本文定义了两类错误定位需求:一类是面向含有单个错误程序的错误定位需求,此时,被所有错误测试用例都执行的语句,出错的可能性更大,这些语句更有助于定位错误,则约简后的测试用例应该执行这些语句,因此,错误定位需求向量由对所有测试用例对应的覆盖向量求交得到;另一类是面向包含多个错误程序的错误定位需求,此时,每个错误测试用例可能只执行其中一个或几个错误语句,每个错误测试用例执行的语句都可能是错误语句,则被错误测试用例执行过的所有语句都将有利于定位错误,因此,错误定位需求向量由对所有错误测试用例对应的覆盖向量求并得到.根据以上分析,本文提出基于语句覆盖和错误定位需求向量的测试用例约简方法,删除与错误定位需求无关或关系较小的测试用例,如图 4所示.
 | Fig. 4 Model of test cases reduction based on statement coverage and fault localization requirement vector图 4 基于语句覆盖和错误定位需求向量的测试用例约简方法模型 |
(1) 通过执行错误测试用例,得到每个错误测试用例所对应的覆盖向量.由于错误测试用例覆盖向量直观地反映了错误测试用例对各个语句的覆盖情况,因此,错误语句必然包含在错误测试用例对应的覆盖向量中.对于含有单个错误的程序,对所有错误测试用例对应的覆盖向量求交,即可得到错误定位需求向量;而对于含有多个错误的程序,对所有错误测试用例对应的覆盖向量求并,可得到错误定位需求向量;
(2) 通过执行正确测试用例,得到正确测试用例覆盖向量集;
(3) 被所有正确测试用例和错误测试用例都执行的语句,对错误定位的贡献不大.因此,屏蔽错误定位需求向量和正确用例覆盖向量集中都执行的语句,将屏蔽后的各个正确测试用例向量与屏蔽后的错误定位需求向量求交,如果结果为全0,表明该正确测试用例与错误定位需求无关或关系较小,加以删除,最终得到基于语句覆盖和错误定位需求向量的测试用例约简后的测试用例.
2.3 基于执行路径信息的测试用例约简方法
已有研究表明:均衡语句覆盖有助于错误定位[7],但具有相同语句覆盖的测试用例,所对应的执行路径未必相同.仅根据语句覆盖集合约简测试用例,可能会丢失很多有用的路径信息.因此,本文提出基于执行路径信息的测试用例约简方法,以均衡执行路径的覆盖,如图 5所示.
 | Fig. 5 Model of test cases reduction based on path information图 5 基于执行路径信息的测试用例约简方法模型 |
对经过基于语句覆盖和错误定位需求向量的测试用例约简后的测试用例进行如下操作:
(1) 提取具有相同覆盖的测试用例所对应的执行路径,删除完全相同路径对应的冗余测试用例;
(2) 对步骤(1)中的剩余路径进行循环标准化,删除冗余路径对应的测试用例,最终得到均衡路径覆盖和约简后的测试用例.
循环标准化的实质就是对每一条路径,将连续的重复片段进行去重,如果几条路径经过标准化后的结果相同,则只保留循环次数最少的路径所对应的测试用例.例如,测试用例t1和t2所对应的执行路径为{0,1,2,3,4,6,8,3, 4,5,6,8,3,4,6,8,3,9}和{0,1,2,3,4,6,8,3,4,6,8,3,4,6,8,3,4,5,6,8,3,4,5,6,8,3,4,6,8,3,4,6,8,3,9},二者标准化后结果都为{0,1,2,3,4,6,8,3,4,5,6,8,3,4,6,8,3,9}.而t1所对应的执行路径循环次数较少,因此删除测试用例t2,只保留t1.
3 基于联合依赖概率模型的错误定位方法 3.1 联合依赖概率模型程序的控制依赖关系描述了一条程序语句语义的变化是否影响其他语句的执行状况.数据依赖描述了变量的定义、使用和引用关系.将控制依赖和数据依赖相结合,可以更好地分析程序元素间的相互影响.因此,在分析程序控制依赖和数据依赖的基础上,本文提出了联合依赖概率模型用于错误定位.
定理1(联合依赖概率模型). 程序代码P的联合依赖概率模型是一个三元组(D,S,R),它记录了节点在不同状态下的依赖概率,其中,
(1) D=(N,E)是P的数据依赖图,N为节点集合,E为数据依赖边集合,表示程序的数据依赖信息;
(2) S是节点到状态的映射.每个节点都对应一个与程序执行相关的状态集合:分支节点和循环节点的状态是其谓词的值(真或假);其他节点的状态表明该节点是否被执行,若节点被执行则为真,否则为假;
(3) R是各节点的联合依赖概率.节点联合依赖概率是根据运行测试用例得到的节点状态依赖概率和节点条件依赖概率计算得到的.
联合依赖概率模型的建立方法如图 6所示.
 | Fig. 6 Establishment of joint dependency probabilistic model图 6 联合依赖概率模型建立方法 |
(1) 通过执行多组测试用例,捕获节点控制依赖轨迹和数据依赖轨迹.
例如,对于程序实例max_min(×)(如图 3所示),执行测试用例t:n=3,a[×]={11,13,12},捕获的控制依赖轨迹为0,1,2,3(true),4(false),6(false),8,3(true),4(true),5,6(false),8,3(true),4(false),6(false),8,3(false),9;捕获的数据依赖轨迹为3(true,(d3[i],d0[n])),4(false,(d3[i],d1[max])),6(false,(d3[i],d1[min])),3(true,(d3[i],d0[n])),4(true,(d3[i],d1[max])),5(d3[i]),6(false,(d3[i],d1[min])),3(true,(d3[i],d0[n])),4(false,(d3[i],d5[max])),6(false,(d3[i],d1[min])).其中, 4(false,(d3[i],d1[max]))表示节点4的执行状态是false,并且节点4数据依赖于节点3和节点1,数据依赖变量分别为i和max.
(2) 根据控制流图(CFG)和控制依赖轨迹,计算节点状态依赖概率,即,节点被执行的概率P(state).分支节点和循环节点记录还需记录状态为真和状态为假的概率,即,P(state=true)和P(state=false);
(a) 对于程序中的每个节点,计算节点被执行的概率:
(1)
(b) 对于分支节点和循环节点,节点的状态分为真和假.因此,除计算节点被执行的概率外,还需计算节点状态为真和状态为假的概率,则有,
P(state)=P(state=true)+P(state=false) (2)
(3)
(4)
(3) 根据数据依赖图(DDG)和数据依赖轨迹,计算节点条件依赖概率(节点在某一状态下,与其数据依赖节点之间的概率),即,P(data dependency|state):
(5)
其中,n(state,data dependency)为节点在数据依赖轨迹中,状态为state、数据依赖为data dependency出现的次数; n(state)为节点在数据依赖轨迹中,状态为state出现的总次数.
(4) 根据节点状态依赖概率和节点条件依赖概率,计算节点联合依赖概率,联合依赖概率为P(state,data dependency),表示节点状态为state、同时数据依赖为data dependency的概率.
联合依赖概率=条件依赖概率x状态依赖概率 (6)
即:P(state,data dependency)=P(data dependency|state)xP(state) (7)
3.2 基于联合依赖概率模型的错误定位方法如果某个节点的联合依赖关系在错误测试用例执行过程中出现的频率较高,而在正确测试用例执行过程中出现的频率较低或没有出现,则该节点的联合依赖关系很可能是错误的.基于这种思想,本文提出了基于联合依赖概率模型的错误定位方法,如图 7所示.
 | Fig. 7 Fault localization approach based on joint dependency probabilistic model图 7 基于联合依赖概率模型的错误定位方法 |
(1) 分别根据正确测试用例和错误测试用例建立联合依赖概率模型.分别记为“联合依赖概率模型(true)”和“联合依赖概率模型(false)”;
(2) 根据“联合依赖概率模型(true)”和“联合依赖概率模型(false)”计算各联合依赖关系的可疑度(suspicious_score(JD)),并根据可疑度对联合依赖关系所对应的节点进行排序.
(8)
对于公式(8),以下两点需要注意:
(1) 对于Pfailed(JD)为0的节点,不计算其联合依赖关系的可疑度,因为概率为0表示该联合依赖关系在错误测试用例中未出现,则此联合依赖关系出错的可能性极小;
(2) 若分母为0,表示该联合依赖关系在正确测试用例中未出现,则该联合依赖关系出错的可能性极大.对于分母同时为0的节点,比较其分子的大小.分子越大,表明该联合依赖关系在错误测试用例中出现的次数越多,则,更有可能是错误.
对于分支节点和循环节点,还需要计算状态为真和假时的联合依赖关系的可疑度,即:
suspicious_score(JD|state=true)和suspicious_score(JD|state=false).
在实验中,选择suspicious_score(JD|state=true)和suspicious_ score(JD|state=false)的较大者作为suspicious_ score,进行错误排名.
4 实验结果分析 4.1 实验数据本文的实验数据使用了Siemens Suite[41]和space[42, 43],具体信息见表 1.表中第1列为程序名称,第2列为每个程序对应的错误版本个数,第3列为程序可执行代码的行数,第4列为每个程序提供的测试用例个数,第5列为每个程序的功能描述.Siemens Suite包含7组实现不同功能的C程序,每组程序通过人工注入的方式创建了基本程序的错误版本,这些错误通常通过修改程序中的一行代码来注入,包括语句的增删和判断条件的修改等,以模拟实际中可能存在的错误.space由欧洲航天局开发,与Siemens Suite相比,space具有更多的代码行数和测试用例.在这170个版本中,删除了其中的21个错误版本,包括:(1) 无错误测试用例:schedules2的第9个版本,replace的第32个版本,space的第1,2,3,12,32,34个错误版本;(2) 仅头文件错误:print_tokens的第4和第6个错误版本; (3) 程序段错误:replace的第27个版本,print_token2的第10个版本,schedule的第5,6,9个版本,space的第25,26,30,35,36,38个版本.删除21个版本后,对Siemens Suite的123个版本和space的26个版本进行了实验.
|
Table 1 Experimental subject programs 表 1 实验数据 |
4.2 实验结果及分析 4.2.1 测试用例约简方法实验结果分析
本文对Siemens Suite提供的7个程序的123个错误版本和space程序的26个错误版本进行了实验.箱式图可直观分析、比较多组数据平均水平和变异程度,具体包括数据的5个特征值:最小值、最大值、中位数、四分之一位数和四分之三位数.其中,四分之一位数和四分之三位数构成箱子的上下两个边,箱子中间的点为中位数,上下两个点为最大值和最小值.
本文采用箱式图统计了8组程序约简率(reduction rate)的分布情况,如图 8所示.
 | Fig. 8 Distribution of percentage in test cases size reduction图 8 约简率分布情况 |
由图 8可以看出,8组程序的箱式图的覆盖范围都比较小,表明约简的测试用例数目比较集中.schedule的最大值比较大,远远偏离了箱式图,这是因为对于schedule的第4个错误版本,在2 650个测试用例中,大部分测试用例所对应的路径基本相同,经循环标准化后删减了大部分测试用例,最终仅剩357个测试用例.尽管约简后的测试用例数目较少,但并未影响错误定位的精度.采用Tarantula方法进行错误定位时,使用约简前2 650个测试用例,错误定位排名为第161位,而使用约简后的357个测试用例,错误定位排名提高到第66位.其中,约简率(reduction rate)使用Yu等人[13]提出的公式(9)进行计算.
(9)
对于程序space,Yu等人[13]在其实验中人工加入了20个错误版本,与本文的实验版本数目不同.因此,本文仅将Siemens Suite的结果与Yu等人提出的方法进行比较,见表 2.其中,SA为基于语句覆盖的测试用例约简方法,VA为基于向量的测试用例约简方法.由表 2可以看出,SA方法具有最大的约简率,本文方法与VA方法的约简率相似.
|
|
Table 2 Experimental results of mean reduction rate on Siemens Suite (%) 表 2 Siemens Suite测试集中平均约简率实验结果(%) |
为了与Yu等人提出的方法作对比,本文将未约简的测试用例和约简后的测试用例作为Tarantula[17]的输入,并记录错误定位结果.结果见表 3,其中,消耗增量(ExpenseChange)定义为
(10)
|
|
Table 3 Experimental results of mean ExpenseChange on Siemens Suite 表 3 Siemens Suite测试集中ExpenseChange均值实验结果 |
由表 3可以看出:SA方法的ExpenseChange皆为负值,表明SA约简后的测试用例降低了错误定位的精度; VA方法的ExpenseChange有正有负,说明VA方法约简后的测试用例,有些版本可以提高错误定位的精度,有些版本却降低了错误定位的精度;而本文提出的测试用例约简方法的ExpenseChange都为正值,且值相对较大,说明本文提出的测试用例约简方法可以有效提高错误定位的精度.
表 4为本文方法在space测试集中的实验结果.由于space程序的可执行代码行数较大,因此,尽管ExpenseChange值相对较小,为0.129,根据公式(10),可疑语句排名平均上升8位,可以有效节省开发人员定位软件错误的时间.
|
|
Table 4 Experimental results of test cases reduction on space program 表 4 space测试集中测试用例约简实验结果 |
4.2.2 错误定位方法实验结果分析
为了与已有研究进行比较,本文采用被广泛应用的T-score[9, 13, 17, 26, 34]来描述错误定位的精度,如公式(11)所示:
(11)
为了验证本文提出的错误定位方法的有效性,本文方法与SBI,SOBER,Tarantula,SF,RankCP方法的实验结果如图 9所示,X轴为找到错误语句需检查语句的百分比,Y轴为成功定位错误版本的比率,记为fault_percent,如公式(12)所示:
(12)
由图 9可以看出,本文方法具有最高的错误定位精度.SBI方法通过谓词覆盖信息计算语句的可疑度,能够隔离程序中的多重错误,但它只记录实体在执行过程中是否被覆盖到,不足以捕获测试用例的行为信息.SOBER改进了SBI,分析了执行过程中谓词为真和假的执行次数.然而,SBI和SOBER方法只能定位与谓词相关的错误,对于与谓词无关的错误,定位效果较差.Tarantula方法利用程序执行时语句的覆盖信息计算所有执行语句的可疑度,进而定位错误语句.虽然Tarantula可以定位所有错误语句,但它只利用了程序运行时各个语句的覆盖信息,并未分析程序执行时的路径信息,也未考虑谓词的具体状态.SF方法在程序具体执行路径的基础上,分析了程序元素间的控制依赖关系以及程序执行时各元素的具体执行状态,其错误定位精度高于SBI,SOBER和Tarantula,但该方法并未分析程序元素间的数据依赖信息.本文方法和RankCP方法不仅分析了程序元素间的控制依赖关系,还分析了程序元素间的数据依赖关系.RankCP将依赖网络与程序分析相结合,提出程序依赖图(PPDG),统计元素间的条件依赖关系.但它假定所有语句被执行的概率都相等,而实际上,程序在执行过程中,每条语句被执行的概率并不相同,对于分支语句和循环语句,每个状态(谓词为真、假)被执行的概率也不同.因为RankCP方法每次只使用一条错误测试用例进行错误定位,因此,该方法统计了最好、最坏以及平均错误定位结果,分别为RankCP-best,RankCP-worst,RankCP-median.本文提出了联合依赖概率模型,该模型不仅能分析每个节点不同状态被执行的概率,而且可以统计节点在不同状态下与其数据依赖父节点间的联合依赖概率,在程序执行路径的基础上充分分析了控制依赖和数据依赖信息,能够更准确地分析程序的错误行为状态,从而能够更有效地定位错误语句.由图 9可以看出,使用未约简的测试用例,本文方法的错误定位效果优于RankCP-best.在检查相同数目的程序语句时,本文方法可以定位更多错误版本.在运行本文方法约简后的测试用例时,检查程序50%的语句,本文方法可以定位所有语句错误.
 | Fig. 9 Comparisons on the effectiveness of each fault localization technique图 9 错误定位效果对比图 |
(13)
|
|
Table 5 Experimental results of fault localization on space program 表 5 space测试集中错误定位实验结果 |
4.2.3 小测试集实验结果分析
在现实情况中,错误测试用例往往很难得到,因此,本文探讨了在错误测试用例数目较少时的错误定位精度.图 10分别为使用1,3,5以及所有的错误测试用例时的错误定位精度.使用的测试用例集为本文方法约简后的测试用例集合.测试对象为Siemens Suite程序集.RankCP方法每次只能使用1条错误测试用例进行错误定位,而本文方法不受错误测试用例个数的限制.图 10表明:同样使用1条错误测试用例,本文方法的错误定位精度高于RankCP-best;随着错误测试用例数目的增多,本文方法具有更高的错误定位精度.
 | Fig. 10 Effect of the number of failed test cases on fault localization图 10 错误测试用例数目对错误定位的影响 |
为了验证本文提出的测试用例约简方法对包含多个错误的程序的有效性,在Siemens Suite测试集上进行了错误注入实验.对于每个程序,只随机选择其中的一个版本进行实验.将相邻的两个错误版本进行错误合并.例如,选择tcas的第8个版本进行实验,错误注入的方式为:将第9个版本的错误注入到第8个版本中.根据多个错误语句,可以计算多个T-score值.选取这些T-score的最大值作为最终的T-score.通过实验发现,面向多个错误的错误定位需求向量包含了较多的语句,约简后的测试用例相对较多.但与未约简的测试用例相比,约简后的测试用例仍然可以提高错误定位的精度.
5 结束语本文将测试用例约简与软件错误定位统一为一个整体,提出了结合测试用例约简与联合依赖概率建模的软件错误自动定位方法.首先,本文充分考虑了错误测试用例对错误定位的重要性,根据软件错误定位的需求,提出面向错误定位需求的测试用例约简方法,充分考虑了程序运行时的路径信息,均衡路径覆盖率,为错误定位提供有效的测试用例,并降低错误定位分析的复杂度;然后,本文定义了一种新的统计分析模型——联合依赖概率模型,并在此基础上提出了基于联合依赖概率模型的错误定位方法,分析了元素间控制依赖、数据依赖以及语句的执行状态.实验结果表明,本文方法能够有效地约简测试用例,并可以有效地定位软件错误.
| [1] | Zhang ZY, Chanb WK, Tsec TH, Yub YT, Hud PF. Non-Parametric statistical fault localization. Journal of Computer and System Sciences, 2011,84:885-905 . |
| [2] | Jobstmann B, Staberb S, Griesmayerc A, Bloem R. Finding and fixing faults. Journal of Computer and System Sciences, 2012,78: 441-460 . |
| [3] | Wong WE, Debroy V, Xu D. Towards better fault localization: A crosstab-based statistical approach. IEEE Trans. on Systems, Man, and Cybernetics, 2012,42(3):378-396 . |
| [4] | Yu K, Lin M, Gao Q, Zhang H, Zhang X. Locating faults using multiple spectra-specific models. In: Proc. of the SAC. 2011 . |
| [5] | Abreu R, Zoeteweij P, van Gemund AJC. On the accuracy of spectrum-based fault localization. In: Proc. of the Testing: Academic and Industrial Conf., Practice and Research Techniques. Windsor, 2007 . |
| [6] | Baudry B, Fleurey F, Traon YL. Improving test suites for efficient fault localization. In: Proc. of the Int’l Conf. on Software Engineering. Shanghai, 2006. 82-91 . |
| [7] | Zhang X, Gu Q, Chen X, Qi J, Chen D. A study of relative redundancy in test-suite reduction while retaining or improving fault- localization effectiveness. In: Proc. of the SAC. 2010. 2229-2236 . |
| [8] | Chen Z, Xu B, Zhang X, Xie C. A novel approach for test suite reduction based on requirement relation contraction. In: Proc. of the SAC. 2008. 390-394 . |
| [9] | Renieris M, Reiss SE. Fault localization with nearest neighbor queries. In: Proc. of the 18th Int’l Conf. on Automated Software Engineering (ASE 2003). Montreal, 2003. 30-39 . |
| [10] | Wang T, Abhik R. Automated path generation for software fault localization. In: Proc. of the 20th IEEE/ACM Int’l Conf. on Automated Software Engineering. New York, 2005. 347-351 . |
| [11] | Hao D, Zhang L, Sun J, Mei H. VIDA: Visual interactive debugging. In: Proc. of the ICSE. 2009. 583-586 . |
| [12] | Hao D, Xie T, Zhang L, Wang X, Sun J, Mei H. Test input reduction for result inspection to facilitate fault localization. Automated Software Engineering, 2010,17:5-31 . |
| [13] | Yu Y, Jones JA, Harrold MJ. An empirical study of the effects of test suite reduction on fault localization. In: Proc. of the ICSE. 2008. 201-210 . |
| [14] | Sterling CD, Olsson RA. Automated bug isolation via program chipping. In: Proc. of the 6th Int’l Symp. on Automated Analysis- Driven Debugging. 2005. 23-32 . |
| [15] | Zhang X, Gupta N. Locating faulty code by multiple points slicing. Software Practice & Experience, 2007,37(9):935-961 . |
| [16] | Wong WE, Qi Y. Effective program debugging based on execution slices and inter-block data dependency. Journal of Systems and Softwar, 2006,79(7):891-903 . |
| [17] | Jones JA, Harrold MJ. Empirical evaluation of the tarantula automatic fault localization technique. In: Proc. of the 20th IEEE/ACM Int’l Conf. on Automated Software Engineering (ASE). 2005. 273-282 . |
| [18] | Renieres M, Reiss SP. Fault localization with nearest neighbor queries. In: Proc. of the 18th ASE. 2003. 30-39 . |
| [19] | Janssen T, Abreu R, van Gemund AJC. Zoltar: A toolset for automatic fault localization. In: Proc. of the 24th ASE. 2009. 662-664 . |
| [20] | Wong WE, Debroy V, Choi B. A family of code coverage-based heuristics for effective fault localization. Journal of Systems and Software, 2010,83(2):188-208 . |
| [21] | Naish L, Lee HJ, Ramamohanarao K. Statements versus predicates in spectral bug localization. In: Proc. of the 17th Asia Pacific Software Engineering Conf. (APSEC). 2010. 375-384 . |
| [22] | Lo LD, Jiang L, Budi A. Comprehensive evaluation of association measures for fault localization. In: Proc. of the 2010 IEEE Int’l Conf. on Software Maintenance (ICSM). 2010. 1-10 . |
| [23] | Masri W. Fault localization based on information flow coverage. Software Testing, Verification and Reliability, 2010,20:121-147 . |
| [24] | Santelices R, Jones JA, Yu Y, Harrold MJ. Lightweight fault-localization using multiple coverage types. In: Proc. of the IEEE 31st Int’l Conf. on Software Engineering (ICSE). 2009. 56-66 . |
| [25] | Jeffrey D, Nagarajan V, Gupta R, Gupta N. Execution supression: An automated iterative technique for locating memory errors. ACM Trans. on Programming Languages and Systems, 2010,32(5):1-36 . |
| [26] | Cleve H, Zeller A. Locating causes of program failures. In: Proc. of the ICSE. 2005. 342-351 . |
| [27] | Gupta N, He H, Zhang X, Gupta R. Locating faulty code using failure-inducing chops. In: Proc. of the ASE. 2005. 263-272 . |
| [28] | Zhang X, Gupta N, Gupta R. Locating faults through automated predicate switching. In: Proc. of the ICSE. 2006. 272-281 . |
| [29] | Dallmeier V, Zeller A, Meyer B. Generating fixes from object behavior anomalies. In: Proc. of the ASE. 2009. 550-554 . |
| [30] | Mariani L, Pezzè M. Dynamic detection of COTS components incompatibility. IEEE Software, 2007,24(5):76-85 . |
| [31] | Leonardo M, Pezze M, Riganelli O, Santoro M. SEIM: Static extraction of interaction models. In: Proc. of the 2nd Int’l Workshop on Principles of Engineering Service Oriented Systems (PESOS) Workshop Colocated with ICSE. 2010. 22-28 . |
| [32] | Liblit B, Naik M, Zheng A, Aiken A, Jordan M. Scalable statistical bug isolation. In: Proc. of the ACM SIGPLAN Conf. on Programming Language Design and Implementation. 2005. 15-26 . |
| [33] | Chilimbi TM, Liblit B, Mehra KK, Nori AV, Vaswani K. Holmes: Effective statistical debugging via efficient path profiling. In: Proc. of the ICSE. 2009. 34-44 . |
| [34] | Liu C, Yan X, Fei L, Han J, Midkiff S. Sober: Statistical model-based bug localization. In: Proc. of the 10th European Software Engineering Conf./13th ACM SIGSOFT Int’l Symp. on Foundations of Software Engineering (ESEC/FSE 2005). 2005. 286-295 . |
| [35] | Wong WE, Wei T, Qi Y, Zhao L. A crosstab-based statistical method for effective fault localization. In: Proc. of the 1st Int’l Conf. on Software Testing, Verification and Validation. 2008. 42-51 . |
| [36] | Feng M, Gupta R. Learning universal probabilistic models for fault localization. In: Proc. of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering. 2010. 81-88 . |
| [37] | Nainar PA, Liblit B. Adaptive bug isolation. In: Proc. of the ICSE. 2010. 255-264 . |
| [38] | Zhang Z, Chan W, Tse T, Jiang B, Wang X. Capturing propagation of infected program states. In: Proc. of the ESEC/FSE. 2009 . |
| [39] | Jiang LX, Su ZD. Context-Aware statistical debugging: From bug predictors to faulty control flow paths. In: Proc. of the ASE. 2007 . |
| [40] | Baah GK, Podgurski A, Harrold MJ. The probabilistic program dependence graph and its application to fault diagnosis. IEEE Trans. on Software Engineering, 2008,87:189-200 . |
| [41] | Hutchins M, Foster H, Goradia T, Ostrand T. Experiments on the effectiveness of dataflow and controlflow-based test adequacy criteria. In: Proc. of the Int’l Conf. on Software Engineering. 1994. 191-200 . |
| [42] | Vokolos F, Frankl P. Empirical evaluation of the textual differencing regression testing techniques. In: Proc. of the Int’l Conf. on Software Maintenance. 1998 . |
| [43] | Aristotle Research Group. Aristotle analysis system. 2007. http://www.cc.gatech.edu/aristotle/ |