基于分支相關(guān)性分析的不可達(dá)路徑檢測方法

姜淑娟　韓　寒　史嬌嬌　張艷梅,2　鞠小林,3　錢俊彥

1(中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　江蘇徐州　221116)2(計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))　南京　210023)3(南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　江蘇南通　226019)4(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))　廣西桂林　541004)(shjjiang@cumt.edu.cn)

基于分支相關(guān)性分析的不可達(dá)路徑檢測方法

姜淑娟1,4韓寒1史嬌嬌1張艷梅1,2鞠小林1,3錢俊彥4

1(中國礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院江蘇徐州221116)2(計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))南京210023)3(南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院江蘇南通226019)4(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))廣西桂林541004)(shjjiang@cumt.edu.cn)

摘要軟件測試中,不可達(dá)路徑的存在會導(dǎo)致測試資源浪費(fèi),有效地檢測程序中的不可達(dá)路徑有助于節(jié)約測試資源、提高測試效率.分支相關(guān)性的存在是不可達(dá)路徑產(chǎn)生的主要起因.因此,確定分支的相關(guān)性在不可達(dá)路徑的檢測中占據(jù)十分重要的地位.提出了一種利用關(guān)聯(lián)分析和數(shù)據(jù)流分析確定分支相關(guān)性的方法,進(jìn)而實(shí)現(xiàn)不可達(dá)路徑的自動檢測.首先,結(jié)合靜態(tài)分析和動態(tài)分析,構(gòu)建反映程序中各分支判斷語句靜態(tài)依賴關(guān)系和動態(tài)執(zhí)行信息的數(shù)據(jù)集;然后,利用關(guān)聯(lián)分析和數(shù)據(jù)流分析技術(shù)確定分支的相關(guān)性;最后,根據(jù)分支相關(guān)性信息檢測不可達(dá)路徑.基于一組基準(zhǔn)程序和開源程序,開展不可達(dá)路徑檢測實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,該方法能夠準(zhǔn)確地檢測出程序中的不可達(dá)路徑,可以有效地提高軟件測試的效率.

關(guān)鍵詞軟件測試;不可達(dá)路徑;分支相關(guān)性;關(guān)聯(lián)分析;數(shù)據(jù)流分析

許多軟件測試問題都可以歸結(jié)為面向路徑的測試數(shù)據(jù)生成問題[1],而不可達(dá)路徑的存在是路徑測試中的一個(gè)難題,因?yàn)闆]有輸入數(shù)據(jù)能經(jīng)過這些不可達(dá)路徑,從而導(dǎo)致測試數(shù)據(jù)生成階段大量人力和資源的浪費(fèi).因此,路徑的可達(dá)性直接影響著路徑測試的效率和充分性，有效地檢測出這些不可達(dá)路徑不僅能夠降低測試成本,而且能提高測試效率.然而,不可達(dá)路徑的檢測是一個(gè)不可判定的問題[2].目前,不可達(dá)路徑檢測方法主要分為靜態(tài)檢測方法[3-14]和動態(tài)檢測方法[15-17]2類.其中靜態(tài)檢測方法可劃分為基于路徑條件可滿足性的檢測方法[3-9]和基于分支相關(guān)性分析的檢測方法[10-14]，前者針對每條路徑，通過對滿足路徑條件的謂詞組合進(jìn)行求解來判定路徑的可達(dá)性，復(fù)雜度較高;后者通過分析分支語句間是否存在相關(guān)性來檢測不可達(dá)路徑.Bodik等人[10]指出分支相關(guān)性的存在是不可達(dá)路徑產(chǎn)生的主要起因.在一段復(fù)雜程序中,有9%～40%的分支語句具有相關(guān)性，但是該類方法無法分析具有復(fù)雜結(jié)構(gòu)的條件謂詞，因此其分支節(jié)點(diǎn)覆蓋率較低[18].而動態(tài)檢測方法通常在面向目標(biāo)路徑生成測試數(shù)據(jù)階段完成對路徑可達(dá)性的判斷,其計(jì)算代價(jià)較大,并且檢測結(jié)果具有較強(qiáng)的不確定性.

關(guān)聯(lián)分析是一項(xiàng)較為成熟的技術(shù)，其目的是在海量數(shù)據(jù)集中發(fā)現(xiàn)數(shù)據(jù)間的關(guān)聯(lián)信息.在程序分析時(shí)采用關(guān)聯(lián)分析技術(shù),有助于以較低的時(shí)間和空間代價(jià)更快、更準(zhǔn)確地從大量的分支判斷語句執(zhí)行信息中獲取程序分支的相關(guān)信息.在關(guān)聯(lián)分析的基礎(chǔ)上對程序進(jìn)行數(shù)據(jù)流分析,并開展不可達(dá)路徑的檢測,可以有效提高檢測精度.因此本文提出一種結(jié)合關(guān)聯(lián)分析和數(shù)據(jù)流分析2種技術(shù)確定分支相關(guān)性的策略,進(jìn)而自動檢測程序中的不可達(dá)路徑.本文的方法結(jié)合了靜態(tài)分析方法和動態(tài)分析方法的優(yōu)勢，既可以避免單純使用靜態(tài)分析方法帶來的分支節(jié)點(diǎn)覆蓋率較低的缺陷,又可以降低動態(tài)分析方法導(dǎo)致的高昂代價(jià).實(shí)驗(yàn)表明:本文的方法能夠準(zhǔn)確地檢測出程序中的不可達(dá)路徑,可以有效地提高軟件測試的效率.

本文的主要貢獻(xiàn)如下:

1) 提出了一種動靜態(tài)結(jié)合的不可達(dá)路徑檢測方法，有效結(jié)合了靜態(tài)分析和動態(tài)分析的優(yōu)勢;

2) 提出了一種分支相關(guān)性確定方法，將分支相關(guān)性分為B-B相關(guān)性和A-B相關(guān)性，首先利用關(guān)聯(lián)分析的方法獲取B-B相關(guān)性信息，并在此基礎(chǔ)上利用靜態(tài)數(shù)據(jù)流分析技術(shù)獲取純A-B相關(guān)性信息，提高了不可達(dá)路徑的檢測精度;

3) 實(shí)驗(yàn)驗(yàn)證了本文方法的有效性.

1預(yù)備知識

在介紹不可達(dá)路徑的檢測方法之前,本節(jié)首先給出不可達(dá)路徑及關(guān)聯(lián)分析相關(guān)的一些基本概念.

定義1.控制流圖.控制流圖(control flow graph, CFG)是程序中語句邏輯執(zhí)行的一種圖形化表示,可由四元組(N,E,s,f)表示.其中,N為節(jié)點(diǎn)的集合,表示程序中的語句;E?N×N為邊的集合,表示程序中語句間的控制關(guān)系;s為程序的入口節(jié)點(diǎn);f為程序的出口節(jié)點(diǎn).

定義3.控制樹[19](predominator tree,PRT).在CFG中,除s外,其他任何節(jié)點(diǎn)都有一個(gè)直接控制.根據(jù)該控制關(guān)系,可構(gòu)成一棵以s為根節(jié)點(diǎn)的控制樹.控制樹可由三元組(N,E,s)表示,其中E={(idom(ni),ni)|ni∈N-{s}}.

定義4.控制樹主干(main trunk of predominator tree,MTPRT).在控制樹中,由出口節(jié)點(diǎn)及其在控制樹中的所有祖先節(jié)點(diǎn)構(gòu)成的節(jié)點(diǎn)序列為控制樹主干.

