廖偉志

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

?

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

廖偉志1,2

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

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

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

1 引言

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

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

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

2 路徑分割的自動判定與分離

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

2.1 變量與節(jié)點的關系

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

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

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

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

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

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

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

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

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

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

2.2 變量與路徑的關系

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

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

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

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

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

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

2.3 路徑分割的自動判定及分離算法

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

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

(1)

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

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

算法1 路徑分割的自動判定及分離算法

輸入：控制流圖的路徑P

輸出：路徑分割信息

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

步驟：

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

Step 2 構造矩陣A.

Step 3 構造矩陣B.

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

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

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

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

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

3.1 主要思想

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

3.2 初始魚群的構造

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

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

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

人工魚X穿越的路徑path(X)與目標路徑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的分支距離,關于這兩個距離的計算方法見文獻[19].

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

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

(3)

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

3.4 人工魚行為

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

(4)

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

(5)

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

3.5 人工魚群算法的改進

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

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

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

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

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

(6)

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

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

3.6 算法流程

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

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

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

步驟：

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

Step 2 調用算法1并插樁被測程序.

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

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

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

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

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

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

Step 9 若新位置在禁忌表中,則轉至Step 4,否則轉至Step 3.

4 實驗

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

為了驗證本文方法的有效性,選擇文獻[11]中圖3所示的sumday程序作為基準程序.將本文方法與文獻[11]及文獻[17]所提出的方法進行比較.為了便于敘述,把本文的方法稱為自動分割-改進人工魚方法(簡稱AD-IAFS方法),同時考察人工分割-改進人工魚方法(簡稱MD-IAFS方法).文獻[11]所提出的方法稱為人工分割-遺傳方法(簡稱MD-GA方法)而文獻[17]的方法稱為人工魚方法(簡稱AFS方法).實驗硬件環(huán)境為2.8GHz PC機、2GB內存；軟件環(huán)境為WinXP+Visual C++6.0.在本文的試驗中,對于MD-GA方法生成測試數(shù)據(jù)時所采用的相關參數(shù)不做任何改變,仍采用文獻[11]所采用的參數(shù)：交叉概率為0.9,變異概率為0.3,輸入變量的范圍為[0,2047],種群規(guī)模為50而最大進化代數(shù)為2000.AD-IAFS和MD-IAFS方法中主要參數(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.

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

表1 時間開銷

表2 成功率

表3 路徑P1搜索空間對比

圖4給出了三種方法在同一路徑P2上15次實驗的迭代次數(shù).從圖中的數(shù)據(jù)可以看出,由于三種方法每次實驗的初始種群都是隨機產(chǎn)生,因此每次生成測試數(shù)據(jù)的迭代次數(shù)都有變化.其中AFS方法迭代次數(shù)變化大,在圖中可以看出反映AFS變化的折線跳躍幅度最大,其次是MD-GA方法,而反映AD-IAFS和MD-IAFS變化的折線跳躍幅度最小.事實上,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ù)據(jù)顯示,AD-IAFS方法在時間開銷(含路徑分割時間)最少,成功率是100%,搜索空間和其它基于路徑分割的測試數(shù)據(jù)生成方法相當.綜合這些指標,本文提出的AD-IAFS方法仍為最好的方法,與在上述sumday程序測試的結論是一致的.

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

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

5 結論

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

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

[1]鞏敦衛(wèi),張婉秋.基于自適應分組的大規(guī)模路徑覆蓋測試數(shù)據(jù)進化生成[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è)大學,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]胡岳峰,高建華.一種面向對象測試用例自動生成的混合算法[J].計算機應用研究,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).基于搜索空間自動縮減的路徑覆蓋測試數(shù)據(jù)進化生成[J].電子學報,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]謝曉園,徐寶文,史亮,聶長海.面向路徑覆蓋的演化測試用例生成技術[J].軟件學報,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]李曉磊,邵之江,錢積新.一種基于動物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實踐,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]王培崇,錢旭.基于改進魚群算法的路徑測試數(shù)據(jù)生成[J].計算機應用,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)國,洪毅.基于馮·諾依曼領域結構的人工魚群算法[J].控制理論與應用，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年生于廣西鳳山,教授,博士,主要研究方向：軟件測試、智能計算.

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;責任編輯：藍紅杰

國家自然科學基金(No.61163012);廣西高?？蒲匈Y助項目(No.2013ZD040);廣西混雜計算與集成電路設計分析重點實驗室開放基金課題(No.2012HCIC01)

TP301

A

0372-2112 (2016)09-2254-08

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.034