杜慶峰，張秋華

（同濟(jì)大學(xué) 軟件學(xué)院，上海 201804）

軟件測試按照類別一般可劃分為黑盒測試（功能性測試）、白盒測試（結(jié)構(gòu)性測試）和非功能性測試.白盒測試主要用于組件（單元）級別的測試，其邏輯覆蓋主要有語句覆蓋、判定覆蓋、條件覆蓋、判定-條件覆蓋、條件組合覆蓋及組件基路徑覆蓋［1］.其中，組件基路徑覆蓋測試是一種重要的路徑覆蓋測試技術(shù)，由于其在測試用例設(shè)計時會出現(xiàn)業(yè)務(wù)邏輯不合理的無效路徑問題，故人工干預(yù)多、測試效率低［1-2］.

由于組件基路徑覆蓋測試的思想是以圖論及向量空間等為依據(jù)，得出的獨立路徑集合中的路徑?jīng)]有考慮其業(yè)務(wù)邏輯的合理存在，因此在大多數(shù)情況下會出現(xiàn)部分路徑從圖論和幾何學(xué)的角度去分析是存在的，但這些路徑所對應(yīng)的業(yè)務(wù)邏輯是不可行的，即路徑是無效的，其結(jié)果導(dǎo)致這些路徑對應(yīng)的測試用例是不可執(zhí)行的［1-2］.這里列舉一個簡單的判定三角形類型程序組件［3-4］（以C語言實現(xiàn)，與用Java等面向?qū)ο笳Z言實現(xiàn)情況類似）來說明路徑從圖論和幾何學(xué)的角度去分析是存在的，但該路徑不具有業(yè)務(wù)邏輯的合理性.圖1為組件程序圖.

圖1 判定三角形類型程序Fig.1 Triangle judgment procedure

圖1左邊部分是程序的節(jié)點劃分情況，這里將順序執(zhí)行的且不會引起程序控制轉(zhuǎn)移的語句整合在一個節(jié)點中，并不影響后面對問題的分析.對應(yīng)的組件程序圖［1］如圖2所示.

圖2 判定三角形形狀的組件程序圖Fig.2 Component program graph of triangle judgment procedure

基路徑覆蓋測試的獨立路徑集合不唯一，圖1獨立路徑中包含路徑：1→3→4→5→7→8→10→12，從圖2可以看出這條路徑是存在的，但是該路徑所對應(yīng)的業(yè)務(wù)邏輯是不合理的，因為節(jié)點3對應(yīng)的語句是判定為非三角形的結(jié)果，所以從業(yè)務(wù)邏輯上不可能再經(jīng)過5→7→8→10→12節(jié)點，故路徑1→3→4→5→7→8→10→12是業(yè)務(wù)邏輯上不合理的無效路徑，其對應(yīng)的測試用例是不可執(zhí)行的.這樣的路徑在這個例子中不止一條，這里僅說明問題的存在，不一一分析.

1982年，McCabe將圖論、向量空間理論引入路徑測試領(lǐng)域［2］，提出了強(qiáng)連通的圈復(fù)雜度，即線性獨立環(huán)路數(shù)量的相關(guān)概念，將被測單元組件轉(zhuǎn)換為程序圖，進(jìn)而提出了一種基路徑算法.該算法得出的獨立路徑集合沒有考慮路徑和業(yè)務(wù)邏輯的結(jié)合，也沒有考慮路徑中變量依賴.McCabe也意識到會出現(xiàn)無效路徑，并給出了以無效路徑為對象用人工干預(yù)的方法使其轉(zhuǎn)化為另一條獨立的業(yè)務(wù)邏輯合理的其他路徑，但這種方法可操作性差，尤其對于比較復(fù)雜或復(fù)雜的單元組件.