定義6. 蘊(yùn)含樹[19](postdominator tree, POT).在CFG中,除f外,其他任何節(jié)點(diǎn)都有一個(gè)直接蘊(yùn)含.根據(jù)該蘊(yùn)含關(guān)系,可構(gòu)成一棵以f為根節(jié)點(diǎn)的蘊(yùn)含樹.蘊(yùn)含樹可由三元組(N,E,f)表示,其中,E={(iimp(ni),ni)|ni∈N-{f}}.

Fig. 1　An example P.圖1　函數(shù)P的示例

定義7. 循環(huán)節(jié)點(diǎn).對于控制流圖CFG中的節(jié)點(diǎn)ni,若存在節(jié)點(diǎn)nj(i≠j),使得nj在CFG對應(yīng)的蘊(yùn)含樹和控制樹中皆是ni的子節(jié)點(diǎn),則節(jié)點(diǎn)ni為循環(huán)節(jié)點(diǎn).

定義8. 路徑.路徑為CFG中的一個(gè)執(zhí)行序列path=(n1,n2,…,nm),其中m為路徑的長度,(ni,ni+1)∈E(i=1,2,…,m-1),若n1=s,nm=f,則path為一條完整路徑,本文中所指的路徑均為完整路徑.若存在一組輸入數(shù)據(jù),使得程序能沿路徑path執(zhí)行,則path為可達(dá)路徑,否則path為不可達(dá)路徑.

定義10. 沖突子路徑.由程序中存在沖突的語句構(gòu)成的語句序列稱為沖突子路徑.根據(jù)產(chǎn)生沖突的語句類型,可分為B-B沖突子路徑和A-B沖突子路徑.

1) B-B沖突子路徑.設(shè)ni和nj是2個(gè)分支判斷語句,如果(ni,nj)有T→T(或T→F)的B-B相關(guān)性,則ni(T)→nj(F)(或ni(T)→nj(T))構(gòu)成B-B沖突子路徑;同樣,如果(ni,nj)有F→T(或F→F)的B-B相關(guān)性,則ni(F)→nj(F)(或ni(F)→nj(T))構(gòu)成B-B沖突子路徑.

2) A-B沖突子路徑.設(shè)n為分支判斷語句,AS為賦值語句集,如果(AS,n)具有&→T(或&→F)的A-B相關(guān)性,則AS→n(F)(或AS→n(T))構(gòu)成A-B沖突子路徑.

為了更加清晰地理解上述概念,下面通過圖1所示的例子進(jìn)行具體的說明.

例1. 圖1(a)為一段由Java語言編寫的程序P,圖1(b)為其相應(yīng)的控制流圖,s,f分別為其入口節(jié)點(diǎn)和出口節(jié)點(diǎn).

根據(jù)控制流圖中的控制關(guān)系和蘊(yùn)含關(guān)系,可以分別得到圖1(c)所示的控制樹和圖1(d)所示的蘊(yùn)含樹,其中,控制樹主干MTPRT={s,n1,n2,n3,n13,f}.對于節(jié)點(diǎn)n6,由于節(jié)點(diǎn)n7,n8,n9,n10在控制樹和蘊(yùn)含樹中皆是節(jié)點(diǎn)n6的子節(jié)點(diǎn),因此節(jié)點(diǎn)n6為循環(huán)節(jié)點(diǎn).對于節(jié)點(diǎn)n6和n7,因?yàn)楫?dāng)節(jié)點(diǎn)n6的取值為真時(shí),節(jié)點(diǎn)n7的取值必為假,因此(n6,n7)有T→F的B-B相關(guān)性.對于路徑path=(s,n1,n2,n3,n4,n5,n6,n7,n8,n10,n6,n11,n13,f),由于path經(jīng)過n6(T)和n7(T),不會有任何一組輸入數(shù)據(jù)能使得程序沿該路徑執(zhí)行,因此路徑path為1條不可達(dá)路徑,而n6(T)→n7(T)則構(gòu)成1條B-B沖突子路徑.對于語句n5,由于賦值語句n1,n2,n4使得語句n5中d≥0取固定值T,因此,({n1,n2,n4},n5)具有&→T的A-B相關(guān)性,然而由于n4?MTPRT,因此({n1,n2,n4},n5)之間&→T的A-B相關(guān)性可轉(zhuǎn)化為(n3,n5)之間T→T的偽B-B相關(guān)性.對于語句n3,由于賦值語句n1使得語句n3中謂詞c==0取固定值T,因此,(n1,n3)具有&→T的A-B相關(guān)性,該A-B相關(guān)性不能轉(zhuǎn)化為B-B相關(guān)性,因此(n1,n3)具有&→T的純A-B相關(guān)性,而n1→n3(F)則構(gòu)成1條A-B沖突子路徑.

定義11. 關(guān)聯(lián)規(guī)則[21].給定:

① 項(xiàng)的集合(itemset):I={i1,i2,…,in};

② 任務(wù)相關(guān)的事務(wù)數(shù)據(jù)集D,其中,每個(gè)事務(wù)TS是I的非空子集,即滿足TS?I;

③ 每個(gè)事務(wù)對應(yīng)唯一的事務(wù)標(biāo)識符TID;

④X,Y為2個(gè)項(xiàng)集,若X?I,Y?I,并且X∩Y=?,則關(guān)聯(lián)規(guī)則的蘊(yùn)涵式為

X?Y[support,confidence]，

其中,規(guī)則X?Y在事務(wù)數(shù)據(jù)集D中成立,X為規(guī)則的前項(xiàng)集,Y為規(guī)則的后項(xiàng)集,support和confidence分別表示X?Y的支持度和置信度.其中,支持度為D中事務(wù)包含X∪Y的概率；置信度為D中包含X的事務(wù)中同時(shí)又包含Y的概率,即條件概率.

滿足最小支持度(min_support)和最小置信度(min_confidence)的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則.最小支持度和最小置信度按需設(shè)定.此外,支持度不小于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集.

2不可達(dá)路徑檢測方法

本節(jié)提出了一種不可達(dá)路徑的自動檢測方法.1)結(jié)合靜態(tài)分析和動態(tài)分析,構(gòu)建反映各分支判斷語句靜態(tài)依賴關(guān)系和動態(tài)執(zhí)行信息的數(shù)據(jù)集;2)通過關(guān)聯(lián)分析方法確定B-B相關(guān)性信息,在此基礎(chǔ)上利用數(shù)據(jù)流分析技術(shù)確定純A-B相關(guān)性信息;3)根據(jù)分支相關(guān)性檢測不可達(dá)路徑.

2.1系統(tǒng)模型

不可達(dá)路徑檢測方法分為3個(gè)階段:①構(gòu)建數(shù)據(jù)集;②確定分支相關(guān)性;③檢測不可達(dá)路徑.系統(tǒng)模型如圖2所示:

Fig. 2　Framework of our method.圖2　系統(tǒng)模型

階段1. 構(gòu)建數(shù)據(jù)集.采用靜動態(tài)結(jié)合的方法,構(gòu)建反映各分支判斷語句靜態(tài)依賴關(guān)系和動態(tài)執(zhí)行信息的數(shù)據(jù)集.首先對程序進(jìn)行靜態(tài)分析,獲取分支節(jié)點(diǎn)序列集;然后采用動態(tài)分析方法,收集程序執(zhí)行時(shí)分支判斷語句的動態(tài)信息,以得到關(guān)聯(lián)分析所需的數(shù)據(jù)集.

