基于组合故障频繁树的最小失效诱因模式定位方法

王　勇　 黄志球　 韦良芬　 李　勇

(1南京航空航天大学计算机科学技术学院, 南京 210016)(2安徽工程大学计算机与信息学院, 芜湖 241000)(3安徽三联学院计算机工程系, 合肥 230601)

组合测试对软件的输入参数组合空间进行抽样,用以触发参数组合所导致的软件失效[1-2]．其中的关键问题是构造符合某种组合测试覆盖准则的最小测试用例集．组合测试研究大多集中于构造有效的测试用例生成算法并评估其有效性．近年来,如何利用组合测试的结果集合来诊断软件失效原因备受关注．Ghandehari等[3]提出了最小失效诱因模式(MFS),定位MFS有助于软件调试过程中的程序故障代码定位与理解．一个软件包含n个输入参数,每个参数包含m个参数值,其参数组合为mn．如何在巨大的输入参数值组合空间中定位MFS是实施组合故障定位的关键．

为了定位MFS,文献[4]提出了逐个替换法,采用启发式方法将触发软件失效的值模式逐个替换,以减小MFS的可能搜索范围．文献[5]提出故障交互特性(FIC)定位方法,将失败测试用例作为种子生成附加测试用例集,通过自适应修改该附加测试用例集,对被测软件进行增强测试,反复迭代直至找到MFS．文献[6]构建了一种特定元组关系树(TRT)来描述所有特定值组合模式的关系,利用TRT可以有效减少生成附加测试用例的数目,并提供MFS的精确定位．然而,这些方法都存在潜在的假设,即运行包含MFS的测试用例一定会触发软件失效．Dumlu等[7]指出在现实系统中,屏蔽效应会导致运行部分中包含MFS的测试用例未必一定触发软件失效．因此,在现实系统中,即使覆盖MFS,软件失效也呈间歇性．上述精确定位方法在不满足潜在假设的情况下很难取得满意的定位效果．研究者们提出的解决方法是计算各个组合的可疑度排名,并将可疑排名列表提交给程序员进行进一步诊断．Yilmaz等[8-9]使用故障分类树分析给定的组合测试集,用以探测软件复杂配置空间中的潜在故障组合模式．Shakya等[10]采用每次一个因子(OPOT)准则生成尽可能多的失败测试用例,以降低故障分类树不平衡所带来的结果偏置．然而,故障分类树所构建的可疑MFS强依赖于根节点的选择．

由软件故障/失效模型[11]可知,无论系统中是否存在屏蔽效应,MFS一定存在于失败测试用例集中,即MFS频繁出现在失败测试集合中．基于文献[12]中的频繁项挖掘算法,本文提出了一种基于组合故障频繁树(CFF-tree)的MFS定位方法．该方法采用了迭代式的定位框架．如果从已有测试用例集中未能得到满意的定位结果,则可以增加附加失败用例,重新定位,直到定位结果满意为止．

1　组合故障定位基础模型

将待测软件(SUT)输入参数集合定义为v={v1,v2,…,vi,…,vn},其中,vi取值来自于离散集合Vi．SUT在运行过程中可能由多个参数值相互作用而导致软件失效．假设一个待测软件的配置参数如表1所示．

表1　待测系统的配置表实例

定义1(测试用例集)组合测试用例集可表示为集合T={(v1,v2,…,vn)|v1∈V1,v2∈V2,…,vn∈Vn}．

定义2(k值模式)对于某个组合测试用例集,n元组中的[-,…,vl1,-,…,vlk,…]被称作k值模式(n≥k>0)．在该元组中,vli取Vi中的某一个固定值,“-”表示对应参数可以取任何值．当k=n时,这个k值模式即为一个测试用例．例如,[-,WinXP,-,NewUser]即为一个2值模式．

定义3(k值失效诱因模式)k值失效诱因模式是指包含此k值失效诱因模式的测试用例将引发软件失效．与此相反,在包含某个k值模式的测试用例集合中,若存在至少一个测试用例被成功执行,则称该k值模式为k值正确模式．一个可疑的k值失效诱因模式是指该k值模式与k值失效诱因模式高度相关．

