基路徑與業(yè)務邏輯結合的有效測試路徑集算法

杜慶峰，張秋華

（同濟大學 軟件學院，上海 201804）

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

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

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

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

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

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

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

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

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

1 算法相關定義

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

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

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

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

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

定義2 變量依賴

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

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

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

定義3 有效路徑集

如果被測程序對應的程序圖中存在一組路徑集合P＝｛P1，P2，…，Pm｝，當且僅當集合中的路徑同時滿足下面三個條件時，則稱路徑集合P是程序圖的有效路徑集.

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

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

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

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

2.1 算法思想

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

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

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

具體算法邏輯如下：

步驟1 依據被測程序，畫出程序圖.

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

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

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

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

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

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

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

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

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

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

（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）情況的復合結構，進行綜合處理即可，算法同樣適用.

2.2 算法實現(xiàn)

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

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

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

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

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

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

2.3 算法復雜度分析

（1）時間復雜度

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

（2）空間復雜度

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

3 算法驗證

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

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

（1）根據組件程序畫出程序圖（見圖2）.

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

依據變量依賴的定義，節(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

即除了非關聯(lián)路徑外余下的有效路徑有三條，結合圖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）依據算法得到以上四條路徑，經過分析可以知道這四條路徑都是可執(zhí)行的，所以這四條路徑構成一個有效的測試路徑集.

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

4 結論

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

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

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

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

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

［1］杜慶峰.高級軟件測試技術［M］.北京：清華大學出版社，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］李慧賢，劉堅.過程內控制依賴的計算［J］.計算機工程與應用，2003（2）：78.LI Huixian，LIU Jian.Computation of intraprocedural control dependence［J］.Software Engineering Institute，2003（2）：78.

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