基于AOE網(wǎng)的軟件關(guān)鍵路徑覆蓋測試

職曉+張江華

摘要：嵌入式軟件的復(fù)雜度越來越高。作為軟件可靠性測試的一種重要方法，完全路徑覆蓋在實際項目測試中越來越不現(xiàn)實。針對這種現(xiàn)狀，提出了一種易于操作的關(guān)鍵路徑覆蓋測試方法。該方法利用AOE網(wǎng)生成全路徑矩陣（APM）算法求出待測程序的關(guān)鍵路徑，然后利用自動化測試工具對程序進行線性代碼與跳轉(zhuǎn)（LCSAJ）分析，最后在其輔助下完成關(guān)鍵路徑覆蓋測試。實驗結(jié)果表明：在保障軟件可靠性的前提下，該方法節(jié)約了測試成本，顯著提升了測試效率，具有一定的工程應(yīng)用價值。

關(guān)鍵詞：AOE網(wǎng)；關(guān)鍵路徑；鄰接矩陣；APM矩陣

中圖分類號：TP306

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2015）003-0026-04

0 引言

嵌入式軟件在嵌入式系統(tǒng)中越來越重要，嵌入式軟件的可靠性成為軟件開發(fā)中的重要因素。路徑覆蓋作為軟件可靠性測試的重要指標(biāo)，在嵌入式軟件測試中應(yīng)用越來越廣泛。然而，由于工程中的代碼邏輯復(fù)雜分支繁多，完全的路徑覆蓋測試用例個數(shù)會隨著程序中分支的增加呈指數(shù)級增長[1]，造成測試成本過高。為了兼顧軟件可靠性和測試成本，從眾多路徑中選出關(guān)鍵路徑進行測試成為近年來嵌入式軟件測試研究的重要課題。

傳統(tǒng)的關(guān)鍵路徑求解算法往往是分別求出所有路徑的最早發(fā)生時間和最遲發(fā)生時間，以及每項路徑的最早開始時間和最遲開始時間，然后判斷哪些路徑是關(guān)鍵路徑，算法過程復(fù)雜。對此，一些研究人員對傳統(tǒng)的算法進行了改進，文獻(xiàn)[2]在廣度優(yōu)先搜索的基礎(chǔ)上，給出了一種求解關(guān)鍵路徑的算法。該算法采用圖的十字鏈表結(jié)構(gòu)形式，不需要拓?fù)渑判騺砬蠼怅P(guān)鍵路徑。然而，此算法需要對圖進行3次廣度優(yōu)先搜索才能輸出所有關(guān)鍵活動，而且不能將所有的關(guān)鍵路徑輸出。文獻(xiàn)[3]在深度優(yōu)先搜索的基礎(chǔ)上，求出從源點到匯點的所有路徑，經(jīng)過分析比較求取關(guān)鍵路徑。由于在求解過程中需要進行多次遞歸回溯，算法的執(zhí)行效率較低。同時，傳統(tǒng)的路徑覆蓋測試用例設(shè)計，是通過人工分析各個判定中的條件來確定用例中各個變量的取值，對于程序較為復(fù)雜的判定，這種方法往往效率較低，而且容易出錯。

針對上述問題，本文提出了一種全新的關(guān)鍵路徑覆蓋測試方法。首先利用程序的AOE網(wǎng)的鄰接矩陣生成矩陣APM算法，求解出待測程序的關(guān)鍵路徑，然后，基于LCSAJ的概念設(shè)計相應(yīng)的測試用例。這種方法不但可以輸出所有關(guān)鍵路徑，而且提高了關(guān)鍵路徑的生成效率。同時，由于存在大量的測試工具可以進行LCSAJ分析，因此可以快速準(zhǔn)確地完成測試用例的設(shè)計。總之，這種方法在保證軟件的可靠性前提下，不僅合理地分配了測試資源，而且大大提高了測試的自動化程度。

1 基本概念

1.1 關(guān)鍵路徑

