劉秀青 杜軍威 李彥霖

（青島科技大學信息科學技術學院 青島 266061）

1 引言

基于圖論的軟件行為分析是常用測試分析方法［1］，不同層面的軟件行為可以抽象建模為各類圖［2］，如控制流圖、數(shù)據(jù)流圖、系統(tǒng)調用圖、用例圖、活動圖等，因而軟件行為分析都可以抽象為基于圖結構特征的分析［2～3］，如每個瞬間軟件行為可以表現(xiàn)為狀態(tài)空間的某些狀態(tài)組合、軟件每次執(zhí)行可以抽象為圖的一個路徑等。但每個狀態(tài)和變遷的正確性并不能表示其系統(tǒng)行為的正確，在一些安全關鍵系統(tǒng)或信息安全系統(tǒng)的行為分析中，每個狀態(tài)或變遷［4］安全并不能表示系統(tǒng)行為的安全性，如列車控制系統(tǒng)中未通過安全狀態(tài)檢測的移動授權行為；并發(fā)系統(tǒng)中時序交替行為約束等。考慮到圖的結構特征，基于圖的分析可以表現(xiàn)為基于圖的不同結構覆蓋的分析［1～3］，如：點覆蓋、邊覆蓋、邊對覆蓋和指定路徑覆蓋分別考慮圖的不同結構特征，而產生覆蓋這些結構的測試路徑則可以檢測狀態(tài)空間的任意狀態(tài)、任意變遷，任意連續(xù)變遷對、及包含某個特征行為的行為分析與檢測。因此，軟件行為分析可以抽象為基于圖論特征覆蓋［2～3］的測試路徑生成問題，同時測試路徑生成需要考慮一定的代價［5～6］和覆蓋特征。

由于存在環(huán)路，基于圖的全路徑分析難以實際實現(xiàn)。目前基于圖的路徑分析主要包含基本路徑分析技術［1］，指定次數(shù)的環(huán)路覆蓋分析技術［7］，Prime路徑分析技術［2，9］等。McCabe最早提出圖的基本路徑的含義［1］，雖然基本路徑的組合可以表達任意路徑，但這并不能證明基本路徑行為正確則任意路徑行為是正確的，且無法檢測環(huán)路中連續(xù)變遷關聯(lián)引發(fā)的行為缺陷問題。其實基本路徑更關心每次判定節(jié)點改變對系統(tǒng)的某條路徑的影響，而無法更多的檢測關聯(lián)路徑。Paul提出基于Prime路徑覆蓋技術［2］可以測試非環(huán)路的連續(xù)變遷覆蓋的測試問題，由于缺乏對測試路徑的質量的評價標準，覆蓋Prime路徑的測試路徑生成則忽視路徑獨立性影響問題。Li Nan提出了最小代價測試路徑問題［5～6］（MCTP），以節(jié)點更少，測試路徑更少，每條測試路徑覆蓋的測試需求更少，測試路徑更短為覆蓋目標進行測試路徑生成，然這些目標本身是相互矛盾的，在路徑數(shù)目、路徑長度、路徑覆蓋比等因素制約下難以生成可行路徑或存在組合路徑龐大等問題。本文提出一種兼顧路徑獨立性與Prime路徑覆蓋的測試路徑生成方法，既考慮路徑獨立性組合問題又考慮連續(xù)變遷覆蓋問題，在保證覆蓋充分性的同時，使得測試路徑數(shù)和總測試路徑長度在可測性前題下保持在合理的范圍，從而保證測試覆蓋度的前提下測試路徑優(yōu)化。

2 基于圖結構覆蓋的測試基本理論

基于圖結構特征的測試問題主要包括如下步驟：選擇一種測試覆蓋性準則，生成滿足符合測試準則的測試需求，進一步生成滿足覆蓋需求的測試路徑，產生驅動測試路徑執(zhí)行的測試數(shù)據(jù)［8］。面向點、邊、邊對、路徑等測試覆蓋準則產生的每一條測試路徑都是系統(tǒng)的一次執(zhí)行，而系統(tǒng)的執(zhí)行需要有測試數(shù)據(jù)驅動，本文考慮結構覆蓋分析的測試路徑生成，忽略驅動測試路徑執(zhí)行的測試數(shù)據(jù)，從而能夠從結構本質進行行為分析，本文主要包含的基本理論如下：

