基于動態(tài)集合進(jìn)化算法的弱變異測試用例集生成

2017-11-15 06:02:45郭后錢王微微趙瑞蓮

計算機(jī)應(yīng)用 2017年9期

郭后錢，王微微，尚穎，趙瑞蓮

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029)(*通信作者電子郵箱Shangy@mail.buct.edu.cn)

郭后錢，王微微，尚穎*，趙瑞蓮

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京 100029)(*通信作者電子郵箱Shangy@mail.buct.edu.cn)

為解決基于集合進(jìn)化算法(SEA)的弱變異測試用例集生成過程中個體規(guī)模固定和執(zhí)行開銷大的問題，提出一種基于動態(tài)集合進(jìn)化算法(DSEA)的弱變異測試用例集生成方法。以測試用例集為個體，生成覆蓋所有變異分支的弱變異測試用例集。在進(jìn)化過程中，集合精簡算子根據(jù)最優(yōu)個體的最小子集及其未覆蓋變異分支數(shù)量計算所需測試用例集的最小規(guī)模，并基于該最小規(guī)模調(diào)整種群中所有個體的規(guī)模，以生成最小規(guī)模的弱變異測試用例集，同時設(shè)計了適用于評估以測試用例集為個體的適應(yīng)度函數(shù)。實驗結(jié)果表明，動態(tài)集合進(jìn)化算法指導(dǎo)弱變異測試用例集生成，獲得的測試用例集規(guī)模比個體初始規(guī)模平均約簡了50.15%，執(zhí)行時間比集合進(jìn)化的弱變異測試用例集生成最多降低了74.58%。因此，動態(tài)集合進(jìn)化算法為最小規(guī)模的弱變異測試用例集生成和提升算法速度提供了一種解決方案。

測試用例生成；弱變異測試；分支覆蓋；集合進(jìn)化算法；貪心算法

0 引言

軟件測試日漸重要，基于變異的測試用例生成技術(shù)(Mutation-based Test Case Generation, MTCG)[1]得到了學(xué)術(shù)界的廣泛關(guān)注。變異測試是一種基于故障植入的軟件測試技術(shù)，使用變異算子對被測程序語句進(jìn)行合乎語法的微小改動，被改動的語句稱為變異語句，帶有變異語句的程序稱為變異體[2]。在變異體上執(zhí)行測試用例，若執(zhí)行結(jié)果和原程序執(zhí)行結(jié)果不同，則稱該變異體被該測試用例殺死，反之則稱該變異體未被殺死。MTCG技術(shù)旨在生成極少的測試用例殺死盡可能多的變異體，以獲得較高質(zhì)量的測試用例集。然而，變異測試代價昂貴，無法應(yīng)用于軟件實際測試中，因此，如何降低變異執(zhí)行開銷是MTCG技術(shù)的重點研究內(nèi)容[3]。

變異測試分為弱變異測試和強變異測試，弱變異測試只需檢測變異體變異位置的狀態(tài)和原程序不同，即可以判定該變異體被殺死；強變異測試則需要檢測變異體執(zhí)行結(jié)果和原程序輸出結(jié)果不同，才可判定變異體被殺死。所以，弱變異測試不用運行完整的程序，其測試代價小于強變異測試，是一種降低變異執(zhí)行開銷的有效途徑[4]。因此，目前大部分研究集中在弱變異測試用例自動生成方面。Papadakis等[5]基于弱變異測試準(zhǔn)則，提出用變異前后的語句構(gòu)建變異分支，將弱變異測試問題轉(zhuǎn)化為變異分支覆蓋問題，這在一定程度上降低了變異測試的執(zhí)行開銷，然而其在測試用例生成時，采用的進(jìn)化算法每次僅以一個變異分支為目標(biāo)，生成一條測試用例，效率較低。隨后，F(xiàn)raser等[6-7]以所有變異分支為目標(biāo)，以測試用例集為個體，利用遺傳算法實現(xiàn)測試用例集的自動生成；在此基礎(chǔ)上，文獻(xiàn)[8]給出了一種基于集合進(jìn)化算法(Set Evolutionary Algorithm, SEA)的弱變異測試用例集生成方法，將測試用例集作為個體，增設(shè)了集合內(nèi)部的交叉算子，通過種群進(jìn)化，使其個體能夠覆蓋更多變異分支，最終生成一個能夠覆蓋全部變異分支的個體或者達(dá)到其最大迭代次數(shù)，即測試用例集生成成功或失敗。該方法的執(zhí)行效率高于傳統(tǒng)的面向單個變異分支的測試用例生成方法，但也存在下面兩個問題：

