利用遺傳算法進行測試用例自動生成

1、利用遺傳算法進行數(shù)據(jù)流分析下的測試用例自動生成摘要： 軟件測試越來越受到重視，但是軟件測試是一個復雜、工作量很大的過程。測試用例的自動生成在一定程度上能夠減小軟件測試的工作量， 但是測試用例自動生成技術是一個難點。 本文通過借鑒遺傳算法，基于數(shù)據(jù)流分析，在 def-use 路徑覆蓋的測試準則上，提出了一個測試用例自動生成的算法。并通過實驗比較了遺傳算法和隨機選擇法在測試用例自動生成上的優(yōu)劣。關鍵詞：軟件測試；數(shù)據(jù)流測試；遺傳算法； GA測試用例自動生成中圖分類號： TP311Automatic Test Data Generation for Data Flow Testing Using a

2、Genetic AlgorithmAbstract: Software testing is more and more important, but the software testing is complex and has heavy workload. The automatic generation of test cases can reduce the workload of software testing, but the automatic generation of test cases is a difficult problem. This paper introd

3、uces an automatic test case generation algorithm which uses genetic algorithm and is based on data flow analysis and is under the test criterion of the def-use path coverage. And compares the advantages and disadvantages between genetic algorithm and random selection method in the automatic generati

4、on of test cases.Key words: software testing; data flow testing; genetic algorithms; automatic test data generation1 引言軟件測試描述一種用來促進鑒定軟件的正確性、 完整性和質量的過程， 是一種實際輸出與預期輸出間的比較過程。 軟件測試主要包含兩方面的內(nèi)容， 測試用例生成和測試充分性準則的應用。 測試充分性準則包括基于控制流和基于數(shù)據(jù)流等， 是用來判定測試數(shù)據(jù)集對于被測試程序是否充分的準則。 軟件測試是一項費時費力且單調(diào)乏味的工作， 測試用例的自動生成能有效提高軟件測試的效率。

5、但是， 測試用例自動生成是軟件測試中的一個難點。 本文利 用遺傳算法對測試用例的自動生成進行探討。2 測試用例自動生成技術簡介2.1 軟件測試相關概念測試用例是為某個特殊目標編制的一組測試輸入、 執(zhí)行條件以及預期結果， 以便測試某個程序路徑或核實是否滿足某個特定需求。測試用例的設計應遵循下列原則 1 。（ 1）準確性：測試用例的設計必須有明確的目標，即針對需求設計測試用例。（ 2）可復用性：設計的測試用例應能在類似的情況下重復使用。（ 3）可追蹤性：測試用例必須能夠追溯到需求。（ 4）完整性：考慮到需求的完整性和邏輯完整性。測試用例自動生成方法可以分為三類，隨機的測試用例生成，結構導向的測試用

6、例生成和基于數(shù)據(jù)規(guī)格說明書的測試用例生成。隨機的測試用例生成從輸入變量的域中隨機產(chǎn)生測試用例。結構導向的測試用例生成基于覆蓋程序中特定的結構元素，比如路徑覆蓋，分支覆蓋和def-use 覆蓋等?；跀?shù)據(jù)規(guī)格說明書的測試用例生成從軟件的說明書中選擇測試用 例。本文所使用的測試用例自動生成技術屬于結構導向的測試用例自動生成技術，使用遺傳算法(genetic algorithm )迭代生成覆蓋全部 def-use路徑的測試用例。 2.2軟件測試的分類軟件測試按照運行狀態(tài)，可以分為靜態(tài)測試和動態(tài)測試。其中靜態(tài)測試是在不執(zhí)行程序 代碼而尋找程序代碼中可能存在的缺陷或評估程序代碼的過程。動態(tài)測試則以測試數(shù)

7、據(jù)為輸入，通過執(zhí)行程序來檢驗程序的動態(tài)行為和運行結果以發(fā)現(xiàn)缺陷。圖1為軟件測試分類的一個例子。本文的軟件測試方法屬于動態(tài)測試中的白盒測試，是基于數(shù)據(jù)流測試中的全定義使用覆蓋。;購春泅試技術)I.M值至亙西) 口連藏而)5盤逑 次,控制而引a判定*動他分析全佗用覆蓋圖1軟件測試技術的分類Fig.1 Classification of the software testing technologies3數(shù)據(jù)流分析技術程序的控制流可以表示出有向圖的形式，其中每個節(jié)點表示可以順序執(zhí)行的語句，其中不包括分支，形成一個基本的語句塊；每條邊表示節(jié)點間控制流的可能的轉移。路徑就是由邊連接起來的節(jié)點的有限序列。

