基于改進模擬退火遺傳算法的測試用例優(yōu)化方法研究

鄭佳琪，何洋，王存?zhèn)?/p>

（四川大學計算機學院，成都 610065）

基于改進模擬退火遺傳算法的測試用例優(yōu)化方法研究

鄭佳琪，何洋，王存?zhèn)?/p>

（四川大學計算機學院，成都 610065）

0　引言

傳統(tǒng)的單元測試的對象是軟件設計的最小單位——模塊，然而對于面向?qū)ο蟮能浖?，單元的概念發(fā)生了變化。面向?qū)ο蟮能浖钚〉目蓽y試單位是封裝的類或?qū)ο?，面向?qū)ο蟮膯卧獪y試其實是對類的測試。面向?qū)ο筌浖哂欣^承性和多態(tài)性，程序中的類都是封裝起來的，類的方法可能會調(diào)用其他類的對象，但由于無法獲取到其他類的對象狀態(tài)，因此自動生成的測試用例對程序中可能存在的多種執(zhí)行路徑不能完全覆蓋，使得測試用例的分支覆蓋率不高。本文對現(xiàn)有的面向?qū)ο筌浖卧獪y試用例生成的方法進行了比較研究，針對測試用例的分支覆蓋率不高這一問題，提出了一種基于改進的模擬退火遺傳算法的測試用例生成方法。

1　基于方法調(diào)用序列優(yōu)化的測試用例生成方法

1.1問題描述

單元測試的主要目標之一是使被測程序達到很高的覆蓋率。由于面向?qū)ο筌浖哂蟹庋b性，類的屬性和操作對外界來說是不可見的，使得測試很難獲取到實際的對象的狀態(tài)。因為從創(chuàng)建對象到最終實現(xiàn)目標對象的過程中，存在大量的方法調(diào)用序列，而有效的方法調(diào)用序列只占全部序列的一小部分。如何對這些序列進行優(yōu)化，使優(yōu)化后的序列對代碼段能實現(xiàn)更高的覆蓋率具有重要意義。如下的代碼所示：

想要實現(xiàn)語句c.int_i=2的目標狀態(tài)，就必須要獲取到一個Class_B的對象，對象中必須包含Object_E的非空集合。而Class B對象可能又調(diào)用了基本類庫或其他程序中的類對象，這給如何有效地生成覆蓋到目標對象狀態(tài)語句c.int_i=2的方法調(diào)用序列帶來了挑戰(zhàn)。同理，代碼段中語句c.int_i=3也可以作為一個復雜的目標對象狀態(tài)，需要方法調(diào)用序列能有效的覆蓋。

1.2單元測試用例生成方法設計

對于待測試程序，分析要實現(xiàn)的目標類并根據(jù)目標類的關鍵字搜索相關方法的主體，得到相關的方法調(diào)用序列。然而，這些提取出來的方法調(diào)用序列不足以有效實現(xiàn)目標對象狀態(tài)，需要對序列進行優(yōu)化。序列優(yōu)化過程運用改進的模擬退火遺傳算法對這些序列進行優(yōu)化，使優(yōu)化過后的序列能更高效的實現(xiàn)目標對象的狀態(tài)。最后，序列作為動態(tài)符號化執(zhí)行方法的種子，生成測試用例。方法的具體流程如圖1所示。

圖1　測試序列優(yōu)化流程

1.3方法調(diào)用序列提取

為了得到方法的調(diào)用序列，本文運用基于文本的代碼搜索方法對被測程序進行序列操作。針對第3.1節(jié)中的示例被測程序代碼，需要獲取到Class_B的對象，所以Class_B為目標類，以Class_B為關鍵字在被測程序源代碼中進行搜索，找出含有Class_B的相關方法調(diào)用序列。提取出的序列可能包括其他的非基本數(shù)據(jù)類型，需要新的序列生成這些非基本數(shù)據(jù)類型。針對于這種情況，需要對包含有其他非基本數(shù)據(jù)類型的序列進行迭代，直到序列中不含有非基本數(shù)據(jù)類型。如下代碼所示為被搜索到的方法。

1.4基于改進的模擬退火遺傳算法的序列優(yōu)化

提取出的方法調(diào)用序列可以獲取到目標類以及其接口，但對于類中的方法中某些的參數(shù)值可能不能覆蓋到復雜分支，需要對序列進行優(yōu)化。對于提取出的序列，目標是希望得到一系列能有效實現(xiàn)所有目標對象狀態(tài)的序列。因此，本文把測試序列優(yōu)化的問題轉(zhuǎn)化為了多目標優(yōu)化［1-2］的問題。運用改進的模擬退火遺傳算法［3-4］的最優(yōu)解搜索能力在這些序列中搜索出全局最優(yōu)解，即能有效實現(xiàn)目標對象狀態(tài)的序列。

