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

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

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

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

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0　引言

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

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

1.1問題描述

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

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

1.2單元測試用例生成方法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

（1）染色體編碼

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

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

對以上序列利用染色體編碼語法進(jìn)行編碼為：

（2）種群初始化

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

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

①個體適應(yīng)度評估和個體選擇

②染色體交叉及變異

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

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

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

2　實(shí)驗(yàn)結(jié)果分析

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

（1）對被測程序進(jìn)行解析，分析被測程序的目標(biāo)類如表1所示。

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

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

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

表1　被測程序AjaxControlToolkit.dll目標(biāo)類列表

圖2　對比實(shí)驗(yàn)結(jié)果

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

3　結(jié)語

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

何洋（1990-），男，四川瀘州人，研究生，研究方向?yàn)檐浖こ獭④浖y試、模型檢測

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

2015-10-20

2015-11-10

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

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

四川省應(yīng)用基礎(chǔ)研究項(xiàng)目（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.