詹澤梅

摘要： 覆蓋測(cè)試是軟件測(cè)試中的重要方法，路徑覆蓋測(cè)試中路徑集的自動(dòng)生成能提高測(cè)試效率。該文提出了一種描述程序分支情況的分支關(guān)系圖，給出了基于分支關(guān)系圖的路徑集自動(dòng)生成算法，實(shí)驗(yàn)證明了該方法的正確性，能有效地求出程序路徑集。

關(guān)鍵詞：路徑集；分支關(guān)系圖；軟件測(cè)試

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）25-5898-04

An Method of Automatic Generation for Paths Set in Software Coverage Testing

ZHAN Ze-mei

（Computer Science College， Yangtze University， Jingzhou 434023，China）

Abstract： Coverage testing is a important method for software testing. Automatic generation for paths set can enhance testing efficiency. A graph of branch relation is proposed for depicting branches in the program. The paper gives an algorithm for finding out paths set， which can work efficiently. The correctness of the algorithm is verified on a example.

Key words： paths set；the graph of branch relation； software testing

軟件測(cè)試是軟件工程理論中非常重要的一個(gè)方面，是提高軟件產(chǎn)品質(zhì)量和可靠性的關(guān)鍵。軟件測(cè)試可以分為功能測(cè)試和結(jié)構(gòu)測(cè)試兩大類。其中結(jié)構(gòu)測(cè)試又稱為白盒測(cè)試，是基于程序結(jié)構(gòu)特征，以實(shí)現(xiàn)某種測(cè)試覆蓋為目的一種測(cè)試方法。路徑覆蓋就是一種針對(duì)結(jié)構(gòu)測(cè)試的常用充分性準(zhǔn)則[1]，該方法可以有效地檢測(cè)程序中的錯(cuò)誤。基于路徑覆蓋的測(cè)試[2]是設(shè)計(jì)足夠的測(cè)試數(shù)據(jù)，覆蓋程序中所有可能的路徑。目前設(shè)計(jì)測(cè)試用例基本上是預(yù)先確定路徑，針對(duì)路徑設(shè)計(jì)對(duì)應(yīng)的測(cè)試用例，所以路徑集的確定對(duì)于路徑覆蓋測(cè)試非常重要。如果完全靠人工確定路徑集會(huì)花費(fèi)很大精力，因此應(yīng)該借助于自動(dòng)化的方法。

路徑集就是指程序中所有可能的路徑的集合。路徑集中沒有兩條完全相同的路徑。由于程序中存在分支語句、循環(huán)語句，程序中的路徑的數(shù)目會(huì)非常大，因此，在有限的測(cè)試資源下進(jìn)行路徑覆蓋測(cè)試，我們只考慮循環(huán)的兩種可能：循環(huán)體未執(zhí)行和循環(huán)體至少執(zhí)行一次。

目前已有的路徑集生成方法有：采用遺傳算法進(jìn)行路徑生成的方法[3]和A. Bertolino 利用簡(jiǎn)化的控制流圖來確定程序路徑。這些方法為生成程序的路徑提供了幫助，但不能保證生成的完整的路徑集。該文提出一種基于分支關(guān)系圖的路徑集生成方法，生成完整的路徑集。

1 程序路徑的表示

本質(zhì)上，程序的執(zhí)行表現(xiàn)為一系列判定條件取值的組合。例如程序1判斷三角形形狀的代碼如下。

1 main（ ）

2 {int a，b，c；

3 scanf（“%d%d%d”，&a，&b，&c）；

4 if （（a+b>c）&&（b+c>a）&&（a+c>b））

5 {if（（a！=b）&&（b！=c）&&（c！=a））

6 printf（"這是一個(gè)普通三角形"）；

7 else

8 if（（（a==b）&&（b！=c））||（（b==c）&&（c！=a））||（（c==a）&&（a！=b）））

9 printf（"這是一個(gè)等腰三角形"）；

10 else

11 printf（"這是一個(gè)等邊三角形"）； } }

12 else

13 printf（"這不是一個(gè)三角形"）；}

該程序總共有四條可執(zhí)行路徑，路徑1：1 2 3 4 12 13，路經(jīng)2：1 2 3 4 5 6，路經(jīng)3：1 2 3 4 5 7 8 9，路經(jīng)4：1 2 3 4 5 7 8 10 11。程序中的判定條件有3個(gè)，判定條件1：（a+b>c）&&（b+c>a）&&（a+c>b），判定條件2：（a！=b）&&（b！=c）&&（c！=a），判定條件3：（（a==b）&&（b！=c））||（（b==c）&&（c！=a））||（（c==a）&&（a！=b）） 。四條執(zhí)行路經(jīng)可用判定條件組合值來表示。由于判定條件可能被執(zhí)行到，也可能未被執(zhí)行到，例如路徑1中判定條件1執(zhí)行到了，而判定條件2和3就未執(zhí)行到。假設(shè)未被執(zhí)行到的判定條件其值用[φ]表示，執(zhí)行到的判定條件就用它的具體值表示，被執(zhí)行到的判定條件取值可為1或0或者其他整型值（switch語句中的條件值）。例1中程序的四條路徑可用判定條件組合值表示，路徑1：0[φ][φ]，路徑2：1 1[φ]，路經(jīng)3：1 0 1，路經(jīng)4：1 0 0。