控制關(guān)系是一個程序正常運行的關(guān)鍵因素，通常用控制流程圖來表征?？刂屏鲌D中有兩個要素，如圖1所示，結(jié)點以標(biāo)有編號的圓圈表示，代表一個或多個無分支的語句；控制流以箭頭表示，表征控制的順序[4]。為了評估程序的控制結(jié)構(gòu)，控制流圖中的連接加入連接權(quán)值a～e，通常把這種帶權(quán)值的控制流圖稱為AOE網(wǎng)。AOE網(wǎng)中入度為零的點稱為源點，出度為零的點稱為匯點。通常AOE網(wǎng)中從源點出發(fā)到匯點結(jié)束的有序結(jié)點序列稱為該AOE網(wǎng)的路徑。路徑中連接權(quán)值的和稱為路徑長度。通常，一個AOE網(wǎng)中最長的路徑就叫關(guān)鍵路徑。

AOE網(wǎng)也可以表示成矩陣的形式，稱為AOE網(wǎng)的鄰接矩陣。一個鄰接矩陣是一個方陣，其行列數(shù)目為AOE網(wǎng)中的結(jié)點數(shù)，行列依次對應(yīng)被標(biāo)識的結(jié)點，矩陣元素對應(yīng)到相應(yīng)結(jié)點間的連接。元素a～e的值代表連接權(quán)值。圖1對應(yīng)的鄰接矩陣如圖2所示。

1.2 線性代碼與跳轉(zhuǎn)

LCSAJ（linear coded sequence and jump）是指可執(zhí)行代碼的線性序列，這個序列的開始可以是程序的開始或控制流中可能跳轉(zhuǎn)的一個起點，它的終點可以是一個明確的控制流跳轉(zhuǎn)點或程序的結(jié)束[5]。這個線性代碼序列可以由一個或多個連續(xù)的基本模塊組成。因此，為了控制流執(zhí)行線性代碼序列和跳轉(zhuǎn)，必須有相應(yīng)的代碼滿足相關(guān)條件。一個LCSAJ由3個要素——開始行、結(jié)束行、跳轉(zhuǎn)目的行組成。程序的一條路徑可能由幾個首尾相連LCSAJ組成，其中第一個LCSAJ起點為程序起點，最后一個LCSAJ的終點為程序終點。

路徑的執(zhí)行關(guān)鍵就是代碼中每一個謂詞條件的選取。基于LCSAJ概念，將源代碼分割成若干子代碼段，通過組合即可實現(xiàn)相應(yīng)的路徑覆蓋?，F(xiàn)在有許多測試工具可供LCSAJ分析，故可借助這些工具得到相關(guān)路徑對應(yīng)的謂詞取值組合，進而準(zhǔn)確迅速地完成指定路徑的覆蓋測試。

2 求解關(guān)鍵路徑

2.1 權(quán)值確定算法

2.1.1 權(quán)值影響因子

（1）分支執(zhí)行概率。嵌入式軟件往往有實際的應(yīng)用背景，因此當(dāng)程序運行到判決結(jié)點時，不同的分支選擇通常對應(yīng)著不同的物理意義，當(dāng)程序運行到判決結(jié)點時，相應(yīng)分支執(zhí)行的概率將影響這些分支權(quán)值的確定。事實上，此概率值通常要根據(jù)軟件用戶的使用情況確定。

（2）函數(shù)接口參數(shù)。被測函數(shù)的接口參數(shù)包括傳值參數(shù)、引用參數(shù)、指針參數(shù)3種類型。傳值參數(shù)調(diào)用單元函數(shù)時傳給函數(shù)的實參并不因函數(shù)調(diào)用而改變，而引用參數(shù)會因函數(shù)的調(diào)用而存在隨時被修改的危險。指針參數(shù)雖然不會因為函數(shù)的調(diào)用改變傳入實參的地址，但會因此存在指針指向的變量值被修改和指針指向內(nèi)存單元改變的可能[6]。綜上所述，指針參數(shù)在函數(shù)調(diào)用時情況最復(fù)雜，因此設(shè)定權(quán)值為2。引用參數(shù)次之，設(shè)定權(quán)值為1.5。權(quán)值參數(shù)最低，設(shè)定權(quán)值為1。式（1）表示函數(shù)的接口參數(shù)對任一分支連接的權(quán)值加權(quán)值Hc的算法，其中Nd為該連接的傳值參數(shù)個數(shù)，Na為引用參數(shù)的個數(shù)，Np為指針參數(shù)的個數(shù)。

