基于改進遺傳算法的測試用例生成研究與仿真

林亞娜

基于改進遺傳算法的測試用例生成研究與仿真

林亞娜

（福州理工學院 計算與信息科學學院，福建 福州 350506）

提出一種基于改進遺傳算法的測試用例自動生成工具，改進的遺傳算法通過路徑構建方法構建目標路徑矩陣集合以及實際路徑矩陣，通過對比目標路徑矩陣與實際路徑矩陣差異設計適應度函數，通過歸一化處理得到適應度值，最后根據適應度值調節遺傳算子，得到問題的最優解集合進而得到全部測試數據。工具通過可視化界面操作實現待測程序的自動插樁、自動生成覆蓋全部路徑的測試用例并代入程序進行測試，最后反饋生成測試結果。改進的算法能夠提高算法收斂速度，降低早熟程度，在覆蓋率及準確度相同的情況下，工具生成用例可以減少測試數據生成時間，達到節省測試成本、提高測試效率的效果。

遺傳算法；自動化測試；適應度函數；遺傳算子

軟件測試工作是軟件質量保證的重要手段[1]。據統計，約80%的軟件缺陷是在單元測試階段發現的[2]。基于路徑覆蓋的白盒測試方法是單元測試階段的重要方法之一，通過手工設計測試用例來覆蓋程序的全部路徑不僅需要花費大量的人力和時間成本，在路徑覆蓋程度方面也很難達到預期的目標。因此，通過算法自動生成測試用例變得尤為重要，在基于路徑覆蓋的測試中，生成測試用例可歸結為尋找有效路徑問題，遺傳算法是解決該問題的一個較成熟的方法。標準的遺傳算法可能產生早熟現象，可能將局部最優解誤認為是全局最優解，難以保證生成測試數據的質量[3]。筆者提出將改進的遺傳算法應用于測試用例自動生成，針對白盒測試中的路徑覆蓋方法，設計自動生成測試用例工具（以下簡稱工具），改進的遺傳算法通過對適應度函數的改進，加快算法的收斂速度，將遺傳算子做自適應的改變，降低算法早熟程度，針對待測程序生成覆蓋多個目標路徑的測試用例，達到一次運行生成覆蓋全部目標路徑的測試用例的效果。將改進的算法研究轉化為實際應用的工具軟件，收集實踐成果的同時也可以提高單元測試中的路徑覆蓋測試的工作效率，節省人力、時間等方面的成本。

1 改進的遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種模擬自然界的進化規律，由Holland[4]在20世紀60年代首次提出，該算法屬于進化算法，是一種通過選擇、交叉、變異操作生成優化搜索問題解決方法的算法。算法優勢在于能夠并行搜索且效率較高[5]。

測試數據的自動生成可以看作遺傳算法通過不斷進化生成符合目標路徑的測試數據的過程[6]。遺傳算法中最關鍵的步驟是算法適應度函數的設計，在標準遺傳算法中，遺傳算子即交叉率、變異率均被設置為固定不變的值，針對待測程序的具體情況不同，固定的遺傳算子無法將算法特點發揮到最優狀態，因此通過設計自適應的遺傳算子可以在遺傳算法執行過程中動態調整算子的值，加速獲取符合目標路徑的測試數據，提高生成有效數據的效率。

1.1 路徑構建

改進的遺傳算法將生成的測試數據代入被測程序，通過待測程序插樁，獲得生成數據對應的實際路徑，記為一維數組PA[]，數組中的元素個數表示該條路徑經過的節點個數，數組中的每個元素表示節點個數的遞減數，每個元素用正、負代表當前分支的走向，元素為正數，表示該元素對應的分支走了為真的方向，而元素為負數，則表示該元素對應的分支走了為假的方向。例如，某條測試數據代入被測函數后，發現經過的路徑有3個節點，前兩個節點走真分支，最后一個節點走假分支，則該路徑記為PA={3,2,-1}。

分析待測程序，利用程序插樁插入的探針，獲得被測程序的全部路徑集合，用二維數組P[][]表示，其中，表示全部路徑數量，[]則對應各條路徑，P[][]表示路徑集合中第條路徑的第個節點的元素值。

