最優(yōu)化分支覆蓋測試路徑集研究與應(yīng)用

石磊++翁鶴

摘要：基于DD圖理論能夠獲取覆蓋整個(gè)路徑的分支測試路徑集合，但缺少精簡無約束邊集合的方法，分支測試用例選取復(fù)雜，工程應(yīng)用更少。在DD圖提煉無約束邊集合的基礎(chǔ)上，對(duì)程序路徑樹進(jìn)行研究，提出通過循環(huán)計(jì)算路徑樹未被選中路徑中包含的未被覆蓋無約束邊的個(gè)數(shù)，實(shí)現(xiàn)最優(yōu)化分支覆蓋測試路徑集選擇方法，滿足基于DO-178B和GJB/Z 141軍用軟件語句、分支和MC/DC測試覆蓋指標(biāo)要求。實(shí)際工程應(yīng)用結(jié)果表明，該方法實(shí)現(xiàn)了優(yōu)化測試用例，滿足了測試充分性要求。

關(guān)鍵詞：DD圖；無約束邊；路徑樹；分支覆蓋測試

DOIDOI：10.11907/rjdk.171499

中圖分類號(hào)：TP319文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：16727800（2017）010015405

0引言

隨著航空武器裝備系統(tǒng)復(fù)雜性提高，軟件所占比例也越來越大[1]，基于DO178B[2]的軟件測試成為保障型號(hào)軟件質(zhì)量的優(yōu)選，滿足程序語句、分支和MC/DC測試覆蓋指標(biāo)要求。在工程活動(dòng)中由于缺乏完備、高效的分支覆蓋測試技術(shù)，致使測試耗費(fèi)和測試效力之間很難達(dá)到平衡[3]。鑒于航空武器裝備系統(tǒng)軟件高可靠性、高安全性和高健壯性需求，應(yīng)對(duì)程序分支進(jìn)行充分性驗(yàn)證，以確保軟件產(chǎn)品質(zhì)量。分支覆蓋率是檢驗(yàn)軟件測試充分性的重要指標(biāo)之一，應(yīng)達(dá)到100%覆蓋的指標(biāo)要求[4]。

為了對(duì)程序的分支進(jìn)行充分性驗(yàn)證，需要研究測試路徑生成、測試輸入數(shù)據(jù)生成以及程序切片[5]等技術(shù)，達(dá)到充分性驗(yàn)證目標(biāo)的關(guān)鍵是通過DD圖提煉無約束邊集合，以獲取覆蓋整個(gè)路徑的測試路徑集合[6]。文獻(xiàn)[7]通過選用十字鏈表結(jié)構(gòu)存儲(chǔ)程序的DD圖求解無約束邊，文獻(xiàn)[8]通過改進(jìn)的FindExactUE算法求解無約束邊，文獻(xiàn)[9]通過基于關(guān)鍵分支尋找算法求解無約束邊，運(yùn)用不同方法能夠獲取無約束邊集合，但缺少精簡無約束邊集合的方法，工程應(yīng)用更少。

本文通過引入樹的理論，結(jié)合DD圖提煉無約束邊方法，通過循環(huán)計(jì)算路徑樹未被選中路徑中包含未被覆蓋的無約束邊的個(gè)數(shù)，以最優(yōu)分支測試路徑集達(dá)到最充分分支覆蓋目標(biāo)。實(shí)驗(yàn)證明該方法切實(shí)可行，工程應(yīng)用較好。

1基本原理與方法

1.1無約束邊集

DD圖是一種決策到?jīng)Q策的有向圖，也是獲取程序無約束邊集合的理論基礎(chǔ)。

定義1DD圖：G=（V，E）有兩個(gè)區(qū)分的邊e0和ek（惟一進(jìn)入的邊和惟一離開的邊），e0可以到達(dá)E的任何一個(gè)邊，E的任何一個(gè)邊都可以到達(dá)ek，對(duì)任何n∈V，n≠H（e0），n≠T（ek），indegree（n）+outdegree（n）>2，indegree（H（e0））=0，outdegree（T（e0））=l，indegree（H（ek））=l，outdegree（T（ek））=0。

以某型產(chǎn)品嵌入式軟件為例，根據(jù)“角通道濾波”函數(shù)jkt的程序流程，可將程序流程圖轉(zhuǎn)換為DD圖，如圖1所示。

定義2主宰關(guān)系：設(shè)G=（V，E）是一個(gè)DD圖，e0和ek分別是G的惟一進(jìn)入的邊和惟一離開的邊。邊ei主宰邊ej，當(dāng)且僅當(dāng)從e0到ej的任一條路徑都通過ei。