8、完全路徑指路徑的第一個節(jié)點是程序的開始節(jié)點，最后一個節(jié)點是程序的終止節(jié)點。一個變量的def-clear路徑指的是該路徑中不包括改變量的一個新的定義。數(shù)據(jù)流分析把焦點放在變量的定義和使用上。而變量的使用又可以分為“c-use ”和“p-use"，c-use指的是變量被用來計算，而 p-use指的是變量被用來進行判定，是判 定語句的一部分。變量的c-use被和節(jié)點相關聯(lián)，而p-use則被與邊相關聯(lián)。數(shù)據(jù)流分析的 目標就是找出變量的所有定義以及和該定義相關聯(lián)的所有使用。這樣的數(shù)據(jù)流關系可以被分為下面兩類。dcu(i)和dpu(i,j) 。dcu(i)指的是這樣一個變量定義的集合，存在一條到

9、節(jié) 點i上的def-clear 路徑,而節(jié)點i包括該變量的一個 c-use ; dpu(i,j)則指的是這樣一個變量定義的集合，存在一條到變量(i,j )的def-clear 路徑，而該邊包括一個該變量的p-use。Reach(i)指的是所有能到節(jié)點i的定義，也就是存在一條def-clear 路徑,能從該變量 的定義節(jié)點到i節(jié)點。Avail(i)指的是所有在節(jié)點i可得到的變量定義，它既包括在節(jié)點i對某變量的定義，也包才所有能到達節(jié)點i并且在節(jié)點i上沒有進行重新定義的變量定義。因此，dcu(i)和dpu(i,j)可由下式計算得到。dcu(i):= reach(i)- c-use(i);dpu(i

10、,j):=avail(i)- p-use(i,j)其中，c-use(i) 指的是在節(jié)點i上存在c-use的變量，p-use(i,j) 指的是在邊(i,j ) 上存在p-use的變量。全路徑就是指從每個變量的定義到該變量每個使用的def-clear 路徑,他可以分成dcu-path和dpu-path兩類。每個Dcu-path可以表示成一個定義節(jié)點，一個c-use節(jié)點，killing nodes集合。Killingnodes是指那些不能包含在 dcu-path 中的節(jié)點，也就是那些對變量的重新定義。Dpu-path可以表示成定義節(jié)點，一個p-use邊以及killing nodes 集合。例如下圖是

11、一個樣例程序。其中語句旁的第一列數(shù)字是語句編號，第二列是語句所屬節(jié)點的編號。1 1INTEGER X,Y,Z12 RELSE21READ(5,*)XtYjZ131F(X.GE.Y)THEN31MII>Z14gMID=Y41出(YLT0THEN1510ELSE52F(X.LT.Y)T1IEN16ioIF(X.GT.Z)TIIEN63MID=Y17iiMID=X74ELSE他12END IF84IF(X.LT2)THEN1913END IF95MID-X2014END IF106ENDJF2114PR1NT*JM】DDLE VALUE=* MIDII7END IF2214END圖2樣例程序F

12、ig.2 Example program其對應的dcu-path如下表。表1樣例程序dcu-path列表Tab.1 List of the dcu-paths of the example programDcu-path 編號變量定義節(jié)點C-use節(jié)點Killing nodes1y13無2x15無3y19無4x111無5mid1143,5,9,116mid3141, 5,9,117mid5141,3,9,118mid9141,3,5,119mid11141,3,5,9其對應的dpu-patn如下表表2樣例程序dpu-path列表Tab.2 List of the dpu-paths of th

13、e example programDpu-path 編號變量定義節(jié)點P-use 邊Killing nodes1y11-2無2z11-2無3y11-8無4z11-8無5x12-3無6y12-3無7x12-4無8y12-4無9x14-5無10z14-5無11x14-6無12z14-6無13x18-9無14y18-9無15x18-10無16y18-10無17x110-11無18z110-11無19x110-12無20z110-12無4遺傳算法簡介4.1 遺傳算法相關概念簡介遺傳算法借鑒了自然界中的適者生存以及遺傳學中的交叉變異現(xiàn)象。遺傳算法從一個群體中選出一部分適應度較高的個體，以一定的概率對選出來

14、的個體進行交叉和變異操作。通過遺傳操作，使優(yōu)良品質被不斷保留、組合，從而不斷產(chǎn)生出更佳的子個體，子代個體中包含父代個體的大量信息，并在總體上勝過父代個體，從而使群體向前進化發(fā)展。經(jīng)過不斷迭代，將會產(chǎn)生滿足要求的群體，或者在迭代次數(shù)達到一定值時，停止算法。交叉操作就是交換兩個染色體中的部分內(nèi)容，變異操作是改變某個染色體的部分內(nèi)容。遺傳算法的有關概念術語定義如下。個體：模擬生物個體而對問題中的對象(本文中是一個測試用例)的一種稱呼。種群：模擬生物種群而由若干個體組成的群體(本文中是一組測試用例)。適應度：借鑒自然界中生物個體對環(huán)境的適應程度，而對問題中的個體對象所涉及的表征其優(yōu)劣的一種測度。染色體

15、：問題中個體的某種字符串形式的編碼表示。編碼與解碼：遺傳算法中兩個必須的數(shù)據(jù)轉換操作，把搜索空間中的參數(shù)或解轉換成遺傳空間中的染色體的操作成為編碼，反之為解碼。遺傳算法的整體結構如下。Simple Genetic Algorithm。Initialize population;Evaluation population;While termination criterion not reached Select solutions for next population; Perform crossover and mutation; Evaluate population;4.2 編碼操作染

16、色體編碼需要遵循以下幾個原則：2(1)輸入?yún)?shù)所能取得的任何值都應存在相應的唯一編碼。(2)任何一個編碼都應存在唯一的參數(shù)值與之對應。(3)選擇使問題得以自然表達的最小字母表進行編碼。(4)編碼方法應和問題本身的相關性大、結合緊密。根據(jù)這幾個原則，我們設計了對應的編碼方法。假設我們有k個變量，每個變量的取值范圍是Di=ai,b,再假設每個變量的精度是di，為了達到這樣一個精度 R應該變成(bi-3)*10di。mi應該取值成一個最小的整數(shù)，滿足(bi- a) *10di <= 2吸1。這樣每個變量就可以 被表示成長度為mi的0-1字符串。將這個字符串轉換成原數(shù)據(jù)的方法如下公式。, bi

