廖偉志

(1.嘉興學(xué)院數(shù)理與信息工程學(xué)院,浙江嘉興 314001; 2.廣西混雜計(jì)算與集成電路設(shè)計(jì)分析重點(diǎn)實(shí)驗(yàn)室,廣西南寧 530006)

?

基于路徑自動(dòng)分割的測試數(shù)據(jù)生成方法

廖偉志1,2

(1.嘉興學(xué)院數(shù)理與信息工程學(xué)院,浙江嘉興 314001; 2.廣西混雜計(jì)算與集成電路設(shè)計(jì)分析重點(diǎn)實(shí)驗(yàn)室,廣西南寧 530006)

為了提高路徑覆蓋測試數(shù)據(jù)生成效率,研究了路徑自動(dòng)分割方法并結(jié)合人工魚群算法提出了一種路徑覆蓋測試數(shù)據(jù)生成方法.首先在分析變量與節(jié)點(diǎn)關(guān)系、變量與路徑關(guān)系的基礎(chǔ)上提出了路徑分割的自動(dòng)判定及分離算法，實(shí)現(xiàn)了變量對子路徑有無影響的自動(dòng)判定;其次引入Levy飛行策略和共軛梯度法對人工魚群算法進(jìn)行了改進(jìn);然后結(jié)合路徑分離的結(jié)果和改進(jìn)的人工魚群算法實(shí)現(xiàn)路徑覆蓋測試數(shù)據(jù)的生成.在利用人工魚生成測試數(shù)據(jù)的過程中,判斷是否有人工魚穿越分離的子路徑.如果有,則記錄人工魚中穿越子路徑相應(yīng)的分量并在人工魚的覓食、聚群及追尾等行為中固定這些分量,從而使得搜索空間不斷減少.最后將提出的方法實(shí)現(xiàn)程序的測試數(shù)據(jù)生成,并與相關(guān)方法進(jìn)行了比較.實(shí)驗(yàn)結(jié)果表明,本文方法在時(shí)間開銷、成功率及算法穩(wěn)定性等方面均具有優(yōu)越性.

軟件測試;路徑分割;測試數(shù)據(jù);路徑覆蓋;人工魚群算法

1 引言

軟件的可信度是衡量軟件質(zhì)量的一個(gè)重要特征,而要提高軟件的可信度,軟件測試則是一項(xiàng)不可或缺的技術(shù),其重要性是不言而喻的.白盒測試是一種重要的軟件測試方法,其中的路徑覆蓋為白盒測試最重要的測試充分性準(zhǔn)則之一.在該準(zhǔn)則下,如何有效地生成覆蓋路徑的測試數(shù)據(jù)是測試工作的關(guān)鍵.顯然,手工生成測試數(shù)據(jù)是一個(gè)非常耗費(fèi)人力和時(shí)間的過程,不僅效率低而且容易出錯(cuò).為此,需要人們研究有效實(shí)現(xiàn)測試數(shù)據(jù)自動(dòng)生成的相關(guān)理論和方法.至今,人們已經(jīng)給出多種測試數(shù)據(jù)自動(dòng)生成方法,包括隨機(jī)法、靜態(tài)法、動(dòng)態(tài)法和試探法[1～3].其中的試探法主要是運(yùn)用啟發(fā)式搜索算法實(shí)現(xiàn)測試數(shù)據(jù)的自動(dòng)生成,已成為國內(nèi)外研究的熱點(diǎn),如文獻(xiàn)[4～7]分別用模擬退火算法、人工免疫算法、禁忌搜索算法及微粒子群優(yōu)化算法得到滿足路徑覆蓋的測試數(shù)據(jù);而文獻(xiàn)[8～15]則對遺傳算法及元啟發(fā)式搜索實(shí)現(xiàn)路徑覆蓋測試數(shù)據(jù)的自動(dòng)生成進(jìn)行了研究.人工魚群算法是李曉磊等模仿魚類行為方式提出的一種基于動(dòng)物自治體的優(yōu)化方法,是集群智能思想的一個(gè)具體應(yīng)用.它能很好地解決非線性函數(shù)優(yōu)化等問題[16].人工魚群算法是一種有效的尋優(yōu)算法,具有并行性、簡單性、尋優(yōu)速度較快的特點(diǎn).實(shí)驗(yàn)表明,在諸多領(lǐng)域的應(yīng)用中人工魚群算法的性能要優(yōu)于遺傳算法及其它啟發(fā)式搜索算法.王培崇等[17]用人工魚群算法實(shí)現(xiàn)路徑覆蓋測試數(shù)據(jù)的自動(dòng)生成,實(shí)驗(yàn)表明基于人工魚群算法的測試數(shù)據(jù)生成效率要高于用粒子群優(yōu)化方法生成測試數(shù)據(jù)的效率,也避免了遺傳算法存在較易收斂于局部最優(yōu)的問題.然而,如何把相關(guān)技術(shù)與人工魚群算法進(jìn)行結(jié)合以實(shí)現(xiàn)路徑覆蓋測試數(shù)據(jù)的有效生成有待進(jìn)一步研究.