通過主宰關(guān)系，可把DD圖G轉(zhuǎn)換為樹，該樹的節(jié)點(diǎn)是DD圖的邊，樹根是e0，稱為主宰樹DT（G），圖2所示為jkt主宰樹。

定義3蘊(yùn)涵關(guān)系：設(shè)G=（V，E）是一個(gè)DD圖，e0和ek分別是G的惟一進(jìn)入的邊和惟一離開的邊。邊ei蘊(yùn)涵邊ej，當(dāng)且僅當(dāng)從ej到ek的任何一條路徑都通過ei。

通過蘊(yùn)涵關(guān)系，可以把DD圖G轉(zhuǎn)換為樹，該樹的節(jié)點(diǎn)是DD圖的邊，樹根是ek，稱為蘊(yùn)涵樹IT（G），圖3為jkt蘊(yùn)涵樹。

定義4無約束邊：如果一個(gè)邊eu不主宰其它的節(jié)點(diǎn)也不被其它節(jié)點(diǎn)所蘊(yùn)涵，則eu稱為無約束邊。

根據(jù)定義，可獲得程序的DD圖、主宰樹DT（G）和蘊(yùn)涵樹IT（G），從而提取程序的無約束邊集合UE（G）=DT（G）∩IT（G）。

jkt的無約束邊集合為：

UE（G）={e4、e5、e6、e7、e8、e9、e11、e12、e13、e14、e15、e16、e17}∩{e1、e2、e3、e4、e5、e6、e8、e9、e11、e12、e14、e15、e16}={e4、e5、e6、e8、e9、e11、e12、e14、e15、e16}，總共10個(gè)葉子節(jié)點(diǎn)。

按理論，覆蓋程序無約束邊集合就能覆蓋整個(gè)程序路徑，能夠滿足型號(hào)軟件測試要求，但在工程應(yīng)用中，不能達(dá)到分支覆蓋測試路徑集最優(yōu)解目標(biāo)，難以應(yīng)用。

1.2程序路徑樹

為求解工程應(yīng)用中分支覆蓋測試路徑集的最優(yōu)解，需要引入樹的理論。

定義5樹：是n（n>=0）個(gè)結(jié)點(diǎn)的有限集，在任意一棵非空樹中：①有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)；②當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1，T2，…，Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹。

定義6二叉樹：是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的節(jié)點(diǎn)），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。

通過DD圖能夠獲取覆蓋整個(gè)程序的無約束邊集，但程序流程直觀性差，測試用例集選取復(fù)雜，需要利用轉(zhuǎn)換規(guī)則將DD圖轉(zhuǎn)換為樹圖。DD圖轉(zhuǎn)換為樹圖的方法包括順序語句、判定語句和循環(huán)語句的轉(zhuǎn)換規(guī)則。

（1） 順序語句。順序執(zhí)行的兩條或者兩條以上語句的結(jié)點(diǎn)，則合并為一個(gè)結(jié)點(diǎn)。

（2） 分支語句。分支語句一般包括原子謂詞、與謂詞、或謂詞、組合謂詞和case分支語句，轉(zhuǎn)換規(guī)則如圖4所示。

（3） 循環(huán)語句。循環(huán)語句一般包括while、for和dountil循環(huán)語句，轉(zhuǎn)換規(guī)則如圖5所示。

依據(jù)樹的理論，通過DD圖轉(zhuǎn)換樹圖的方法能夠?qū)D圖轉(zhuǎn)換為路徑樹，其以二叉樹的形式表示，當(dāng)遍歷二叉樹葉子節(jié)點(diǎn)到二叉樹根節(jié)點(diǎn)的一條路徑時(shí)，即生成與該路徑相對(duì)應(yīng)的一組測試用例，如圖6所示。例如路徑1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}表示為一個(gè)測試用例。從圖6可以看出，e8和e9節(jié)點(diǎn)下路徑集在e6和e7節(jié)點(diǎn)下是相同的（采用示意圖表示），路徑圖使得程序流程更加清晰，測試用例選取更加便捷，表示方法更適合工程應(yīng)用。endprint

因此，通過程序路徑樹能夠快速、準(zhǔn)確、完整計(jì)算出100%覆蓋程序分支路徑的測試用例集，jkt函數(shù)所需的覆蓋分支測試用例集數(shù)為26個(gè)。

1.3最優(yōu)解方法