1993年，Nakajo等［3］提出了組件基路徑覆蓋測試的路徑中變量的定義-使用鏈（define-use chains）概念，研究了路徑中變量定義和使用的關(guān)系，但沒能提出一種具體的方法或模型來解決基路徑中的無效路徑問題.2008年，Yan等［4］提出了一種程序中變量約束限制和交互的基路徑覆蓋測試思想.這種方法是基于C語言的，是在McCabe方法基礎(chǔ)上的改進(jìn)，但也沒能有效解決基路徑中的無效路徑問題.2009年，Yates等［5］提出了JJ- Paths模型，通過分析JJPaths及其路徑序列來分析程序組件中語句和分支的合理性，繞過無效路徑問題，其目的是變相達(dá)到合理的基路徑覆蓋，但仍有待于進(jìn)一步研究并驗證.2010年，Zolotov等［6］提出了一種基于路徑的高速結(jié)構(gòu)測試模型，該模型提出了統(tǒng)計路徑跟蹤，為基路徑測試中的路徑相關(guān)性度量提供了依據(jù)，如能夠反映基路徑中無效路徑可能的占比關(guān)系等，為解決無效路徑問題提供幫助，但未能對基路徑集合中出現(xiàn)的無效路徑提出根本的處理策略.2011年，筆者首次提出通過將路徑業(yè)務(wù)邏輯與組件程序圖結(jié)合構(gòu)建優(yōu)化程序圖的思想，為解決無效路徑問題提出了一種新思路［7］.

綜合以上分析，目前基路徑覆蓋測試技術(shù)的獨立路徑集合中存在無效路徑問題，即路徑在業(yè)務(wù)邏輯上不可行的瓶頸仍沒有得到解決，這直接導(dǎo)致基路徑覆蓋測試技術(shù)使用過程中人工干預(yù)多、效率低.本文在分析基路徑覆蓋測試技術(shù)和邏輯覆蓋測試技術(shù)的基礎(chǔ)上，將兩者結(jié)合提出了組件基路徑覆蓋測試有效路徑集生成模型，解決了組件基路徑覆蓋測試中存在的不足和瓶頸.該模型生成的獨立路徑集合中避免了出現(xiàn)從圖論及集合學(xué)方面理解存在的路徑，但這些路徑不符合業(yè)務(wù)邏輯的情況，進(jìn)而解決了無效路徑問題.這樣得出的路徑集不但滿足基路徑覆蓋測試的原理和思想，同時路徑集合中的所有路徑均具有業(yè)務(wù)邏輯的合理性.

1 算法相關(guān)定義

結(jié)合被測程序的程序圖和業(yè)務(wù)邏輯，為了便于本文第3節(jié)中算法的分析，在此對算法涉及到的相關(guān)概念進(jìn)行了定義.

定義1 非關(guān)聯(lián)路徑

在被測程序?qū)?yīng)的程序圖中，如果存在一些路徑且這些路徑與被測程序的業(yè)務(wù)邏輯沒有直接關(guān)聯(lián)，則稱之為非關(guān)聯(lián)路徑.下面以例子加以說明.

在一個給500個員工代發(fā)工資組件的單元系統(tǒng)中，根據(jù)一個工資單文件（fileA）中的工資金額來給系統(tǒng)中的用戶發(fā)工資，其偽代碼和節(jié)點劃分及程序圖［1］分別如圖3和4所示.

該組件程序中的非關(guān)聯(lián)路徑為1→2→3→4→7，即當(dāng)打開或者讀取文件失?。ㄈ鏵ileA不存在或者格式錯誤等）的路徑，該路徑與發(fā)工資具體的業(yè)務(wù)邏輯沒有關(guān)系.

定義2 變量依賴

在被測程序?qū)?yīng)的程序圖中，如果存在節(jié)點Ni與節(jié)點Nm，從節(jié)點Ni到節(jié)點Nm存在路徑P，且在節(jié)點Ni處對特定變量V進(jìn)行定義并初始化賦值，則存在以下兩種情況：

（1）如果在節(jié)點Nm處引用變量V并且在路徑P的其他節(jié)點處沒有對V進(jìn)行重新定義或賦值，那么節(jié)點Nm變量依賴于節(jié)點Ni.

（2）如果在節(jié)點Nm處對V進(jìn)行重新賦值或計算，從而改變V的值，那么節(jié)點Nm變量也依賴于節(jié)點Ni，且Nm與Ni關(guān)于變量V相互依賴.

定義3 有效路徑集