上述文獻(xiàn)在運(yùn)用相關(guān)算法生成測試數(shù)據(jù)時(shí),主要是在程序輸入的全空間內(nèi)搜索測試數(shù)據(jù).因此,如何縮減搜索空間從而有效提高測試數(shù)據(jù)的生成效率仍需人們做深入的探討.文獻(xiàn)[18]通過對測試數(shù)據(jù)的評價(jià)提出縮小輸入空間的策略,提高算法效率,并將其應(yīng)用于面向?qū)ο蟮能浖y試.張巖等[11]則通過分析目標(biāo)路徑與輸入變量之間的關(guān)系,將可分目標(biāo)路徑分離出與部分分量相關(guān)的子路徑;然后固定被穿越子路徑對應(yīng)的輸入分量,使種群在不斷縮小的空間里尋找測試數(shù)據(jù),從而達(dá)到提高測試數(shù)據(jù)生成效率的目的.但路徑是否可分的判定及可分路徑的分離均是通過人工實(shí)現(xiàn),嚴(yán)重影響測試數(shù)據(jù)的生成效率.

針對上述問題,本文在研究路徑自動(dòng)分割方法的基礎(chǔ)上,結(jié)合人工魚群算法提出了一種路徑覆蓋測試數(shù)據(jù)生成方法.首先在分析變量與節(jié)點(diǎn)關(guān)系、變量與路徑關(guān)系的基礎(chǔ)上提出了路徑分割的自動(dòng)判定及分離算法,實(shí)現(xiàn)了路徑上哪些輸入變量對哪些子路徑有影響而對哪些子路徑無影響的自動(dòng)判定.其次,為了提高人工魚群算法的求解能力,引入Levy飛行策略和共軛梯度法對人工魚群算法進(jìn)行了改進(jìn).最后結(jié)合路徑分離的結(jié)果和人工魚群算法實(shí)現(xiàn)路徑覆蓋測試數(shù)據(jù)的自動(dòng)生成.在利用人工魚生成測試數(shù)據(jù)的過程中,判斷是否有人工魚穿越分離的子路徑.如果有,則記錄人工魚中穿越子路徑相應(yīng)的分量并在人工魚的覓食、聚群及追尾等行為中固定這些分量,使搜索空間不斷減少,從而有效地提高了測試數(shù)據(jù)的生成效率.

2 路徑分割的自動(dòng)判定與分離

張巖等[11]通過分析目標(biāo)路徑與輸入變量之間的關(guān)系，將可分目標(biāo)路徑分離出與部分分量相關(guān)的子路徑,但路徑是否可分的判定及可分路徑的分離均是通過人工實(shí)現(xiàn).本節(jié)將在分析變量與節(jié)點(diǎn)關(guān)系、變量與路徑關(guān)系的基礎(chǔ)上提出一種路徑分割的自動(dòng)判定及分離算法.關(guān)于語句塊、控制流圖及路徑等基本概念見文獻(xiàn)[11].

2.1 變量與節(jié)點(diǎn)的關(guān)系

定義1 設(shè)x和y分別為被測程序的輸入變量,如果在程序中存在賦值語句：y=包含x的表達(dá)式,則稱變量x顯式影響變量y.

定義2 設(shè)x,y和z分別為被測程序的輸入變量,如果x顯式影響y,同時(shí)y顯式影響z,則稱x隱式影響z.

把x顯式影響y或x隱式影響y統(tǒng)稱為x影響y.

定義3 設(shè)x和P分別為被測程序的輸入變量及控制流圖的路徑,n為路徑P上的一個(gè)節(jié)點(diǎn),若n為決策節(jié)點(diǎn)且x出現(xiàn)在該節(jié)點(diǎn)中,或者x出現(xiàn)在非決策節(jié)點(diǎn)n的賦值語句中,則稱變量x顯式影響節(jié)點(diǎn)n.

定義4 設(shè)x,y為被測程序的輸入變量,n為路徑P上的一個(gè)節(jié)點(diǎn),若x顯式影響節(jié)點(diǎn)n而且y影響x,則稱變量y隱式影響節(jié)點(diǎn)n.

把變量x顯式影響節(jié)點(diǎn)n或變量x隱式影響節(jié)點(diǎn)n統(tǒng)稱為變量x影響節(jié)點(diǎn)n.

為了描述變量對變量的影響及變量對節(jié)點(diǎn)的影響,本文定義兩個(gè)矩陣：一個(gè)是路徑P上變量對變量影響的矩陣A,另一個(gè)則是變量對路徑P上各個(gè)節(jié)點(diǎn)影響的矩陣B.設(shè)路徑P={s,n1,…,nk,e}上的輸入變量集X={x1,…,xm},用m×m矩陣表示變量對變量影響的矩陣,且規(guī)定矩陣第i行第j列的元素

用m×k矩陣表示變量對路徑P上各個(gè)節(jié)點(diǎn)影響的矩陣,且規(guī)定矩陣第i行第j列的元素

矩陣A的求解步驟如下：①首先置矩陣A的初始值為0;②掃描路徑P上的各個(gè)非決策節(jié)點(diǎn),如果節(jié)點(diǎn)中含有賦值語句{xj=包含xi的表達(dá)式},則令aij的值為1;③如果aij=1且ajt=1,則令ait的值為1;④反復(fù)執(zhí)行③直到矩陣A元素值不再發(fā)生改變.