1)個體規(guī)模(即其包含的測試用例個數(shù))在進(jìn)化過程中是固定不變的，因此需要設(shè)置適當(dāng)?shù)膫€體初始規(guī)模。然而通常情況下，測試人員無法事先根據(jù)擬覆蓋變異分支的個數(shù)確定所需的測試用例個數(shù)：取值過大，容易引起測試用例生成開銷的增大和存儲空間的浪費；取值過小，又可能導(dǎo)致測試用例集生成失敗。

2)其以目前廣泛使用的分支距離作為適應(yīng)度函數(shù)，不適合于以集合為個體的進(jìn)化評估，且該適應(yīng)度函數(shù)計算開銷大。

因此，本文提出了一種基于動態(tài)集合進(jìn)化算法(Dynamic Set Evolutionary Algorithm, DSEA)的弱變異測試用例集生成方法，該方法的個體規(guī)模是動態(tài)可變的，在進(jìn)化過程中，尋找合適的個體規(guī)模，以生成較小規(guī)模的測試用例集，同時避免個體初始規(guī)模對于測試用例集生成的影響。本文的主要貢獻(xiàn)如下：

1)提出了一個動態(tài)集合進(jìn)化算法，通過增設(shè)集合精簡算子，優(yōu)化種群中的個體規(guī)模，使個體規(guī)模在進(jìn)化過程中得以動態(tài)調(diào)整，以尋找合適的測試用例集規(guī)模。

2)設(shè)計了一個適用于集合進(jìn)化的適應(yīng)度函數(shù)，降低了動態(tài)集合進(jìn)化算法在弱變異測試用例集自動生成中的計算開銷。

3)在5個基準(zhǔn)程序上，實現(xiàn)了基于動態(tài)集合進(jìn)化的弱變異測試用例集自動生成，并與使用集合進(jìn)化的弱變異測試用例集生成方法進(jìn)行比較，結(jié)果表明利用動態(tài)集合進(jìn)化算法的弱變異測試用例集生成其時間開銷最多降低了74.58%，生成的測試用例集規(guī)模平均減少了50.15%。

1 相關(guān)研究

1.1 弱變異測試

對于給定的被測程序P，在其語句s上實施某一變異算子，得到變異語句s′，將被測程序P中s替換成s′，保持其他語句不變，則可以得到P的一個變異體M[9]。其中變異算子的定義是：在符合語法規(guī)則的前提下，從原程序生成差別極小程序(即變異體)的轉(zhuǎn)換規(guī)則。

例如，針對圖1所示原程序中的語句c=a+b，實施基本算術(shù)運算符替代變異操作，即分別用“-”“*”和“/”代替原始運算符“+”，生成3個變異體m1、m2和m3，如圖1所示。

變異測試通過執(zhí)行測試用例并檢測變異體與原程序的執(zhí)行結(jié)果來判定變異體是否被殺死。當(dāng)測試用例集足夠完備時，未被殺死的變異體，稱為等價變異體[10]。殺死的變異體數(shù)量占非等價變異體數(shù)量的比值，稱為變異得分[11]，常用來評價測試用例集的質(zhì)量。變異得分越高，測試用例集質(zhì)量越好。

一般情況下，測試用例殺死變異體需滿足3個條件：1)可達(dá)性條件：變異位置可以被測試用例執(zhí)行到；2)必要性條件：原程序與變異體在變異位置的執(zhí)行狀態(tài)不同；3)充分性條件：原程序與變異體的輸出結(jié)果不同。

滿足上述3個條件的變異測試即為強變異測試，由于充分性條件需要執(zhí)行完整的程序，執(zhí)行成本高，為降低執(zhí)行開銷，Howden[12]給出了弱變異測試準(zhǔn)則，只需滿足上述前兩個條件——可達(dá)性與必要性，即可判定變異體被殺死。

圖1 變異體示意圖

1.2 弱變異測試用例集生成

弱變異測試用例集生成是指生成滿足弱變異測試準(zhǔn)則的測試用例集。Papadakis等[5]認(rèn)為可以將弱變異測試準(zhǔn)則轉(zhuǎn)化為變異分支覆蓋準(zhǔn)則，其變異分支與變異分支覆蓋準(zhǔn)則定義如下：

定義1 變異分支。設(shè)原語句的主體表達(dá)式為e，實施某一變異算子后獲得變異語句的主體表達(dá)式為e′，構(gòu)造條件不等式e!=e′，該條件不等式則為一個變異分支。

例如，對于圖1中原程序語句c=a+b，應(yīng)用基本算術(shù)運算符替代變異操作后，對應(yīng)的三個變異語句分別為c=a-b、c=a*b和c=a/b，其變異分支分別為a+b!= a-b、a+b!= a*b和a+b!= a/b。