階段2. 確定分支相關(guān)性.首先利用關(guān)聯(lián)分析技術(shù)對數(shù)據(jù)集進(jìn)行分析,確定包含偽B-B相關(guān)性在內(nèi)的B-B相關(guān)性;然后利用數(shù)據(jù)流分析方法,并結(jié)合B-B相關(guān)性信息,確定純A-B相關(guān)性信息.

階段3. 檢測不可達(dá)路徑.根據(jù)分支相關(guān)性信息確定沖突子路徑,進(jìn)而檢測程序中的不可達(dá)路徑.將不可達(dá)路徑的檢測運(yùn)用到軟件測試中,從而節(jié)約測試資源、提高測試效率.

2.2數(shù)據(jù)集的構(gòu)建

在本節(jié)中,我們利用動靜態(tài)相結(jié)合的方法對源程序進(jìn)行分析,構(gòu)建反映各分支判斷語句靜態(tài)依賴關(guān)系和動態(tài)執(zhí)行信息的數(shù)據(jù)集.

首先,利用Soot①對程序進(jìn)行靜態(tài)分析,構(gòu)建程序的控制流圖、控制樹及蘊(yùn)含樹,然后通過搜索控制樹獲取具有控制關(guān)系的分支節(jié)點(diǎn)序列集U,U滿足4個(gè)條件:

1)U覆蓋控制流圖中的全部分支節(jié)點(diǎn);

2) ?ui∈U,ui包含了控制樹主干中的每一個(gè)分支節(jié)點(diǎn);

3) ?ui∈U,存在一條路徑pathi,使得pathi包含了ui中的每一個(gè)節(jié)點(diǎn);

4) ?ui∈U,?uj∈U,ui≠uj,其中i≠j.

?ui∈U,采用動態(tài)分析技術(shù),通過JDI(Java debug interface)②監(jiān)聽序列ui中各個(gè)分支節(jié)點(diǎn)ni 1,ni 2,…,ni k的執(zhí)行情況,在輸入域內(nèi)隨機(jī)獲取M個(gè)抽樣輸入數(shù)據(jù),要求當(dāng)程序輸入每個(gè)抽樣數(shù)據(jù)時(shí)ni 1,ni 2,…,ni k全部執(zhí)行,若存在某節(jié)點(diǎn)nix不執(zhí)行,則換取其他抽樣值,直到所有的分支節(jié)點(diǎn)都執(zhí)行.在隨機(jī)抽樣時(shí),我們會使各抽樣值均勻分布在輸入域內(nèi).如果?ui∈U,利用隨機(jī)抽樣不能使ui中的所有分支節(jié)點(diǎn)都執(zhí)行,本文將不會對ui構(gòu)建相應(yīng)數(shù)據(jù)集.因?yàn)榻?jīng)過前期的多次實(shí)驗(yàn),對于不同的ui,隨機(jī)抽樣并執(zhí)行程序,如果出現(xiàn)不能使得ui中的所有分支節(jié)點(diǎn)都執(zhí)行的情況,則會改進(jìn)抽樣方法,適時(shí)調(diào)整抽樣的子區(qū)域,若仍有上述情況發(fā)生,則對ui進(jìn)行手動分析.

M值的設(shè)定對于實(shí)驗(yàn)結(jié)果存在著一定的影響,該值增大時(shí)可能但不一定會提高不可達(dá)路徑的檢測精度,但會增加檢測的復(fù)雜度,值太小時(shí)則會降低檢測精度,增加漏報(bào)和誤報(bào)情況的發(fā)生,本文中M值主要根據(jù)分支節(jié)點(diǎn)序列中節(jié)點(diǎn)的個(gè)數(shù)和輸入?yún)?shù)的個(gè)數(shù)進(jìn)行設(shè)定,設(shè)序列中分支節(jié)點(diǎn)的個(gè)數(shù)為n,輸入?yún)?shù)的個(gè)數(shù)為k,則統(tǒng)計(jì)數(shù)據(jù)量設(shè)為k×2n+1.

為了提高算法的效率,我們僅記錄并分析各分支節(jié)點(diǎn)的信息.?ui∈U,分析當(dāng)程序輸入抽樣值Ii j時(shí)ui中各分支節(jié)點(diǎn)的取向(TF),從而得到抽樣值Ii j對應(yīng)的分支節(jié)點(diǎn)取值序列pi j,依此類推,獲取M個(gè)抽樣值的分支節(jié)點(diǎn)取值序列集vi.為了避免路徑數(shù)目過于龐大,對于循環(huán)次數(shù)較多的循環(huán)語句,我們限制其執(zhí)行次數(shù)不超過3,并記錄其每次執(zhí)行時(shí)的取值情況.最終分支節(jié)點(diǎn)序列集U將得到一個(gè)分支節(jié)點(diǎn)取值序列集的集合V,即

V={v1,v2,…,vi}={{p11,p12,…,p1 M},

{p21,p22,…,p2 M},…,{pi 1,pi 2,…,pi M}}，

其中,pi j是當(dāng)程序輸入抽樣值Ii j時(shí)ui中各分支節(jié)點(diǎn)的取值序列,pi j中的每個(gè)元素取值為TF.

算法1.分支節(jié)點(diǎn)取值序列集的獲取算法.

Function:GetCSValue(TP,PRT)

輸入:待測程序TP、待測程序的控制樹PRT；

輸出:分支節(jié)點(diǎn)取值序列V.

①V=?;

②U=?;

③c=f;

④ do

⑤l=c;

⑥c=c.PRTParentNode;

⑦Analyze(c,l);

⑧ while (c.PRTParentNode!=NULL);

⑨ for (eachui∈U) do

⑩ for (intj=1;j≤M;j++) do

procedureAnalyze(PRTNodec,PRTNodel)

獲取分支節(jié)點(diǎn)取值序列集的集合V之后,對其進(jìn)行關(guān)聯(lián)分析之前,?vi∈V,需要將vi轉(zhuǎn)換為關(guān)聯(lián)分析所需的數(shù)據(jù)集.?vi∈V,按如下方式將vi轉(zhuǎn)化為數(shù)據(jù)集Di,即:

No.ni1ni2…nik1TF…T2FT…T?????MTT…F

其中:

2.3分支相關(guān)性的確定

本節(jié)首先利用關(guān)聯(lián)分析技術(shù)對數(shù)據(jù)集進(jìn)行分析,確定包含偽B-B相關(guān)性在內(nèi)的B-B相關(guān)性,然后利用數(shù)據(jù)流分析方法,并結(jié)合B-B相關(guān)性信息,確定純A-B相關(guān)性信息.

2.3.1基于關(guān)聯(lián)分析的B-B相關(guān)性的確定

本節(jié)對數(shù)據(jù)集進(jìn)行關(guān)聯(lián)分析,從而確定包含偽B-B相關(guān)性在內(nèi)的B-B相關(guān)性信息.?Di∈D,首先從數(shù)據(jù)集Di中找出所有的頻繁項(xiàng)集,然后再由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則.我們對傳統(tǒng)的強(qiáng)關(guān)聯(lián)規(guī)則生成算法[21]進(jìn)行了改進(jìn),避免生成無用的強(qiáng)關(guān)聯(lián)規(guī)則,使其更適用于B-B相關(guān)性的確定,從而提高算法的效率和精度.

