劉 冬，靳蓓蓓，闕向紅

(1.皖南醫(yī)學(xué)院第一附屬醫(yī)院 計(jì)算機(jī)中心，安徽 蕪湖 241001；2.華中科技大學(xué) 網(wǎng)絡(luò)與計(jì)算中心，湖北 武漢 430030；3.安徽師范大學(xué)，安徽 蕪湖 241000)

基于一種遺傳算法的最小測試用例集自動(dòng)生成

劉 冬1,2，靳蓓蓓3，闕向紅2

(1.皖南醫(yī)學(xué)院第一附屬醫(yī)院 計(jì)算機(jī)中心，安徽 蕪湖 241001；2.華中科技大學(xué) 網(wǎng)絡(luò)與計(jì)算中心，湖北 武漢 430030；3.安徽師范大學(xué)，安徽 蕪湖 241000)

測試數(shù)據(jù)的生成是一個(gè)復(fù)雜的問題，且其技術(shù)和方法還不成熟。在生成最小測試用例集過程中，為了避免基本遺傳算法對(duì)已經(jīng)滿足測試需求的測試用例重復(fù)進(jìn)行遺傳操作，文中在基本遺傳算法的基礎(chǔ)上，最大提高遺傳算法的穩(wěn)定性，提出最大穩(wěn)定遺傳算法(LSGA)。該算法能很好地保證種群的最大穩(wěn)定性，提高搜索性能，最后對(duì)該算法從概率角度理論證明其優(yōu)越性。實(shí)例分析表明，利用該算法能較快生成最小測試用例集，從而實(shí)現(xiàn)對(duì)測試目標(biāo)的充分測試，提高測試效率，降低測試成本。

測試用例集;測試用例;基本路徑集;基本遺傳算法;軟件測試

1 概 述

自動(dòng)生成測試用例的問題是一個(gè)非常困難的問題，也是軟件測試自動(dòng)化的一個(gè)重要環(huán)節(jié)。自從基本遺傳算法被提出，許多研究者在軟件測試中不斷嘗試引入基本遺傳算法。Jones[1]和Hermadi[2]引入基本遺傳算法(GA)解決自動(dòng)生成測試用例問題，并進(jìn)行性能分析。文獻(xiàn)[3]比較了GA和梯度下降法的搜索性能，并通過兩個(gè)具體的實(shí)例驗(yàn)證了GA明顯優(yōu)于梯度下降法。Jones[4]和Wegener[5]的研究證明，通過GA生成的測試用例數(shù)明顯少于梯度下降法。然而之前的研究成果都是根據(jù)給出的某一個(gè)測試需求，使用各類算法生成測試用例，該用例滿足這個(gè)測試需求。例如文獻(xiàn)[6]中闡述的基于路徑的自動(dòng)生成測試數(shù)據(jù)，為實(shí)現(xiàn)路徑覆蓋，用模擬退火遺傳算法或其他啟發(fā)式算法測試人工選擇的一條路徑，從而產(chǎn)生一個(gè)測試用例，覆蓋該路徑，而想要覆蓋其他不同的路徑，就必須由人工不停選擇不同的測試路徑。這樣就暴露出一個(gè)問題。若測試需要待測程序中所有路徑都被覆蓋，就必須人工指定所有測試路徑。那么工作量就比較大，費(fèi)時(shí)、費(fèi)力。

因此，文中希望能自動(dòng)生成一個(gè)最小測試用例集，該用例集中的測試用例能全部覆蓋所有路徑，且每個(gè)測試用例僅覆蓋其中一條路徑。有關(guān)生成最小測試用例集的問題已經(jīng)有大量的研究成果。

Johnson[7]引入貪心算法對(duì)測試用例集進(jìn)行精簡。文獻(xiàn)[8]提出一種根據(jù)測試用例的重要性來選擇用例的啟發(fā)式方法，并用該方法實(shí)現(xiàn)冗余測試用例的刪減。在結(jié)合了貪心算法和啟發(fā)式算法優(yōu)點(diǎn)的基礎(chǔ)上，Chen和Lau[9-10]提出了一種新的測試用例集簡化的啟發(fā)式算法。此外，Lee和Chung[11]將簡化測試用例集問題轉(zhuǎn)化成整數(shù)規(guī)劃問題，并把整數(shù)規(guī)劃方法用于選擇測試用例，該方法可以保證選出的測試用例組成的用例集是最優(yōu)的簡化測試用例集。文獻(xiàn)[12]充分考慮測試目標(biāo)中測試需求之間的相互關(guān)系，劃分所有滿足測試需求的可用測試用例，從而形成一個(gè)測試用例集，然后再運(yùn)用上述算法進(jìn)行簡化。馬雪英[13]和全君林[14]分別研究了遺傳算法在測試用例集最小化中的應(yīng)用。申利民等[15]提出一種基于遺傳蟻群融合算法的測試用例最小化方法。

