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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

1 相關(guān)研究

1.1 弱變異測試

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

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

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

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

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

圖1 變異體示意圖

1.2 弱變異測試用例集生成

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

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

例如，對(duì)于圖1中原程序語句c=a+b，應(yīng)用基本算術(shù)運(yùn)算符替代變異操作后，對(duì)應(yīng)的三個(gè)變異語句分別為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′，對(duì)程序P′執(zhí)行測試用例集，使得P′中每個(gè)變異分支其值為真的情況至少出現(xiàn)一次，則稱該測試用例集滿足變異分支覆蓋準(zhǔn)則。

將圖1中原程序語句c=a+b的三個(gè)變異分支插入到該語句c=a+b前，形成一個(gè)新的程序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)則，將每個(gè)變異分支看作一個(gè)目標(biāo)，使得弱變異測試用例集的自動(dòng)生成可以看作是一個(gè)多目標(biāo)問題，即生成若干測試用例，覆蓋所有變異分支。

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

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

Initialpop;

//初始化

evaluate(pop);

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

repeat

Inner_crossover(pop);

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

Inter_crossover(pop);

//個(gè)體之間交叉操作

Mutate(pop);

//個(gè)體變異操作

evaluate(pop);

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

pop=update(pop);

//種群更新

until(滿足終止條件)

1)集合交叉Crossover()。

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

2)集合變異Mutate()。

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

3)種群更新update()。

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

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

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

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

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

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

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

Initialpop;

//初始化

evaluate(pop);

//計(jì)算個(gè)體的適應(yīng)度值

repeat

refine_set=Greedy_Essential(best_Ind);

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

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

//測試用例集生成

else{

Nt=estimate(refine_set);

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

pop=adjust(pop,Nt,refine_set);

//調(diào)整個(gè)體

Inner_crossover(pop);

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

Inter_crossover(pop);

//個(gè)體之間交叉操作

Mutate(pop);

//變異操作

evaluate(pop);

//計(jì)算個(gè)體的適應(yīng)度值

pop=update(pop);

//種群更新

}

until(滿足終止條件)

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

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

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

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

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

(1)

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

2.2.2 集合精簡算子

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

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

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

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

調(diào)整個(gè)體規(guī)模adjust()：在每一輪種群進(jìn)化過程中，根據(jù)估算的個(gè)體合適規(guī)模Nt=|refine_set|+|Rf|，對(duì)種群中的個(gè)體規(guī)模進(jìn)行調(diào)整。比較當(dāng)前種群中的個(gè)體規(guī)模與Nt的大?。喝魝€(gè)體規(guī)?！軳t，調(diào)整策略為：最優(yōu)個(gè)體通過其精簡集refine_set中加入|Rf|條測試用例，將規(guī)模調(diào)整為Nt，其他個(gè)體移除(|best_Ind|-Nt)條測試用例，將規(guī)模調(diào)整為Nt；若個(gè)體規(guī)模

2.2.3 種群更新策略

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

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

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

3.1 基準(zhǔn)程序

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

表1 基準(zhǔn)程序

3.2 研究問題

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

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

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

3.3 實(shí)驗(yàn)過程

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

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

表2 分支距離計(jì)算方法

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

實(shí)驗(yàn)環(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é)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 兩種算法時(shí)間開銷對(duì)比

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

4 結(jié)語

測試用例集的自動(dòng)生成一直是軟件工業(yè)界關(guān)注的重點(diǎn)。本文在弱變異測試準(zhǔn)則轉(zhuǎn)化為變異分支覆蓋準(zhǔn)則的基礎(chǔ)上，研究如何高效快速地生成較小規(guī)模的弱變異測試用例集?；诖?，本文提出一種基于動(dòng)態(tài)集合進(jìn)化算法的弱變異測試用例集生成方法，以測試用例集為個(gè)體，在進(jìn)化過程中根據(jù)執(zhí)行信息動(dòng)態(tài)調(diào)整個(gè)體規(guī)模，尋找適當(dāng)?shù)臏y試用例集規(guī)模，生成較小規(guī)模的測試用例集，降低執(zhí)行開銷和節(jié)省存儲(chǔ)空間；同時(shí)設(shè)計(jì)了一個(gè)適用于集合進(jìn)化的適應(yīng)度函數(shù)，以降低計(jì)算開銷。研究表明基于動(dòng)態(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ì)算機(jī)學(xué)報(bào),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é)報(bào),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é)報(bào),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ì)算機(jī)學(xué)報(bào),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é)基金資助項(xiàng)目(61472025, 61672085)。

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

1001- 9081(2017)09- 2659- 06

10.11772/j.issn.1001- 9081.2017.09.2659

TP311.5

A

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.