17、- ai Xi = ai + Xi * (2Ami) -1例如，假設有變量 x, y, -3.0<=x<=12.1, 4.1<=y<=5.8,且需要的精度是 4,也就是保留4位小數(shù)。X的定義域的長度是12.1- (-3) =15.1。所以我們希望編碼后的字符串的長度能夠 表示15.1*10000。此外，2A17 < 151000 <=2A18 ,所以mx應取值18,也就是用 18位0-1字 符串對x進行編碼。同理可得，my應取值17,所以對x,y進行編碼需要33位長的字符串。假設對x,y編碼后的字符串是 010001001011010000111110010

18、100010 ,此時前18位表示的 是x,后17位表示的是y。有上式計算可得，x = 1.0542, y=5.7553。4.3 適應度的計算對種群的初始化就是隨機產(chǎn)生個pop-size個m位的0-1字符串，其中pop-size是種群的大小。算法根據(jù)每個測試用例新覆蓋的def-use路徑的數(shù)量來計算對應的適應度。測試用例m的適應度計算方法如下。1.1 新覆蓋的def - use路徑數(shù)量 eVal(Vi)=總共的路徑數(shù)量適應度是遺傳算法唯一的反饋。當某測試用例的適應度大于0時，我們認為這個測試用例是有效的。4.4 個體的選擇從有效的個體中選擇一部分以產(chǎn)生下一代種群，當種群中沒有有效的個體時，我們將

19、選擇整個種群以產(chǎn)生下一代種群。選擇的方法主要有兩類，輪盤選擇法和隨機選擇法。輪盤選擇法將一個圓分為種群大小個扇形區(qū)間，區(qū)間大小與該區(qū)間所代表的染色體的適應度成正比。設一固定指針，轉動輪盤，等其停止后，指針指向的區(qū)間對應的染色體即被選中。輪盤的創(chuàng)造算法如下。(1)計算每個染色體的適應度eval(v i) o(2)計算整個種群的適應度F = £ iyeevalWi)。(3)計算每個有效染色體被選中的概率pi = eval(v i)/F 。 P也是染色體占據(jù)的扇形面積的比例。(4)為每個染色體計算一個累計概率qi = £ ijpj。選擇一個染色體的算法如下。(1)隨機產(chǎn)生一個 0

20、到1之間的浮點數(shù)r。(2)如果r < q 1,就選擇染色體v1,否則如果qi-1 < r <=q i,那么就選擇染色體 vi。重復pop_size次，就選擇了 pop_size個染色體參與遺傳操作。隨機選擇法就是從有效染色體中隨機選擇pop_size個參與遺傳操作，每個染色體被選中的概率相等。算法如下。(1)假設有效染色體的個數(shù)是l ,那么將染色體從 0到l編號。(2)隨機產(chǎn)生一個 0到l之間的整數(shù)，選擇相應編號的染色體。重復這個過程pop_size次，就選擇了 pop_size個染色體參與遺傳操作。4.5 遺傳操作遺傳操作有交叉和變異。交叉操作指通過一對雙親個體中的遺傳信息

