基于組合故障頻繁樹的最小失效誘因模式定位方法

王　勇　 黃志球　 韋良芬　 李　勇

(1南京航空航天大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 南京 210016)(2安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院, 蕪湖 241000)(3安徽三聯(lián)學(xué)院計(jì)算機(jī)工程系, 合肥 230601)

組合測(cè)試對(duì)軟件的輸入?yún)?shù)組合空間進(jìn)行抽樣,用以觸發(fā)參數(shù)組合所導(dǎo)致的軟件失效[1-2]．其中的關(guān)鍵問題是構(gòu)造符合某種組合測(cè)試覆蓋準(zhǔn)則的最小測(cè)試用例集．組合測(cè)試研究大多集中于構(gòu)造有效的測(cè)試用例生成算法并評(píng)估其有效性．近年來(lái),如何利用組合測(cè)試的結(jié)果集合來(lái)診斷軟件失效原因備受關(guān)注．Ghandehari等[3]提出了最小失效誘因模式(MFS),定位MFS有助于軟件調(diào)試過程中的程序故障代碼定位與理解．一個(gè)軟件包含n個(gè)輸入?yún)?shù),每個(gè)參數(shù)包含m個(gè)參數(shù)值,其參數(shù)組合為mn．如何在巨大的輸入?yún)?shù)值組合空間中定位MFS是實(shí)施組合故障定位的關(guān)鍵．

為了定位MFS,文獻(xiàn)[4]提出了逐個(gè)替換法,采用啟發(fā)式方法將觸發(fā)軟件失效的值模式逐個(gè)替換,以減小MFS的可能搜索范圍．文獻(xiàn)[5]提出故障交互特性(FIC)定位方法,將失敗測(cè)試用例作為種子生成附加測(cè)試用例集,通過自適應(yīng)修改該附加測(cè)試用例集,對(duì)被測(cè)軟件進(jìn)行增強(qiáng)測(cè)試,反復(fù)迭代直至找到MFS．文獻(xiàn)[6]構(gòu)建了一種特定元組關(guān)系樹(TRT)來(lái)描述所有特定值組合模式的關(guān)系,利用TRT可以有效減少生成附加測(cè)試用例的數(shù)目,并提供MFS的精確定位．然而,這些方法都存在潛在的假設(shè),即運(yùn)行包含MFS的測(cè)試用例一定會(huì)觸發(fā)軟件失效．Dumlu等[7]指出在現(xiàn)實(shí)系統(tǒng)中,屏蔽效應(yīng)會(huì)導(dǎo)致運(yùn)行部分中包含MFS的測(cè)試用例未必一定觸發(fā)軟件失效．因此,在現(xiàn)實(shí)系統(tǒng)中,即使覆蓋MFS,軟件失效也呈間歇性．上述精確定位方法在不滿足潛在假設(shè)的情況下很難取得滿意的定位效果．研究者們提出的解決方法是計(jì)算各個(gè)組合的可疑度排名,并將可疑排名列表提交給程序員進(jìn)行進(jìn)一步診斷．Yilmaz等[8-9]使用故障分類樹分析給定的組合測(cè)試集,用以探測(cè)軟件復(fù)雜配置空間中的潛在故障組合模式．Shakya等[10]采用每次一個(gè)因子(OPOT)準(zhǔn)則生成盡可能多的失敗測(cè)試用例,以降低故障分類樹不平衡所帶來(lái)的結(jié)果偏置．然而,故障分類樹所構(gòu)建的可疑MFS強(qiáng)依賴于根節(jié)點(diǎn)的選擇．

由軟件故障/失效模型[11]可知,無(wú)論系統(tǒng)中是否存在屏蔽效應(yīng),MFS一定存在于失敗測(cè)試用例集中,即MFS頻繁出現(xiàn)在失敗測(cè)試集合中．基于文獻(xiàn)[12]中的頻繁項(xiàng)挖掘算法,本文提出了一種基于組合故障頻繁樹(CFF-tree)的MFS定位方法．該方法采用了迭代式的定位框架．如果從已有測(cè)試用例集中未能得到滿意的定位結(jié)果,則可以增加附加失敗用例,重新定位,直到定位結(jié)果滿意為止．

1　組合故障定位基礎(chǔ)模型