對Di進(jìn)行關(guān)聯(lián)分析之前,需要設(shè)定min_support和min_confidence,2值的設(shè)定直接影響得到B-B相關(guān)性信息的可靠性和正確率,結(jié)合B-B相關(guān)性的定義和特點(diǎn),令:

min_confidence=100%.

1) 從Di中找出所有的頻繁項(xiàng)集

從數(shù)據(jù)集Di中,找出所有滿足支持度大于等于min_support的頻繁項(xiàng)集.以2-項(xiàng)集{ni=T,nj=F}為例,其支持度為

support({ni=T,nj=F})=

(1)

我們采用FP-Growth[22]算法對數(shù)據(jù)集進(jìn)行分析.FP-Growth算法采用分治的方法,首先讀取數(shù)據(jù)集Di,構(gòu)造頻繁1-項(xiàng)集及FP-Tree；然后將FP-Tree分解成一些條件模式基(conditional pattern base, CPB)(頻繁項(xiàng)在FP-Tree中的所有節(jié)點(diǎn)祖先路徑的集合),每個(gè)CPB和1個(gè)頻繁1-項(xiàng)集相關(guān)聯(lián),根據(jù)CPB構(gòu)造其相應(yīng)的條件FP-tree;最后采用遞歸算法分別對這些條件FP-tree進(jìn)行挖掘,從而得到所有的頻繁項(xiàng)集F(Di,min_support).

2) 由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則

利用上一步得到的頻繁項(xiàng)集F(Di,min_support)產(chǎn)生置信度大于等于min_confidence的規(guī)則.以頻繁項(xiàng)集{ni=T,nj=F}為例,它產(chǎn)生的規(guī)則ni=T?nj=F,其置信度為

confidence({ni=T}?{nj=F})=

(2)

在傳統(tǒng)的算法中,如果某一規(guī)則的置信度大于等于min_confidence,則該規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則.本文改進(jìn)了傳統(tǒng)的算法,將程序中各分支判斷語句的靜態(tài)依賴信息與算法相結(jié)合,避免生成無用的強(qiáng)關(guān)聯(lián)規(guī)則,使其更適用于B-B相關(guān)性的確定,改進(jìn)后的算法步驟如下:

1) ?f∈F(Di,min_support),產(chǎn)生f的所有非空子集;

2) 對于f的每一個(gè)非空子集g,若規(guī)則g?(f-g)滿足3個(gè)條件:

① (f-g)中的元素個(gè)數(shù)card(f-g)=1;

則規(guī)則g?(f-g)為 “有用的強(qiáng)關(guān)聯(lián)規(guī)則”.

下面通過一個(gè)例子說明基于關(guān)聯(lián)分析的B-B相關(guān)性的確定過程.

Fig. 3　Diand FP-Tree of Di.圖3　Di及其FP-Tree

對FP-Tree進(jìn)行關(guān)聯(lián)分析,可得到支持度大于等于25%的所有頻繁項(xiàng)集F(Di,25%),如表1所示:

Table 1　Frequent Itemsets F(Di,25%)

2.3.2基于數(shù)據(jù)流分析的純A-B相關(guān)性的確定

算法2.純A-B相關(guān)性獲取算法.

FunctionGetABCorrelation(TP,MTPRT,ARList)

輸入:待測程序TP、TP的控制樹主干MTPRT、有效強(qiáng)關(guān)聯(lián)規(guī)則集ARList；

輸出:純A-B相關(guān)性集A-BcorrelationsList.

①A-BcorrelationsList=?;

②CSList=TP中的所有分支判斷語句集合;

③NCSList=ARList中各后項(xiàng)集出現(xiàn)過的分支判斷語句集合;

④ for (eachci∈CSList) do

⑤ if (ci?NCSList) then

⑥r(nóng)eferencelocalList=ci引用變量;

⑦ancestorList=MTPRT中ci的祖先;

⑧ intflag=1;

⑨ for (eachrj∈referencelocalList) do

⑩DataFlowAnalysis(rj,ancestorList);

2.4不可達(dá)路徑的檢測

本節(jié)根據(jù)得到的分支相關(guān)性信息確定沖突子路徑,從而檢測程序中的不可達(dá)路徑.其中,根據(jù)B-B相關(guān)性信息確定B-B沖突子路徑,根據(jù)純A-B相關(guān)性信息確定A-B沖突子路徑.

1)B-B沖突子路徑的確定.設(shè)ni和nj是程序中的2個(gè)分支判斷語句,如果經(jīng)過關(guān)聯(lián)分析后得到(ni,nj)有T→T(或T→F)的相關(guān)性,則ni(T)→nj(F)(或ni(T)→nj(T))構(gòu)成B-B沖突子路徑;同樣,如果(ni,nj)有F→T(或F→F)的相關(guān)性,則ni(F)→nj(F)(或ni(F)→nj(T))構(gòu)成B-B沖突子路徑.

2)A-B沖突子路徑的確定.設(shè)n為分支判斷語句,AS為賦值語句集,如果經(jīng)過數(shù)據(jù)流分析后得到(AS,n)具有&→T或&→F的相關(guān)性,則AS→n(F)或AS→n(T)構(gòu)成A-B沖突子路徑.

在得到的各條B-B沖突子路徑中,可能存在著矛盾、冗余或是無用沖突子路徑,可根據(jù)3個(gè)規(guī)則進(jìn)行刪減：

規(guī)則1. 矛盾沖突子路徑刪減規(guī)則.若ni(T)→nj(T)與ni(T)→nj(F)為2條B-B沖突子路徑,且ni與nj同時(shí)存在于多個(gè)分支節(jié)點(diǎn)序列中,則稱這2條子路徑為矛盾的沖突子路徑,并將這2條子路徑全部刪除;同理,若ni(F)→nj(T)與ni(F)→nj(F)為2條B-B沖突子路徑,并且ni與nj同時(shí)存在于多個(gè)分支節(jié)點(diǎn)序列中,應(yīng)全部刪除.

規(guī)則2. 冗余沖突子路徑刪減規(guī)則.若ni(F)→nk(F)與ni(F),nj(T)→nk(F)為2條B-B沖突子路徑,由于任何可以被后者檢測出來的不可達(dá)路徑同樣也可以被前者檢測出來,因此稱ni(F),nj(T)→nj(F)這類子路徑為冗余的沖突子路徑,并將其刪除.

規(guī)則3. 無用沖突子路徑刪減規(guī)則.設(shè)ni和nj是2個(gè)分支節(jié)點(diǎn),且ni與nj同時(shí)存在于多個(gè)分支節(jié)點(diǎn)序列中,我們將這些序列的集合記為BNS.若在BNS中存在2條分支節(jié)點(diǎn)序列a,b,若存在1條B-B沖突子路徑ni(T)→nj(T),該沖突子路徑可通過分析a得到,并且不能由b得到,則稱ni(T)→nj(T)這類子路徑為無用的沖突子路徑,并將其刪除.

確定沖突子路徑后,根據(jù)不可達(dá)路徑檢測規(guī)則檢測程序中的不可達(dá)路徑.

不可達(dá)路徑檢測規(guī)則:對于任何一條路徑,若該路徑包含沖突子路徑,則它為不可達(dá)路徑.