本文中采用字符串表示路徑，可將路徑的組合值轉(zhuǎn)換為字符串形式，在分支序號(hào)前加字母c，在取值前加字母v，對(duì)未被執(zhí)行到的分支可省略，例如路徑1可表示為c1v0，路徑4表示為c1v1c2v0c3v0。

2 分支關(guān)系圖

2.1 分支結(jié)點(diǎn)

分支關(guān)系圖表示程序中分支情況，由于對(duì)于循環(huán)語句只考慮其循環(huán)體被執(zhí)行和未被執(zhí)行兩種情況，所以分支關(guān)系圖也描述了循環(huán)語句產(chǎn)生的分支。分支關(guān)系圖中一個(gè)結(jié)點(diǎn)代表一個(gè)條件分支，結(jié)點(diǎn)中記錄了該分支的判定條件序號(hào)和取值等信息，結(jié)點(diǎn)類型struct node定義如下：

struct node{

int number；

int value；

struct node * left；

struct node * right；

struct node * parallel；

}

number屬性表示判定條件序號(hào)，value屬性表示判定條件取值，left屬性指向內(nèi)層語句中的分支結(jié)點(diǎn)。內(nèi)層語句包括if子句、else子句、case后語句、循環(huán)體語句。right指向同一判定條件的其他分支，同屬于一個(gè)判定條件的分支取值互不相同。parallel指向同層次的其他判定條件的分支結(jié)點(diǎn)。

2.2 分支關(guān)系圖的創(chuàng)建

在遍歷抽象語法樹的過程中建立程序分支關(guān)系圖。在遍歷的過程中，遇到不同的節(jié)點(diǎn)進(jìn)行不同的處理，直到掃描結(jié)束。

當(dāng)被掃描結(jié)點(diǎn)為賦值語句或表達(dá)式語句或輸入輸出語句時(shí)，直接跳過，不進(jìn)行任何操作。

當(dāng)被掃描結(jié)點(diǎn)為if語句，則為該if語句的判定條件建立值為1的分支節(jié)點(diǎn)，和值為0的分支結(jié)點(diǎn)，再掃描if子句和掃描else子句。

當(dāng)被掃描結(jié)點(diǎn)為循環(huán)語句時(shí)，則為該循環(huán)條件建立值為1和值為0的分支結(jié)點(diǎn)，再掃描循環(huán)體。若被掃描結(jié)點(diǎn)為switch語句則為每個(gè)case和default建立一個(gè)分支結(jié)點(diǎn)，再掃描每個(gè)case分支語句。

程序1對(duì)應(yīng)的分支關(guān)系圖如圖1。

圖1 程序1的分支關(guān)系圖

3 路徑集生成算法

3.1 算法

建立分支關(guān)系圖后，通過遍歷該圖生成路徑集。在遍歷過程中記錄結(jié)點(diǎn)的分支序號(hào)和取值，在分支序號(hào)前加字母c，在取值前加字母v，將記錄的分支組合值字符串與該結(jié)點(diǎn)三個(gè)指針?biāo)阜种У慕M合值字符串進(jìn)行某種形式的連接。結(jié)點(diǎn)與其left所指分支屬于外層和內(nèi)層關(guān)系，應(yīng)進(jìn)行組合值字符串的直接連接；結(jié)點(diǎn)與其right所指分支結(jié)點(diǎn)為同一判定條件的不同取值結(jié)點(diǎn)，分屬于不同的路徑，是并列關(guān)系，應(yīng)用逗號(hào)連接組合值字符串；結(jié)點(diǎn)與parallel所指分支屬于同一層次，兩組合值字符串應(yīng)進(jìn)行路經(jīng)個(gè)體的矢量相乘。詳細(xì)算法如下。

算法1：Point（ ）//描述結(jié)點(diǎn)與其left所指分支之間的組合值字符串直接連接

參數(shù)：str1字符串1首地址，str2字符串2首地址

返回值：結(jié)果字符串地址