矩陣B的求解步驟如下：①首先置矩陣B的初始值為0;②掃描路徑P上的各個(gè)節(jié)點(diǎn);如果xi顯式影響節(jié)點(diǎn)nj，則令bij的值為1;③如果aij=1且bjt=1,則令bit的值為1;④反復(fù)執(zhí)行③直到矩陣B元素值不再發(fā)生改變.

2.2 變量與路徑的關(guān)系

定義5 設(shè)B為變量對路徑P上各個(gè)節(jié)點(diǎn)影響的矩陣,如果矩陣的第i行元素滿足:存在j(1≤j≤k)使得對任何大于等于1且小于等于j的整數(shù)l均有bil=0,則稱節(jié)點(diǎn)nj和nj+1(j+1≤k)為基于變量xi在路徑P上的分界點(diǎn),且稱變量xi不影響P的子路徑{n1,…,nj}.

定義6 設(shè)B為變量對路徑P上各個(gè)節(jié)點(diǎn)影響的矩陣,如果矩陣的第i行元素滿足:存在j(1≤j≤k)使得對任何大于等于j且小于等于k的整數(shù)l均有bil=0,則稱節(jié)點(diǎn)nj和nj-1(1≤j-1)為基于變量xi在路徑P上的分界點(diǎn),且稱變量xi不影響P的子路徑{nj,…,nk}.

定義7 設(shè)變量集V={x1,…,xm}且路徑P上的節(jié)點(diǎn)分別為n1,…,nk(不含起始和結(jié)束節(jié)點(diǎn)),如果存在節(jié)點(diǎn)nj(1≤j≤k)使得該節(jié)點(diǎn)為V中任意變量在路徑P上的一個(gè)分界點(diǎn)，則稱該路徑基于變量集V是可分的.

性質(zhì)1 設(shè)節(jié)點(diǎn)nj為可分路徑P={n1,…,nk}上的分界點(diǎn),則有：①如果j=1,則路徑分割為{n1}和{n2,…,nk}兩部分;②如果j=k,則路徑分割為{nk}和{n1,…,nk-1}兩部分;③如果1

定理1 設(shè)節(jié)點(diǎn)nj為可分路徑P={n1,…,nk}上的分界點(diǎn)且把P分割為{n1,…,nj}和{nj+1,…,nk}兩條子路徑,若V為P上的變量集,則基于該分界點(diǎn)V可分為兩個(gè)變量子集V1和V2,且同一變量子集中的每個(gè)變量不影響而且僅不影響P的同一條子路徑.

證明 由于路徑P基于變量集V是可分的且分界點(diǎn)為nj,根據(jù)定義7易知節(jié)點(diǎn)nj均為V中任意變量在路徑P上的一個(gè)分界點(diǎn),因此由定義5,6可知V中任意變量必然不影響P的子路徑{n1,…,nj}或者不影響子路徑{nj+1,…,nk},不妨把那些不影響{n1,…,nj}的變量放在變量子集V1,而把那些不影響{nj+1,…,nk}的變量放在變量子集V2,顯然有V1∩V2=(且V1∪V2=V,證畢.

2.3 路徑分割的自動(dòng)判定及分離算法

設(shè)路徑P基于變量集V是可分的且有l(wèi)種路徑分割方法,那么哪一種分割是最好的？由于變量不影響路徑的長度越長則測試數(shù)據(jù)的搜索空間就會(huì)越小,因此若各個(gè)變量不影響路徑的長度總和越大,則總的測試數(shù)據(jù)搜索空間就越小.為此本文選擇使得變量不影響路徑的長度總和最大的分割方法為最好的分割方法.設(shè)某種分割法的分界點(diǎn)為nj,基于該分界點(diǎn)V可分為兩個(gè)變量子集V1和V2,且V1不影響{n1,…,nj}而V2不影響{nj+1,…,nk},則V中所有變量不影響路徑的總長度計(jì)算方法如下式：

length=|V1|×j+|V2|×(k-j)

(1)

其中|V1|和|V2|分別為集合V1和V2的元素個(gè)數(shù).

下面給出路徑分割的自動(dòng)判定及分離算法,主要思想如下：首先掃描路徑上各個(gè)節(jié)點(diǎn)的變量;然后構(gòu)造變量對變量影響矩陣A及變量對節(jié)點(diǎn)影響矩陣B;其次由矩陣B找出基于各個(gè)變量在路徑上的分界點(diǎn)集,然后依據(jù)分界點(diǎn)集的交集判定路徑是否可分,若可分則根據(jù)式(1)確定分割方案;最后輸出分割的路徑及對應(yīng)的變量子集.具體的實(shí)現(xiàn)步驟見算法1.

算法1 路徑分割的自動(dòng)判定及分離算法

輸入：控制流圖的路徑P

輸出：路徑分割信息

（3）科技英語利用隱喻轉(zhuǎn)移語義，具體表現(xiàn)如下：一是把熟知事物的性質(zhì)轉(zhuǎn)移到另一事物。例如connecting rod（連桿），intake valve（進(jìn)氣門）等。 二是把熟知事物的形狀轉(zhuǎn)移到新事物上，如I-steel beam（工字鋼梁），pincer pliers（老虎鉗）等。三是將熟知事物結(jié)構(gòu)轉(zhuǎn)移給新事物，如body（車身），exhaust valve（排氣閥）等。四是把原有領(lǐng)域的術(shù)語用于另一領(lǐng)域，產(chǎn)生新的詞義，如 hollow（洞）--凹槽、jacket（夾克）--套等。

步驟：

Step 1 掃描路徑P上各個(gè)節(jié)點(diǎn)的變量并置入變量集V中.

Step 2 構(gòu)造矩陣A.

Step 3 構(gòu)造矩陣B.

Step 4 根據(jù)矩陣B確定基于各個(gè)變量xi在路徑P上的分界點(diǎn)集Si.

Step 5 令Scom=Si1∩Si2∩…∩Sil,其中l(wèi)=|V|.

Step 6 若Scom為空集,則表明路徑P不可分,轉(zhuǎn)至Step 8.

Step 7 若Scom不為空集,則依據(jù)式(1)查找使length為最大的分割法并輸出分割的路徑及變量子集V1和V2.

3 基于路徑分割和人工魚群算法的測試數(shù)據(jù)生成

3.1 主要思想

對于給定的路徑P,在人工魚群算法中按如下形式定義人工魚：人工魚的每個(gè)分量對應(yīng)于目標(biāo)路徑上的一個(gè)變量.根據(jù)設(shè)計(jì)的評價(jià)函數(shù),利用人工魚群算法中的覓食、聚群及追尾等行為改變?nèi)斯~的位置(即改變輸入變量的值)從而得到所需的路徑覆蓋測試數(shù)據(jù).在此過程中,首先根據(jù)算法1對目標(biāo)路徑進(jìn)行分離,然后確定不影響各個(gè)子路徑的變量集,接著判斷是否有人工魚穿越分離的子路徑.如果有,則記錄該人工魚中穿越子路徑相應(yīng)的分量,并在人工魚前進(jìn)的過程中固定這些分量的值,即不再去搜索這些分量的域空間,因此測試數(shù)據(jù)的搜索空間將不斷得到縮小從而能夠有效地提高測試數(shù)據(jù)的生成效率.