1.2 適應度函數設計

適應度函數在遺傳算法中體現了優勝劣汰的進化原則，是遺傳算法的關鍵[7]。改進的算法通過比較實際路徑PA與目標路徑集合中所有路徑的相似程度的平均值作為當前測試數據的適應度。

通過1.1的路徑構建，對比兩條路徑的相似程度可以看作對比兩個元素個數相同的一維數組的相似程度，從第一個節點開始一一對比，根據路徑構建原則，如果兩條路徑的第一個分支點就是相反的，即實際路徑的第一個節點走真分支，目標路徑的第一個節點走假分支，則認為兩條路徑的不匹配程度比較大，也就是說越靠前的節點出現不匹配的情況越能夠影響兩條路徑的相似程度，造成兩條路徑相似程度越低。因此，設計適應度函數為兩條路徑對應位置元素帶符號做乘法后，將所有元素做乘法后的結果相加，得到的結果為適應度值，為便于比較，將適應度值與目標路徑的各個元素的平方和做除法，將數值進行歸結到[-1,1]的閉區間處理，得到適應度值，如下式

Fitness = [(3*(-3))+(2*(-2))+(1*1)]/[32+ (-2)2+ 12]=-12/14 = -0.86

按公式(1)計算出的適應度，最差情況，即所有元素全部不匹配的情況，得到適應度為-1，各個元素全部匹配得到的適應度為1。

1.3 遺傳算子自適應設計

遺傳算子是算法的核心部分之一，算子的設定影響著遺傳算法的搜索能力和效率[8]。在標準的遺傳算法中，交叉率、變異率等算子均為固定值，針對待測對象情況，固定的遺傳算子值將不符合實際情況，而隨著算法的進行，將會出現偏離最優解的情況，自適應的調整遺傳算子會隨著算法的運行，適當增加種群多樣性，避免陷入算法早熟收斂，提高獲取最優解的效率[9]，對遺傳算子的動態改進將對算法的優化能力起到輔助作用。

設定初始的交叉率、變異率，在算法運行過程中，個體的適應度與種群的平均適應度比較，當個體適應度小于種群平均適應度時，說明個體需要提高變異、交叉概率以提高物種多樣性，提高交叉率、變異率；當個體適應度大于種群平均適應度時，則相反，降低交叉率、變異率。

為了便于表示交叉率、變異率升高或降低的程度，首先將個體的適應度值做歸一化處理，根據公式(1)，計算個體適應度得到的值在[-1,1]閉區間，利用如下公式(2)將適應度做歸一化，將新的適應度值控制在[0,1]的閉區間內。

公式(2)中Fitness'表示歸一化后的個體適應度值，Min表示原適應度閉區間的最小值，即-1；Max表示原適應度閉區間的最大值，即1。按公式(2)變換后，如上案例中的新的個體適應度值變為：

Fitness’ = [-0.86-(-1)]/[1-(-1)] = 0.14/2 = 0.07

將歸一化處理后的適應度值用于如下公式（3）、（4），得到交叉率Pcross和變異率Pmutation的自適應變化后的值。

2 自動生成測試用例工具設計

基于改進遺傳算法的自動生成測試用例工具主要針對Java語言開發的程序進行自動化測試用例的生成，工具的開發前臺使用JSP、JavaScript、CSS樣式等進行繪制頁面，后臺環境配置如表1所示。

表1 工具后臺環境配置

以改進的遺傳算法為核心，測試用例自動生成工具針對用戶導入的待測程序，可一次性生成所有目標路徑對應的測試用例，并將測試用例返回結果反饋給用戶，以評價程序是否存在缺陷。工具實現了基于B/S模式的測試用例自動生成功能，目前主要設計三個功能頁面，即準備測試、測試數據生成、測試結果反饋。其中核心功能為測試數據生成。整體開發功能流程如圖1所示，工具代碼結構如圖2所示。

圖1 基于改進遺傳算法的自動生成測試用例工具功能流程圖

圖2 自動生成測試用例工具代碼結構