定義2 變異分支覆蓋準(zhǔn)則。在原程序P的相應(yīng)語句前插入其生成的所有變異分支，形成插樁程序P′，對程序P′執(zhí)行測試用例集，使得P′中每個變異分支其值為真的情況至少出現(xiàn)一次，則稱該測試用例集滿足變異分支覆蓋準(zhǔn)則。

將圖1中原程序語句c=a+b的三個變異分支插入到該語句c=a+b前，形成一個新的程序P′，如下所示。

class ClassA{

int s(int a,int b){

int c;

if((a+b)!=(a-b)){printf("m1 is killed");}

if((a+b)!=(a*b)){printf("m2 is killed");}

if((a+b)!=(a/b)){printf("m3 is killed");}

c=a+b;

return c;

}}

若測試用例集能夠覆蓋P′所有變異分支的真分支，則可檢測出原程序與所有變異體在變異位置的執(zhí)行狀態(tài)不同；即測試用例集滿足變異分支覆蓋準(zhǔn)則，等同于滿足弱變異測試準(zhǔn)則。

因此，基于弱變異測試準(zhǔn)則的測試用例生成問題可轉(zhuǎn)換為滿足變異分支覆蓋準(zhǔn)則的測試用例生成問題，通過不斷生成測試用例，直到所有變異分支都被覆蓋為止。

1.3 基于集合進(jìn)化的弱變異測試用例集生成

將弱變異測試準(zhǔn)則轉(zhuǎn)化為變異分支覆蓋準(zhǔn)則，將每個變異分支看作一個目標(biāo)，使得弱變異測試用例集的自動生成可以看作是一個多目標(biāo)問題，即生成若干測試用例，覆蓋所有變異分支。

利用進(jìn)化算法實現(xiàn)測試用例自動生成是一種常用的方法。傳統(tǒng)進(jìn)化算法，一個個體代表一個解。當(dāng)一個個體代表多個解的集合時，相應(yīng)的進(jìn)化優(yōu)化算法稱為集合進(jìn)化[13]，該算法可以一次生成滿足多個目標(biāo)的解集，而不是每次生成滿足單個目標(biāo)的解。將集合進(jìn)化算法應(yīng)用于弱變異測試用例集生成，其種群中的個體為測試用例集合，通過交叉、變異操作生成新個體。基于集合進(jìn)化的弱變異測試用例集生成如算法1所示。

算法1 基于集合進(jìn)化的弱變異測試用例生成算法SEA。

Initialpop;

//初始化

evaluate(pop);

//計算適應(yīng)度值

repeat

Inner_crossover(pop);

//個體內(nèi)部交叉操作

Inter_crossover(pop);

//個體之間交叉操作

Mutate(pop);

//個體變異操作

evaluate(pop);

//計算適應(yīng)度值

pop=update(pop);

//種群更新

until(滿足終止條件)

1)集合交叉Crossover()。

集合進(jìn)化種群中的個體是一個集合，其既可以通過兩個集合交叉產(chǎn)生新個體，又可以通過集合內(nèi)部交叉產(chǎn)生新個體，因此，集合交叉又可分為集合間交叉Inter_crossover()和集合內(nèi)交叉Inner_crossover()兩種，其中集合內(nèi)交叉是集合進(jìn)化算法所特有的。常用的集合交叉方式為單點交叉。

2)集合變異Mutate()。

集合變異是指通過對集合(個體)中的元素進(jìn)行更改，產(chǎn)生新的個體。常用的集合變異策略是隨機(jī)變異，即隨機(jī)選擇個體的某個基因進(jìn)行變異。

3)種群更新update()。

種群更新策略決定哪些個體可以進(jìn)入下一代種群。集合進(jìn)化算法中常用的種群更新策略為(μ+λ)更新策略，即種群規(guī)模為μ，其通過交叉變異產(chǎn)生λ個子代個體，在μ個父代個體與λ個子代個體中根據(jù)適應(yīng)度值選擇μ個個體進(jìn)入下一代種群。

將集合進(jìn)化算法應(yīng)用于弱變異測試用例集生成，其生成效率高于傳統(tǒng)方法，但其個體規(guī)模在進(jìn)化過程中是固定不變的，需要事先設(shè)置合適的個體初始規(guī)模，這是很困難的。此外，其使用分支距離作為適應(yīng)度函數(shù)，需要計算謂詞分支距離，增加了計算開銷。因此，本文提出一種動態(tài)集合進(jìn)化算法，用于實現(xiàn)弱變異測試用例集的自動生成。

2 動態(tài)集合進(jìn)化的弱變異測試用例集生成

本文針對弱變異測試用例集自動生成，提出一種動態(tài)集合進(jìn)化算法，通過增設(shè)集合精簡算子，動態(tài)調(diào)整個體規(guī)模，以尋找合適的測試用例集規(guī)模，同時避免個體初始規(guī)模對生成測試用例集規(guī)模的影響；設(shè)計了適用于集合進(jìn)化的適應(yīng)度函數(shù)，降低弱變異測試用例集生成的計算開銷。