3.2 初始魚群的構(gòu)造

設(shè)目標(biāo)路徑P上的m個(gè)變量及其取值范圍分別為a1∈[min1,max1],…,am∈[minm,maxm],人工魚X包含m個(gè)分量x1,…,xm,分別對應(yīng)于變量a1,…,am,初始人工魚第i個(gè)分量xi的值為[mini,maxi]中的一個(gè)隨機(jī)值.

3.3 評價(jià)函數(shù)的設(shè)置

人工魚X包含|V|個(gè)分量(其中V為目標(biāo)路徑P上的變量集合)，每個(gè)分量對應(yīng)于V中的一個(gè)變量,第i個(gè)分量記為xi.記path(X)為X穿越的路徑,穿越目標(biāo)路徑P的輸入為X*,若X與X*相同,則X就是所求的測試數(shù)據(jù).

人工魚X穿越的路徑path(X)與目標(biāo)路徑P的距離如下式:

dis(path(X),P)=lev(path(X),P)+bra(path(X),P)

(2)

其中l(wèi)ev(path(X),P)為path(X)與P的層距離，而bra(path(X),P)為path(X)與P的分支距離,關(guān)于這兩個(gè)距離的計(jì)算方法見文獻(xiàn)[19].

設(shè)人工魚X優(yōu)劣的評價(jià)函數(shù)為f(X),其定義見式(3)：

f(X)=dis(path(X),P)

(3)

f(X)越小的人工魚就意味著該人工魚越優(yōu),當(dāng)f(X)=0時(shí),該人工魚就是所求的解.

3.4 人工魚行為

在覓食行為中,如果當(dāng)前人工魚X的第i個(gè)分量xi就是穿越了可分離目標(biāo)路徑P的某一子路徑的數(shù)據(jù),則該分量的值就被固化,即隨機(jī)狀態(tài)Y的第i個(gè)分量的數(shù)據(jù)就等于xi,只需改變X中不滿足此類條件的分量.覓食行為中隨機(jī)狀態(tài)Y的各分量值由式(4)給出：

(4)

在聚群行為中,如果當(dāng)前人工魚X的第i個(gè)分量xi或者X伙伴的第i個(gè)分量zi就是穿越了可分離目標(biāo)路徑P的某一子路徑的數(shù)據(jù),則中心位置Yc第i個(gè)分量的數(shù)據(jù)就等于xi或zi,否則等于X所有伙伴在該分量的數(shù)據(jù)和的平均值.中心位置Yc各分量的值按式(5)計(jì)算：

(5)

其中nf為當(dāng)前人工魚X領(lǐng)域內(nèi)的伙伴數(shù)目,zi為X某個(gè)伙伴的第i個(gè)分量.其它人工魚行為同基本人工魚群算法.

3.5 人工魚群算法的改進(jìn)