在不可達(dá)路徑的檢測過程中,分支相關(guān)性的確定主要依賴于程序中分支節(jié)點(diǎn)的執(zhí)行情況.輸入的數(shù)據(jù)是隨機(jī)抽取的,因此分支節(jié)點(diǎn)的執(zhí)行情況也帶有一定的隨機(jī)性質(zhì).然而,隨機(jī)數(shù)據(jù)的抽樣規(guī)模會影響本文方法的檢測效果與效率.如果抽樣數(shù)據(jù)過多,此時(shí)采集數(shù)據(jù)比較全面,因此檢測效果較好,但耗時(shí)較多;反之如果隨機(jī)抽取的輸入數(shù)據(jù)過少,此時(shí)采集數(shù)據(jù)不夠全面,因此可能產(chǎn)生誤報(bào)和漏報(bào)的情況,檢測效果較差,但耗時(shí)較少.為了達(dá)到較好的平衡點(diǎn),我們在隨機(jī)抽樣階段,根據(jù)輸入數(shù)據(jù)的可選值域范圍,使抽樣值的數(shù)量足夠大,并令采樣分布在輸入域的各個(gè)區(qū)域.針對可能會造成抽樣不完善的情況,如當(dāng)一個(gè)分支涉及的值域較大而另一個(gè)分支涉及的值域較小時(shí),本文采取如下措施進(jìn)行處理,即針對各個(gè)分支判斷語句中的條件表達(dá)式,通過區(qū)間算術(shù)方法并結(jié)合輸入域的邊界信息獲取分支取值域,盡可能降低因抽樣不均衡導(dǎo)致誤報(bào)、漏報(bào)的可能性.

3實(shí)驗(yàn)

為了評估本文的方法,首先用一個(gè)實(shí)例進(jìn)行了驗(yàn)證，然后選取了5個(gè)基準(zhǔn)程序和5個(gè)開源項(xiàng)目作為測試對象,檢測程序中的不可達(dá)路徑.

3.1實(shí)例分析

以程序P′為例來驗(yàn)證本文方法的有效性,圖4(a)～4(d)分別為P′的源代碼、控制流圖及其控制樹、蘊(yùn)含樹.

步驟1. 確定B-B相關(guān)性.對P′的控制流圖、控制樹及蘊(yùn)含樹進(jìn)行搜索,可得到分支節(jié)點(diǎn)序列集U={{n3,n4,n5,n14,n17},{ n3,n4,n10,n14,n17}},P′的輸入向量為(a,check),在輸入域[-350,350]×[T,F]內(nèi)隨機(jī)抽樣,在此例中,設(shè)置抽樣值的數(shù)目M=128.在抽樣值的輸入下執(zhí)行程序,分別得到u1,u2對應(yīng)的數(shù)據(jù)集D1,D2,然后分別對D1,D2進(jìn)行關(guān)聯(lián)分析,可得到表2和表3所示的分析結(jié)果.

Fig. 4　An example P′.圖4　示例P′

步驟2. 確定純A-B相關(guān)性.對未在后項(xiàng)集中出現(xiàn)的分支判斷語句n3進(jìn)行分析,語句n3中的引用變量為z,利用數(shù)據(jù)流技術(shù)分析s→n3間z的定值信息,可得到賦值語句n1和n2使得語句n3中z恒等于1.因此,({n1,n2},n3)具有&→T的A-B相關(guān)性.

步驟3. 確定沖突子路徑.根據(jù)表2及表3中的B-B相關(guān)性信息,可得到程序P′中的B-B沖突子路徑信息,然后根據(jù)沖突子路徑的刪減規(guī)則對B-B沖突子路徑進(jìn)行刪減,最終得到如表4所示的B-B沖突子路徑.以n5(n6)→n14(n16)為例,其n5和n14是2個(gè)分支判斷語句,n6為n5的真分支,n16為n14的假分支,因?yàn)?n5,n14)有T→T的相關(guān)性,所以n5(T)→n14(F)是1條B-B沖突子路徑.沖突子路徑的刪減過程如下:

1) 刪除矛盾沖突子路徑.因?yàn)樵趗1中(n3,n4)有T→T的相關(guān)性,且在u2中(n3,n4)有T→F的相關(guān)性,所以n3(T)→n4(F)和n3(T)→n4(T)是2條B-B沖突子路徑.由于n3和n4同時(shí)存在于u1和u2中,因此這2條子路徑為矛盾的沖突子路徑,全部刪除,其他此類型沖突子路徑刪除方法相同.

2) 刪除冗余沖突子路徑.因?yàn)樵趗2中(n3,n10)有T→F的相關(guān)性,(n3,n4,n10)有TF→F的相關(guān)性,所以n3(T)→n10(T)與n3(T),n4(F)→n10(T)為2條B-B沖突子路徑.由于任何可以被n3(T),n4(F)→n10(T)檢測出來的不可達(dá)路徑同樣也可以被n3(T)→n10(T)檢測出來,因此n3(T),n4(F)→n10(T)為冗余的沖突子路徑,將其刪除,其他此類型沖突子路徑刪除方法相同.

3) 刪除無用沖突子路徑.n14與n17同時(shí)存在于u1和u2中,因?yàn)樵趗1中(n14,n17)有T→F的相關(guān)性,所以n14(T)→n17(T)是1條B-B沖突子路徑.但該沖突子路徑不能通過u2得到,因此n14(T)→n17(T)為無用的沖突子路徑,將其刪除.根據(jù)A-B相關(guān)性n1,n2→n3(T)可得到n1,n2→n3(n20)是1條A-B沖突子路徑，如表5所示.

Table 2　B-B Correlations in u1

Continued (Table 2)

Table 3　B-B Correlations in u2

Table 4　B-B Conflicting Subpaths of P′

Table 5　A-B Conflicting Subpaths of P′

步驟4. 檢測不可達(dá)路徑.根據(jù)表4和表5來檢測P′中不可達(dá)路徑,在P′的17條路徑中共有14條不可達(dá)路徑(用pi表示).分別如下:

p1=(s,n1,n2,n3,n4,n5,n6,n8,n14,n15,n17,n18,n19,f);

p2=(s,n1,n2,n3,n4,n5,n6,n8,n14,n16,n17,n18,n19,f);

p3=(s,n1,n2,n3,n4,n5,n6,n8,n14,n16,n17,n19,f);

p4=(s,n1,n2,n3,n4,n5,n7,n8,n14,n15,n17,n18,n19,f);

p5=(s,n1,n2,n3,n4,n5,n7,n8,n14,n15,n17,n19,f);

p6=(s,n1,n2,n3,n4,n5,n7,n8,n14,n16,n17,n19,f);

p7=(s,n1,n2,n3,n4,n9,n10,n11,n13,n14,n15,n17,n18,n19,f);

p8=(s,n1,n2,n3,n4,n9,n10,n11,n13,n14,n15,n17,n19,f);

p9=(s,n1,n2,n3,n4,n9,n10,n11,n13,n14,n16,n17,n18,n19,f);

p10=(s,n1,n2,n3,n4,n9,n10,n11,n13,n14,n16,n17,n19,f);

p11=(s,n1,n2,n3,n4,n9,n10,n12,n13,n14,n15,n17,n18,n19,f);

p12=(s,n1,n2,n3,n4,n9,n10,n12,n13,n14,n15,n17,n19,f);

p13=(s,n1,n2,n3,n4,n9,n10,n12,n13,n14,n16,n17,n19,f).