2.1 動態(tài)集合進(jìn)化的弱變異測試用例集生成算法

基于動態(tài)集合進(jìn)化的弱變異測試用例集生成的核心思想是以變異分支覆蓋為準(zhǔn)則，以測試用例集合為個體，在種群進(jìn)化過程中，動態(tài)調(diào)整個體規(guī)模，以尋找合適的測試用例集規(guī)模，生成較小規(guī)模的測試用例集，實現(xiàn)弱變異測試用例集的自動生成。基于動態(tài)集合進(jìn)化的弱變異測試用例集生成如算法2所示。

算法2 基于動態(tài)集合進(jìn)化的弱變異測試用例集生成DSEA。

Initialpop;

//初始化

evaluate(pop);

//計算個體的適應(yīng)度值

repeat

refine_set=Greedy_Essential(best_Ind);

//精簡最優(yōu)個體

if(best_Ind.fitness==0){returnrefine_set;}

//測試用例集生成

else{

Nt=estimate(refine_set);

//估算個體(測試用例集)合適規(guī)模

pop=adjust(pop,Nt,refine_set);

//調(diào)整個體

Inner_crossover(pop);

//個體內(nèi)部交叉操作

Inter_crossover(pop);

//個體之間交叉操作

Mutate(pop);

//變異操作

evaluate(pop);

//計算個體的適應(yīng)度值

pop=update(pop);

//種群更新

}

until(滿足終止條件)

因此，基于動態(tài)集合進(jìn)化的弱變異測試用例集生成首先初始化種群pop，利用evaluate()函數(shù)計算種群中個體的適應(yīng)度值；通過Greedy_Essential()函數(shù)對最優(yōu)個體進(jìn)行精簡，除去冗余，獲得最優(yōu)個體的精簡集refine_set；若最優(yōu)個體精簡集refine_set能夠覆蓋所有的變異分支，則弱變異測試用例集生成，算法結(jié)束；否則，estimate()函數(shù)根據(jù)最優(yōu)個體精簡集規(guī)模和未覆蓋的變異分支數(shù)量估算個體(測試用例集)的適當(dāng)規(guī)模Nt，adjust()函數(shù)依據(jù)Nt調(diào)整種群的個體規(guī)模；對調(diào)整后的種群應(yīng)用集合進(jìn)化算法，實施交叉、變異操作生成新個體，update()函數(shù)根據(jù)種群更新策略對種群進(jìn)行更新。重復(fù)上述過程，直到進(jìn)化次數(shù)到達(dá)指定值或者生成弱變異測試用例集。

2.2 適應(yīng)度函數(shù)及動態(tài)集合進(jìn)化的設(shè)計

2.2.1 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來評估個體的優(yōu)劣，本文動態(tài)集合進(jìn)化算法的個體是測試用例集，目標(biāo)是覆蓋全部變異分支，因此本文將個體未覆蓋的變異分支數(shù)量作為衡量個體優(yōu)劣的適應(yīng)度函數(shù)。

假設(shè)被測程序的變異分支集為B，當(dāng)前個體Ind對每個變異分支bi(bi∈B)的覆蓋情況用fi(Ind)表示，即fi(Ind)=0表示變異分支bi被當(dāng)前個體Ind覆蓋，fi(Ind)=1表示個體Ind未覆蓋變異分支bi，則適應(yīng)度函數(shù)Fitness(Ind)的計算公式可以表示為：

(1)

Fitness(Ind)值越小，說明Ind沒有覆蓋的變異分支越少。當(dāng)Fitness(Ind)為0時，說明當(dāng)前個體覆蓋了全部的變異分支，滿足變異分支覆蓋準(zhǔn)則。

2.2.2 集合精簡算子

集合精簡算子用以調(diào)整種群中個體的規(guī)模，以尋找適當(dāng)?shù)臏y試用例集規(guī)模，生成較小規(guī)模的測試用例集，同時可在集合進(jìn)化過程中節(jié)省存儲空間。

集合精簡算子由3部分組成，即去除最優(yōu)個體的冗余基因獲得其精簡集Greedy_Essential()，估算適當(dāng)?shù)膫€體(測試用例集)規(guī)模estimate()和動態(tài)調(diào)整個體規(guī)模adjust()。