人工魚群算法作為一種隨機(jī)搜索算法,具有對初值要求不高、全局收斂性好、魯棒性強(qiáng)、簡單易實(shí)現(xiàn)的優(yōu)點(diǎn),但人工魚群算法尤其是基本人工魚群算法也存在著尋優(yōu)精度不高、后期收斂速度慢的問題.為了解決這些問題,人們已經(jīng)在諸多方面對算法進(jìn)行改進(jìn),主要改進(jìn)的策略有：①自適應(yīng)調(diào)整視野和步長,提高了收斂速度和尋優(yōu)精度;②引入禁忌表避免位置的重復(fù)訪問從而增強(qiáng)全局尋優(yōu)能力和尋優(yōu)效率;③為防止人工魚在游動(dòng)中出現(xiàn)退化采取了最優(yōu)個(gè)體保留策略,該策略使得算法具有求解精度高、尋優(yōu)成功率高、收斂速度快及算法穩(wěn)定等優(yōu)點(diǎn).

本文人工魚群算法除了采取上述的改進(jìn)方法之外,還提出了如下的改進(jìn)策略：

(1)利用Levy飛行使人工魚跳出局部極值

Levy飛行會(huì)產(chǎn)生較大跳躍從而能夠有效跳出局部極值,已有的人工魚群算法還沒有采用Levy飛行來解決人工魚跳出局部解的問題.本文采用Levy飛行模式來模擬人工魚的跳躍行為,使得人工魚在游動(dòng)過程中能夠有效跳出局部極值.人工魚位置的更新公式如下：

Xj+1=Xj+α⊕Levy(λ)

(6)

(2)采用共軛梯度法提高人工魚的局部尋優(yōu)能力

在人工魚群算法中引入共軛梯度法的目的在于:與基本人工魚群算法不同,經(jīng)過更新后的人工魚位置不是直接進(jìn)入下一次迭代,而是把得到的人工魚位置的梯度和共軛因子相乘后加到負(fù)梯度上計(jì)算出一組共軛方向,然后沿該方向搜索得到人工魚的新位置,之后再進(jìn)入下一次迭代,從而保證了算法的局部尋優(yōu)能力得到提高.在本文人工魚群算法中共軛梯度法的主要步驟如下：

3.6 算法流程

算法2 路徑覆蓋測試數(shù)據(jù)生成算法

輸入：程序控制流圖的路徑P

輸出：覆蓋路徑P的測試數(shù)據(jù)

步驟：

Step 1 設(shè)置人工魚群的相關(guān)參數(shù)、初始化種群、輸入目標(biāo)路徑P的相關(guān)信息.

Step 2 調(diào)用算法1并插樁被測程序.

Step 3 根據(jù)評價(jià)函數(shù)計(jì)算各人工魚的適應(yīng)值,將該適應(yīng)值與公告板的最優(yōu)人工魚進(jìn)行比較,若更優(yōu)則將其賦給公告板.同時(shí),在禁忌表中記錄各條人工魚已達(dá)到的歷史最優(yōu)點(diǎn)及已遍歷的解空間.

Step 4 根據(jù)如下公式[20]自適應(yīng)計(jì)算人工魚的視野與步長：

Step 5 判斷是否有人工魚穿越由P分離出的子路徑.如果有,則記錄影響該子路徑變量的值,用該值替換其它人工魚相應(yīng)分量的值并固化.

Step 6 若已經(jīng)迭代M次人工魚的適應(yīng)值未有明顯變化,則利用Levy飛行使人工魚跳出局部極值;否則根據(jù)覓食行為、聚群行為和追尾行為并結(jié)合最優(yōu)個(gè)體保留策略計(jì)算人工魚新的位置.

Step 7 采用共軛梯度法計(jì)算人工魚的新位置.

Step 8 若滿足終止條件則輸出最優(yōu)解,算法結(jié)束,否則轉(zhuǎn)至Step 9.

Step 9 若新位置在禁忌表中,則轉(zhuǎn)至Step 4,否則轉(zhuǎn)至Step 3.

4 實(shí)驗(yàn)

為了對本文所提出的方法提供技術(shù)支持,在Windows操作系統(tǒng)下采用C++語言開發(fā)了兩個(gè)程序,包括C程序路徑的自動(dòng)分割程序(Automatic Division of Path,簡稱ADP)和用于生成測試數(shù)據(jù)的人工魚群算法(Artificial Fish Swarm Algorithm for Test Data Generation,簡稱AFS-TDG).在ADP的設(shè)計(jì)中,首先利用編譯技術(shù)實(shí)現(xiàn)了C程序路徑上各個(gè)節(jié)點(diǎn)所包含變量的識別,然后根據(jù)算法1進(jìn)行代碼設(shè)計(jì)與實(shí)現(xiàn),最后輸出分割的路徑及其相關(guān)的變量子集.而AFS-TDG則是在已有的基本人工魚群算法的程序代碼基礎(chǔ)上增加了實(shí)現(xiàn)禁忌表的讀寫、人工魚視野與步長的自適應(yīng)調(diào)整、利用Levy飛行使人工魚跳出局部極值、最優(yōu)個(gè)體保留及共軛梯度法調(diào)整人工魚位置等功能的代碼.