整體代碼分為四個部分，分別用于存放待測程序、改進遺傳算法、Servlet以及JSP頁面等。首先，testedPro包中為待測程序以及經路徑構建后的程序（帶_Modify.java）；其次，ga包中為改進遺傳算法；第三，recreate、resultfile包中存放Servlet，用于接收工具頁面輸入，并針對頁面輸入參數做相關處理，其中ReCreateServlet.java用于接收測試準備頁數據，獲取到待測原文件，讀取原文件內容并通過1.1中路徑構建方法進行路徑構建，并生成新的待測文件，存放在testedPro包中，GetResult用于獲取測試數據自動生成頁面中的設定值，調用改進的遺傳算法方法（AllOnesGA.java），最終獲取測試數據集合并將其傳遞給測試結果反饋頁面；最后，webapp下存放工具的主要功能界面，分別是測試準備頁、測試數據自動生成頁以及測試結果反饋頁。

2.1 測試準備

在測試數據準備階段，界面預留了需求編號、設計編號、程序編號三個輸入框，以便于將生成測試用例快速地與需求階段的需求規格說明、設計階段的設計書以及編碼階段的程序一一對應，利用這三個編號自動生成測試用例的標識，也為工具的后期功能擴展預留接口。模擬準備測試頁面如圖3(a)所示。

圖3 工具頁面

需求編號、設計編號、程序編號可通過手工輸入，需上傳待測程序，僅支持上傳一個.java文件，以上四個字段帶有星號標記，為必須輸入字段；點擊下一步，工具檢測三個編號是否輸入以及待測程序是否上傳，檢查通過后點擊下一步，進入測試數據自動生成頁面。

在跳轉到下一個頁面之前，工具后臺程序需完成如下兩步：

以待測程序為基礎，通過1.1的路徑構建原則，生成一個新的插樁后的待測程序，新的程序命名在原程序名后加后綴“_Modify”。

讀取待測插樁后程序文件內容，找出程序中的所有方法，并確定每個方法的輸入變量類型以及輸入順序，傳遞給下一個測試數據自動生成頁面。

2.2 測試數據自動生成

在測試數據自動生成頁面，將上一步上傳的被測程序名顯示出來，通過分析程序，檢測出待測程序中的方法并羅列出來，前面加復選框，用戶可以選擇需要生成用例的方法。選中某方法后，下面會對應出現初始種群數、初始交叉率、初始變異率的設置界面，用戶可以根據方法的復雜程度設置需要的參數，交叉率和變異率會隨著遺傳算法的執行，根據公式（2）、（3）、（4）進行自適應的調整，界面如圖3(b)所示。

點擊開始生成用例按鈕，出現進度條及進度提示信息，后臺程序開始根據頁面選中的方法逐個生成測試用例，以選中一個方法為例，按如下步驟說明程序執行過程：

步驟一：利用生成的插樁程序獲取測試數據自動生成頁面選中方法的目標路徑集合。

步驟二：利用改進的遺傳算法，即1.2適應度函數的設計以及1.3自適應的交叉率、變異率的設計，生成第t代測試數據（t=1，2，3…）。

將情景教學應用在護理帶教服務當中,可以有效的提高護理實習生在專業知識方面的掌握程度、實踐操作能力以及應急能力等多方面的能力,在制定計劃時可以評估患者的綜合素質,并將患者所存在的共性、個性問題進行針對性考慮和分析,將改進措施規劃在循環計劃當中,并實施計劃,借助和實習生共同制定的計劃進行護理教學,可以顯著提升護理教學的價值與意義,同時借助情景教學可以實現護理教學質量的循環性提升作用,達到一個良性循環,從而實現不斷提升護理實習生護理能力的目標[4]-[5]。

步驟三：循環當前種群中的個體即測試數據，代入插裝后的被測程序，獲得測試數據對應的實際路徑，進行當前個體即測試數據適應度的計算，具體流程如圖4所示。

流程中的過濾目標路徑集合中不可能匹配路徑即尋找目標路徑集合中所包含元素個數與實際路徑元素個數不同的路徑。路徑中元素個數代表了測試數據在被測程序中經過的分支，如果分支數不同則證明路徑不可能匹配，因此計算不可能匹配路徑的相似程度是沒有意義的。

圖4 計算個體適應度流程圖