p14=(s,n1,n2,n3,n20,f).

3.2基準(zhǔn)程序?qū)嶒?yàn)數(shù)據(jù)及分析

為了進(jìn)一步驗(yàn)證本文方法的有效性,實(shí)驗(yàn)部分對一組基準(zhǔn)程序進(jìn)行了分析,在保證分支結(jié)點(diǎn)被100%覆蓋的前提下，最終得到的實(shí)驗(yàn)數(shù)據(jù)如表6所示.表6列出了被測基準(zhǔn)程序的信息(1～3列)和不可達(dá)路徑檢測結(jié)果(4列).從表6可以看到,本文方法可以檢測出各程序中所有的不可達(dá)路徑.我們通過手動分析來驗(yàn)證實(shí)驗(yàn)結(jié)果的正確性,經(jīng)核對,本文方法所檢測到的不可達(dá)路徑均為不可達(dá)路徑,未發(fā)生誤報(bào)和漏報(bào)情況.

Table 6　Experimental Results of Benchmark Programs

3.3開源項(xiàng)目實(shí)驗(yàn)數(shù)據(jù)及分析

利用一組開源程序進(jìn)行檢測,進(jìn)一步評估本文的方法在復(fù)雜程序中檢測不可達(dá)路徑的準(zhǔn)確性和性能,這些開源程序可以從SIR(software-artifact infrastructure repository)①下載.這些程序都不是以數(shù)值計(jì)算為主的程序.其中,NanoXML是一個(gè)小型的XML解析器,XML-security為XML數(shù)字簽名工具,具有較高的代碼量和復(fù)雜的程序結(jié)構(gòu).此外,本節(jié)將本文的方法與Gong的方法[23]和Suhendra的方法[11]進(jìn)行了對比.Gong方法利用最大似然估計(jì)法獲取分支相關(guān)性(B-B相關(guān)性)信息,進(jìn)而實(shí)現(xiàn)不可達(dá)路徑的檢測;Suhendra方法使用靜態(tài)分支相關(guān)性分析方法,通過檢查賦值語句和分支判斷語句之間、不同分支判斷語句之間是否存在沖突來檢測程序中的不可達(dá)路徑.表7中列出了被測程序的信息,表8為對開源程序的不可達(dá)路徑檢測結(jié)果.其中,表8的第2列為總路徑數(shù).基于程序控制流圖分析,先計(jì)算普通分支或嵌套分支結(jié)構(gòu)對應(yīng)的路徑數(shù),然后根據(jù)各部分間的連接方式(如串接等)計(jì)算程序的總路徑數(shù)；第3列為不可達(dá)路徑數(shù).通過本文方法檢測到的不可達(dá)路徑數(shù)與人工分析得到的不可達(dá)路徑數(shù)進(jìn)行對比.本文的一位作者與 2名大學(xué)四年級學(xué)生花費(fèi)近2個(gè)月時(shí)間,手動分析來評估試驗(yàn)結(jié)果的正確性,借助Soot,GraphViz②等工具對程序的數(shù)據(jù)依賴、調(diào)用依賴關(guān)系等信息進(jìn)行可視化處理,一定程度上降低了手動分析的工作量.圖5和圖6分別從分支節(jié)點(diǎn)覆蓋率和檢測精度2個(gè)方面將本文的方法與其他 2種方法進(jìn)行了比較.

Table 7　Descriptions of Industry Programs

Table 8　Comparison of Results of SIR’s Programs

Fig. 5　Comparison of branch node coverage of three methods.圖5　分支節(jié)點(diǎn)覆蓋率比較

Fig. 6　Comparison of detection accuracy of three methods.圖6　檢測精度比較

從表8、圖5和圖6可以看到,本文方法可以檢測出程序中所有不可達(dá)路徑.而Suhendra方法由于在分析賦值語句對分支判斷語句的影響時(shí),僅能分析對變量直接進(jìn)行常量賦值的賦值語句,且該方法不能很好地處理帶有循環(huán)等結(jié)構(gòu)的程序.因此該方法只能檢測出程序中的部分不可達(dá)路徑,分支節(jié)點(diǎn)覆蓋率和檢測精度較低.特別是在分析程序Elevator時(shí),Suhendra方法檢測精度僅有32.8%.Gong方法分支節(jié)點(diǎn)覆蓋率較高,但是由于該方法沒有對A-B相關(guān)性進(jìn)行分析,且在分析B-B相關(guān)性時(shí),該方法需要對具有B-B相關(guān)性的分支判斷語句的個(gè)數(shù)的最大值進(jìn)行限定,無法檢測到由多于限定值的分支判斷語句間B-B相關(guān)性而引起的不可達(dá)路徑.因此,在檢測精度方面,Gong方法相對于本文方法較低.

綜上所述,不管是對基準(zhǔn)程序還是開源項(xiàng)目,本文方法在不可達(dá)路徑檢測方面都有較好效果,可以準(zhǔn)確地檢測出被測程序中的不可達(dá)路徑.當(dāng)分支節(jié)點(diǎn)覆蓋率小于100%時(shí),本文方法可能產(chǎn)生誤報(bào)和漏報(bào).我們在隨機(jī)抽樣階段已采取措施將此可能性降到最低.在2組實(shí)驗(yàn)中,本文方法均未出現(xiàn)誤報(bào)和漏報(bào)情況.在時(shí)間復(fù)雜度方面,假設(shè)待測程序的語句條數(shù)為N,本文方法的時(shí)間復(fù)雜度為O(4N2),Gong方法的復(fù)雜度為O(3N2),Suhendra方法的時(shí)間復(fù)雜度為O(2N2),本文的方法在時(shí)間復(fù)雜度方面較其他2種方法稍有增加,但總體上仍屬于同一個(gè)數(shù)量級.可見，本文方法是一種有效的檢測程序中不可達(dá)路徑的方法,可有效地提高軟件測試的效率.

4相關(guān)工作

目前,很多學(xué)者針對不可達(dá)路徑檢測開展廣泛研究,提出了若干解決方法.常見的方法主要有靜態(tài)檢測方法和動態(tài)檢測方法2類:

