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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

1 相關(guān)研究

1.1 弱變異測(cè)試

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

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

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

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

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

圖1 變異體示意圖

1.2 弱變異測(cè)試用例集生成

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

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

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

將圖1中原程序語(yǔ)句c=a+b的三個(gè)變異分支插入到該語(yǔ)句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;

}}

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

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

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

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

利用進(jìn)化算法實(shí)現(xiàn)測(cè)試用例自動(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)用于弱變異測(cè)試用例集生成，其種群中的個(gè)體為測(cè)試用例集合，通過(guò)交叉、變異操作生成新個(gè)體。基于集合進(jìn)化的弱變異測(cè)試用例集生成如算法1所示。

算法1 基于集合進(jìn)化的弱變異測(cè)試用例生成算法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è)集合，其既可以通過(guò)兩個(gè)集合交叉產(chǎn)生新個(gè)體，又可以通過(guò)集合內(nèi)部交叉產(chǎn)生新個(gè)體，因此，集合交叉又可分為集合間交叉Inter_crossover()和集合內(nèi)交叉Inner_crossover()兩種，其中集合內(nèi)交叉是集合進(jìn)化算法所特有的。常用的集合交叉方式為單點(diǎn)交叉。

2)集合變異Mutate()。

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

3)種群更新update()。

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

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

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

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

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

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

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

Initialpop;

//初始化

evaluate(pop);

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

repeat

refine_set=Greedy_Essential(best_Ind);

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

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

//測(cè)試用例集生成

else{

Nt=estimate(refine_set);

//估算個(gè)體(測(cè)試用例集)合適規(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)化的弱變異測(cè)試用例集生成首先初始化種群pop，利用evaluate()函數(shù)計(jì)算種群中個(gè)體的適應(yīng)度值；通過(guò)Greedy_Essential()函數(shù)對(duì)最優(yōu)個(gè)體進(jìn)行精簡(jiǎn)，除去冗余，獲得最優(yōu)個(gè)體的精簡(jiǎn)集refine_set；若最優(yōu)個(gè)體精簡(jiǎn)集refine_set能夠覆蓋所有的變異分支，則弱變異測(cè)試用例集生成，算法結(jié)束；否則，estimate()函數(shù)根據(jù)最優(yōu)個(gè)體精簡(jiǎn)集規(guī)模和未覆蓋的變異分支數(shù)量估算個(gè)體(測(cè)試用例集)的適當(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ù)上述過(guò)程，直到進(jìn)化次數(shù)到達(dá)指定值或者生成弱變異測(cè)試用例集。

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

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

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

假設(shè)被測(cè)程序的變異分支集為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)值越小，說(shuō)明Ind沒有覆蓋的變異分支越少。當(dāng)Fitness(Ind)為0時(shí)，說(shuō)明當(dāng)前個(gè)體覆蓋了全部的變異分支，滿足變異分支覆蓋準(zhǔn)則。

2.2.2 集合精簡(jiǎn)算子

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

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

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

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

調(diào)整個(gè)體規(guī)模adjust()：在每一輪種群進(jìn)化過(guò)程中，根據(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è)體通過(guò)其精簡(jiǎn)集refine_set中加入|Rf|條測(cè)試用例，將規(guī)模調(diào)整為Nt，其他個(gè)體移除(|best_Ind|-Nt)條測(cè)試用例，將規(guī)模調(diào)整為Nt；若個(gè)體規(guī)模

2.2.3 種群更新策略

集合進(jìn)化的種群更新update()采用(μ+λ)更新策略，即在進(jìn)化過(guò)程中保留父代與子代中的優(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ī)模的弱變異測(cè)試用例集并降低執(zhí)行開銷，設(shè)計(jì)實(shí)驗(yàn)，分析比較文獻(xiàn)[8]中的基于集合進(jìn)化的弱變異測(cè)試用例集生成方法和本文提出的基于動(dòng)態(tài)集合進(jìn)化的弱變異測(cè)試用例集生成方法在生成的測(cè)試用例集規(guī)模和執(zhí)行時(shí)間上的優(yōu)劣。

3.1 基準(zhǔn)程序

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

表1 基準(zhǔn)程序

3.2 研究問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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)化的測(cè)試用例生成方法[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),陳永偉,田甜.消息傳遞并行程序的弱變異測(cè)試及其轉(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] 章曉芳,徐寶文,聶長(zhǎng)海,等.一種基于測(cè)試需求約簡(jiǎn)的測(cè)試用例集優(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。

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

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

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.