將待測(cè)軟件(SUT)輸入?yún)?shù)集合定義為v={v1,v2,…,vi,…,vn},其中,vi取值來(lái)自于離散集合Vi．SUT在運(yùn)行過程中可能由多個(gè)參數(shù)值相互作用而導(dǎo)致軟件失效．假設(shè)一個(gè)待測(cè)軟件的配置參數(shù)如表1所示．

表1　待測(cè)系統(tǒng)的配置表實(shí)例

定義1(測(cè)試用例集)組合測(cè)試用例集可表示為集合T={(v1,v2,…,vn)|v1∈V1,v2∈V2,…,vn∈Vn}．

定義2(k值模式)對(duì)于某個(gè)組合測(cè)試用例集,n元組中的[-,…,vl1,-,…,vlk,…]被稱作k值模式(n≥k>0)．在該元組中,vli取Vi中的某一個(gè)固定值,“-”表示對(duì)應(yīng)參數(shù)可以取任何值．當(dāng)k=n時(shí),這個(gè)k值模式即為一個(gè)測(cè)試用例．例如,[-,WinXP,-,NewUser]即為一個(gè)2值模式．

定義3(k值失效誘因模式)k值失效誘因模式是指包含此k值失效誘因模式的測(cè)試用例將引發(fā)軟件失效．與此相反,在包含某個(gè)k值模式的測(cè)試用例集合中,若存在至少一個(gè)測(cè)試用例被成功執(zhí)行,則稱該k值模式為k值正確模式．一個(gè)可疑的k值失效誘因模式是指該k值模式與k值失效誘因模式高度相關(guān)．