優(yōu)化目標：優(yōu)化過后的序列能覆蓋到所有目標分支。

約束條件：染色體中基因表示的方法符合彼此間的調(diào)用關系。

改進的模擬退火遺傳算法的優(yōu)化過程如下所示：

（1）染色體編碼

提取出的序列包含目標類的構(gòu)造函數(shù)和方法調(diào)用序列，把調(diào)用的序列操作和關聯(lián)參數(shù)的值一同編碼為染色體。

假設在上一小節(jié)中提取的序列為：

對以上序列利用染色體編碼語法進行編碼為：

（2）種群初始化

本文算法的初始種群不是隨機的染色體，而是把提取出的序列集合作為初始種群。將算法中的useRandom值設置為false，則表示初始種群不是隨機得到的。

（3）對現(xiàn)有種群實施如下算法操作,直至產(chǎn)生出下一代新的群體:

①個體適應度評估和個體選擇

②染色體交叉及變異

本文采用多點交叉、插入和移除方法調(diào)用的交叉變異方式。多點交叉是在需要交叉的兩個染色體中隨機選擇若干個中間點，這些中間點需要在目標類的構(gòu)造函數(shù)之后和最后一個調(diào)用方法之前。把無關的構(gòu)造函數(shù)和方法調(diào)用刪除，插入必要的構(gòu)造函數(shù)。并把沖突的變量名重新命名。插入方法調(diào)用在原本的染色體中隨機的插入方法調(diào)用，同時也要插入方法的調(diào)用的參數(shù)。移除方法調(diào)用是在染色體中隨機的移除方法調(diào)用，同時也要把這些方法調(diào)用的參數(shù)移除。

（4）上一步產(chǎn)生出新種群后，選擇一個目標分支，用算法搜索整個序列種群，找到可以覆蓋到目標分支的方法調(diào)用序列。在種群中的每個方法調(diào)用序列都要執(zhí)行一次確認是否覆蓋到目標分支。如果發(fā)現(xiàn)一個方法調(diào)用序列覆蓋到了目標分支，那它將會保留下來，若種群中的個體覆蓋了全部目標分支，或算法超過了設定的最長執(zhí)行時間，則算法的優(yōu)化過程結(jié)束。

把經(jīng)過上述一系列處理的序列集合作為符號化執(zhí)行方法的種子。生成最終的測試用例。與傳統(tǒng)的符號化方法所不同的是，本文優(yōu)化的序列中包含目標對象的創(chuàng)建和目標方法的調(diào)用，可以覆蓋的到程序中更多的分支，測試用例的分支覆蓋率將會提高。

2　實驗結(jié)果分析

為驗證本文改進算法的可行性及效率，與隨機算法及動態(tài)符號化執(zhí)行算法的進行了對比實驗。實驗選取了面向?qū)ο髥卧獪y試中被使用頻率較高的.NET程序AJAX Control Toolkit作為被測程序，在Windows平臺下運用 Reflector、WebMiner、Visual Studio 2010及Pex工具進行實驗，實驗步驟如下所示：

（1）對被測程序進行解析，分析被測程序的目標類如表1所示。

（2）提取方法調(diào)用序列，并對提取出來的方法調(diào)用序列運用本文改進的模擬退火遺傳算法進行優(yōu)化。本實驗收集了優(yōu)化的結(jié)果，去除重復的序列后，共得到17593條方法調(diào)用的序列。

（3）對優(yōu)化后的序列運用Pex工具最終生成測試用例。

通過以上實驗過程，最終生成了10387個可用的測試用例。與基于隨機算法工具Randoop、動態(tài)符號化執(zhí)行算法工具Pex生成的測試用例進行對比實驗，實驗結(jié)果如圖2所示。

表1　被測程序AjaxControlToolkit.dll目標類列表

圖2　對比實驗結(jié)果

從表中可以看到本文方法比基于隨機測試工具Randoop所達到的分支覆蓋率高，本文方法的覆蓋率比Randoop平均高12.6%。對于6個命名空間中有5個的測試過程中原型系統(tǒng)的覆蓋率是高于Randoop的，其中AjaxControl-Toolkit.MaskedEditValidatorCompatibility命名空間，Randoop和本文方法的覆蓋率均為0，因為這個命名空間的類是內(nèi)部靜態(tài)類，不對外提供接口，外部類不能訪問，Randoop和本文方法都提取不到類方法的調(diào)用序列。從圖中可以看到，本文方法比基于動態(tài)符號化測試工具Pex所達到的分支覆蓋率平均高4.2%。