獲得最優(yōu)個體精簡集Greedy_Essential()：個體中冗余的基因擴(kuò)大了自身的規(guī)模，通過除去個體中的冗余基因，可以獲得較小規(guī)模的個體，同時還可以節(jié)省存儲空間。E貪心算法[14]是一種常用的精簡測試用例集方法，它在貪心算法的基礎(chǔ)上加入了essential策略，即由essential策略和greedy策略組成，essential策略的主要思想是選取出必要的元素。本文中的個體是測試用例集，除去測試用例集中的冗余測試用例，即可對該測試用例集進(jìn)行精簡，因此，本文根據(jù)E貪心算法，設(shè)計Greedy_Essential()函數(shù)，對最優(yōu)個體進(jìn)行精簡。假設(shè)被測程序的變異分支集為B，最優(yōu)個體由m個測試用例組成，即best_Ind={x1,x2,…,xm}，best_Ind覆蓋的變異分支集為Rp，未覆蓋的變異分支集為Rf，則該最優(yōu)個體的適應(yīng)度函數(shù)值為|Rf|；若測試用例xi(xi∈best_Ind)覆蓋的變異分支集記為bxi，則best_Ind中測試用例對應(yīng)覆蓋的變異分支集記為R={bx1,bx2,…,bxm}, 那么Greedy_Essential()首先應(yīng)用essential策略，選取出必要的測試用例，即某個變異分支只被best_Ind中的某個測試用例所覆蓋，那么這個測試用例就不可能是冗余的測試用例，將該測試用例放入精簡集refine_set并從best_Ind中刪除，同時從R和Rp中刪去其覆蓋的變異分支，繼續(xù)從best_Ind中選取必要的測試用例，放入精簡集refine_set，直到Rp中不存在只被best_Ind中一個測試用例覆蓋的變異分支為止。然后使用greedy策略，根據(jù)R中變異分支集的規(guī)模，從best_Ind中選取測試用例，每次選取R中最大規(guī)模元素對應(yīng)的測試用例，放入精簡集refine_set，并從R和Rp中刪去該測試用例覆蓋的變異分支，繼續(xù)選取直到Rp中不存在變異分支。綜上，選取出的所有測試用例組成了最優(yōu)個體精簡集refine_set。

估算個體合適規(guī)模estimate()：種群進(jìn)化過程中，通過在個體中添加額外的測試用例以覆蓋其未覆蓋的變異分支，可以估算合適的個體規(guī)模。由于最優(yōu)個體未覆蓋變異分支數(shù)量最少，所以其在理論上需要添加的額外測試用例個數(shù)最少。因此，可以通過最優(yōu)個體精簡集規(guī)模|refine_set|加上其未覆蓋變異分支數(shù)|Rf|作為估算的個體合適規(guī)模，即個體合適規(guī)模為Nt=|refine_set|+|Rf|。

2.2.3 種群更新策略

集合進(jìn)化的種群更新update()采用(μ+λ)更新策略，即在進(jìn)化過程中保留父代與子代中的優(yōu)秀個體，易導(dǎo)致種群失去多樣性。結(jié)合進(jìn)化策略中(μ，λ)更新[15]中只在λ個子代個體中擇優(yōu)選擇μ個個體組成下一代種群，本文設(shè)計一種新的種群更新策略(μ，λ+1)更新策略，μ表示當(dāng)前種群中有μ個父代個體，λ+1表示從λ個子代個體與1個父代最優(yōu)個體組成的臨時種群(要求λ+1>μ)中根據(jù)適應(yīng)度值擇優(yōu)選擇出μ個個體組成下一代種群，不僅保證了種群的多樣性，同時保證了種群進(jìn)化的質(zhì)量不會下降。

3 實驗

為驗證本文方法能否在不受個體初始規(guī)模影響的前提下，生成較小規(guī)模的弱變異測試用例集并降低執(zhí)行開銷，設(shè)計實驗，分析比較文獻(xiàn)[8]中的基于集合進(jìn)化的弱變異測試用例集生成方法和本文提出的基于動態(tài)集合進(jìn)化的弱變異測試用例集生成方法在生成的測試用例集規(guī)模和執(zhí)行時間上的優(yōu)劣。

3.1 基準(zhǔn)程序

實驗以5個變異測試常用的Java程序作為基準(zhǔn)程序[5,8],其程序的ID、總代碼行數(shù)、生成的變異分支數(shù)以及程序說明如表1所示。

表1 基準(zhǔn)程序

3.2 研究問題

為驗證本文的動態(tài)集合進(jìn)化算法在生成弱變異測試用例集時，是否能不受個體初始規(guī)模的影響，生成較小規(guī)模的測試用例集并降低執(zhí)行開銷，本文從以下兩個方面進(jìn)行研究：

1)利用動態(tài)集合進(jìn)化算法實現(xiàn)弱變異測試用例集自動生成時，個體初始規(guī)模對其最終生成的測試用例集規(guī)模是否有影響？與使用集合進(jìn)化的弱變異測試用例集生成方法相比，能否生成更小規(guī)模的測試用例集？