如果被測程序?qū)?yīng)的程序圖中存在一組路徑集合P＝｛P1，P2，…，Pm｝，當(dāng)且僅當(dāng)集合中的路徑同時滿足下面三個條件時，則稱路徑集合P是程序圖的有效路徑集.

（1）P 中的每一條路徑｛P1，P2，…，Pm｝都是可執(zhí)行的.

（2）P 中的每一條路徑｛P1，P2，…，Pm｝分別代表不同的業(yè)務(wù)邏輯（線性無關(guān)性）.

（3）P中的所有路徑覆蓋了基本的業(yè)務(wù)邏輯.

2 有效路徑集算法思想及邏輯實現(xiàn)

2.1 算法思想

本算法是基于組件級別的測試算法，其核心思想主要分為兩部分：

第一步，對McCabe覆蓋中產(chǎn)生不可執(zhí)行路徑的那些路徑和節(jié)點進(jìn)行處理，使不可執(zhí)行路徑不會出現(xiàn)在有效路徑集里［8-9］.通過定義非關(guān)聯(lián)路徑，將導(dǎo)致出現(xiàn)不可執(zhí)行路徑的節(jié)點通過變量依賴隔離出來，并在非關(guān)聯(lián)路徑找出之后，將有變量依賴關(guān)系且入度和出度均為1的節(jié)點從程序圖中刪除，這樣在第二步中就不會出現(xiàn)不可執(zhí)行路徑.具體算法邏輯將在下面的算法邏輯步驟2中作詳細(xì)說明.

第二步，采用自底向上遍歷程序圖的方法，從匯節(jié)點［1］出發(fā)尋找有效路徑.這種從結(jié)果出發(fā)逐步向上遍歷程序圖的各種分支和判定結(jié)構(gòu)的方法，既保證了基路徑覆蓋又保證了程序邏輯覆蓋的完整性.具體算法邏輯將在下面算法邏輯步驟3中作詳細(xì)說明.

具體算法邏輯如下：

步驟1 依據(jù)被測程序，畫出程序圖.

步驟2 找出程序圖中的非關(guān)聯(lián)路徑，將其中入度和出度均為1的節(jié)點從程序圖中隔離并刪除（源節(jié)點和匯接點除外），保留重復(fù)的節(jié)點，得到優(yōu)化后的程序圖.

步驟3 在優(yōu)化后的程序圖中，運(yùn)用公式VE＝-C）＋D計算有效路徑集元素的個數(shù)并找出有效路徑.其中，VE是有效路徑集的元素的個數(shù)；Ii是從匯節(jié)點向上遍歷的第一個入度不小于2的節(jié)點的入度；C＝Count（Ii-1＞2），是i節(jié)點的直接前置節(jié)點中入度不小于2的節(jié)點的個數(shù)；D是非關(guān)聯(lián)路徑的個數(shù)；m是從匯節(jié)點開始向上遍歷到某個節(jié)點時遍歷器的計數(shù).該節(jié)點同時滿足以下兩個條件：①該節(jié)點是前面某一個入度不小于2的節(jié)點的一個直接前置節(jié)點；② 該節(jié)點的所有直接前置節(jié)點入度小于2.

不難看出，該公式是一個遞歸公式，遞歸過程如下：

在程序圖中，從匯節(jié)點開始向上遍歷找到第一個入度不小于2的節(jié)點i，其入度記為Ii，需要注意的是，對于存在循環(huán)的時候，忽略進(jìn)入循環(huán)的那個節(jié)點.

從節(jié)點i開始向上遍歷，設(shè)節(jié)點i的直接前置節(jié)點中入度不小于2的節(jié)點個數(shù)為C，則節(jié)點i處得到的有效路徑個數(shù)為（Ii-C）.用同樣的方法計算節(jié)點i的每一個直接前置節(jié)點處的有效路徑個數(shù)，并不斷向上遍歷.

遞歸結(jié)束條件：通過上面的遞歸遍歷到的某個入度大于或者等于2的節(jié)點，其所有直接前置節(jié)點的入度都小于2，則遍歷結(jié)束.

遍歷結(jié)束后，將得到的所有（Ii-C）相加，再加上非關(guān)聯(lián)路徑數(shù)目就可以得出總的有效路徑的個數(shù).