為了驗(yàn)證本文方法的有效性,選擇文獻(xiàn)[11]中圖3所示的sumday程序作為基準(zhǔn)程序.將本文方法與文獻(xiàn)[11]及文獻(xiàn)[17]所提出的方法進(jìn)行比較.為了便于敘述,把本文的方法稱為自動(dòng)分割-改進(jìn)人工魚方法(簡稱AD-IAFS方法),同時(shí)考察人工分割-改進(jìn)人工魚方法(簡稱MD-IAFS方法).文獻(xiàn)[11]所提出的方法稱為人工分割-遺傳方法(簡稱MD-GA方法)而文獻(xiàn)[17]的方法稱為人工魚方法(簡稱AFS方法).實(shí)驗(yàn)硬件環(huán)境為2.8GHz PC機(jī)、2GB內(nèi)存；軟件環(huán)境為WinXP+Visual C++6.0.在本文的試驗(yàn)中,對于MD-GA方法生成測試數(shù)據(jù)時(shí)所采用的相關(guān)參數(shù)不做任何改變,仍采用文獻(xiàn)[11]所采用的參數(shù)：交叉概率為0.9,變異概率為0.3,輸入變量的范圍為[0,2047],種群規(guī)模為50而最大進(jìn)化代數(shù)為2000.AD-IAFS和MD-IAFS方法中主要參數(shù)設(shè)置如下：視野和步長分別為120和18,魚群規(guī)模為20,λ=1.7,M=10.類似于AD-IAFS,在AFS中人工魚視野和步長也分別為120和18,魚群規(guī)模為20.

考慮sumday程序控制流圖的3條路徑：P1={s,n1,n3,n5,n6,n5,n6,n5,n7,e},P2={s,n1,n2,n3,n5,n6,n5,n7,e},P3={s,n1,n2,n3,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n7,e}.P1可分割為路徑P11={n1,n3}和P12={n3,n5,n6,n5,n6,n5,n7},其中變量year只影響P11而不影響P12,而變量month和day只影響P12而不影響P11.P2可分割為路徑P21={n1,n3}和P22={n3,n5,n6,n5,n7},其中變量year只影響P21而不影響P22,而變量month和day只影響P22而不影響P21.P3可分割為路徑P31={n1,n3}和P32={n3,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n6,n5,n7},其中變量year只影響P31而不影響P32,而變量month和day只影響P32而不影響P31.

對于所要比較的四種方法,每種方法均進(jìn)行15次實(shí)驗(yàn).圖3顯示了AD-IAFS、MD-IAFS、MD-GA和AFS方法生成覆蓋路徑P1、P2和P3測試數(shù)據(jù)所需要的平均迭代次數(shù),對于每條路徑AD-IAFS方法和MD-IAFS所需的迭代次數(shù)均是最少的,說明了本文具有路徑分割的改進(jìn)人工魚群算法均優(yōu)于AFS算法和有路徑分割的遺傳算法.由表1可知,AD-IAFS方法的時(shí)間開銷比AFS方法平均要少一半而與不計(jì)人工分割路徑的MD-GA方法時(shí)間開銷相當(dāng),但遠(yuǎn)遠(yuǎn)小于含人工分割路徑時(shí)間開銷的MD-GA方法和MD-IAFS方法.需要說明的是,在本實(shí)驗(yàn)中，P1、P2和P3路徑人工分割的平均時(shí)間開銷為5分鐘,即為300000毫秒.如果程序的控制流圖規(guī)模增加,人工分割路徑的平均時(shí)間開銷遠(yuǎn)不只5分鐘.由此可以看出,基于路徑分割的搜索空間縮減方法能夠有效地提高測試數(shù)據(jù)的生成效率,但其前提是：路徑的分割一定是由計(jì)算機(jī)自動(dòng)完成,否則依靠人工分割路徑并不能真正提高效率,反而其時(shí)間開銷都遠(yuǎn)大于任何一種已有測試數(shù)據(jù)生成方法的時(shí)間開銷.由表2可知,基于路徑分割的AD-IAFS、MD-IAFS和MD-GA方法生成測試數(shù)據(jù)的成功率均能達(dá)到100%,而AFS方法生成穿越路徑P1、P2和P3的測試數(shù)據(jù)成功率分別為92.5%,98.7%和97.2%.由以上數(shù)據(jù)不難看出,AD-IAFS方法生成測試數(shù)據(jù)的效率均明顯高于MD-GA、MD-IAFS和AFS方法,其成功率和MD-GA、MD-IAFS方法相當(dāng)而高于AFS方法.從路徑搜索空間對比表3可看出，在基于路徑分割的測試數(shù)據(jù)生成方法中,在穿越n1,n3時(shí)只對year進(jìn)行搜索,而不對month和day進(jìn)行搜索;而在穿越n3,n5,n6,n7時(shí)只對month和day進(jìn)行搜索,而不對year進(jìn)行搜索.不采用基于路徑分割的AFS則需要進(jìn)行全空間搜索.

表1 時(shí)間開銷

表2 成功率

表3 路徑P1搜索空間對比