2)利用動態(tài)集合進(jìn)化算法生成弱變異測試用例集，相比于基于集合進(jìn)化的弱變異測試用例集生成，其執(zhí)行開銷是否有所降低？

3.3 實驗過程

首先，利用MuClipse工具[16]對表1所示的5個基準(zhǔn)程序?qū)嵤?5種方法級運算符變異操作，如算術(shù)運算符替換操作、邏輯運算符插入替換等操作，形成變異分支，并將所有變異分支插入原程序相應(yīng)位置，形成插樁后的被測程序，其相應(yīng)的變異分支數(shù)如表1第4列所示。

然后，利用集合進(jìn)化算法和本文提出的動態(tài)集合進(jìn)化算法，生成基準(zhǔn)程序的弱變異測試用例集。集合進(jìn)化算法采用分支距離作為其適應(yīng)度，計算方法如表2所示，T、F列分別表示條件語句為真(T)、假(F)時分支距離。

表2 分支距離計算方法

為保持實驗結(jié)果的可比性，兩種算法使用相同的參數(shù)，即種群規(guī)模為100，集合內(nèi)部的交叉概率P_inner為0.2，集合間交叉概率P_inter為0.7，集合變異的概率P_mutation為0.1。

實驗環(huán)境為Intel Core i7-4790 CPU 3.60 GHz，4.00 GB內(nèi)存，采用Microsoft Windows 7 64位操作系統(tǒng)和Eclipse SDK 4.2.2集成開發(fā)環(huán)境。

3.4 結(jié)果與分析

對于表1程序，分別以本文提出的動態(tài)集合進(jìn)化算法(DSEA)與集合進(jìn)化算法(SEA)生成弱變異測試用例集，生成的測試用例集規(guī)模如表3所示。

為探討基于動態(tài)集合進(jìn)化算法的弱變異測試用例集生成方法最終產(chǎn)生的測試用例集規(guī)模是否受個體初始規(guī)模的影響，本文對5個基準(zhǔn)程序，在5組個體初始規(guī)模下，進(jìn)行弱變異測試用例集生成。每個程序第一組個體初始規(guī)模的設(shè)置參照文獻(xiàn)[8]的個體初始規(guī)模值，隨后個體規(guī)模以5遞增，每組實驗重復(fù)十次，生成的弱變異測試用例集平均規(guī)模如表3所示。

表3 動態(tài)集合進(jìn)化算法生成的測試用例集規(guī)模

由表3可知，利用動態(tài)集合進(jìn)化算法實現(xiàn)弱變異測試用例集生成時，其生成的測試用例集規(guī)模不受個體初始規(guī)模的影響，并且約簡率最低為31.98%，平均為50.15%，約簡率是指最終生成的測試用例集約簡規(guī)模與個體初始規(guī)模的比值。

此外，實驗還討論了個體初始規(guī)模小于所需測試用例集規(guī)模的情況，結(jié)果如表4所示。

由表4可以看出，即使個體初始規(guī)模較小，利用動態(tài)集合進(jìn)化算法(DSEA)仍能生成所需的測試用例集，滿足弱變異測試準(zhǔn)則。而集合進(jìn)化算法(SEA)在個體初始規(guī)模小于所需測試用例集規(guī)模時，無法生成覆蓋全部變異分支的測試用例集。

表4 個體初始規(guī)模較小的弱變異測試用例集生成

集合進(jìn)化算法應(yīng)用于弱變異測試用例集生成時，其生成效率受個體初始規(guī)模影響，且最終生成的測試用例集規(guī)模即為個體初始規(guī)模。而動態(tài)集合進(jìn)化算法其最終生成的測試用例集規(guī)模不受個體初始規(guī)模影響，且生成的測試用例集規(guī)模很大程度上接近所需測試用例集的最小規(guī)模。

為分析對比動態(tài)集合進(jìn)化算法和集合進(jìn)化算法在生成弱變異測試用例集的時間開銷，本文對5個基準(zhǔn)程序，參照表3最終生成的測試用例集規(guī)模設(shè)置個體初始規(guī)模，重復(fù)進(jìn)行10次弱變異測試用例集生成，其生成的測試用例集規(guī)模和執(zhí)行時間如表5所示。

表5 兩種算法執(zhí)行時間開銷對比

由表5可知，利用動態(tài)集合進(jìn)化算法生成的弱變異測試用例集規(guī)模更小，其執(zhí)行時間也更少。執(zhí)行時間減少最多的是程序J2，比集合進(jìn)化算法降低了74.58%，程序J4的執(zhí)行時間也降低了64.13%。從表1可以看出，J2和J4的程序規(guī)模較大，生成的變異體數(shù)量也較多，因此可以認(rèn)為，被測程序的變異分支數(shù)越多，動態(tài)集合進(jìn)化算法越適用，弱變異測試用例集生成效率越高。

