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

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

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

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

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

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

0　引言

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

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

1.1問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

（1）染色體編碼

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

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

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

（2）種群初始化

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

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

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

②染色體交叉及變異

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

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)語(yǔ)

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

［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é)生會(huì)員，研究方向?yàn)檐浖こ獭④浖y(cè)試

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

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

2015-10-20

2015-11-10

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

測(cè)試用例生成；方法調(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.