步驟4 依據(jù)步驟3得出的有效路徑集的路徑個數(shù)，在優(yōu)化后的程序圖中取路徑.采用自底向上的方法，從匯節(jié)點出發(fā)，找到第一個入度不小于2的節(jié)點，然后沿著它的各個直接前置節(jié)點分別取一次，對于它的直接節(jié)點如果入度也不小于2，則按照同樣的方法取節(jié)點，直到取盡各種情況.

用以上計算方法得到有效路徑集中的路徑個數(shù)和具體路徑，需要考慮程序內(nèi)部各種語句結(jié)構(gòu).各種常見程序的基本語句結(jié)構(gòu)有：順序執(zhí)行的語句、條件語句（if語句）、循環(huán)語句（for語句、while語句）、選擇語句（switch（case）語句）等.

下面就算法中可能出現(xiàn)的各種語句結(jié)構(gòu)［10］進(jìn)行舉例說明并就有效路徑的計算進(jìn)行分析.

（1）對于順序執(zhí)行語句，有效路徑個數(shù)VE＝1，如圖5所示.

圖5 順序執(zhí)行的語句Fig.5 Sequential statement

（2）對于包含If條件語句的情況，如圖6所示，VE＝4-0＝4.

圖6 條件語句Fig.6 Conditional statement

（3）對于包含循環(huán)語句的情況，如圖7所示，VE＝2.

圖7 循環(huán)語句Fig.7 Loop statement

（4）對于包含Switch（case）語句的情況，如圖8所示，VE＝n＋1.

圖8 Switch（case）語句Fig.8 Switch（case）sentence

如果在程序圖中出現(xiàn)同時包含（1）～（4）情況的復(fù)合結(jié)構(gòu)，進(jìn)行綜合處理即可，算法同樣適用.

2.2 算法實現(xiàn)

由于本算法是研究基于組件級別的測試算法，一般情況下單個組件程序圖中劃分的節(jié)點數(shù)是有限的.對于程序圖G＝（V，E），其中V是程序圖中節(jié)點的集合，E是邊（節(jié)點關(guān)系）的集合.那么，E可以通過定義一個n×n的鄰接矩陣R（其中n是節(jié)點的個數(shù)），當(dāng)節(jié)點j是節(jié)點i的直接后繼節(jié)點時，令R［i］［j］＝1，否則令它為0.由于程序圖是個有向圖，所以鄰接矩陣中第i行非零元素的個數(shù)為節(jié)點i的出度，第i列非零元素的個數(shù)為節(jié)點i的入度.當(dāng)n特別大時，為了節(jié)省存儲空間，可以通過鄰接表的方式來實現(xiàn)，即：定義n個長度為n的向量（vector），每個向量里面的內(nèi)容是該節(jié)點所能指向的節(jié)點的集合（即存儲的是該節(jié)點的直接后繼節(jié)點）.兩種實現(xiàn)方法不影響算法的分析，下面就以鄰接矩陣的方式對該算法的兩個關(guān)鍵步驟的實現(xiàn)進(jìn)行詳細(xì)的說明.

第一步 生成優(yōu)化后的程序圖子算法.依據(jù)變量依賴和非關(guān)聯(lián)路徑隔離并刪除導(dǎo)致產(chǎn)生不可執(zhí)行路徑的非重復(fù)的節(jié)點和邊，這里的非重復(fù)可以理解為節(jié)點入度和出度均為1的情況.得出優(yōu)化后的程序圖的子算法（偽代碼）如圖9所示.

圖9 生成優(yōu)化后的程序圖的子算法Fig.9 Sub-algorithm of program graph optimization

第二步 生成有效路徑集子算法.依據(jù)優(yōu)化后的程序圖，采用遍歷分別取各種分支的情況來生成有效路徑集.需要注意的是，由于生成路徑時，采用的是自底向上的遍歷法，所以可以先將原來表示節(jié)點關(guān)系的鄰接矩陣進(jìn)行轉(zhuǎn)置，這樣就可以通過轉(zhuǎn)置后的矩陣采用自底向上遍歷法來獲取路徑.

該子算法的具體實現(xiàn)（偽代碼）如圖10所示.

圖10 生成有效路徑集的子算法Fig.10 Sub-algorithm of effective-path set generation

