石磊++翁鶴

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

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

DOIDOI：10.11907/rjdk.171499

中圖分類號：TP319文獻標識碼：A文章編號：16727800（2017）010015405

0引言

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

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

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

1基本原理與方法

1.1無約束邊集

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

定義1DD圖：G=（V，E）有兩個區(qū)分的邊e0和ek（惟一進入的邊和惟一離開的邊），e0可以到達E的任何一個邊，E的任何一個邊都可以到達ek，對任何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）是一個DD圖，e0和ek分別是G的惟一進入的邊和惟一離開的邊。邊ei主宰邊ej，當且僅當從e0到ej的任一條路徑都通過ei。

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

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

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

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

根據(jù)定義，可獲得程序的DD圖、主宰樹DT（G）和蘊涵樹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個葉子節(jié)點。

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

1.2程序路徑樹

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

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

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

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

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

（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)換為路徑樹，其以二叉樹的形式表示，當遍歷二叉樹葉子節(jié)點到二叉樹根節(jié)點的一條路徑時，即生成與該路徑相對應的一組測試用例，如圖6所示。例如路徑1={e1→e2→e3→e4→e7→e8→e10→e11→e13→e15→e17}表示為一個測試用例。從圖6可以看出，e8和e9節(jié)點下路徑集在e6和e7節(jié)點下是相同的（采用示意圖表示），路徑圖使得程序流程更加清晰，測試用例選取更加便捷，表示方法更適合工程應用。endprint

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

1.3最優(yōu)解方法

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

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

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

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

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

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

（5） 第四次篩選。執(zhí)行第4次篩選，表4中的路徑25={e1→e14→e15→e17}包含的無約束邊最多有1個，是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í)行分支覆蓋測試時，只需從26個分支路徑的測試用例集中選擇路徑1、路徑16、路徑17和路徑25這4條路徑，即可滿足DO178B和GJB/Z 141對分支覆蓋測試100%的指標要求，實現(xiàn)最優(yōu)分支測試路徑集達到最充分分支覆蓋目標。

2工程應用

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

2.1重要度評價

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

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

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

2.2最優(yōu)化求解

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

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

2.3應用驗證

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

對測試結(jié)果統(tǒng)計分析可知，分支覆蓋測試用例數(shù)均有不同程度的降低，最大降低80%，最小降低為0，平均降低率達到60%以上，方法應用效果明顯。但也存在沒有降低分支覆蓋測試用例數(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)化分支覆蓋測試路徑集方法，對DD圖無約束邊在路徑構(gòu)造方面的使用方法進行了擴充，引入程序路徑樹，可解決精簡覆蓋無約束邊的路徑集合，使其數(shù)目達到充分測試整個路徑的最優(yōu)解目標。該方法在工程應用方面也得到了驗證，降低了分支覆蓋測試路徑集，確保了測試的充分性。后續(xù)可利用計算機技術(shù)進行自動化處理，提升測試效率，滿足實際工程需要。

參考文獻：

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

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

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

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

[5]李必信，方祥圣，袁海，等.一種基于程序切片技術(shù)的軟件測試方法[J].計算機科學，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].計算機科學，2009，36（2）：296298.

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

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

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

責任編輯（責任編輯：杜能鋼）endprint