1) 靜態(tài)檢測方法可分為基于路徑條件可滿足性的檢測方法和基于分支相關(guān)性檢測方法.在路徑條件可滿足性分析方面,文獻(xiàn)[3-5]使用方程組來表示各條路徑,通過判斷方程組是否有解來判定路徑的可達(dá)性.然而,這類方法的復(fù)雜度較高,而且在處理帶有數(shù)組、指針等結(jié)構(gòu)的程序時(shí),不能很好地工作;文獻(xiàn)[6-7]將區(qū)間算術(shù)用于判斷路徑的可達(dá)性,但是該類方法不能很好地解決條件謂詞中包含非線性表達(dá)式的情況;Ding等人[8]使用符號執(zhí)行技術(shù)對符合代碼模式的分支進(jìn)行分析,進(jìn)而實(shí)現(xiàn)不可達(dá)路徑的檢測;肖慶等人[9]使用變量的抽象取值范圍來表示屬性狀態(tài)條件,通過判斷屬性狀態(tài)條件中的變量取值范圍是否為空來判斷路徑的可達(dá)性.在分支相關(guān)性的分析方面,Bodik等人[10]在傳統(tǒng)的數(shù)據(jù)流分析中加入了分支相關(guān)性分析,從而提高傳統(tǒng)數(shù)據(jù)流分析的精度;Suhendra等人[11]通過檢查賦值語句和分支語句之間、不同分支語句之間是否存在沖突來檢測不可達(dá)路徑.然而,該方法在分析賦值語句對分支語句的影響時(shí),僅能分析對變量直接進(jìn)行常量賦值的賦值語句,且該方法不能很好地處理帶有循環(huán)等結(jié)構(gòu)的程序;Burhan等人[12]使用靜態(tài)分析技術(shù)對程序的控制流和數(shù)據(jù)流進(jìn)行分析,確定存在相關(guān)性的語句,進(jìn)而檢測不可達(dá)路徑;Frank[13]對傳統(tǒng)的數(shù)據(jù)流分析算法進(jìn)行了改進(jìn),并將其用于面向?qū)ο蟪绦虻牟豢蛇_(dá)路徑檢測;Mu等人[14]提出了一種面向函數(shù)調(diào)用關(guān)系的不可達(dá)路徑檢測算法,通過分析程序的控制流和數(shù)據(jù)流信息獲取條件分支相關(guān)性信息,從而實(shí)現(xiàn)面向函數(shù)的不可達(dá)路徑的檢測.在靜態(tài)檢測方法中,基于路徑條件可滿足性的檢測方法復(fù)雜度較高,而基于分支相關(guān)性的檢測方法分支節(jié)點(diǎn)覆蓋率較低.本文提出了一種基于分支相關(guān)性分析、動靜態(tài)結(jié)合的不可達(dá)路徑檢測方法,通過關(guān)聯(lián)分析和數(shù)據(jù)流分析獲取分支相關(guān)性信息,提高了不可達(dá)路徑的檢測精度,并有效克服了使用純靜態(tài)分支相關(guān)性分析方法分支節(jié)點(diǎn)覆蓋率低的問題,能有效處理帶有復(fù)雜謂詞表達(dá)式的程序.

2) 動態(tài)檢測方法通常是在對目標(biāo)路徑生成測試數(shù)據(jù)階段來判定路徑的可達(dá)性.Balakrishnan等人[15]提出了一種語義更新技術(shù),它能從語義上自動排除程序中的不可達(dá)路徑.文獻(xiàn)[16-17]利用遺傳算法來檢測不可達(dá)路徑,為了更好地引導(dǎo)搜索,該類方法通過結(jié)合控制流圖進(jìn)行適應(yīng)度函數(shù)的設(shè)計(jì).然而,該類方法的計(jì)算代價(jià)較大.本文方法利用JDI獲取分支判斷語句的執(zhí)行信息,并在此基礎(chǔ)上采用關(guān)聯(lián)分析技術(shù)確定分支的相關(guān)性信息,降低了計(jì)算代價(jià).

除以上2類主要方法外,研究人員還提出一些動靜態(tài)結(jié)合的不可達(dá)路徑檢測方法.Yang等人[24]首先使用靜態(tài)數(shù)據(jù)流分析方法評估路徑的可達(dá)性,路徑中定義使用對懲罰值之和越低表示路徑的可達(dá)性越高,然后根據(jù)評估值移除路徑集中的不可達(dá)路徑,最后針對靜態(tài)方法未檢測到的不可達(dá)路徑,在測試數(shù)據(jù)生成階段利用基于元啟發(fā)式動態(tài)分析技術(shù)進(jìn)行檢測.Gong等人[23]首先通過最大似然估計(jì)法計(jì)算分支判斷語句不同輸出結(jié)果的條件分布概率值,確定分支相關(guān)性(B-B相關(guān)性),然后根據(jù)分支相關(guān)性檢測不可達(dá)路徑.與本文方法不同的是:1)Gong方法沒有分析A-B相關(guān)性信息,無法檢測到僅由純A-B相關(guān)性引起(不是由B-B相關(guān)性引起)的不可達(dá)路徑;2)在對開源項(xiàng)目進(jìn)行不可達(dá)路徑檢測時(shí),該方法對具有B-B相關(guān)性的分支判斷語句數(shù)的最大值進(jìn)行了限定,無法檢測到由多于限定值的分支判斷語句間的B-B相關(guān)性而引起的不可達(dá)路徑,而本文的方法無需此約束即可檢測由任意分支判斷語句間B-B相關(guān)性引起的不可達(dá)路徑,從而具備更強(qiáng)的適用性.

本文方法利用關(guān)聯(lián)分析和數(shù)據(jù)流分析技術(shù)對引起分支相關(guān)性的情況進(jìn)行全面的分析,具有較強(qiáng)的不可達(dá)路徑檢測能力和較高的檢測精度,可以準(zhǔn)確地檢測出被測程序中的不可達(dá)路徑.綜上所述,本文方法是一種有效的不可達(dá)路徑檢測方法,可以有效地提高軟件測試的效率.

5結(jié)論與進(jìn)一步工作

本文提出了一種新的不可達(dá)路徑檢測方法,首先構(gòu)建反映各分支判斷語句靜態(tài)依賴關(guān)系和動態(tài)執(zhí)行信息數(shù)據(jù)集;然后利用關(guān)聯(lián)分析方法獲取B-B相關(guān)性信息,在此基礎(chǔ)上利用靜態(tài)數(shù)據(jù)流分析技術(shù)獲取純A-B相關(guān)性信息,提高了不可達(dá)路徑的檢測精度;最后根據(jù)分支相關(guān)性檢測不可達(dá)路徑.通過實(shí)驗(yàn)與分析,本文方法能夠準(zhǔn)確地檢測出程序中的不可達(dá)路徑,進(jìn)而可以有效地提高軟件測試的效率.

未來還有幾個(gè)方面的問題需要深入研究:如針對本文的方法還需要進(jìn)行大量的實(shí)驗(yàn)進(jìn)行驗(yàn)證;進(jìn)一步完善我們的原型工具,為后續(xù)的路徑測試提供有價(jià)值的信息.此外,對關(guān)聯(lián)分析方法進(jìn)一步的改進(jìn)和優(yōu)化,使其更適用于B-B分支相關(guān)性的確定;如何縮減冗余的強(qiáng)關(guān)聯(lián)規(guī)則也是我們未來研究方向之一.

參考文獻(xiàn)

[1]Shan Jinhui, Jiang Ying, Sun Ping. The progress of testing research[J]. Journal of Beijing University, 2005, 41(1): 134-145 (in Chinese)(單錦輝, 姜瑛, 孫萍. 軟件測試研究進(jìn)展[J]. 北京大學(xué)學(xué)報(bào), 2005, 41(1): 134-145)

[2]Hedley D, Hennell M A. The causes and effects of infeasible paths in computer programs[C]Proc of the 8th Int Conf on Software Engineering. New York: ACM, 1985: 259-266

[3]Coward P D. Symbolic execution and testing[J]. Information and Software Technology, 1991, 33(1): 53-64

[4]Goldberg A, Wang T C, Zimmerman D. Applications of feasible path analysis to program testing[C]Proc of the 1994 Int Symp on Software Testing and Analysis. New York: ACM, 1994: 80-94

[5]Cadar C, Dunbar D, Engler D. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs[C]Proc of the 8th USENIX Conf on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2008: 209-224

[6]Wang Silan, Wang Yawen, Gong Yunzhan. Path chooses based on interval arithmetic for unit coverage testing[J]. Journal of Tsinghua University, 2011, 51(S1): 1402-1406 (in Chinese)(王思嵐, 王雅文, 宮云戰(zhàn). 單元覆蓋測試中基于區(qū)間運(yùn)算的路徑選擇[J]. 清華大學(xué)學(xué)報(bào), 2011, 51(S1): 1402-1406)