步驟四：當如上圖4中的目標路徑集合中沒有目標路徑時，表示所有目標路徑均找到測試數據，程序結束，將找到的所有測試數據以及代入程序后獲得的結果反饋給下一頁面即測試結果反饋。

2.3 測試結果反饋

將改進的遺傳算法針對每個方法返回的測試數據以及輸出結果逐條列出，用戶可以在工具的測試結果反饋頁面查看數據生成情況，核對預期結果與實際結果是否一致，判斷程序是否存在異常，支持將選中的方法對應的測試用例導出到excel表格中。具體頁面如圖3(c)所示。

頁面中的測試用例編號由圖3(a)測試準備頁輸入的需求編號、設計編號、程序編號、測試用例序號組成，為未來自動生成測試用例工具向需求、設計、編碼階段的拓展預留接口，工具將在生成的測試用例上面提示選中方法目標路徑條數以及生成的測試用例個數。

3 仿真實驗

為了驗證基于改進的遺傳算法的自動生成測試用例工具的可用性，以基礎程序中判斷三角形程序為例展開仿真實驗，首先針對待測程序進行人工分析，得到目標路徑，然后將待測程序導入工具，利用工具按步驟實施，導出測試用例結果，最后對比人工分析與工具生成的結果，驗證工具的可用性。

3.1 仿真實驗準備

實驗環境配置為2.3 GHz四核Inter（R）i5-6300HQ處理器，8 GB內存，Windows10操作系統，Eclipse版本：2019-09 R (4.13.0)，JVM版本1.8.0_121。

改進的遺傳算法默認的種群數量為50，變異率為0.9，交叉率為0.3，這三個參數僅作為用戶參考數值，具體數值可以通過工具的測試用例生成頁面進行調整修改。

3.2 待測程序分析及工具仿真

分析三角形問題源程序，三角形問題的輸入值為3個整型變量，表示輸入的三條邊，分析三邊數值判斷三角形類別，能夠得出的情況有一般三角形、等腰三角形、等邊三角形、直角三角形以及不能構成三角形。

人工分析采用McCabe的基本路徑測試方法，在白盒測試中基本路徑分析法被認為是嚴謹而有效的測試方法[10]，基本思想是分析程序控制流圖中的結構環路復雜度，導出基本路徑集合，并以此為依據設計測試用例。控制流圖由節點和邊構成，通過節點和邊計算程序結構復雜程度，又稱為圈復雜度，代表程序中的目標路徑數。控制流圖中表示邊的數量，表示節點個數，表示待測程序，其環路復雜度公式可表示為：

()=-+2，

最后得到所有的目標路徑。

首先分析源程序，待測程序如下圖5所示。

圖5 待測程序判斷三角形源代碼

其次，根據如上源代碼繪制程序流程圖，如下圖6所示。

圖6 判斷三角形程序流程圖

根據流程圖繪制控制流圖如下圖7所示。控制流圖節點的數字表示對應圖5中源程序的行數。

圖7 被測程序-判斷三角形程序控制流圖

根據控制流圖可得邊的個數= 14，節點個數= 11，根據圈復雜度計算公式可得

然后根據控制流圖找到5條目標路徑。根據目標路徑，可人工設計測試用例如下表2所示。

表2 人工設計的測試用例表

3.3 工具仿真

通過工具實現自動生成測試用例并將結果導出到excel中。首先將待測程序Angles.java上傳到測試準備頁，并填寫需求編號、設計編號以及程序編號；后臺根據路徑構建原則進行程序插裝并生成新的待測程序Angles_Modify.java，并獲取待測程序中的方法名及輸入變量個數、類型等信息，在測試數據自動生成頁面，針對所選待測方法，設置初始的遺傳因子，遺傳算法運行過程中，遺傳因子會根據公式(3)、(4)隨著反饋結果的情況自適應地調整；在反饋結果頁面，顯示出全部生成的測試用例，并支持導出所有測試用例。

以三角形問題為例，工具生成的測試用例如表3所示。

表3 工具生成的測試用例

表3中的覆蓋路徑指根據路徑構建原則，對應測試數據經過的構建后的路徑，因三角形待測程序中存在4個分支點，見圖5程序源代碼。根據路徑構建原則，構建出5種情況下的路徑分別與自動生成的數據對應。