根據(jù)定義1，覆蓋所有無約束邊的路徑集也覆蓋了所有路徑，而在滿足覆蓋所有分支路徑邊的集合中，無約束邊是最少的。據(jù)此可推斷，在選取分支覆蓋測試路徑時(shí)，使每一條從e0到ek的分支測試路徑盡可能充分地覆蓋無約束邊集合UE（G）中的所有節(jié)點(diǎn)，就能達(dá)到精簡分支覆蓋測試路徑集的目標(biāo)，實(shí)現(xiàn)最優(yōu)解求解。因此，可通過循環(huán)計(jì)算程序路徑樹未被選中路徑中包含未被覆蓋的無約束邊的個(gè)數(shù)，選擇最佳測試路徑，直到無約束邊全部覆蓋。最優(yōu)解求解流程如圖7所示。

以jkt函數(shù)為例，最優(yōu)解求解過程如下：

（1）獨(dú)立路徑總數(shù)。根據(jù)路徑樹可以獲取jkt函數(shù)100%覆蓋程序分支路徑的測試用例集26個(gè)，如表1所示。

（2）第1次篩選。執(zhí)行第1次篩選，表1中的路徑1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}包含的無約束邊最多有4個(gè)，分別是e4、e8、e11和e15，未被覆蓋的無約束邊集合更新為UE（G）={e5、e6、e9、e12、e14、e16}。第一次篩選后，UE（G）非空，更新獨(dú)立路徑總數(shù)，如表2所示。

（3）第2次篩選。執(zhí)行第2次篩選，表2中的路徑16={e1→e2→e3→e5→e7→e9→e10→e12→e13→e16→e17}包含的無約束邊最多有4個(gè)，分別是e5、e9、e12和e16，所以被選中，未被覆蓋的無約束邊集合更新為UE（G）={e6、e14}。第2次篩選后，UE（G）非空，更新獨(dú)立路徑總數(shù)，如表3所示。

（4）第3次篩選。執(zhí)行第3次篩選，表3中的路徑17={e1→e2→e6→e8→e10→e11→e13→e15→e17}包含的無約束邊最多有1個(gè)e6，所以被選中，未被覆蓋的無約束邊集合更新為UE（G）={e14}。第3次篩選后，UE（G）非空，更新獨(dú)立路徑總數(shù)如表4所示。

（5） 第四次篩選。執(zhí)行第4次篩選，表4中的路徑25={e1→e14→e15→e17}包含的無約束邊最多有1個(gè)，是e14，所以被選中，則未被覆蓋的無約束邊集合更新為UE（G）={空}。第4次篩選后，UE（G）為空，求解結(jié)束。

經(jīng)過求解，有4條分支測試路徑被選中，分別是：

路徑1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}

路徑16={e1→e2→e3→e5→e7→e9→e10→e12→e13→e16→e17}

路徑17={e1→e2→e6→e8→e10→e11→e13→e15→e17}

路徑25={e1→e14→e15→e17}

因此，在執(zhí)行分支覆蓋測試時(shí)，只需從26個(gè)分支路徑的測試用例集中選擇路徑1、路徑16、路徑17和路徑25這4條路徑，即可滿足DO178B和GJB/Z 141對(duì)分支覆蓋測試100%的指標(biāo)要求，實(shí)現(xiàn)最優(yōu)分支測試路徑集達(dá)到最充分分支覆蓋目標(biāo)。

2工程應(yīng)用

以某型產(chǎn)品嵌入式軟件為例，對(duì)最優(yōu)化分支覆蓋測試路徑集的研究進(jìn)行工程化應(yīng)用，以驗(yàn)證應(yīng)用效果。

2.1重要度評(píng)價(jià)

由于型號(hào)嵌入式軟件的大量使用，軟件所要完成的功能日益復(fù)雜，導(dǎo)致嵌入式軟件復(fù)雜度也呈正比上升。在實(shí)際工程應(yīng)用中首先要對(duì)程序進(jìn)行質(zhì)量度量分析，以確定函數(shù)的測試優(yōu)先級(jí)，對(duì)關(guān)鍵/重要函數(shù)進(jìn)行充分性測試，以保證軟件功能的正確性。一般利用McCabe質(zhì)量度量模型[7]獲取每個(gè)函數(shù)的質(zhì)量度量數(shù)據(jù)，對(duì)于圈復(fù)雜度V（G）≥10的程序按照由大到小原則進(jìn)行測試優(yōu)先級(jí)排序，以確定測試順序。

利用McCabe工具對(duì)某型產(chǎn)品嵌入式軟件進(jìn)行質(zhì)量度量分析，共分析342個(gè)函數(shù)，其中圈復(fù)雜度V（G）≥10的函數(shù)有76個(gè)，按由大到小原則獲取函數(shù)測試優(yōu)先級(jí)，函數(shù)V（G）相同時(shí)則按照McCabe模型EV（G）指標(biāo)由大到小排序，最終形成測試順序如表5所示。

通過測試順序排序，優(yōu)先保障對(duì)復(fù)雜度高的函數(shù)進(jìn)行測試驗(yàn)證，確保測試充分性要求，提升測試工作效率。