21、進行隨機重組，產(chǎn)生與雙親遺傳信息相同、 組合不同的新個體。交叉操作分為單點交叉和多點交叉，如下圖 3。圖3單點交叉Fig.3 One-point crossover圖4多點交叉Fig.4 Multi-point crossover本文采用的是單點交叉。在進行交叉操作前，還要先選取要進行交叉操作的染色體。選取染色體根據(jù)概率 pc進行，取值范圍通常是0.40.99。選取染色體的算法如下。(1)為每個染色體進行下面兩步的操作。(2)隨機產(chǎn)生一個 0到1之間的浮點數(shù)r。(3)如果r < pc,就選取相應的染色體。由此，我們選取了要進行交叉操作的染色體。對每一對染色體，算法隨機產(chǎn)生一個區(qū)間在1,m

22、-1的整數(shù)pos以表示交叉操作的起始位置，其中m是染色體的長度。對染色體b1b2, bposbpos+1, bm和 Ci, CposCpos+1 , Cm進行父叉操作后，變換為b1b2, bposCpos+1, Cm和Ci , Cposbpos+1, bmo變異操作指單獨改變個體內(nèi)一個或者多個基因座上的基因而產(chǎn)生新的個體。變異發(fā)生在染色體的各個位上，根據(jù)一個變異概率pm進行變異，取值范圍通常是0.00010.1 ,所以期望的變異位數(shù)是 pm*m*pop_size。每個染色體的每一位都有相同的概率變異。對交叉操作后 的每個染色體在每一位上進行如下操作。(1)隨機產(chǎn)生一個 0到1之間的浮點數(shù)r。(

23、2)如果r < pm,則對該位進行變異操作，將 0變異成1或將1變異成0。5實驗分析程序結果用到一個整型的向量，叫做 define-use coverage vector ,用于記錄每個 def-use路徑對應的測試用例。樣例程序對應的define-use 覆蓋向量如下表。表3樣例程序的def-use覆蓋向量Tab.3 The def-use coverage vector of the example programDcu-path123456789測試用例31029131029Dpu-path12345678910測試用例33113310101010Dpu-path111213141

24、51617181920測試用例121222119911其中，測試用例對應的編號是程序運行過程中測試用例生成時的順序。上表是利用遺傳算法自動生成測試用例的結果。為了比較遺傳算法和隨機算法在自動生成測試用例方面的優(yōu)劣，實驗在15個FORTRAN程序上分別運行遺傳算法和隨機法。其中遺傳算法設定 pc = 0.8,pm = 0.15。得到的程序運行結果如下表。表4遺傳算法與隨機算法的比較Tab.4 A comparison between the GA technique and the random testing technique程序編號變量個數(shù)種群大小方法迭代次數(shù)測試用例個數(shù)覆蓋率138遺傳算

25、法46100隨機算法26100238遺傳算法16100隨機算法27100338遺傳算法34100隨機算法354100438遺傳算法164100隨機算法284100538遺傳算法18681.3隨機算法26681.3648遺傳算法38100隨機算法58100738遺傳算法45100隨機算法9151008310遺傳算法151063.6隨機算法51958.4928遺傳算法13100隨機算法441001018遺傳算法75100隨機算法351001118遺傳算法2592隨機算法45921238遺傳算法55100隨機算法9151001324遺傳算法5396隨機算法23961418遺傳算法2663.6隨機算法

26、15663.61538遺傳算法81187.2隨機算法16981.7從上表可以發(fā)現(xiàn)遺傳算法有12個運行的都比隨機算法好， 其中有10個只需要更小的迭代次數(shù)就能達到相同的覆蓋率而第8個和第15個，遺傳算法使用了更少了迭代次數(shù)達到了更高的覆蓋率。所以，遺傳算法的性能優(yōu)于隨機算法。為了比較遺傳算法中，輪盤選擇法和隨機選擇法的優(yōu)劣，實驗在上述的15個程序中運行了分別采用輪盤選擇法和隨機選擇法的遺傳算法，實驗結果如下。表5輪盤選擇法和隨機選擇法的比較Tab.5 A comparison between parent selection methods used in the GA technique程序編號選擇方法迭代次數(shù)測試用例個數(shù)覆蓋率1輪盤選擇法46100隨機選擇法461002輪盤選擇法16100隨機選擇法161003輪盤選擇法34