通過工具仿真可得，工具可以針對待測程序自動生成覆蓋全部路徑的測試數據，與人工設計相比在準確性相同的情況下，提高了設計測試用例的效率。

4 結論

通過改進的遺傳算法提出了基于路徑覆蓋的測試用例自動生成方法并將算法應用于自動化生成用例工具中。相比于基本遺傳算法，筆者提出對適應度函數進行改進，加速算法收斂，提高數據生成效率；對遺傳算子即交叉率、變異率做自適應改進，使得算法更快速地找到適合的數據；基于改進算法開發了一款測試數據自動生成工具，自動地分析待測程序并根據預設參數生成測試用例，預留測試用例與需求階段、設計階段、開發階段對接的接口，以便后期工具的擴展。

改進的遺傳算法生成測試用例的輸入值僅支持數字類型，對于具有特殊含義的文本類型沒有很好的支持，下一階段將針對文本類型及其他類型的輸入變量進行自動化生成的研究。

[1] Kim J, Kim E S, Yoo J, et al. An Integrated Software Testing Framework for FPGA-Based Controllers in Nuclear Power Plants[J]. Nuclear Engineering & Tech- nology, 2016, 48(2): 470-481.

[2] 錢麗,萬家華,陳秀明,等.基本路徑測試算法的改進與應用[J].長春理工大學學報(自然科學版),2016,39(1):107- 111.

[3] 孫德剛.基于改進遺傳算法的軟件測試數據自動生成系統研究[J].現代信息科技,2020,4(1):23-24.

[4] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Ann Arbor: University of Michigan Press, 1975: 170-173.

[5] 陳宏,宋艷.基于改進遺傳算法的城市交通最佳路徑選擇[J].唐山師范學院學報,2010,32(5):72-74.

[6] 曹珣,方徽星.基于改進型GA的測試數據自動生成研究[J].信息記錄材料,2020,21(8):158-159.

[7] 夏春艷,張巖,萬里,等.基于否定選擇遺傳算法的路徑覆蓋測試數據生成[J].電子學報,2019,47(12):2630-2638.

[8] 赫彥文,劉紫陽,李建義,等.基于遺傳算法的測試用例自動生成方法綜述[J].廊坊師范學院學報(自然科學版), 2020,20(4):16-20.

[9] 包曉安,熊子健,張唯,等.一種基于改進遺傳算法的路徑測試用例生成方法[J].計算機科學,2018,45(8):174-178.

[10] 王敏,馬敏,張志.基本路徑測試用例設計的改進方法[J].計算機應用與軟件,2019,36(10):17-22.

Research and Simulation of Test Cases GenerationBased on Improved Genetic Algorithm

LIN Ya-na

(Computing and Information Science College, Fuzhou Institute of Technology, Fuzhou 350506, China

Path coverage testing is an important method in White-Box Testing.It takes a lot of time to design test cases that cover all paths.To solve this problem, an automatic test case generation tool based on improved genetic algorithm is proposed.The improved genetic algorithm constructs the target path matrix and the actual path matrix by the path construction method. It designs the fitness by comparing the differences between the target path matrix and the actual path matrix, obtains the fitness value through normalization, and finally adjusts the genetics according to the fitness value. This method can get the optimal solution set of the problem and then get all the test data. The improved algorithm can increase the algorithm convergence speed and reduce the premature degree. With the same coverage and accuracy, this tool can do program instrumentation, generate test cases covering all paths, and use the test cases to run the program and feedback test results.These are all operated with a visual interface. It saves test costs and improves test efficiency.

Genetic Algorithm(GA); automated test; fitness; genetic operators

TP311.51

A

1009-9115(2022)03-0072-07

10.3969/j.issn.1009-9115.2022.03.019

福建省教育廳中青年教師教育科研項目（科技類）（JAT191009），福州理工學院校級科研項目（FTKY21057）

2021-04-16

2021-12-03

林亞娜（1985-），女，遼寧沈陽人，碩士，高級工程師，研究方向為軟件測試技術、遺傳算法。

（責任編輯、校對：田敬軍）