定義 1 路徑［8～9］的相關定義：圖 G=(V，E，Vs，Ve)，其中V是所有節(jié)點的集合，E是所有邊的集合E={(vi，vj)|vi，vj∈ V}，Vs為圖的始點集合，Ve為圖的終點集合。該圖的路徑表示節(jié)點或邊的序列，表示為 p=v1v2…vm，其中vi∈V ，(vi，vi+1)∈E(1≤i≤m)。定義Node（p）為路徑p的節(jié)點集合，Edge（p）為路徑p的所有邊的集合，SubPath（p）為p的子路徑集合；定義Path（G）為圖G產生的所有路徑。

定義2 路徑的獨立性：基于圖G=(V，E，Vs，Ve)的一個路徑集合 P={p1，p2，…，pm}，如果同時滿足如下兩條，則該路徑集合的路徑是滿足獨立性：

即，如果一個路徑集合中的路徑都不是該集合的其他路徑的線性組合，且圖中的任意一條路徑是該組路徑集合的線性組合，則該組路徑滿足獨立性。

定義3 基本路徑：目前文獻中還沒有基本路徑的形式化定義，一般給出的非形式化的定義是：每次產生的基本路徑應該包含不同于已存基本路徑的一條新邊［1］。

引理1 基本路徑集合是滿足路徑獨立性的［1］。

基本路徑集合應是不能夠相互表達，但可以表達為任意路徑的線性組合?；韭窂蕉攘亢蜕伤惴ū容^著名的是McCabe提出的圈復雜度計量法［7］，即圖的基本路徑數(shù)量等于圖的圈復雜度數(shù)。給定一圖G，圈復雜度V（G）有三種計算公式：1）V（G）=e-n+2p（e代表圖的邊數(shù)，n是圖的節(jié)點數(shù)，p為圖中的連通數(shù)），2）V（G）=P+1（其中P為判斷節(jié)點的個數(shù)，如果圖為控制流圖），3）V（G）= 封閉區(qū)域數(shù)（圖的內、外封閉區(qū)域）。然而，基本路徑的定義并沒有約定生成算法，如果僅從每次生成的路徑包含新邊的角度，并不能證明生成的路徑集合是基本路徑。如圖1所示，生成的路徑集合 P={v0，v1，v3，v4，v6;v0，v2，v3，v5，v6}，因不存在新的邊的路徑，但該路徑的數(shù)目為2并不等于圈復雜度數(shù)3。僅僅這兩條測試路徑并不能測試所有的判定條件組合，不能滿足所有的測試需求?；韭窂皆谏傻倪^程中遵循每次只更改路徑中的一個判定節(jié)點的原則，能夠包含所有的獨立路徑，較大限度地做到充分測試的同時避免了不必要的冗余。

圖1 單輸入單輸出圖

引理2 在基本路徑生成過程中，一條新路徑是基本路徑，當且僅當其包含的一個判定節(jié)點產生新的一次判定取值且不存在其包含的判定節(jié)點產生超過2次新的取值。

證明：生成的一條新路徑中，產生一個新的判定取值，則一定產生一條新邊，滿足定義4的基本路徑定義，同時不會產生某個判定的新的兩次以上取值，則能夠表現(xiàn)每個判定節(jié)點的獨立性影響作用。該引理不僅能夠說明基本路徑的本質含義，同時也給基本路徑生成算法提供支持。

按照引理2，圖1產生的基本路徑集合為P={v0， v1， v3， v4， v6;v0， v2， v3， v5， v6;v0， v2， v3， v5， v6} 。

定義 4 Prime路徑：圖 G=(V，E，Vs，Ve)的一條路徑 p=v1，v2，…，vm，如果 1＜i≠j＜m ，vi≠vj，則稱為 p 為簡單路徑［2，10］，如果不存在簡單路徑 q ，使 p∈SubPath(q)，p為Prime路徑。即簡單路徑就是一條僅可能存在開始節(jié)點和終止節(jié)點相同外，沒有任何節(jié)點出現(xiàn)超過一次，也就是說簡單路徑?jīng)]有內部環(huán)。Prime路徑是最長的簡單路徑，它不會為其它簡單路徑的子路徑。

定義 5 測試路徑［2］：給定圖 G=(V，E，Vs，Ve)的測試需求集合TR，任意tr∈TR，存在一條路徑p=v1，v2，…，vm， v1∈Vs， ∧vm∈Vs，tr∈SubPath(p)。即測試路徑是從某個起始節(jié)點開始，終止于某個結束節(jié)點的一條路徑，路徑長度允許為0。測試路徑代表了測試用例的執(zhí)行軌跡，一些測試路徑可以被很多測試數(shù)據(jù)執(zhí)行，也可能是語義不可達的路徑，而無法存在測試數(shù)據(jù)執(zhí)行。