（3）全局變量。全局變量的作用域從定義開始，到程序結(jié)束終止，其影響范圍相對較大，全局變量使得程序各模塊之間的耦合度增加，函數(shù)依賴這些全局變量。當(dāng)一個全局變量值被誤操作時，會對其它模塊造成影響。由于全局變量對源程序影響很大，測試時要特別小心，因此設(shè)定權(quán)值為3。式（2）表示函數(shù)的全局變量對任一分支連接的權(quán)值加權(quán)值Hg的算法，其中Ng為該連接的傳值參數(shù)個數(shù)。

（4）局部變量。局部變量的作用域是從變量定義開始到該單元函數(shù)結(jié)束終止。局部變量的影響區(qū)域表示了該函數(shù)對該局部變量的敏感性。當(dāng)局域變量值改變時，僅影響函數(shù)內(nèi)部作用域的語句，相對全局變量來說，其影響范圍較小，因此其權(quán)值設(shè)為1。式（3）表示函數(shù)的局部變量對任一分支連接的權(quán)值加權(quán)值Hc的算法，其中Nd為該連接的權(quán)值參數(shù)個數(shù)，Na為引用參數(shù)的個數(shù)，Np為指針參數(shù)的個數(shù)。

2.1.2 權(quán)值的數(shù)學(xué)模型

通常，控制流圖矩陣中的連接權(quán)值初始值設(shè)為1。根據(jù)以上權(quán)值影響因子對分支連接權(quán)值的影響，可以得到該連接的附加權(quán)值，最終將兩部分相加便可得到最終的權(quán)值，如公式（4）所示。其中Wij表示i結(jié)點到j(luò)結(jié)點之間的連接權(quán)值，Pij表示該連接的執(zhí)行概率。

2.2 關(guān)鍵路徑求解算法

關(guān)鍵路徑求解算法實際上是利用被測程序的AOE網(wǎng)絡(luò)鄰接矩陣G[i][j]來生成全路徑矩陣APM的過程。APM顧名思義，其每行分別代表程序可能的執(zhí)行路徑及其路徑的累加權(quán)值。矩陣的最后一列為每條路徑的權(quán)值和，其余每個元素分別代表了該路徑中的各個結(jié)點號。具體算法描述如下：

①初始化矩陣APMG，存儲每條路徑的權(quán)值累加值向量a[n]；②在鄰接矩陣G的第一行中逐一查找所有的非零元素，并在APMG中記錄相應(yīng)的列號和此行的直接后序結(jié)點數(shù)k，最后累加APMG中前k行相鄰元素間的權(quán)值，并存在a[n]中；③設(shè)i=2，m為G的行數(shù)；④若i>m，則轉(zhuǎn)至⑧，否則查找G的第i行，依次找出非零元素的列號，共計cout個；⑤查找APMG中元素最大值等于i-1的行。若查找到，則執(zhí)行步驟⑥；若查找不到，則轉(zhuǎn)至步驟⑦；⑥將找到的APMG行復(fù)制count-1個，然后依次將步驟④找到的結(jié)點列號添加到APMG中，上述找到的APMG行和復(fù)制生成的行相應(yīng)列進行更新，最后累加更新后的APMG權(quán)累加值；⑦繼續(xù)查找APMG中滿足步驟⑤條件的行。若找到，則轉(zhuǎn)至步驟⑤繼續(xù)執(zhí)行；若查找不到，則轉(zhuǎn)至步驟⑧；⑧i=i+1，返回步驟④；⑨結(jié)合APMG和a[n]生成輸出的APM矩陣，每行即為一個程序執(zhí)行路徑；B10APM中最后一列的最大元素所在行即為關(guān)鍵路徑，結(jié)束。

3 實例分析

為了驗證上述關(guān)鍵路徑覆蓋測試方法，以下面的程序為例加以分析說明，程序代碼如下：

3.1 靜態(tài)分析

對上面代碼進行靜態(tài)分析，可以得到相應(yīng)的控制流圖，如圖3所示。

同時，通過靜態(tài)分析還可得到源代碼中變量的類型以及定義使用情況，進而根據(jù)式（4）的權(quán)值數(shù)學(xué)模型計算得到圖3中相應(yīng)的連接權(quán)值，結(jié)果如表1所示。將圖3的連接賦以表1中求得的權(quán)值，即得到源代碼的AOE網(wǎng)。