為了實(shí)現(xiàn)最小測試用例集的自動(dòng)生成，文中用一個(gè)測試用例滿足基本路徑集中的一個(gè)獨(dú)立路徑，通過獨(dú)立路徑表記錄測試需求滿足情況，給出最大穩(wěn)定遺傳算法(LSGA)[16]，并從概率角度理論證明其比基本遺傳算法優(yōu)越。最后通過實(shí)例分析表明，該算法比基本遺傳算法具有更高的效率。

2 LSGA算法

2.1 算法描述

第2步：將獲得的種群運(yùn)行待測程序。

第7步：檢驗(yàn)停止標(biāo)準(zhǔn)，若滿足則停止，否則K=K+1，并返回第2步。

2.2 構(gòu)造適應(yīng)度函數(shù)

在實(shí)際問題的應(yīng)用過程中，適應(yīng)度函數(shù)是LSGA算法和實(shí)際問題的接口，利用其評(píng)價(jià)最優(yōu)解。文中為了獲得最小測試用例集并且覆蓋待測程序中的所有路徑，記錄已經(jīng)覆蓋過的路徑，采用“鄰近者優(yōu)先”的原則，再動(dòng)態(tài)修正其適應(yīng)度值。具體算法實(shí)現(xiàn)如下：

第1步：初始化初始種群中每個(gè)個(gè)體的適應(yīng)度，一般為所要覆蓋的路徑數(shù)Cmax。

第4步：判斷是否覆蓋了待測程序的所有路徑，是則結(jié)束，否則進(jìn)入下一代操作，重復(fù)第2步。

2.3 算法性能分析

與GA算法相比，LSGA算法具有較強(qiáng)的效率。下面從概率角度對(duì)它的優(yōu)越性進(jìn)行描述和證明。

引理1：K代種群中，個(gè)體i滿足某個(gè)測試需求的概率：

證明：因?yàn)槎M(jìn)制個(gè)體串長為L，所以個(gè)體串最多有2L種位串?？紤]種群規(guī)模M與2L-1之間的關(guān)系，可以分為三種關(guān)系：M>2L-1，M=2L-1和M<2L-1。對(duì)于這三種關(guān)系，某代種群中可能含有多個(gè)相同的個(gè)體，即Z(i,k)>1，對(duì)于前兩種關(guān)系可能存在Z(i,k)=0，在第三種關(guān)系中一定存在Z(i,k)=0的情況。為了使Z(i,k)無論取什么值都不影響統(tǒng)計(jì)種群中個(gè)體i滿足某個(gè)測試需求的概率，這里使用加權(quán)概率統(tǒng)計(jì)法。

其中權(quán)值為個(gè)體i的適應(yīng)度值，可以表示為：

證畢。

引理1給出了評(píng)價(jià)個(gè)體滿足測試需求的概率公式，由此下面就可以利用該公式證明LSGA算法的優(yōu)越性。

定理1：個(gè)體i利用LSGA算法生成最小測試用例集的概率比GA算法大。

證畢。

定理2：LSGA算法能以概率滿足終止條件的迭代代數(shù)少于GA算法。

證明：根據(jù)輪盤賭選擇法計(jì)算概率可得到LSGA算法第K代終止的概率為：

GA算法第K代終止的概率為：

證畢。

3 實(shí)例分析

前面已經(jīng)從概率角度理論證明了LSGA算法比GA算法優(yōu)越，該算法仍然是啟發(fā)式方法，算法的有效性應(yīng)該通過實(shí)驗(yàn)來驗(yàn)證。本節(jié)通過軟件測試中常見的一個(gè)測試案例—直角三角形判定程序來驗(yàn)證LSGA算法的優(yōu)越性。

在研究過程中，筆者開發(fā)了最小測試用例集自動(dòng)生成的系統(tǒng)原型。系統(tǒng)通過分別調(diào)用LSGA算法包和GA算法包，分別記錄兩種算法生成最小測試用例集的迭代代數(shù)。由于初始種群是隨機(jī)生成的，為了保證數(shù)據(jù)的可信性，這里針對(duì)每個(gè)實(shí)驗(yàn)分別執(zhí)行10次，然后取其平均值。

3.1 實(shí)驗(yàn)驗(yàn)證

3.2 實(shí)驗(yàn)結(jié)果

對(duì)LSGA算法和GA算法得到最小測試用例集的運(yùn)行時(shí)間進(jìn)行了考察，結(jié)果如圖1、圖2所示。

從圖中可以很清晰地看出，利用LSGA算法生成最小測試用例集的運(yùn)行時(shí)間遠(yuǎn)小于用GA算法生成最小測試用例集的運(yùn)行時(shí)間，具有很好的效益。

圖1 實(shí)驗(yàn)1運(yùn)行時(shí)間對(duì)比圖

圖2 實(shí)驗(yàn)2運(yùn)行時(shí)間對(duì)比圖

4 結(jié)束語