3 一種覆蓋行為獨立性的Prime測試路徑生成技術

目前存在的面向節(jié)點、邊、邊對、Prime路徑等覆蓋的測試路徑生成技術，或考慮以較少的代價將測試需求目標覆蓋，或考慮測試路徑的可行性問題，較少考慮測試路徑之間與其分布的合理性。

基于Prime路徑的測試路徑生成技術目前常用兩種方法，其一采用將Prime路徑之間的鏈接關系轉換為一種流圖網(wǎng)絡（Flow network）［10］，通過求面向流圖節(jié)點覆蓋路徑生成技術產生覆蓋Prime路徑的測試路徑生成技術；其二采用超串（Superstring）生成技術［5，6，9］，采用啟發(fā)式算法逐層合并 Prime路徑，最后形成覆蓋Prime路徑的測試路徑。上述兩種方法可以生成面向Prime路徑覆蓋的測試路徑，同時也可以生成總路徑長度最小的測試路徑集合。但這些生成算法都忽略了路徑之間的獨立性問題。

根據(jù)Prime路徑的定義，考慮到圖中包含環(huán)路，根據(jù)Prime路徑的起點和終點類型，s代表開始節(jié)點，t表示終止節(jié)點，c表示環(huán)中的節(jié)點，將Prime路徑分為如下幾種類型：1）s→c，這類Prime路徑是從開始節(jié)點到環(huán)內的Prime路徑；2）c→t，這類Prime路徑是從環(huán)內到終止節(jié)點的Prime路徑；3）s→t，這類Prime路徑是從開始節(jié)點到終止節(jié)點的Prime路徑；4）c→c′（c′是不同于c的環(huán)），這類Prime路徑是從一個環(huán)內到另一個環(huán)內的Prime路徑；5）c→c，是一個自環(huán)路徑。按照Prime路徑類型，選擇一種覆蓋策略依此覆蓋s→c、c→c、c→c′、c→t及 s→t這5類Prime路徑類型，生成滿足路徑獨立性的測試路徑集合。

滿足獨立性需求的的Prime路徑測試路徑的生成策略及算法（IndPriTestPath Algorithm）如下：

Step 1 首先選擇s→t類型的Prime路徑，這些Prime路徑本身也是測試路徑，將這些Prime路徑加入到完成路徑集合和待生成的測試路徑集合中，同時將選擇的Prime路徑標記已覆蓋；

Step 2 從完成路徑集合中選擇一條路徑，采用逆向搜索，查找是否存在沒有被完全覆蓋的判定節(jié)點，若存在，執(zhí)行Step 3，若不存在，說明該測試路徑的判定節(jié)點均已搜索完，選擇下一條測試路徑，重復step 2，如果完成路徑集合中所有的Prime路徑都已搜索完畢，執(zhí)行Step 5；

Step 3 選取該判定節(jié)點的一條新邊，以該新邊為結尾的路徑，按照超串匹配規(guī)則選擇c→c′或c→t兩種類型的Prime路徑進行擴展：

如果是c→t類型，則產生新的一條測試路徑加入到測試路徑集合中，同時標記該Prime路徑，轉到Step 4；

如果是c→c′類型，則判定該條路徑中是否存在一個判定節(jié)點同時出現(xiàn)兩次新值，如果存在則舍棄該條路徑，繼續(xù)選擇新的Prime路徑，重復Step 3

Step 4 繼續(xù)逆向搜尋該路徑，如果仍有判定節(jié)點存在新的取值，重復執(zhí)行Step 2。

Step 5 如果仍存在Prime路徑未覆蓋，則該Prime路徑為環(huán)路，從測試路徑集合中選擇一條包含該環(huán)起始節(jié)點n的最短路徑p，用該Prime路徑替換

測試路徑中的節(jié)點n生成新的測試路徑 p′，并刪除原測試路徑p；如果不存在Prime路徑未覆蓋，則結束。

引理3 無自環(huán)有向圖中，滿足Prime路徑覆蓋的測試用例集合能夠覆蓋圖中的每個環(huán)路零次和兩次。