{ char t[60]，*p2=0，*q；

if （*str2=='c'）// c1v0·c2v1形式

{q為str1字符串和str2字符串直接相連}

if（*str2=='{'） // c1v0·{c2v1，c2v0}形式

{ 計(jì)算str2中條件組合值的個(gè)數(shù)i

計(jì)算結(jié)果字符串的大致長(zhǎng)度n

q= （char *）malloc（n）；

q[0]='＼0'；

p2=str2+1；

將str2中條件組合值逐個(gè)與str1中值直接連接，并加入q中 }

return q；

}

算法2：VectorMulti（ ）//描述結(jié)點(diǎn)與其parallel所指分支之間的組合值字符串矢量乘

參數(shù)：str1字符串1首地址，str2字符串2首地址

返回值：結(jié)果字符串地址

{char *s；

計(jì)算str1中條件組合值的個(gè)數(shù)i1和str2中條件組合值的個(gè)數(shù)i2；

計(jì)算結(jié)果字符串的大致長(zhǎng)度n；

s=（char *）malloc（n）；

s[0]={ ‘； s[1]=＼0；

while（str1中每一個(gè)條件組合值t1）

While（str2中每一個(gè)條件組合值t2）

{ 將t1與t2直接相連，并復(fù)制到s末尾

向s中加入逗號(hào)分隔符“，”； }

strcat（s，” }”）；

return s；

}

算法3：Comma（ ）//描述結(jié)點(diǎn)與其right所指分支之間的組合值字符串逗號(hào)連接

參數(shù)：str1字符串1首地址，str2字符串2首地址

返回值：結(jié)果字符串地址

{char * p；

p=（char）malloc（strlen（str1）+strlen（str2））；

將”{”復(fù)制到p中；

將str1中的分支條件值字符串復(fù)制到p末尾；

將逗號(hào)加入p字符串末尾；

將str2中的分支條件值字符串加入p字符串末尾；

將”}”復(fù)制到p末尾；

return p；

}

算法4：TravelGraph（）//遍歷分支關(guān)系圖，求路徑集字符串。

參數(shù)：分支關(guān)系圖根指針root

返回值：字符串地址

{計(jì)算該節(jié)點(diǎn)字符串p=“c”+number+”v”+value；

if（（root->left==0）&&（root->right==0）&&（root->parallel==0））

{ return p；}

else if （（root->left==0）&&（root->parallel==0））

{ q=Comma（p， TravelGraph （root->right ））； return q；}

else if（（root->right==0）&&（root->parallel==0））

{q=Point（p， TravelGraph （root->left））； return q；}

else if （root->left==0）

{q=Comma（p， TravelGraph （root->right ））； w=VectorMulti（q，TravelGraph（root->parallel））； return w；}

else if （root->parallel==0）

{q=Point（p， TravelGraph （root->left））； w=Comma（q， TravelGraph （root->right ））； return w；}

else if

（（root->left！=0）&&（root->right！=0）&&（root->parallel！=0））

{q=Point（p，TravelGraph（root->left））；w=Comma（q， TravelGraph （root->right））； s=VectorMulti（w，TravelGraph（root->parallel））； return s；}

else {printf（“錯(cuò)誤，結(jié)點(diǎn)異?！保?；}

}

3.2 實(shí)例分析

利用本算法對(duì)程序1進(jìn)行掃描分析，最終求得的路徑集結(jié)果為：c1v1c2v1， c1v1c2v0c3v1， c1v1c2v0c3v0，c1v0。該結(jié)果字符串清楚地表示了程序1的所有路徑及每條路徑的判定條件組合值，實(shí)驗(yàn)證明了本算法能有效地自動(dòng)生成路徑集。

4 結(jié)束語

面向路徑覆蓋的測(cè)試用例自動(dòng)生成必須首先確定路徑集，該文提出了一種路徑集的自動(dòng)生成方法，首先在掃描抽象語法樹的過程中建立分支關(guān)系圖，然后遍歷分支關(guān)系圖求出程序的路徑集。實(shí)驗(yàn)證明該方法能有效的求出程序的路徑集。但是，本方法仍然存在缺陷，在某些情況下求得的路徑集中會(huì)存在不可達(dá)的路徑，如何排除路徑集中全部不可達(dá)路徑是下一步要研究的問題。

參考文獻(xiàn)：

[1] Bertolino A，Marré M.How Many Paths Are Needed for Branch Testing？[J].The Journal of Systems and Software，1996，35（2）：95-106.

[2] Jin-Cherng Lin，Pu-Lin Yeh.Automatic Test Data Generation for Path Testing Using GAs[J].An International Journal，2001，131：47-64.

[3] Bint J R，Site R.Optimizing Testing Efficiency with Error Prone Path Identification and Genetic Algorithms[C] //Proc.of Australian Software Engineering Conference，2004：106-115.