3　結(jié)語

本文以面向?qū)ο筌浖卧獪y試用例的生成作為研究問題，首先，通過對現(xiàn)有的幾種單元測試用例生成方法進行對比研究和分析，提出了一種可行的基于改進的模擬退火遺傳算法的面向?qū)ο筌浖卧獪y試用例優(yōu)化方法。該方法通過對被測程序提取出相關的方法調(diào)用序列，然后運用改進的模擬退火遺傳算法對序列進行優(yōu)化，優(yōu)化出可以覆蓋到更多分支的方法調(diào)用序列，接著把這些序列作為基于動態(tài)符號化執(zhí)行方法的輸入生成單元測試用例。并通過對比實驗驗證了本文方法比隨機方法和動態(tài)符號化執(zhí)行方法具有更高的分支覆蓋率。然而，在本文提出這一方法中，還有需要進一步的工作需要研究和探索。例如，本文方法需要借助其他工具生成測試用例，希望在以后的工作中可以實現(xiàn)一個完整的工具。

［1］Zhang L,Tong D,Lin H,Cheng,X,Wang KY.Test Program Generation Based on Multi-Objective Evolutionary Algorithm.Journal of Computer-Aided Design and Computer Graphics，2010，22（8）:1382-1389.

［2］Oster N,Saglietti F.Automatic Test Data Generation by Multi-Objective Optimization.Proc.Of 25th Int'l Conf.on Computer Safety, Security and Reliability，2006：426-438.

［3］Wang ZG,Wong YS,Rahman M.Development of a Parallel Optimization Method Based on Genetic Simulated Annealing Algorithm［J］. IEEE,2005,31（8-9）:839-857.

［4］Hongbo S,Shenhua Z,Zhihong S.Research on Assembly Sequence Planning Based on Genetic Simulated Annealing Algorithm and Ant Colony Optimization Algorithm［J］.IEEE，2009，29（3）:249-256.

Test Case Generation；Method-Call Sequence；Simulated Annealing Genetic Algorithms；Branch Coverage

A Method of Test Case Optimization Based on Improved Simulated Annealing Genetic Algorithm

ZHENG Jia-qi,HE Yang,Wang Cun-wei
（College of Computer,Sichuan University,Chengdu 610065）

1007-1423（2015）32-0003-04

10.3969/j.issn.1007-1423.2015.32.001

鄭佳琪（1990-），男，內(nèi)蒙古赤峰人，研究生，CCF學生會員，研究方向為軟件工程、軟件測試

何洋（1990-），男，四川瀘州人，研究生，研究方向為軟件工程、軟件測試、模型檢測

王存?zhèn)ィ?989-），男，山西大同人，研究生，研究方向為數(shù)據(jù)挖掘

2015-10-20

2015-11-10

面向?qū)ο筌浖煌趥鹘y(tǒng)的面向過程軟件，其具有封裝性、繼承性和多態(tài)性。面向?qū)ο筌浖蓄惖姆椒ㄖ锌赡軙{(diào)用其他類的對象，導致很難獲取其他類的對象狀態(tài)，并且由于其繼承性和多態(tài)性，程序中可能存在多種執(zhí)行路徑，如果用傳統(tǒng)方法生成測試用例，很難達到較高的測試覆蓋率。針對這個問題，提出一種新的面向?qū)ο筌浖卧獪y試用例生成方法。這一方法基于改進的模擬退火遺傳算法，使得優(yōu)化過的測試序列可以覆蓋到程序中更多的分支，生成的測試用例具有更高的覆蓋率。通過實驗驗證方法的可行性，并與其他方法進行對比實驗。實驗結(jié)果證明該方法具有較高的分支覆蓋率。

測試用例生成；方法調(diào)用序列；模擬退火遺傳算法；分支覆蓋率

四川省應用基礎研究項目（No.2014JY0112）

Different from procedure-oriented software,object-oriented program has encapsulation,inheritance and polymorphism.The methods of classes in object-oriented program may call the objects of other classes.But it is too difficult to get the real objects state.And because of its inheritance and polymorphism,there may have a variety of program execution path.It is difficult to achieve satisfy the test coverage if it use the conventional method to generate the test cases.Aiming at this problem,proposes an approach of object-oriented program unit test case generation based on improved simulated annealing genetic algorithm.The test sequences optimized by simulated annealing genetic algorithm can cover more branches in the program,the generated test cases will have higher coverage.Finally,the feasibility of the method is verified by the experiments and compared with other methods.Experimental results show that the proposed approach has higher branch coverage.