職曉+張江華

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

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

中圖分類號(hào)：TP306

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

0 引言

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

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

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

1 基本概念

1.1 關(guān)鍵路徑

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)例分析

為了驗(yàn)證上述關(guān)鍵路徑覆蓋測(cè)試方法，以下面的程序?yàn)槔右苑治稣f明，程序代碼如下：

3.1 靜態(tài)分析

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

同時(shí)，通過靜態(tài)分析還可得到源代碼中變量的類型以及定義使用情況，進(jìn)而根據(jù)式（4）的權(quán)值數(shù)學(xué)模型計(jì)算得到圖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），對(duì)應(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)鍵路徑覆蓋測(cè)試

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 周濤.航天型號(hào)軟件測(cè)試[M].北京：宇航出版社，1999：83-86.

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

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

[4] 周元哲，張慶生，王偉偉，等.軟件測(cè)試案例教程[M].北京：機(jī)械工業(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)先級(jí)的單元測(cè)試技術(shù)應(yīng)用研究[J].應(yīng)用科技，2010，37（7）：30-32.

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