根據(jù)求解關(guān)鍵路徑算法，MATLAB仿真可以得到矩陣APM，如公式（6）所示。從式（6）可以看到，矩陣的每一行即代表一條程序路徑，分別為（0，1，2，3，5，6，7，9，10）、（0，1，4，5，6，7，9，10）、（0，1，2，3，5，6，8，9，10）、（0，1，4，5，6，8，9，10），對應(yīng)的路徑權(quán)值分別為19.3、14.7、20.6、16，故得出路徑（0，1，2，3，5，6，8，9，10）的權(quán)值最大，此即為所求的關(guān)鍵路徑。

APM=012356791019.3014567910014.7012356891020.60145689100164×10（6）

3.3 基于LCSAJ關(guān)鍵路徑覆蓋測試

利用自動化測試工具Testbed對被測源代碼進行分析。首先，得到源代碼的LCSAJ表，如表2所示，LCSAJ由3個要素即3個行號（A，B，C）來確定標(biāo)識，其中A是開始行，B是結(jié)束行，C是跳轉(zhuǎn)目的行。表中的每個LCSAJ的3個行號均對應(yīng)待測源代碼中的標(biāo)識行號。

其次，Testbed還提供了各個LCSAJ的組合關(guān)系表（LCSAJ Precondition Table），結(jié)合步驟2得到的關(guān)鍵路徑（0，1，2，3，5，6，8，9，10），經(jīng)過簡單分析可以得出，關(guān)鍵路徑對應(yīng)的LCSAJ組合對應(yīng)表2中的LCSAJ編號序列（3，10，14）。

最后依照Testbed分析給出的LCSAJ內(nèi)部條件表（LCSAJ Internal Condition Table），可以迅速得出此條關(guān)鍵路徑對應(yīng)的判定條件組合為（（x>3）&&（z<10））， x≠4和*y≤5，即最終的關(guān)鍵路徑覆蓋測試用例只需滿足：Ψ={（x，y，z）|（x>3）&&（x≠4）&&（*y≤5）&&（z<10）}。經(jīng)驗證，上述測試用例在程序?qū)嶋H運行中可以完整地執(zhí)行，實現(xiàn)了該代碼關(guān)鍵路徑的最終覆蓋。

采用本文關(guān)鍵路徑覆蓋測試，在保證關(guān)鍵路徑覆蓋的同時，語句覆蓋達(dá)到71%，分支覆蓋達(dá)到50%。在此基礎(chǔ)上只需再補充1個用例即可實現(xiàn)相關(guān)軟件測試需求中的語句和分支的100%覆蓋。相比傳統(tǒng)的隨機生成用例的路徑覆蓋測試方法，本方法可以有針對性地調(diào)整測試用例的優(yōu)先級，達(dá)到在測試資源有限的情況下，優(yōu)化測試資源分配、提升測試效率的目的。

4 結(jié)語

本文針對傳統(tǒng)的路徑覆蓋方法存在工作量大不易實施的問題，提出了一種易于操作的路徑覆蓋測試方法。首先利用AOE網(wǎng)生成矩陣APM算法求出待測程序的關(guān)鍵路徑，然后利用自動化測試工具對程序進行LCSAJ分析，最終在其輔助下完成關(guān)鍵路徑覆蓋的測試。實踐證明，該方法不僅提高了關(guān)鍵路徑的求解效率，而且簡化了路徑覆蓋測試用例的設(shè)計過程，因而在實際工程中節(jié)省了測試資源，提升了測試效率。

參考文獻(xiàn)：

[1] 周濤.航天型號軟件測試[M].北京：宇航出版社，1999：83-86.

[2] 徐鳳生，黃倩.關(guān)鍵路徑求解的新算法[J].計算機應(yīng)用，2004，24（12）：108-109.

[3] 孟繁楨.求關(guān)鍵路徑的一個算法[J].計算機工程，2001，21（4）：6-9.

[4] 周元哲，張慶生，王偉偉，等.軟件測試案例教程[M].北京：機械工業(yè)出版社，2013：87-88.

[5] LDRA.C_C++ LDRA testbed technical description[EB/OL].2000.http：//wenku.baidu.com/link？url=lF Mx3z1sT Wi3qTB hS7QQlQ QWZTL SYDxgE ppb 5fIO8-yS0y-gZ WEtU3E SySwxC gG4kYVghE vgy2h MHQUdl8 x6V4k2uH_8 32m2 UW6 NA5 bzTZe.

[6] 高峰，鄭純，劉廠.基于優(yōu)先級的單元測試技術(shù)應(yīng)用研究[J].應(yīng)用科技，2010，37（7）：30-32.

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