證明：首先證明滿足Prime路徑覆蓋的測試用例集合能夠包含每個環(huán)路的零次和兩次的執(zhí)行序列。1）假設，測試用例集合中存在一個環(huán)沒有被包含，考慮一般性環(huán)路設該路徑為 ai，ai+1，ai+2…ai+k，ai+k+1，ai=ak，零次循環(huán)表示測試用例需要覆蓋aiak+1的動作序列，即不存在某個測試用例覆蓋aiak+1，又ai=ak，則說明不存在一條路徑包含akak+1，也不存在路徑ak-1akak+1，但是ak-1akak+1是一條從環(huán)內到環(huán)外的路徑，被Prime路徑包含在內，因此該假設不成立。2）對于圖中的環(huán)而言，每個環(huán)都是一個Prime路徑，因此滿足Prime路徑覆蓋的測試用例集合一定包含圖中的所有環(huán)。3）考慮 一 般 性 環(huán) 路 ，設 該 路 徑 為 ai，ai+1，ai+2…ai+k，ai+k+1，ai=ak，對于環(huán) ai，ai+1，ai+2…ak，肯定在另外一個環(huán) ai+j…ak，ai+1…ai+j，ai=ak，根據(jù) Prime路徑覆蓋準則，ai+j…ak，ai+1…ai+j肯定被覆蓋一次，但到 ai+j肯定經(jīng)過 ai，環(huán) ai+j…ak，ai+1…ai+j中包含ai，最后環(huán) ai+j…ak，ai+1…ai+j的最后一個節(jié)點 ai+j在環(huán)內，Prime路徑覆蓋包含環(huán)內到環(huán)外的路徑，肯定也經(jīng)過ai，因此Prime路徑覆蓋包含每個環(huán)路兩次。

無自環(huán)的Prime路徑測試可以滿足圖中的節(jié)點覆蓋、邊覆蓋和邊對覆蓋，能夠充分保證測試的充分性，但卻無法保證路徑的獨立可行性。

引理4 所有s→t類型的Prime路徑都是滿足獨立性的基本路徑。

證明：設 p=v1，v2，…，vm為任意一條 s→ t類型的Prime路徑，且 v1∈Vs∧vm∈Ve，所以p也為一條測試路徑。因為p為簡單路徑，則 vi≠vj(1＜i≠j＜m)。即除首尾兩個節(jié)點外，其它節(jié)點不存在重復，也就是每個判定節(jié)點只有一次取值，所以p是滿足獨立性的基本路徑。

定理1 一條基本路徑從起始節(jié)點到終止節(jié)點一定可以分解為一條或幾條Prime路徑的組合。

證明：假設存在一條基本路徑 v1，v2…vt，v1為開始節(jié)點，vf為終止節(jié)點，該基本路徑分為有環(huán)和無環(huán)兩種情況。1）基本路徑中不存在環(huán)路：根據(jù)Prime路徑的定義可知，這條基本路徑也是Prime路徑 ；2）基 本 路 徑 中 存 在 環(huán) 路 ，即 v1，v2…vi，vi+1，…vj-1，vj，…vt，其中 vi=vj：根據(jù)超串問題［5～6］，可以將該路徑分解 v1，v2…vj-1以及 vi+1…vt兩條路徑，根據(jù)Prime路徑的定義可知，這兩條路徑均是Prime路徑，即該基本路徑可以分解為兩條Prime路徑的組合。由此可見，一條基本路徑從開始節(jié)點到終止節(jié)點一定可以分解為一條或幾條Prime路徑的組合。

定理2 采用算法1生成的測試路徑集合，其能夠覆蓋所有Prime路徑且滿足每個判定獨立影響至少1條路徑。

該定理易通過算法的執(zhí)行過程得證。首先算法終止的條件是所有的Prime路徑都會被包含，所有生成的測試路徑集合滿足Prime路徑覆蓋。根據(jù)Prime路徑的合成策略，下面三類擴展方案均滿足判定節(jié)點的獨立影響。

1）算法選用的起始路徑為s→t類型的路徑，該類路徑對每個判定節(jié)點只有一次取值，其后采用啟發(fā)式算法選擇其它Prime路徑，啟發(fā)式的目標是a）優(yōu)先選擇c→t類型的路徑，其次選擇c→c′類型路徑，能夠快速到終止節(jié)點，以期獲得較短的路徑；b）每次新增加的Prime路徑與原來構成的測試路徑，其判定節(jié)點不允許出現(xiàn)兩條新邊，以期獲得每個判定的獨立影響；

2）對s→c類型的路徑也是采用1）Prime路徑的擴展策略；

