利用遺傳算法進(jìn)行測試用例自動(dòng)生成

1、利用遺傳算法進(jìn)行數(shù)據(jù)流分析下的測試用例自動(dòng)生成摘要： 軟件測試越來越受到重視，但是軟件測試是一個(gè)復(fù)雜、工作量很大的過程。測試用例的自動(dòng)生成在一定程度上能夠減小軟件測試的工作量， 但是測試用例自動(dòng)生成技術(shù)是一個(gè)難點(diǎn)。 本文通過借鑒遺傳算法，基于數(shù)據(jù)流分析，在 def-use 路徑覆蓋的測試準(zhǔn)則上，提出了一個(gè)測試用例自動(dòng)生成的算法。并通過實(shí)驗(yàn)比較了遺傳算法和隨機(jī)選擇法在測試用例自動(dòng)生成上的優(yōu)劣。關(guān)鍵詞：軟件測試；數(shù)據(jù)流測試；遺傳算法； GA測試用例自動(dòng)生成中圖分類號(hào)： 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 引言軟件測試描述一種用來促進(jìn)鑒定軟件的正確性、 完整性和質(zhì)量的過程， 是一種實(shí)際輸出與預(yù)期輸出間的比較過程。 軟件測試主要包含兩方面的內(nèi)容， 測試用例生成和測試充分性準(zhǔn)則的應(yīng)用。 測試充分性準(zhǔn)則包括基于控制流和基于數(shù)據(jù)流等， 是用來判定測試數(shù)據(jù)集對(duì)于被測試程序是否充分的準(zhǔn)則。 軟件測試是一項(xiàng)費(fèi)時(shí)費(fèi)力且單調(diào)乏味的工作， 測試用例的自動(dòng)生成能有效提高軟件測試的效率。

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

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

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

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

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

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

11、一個(gè)樣例程序。其中語句旁的第一列數(shù)字是語句編號(hào)，第二列是語句所屬節(jié)點(diǎn)的編號(hào)。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其對(duì)應(yīng)的dcu-path如下表。表1樣例程序dcu-path列表Tab.1 List of the dcu-paths of the example programDcu-path 編號(hào)變量定義節(jié)點(diǎn)C-use節(jié)點(diǎn)Killing nodes1y13無2x15無3y19無4x111無5mid1143,5,9,116mid3141, 5,9,117mid5141,3,9,118mid9141,3,5,119mid11141,3,5,9其對(duì)應(yīng)的dpu-patn如下表表2樣例程序dpu-path列表Tab.2 List of the dpu-paths of th

13、e example programDpu-path 編號(hào)變量定義節(jié)點(diǎn)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 遺傳算法相關(guān)概念簡介遺傳算法借鑒了自然界中的適者生存以及遺傳學(xué)中的交叉變異現(xiàn)象。遺傳算法從一個(gè)群體中選出一部分適應(yīng)度較高的個(gè)體，以一定的概率對(duì)選出來

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

15、：問題中個(gè)體的某種字符串形式的編碼表示。編碼與解碼：遺傳算法中兩個(gè)必須的數(shù)據(jù)轉(zhuǎn)換操作，把搜索空間中的參數(shù)或解轉(zhuǎn)換成遺傳空間中的染色體的操作成為編碼，反之為解碼。遺傳算法的整體結(jié)構(gòu)如下。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、色體編碼需要遵循以下幾個(gè)原則：2(1)輸入?yún)?shù)所能取得的任何值都應(yīng)存在相應(yīng)的唯一編碼。(2)任何一個(gè)編碼都應(yīng)存在唯一的參數(shù)值與之對(duì)應(yīng)。(3)選擇使問題得以自然表達(dá)的最小字母表進(jìn)行編碼。(4)編碼方法應(yīng)和問題本身的相關(guān)性大、結(jié)合緊密。根據(jù)這幾個(gè)原則，我們?cè)O(shè)計(jì)了對(duì)應(yīng)的編碼方法。假設(shè)我們有k個(gè)變量，每個(gè)變量的取值范圍是Di=ai,b,再假設(shè)每個(gè)變量的精度是di，為了達(dá)到這樣一個(gè)精度 R應(yīng)該變成(bi-3)*10di。mi應(yīng)該取值成一個(gè)最小的整數(shù)，滿足(bi- a) *10di <= 2吸1。這樣每個(gè)變量就可以 被表示成長度為mi的0-1字符串。將這個(gè)字符串轉(zhuǎn)換成原數(shù)據(jù)的方法如下公式。, bi

17、- ai Xi = ai + Xi * (2Ami) -1例如，假設(shè)有變量 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應(yīng)取值18,也就是用 18位0-1字 符串對(duì)x進(jìn)行編碼。同理可得，my應(yīng)取值17,所以對(duì)x,y進(jìn)行編碼需要33位長的字符串。假設(shè)對(duì)x,y編碼后的字符串是 010001001011010000111110010

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

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

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

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

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

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

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

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

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