劉 冬，靳蓓蓓，闕向紅

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

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

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

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

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

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

1 概 述

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

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

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

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

2 LSGA算法

2.1 算法描述

第2步：將獲得的種群運行待測程序。

第7步：檢驗停止標準，若滿足則停止，否則K=K+1，并返回第2步。

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

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

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

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

2.3 算法性能分析

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

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

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

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

證畢。

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

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

證畢。

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

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

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

證畢。

3 實例分析

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

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

3.1 實驗驗證

3.2 實驗結(jié)果

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

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

圖1 實驗1運行時間對比圖

圖2 實驗2運行時間對比圖

4 結(jié)束語

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

[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].計算機學報,2003,26(12):1690-1695.

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

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

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

[16] 劉 冬,靳蓓蓓,闕向紅.基于LSGA的最小測試用例集自動生成[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

時間：2016-03-22

國家自然科學基金專項基金項目(81141073);安徽省科技計劃項目(1301042203);安徽省高校省級自然科學研究重點項目(KJ2015A241);蕪湖市科技計劃項目(2012hm35-1)

劉 冬(1979-),男,碩士,高級工程師,研究方向為軟件測試、醫(yī)學信息處理等。

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