2.3 算法復(fù)雜度分析

（1）時間復(fù)雜度

假設(shè)程序圖中節(jié)點數(shù)為n，根據(jù)第2.2中的算法實現(xiàn)步驟，第一步中初始化節(jié)點信息的時間復(fù)雜度為O（n），遍歷一維數(shù)組找出變量依賴關(guān)系的時間復(fù)雜度也為O（n）.二維數(shù)組初始化并檢查節(jié)點是否有直接相鄰關(guān)系的時間復(fù)雜度是O（n2），遍歷并刪除非關(guān)聯(lián)路徑中的非重復(fù)節(jié)點需要的時間復(fù)雜度是O（n）.所以第一步的總時間復(fù)雜度是3O（n）＋O（n2）≈O（n2）.第二步中找出前置節(jié)點集合的時間復(fù)雜度為O（n），將二維數(shù)組構(gòu)成的矩陣轉(zhuǎn)置時需要的時間復(fù)雜度是O（n2），自底向上遍歷找出有效路徑時的時間復(fù)雜度是O（n），所以第二步中總的時間復(fù)雜度是O（n2）＋2O（n）≈O（n2）.因此整個算法的最大時間復(fù)雜度是O（n2）.

（2）空間復(fù)雜度

同樣假設(shè)程序圖中節(jié)點數(shù)為n，則創(chuàng)建節(jié)點的一維數(shù)組空間復(fù)雜度是O（n），鄰接矩陣的二維數(shù)組空間復(fù)雜度是O（n2），存儲節(jié)點變量依賴關(guān)系的一維數(shù)組空間復(fù)雜度為O（n），自底向上生成有效路徑集時對鄰接矩陣進(jìn)行轉(zhuǎn)置保存其副本的空間復(fù)雜度為O（n2）.所以總的空間復(fù)雜度是：O（n）＋O（n2）＋O（n）＋O（n2）≈O（n2）.

3 算法驗證

根據(jù)第2.2節(jié)算法實現(xiàn)可知，本算法可以通過程序自動實現(xiàn)，這里不再贅述，僅以一個具體的組件例子對算法邏輯進(jìn)行驗證.

組件需求描述：判定三角形類型，根據(jù)用戶輸入的三個邊數(shù)據(jù)，輸出三角形的類型.若三個邊數(shù)據(jù)不滿足構(gòu)成三角形的條件（兩邊之和大于第三邊）則輸出“非三角形”，反之輸出其具體的三角形類型（普通三角形、等腰三角形、等邊三角形），其具體的程序及程序見圖1和2.

（1）根據(jù)組件程序畫出程序圖（見圖2）.

（2）依據(jù)組件需求描述中的業(yè)務(wù)邏輯，在程序圖中找出非關(guān)聯(lián)路徑，將其路徑從程序圖中隔離并刪除，保留重復(fù)的節(jié)點和循環(huán)中的路徑，得到優(yōu)化后的程序圖.故可以得到一條非關(guān)聯(lián)路徑，即為三角形類型判定失敗的業(yè)務(wù)邏輯：P1.因條件語句在節(jié)點4判定失敗未能進(jìn)入具體類型判定的路徑為1→3→4→11→12.

依據(jù)變量依賴的定義，節(jié)點4變量依賴于節(jié)點3，在路徑P1中，節(jié)點3和節(jié)點11的入度和出度均為1，故可以從程序圖中去掉.由此得到優(yōu)化后的程序圖如圖11.

圖11 三角形類型判定組件優(yōu)化后的程序圖Fig.11 Program graph of triangle judgment procedure after optimization

即除了非關(guān)聯(lián)路徑外余下的有效路徑有三條，結(jié)合圖11，得到余下的有效路徑分別如下：

P2：在節(jié)點10的直接前置節(jié)點中選節(jié)點6得到路徑1→2→4→5→6→10→12.

P3：在節(jié)點10的直接前置節(jié)點中選節(jié)點8得到路徑1→2→4→5→7→8→10→12.

P4：在節(jié)點10的直接前置節(jié)點中選節(jié)點9得到路徑1→2→4→5→7→9→10→12.