2.2最優(yōu)化求解

按照本文提出的分支覆蓋測試路徑集最優(yōu)解求解過程，對(duì)經(jīng)過測試排序的76個(gè)函數(shù)進(jìn)行最優(yōu)解求解，獲取76個(gè)函數(shù)的最優(yōu)化分支覆蓋測試路徑集，過程如下：①計(jì)算每個(gè)函數(shù)的DD圖、主宰樹和蘊(yùn)涵樹，獲取無約束邊集合；②利用轉(zhuǎn)換規(guī)則，將DD圖轉(zhuǎn)換為樹圖，獲取程序路徑樹，計(jì)算獨(dú)立路徑總數(shù)；③利用求解流程，通過循環(huán)計(jì)算路徑樹未被選中路徑中包含未被覆蓋的無約束邊個(gè)數(shù)，獲取最優(yōu)解。

通過最優(yōu)解求解，能夠獲得滿足基于DO178B和GJB/Z 141軍用軟件語句、分支和MC/DC測試覆蓋指標(biāo)要求的最優(yōu)解測試用例。最優(yōu)解測試路徑集結(jié)果如表6所示。

2.3應(yīng)用驗(yàn)證

為驗(yàn)證方法的有效性，對(duì)76個(gè)函數(shù)進(jìn)行重新測試驗(yàn)證，未采用最優(yōu)解求解的測試路徑集如表7所示。

對(duì)測試結(jié)果統(tǒng)計(jì)分析可知，分支覆蓋測試用例數(shù)均有不同程度的降低，最大降低80%，最小降低為0，平均降低率達(dá)到60%以上，方法應(yīng)用效果明顯。但也存在沒有降低分支覆蓋測試用例數(shù)的函數(shù)，即與未采用求解過程所需的分支覆蓋測試用例數(shù)相同，這說明最優(yōu)化分支覆蓋測試路徑集的方法不僅與基礎(chǔ)原理有關(guān)，而且與程序的邏輯結(jié)構(gòu)關(guān)系緊密，使用最優(yōu)化求解不一定獲得最優(yōu)測試用例集，但大多數(shù)函數(shù)可以使用該方法獲取最優(yōu)分支覆蓋測試路徑集。

3結(jié)語

本文通過使用最優(yōu)化分支覆蓋測試路徑集方法，對(duì)DD圖無約束邊在路徑構(gòu)造方面的使用方法進(jìn)行了擴(kuò)充，引入程序路徑樹，可解決精簡覆蓋無約束邊的路徑集合，使其數(shù)目達(dá)到充分測試整個(gè)路徑的最優(yōu)解目標(biāo)。該方法在工程應(yīng)用方面也得到了驗(yàn)證，降低了分支覆蓋測試路徑集，確保了測試的充分性。后續(xù)可利用計(jì)算機(jī)技術(shù)進(jìn)行自動(dòng)化處理，提升測試效率，滿足實(shí)際工程需要。

參考文獻(xiàn)：

＼[1＼]劉斌.軟件驗(yàn)證與確認(rèn)[M].北京：國防工業(yè)出版社，2011.

[2]RTCA.DO178B機(jī)載系統(tǒng)和設(shè)備合格審定中的軟件考慮[S].RTCA/EUROCAE，1992.

[3]白曉東，劉代軍，張蓬蓬.空空導(dǎo)彈[M].北京：國防工業(yè)出版社，2014.

[4]許聚常，朱國慶，尹平.GJB/Z1412004 軍用軟件測試指南[S].北京：中國人民解放軍總裝備部，2004.

[5]李必信，方祥圣，袁海，等.一種基于程序切片技術(shù)的軟件測試方法[J].計(jì)算機(jī)科學(xué)，2001，28（12）：99101.

[6]A BERTOLINO，R MIRANDOLA，E PECILOA. A case study in branch testing automation. [J].Journal of System and Software，1997，38（1）：4759.

[7]葉俊民，王俊杰，董威.一種基于程序DD圖的無約束邊生成算法[J].計(jì)算機(jī)科學(xué)，2009，36（2）：296298.

[8]姜姍姍，趙中華.分支覆蓋測試路徑集生成系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2010，30（增刊1）：218224.

[9]施冬梅.分支測試中關(guān)鍵分支的尋找算法[J].計(jì)算機(jī)與數(shù)字工程，2011（9）：1619.

[10]尹平，許聚常，張慧穎.軟件測試與軟件質(zhì)量評(píng)價(jià)[M].北京：國防工業(yè)出版社，2008.

責(zé)任編輯（責(zé)任編輯：杜能鋼）endprint