為更直觀地對比兩種算法的弱變異測試用例集生成時間開銷，圖2(a)(b)分別給出了J2和J4 10次重復(fù)生成弱變異測試用例集的執(zhí)行時間，并按執(zhí)行時間升序排列。由圖2可以看出動態(tài)集合進(jìn)化算法應(yīng)用于弱變異測試用例集生成時，其執(zhí)行時間明顯少于集合進(jìn)化算法。

為分析比較兩種算法在不同個體初始規(guī)模下，對弱變異測試用例集生成所需時間的影響，本文設(shè)置了5組不同的個體初始規(guī)模，圖3(a)(b)分別給出了程序J2和J4在不同個體初始規(guī)模下的測試用例集生成時間開銷。

由圖3可以看出，不同的個體初始規(guī)模下，動態(tài)集合進(jìn)化算法實現(xiàn)弱變異測試用例集生成的執(zhí)行時間明顯低于集合進(jìn)化算法。所以，利用動態(tài)集合進(jìn)化算法生成弱變異測試用例集，相比于基于集合進(jìn)化的弱變異測試用例集生成，其執(zhí)行開銷明顯降低。

圖2 兩種算法時間開銷對比

圖3 兩種算法不同個體初始規(guī)模的時間開銷對比

4 結(jié)語

測試用例集的自動生成一直是軟件工業(yè)界關(guān)注的重點。本文在弱變異測試準(zhǔn)則轉(zhuǎn)化為變異分支覆蓋準(zhǔn)則的基礎(chǔ)上，研究如何高效快速地生成較小規(guī)模的弱變異測試用例集。基于此，本文提出一種基于動態(tài)集合進(jìn)化算法的弱變異測試用例集生成方法，以測試用例集為個體，在進(jìn)化過程中根據(jù)執(zhí)行信息動態(tài)調(diào)整個體規(guī)模，尋找適當(dāng)?shù)臏y試用例集規(guī)模，生成較小規(guī)模的測試用例集，降低執(zhí)行開銷和節(jié)省存儲空間；同時設(shè)計了一個適用于集合進(jìn)化的適應(yīng)度函數(shù)，以降低計算開銷。研究表明基于動態(tài)集合進(jìn)化的弱變異測試用例集生成方法在執(zhí)行開銷和生成的測試用例集規(guī)模得到了極大的改善，提高了弱變異測試效率。

References)

[1] HANH L T M, BINH N T, TUNG K T. Survey on mutation-based test data generation [EB/OL]. [2017- 01- 04]. http://iaesjournal.com/online/index.php/IJECE/article/view/7917.

[2] PAPADAKIS M, MALEVRIS N. Searching and generating test inputs for mutation testing [J]. SpringerPlus, 2013, 2(1): 121.

[3] DAVE M, AGRAWAL R. Mutation testing and test data generation approaches: a review [C]// Smart Trends for Information Technology and Computer Communications. Berlin: Springer, 2016: 373-382.

[4] SOUZA F C, SOUZA M, PAPADAKIS M, et al. Test data generation techniques for mutation testing: a systematic mapping [EB/OL]. [2014- 04- 25]. http://pages.cs.aueb.gr/～mpapad/papers/eselaw2014.pdf.

[5] PAPADAKIS M, MALEVRIS N. Automatically performing weak mutation with the aid of symbolic execution, concolic testing and search-based testing [J]. Software Quality Control, 2011, 19(4): 691-723.

[6] FRASER G, ARCURI A. Whole test suite generation [J]. IEEE Transactions on Software Engineering, 2013, 39(2): 276-291.

[7] FRASER G, ARCURI A. Achieving scalable mutation-based generation of whole test suites [J]. Empirical Software Engineering, 2015, 20(3): 783-812.

[8] 張功杰,鞏敦衛(wèi),姚香娟.基于變異分析和集合進(jìn)化的測試用例生成方法[J].計算機(jī)學(xué)報,2015,38(11):2318-2331.(ZHANG G J,GONG D W, YAO X J. Test case generation based on mutation analysis and set evolution [J]. Chinese Journal of Computers, 2015, 38(11): 2318-2331.)

[9] 鞏敦衛(wèi),陳永偉,田甜.消息傳遞并行程序的弱變異測試及其轉(zhuǎn)化[J].軟件學(xué)報,2016,27(8):2008-2024.(GONG D W, CHEN Y W, TIAN T. Weak mutation testing and its transformation for message passing parallel programs [J]. Journal of Software, 2016, 27(8): 2008-2024.)

[10] KINTIS M, PAPADAKIS M, MALEVRIS N. Isolating first order equivalent mutants via second order mutation [C]// Proceedings of the 2012 IEEE 5th International Conference on Software Testing, Verification and Validation. Washington, DC: IEEE Computer Society, 2012: 701-710.