（4）依據(jù)算法得到以上四條路徑，經(jīng)過分析可以知道這四條路徑都是可執(zhí)行的，所以這四條路徑構(gòu)成一個有效的測試路徑集.

依據(jù)本算法可得到有效路徑集并轉(zhuǎn)換為相應(yīng)的測試用例，可以發(fā)現(xiàn)四個測試用例代表的業(yè)務(wù)邏輯分別是：輸入的三個數(shù)據(jù)無法構(gòu)成三角形、能構(gòu)成等腰三角形、能構(gòu)成等邊三角形、只能構(gòu)成普通三角形四種情形.由此可見，本算法得出的測試用例不僅滿足McCabe基路徑覆蓋（線性無關(guān)），且得出的有效路徑集合中的路徑都是可執(zhí)行的，同時最大限度滿足了業(yè)務(wù)邏輯覆蓋.

4 結(jié)論

（1）將業(yè)務(wù)邏輯與基路徑相結(jié)合進(jìn)行基路徑分析，這樣就保證了得到的測試用例是可執(zhí)行的且符合業(yè)務(wù)邏輯的.

（2）采用自底向上遍歷程序圖的方法，從匯節(jié)點出發(fā)遍歷并分別取各種分支情況，在遍歷過程中將白盒測試中邏輯覆蓋的思想融合在其中，在最大程度上保證了測試用例符合基路徑覆蓋和基本的業(yè)務(wù)邏輯.

（3）算法時間復(fù)雜度比較低，為O（n2）.

（4）算法得出的有效路徑集轉(zhuǎn)化為相應(yīng)的測試用例時，由于有效路徑集中的路徑是相互獨立的，所以相應(yīng)的業(yè)務(wù)邏輯也不會相互重復(fù)，避免了測試用例的冗余.

（5）根據(jù)本算法的推導(dǎo)和分析過程可知，該算法也同樣適用于組件間的集成測試和系統(tǒng)測試，可以理解為，在集成測試中節(jié)點可以對應(yīng)于單個組件，在系統(tǒng)測試中節(jié)點可以對應(yīng)于子系統(tǒng)，故算法具有良好的可擴(kuò)展性和應(yīng)用前景.

［1］杜慶峰.高級軟件測試技術(shù)［M］.北京：清華大學(xué)出版社，2011.DU Qingfeng.Senior software engineering［M］.Beijing：Tsinghua University Press，2011.

［2］Jorgensen P C.Software testing—a craftman’s approach［M］.Boca Raton：CRC Press LLC，1995.

［3］Nakajo T，Yamaguchi I，Kume H.A test-path determination method based on define-use chains：test conditions and program fault overlooks［J］.Systems and Computers in Japan，1993，24（5）：14.

［4］YAN Jun，ZHANG Jian.An efficient method to generate feasible paths for basis path testing［J］.Information Processing Letters，2008，107（3-4）：87.

［5］Yates D F，Malevris N.Inclusion，subsumption，JJ-paths，and structured path testing：a redress［J］.Software Testing，Verification and Reliability，2009，19（3）：199.

［6］Zolotov V，XIONG Jinjun，F(xiàn)atemi H.Statistical path selection for at-speed test［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2010，29（5）：749.

［7］DU Qingfeng，DONG Xiao.An improved algorithm for basis path testing［C］∥2011 International Conference on Business Management and Electronic Information， BMEI 2011.Piscataway：IEEE，2011：175-178.

［8］ZHANG Zhonglin， MEI Lingxia.An improved method of acquiring basis path for software testing［C］∥5th International Conference on Computer Science and Education，ICCSE 2010.Piscataway：IEEE Computer Society，2010：1891-1894.

［9］李慧賢，劉堅.過程內(nèi)控制依賴的計算［J］.計算機(jī)工程與應(yīng)用，2003（2）：78.LI Huixian，LIU Jian.Computation of intraprocedural control dependence［J］.Software Engineering Institute，2003（2）：78.

［10］杜慶峰，李娜.白盒測試基路徑算法［J］.計算機(jī)工程，2009，35（15）：100.DU Qingfeng，LI Na.Basis paths algorithm of white-box testing［J］.Computer Engineering，2009，35（15）：100.