文中對(duì)LSGA算法進(jìn)行了理論分析，該算法能很好地保證種群的最大穩(wěn)定性，提高搜索性能。首先從概率角度理論證明了LSGA算法優(yōu)越于GA算法，然后將算法用于實(shí)例驗(yàn)證。結(jié)果表明，利用該算法能較快生成最小測試用例集，從而實(shí)現(xiàn)對(duì)測試目標(biāo)的充分測試，提高測試效率，降低測試成本。

[1] Jones B F,Sthamer H H,Eyres D E.Automatic structural testing using genetic algorithms[J].Software Engineering Journal,1996,11(5):299-306.

[2] Hermadi I, Ahmed M A. Genetic algorithm based test data generator[C]//Proc of 2003 congress on evolutionary computation.[s.l.]:[s.n.],2003:85-91.

[3] Michael C C,McGraw G E,Schatz M A,et al.Genetic algorithms for dynamic test data generation[C]//Proc of 12th IEEE international conference on automated software engi-

neering.[s.l.]:IEEE,1997:307-308.

[4] Jones B F,Eyres D E,Sthamer H H.A strategy for using genetic algorithms to automate branch and fault-based testing[J].The Computer Journal,1998,41(2):98-107.

[5] Wegener J,Baresel A,Sthamer H.Evolutionary test environment for automatic structural testing[J].Information and Software Technology,2001,43(4):841-854.

[6] Eugenia D,Javier T,Raquel B.Automated software testing using a metaheuristic technique based on tabu search[C]//Proc of 18th IEEE international conference on automated software engineering.[s.l.]:IEEE,2003:310-313.

[7] Johnson D S.Approximation algorithms for combinatorial problems[J].Journal of Computer and System Sciences,1974,9(3):256-278.

[8] Harrold M J,Gupta R,Soffa M L.A methodology for controlling the size of a test suite[J].ACM Transactions on Software Engineering and Methodology,1993,2(3):270-285.

[9] Chen T Y,Lau M F.A new heuristic for test suite reduction[J].Information and Software Technology,1998,40(5-6):347-354.

[10] Chen T Y,Lau M F.Heuristics towards the optimization of the size of a test suite[C]//Proceedings of the 3rd international conference on software quality management.Seville,Espagne:[s.n.],1995:415-424.

[11] Lee J G,Chung C G.An optimal representative set selection method[J].Information and Software Technology,2000,42(1):17-25.

[12] 聶長海,徐寶文.一種最小測試用例集生成方法[J].計(jì)算機(jī)學(xué)報(bào),2003,26(12):1690-1695.

[13] 馬雪英,盛斌奎,葉澄清.用遺傳算法的測試用例最小化[J].計(jì)算機(jī)科學(xué),2007,34(1):285-288.

[14] 全君林,陸 璐.基于遺傳算法測試用例集極小化研究[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(19):58-61.

[15] 申利民,高 潔.基于遺傳蟻群融合算法的測試用例最小化研究[J].計(jì)算機(jī)工程,2012,38(16):57-60.

[16] 劉 冬,靳蓓蓓,闕向紅.基于LSGA的最小測試用例集自動(dòng)生成[J].微電子學(xué)與計(jì)算機(jī),2011,28(12):115-118.

Automatic Generation of Minimal Test Set Based on a Genetic Algorithm

LIU Dong1,2,JIN Bei-bei3,QUE Xiang-hong2

(1.Computing Center,First Affiliated Hospital of Wannan Medical College,Wuhu 241001,China; 2.Computing Center,Huazhong University of Science and Technology,Wuhan 430030,China; 3.Anhui Normal University,Wuhu 241000,China)

Test data generation is a complicated problem and its method and technique is not mature.In the process of the minimum test case generation,the Largest Steady Genetic Algorithm (LSGA) is proposed to improve the stability greatly,which is based on the basic genetic algorithm,in order to avoid repeat genetic manipulation of test case which has been met the testing requirement.This algorithm can guarantee the largest population stability and improve the search performance.Contrasted with the genetic algorithm,its superiority is proved from the perspective of the probability.Example analysis shows that using the proposed algorithm can rapidly generate minimum test case sets,achieving the target of the full test,improving the test efficiency and reducing test cost.

test set;test case;basic path set;simple genetic algorithm;software testing

2015-04-16

2015-08-18

時(shí)間：2016-03-22

國家自然科學(xué)基金專項(xiàng)基金項(xiàng)目(81141073);安徽省科技計(jì)劃項(xiàng)目(1301042203);安徽省高校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2015A241);蕪湖市科技計(jì)劃項(xiàng)目(2012hm35-1)

劉 冬(1979-),男,碩士,高級(jí)工程師,研究方向?yàn)檐浖y試、醫(yī)學(xué)信息處理等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1518.026.html

TP301.6

A

1673-629X(2016)04-0086-04

10.3969/j.issn.1673-629X.2016.04.019