[7]Wang Zhiyan, Liu Chunnian. Applications of interval arithmetic to software testing[J]. Journal of Software, 1998, 9(6): 438-443 (in Chinese)(王志言, 劉椿年. 區(qū)間算術(shù)在軟件測試中的應(yīng)用[J]. 軟件學(xué)報(bào), 1998, 9(6): 438-443)

[8]Ding S, Zhang H Y, Tan H B K. Detecting infeasible branches based on code patterns[C]Proc of the CSMR-WCRE Conf on Software Maintenance, Reengineering and Reverse Engineering. Piscataway, NJ: IEEE, 2014: 74-83

[9]Xiao Qing, Gong Yunzhan, Yang Zhaohong, et al. Path sensitive static defect detecting method[J]. Journal of Software, 2010, 21(2): 209-217 (in Chinese)(肖慶, 宮云戰(zhàn), 楊朝紅, 等. 一種路徑敏感的靜態(tài)缺陷檢測方法[J]. 軟件學(xué)報(bào), 2010, 21(2): 209-217)

[10]Bodik R, Gupta R, Soffa M L. Refining data flow information using infeasible paths[C]Proc of the 6th European Software Engineering Conf and the 5th ACM SIGSOFT Symp on the Foundations of Software Engineering. New York: ACM, 1997: 361-377

[11]Suhendra V, Mitra T, Roychoudhury A, et al. Efficient detection and exploitation of infeasible paths for software timing analysis[C]Proc of the IEEEACM Design Automation Conf. New York: ACM, 2006: 358-363

[12]Burhan B, Izzat A. Infeasible paths detection using static analysis[J]. The Research Bulletin of Jordan ACM, 2013, 2(3): 120-126

[13]Frank T. Infeasible paths in object-oriented programs[J]. Science of Computer Programming, 2015, 97(P1): 91-97

[14]Mu Yongmin, Zheng Yuhui, Zhang Zhihua, et al. The algorithm of infeasible paths extraction oriented the function calling relationship[J]. Chinese Journal of Electronics, 2012, 21(2): 236-240

[16]Bueno P M S, Jino M. Identification of potentially infeasible program paths by monitoring the search for test data[C]Proc of the 15th IEEE Int Automated Software Engineering Conf. Piscataway, NJ: IEEE, 2000: 209-218

[17]Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning[M]. New York: Addison-Wesley, 1989

[18]Chen Rui. Infeasible path identification and its application in structural test[D]. Beijing: Institute of Computing Technology, Chinese Academy of Sciences, 2006 (in Chinese)(陳蕊. 程序中不可達(dá)路徑的識別及其在結(jié)構(gòu)測試中的應(yīng)用[D]. 北京: 中國科學(xué)院計(jì)算技術(shù)研究所, 2006)

[19]Agrawal H. Dominators, super blocks, and program coverage[C]Proc of the 21st Annual ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 1994: 25-34

[20]Mao Chengying, Lu Yansheng. A simplified method for generating test path cases in branch testing[J]. Journal of Computer Research and Development, 2006, 43(2): 321-328 (in Chinese)(毛澄映, 盧炎生. 分支測試中測試路徑用例的簡化生成方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2006, 43(2): 321-328)

[21]Shen Bin. Research on the technologies of association rules[D]. Hangzhou: Zhejiang University, 2007 (in Chinese)(沈斌. 關(guān)聯(lián)規(guī)則相關(guān)技術(shù)研究[D]. 杭州: 浙江大學(xué), 2007)

[22]Han Jiawei, Pei Jian, Yin Yiwen. Mining frequent patterns without candidate generation[C]Proc of the 2000 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2000: 1-12

[23]Gong Dunwei, Yao Xiangjuan. Automatic detection of infeasible paths in software testing[J]. IET Software, 2010, 4(5): 361-370

[24]Yang Rui, Chen Zhenyu, Xu Baowen, et al. Improve the effectiveness of test case generation on EFSM via automatic path feasibility analysis[C]Proc of the 13th IEEE Int High Assurance Systems Engineering Symp. Piscataway, NJ: IEEE, 2011: 17-24

Jiang Shujuan, born in 1966. Professor and PhD supervisor. Member of China Computer Federation. Her research interests include compilation techniques and software engineering.

Han Han, born in 1989. Master. Her research interests include program analysis and software testing (hhan@cumt.edu.cn).

Shi Jiaojiao, born in 1988. Master. Her research interests include program analysis and software testing (sjiao888@126.com).

Zhang Yanmei, born in 1982. PhD and lecturer. Her research interests include program analysis and software testing (ymzhang@cumt.edu.cn).

Ju Xiaolin, born in 1976. PhD and associate professor. His research interests include program analysis and software testing (XiaolinJu@gmail.edu.cn).

Qian Junyan, born in 1973. PhD and professor. Member of China Computer Federation. His research interests include software engineering, model checking and program verification (qjy2000@guet.edu.cn).

Detecting Infeasible Paths Based on Branch Correlations Analysis

Jiang Shujuan1,4, Han Han1, Shi Jiaojiao1, Zhang Yanmei1,2, Ju Xiaolin1,3, and Qian Junyan4

1(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,Xuzhou,Jiangsu221116)2(StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210023)3(SchoolofComputerScienceandTechnology,NantongUniversity,Nantong,Jiangsu226019)4(GuangxiKeyLaboratoryofTrustedSoftware(GuilinUniversityofElectronicTechnology),Guilin,Guangxi541004)

AbstractThe existence of infeasible paths causes a waste of test resources in software testing. Detecting these infeasible paths effectively can save test resources and improve test efficiency. Since the correlation of different conditional statements is the main reason of causing infeasible paths of a program and it costs effort for attempting to cover these paths which are never executed during software testing, the determination of branch correlations plays an important role in detecting infeasible paths. The paper proposes a new approach for detecting the infeasible paths based on association analysis and data flow analysis. Firstly, it builds the data-sets that reflect the static dependencies and the dynamic execution information of conditional statements by combining static analysis with dynamic analysis; then, with two types of branch correlations (called A-B correlation and B-B correlation) defined, it determines the branch correlations respectively with two introduced algorithms which are based on association analysis and data flow analysis; finally, it detects the infeasible paths in accordance with the obtained and refined branch correlations. The paper applies the proposed approach to some benchmarks programs and industry programs to validate its efficiency and effectiveness. The experimental results indicate that our approach can detect infeasible paths accurately and improve the efficiency of software testing.

Key wordssoftware testing; infeasible paths; branch correlations; association analysis; data flow analysis

收稿日期：2014-09-15；修回日期：2015-10-09

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61502497,61562015)；計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué))基金項(xiàng)目(KFKT2014B19)；廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué))研究課題(kx201530)；南通市應(yīng)用研究計(jì)劃基金項(xiàng)目(BK2014055)

中圖法分類號TP311

This work was supported by the National Natural Science Foundation of China (61502497,61562015), the Foundation of State Key Laboratory for Novel Software Technology (Nanjing University) (KFKT2014B19), the Foundation of Guangxi Key Laboratory of Trusted Software (Guilin University of Electronic Technology) (kx201530), and the Nantong Application Research Plan Foundation (BK2014055).