定义4(子模式)假设m1和m2为待测系统SUT的2个值模式．如果m1中取定的参数值为m2中取定参数值的子集,则称m1为m2的子模式,m2为m1`的父模式．

定义5(k值MFS)如果k值失效诱因模式为k值MFS,则其所有的子模式均为正确模式．最小k值MFS为软件失效的根源．

定义6(屏蔽效应)屏蔽效应是指受运行环境影响,包含某个k值MFS的运行偶然成功执行．Dumlu等[7]指出产生屏蔽效应的原因可能是,受其他值模式的影响,软件在运行过程中提前返回或突发异常而导致程序运行未执行MFS．

由于存在屏蔽效应,运行包含MFS的测试用例不一定触发软件失效．假设[-,WinXP,-,NewUser]为2值MFS,则包含该模式的所有测试用例有可能触发软件失效,也有可能偶然成功执行．组合测试的目标是构建最小测试用例集,以触发潜在的软件组合故障．组合测试的测试用例生成算法集通常是构建混合取值覆盖表．

定义8(基本选择覆盖测试准则)在系统中,为每一个参数选择一个固定值,该固定值定义为基本选择参数值,而该参数的其他可能取值为非基本选择参数值．由所有参数的基本选择参数值构成的测试用例被称为基本测试用例．依据基本选择测试覆盖测试准则,新的测试用例生成方法为,每次将基本选择中的某一个参数选择为非基本选择的参数值,其他基本选择参数值保持不变．

基本选择测试用例通常可看作是一个重要的测试用例．在定位MFS中需要增加失败测试用例的个数,因此,可将每一个失败测试用例作为一个基本选择测试用例．在这个基本选择测试用例的基础上以基本选择覆盖准则生成新的测试用例．每次生成的测试用例中只会有一个参数值与失败测试用例不同,故而生成的新测试更可能触发软件失效．

2　实例分析

假设待测软件SUT包含4个配置参数a,b,c,d．等价划分后a∈{1,2},b∈{1,2,3},c∈{1,2},d∈{1,2,3}．采用2路组合测试,生成9个测试用例．假设故障组合为{b=2,c=2},其组合测试结果见表2中测试用例1～测试用例9,其中测试用例4和测试用例6触发软件失败．

为了增加失败测试用例的数目,对失败测试用例4和测试用例6采用基本选择覆盖测试准则进行附加测试．需生成8个附加测试用例,其中1个测试用例和前面重复,因此,总共新生成7个附加测试用例．测试用例集和测试结果见表2中测试用侧10～测试用例16．假设受屏蔽效应影响,测试用例13本应产生软件失效却成功执行．在精确的组合故障定位中,考虑到成功测试用例14包含了配置组合{b=2,c=2},则可排除{b=2,c=2}为MFS．因此,在具有屏蔽效应影响的情况下,很难利用精确定位方法进行组合故障定位．

表2　组合测试用例集及测试结果

MFS一定存在于失败测试用例中,且在失败测试用例集中出现频繁．因此,定位失败测试用例集中的频繁项集合,最频繁的项集则最可能为MFS．

为了降低MFS定位代价,采用迭代的组合故障定位框架．基于基本测试用例集和测试结果,运行基于组合故障频繁树的挖掘方法,得到4个支持度为1的可疑MFS．为了对其进行进一步排查,随机选择附加测试集合中的一个测试用例．假设测试用例为[1,2,2,2],虽然包含了MFS,但受屏蔽效应影响,仍能成功运行．该方法将过滤掉该测试用例,继续随机选择未执行的测试用例．假设选择了测试用例[2,2,2,2],运行结果为软件失效,将失败测试用例加入到失败测试集中,重新运行故障定位方法．最终,该方法输出最大频繁项{b=2,c=2},该最大频繁项即为MFS．由此可见,该方法仅附加了2个测试用例便能定位出真实的MFS．

3　组合故障定位

3.1　迭代故障定位框架

MFS定位问题的本质是利用较少的附加测试,以减少待检查可疑组合的数目．失败测试中一定包含MFS,因此,失败测试用例集中最频繁的项集最可能为MFS．本文方法需要构造一个组合故障频繁树来存储失败测试用例集中频繁参数值组合之间的关系,然后基于组合故障频繁树给出频繁度top-k的可疑MFS,提交给程序员进一步检查．

考虑附加测试的代价,该故障定位方法可以是迭代的,主要步骤如下:

① 收集基本测试用例集和测试结果．

② 运行MFS定位算法,进行故障定位．

③ 如果MFS位于可疑MFS列表的前J位(仿真实验中设置为1),则该故障定位框架停止;否则,转步骤④．

④ 基于基本选择覆盖测试准则,生成附加测试集合,随机选择一个未测试的测试用例进行测试．如果该测试用例为成功测试用例,则重新执行步骤④;否则,将失败测试用例加入基本测试用例集,转步骤②．

3.2　组合故障频繁树

实际中,希望以一种紧凑的树结构存储失败测试参数值之间的组合关系,以减少待检查组合参数值的数目．如果参数值组合在失败测试用例出现得不频繁,则可以对这些参数值及其组合进行约简．

定义8(支持度)规则x→y的支持度表示为x和y在事务集中同时出现的概率,记为support(x→y),即

support(x→y)=p(x∪y)

(1)

在MFS定位的上下文中,对失败测试用例的参数值组合进行频繁项集挖掘,支持度表示为参数值组合在失败测试中的频繁度．假设系统中只存在一个MFS,则该MFS的频繁度为1. 考虑到可能存在多个组合故障模式,故可根据特定情况对频繁度进行设置．假设support(x→failed)=0.5．支持度高于0.5的项集被认为是频繁项集．如第2节实例所示,support({b=2,c=2}→failed)=3/3=1．由于对每一个频繁项集而言,失败测试用例集的总数目固定．因此,可以用频繁项出现的次数表示支持度．

如第2节实例所示,失败测试用例集Tf={T4,T6,T10,T14},在频繁项集合中需要对每一个参数的参数值进行区别,将参数名作为字符串前缀加在其参数值前面．例如,{a=1}标识为“a1”．依据每一个参数值在失败测试用例集中出现次数进行排序可得“b2”:4, “c2”:4,“a1”:2, “a2”:2, “d3”:2, “d1”:1, “d2”:1．依据支持度0.5的阈值,过滤掉小于支持度的项“d1”和“d2”．按支持度降序对各参数值进行重排,并将每一个测试用例集重排的结果称为一个事务．失败测试用例集和事务见表3．

表3　失败测试用例集和频繁项集

定义9(组合故障频繁树)一棵组合故障频繁树可以表示成一个三元组T={root,ips, fht}．其中,root为根节点,通常标识为Null;ips为项前缀子树,是root的孩子节点集合;fht为频繁项的头指针表．

定义10(项前缀子树)该子树的每一个树节点包括3个域:item-name,count和node link.其中,item-name为项的标识;count为到达该节点的子路径个数;node-link为指向具有相同项标识的下一个节点的链接,若不存在相同项标识的下一个节点,则表示为Null．

定义11(频繁项头表)频繁项头表包括item-name和head-of-node-link两个域．其中,item-name为项名;head-of-node-link为指向CFF-tree中第1个item-name的节点．

基于CFF-tree的定义,构建CFF-tree．具体算法见算法1.

算法1CFF-tree的构建

输入:失败测试用例集Γf．

输出: 组合故障频繁树T．

1扫描Γf,收集参数值的频繁项集F及其频繁度计数．将F按频繁度计数降序重排为L,L即为参数值频繁项集的集合．

2生成组合故障频繁树T的根节点root,并将其标记为Null．

3对L中的每一个有序的频繁项集执行:将频繁项集的第1个项赋给q,剩余的其他项作为整体赋给Q,然后调用函数insert-tree([q|Q],T)．

4返回T

在算法1中,insert-tree([q|Q],T)执行如下:如果T存在一个孩子节点N,使得N.item-name=q.item-name, 则N.count++．否则,生成一个新节点N,令N.count=1,并将其父节点指针指向T,node link指针指向具有相同item-name的节点;如果P为非空集,则递归调用insert-tree(Q,N)．

给定表3的失败测试用例集,利用算法1构建的CFF-tree如图1所示．

图1　基于算法1构建的CFF-tree

3.3　最小失效诱因模式挖掘

定义12(条件模式基)一个参数值的条件模式基是以该参数值为结尾的路径集合．

给定一棵CFF-tree和频繁度阈值,对每一个频繁参数值,抽取其频繁项集,具体步骤如下:

① 从CFF-tree中获得该频繁参数值的条件模式基;

② 利用条件模式基,构建一个条件CFF-tree;

③ 重复步骤①和步骤②,直到CFF-tree包含单个路径为至．

如图1中,参数值“d3”的条件基为{〈“b2”,“c2”,“a1”,“d3”〉:1, 〈“b2”,“c2”,“a2”,“d3”〉: 1}, 参数值“a1”的条件模式基为{〈“b2”,“c2”,“a2”〉:2}．如果参数值“a1”为频繁项,则以参数值“a1”为后缀的频繁项集可求解其条件模式基．如果条件模式基为单个路径,则频繁项集为路径中所有参数值与该参数值的组合．例如,以“a1”为后缀的频繁项集为{“b2”,“c2”}与“a1”的组合,其结果为{{“b2”,“a1”},{“c2”,“a1”},{“b2”,“c2”,“a1”}}．如果条件模式基为多条路径,则递归求解,并对每一个结果进行组合．例如,参数值“d3”的条件模式基为多条路径{〈“b2”,“c2”,“a1”,“d3”〉:1, 〈“b2”,“c2”,“a2”,“d3”〉:1},假设最小支持度为2,“a1”和“a2”虽然是满足最小支持度为2的频繁项,但{“a1”,“d3”},{“a2”,“d3”}不满足最小支持度,在由“d3”构建的条件CFF-tree中应该过滤掉“a1”,“a3”．利用这2条路径构建的条件CFF-tree可合并为一条路径,其频繁项集可以利用单路径处理方法进行求解．由此可知,由“d3”结尾、最小支持度为2的频繁项为{〈“d3”〉, 〈“b2”,“d3”〉,〈“c2”,“d3”〉,〈“b2”,“c2”,“d3”〉}．

由此得到的频繁项集合中元素数目可能依然很庞大,需要对频繁项集进行进一步约简处理．假设存在频繁项集〈“d3”:2〉和〈“a2”,“d3”〉:2．后者包含前者且其频繁度相同,故可将其归并为〈“a2”,“d3”〉:2．

最后,给出列表中的前J个(J可由程序调试人员自己设置)的频繁项作为可疑最小失效诱因模式,提交给程序调试人员进行人工判定．

3.4　算法复杂度分析

MFS定位的算法复杂度主要体现在构建CFF-tree和基于CFF-tree的组合故障频繁项定位上．令n表示失败测试用例的数目,m表示每个测试用例包含参数值的平均数．主要步骤的时间复杂度分别为:① 获得每个参数值频繁度的时间复杂度O(n);② 根据表头项fht对失败测试用例集中每个参数值进行排序的时间复杂度O(nmlogm);③ 构建组合故障频繁树的算法时间复杂度O(nm2);④ 故障模式定位的时间复杂度O(nm2)．

由此可知,组合故障模式定位算法的时间复杂度为O(nm2)．该算法所需要的存储空间主要用于存储CFF-tree．在最坏的情况下,每一个失败测试用例的参数值不存在重叠． 假设一棵组合故障频繁树的最大深度为e,最大宽度为f,则构建组合故障频繁树的空间复杂度为O(ef)．组合测试的测试用例数目较少,而失败测试用例数目更少,因此,该算法的时间复杂度和空间复杂度均较小．

4　仿真实验

4.1　传统组合故障定位

假设待测系统个数u分别包含8,10,12个参数,每个参数存在3个参数值．利用组合测试工具ACTS[13]推荐的IPOG算法生成覆盖表．例如,对于包含8个参数的待测系统,生成的二维覆盖表包含15个测试用例,三维覆盖表包含60个测试用例,四维覆盖表包含191个测试用例．

为了评估不存在屏蔽效应影响下所提方法的有效性,将文献[6]提出的元组关系树模型TRT作为基准方法进行实验．文献[7]提出了一种用于组合测试故障定位的关系树模型,即构造一个关系树来记录所有待测元组及其之间的关系,并基于元组关系树进行故障定位．元组关系树模型TRT给出4种测试用例挑选策略,选用其最优的测试用例挑选策(略路径法)作为比较标准．与所提方法不同,TRT方法使用精确定位方法．根据MFS定义,需要检验MFS中所有子元组是否都为正确元组．然而,存在屏蔽效应影响的情况下,该方法显然是不适用的．对测试用例集注入MFS,将包含MFS的测试用例设置为失败的测试用例．

模拟不存在屏蔽效应影响情况下,注入包含单个t维覆盖表的MFS,将包含MFS的测试用例设置为失败测试用例．将测试用例集合划分为成功测试用例集和失败测试用例集．利用所提方法的迭代定位框架,得到每一次附加测试用例数．对于3组不同参数的待测系统,选用不同的MFS重复进行100次实验,并记录每次附加测试用例数目,结果见图2．由图可知,所提方法优于TRT方法．值得注意的是,TRT方法使用精确定位,需要检查MFS中所有子元组是否都为正确元组,这一过程将增加附加测试用例数;理论上,该方法是有效的,但如果存在屏蔽效应影响,则很难得到理想的定位结果．与TRT方法不同,所提方法直接给出最可疑MFS,提交程序员进一步检查．假设真实的MFS在可疑列表中排名第1,即可认为定位出正确结果．实验中, CFF-tree的定位结果与参与定位的失败测试用例数目高度相关．例如,对于一个二维MFS,只需要2～3个失败测试用例即可得到较为满意的定位效果．

(a) 8个参数二维比较

(b) 8个参数三维比较

(c) 8个参数四维比较

(d) 10个参数二维比较

(e) 10个参数三维比较

(f) 10个参数四维比较

(g) 12个参数二维比较

(h) 12个参数三维比较

(i) 12个参数四维比较

图2不同环境下所提方法和TRT方法结果比较

4.2　屏蔽效应下的组合故障定位

假定待测软件包含10个参数,在存在屏蔽效应影响的情况下,包含MFS的测试用例以10%和30%的概率偶然成功执行．通过ACTS工具生成二维、三维、四维覆盖矩阵．在测试用例集中注入单个MFS, 使得运行包含MFS的测试用例以一定的概率成功执行．例如,当屏蔽效应的概率为30%时,对每一个包含MFS的测试用例调用一个随机函数,该随机函数以30%概率设置该测试用例为成功测试用例,以70%的概率设置该测试用例为失败测试用例．

同样地,利用所提方法的迭代定位框架,得到每一次附加测试用例数．在2种不同屏蔽效应影响情况下,分别注入二维、三维、四维MFS．在实验过程中,选用不同参数值组合的MFS,重复进行100次故障定位,并记录每次附加测试数目,结果见图3．图中, ME和NME分别表示存在和不存在屏蔽效应2种情况．由图可知,随着屏蔽概率的增加,所使用的附加测试数目明显增大．与不存在屏蔽效应影响情况类似,MFS定位结果高度依赖于失败测试用例数目．因此,CFF-tree方法能在一定数目的失败测试用例集中有效定位MFS．

5　结论

1) 提出了一种基于组合故障频繁树的最小失效诱因模式定位方法．基于测试用例集及测试结果,利用失败测试用例集构建组合故障频繁树CFF-tree,进而生成可疑最小失效诱因模式列表．

2) 使用附加测试技术,给出了一种最小失效诱因模式迭代定位框架．利用该迭代定位框架进行多次迭代,可以有效缩减MFS的搜索范围,直到满足某一停止准则．

3) 分别针对存在和不存在屏蔽效应影响2种情况下设计仿真实验．结果表明,所提方法在定位最小失效诱因模式的基础上,可以有效减少附加测试的数目．

(a) 10%屏蔽概率下二维比较

(b) 10%屏蔽概率下三维比较

(c) 10%屏蔽概率下四维比较

(d) 30%屏蔽概率下二维比较

(e) 30%屏蔽概率下三维比较

(f) 30%屏蔽概率下四维比较

图3不同屏蔽概率下所提方法的结果比较

参考文献(References)

[1] Nie C, Leung H. A survey of combinatorial testing[J].ACMComputingSurveys, 2011,43(2): 1-29. DOI:10.1145/1883612.1883618.

[2] 严俊, 张健. 组合测试:原理与方法[J]. 软件学报, 2009, 20(6): 1393-1405. DOI:10.3724/SP.J.1001.2009.03497.

Yan Jun, Zhang Jian. Combinatorial testing: Principles and methods[J].JournalofSoftware, 2009,20(6): 1393-1405. DOI:10.3724/SP.J.1001.2009.03497. (in Chinese)

[3] Ghandehari L S G, Lei Y, Xie T, et al. Identifying failure-inducing combinations in a combinatorial test set[C]//2012IEEEFifthInternationalConferenceonSoftwareTesting,VerificationandValidation. Montreal, Canada, 2012: 370-379. DOI:10.1109/icst.2012.117.

[4] Nie C, Leung H. The minimal failure-causing schema of combinatorial testing[J].ACMTransactionsonSoftwareEngineeringandMethodology, 2011,20(4): 1-38. DOI:10.1145/2000799.2000801.

[5] Zhang Z, Zhang J. Characterizing failure-causing parameter interactions by adaptive testing[C]//Proceedingsofthe2011InternationalSymposiumonSoftwareTestingandAnalysis. Toronto, Canada, 2011: 331-341. DOI:10.1145/2001420.2001460.

[6] Niu X, Nie C, Lei Y, et al. Identifying failure-inducing combinations using tuple relationship[C]//2013IEEESixthInternationalConferenceonSoftwareTesting,VerificationandValidationWorkshops. Luxembourg, Luxembourg, 2013: 271-280. DOI:10.1109/icstw.2013.38.

[7] Dumlu E, Yilmaz C, Cohen M B, et al. Feedback driven adaptive combinatorial testing[C]//Proceedingsofthe2011InternationalSymposiumonSoftwareTestingandAnalysis. Toronto, Canada, 2011: 243-253. DOI:10.1145/2001420.2001450.

[8] Yilmaz C, Fouche S, Cohen M B, et al. Moving forward with combinatorial interaction testing[J].Computer, 2014,47(2): 37-45. 37-45. DOI:10.1109/mc.2013.408.

[9] Yilmaz C, Cohen M B, Porter A A. Covering arrays for efficient fault characterization in complex configuration spaces[J].IEEETransactionsonSoftwareEngineering, 2006,32(1): 20-34. DOI:10.1109/tse.2006.8.

[10] Shakya K, Xie T, Li N, et al. Isolating failure-inducing combinations in combinatorial testing using test augmentation and classification[C]// 2012IEEEFifthInternationalConferenceonSoftwareTesting,VerificationandValidation. Montreal, Canada, 2012: 620-623.DOI:10.1109/icst.2012.149.

[11] Ammann P, Offutt J.Introductiontosoftwaretesting[M]. Cambridge,UK: Cambridge University Press, 2016:31-32.

[12] Han J, Pei J, Kamber M.Datamining:Conceptsandtechniques[M]. Amsterdam, the Netherlands: Elsevier, 2011:246-253.

[13] Ghandehari L S, Chandrasekaran J, Lei Y,et al. BEN: A combinatorial testing-based fault localization tool[C]//IEEEEighthInternationalConferenceonSoftwareTestingVerificationandValidationWorkshops. Graz, Australia, 2015:1-4.