圖4給出了三種方法在同一路徑P2上15次實(shí)驗(yàn)的迭代次數(shù).從圖中的數(shù)據(jù)可以看出,由于三種方法每次實(shí)驗(yàn)的初始種群都是隨機(jī)產(chǎn)生,因此每次生成測試數(shù)據(jù)的迭代次數(shù)都有變化.其中AFS方法迭代次數(shù)變化大,在圖中可以看出反映AFS變化的折線跳躍幅度最大,其次是MD-GA方法,而反映AD-IAFS和MD-IAFS變化的折線跳躍幅度最小.事實(shí)上,MD-GA方法迭代次數(shù)的方差值為19879.5,AFS方法迭代次數(shù)的方差值為38437.2,而AD-IAFS和MD-IAFS方法的方差值為4743.1,該值為MD-GA方法的1/4而僅為AFS方法的1/8左右,說明本文方法的穩(wěn)定性均比MD-GA和AFS方法好.

再考察上述幾種方法在如圖1程序測試數(shù)據(jù)生成效率的對比情況.表4給出了如圖1程序路徑P測試數(shù)據(jù)生成在時(shí)間開銷、成功率及搜索空間的比較.表中的數(shù)據(jù)顯示,AD-IAFS方法在時(shí)間開銷(含路徑分割時(shí)間)最少,成功率是100%,搜索空間和其它基于路徑分割的測試數(shù)據(jù)生成方法相當(dāng).綜合這些指標(biāo),本文提出的AD-IAFS方法仍為最好的方法,與在上述sumday程序測試的結(jié)論是一致的.

表4 如圖1程序路徑P測試數(shù)據(jù)生成對比

從實(shí)驗(yàn)數(shù)據(jù)不難看出,基于計(jì)算機(jī)實(shí)現(xiàn)的路徑自動(dòng)分割方法相比人工路徑分割方法在時(shí)間效率上優(yōu)勢明顯.另一方面,人工分割不僅需要測試人員掌握分割方法,而且在分割的過程中容易出錯(cuò),分割的正確性難以保證,因此可靠性差;而自動(dòng)分割方法由于是通過計(jì)算機(jī)實(shí)現(xiàn),速度快而且可靠性高.

5 結(jié)論

本文提出一種新的路徑覆蓋測試數(shù)據(jù)生成方法,主要貢獻(xiàn)包括：①提出一種路徑分割自動(dòng)判定與分離方法,解決了人工分割路徑的弊端,為在測試數(shù)據(jù)生成過程中縮減搜索空間以提高生成效率提供了一種有效的方法;②給出了基于Levy飛行和共軛梯度的人工魚群改進(jìn)算法,改進(jìn)的人工魚群算法不僅能有效提高局部尋優(yōu)能力而且能有效避免人工魚陷入局部最優(yōu);③提出了基于路徑分割的測試數(shù)據(jù)生成人工魚群算法.實(shí)驗(yàn)表明該方法是一種有效的測試數(shù)據(jù)生成方法,在時(shí)間開銷、成功率及算法穩(wěn)定性方面均具有優(yōu)越性.

當(dāng)前主要將所提出的方法用于單路徑覆蓋測試數(shù)據(jù)的生成.如何把本文的方法運(yùn)用到多路徑覆蓋測試數(shù)據(jù)的生成從而滿足實(shí)際應(yīng)用中復(fù)雜軟件多路徑覆蓋測試數(shù)據(jù)生成的需求仍需做進(jìn)一步研究.

[1]鞏敦衛(wèi),張婉秋.基于自適應(yīng)分組的大規(guī)模路徑覆蓋測試數(shù)據(jù)進(jìn)化生成[J].控制與決策,2011,26(7):979-983.

Gong Dunwei,Zhang Wanqiu.Evolutionary generation of test data for many paths coverage based on adaptive grouping[J].Control and Decision,2011,26(7):979-983.(in Chinese)

[2]張婉秋.基于遺傳算法的多路徑覆蓋測試數(shù)據(jù)生成方法[D].江蘇徐州：中國礦業(yè)大學(xué),2010.

Zhang Wanqiu.Genetic algorithm based test data generation for multiple paths coverage[D].Xuzhou,Jiangsu:China University of Mining and Technology,2010.(in Chinese)

[3]Stefan J Galler,Bernhard K Aichernig.Survey on test data generation tools[J].International Journal on Software Tools for Technology Transfer,2014,16(6):727-751.

[4]Nigel Tracey,John Clark,Keith Mander.An automated framework for structural test-data generation[A].Proceedings of the International Conference on Automated Software Engineering[C].USA：IEEE,1998.285-285.

[5]Xiaofeng Xu,Yan Chen,Xiaochao Li.A path-oriented test data generation approach for automatic software testing[A].Proceedings of the 2ndInternational Conference on Anti-counterfeiting,Security and Identification[C].Piscataway:IEEE,2008.63-66.

[6]Eugenia Diaz,Javier Tuya,Raquel Blanco.A tabu search algorithm for structural software testing[J].Computers & Operations Research,2008,35(10):3052-3072.

[7]胡岳峰,高建華.一種面向?qū)ο鬁y試用例自動(dòng)生成的混合算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(3):786-788.

Hu Yuefeng,Gao Jianhua.Hybrid algorithm of automatically generating of test data for object-oriented program[J].Application Research of Computers,2008,25(3):786-788.(in Chinese)

