最優化分支覆蓋測試路徑集研究與應用

石磊++翁鶴

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

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

DOIDOI：10.11907/rjdk.171499

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

0引言

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

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

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

1基本原理與方法

1.1無約束邊集

DD圖是一種決策到決策的有向圖，也是獲取程序無約束邊集合的理論基礎。

定義1DD圖：G=（V，E）有兩個區分的邊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。

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

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

通過主宰關系，可把DD圖G轉換為樹，該樹的節點是DD圖的邊，樹根是e0，稱為主宰樹DT（G），圖2所示為jkt主宰樹。

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

通過蘊涵關系，可以把DD圖G轉換為樹，該樹的節點是DD圖的邊，樹根是ek，稱為蘊涵樹IT（G），圖3為jkt蘊涵樹。

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

根據定義，可獲得程序的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個葉子節點。

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

1.2程序路徑樹

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

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

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

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

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

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

（3） 循環語句。循環語句一般包括while、for和dountil循環語句，轉換規則如圖5所示。

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

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

1.3最優解方法

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

以jkt函數為例，最優解求解過程如下：

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

（2）第1次篩選。執行第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）非空，更新獨立路徑總數，如表2所示。

（3）第2次篩選。執行第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）非空，更新獨立路徑總數，如表3所示。

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

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

經過求解，有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}

因此，在執行分支覆蓋測試時，只需從26個分支路徑的測試用例集中選擇路徑1、路徑16、路徑17和路徑25這4條路徑，即可滿足DO178B和GJB/Z 141對分支覆蓋測試100%的指標要求，實現最優分支測試路徑集達到最充分分支覆蓋目標。

2工程應用

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

2.1重要度評價

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

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

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

2.2最優化求解

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

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

2.3應用驗證

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

對測試結果統計分析可知，分支覆蓋測試用例數均有不同程度的降低，最大降低80%，最小降低為0，平均降低率達到60%以上，方法應用效果明顯。但也存在沒有降低分支覆蓋測試用例數的函數，即與未采用求解過程所需的分支覆蓋測試用例數相同，這說明最優化分支覆蓋測試路徑集的方法不僅與基礎原理有關，而且與程序的邏輯結構關系緊密，使用最優化求解不一定獲得最優測試用例集，但大多數函數可以使用該方法獲取最優分支覆蓋測試路徑集。

3結語

本文通過使用最優化分支覆蓋測試路徑集方法，對DD圖無約束邊在路徑構造方面的使用方法進行了擴充，引入程序路徑樹，可解決精簡覆蓋無約束邊的路徑集合，使其數目達到充分測試整個路徑的最優解目標。該方法在工程應用方面也得到了驗證，降低了分支覆蓋測試路徑集，確保了測試的充分性。后續可利用計算機技術進行自動化處理，提升測試效率，滿足實際工程需要。

參考文獻：

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

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

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

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

[5]李必信，方祥圣，袁海，等.一種基于程序切片技術的軟件測試方法[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]姜姍姍，趙中華.分支覆蓋測試路徑集生成系統設計與實現[J].計算機應用，2010，30（增刊1）：218224.

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

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

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