[11] JIA Y, HARMAN M. An analysis and survey of the development of mutation testing [J]. IEEE Transactions on Software Engineering, 2011, 37(5): 649-678.

[12] HOWDEN W E. Weak mutation testing and completeness of test sets [J]. IEEE Transactions on Software Engineering, 1982, 8(4): 371-379.

[13] GONG D, WANG G, SUN X, et al. A set-based genetic algorithm for solving the many-objective optimization problem [J]. Soft Computing, 2015, 19(6): 1477-1495.

[14] 章曉芳,徐寶文,聶長海,等.一種基于測試需求約簡的測試用例集優(yōu)化方法[J].軟件學(xué)報,2007,18(4):821-831.(ZHANG X F, XU B W, NIE C H, et al. An approach for optimizing test suite based on testing requirement reduction [J]. Journal of Software, 2007, 18(4): 821-831.)[15] 周永權(quán),張明,趙斌.基于進(jìn)化策略方法求任意函數(shù)的數(shù)值積分[J].計算機(jī)學(xué)報,2008,31(2):196-206.(ZHOU Y Q, ZHANG M, ZHAO B. Solving numerical integration based on evolution strategy method [J]. Chinese Journal of Computers, 2008, 31(2): 196-206.)

[16] SEGURA S, HIERONS R M, BENAVIDES D, et al. Automated metamorphic testing on the analyses of feature models [J]. Information and Software Technology, 2011, 53(3): 245-258.

Weakmutationtestcasesetgenerationbasedondynamicsetevolutionaryalgorithm

GUO Houqian, WANG Weiwei, SHANG Ying*, ZHAO Ruilian

(CollegeofInformationScienceandTechnology,BeijinguniversityofChemicalTechnology,Beijing100029,China)

To solve the problem of fixed individual scale and high execution cost of weak mutation test case set generation based on Set Evolutionary Algorithm (SEA), a generation method of weak mutation test case set based on Dynamic Set Evolutionary Algorithm (DSEA) was proposed. The test case sets were used as individuals to generate some weak mutations to cover all mutant branches. In the evolutionary process, according to the minimum subset of the optimal individuals and the number of uncovered mutation branches, the minimum scale of the required test case set was calculated by the set compact operator. And the size of all individuals in the population was adjusted based on the minimum scale to generate the smallest scale of the weak mutation test case set. At the same time, a fitness function for assessing a use case set as an individual was designed. The experimental results show that when the dynamic ensemble evolution algorithm is used to guide the generation of weak mutation test cases, and the scale of the test cases was 50.15% lower than the initial size of the individuals, and the execution time is lower than that of SEA by 74.58% at most. Thus, the dynamic ensemble evolution algorithm provides a solution for generating of the weak mutation test case set with minimum scale and enhancing the algorithm speed.

test case generation; weak mutation testing; branch coverage; Set Evolutionary Algorithm (SEA); greedy algorithm

2017- 03- 30;

2017- 04- 23。

國家自然科學(xué)基金資助項目(61472025, 61672085)。

郭后錢(1990—)，女，安徽六安人，碩士研究生，主要研究方向：軟件測試；王微微(1990—)，女，河北滄州人，博士研究生，CCF會員，主要研究方向：軟件測試；尚穎(1976—)，女，吉林四平人，講師，博士，CCF會員，主要研究方向：軟件測試；趙瑞蓮(1964—)，女，山西忻州人，教授，博士，CCF會員，主要研究方向：軟件測試、軟件可靠性分析。

1001- 9081(2017)09- 2659- 06

10.11772/j.issn.1001- 9081.2017.09.2659

TP311.5

This work is partially supported by the National Natural Science Foundation of China (61472025, 61672085).

GUOHouqian, born in 1990, M. S. candidate. Her research interest include software testing.

WANGWeiwei, born in 1990, Ph. D. candidate. Her research interest include software testing.

SHANGYing, born in 1976, Ph. D., lecturer. Her research interest include software testing.

ZHAORuilian, born in 1964, Ph. D., professor. Her research interests include software testing, software reliability analysis.

計算機(jī)應(yīng)用2017年9期

計算機(jī)應(yīng)用的其它文章: 基于移動用戶上下文相似度的張量分解推薦算法; 基于螺旋圖的時間序列數(shù)據(jù)可視化; 高維小樣本分類問題中特征選擇研究綜述; 基于子矩陣波束形成輸出直流響應(yīng)加權(quán)的目標(biāo)檢測方法; 基于免疫粒子群算法的中央空調(diào)冷凍水系統(tǒng)優(yōu)化控制; 基于SIFT的說話人唇動識別