3）對c→c類型的路徑，在最短包含環(huán)路節(jié)點的Prime路徑基礎上進行擴展，以期使環(huán)路影響較短的路徑，從而也只產生一次判定節(jié)點的改變。

通過上面分析，容易看出定理2得證。

4 實例分析

采用文獻［5］的例子，對圖2的自動投幣售貨機FSM圖進行分析。該FSM包括9個變遷和3個事件，這三個事件分別為“AddChoc”，“Coin”和“GetChoc”，箭頭代表事件觸發(fā)后的轉換。該FSM由4個狀態(tài)組成：1，2，3，4。狀態(tài)1是初始狀態(tài)，狀態(tài)4為終止狀態(tài)。狀態(tài)1表示貨幣等于0且巧克力的數(shù)量是0；狀態(tài)2表示貨幣大于0但巧克力的數(shù)量等于0；狀態(tài)4表示貨幣和巧克力都大于0；狀態(tài)3表示貨幣等于0巧克力數(shù)量大于零。相應的狀態(tài)表示顧客投幣和服務人員放入巧克力的狀態(tài)轉換。

圖2 一種自動售貨機的FSM

為了測試該自動售貨機的行為，主要分析面向判定節(jié)點的獨立性影響和連續(xù)變遷的覆蓋問題，采用文獻［2］的算法求得的圖2的Prime路徑集合如表1所示。

表1 Prime路徑列表

如果圖2采用基本路徑覆蓋，得到的基本路徑集合如表2所示，雖基本路徑集合是不唯一的，但基本路徑集合的總數(shù)是確定的。由于基本路徑也是測試路徑，表2也給出了該基本路徑覆蓋Prime路徑的情況，和每個基本路徑生成對判定節(jié)點的取值影響情況。

表2 基本路徑及其覆蓋信息列表

生成的基本路徑并不能覆蓋（3，4）和（4，1），（4，1）和（1，3）等的有效邊對，因此，一些連續(xù)邊對影響的行為無法檢測出；而Prime路徑能夠覆蓋最大可能的無環(huán)連續(xù)邊對，但其產生的測試路徑不唯一，表3中兩組測試路徑集合，雖然測試代價較小，但存在測試路徑過長，實際測試時或因變遷和狀態(tài)之間存在太多的約束，難以產生有效的測試數(shù)據(jù)驅動路徑執(zhí)行，且該測試路徑并不能滿足路徑集合的獨立性需求，制約系統(tǒng)行為檢測能力。

采用InPrTestPath算法，圖2產生的測試路徑集合如表4所示。圖2中有4個判定節(jié)點：節(jié)點1可取值AddChoc和Coin，節(jié)點2可取值AddChoc和Coin，節(jié)點3可取值可取值AddChoc和Coin，節(jié)點4可取值可取值AddChoc、和GetChoc。Anurag算法雖然總路徑長度最短，但只有一條路徑，即只有1個判定節(jié)點對路徑生成起決定作用；Paul&Nan Li算法較Anurag算法而言，判定節(jié)點的獨立性覆蓋需求滿足度有所提升，但也僅有2個判定對路徑生成起決定作用。表4雖然路徑數(shù)目、總路徑長度都超過兩類Prime路徑生成算法，但該算法在生成每條新路徑時只改變一個節(jié)點的判定值，4個判定節(jié)點均對路徑生成起決定作用。通過分析新路徑的判定節(jié)點滿足度顯而易見，表3中的兩個Prime算法都無法滿足判定節(jié)點的獨立性覆蓋需求，考慮兼顧獨立性和連續(xù)邊的覆蓋分析，本文算法更易滿足。

表3 最短總長度測試路徑列表

5 結語

通過分析兩種常見的面向路徑覆蓋的測試準則：Prime路徑覆蓋準和基本路徑覆蓋準則各自內涵及其優(yōu)缺點，提出一種兼顧路徑獨立性和連續(xù)邊覆蓋的測試路徑生成技術。生成算法采用面向兩個目標的啟發(fā)式選擇策略，綜合考慮測試路徑總長度、判定節(jié)點獨立性影響、測試路徑數(shù)目、單測試路徑長度等綜合因素，通過本算法產生的測試路徑集合即考慮路徑獨立性組合問題又考慮連續(xù)變遷覆蓋問題，在保證覆蓋充分性的同時，使得測試路徑數(shù)和總測試路徑長度在可測性前提下保持在合理的范圍，從而保證測試覆蓋度的前提下測試路徑優(yōu)化。

表4 一種覆蓋獨立性的Prime測試路徑列表