杜慶峰，張秋華

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義2 變量依賴

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

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

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

定義3 有效路徑集

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

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

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

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

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

2.1 算法思想

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

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

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

具體算法邏輯如下：

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

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

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

不難看出，該公式是一個(gè)遞歸公式，遞歸過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

圖6 條件語(yǔ)句Fig.6 Conditional statement

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

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

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

圖8 Switch（case）語(yǔ)句Fig.8 Switch（case）sentence

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

2.2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

3 算法驗(yàn)證

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

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

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

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

依據(jù)變量依賴的定義，節(jié)點(diǎn)4變量依賴于節(jié)點(diǎn)3，在路徑P1中，節(jié)點(diǎn)3和節(jié)點(diǎn)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é)點(diǎn)10的直接前置節(jié)點(diǎn)中選節(jié)點(diǎn)6得到路徑1→2→4→5→6→10→12.

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

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

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

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

4 結(jié)論

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

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

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

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

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

［1］杜慶峰.高級(jí)軟件測(cè)試技術(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］李慧賢，劉堅(jiān).過(guò)程內(nèi)控制依賴的計(jì)算［J］.計(jì)算機(jī)工程與應(yīng)用，2003（2）：78.LI Huixian，LIU Jian.Computation of intraprocedural control dependence［J］.Software Engineering Institute，2003（2）：78.

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