定義4(子模式)假設(shè)m1和m2為待測(cè)系統(tǒng)SUT的2個(gè)值模式．如果m1中取定的參數(shù)值為m2中取定參數(shù)值的子集,則稱m1為m2的子模式,m2為m1`的父模式．

定義5(k值MFS)如果k值失效誘因模式為k值MFS,則其所有的子模式均為正確模式．最小k值MFS為軟件失效的根源．

定義6(屏蔽效應(yīng))屏蔽效應(yīng)是指受運(yùn)行環(huán)境影響,包含某個(gè)k值MFS的運(yùn)行偶然成功執(zhí)行．Dumlu等[7]指出產(chǎn)生屏蔽效應(yīng)的原因可能是,受其他值模式的影響,軟件在運(yùn)行過程中提前返回或突發(fā)異常而導(dǎo)致程序運(yùn)行未執(zhí)行MFS．

由于存在屏蔽效應(yīng),運(yùn)行包含MFS的測(cè)試用例不一定觸發(fā)軟件失效．假設(shè)[-,WinXP,-,NewUser]為2值MFS,則包含該模式的所有測(cè)試用例有可能觸發(fā)軟件失效,也有可能偶然成功執(zhí)行．組合測(cè)試的目標(biāo)是構(gòu)建最小測(cè)試用例集,以觸發(fā)潛在的軟件組合故障．組合測(cè)試的測(cè)試用例生成算法集通常是構(gòu)建混合取值覆蓋表．

定義8(基本選擇覆蓋測(cè)試準(zhǔn)則)在系統(tǒng)中,為每一個(gè)參數(shù)選擇一個(gè)固定值,該固定值定義為基本選擇參數(shù)值,而該參數(shù)的其他可能取值為非基本選擇參數(shù)值．由所有參數(shù)的基本選擇參數(shù)值構(gòu)成的測(cè)試用例被稱為基本測(cè)試用例．依據(jù)基本選擇測(cè)試覆蓋測(cè)試準(zhǔn)則,新的測(cè)試用例生成方法為,每次將基本選擇中的某一個(gè)參數(shù)選擇為非基本選擇的參數(shù)值,其他基本選擇參數(shù)值保持不變．

基本選擇測(cè)試用例通?？煽醋魇且粋€(gè)重要的測(cè)試用例．在定位MFS中需要增加失敗測(cè)試用例的個(gè)數(shù),因此,可將每一個(gè)失敗測(cè)試用例作為一個(gè)基本選擇測(cè)試用例．在這個(gè)基本選擇測(cè)試用例的基礎(chǔ)上以基本選擇覆蓋準(zhǔn)則生成新的測(cè)試用例．每次生成的測(cè)試用例中只會(huì)有一個(gè)參數(shù)值與失敗測(cè)試用例不同,故而生成的新測(cè)試更可能觸發(fā)軟件失效．

2　實(shí)例分析

假設(shè)待測(cè)軟件SUT包含4個(gè)配置參數(shù)a,b,c,d．等價(jià)劃分后a∈{1,2},b∈{1,2,3},c∈{1,2},d∈{1,2,3}．采用2路組合測(cè)試,生成9個(gè)測(cè)試用例．假設(shè)故障組合為{b=2,c=2},其組合測(cè)試結(jié)果見表2中測(cè)試用例1～測(cè)試用例9,其中測(cè)試用例4和測(cè)試用例6觸發(fā)軟件失敗．

為了增加失敗測(cè)試用例的數(shù)目,對(duì)失敗測(cè)試用例4和測(cè)試用例6采用基本選擇覆蓋測(cè)試準(zhǔn)則進(jìn)行附加測(cè)試．需生成8個(gè)附加測(cè)試用例,其中1個(gè)測(cè)試用例和前面重復(fù),因此,總共新生成7個(gè)附加測(cè)試用例．測(cè)試用例集和測(cè)試結(jié)果見表2中測(cè)試用側(cè)10～測(cè)試用例16．假設(shè)受屏蔽效應(yīng)影響,測(cè)試用例13本應(yīng)產(chǎn)生軟件失效卻成功執(zhí)行．在精確的組合故障定位中,考慮到成功測(cè)試用例14包含了配置組合{b=2,c=2},則可排除{b=2,c=2}為MFS．因此,在具有屏蔽效應(yīng)影響的情況下,很難利用精確定位方法進(jìn)行組合故障定位．

表2　組合測(cè)試用例集及測(cè)試結(jié)果

MFS一定存在于失敗測(cè)試用例中,且在失敗測(cè)試用例集中出現(xiàn)頻繁．因此,定位失敗測(cè)試用例集中的頻繁項(xiàng)集合,最頻繁的項(xiàng)集則最可能為MFS．

為了降低MFS定位代價(jià),采用迭代的組合故障定位框架．基于基本測(cè)試用例集和測(cè)試結(jié)果,運(yùn)行基于組合故障頻繁樹的挖掘方法,得到4個(gè)支持度為1的可疑MFS．為了對(duì)其進(jìn)行進(jìn)一步排查,隨機(jī)選擇附加測(cè)試集合中的一個(gè)測(cè)試用例．假設(shè)測(cè)試用例為[1,2,2,2],雖然包含了MFS,但受屏蔽效應(yīng)影響,仍能成功運(yùn)行．該方法將過濾掉該測(cè)試用例,繼續(xù)隨機(jī)選擇未執(zhí)行的測(cè)試用例．假設(shè)選擇了測(cè)試用例[2,2,2,2],運(yùn)行結(jié)果為軟件失效,將失敗測(cè)試用例加入到失敗測(cè)試集中,重新運(yùn)行故障定位方法．最終,該方法輸出最大頻繁項(xiàng){b=2,c=2},該最大頻繁項(xiàng)即為MFS．由此可見,該方法僅附加了2個(gè)測(cè)試用例便能定位出真實(shí)的MFS．

3　組合故障定位

3.1　迭代故障定位框架

MFS定位問題的本質(zhì)是利用較少的附加測(cè)試,以減少待檢查可疑組合的數(shù)目．失敗測(cè)試中一定包含MFS,因此,失敗測(cè)試用例集中最頻繁的項(xiàng)集最可能為MFS．本文方法需要構(gòu)造一個(gè)組合故障頻繁樹來(lái)存儲(chǔ)失敗測(cè)試用例集中頻繁參數(shù)值組合之間的關(guān)系,然后基于組合故障頻繁樹給出頻繁度top-k的可疑MFS,提交給程序員進(jìn)一步檢查．

考慮附加測(cè)試的代價(jià),該故障定位方法可以是迭代的,主要步驟如下:

① 收集基本測(cè)試用例集和測(cè)試結(jié)果．

② 運(yùn)行MFS定位算法,進(jìn)行故障定位．

③ 如果MFS位于可疑MFS列表的前J位(仿真實(shí)驗(yàn)中設(shè)置為1),則該故障定位框架停止;否則,轉(zhuǎn)步驟④．

④ 基于基本選擇覆蓋測(cè)試準(zhǔn)則,生成附加測(cè)試集合,隨機(jī)選擇一個(gè)未測(cè)試的測(cè)試用例進(jìn)行測(cè)試．如果該測(cè)試用例為成功測(cè)試用例,則重新執(zhí)行步驟④;否則,將失敗測(cè)試用例加入基本測(cè)試用例集,轉(zhuǎn)步驟②．

3.2　組合故障頻繁樹

實(shí)際中,希望以一種緊湊的樹結(jié)構(gòu)存儲(chǔ)失敗測(cè)試參數(shù)值之間的組合關(guān)系,以減少待檢查組合參數(shù)值的數(shù)目．如果參數(shù)值組合在失敗測(cè)試用例出現(xiàn)得不頻繁,則可以對(duì)這些參數(shù)值及其組合進(jìn)行約簡(jiǎn)．

定義8(支持度)規(guī)則x→y的支持度表示為x和y在事務(wù)集中同時(shí)出現(xiàn)的概率,記為support(x→y),即

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

(1)

在MFS定位的上下文中,對(duì)失敗測(cè)試用例的參數(shù)值組合進(jìn)行頻繁項(xiàng)集挖掘,支持度表示為參數(shù)值組合在失敗測(cè)試中的頻繁度．假設(shè)系統(tǒng)中只存在一個(gè)MFS,則該MFS的頻繁度為1. 考慮到可能存在多個(gè)組合故障模式,故可根據(jù)特定情況對(duì)頻繁度進(jìn)行設(shè)置．假設(shè)support(x→failed)=0.5．支持度高于0.5的項(xiàng)集被認(rèn)為是頻繁項(xiàng)集．如第2節(jié)實(shí)例所示,support({b=2,c=2}→failed)=3/3=1．由于對(duì)每一個(gè)頻繁項(xiàng)集而言,失敗測(cè)試用例集的總數(shù)目固定．因此,可以用頻繁項(xiàng)出現(xiàn)的次數(shù)表示支持度．

如第2節(jié)實(shí)例所示,失敗測(cè)試用例集Tf={T4,T6,T10,T14},在頻繁項(xiàng)集合中需要對(duì)每一個(gè)參數(shù)的參數(shù)值進(jìn)行區(qū)別,將參數(shù)名作為字符串前綴加在其參數(shù)值前面．例如,{a=1}標(biāo)識(shí)為“a1”．依據(jù)每一個(gè)參數(shù)值在失敗測(cè)試用例集中出現(xiàn)次數(shù)進(jìn)行排序可得“b2”:4, “c2”:4,“a1”:2, “a2”:2, “d3”:2, “d1”:1, “d2”:1．依據(jù)支持度0.5的閾值,過濾掉小于支持度的項(xiàng)“d1”和“d2”．按支持度降序?qū)Ω鲄?shù)值進(jìn)行重排,并將每一個(gè)測(cè)試用例集重排的結(jié)果稱為一個(gè)事務(wù)．失敗測(cè)試用例集和事務(wù)見表3．

表3　失敗測(cè)試用例集和頻繁項(xiàng)集

定義9(組合故障頻繁樹)一棵組合故障頻繁樹可以表示成一個(gè)三元組T={root,ips, fht}．其中,root為根節(jié)點(diǎn),通常標(biāo)識(shí)為Null;ips為項(xiàng)前綴子樹,是root的孩子節(jié)點(diǎn)集合;fht為頻繁項(xiàng)的頭指針表．

定義10(項(xiàng)前綴子樹)該子樹的每一個(gè)樹節(jié)點(diǎn)包括3個(gè)域:item-name,count和node link.其中,item-name為項(xiàng)的標(biāo)識(shí);count為到達(dá)該節(jié)點(diǎn)的子路徑個(gè)數(shù);node-link為指向具有相同項(xiàng)標(biāo)識(shí)的下一個(gè)節(jié)點(diǎn)的鏈接,若不存在相同項(xiàng)標(biāo)識(shí)的下一個(gè)節(jié)點(diǎn),則表示為Null．

定義11(頻繁項(xiàng)頭表)頻繁項(xiàng)頭表包括item-name和head-of-node-link兩個(gè)域．其中,item-name為項(xiàng)名;head-of-node-link為指向CFF-tree中第1個(gè)item-name的節(jié)點(diǎn)．

基于CFF-tree的定義,構(gòu)建CFF-tree．具體算法見算法1.

算法1CFF-tree的構(gòu)建

輸入:失敗測(cè)試用例集Γf．

輸出: 組合故障頻繁樹T．

1掃描Γf,收集參數(shù)值的頻繁項(xiàng)集F及其頻繁度計(jì)數(shù)．將F按頻繁度計(jì)數(shù)降序重排為L(zhǎng),L即為參數(shù)值頻繁項(xiàng)集的集合．

2生成組合故障頻繁樹T的根節(jié)點(diǎn)root,并將其標(biāo)記為Null．

3對(duì)L中的每一個(gè)有序的頻繁項(xiàng)集執(zhí)行:將頻繁項(xiàng)集的第1個(gè)項(xiàng)賦給q,剩余的其他項(xiàng)作為整體賦給Q,然后調(diào)用函數(shù)insert-tree([q|Q],T)．

4返回T

在算法1中,insert-tree([q|Q],T)執(zhí)行如下:如果T存在一個(gè)孩子節(jié)點(diǎn)N,使得N.item-name=q.item-name, 則N.count++．否則,生成一個(gè)新節(jié)點(diǎn)N,令N.count=1,并將其父節(jié)點(diǎn)指針指向T,node link指針指向具有相同item-name的節(jié)點(diǎn);如果P為非空集,則遞歸調(diào)用insert-tree(Q,N)．

給定表3的失敗測(cè)試用例集,利用算法1構(gòu)建的CFF-tree如圖1所示．

圖1　基于算法1構(gòu)建的CFF-tree

3.3　最小失效誘因模式挖掘

定義12(條件模式基)一個(gè)參數(shù)值的條件模式基是以該參數(shù)值為結(jié)尾的路徑集合．

給定一棵CFF-tree和頻繁度閾值,對(duì)每一個(gè)頻繁參數(shù)值,抽取其頻繁項(xiàng)集,具體步驟如下:

① 從CFF-tree中獲得該頻繁參數(shù)值的條件模式基;

② 利用條件模式基,構(gòu)建一個(gè)條件CFF-tree;

③ 重復(fù)步驟①和步驟②,直到CFF-tree包含單個(gè)路徑為至．

如圖1中,參數(shù)值“d3”的條件基為{〈“b2”,“c2”,“a1”,“d3”〉:1, 〈“b2”,“c2”,“a2”,“d3”〉: 1}, 參數(shù)值“a1”的條件模式基為{〈“b2”,“c2”,“a2”〉:2}．如果參數(shù)值“a1”為頻繁項(xiàng),則以參數(shù)值“a1”為后綴的頻繁項(xiàng)集可求解其條件模式基．如果條件模式基為單個(gè)路徑,則頻繁項(xiàng)集為路徑中所有參數(shù)值與該參數(shù)值的組合．例如,以“a1”為后綴的頻繁項(xiàng)集為{“b2”,“c2”}與“a1”的組合,其結(jié)果為{{“b2”,“a1”},{“c2”,“a1”},{“b2”,“c2”,“a1”}}．如果條件模式基為多條路徑,則遞歸求解,并對(duì)每一個(gè)結(jié)果進(jìn)行組合．例如,參數(shù)值“d3”的條件模式基為多條路徑{〈“b2”,“c2”,“a1”,“d3”〉:1, 〈“b2”,“c2”,“a2”,“d3”〉:1},假設(shè)最小支持度為2,“a1”和“a2”雖然是滿足最小支持度為2的頻繁項(xiàng),但{“a1”,“d3”},{“a2”,“d3”}不滿足最小支持度,在由“d3”構(gòu)建的條件CFF-tree中應(yīng)該過濾掉“a1”,“a3”．利用這2條路徑構(gòu)建的條件CFF-tree可合并為一條路徑,其頻繁項(xiàng)集可以利用單路徑處理方法進(jìn)行求解．由此可知,由“d3”結(jié)尾、最小支持度為2的頻繁項(xiàng)為{〈“d3”〉, 〈“b2”,“d3”〉,〈“c2”,“d3”〉,〈“b2”,“c2”,“d3”〉}．

由此得到的頻繁項(xiàng)集合中元素?cái)?shù)目可能依然很龐大,需要對(duì)頻繁項(xiàng)集進(jìn)行進(jìn)一步約簡(jiǎn)處理．假設(shè)存在頻繁項(xiàng)集〈“d3”:2〉和〈“a2”,“d3”〉:2．后者包含前者且其頻繁度相同,故可將其歸并為〈“a2”,“d3”〉:2．

最后,給出列表中的前J個(gè)(J可由程序調(diào)試人員自己設(shè)置)的頻繁項(xiàng)作為可疑最小失效誘因模式,提交給程序調(diào)試人員進(jìn)行人工判定．

3.4　算法復(fù)雜度分析

MFS定位的算法復(fù)雜度主要體現(xiàn)在構(gòu)建CFF-tree和基于CFF-tree的組合故障頻繁項(xiàng)定位上．令n表示失敗測(cè)試用例的數(shù)目,m表示每個(gè)測(cè)試用例包含參數(shù)值的平均數(shù)．主要步驟的時(shí)間復(fù)雜度分別為:① 獲得每個(gè)參數(shù)值頻繁度的時(shí)間復(fù)雜度O(n);② 根據(jù)表頭項(xiàng)fht對(duì)失敗測(cè)試用例集中每個(gè)參數(shù)值進(jìn)行排序的時(shí)間復(fù)雜度O(nmlogm);③ 構(gòu)建組合故障頻繁樹的算法時(shí)間復(fù)雜度O(nm2);④ 故障模式定位的時(shí)間復(fù)雜度O(nm2)．

由此可知,組合故障模式定位算法的時(shí)間復(fù)雜度為O(nm2)．該算法所需要的存儲(chǔ)空間主要用于存儲(chǔ)CFF-tree．在最壞的情況下,每一個(gè)失敗測(cè)試用例的參數(shù)值不存在重疊． 假設(shè)一棵組合故障頻繁樹的最大深度為e,最大寬度為f,則構(gòu)建組合故障頻繁樹的空間復(fù)雜度為O(ef)．組合測(cè)試的測(cè)試用例數(shù)目較少,而失敗測(cè)試用例數(shù)目更少,因此,該算法的時(shí)間復(fù)雜度和空間復(fù)雜度均較?。?/p>

4　仿真實(shí)驗(yàn)

4.1　傳統(tǒng)組合故障定位

假設(shè)待測(cè)系統(tǒng)個(gè)數(shù)u分別包含8,10,12個(gè)參數(shù),每個(gè)參數(shù)存在3個(gè)參數(shù)值．利用組合測(cè)試工具ACTS[13]推薦的IPOG算法生成覆蓋表．例如,對(duì)于包含8個(gè)參數(shù)的待測(cè)系統(tǒng),生成的二維覆蓋表包含15個(gè)測(cè)試用例,三維覆蓋表包含60個(gè)測(cè)試用例,四維覆蓋表包含191個(gè)測(cè)試用例．

為了評(píng)估不存在屏蔽效應(yīng)影響下所提方法的有效性,將文獻(xiàn)[6]提出的元組關(guān)系樹模型TRT作為基準(zhǔn)方法進(jìn)行實(shí)驗(yàn)．文獻(xiàn)[7]提出了一種用于組合測(cè)試故障定位的關(guān)系樹模型,即構(gòu)造一個(gè)關(guān)系樹來(lái)記錄所有待測(cè)元組及其之間的關(guān)系,并基于元組關(guān)系樹進(jìn)行故障定位．元組關(guān)系樹模型TRT給出4種測(cè)試用例挑選策略,選用其最優(yōu)的測(cè)試用例挑選策(略路徑法)作為比較標(biāo)準(zhǔn)．與所提方法不同,TRT方法使用精確定位方法．根據(jù)MFS定義,需要檢驗(yàn)MFS中所有子元組是否都為正確元組．然而,存在屏蔽效應(yīng)影響的情況下,該方法顯然是不適用的．對(duì)測(cè)試用例集注入MFS,將包含MFS的測(cè)試用例設(shè)置為失敗的測(cè)試用例．

模擬不存在屏蔽效應(yīng)影響情況下,注入包含單個(gè)t維覆蓋表的MFS,將包含MFS的測(cè)試用例設(shè)置為失敗測(cè)試用例．將測(cè)試用例集合劃分為成功測(cè)試用例集和失敗測(cè)試用例集．利用所提方法的迭代定位框架,得到每一次附加測(cè)試用例數(shù)．對(duì)于3組不同參數(shù)的待測(cè)系統(tǒng),選用不同的MFS重復(fù)進(jìn)行100次實(shí)驗(yàn),并記錄每次附加測(cè)試用例數(shù)目,結(jié)果見圖2．由圖可知,所提方法優(yōu)于TRT方法．值得注意的是,TRT方法使用精確定位,需要檢查MFS中所有子元組是否都為正確元組,這一過程將增加附加測(cè)試用例數(shù);理論上,該方法是有效的,但如果存在屏蔽效應(yīng)影響,則很難得到理想的定位結(jié)果．與TRT方法不同,所提方法直接給出最可疑MFS,提交程序員進(jìn)一步檢查．假設(shè)真實(shí)的MFS在可疑列表中排名第1,即可認(rèn)為定位出正確結(jié)果．實(shí)驗(yàn)中, CFF-tree的定位結(jié)果與參與定位的失敗測(cè)試用例數(shù)目高度相關(guān)．例如,對(duì)于一個(gè)二維MFS,只需要2～3個(gè)失敗測(cè)試用例即可得到較為滿意的定位效果．

(a) 8個(gè)參數(shù)二維比較

(b) 8個(gè)參數(shù)三維比較

(c) 8個(gè)參數(shù)四維比較

(d) 10個(gè)參數(shù)二維比較

(e) 10個(gè)參數(shù)三維比較

(f) 10個(gè)參數(shù)四維比較

(g) 12個(gè)參數(shù)二維比較

(h) 12個(gè)參數(shù)三維比較

(i) 12個(gè)參數(shù)四維比較

圖2不同環(huán)境下所提方法和TRT方法結(jié)果比較

4.2　屏蔽效應(yīng)下的組合故障定位

假定待測(cè)軟件包含10個(gè)參數(shù),在存在屏蔽效應(yīng)影響的情況下,包含MFS的測(cè)試用例以10%和30%的概率偶然成功執(zhí)行．通過ACTS工具生成二維、三維、四維覆蓋矩陣．在測(cè)試用例集中注入單個(gè)MFS, 使得運(yùn)行包含MFS的測(cè)試用例以一定的概率成功執(zhí)行．例如,當(dāng)屏蔽效應(yīng)的概率為30%時(shí),對(duì)每一個(gè)包含MFS的測(cè)試用例調(diào)用一個(gè)隨機(jī)函數(shù),該隨機(jī)函數(shù)以30%概率設(shè)置該測(cè)試用例為成功測(cè)試用例,以70%的概率設(shè)置該測(cè)試用例為失敗測(cè)試用例．

同樣地,利用所提方法的迭代定位框架,得到每一次附加測(cè)試用例數(shù)．在2種不同屏蔽效應(yīng)影響情況下,分別注入二維、三維、四維MFS．在實(shí)驗(yàn)過程中,選用不同參數(shù)值組合的MFS,重復(fù)進(jìn)行100次故障定位,并記錄每次附加測(cè)試數(shù)目,結(jié)果見圖3．圖中, ME和NME分別表示存在和不存在屏蔽效應(yīng)2種情況．由圖可知,隨著屏蔽概率的增加,所使用的附加測(cè)試數(shù)目明顯增大．與不存在屏蔽效應(yīng)影響情況類似,MFS定位結(jié)果高度依賴于失敗測(cè)試用例數(shù)目．因此,CFF-tree方法能在一定數(shù)目的失敗測(cè)試用例集中有效定位MFS．

5　結(jié)論

1) 提出了一種基于組合故障頻繁樹的最小失效誘因模式定位方法．基于測(cè)試用例集及測(cè)試結(jié)果,利用失敗測(cè)試用例集構(gòu)建組合故障頻繁樹CFF-tree,進(jìn)而生成可疑最小失效誘因模式列表．

2) 使用附加測(cè)試技術(shù),給出了一種最小失效誘因模式迭代定位框架．利用該迭代定位框架進(jìn)行多次迭代,可以有效縮減MFS的搜索范圍,直到滿足某一停止準(zhǔn)則．

3) 分別針對(duì)存在和不存在屏蔽效應(yīng)影響2種情況下設(shè)計(jì)仿真實(shí)驗(yàn)．結(jié)果表明,所提方法在定位最小失效誘因模式的基礎(chǔ)上,可以有效減少附加測(cè)試的數(shù)目．

(a) 10%屏蔽概率下二維比較

(b) 10%屏蔽概率下三維比較

(c) 10%屏蔽概率下四維比較

(d) 30%屏蔽概率下二維比較

(e) 30%屏蔽概率下三維比較

(f) 30%屏蔽概率下四維比較

圖3不同屏蔽概率下所提方法的結(jié)果比較

參考文獻(xiàn)(References)

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

[2] 嚴(yán)俊, 張健. 組合測(cè)試:原理與方法[J]. 軟件學(xué)報(bào), 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.