[8]Moataz A Ahmed,Irman Hermadi.GA-based multiple paths test data generator[J].Computers & Operations Research,2008,35(10):3107-3124.

[9]Paulo Marcos Siqueira Bueno,Mario Jino.Automatic test data generation for program paths using genetic algorithms[J].International Journal of Software Engineering and Knowledge Engineering,2002,12(6):691-709.

[10]Jin-Cherng Lin,Pu-Lin Yeh.Automatic data generation for path testing using Gas[J].Information Sciences,2001,131(1-4):47-64.

[11]張巖,鞏敦衛(wèi).基于搜索空間自動(dòng)縮減的路徑覆蓋測試數(shù)據(jù)進(jìn)化生成[J].電子學(xué)報(bào),2012,40(5):1011-1016.

Zhang Yan,Gong Dunwei.Evolutionary generation of test data for path coverage based on automatic reduction of search space[J].Acta Electronica Sinica,2012,40(5):1011-1016.(in Chinese)

[12]A A Sofokleous,A S Andreou.Automatic evolutionary test data generation for dynamic software testing[J].Journal of System and Software,2008,81(11):1883-1898.

[13]謝曉園,徐寶文,史亮,聶長海.面向路徑覆蓋的演化測試用例生成技術(shù)[J].軟件學(xué)報(bào),2009,20(12):3117-3136.

Xie Xiaoyuan,Xu Baowen,Shi Liang,Nie Changhai.Genetic test case generation for path-oriented testing[J].Journal of Software,2009,20(12):3117-3136.(in Chinese)

[14]Yong Chen,Yong Zhong.Automatic path-oriented test data generation using a multi-population genetic algorithm[A].Proceeding of the 4th International Conference on Natural Computation[C].Piscataway:IEEE Press,2008.565-570.

[15]Chengying Mao.Structural test data generation based on harmony search[J].Lecture Notes in Computer Science,2013.353-360.

[16]李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38

Li Xiaolei,Shao Zhijiang,Qian Jixin.An optimizing method based on autonomous animats:fish-swarm algorithm[J].Systems Engineering-Theory & Practice,2002,22(11):32-38.(in Chinese)

[17]王培崇,錢旭.基于改進(jìn)魚群算法的路徑測試數(shù)據(jù)生成[J].計(jì)算機(jī)應(yīng)用,2013,33(4):1139-1141.

Wang Peichong,Qian Xu.Path test data generation based on improved artificial fish swarm algorithm[J].Journal of Computer Applications,2013,33(4):1139-1141.(in Chinese)

[18]JCB Ribeiro,MA Zenha-Rela,FFD Vega.Test case evolution and input domain reduction strategies for the evolutionary testing of object-oriented software[J].Information and Software Technology,2009,51(11):1534-1548.

[19]McMinn P.Evolutionary Search for test data in the presence of state behavior[D].Sheffied,England:University of Sheffied,2005.

[20]王聯(lián)國,洪毅.基于馮·諾依曼領(lǐng)域結(jié)構(gòu)的人工魚群算法[J].控制理論與應(yīng)用，2010,27(6):775-780.

Wang Lianguo,Hong Yi.Artificial fish-swarm algorithm based on Von Neuman neighborhood[J].Control Theory & Applications，2010,27(6):775-780.(in Chinese)

廖偉志 男,1974年生于廣西鳳山,教授,博士,主要研究方向：軟件測試、智能計(jì)算.

E-mail:weizhiliao2002@aliyun.com

Test Data Generation Based on Automatic Division of Path

LIAO Wei-zhi1,2

(1.CollegeofMathematicsPhysicsandInformationEngineering,JiaxingUniversity,Jiaxing,Zhejiang314001,China；2.GuangxiKeylaboratoryofHybridComputationandICDesignAnalysis,Nanning,Guangxi530006,China)

In order to improve the efficiency of test data generation for path coverage,a method for generating test data was proposed,which was based on automatic division of path and artificial fish-swarm (AFS) algorithm.Firstly,the relations between variables and nodes,and between variables and paths,were analyzed.Based on the analysis an algorithm for automatic division of path was presented,which can automatically judge the impact of variables on sub-paths.Secondly,an improved AFS algorithm was developed based on Levy flying and conjugate gradient.By making use of the result of path division and the improved AFS algorithm,a new method for searching test data was proposed.If there exist sub paths that the fish pass through in the process of using AFS to generate test data,the corresponding component of these fish were fixed,so that search space were reduced.Finally,the proposed method was applied to the test data generation of programs.It is shown that our method outperforms the related methods in running time,success rate and stability.

software testing;path division;test data;path coverage;artificial fish-swarm algorithm

2014-10-10;

2015-03-26;責(zé)任編輯：藍(lán)紅杰

國家自然科學(xué)基金(No.61163012);廣西高校科研資助項(xiàng)目(No.2013ZD040);廣西混雜計(jì)算與集成電路設(shè)計(jì)分析重點(diǎn)實(shí)驗(yàn)室開放基金課題(No.2012HCIC01)

TP301

A

0372-2112 (2016)09-2254-08

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.034