面向?qū)ο筌浖臏y(cè)試用例自動(dòng)再生成方法?

陳 雙 徐 望

1 引言

對(duì)于一些開(kāi)發(fā)和維護(hù)周期較長(zhǎng)的軟件項(xiàng)目來(lái)說(shuō)，測(cè)試人員會(huì)持續(xù)不斷地為被測(cè)軟件設(shè)計(jì)和開(kāi)發(fā)新的測(cè)試用例。隨著軟件測(cè)試工作的開(kāi)展，一定時(shí)間后會(huì)積累下許多測(cè)試用例。軟件研發(fā)團(tuán)隊(duì)通常會(huì)建立并維護(hù)一個(gè)測(cè)試用例庫(kù)將已有測(cè)試用例通過(guò)合理的分類(lèi)有效地管理起來(lái)，以方便開(kāi)發(fā)和測(cè)試人員查詢(xún)、執(zhí)行、共享和復(fù)用這些測(cè)試用例。

對(duì)面向?qū)ο筌浖?，每個(gè)測(cè)試用例由一個(gè)方法調(diào)用序列構(gòu)成。因此，面向?qū)ο筌浖臏y(cè)試用例庫(kù)可以提供大量的方法調(diào)用序列［1］。如果能從如此眾多的方法調(diào)用序列中發(fā)現(xiàn)一些規(guī)律性信息，就可以利用這些信息為新的測(cè)試用例生成提供指導(dǎo)［2］。

現(xiàn)有的測(cè)試用例自動(dòng)生成方法通常隱含地假定沒(méi)有現(xiàn)成的測(cè)試用例可供參考。然而，當(dāng)該假定與實(shí)際情況不符時(shí)，就會(huì)錯(cuò)過(guò)從現(xiàn)有測(cè)試用例（特別是人工創(chuàng)建的測(cè)試用例）中獲取有用信息的機(jī)會(huì)。最近，Yoo等提出了一種旨在利用現(xiàn)有測(cè)試數(shù)據(jù)，生成新測(cè)試數(shù)據(jù)的測(cè)試數(shù)據(jù)再生成（test data regeneration）技術(shù)［3］。

目前，大量軟件項(xiàng)目采用面向?qū)ο筌浖_(kāi)發(fā)范型。對(duì)面向?qū)ο筌浖?，測(cè)試用例不再是一組簡(jiǎn)單的測(cè)試輸入值，而是一系列有序執(zhí)行的方法調(diào)用序列［4］。為此，本文受現(xiàn)有測(cè)試數(shù)據(jù)再生成研究的啟發(fā)，提出了一種基于序列模式挖掘技術(shù)的面向?qū)ο筌浖y(cè)試用例自動(dòng)再生成策略，利用面向?qū)ο筌浖y(cè)試用例庫(kù)所提供的大量已有測(cè)試用例資源，為面向?qū)ο筌浖尚碌臏y(cè)試用例。

2 面向?qū)ο筌浖臏y(cè)試用例自動(dòng)再生成方法

面向?qū)ο筌浖拿總€(gè)測(cè)試用例都是一個(gè)方法調(diào)用序列。如果被測(cè)面向?qū)ο筌浖延袦y(cè)試用例庫(kù)，就可以采用序列模式挖掘技術(shù)，從測(cè)試用例庫(kù)的大量方法調(diào)用序列中識(shí)別出所蘊(yùn)含的序列模式。這些序列模式通常揭示了相關(guān)方法的重要用法或是慣用形式，可以用于構(gòu)建新的測(cè)試用例［5～6］。

假設(shè)已知被測(cè)面向?qū)ο筌浖?、覆蓋準(zhǔn)則以及用以測(cè)試的測(cè)試用例庫(kù)，其中每個(gè)測(cè)試用例是一個(gè)方法調(diào)用序列，則基于序列模式挖掘的測(cè)試用例再生成可以描述為：

1）從測(cè)試用例庫(kù)T中識(shí)別出滿(mǎn)足最小支持度θ的序列模式集合S，其中，每個(gè)序列模式s∈S是一個(gè)mcs子序列并且在T中出現(xiàn)不少于θ ||T次（ ||T為測(cè)試用例庫(kù)T中含有的全部測(cè)試用例數(shù)）；

2）以S為基礎(chǔ)，利用遺傳算法為被測(cè)軟件p生成滿(mǎn)足指定覆蓋準(zhǔn)則c的新測(cè)試用例集T'。

下面將分別描述基于序列模式挖掘的測(cè)試用例再生成策略。

2.1 測(cè)試用例庫(kù)的序列模式挖掘算法

本文提出采用BIDE序列模式挖掘策略［5～6］，從給定的測(cè)試用例庫(kù)T中獲取頻繁序列模式S。為此，首先定義前綴序列和后綴序列如下。

定義1：前綴序列（prefix sequence）。假設(shè)給定面向?qū)ο筌浖姆椒ㄕ{(diào)用序列 α= ＜m1，m2，…，mi，…，mn＞ ，那么 α 的子序列 β=＜m1，m2，…，mi-1＞ 稱(chēng)為α關(guān)于mi方法的前綴序列。

定義2：后綴序列（suffix sequence）。假設(shè)給定面向?qū)ο筌浖姆椒ㄕ{(diào)用序列 α= ＜m1，m2，…，mi，…，mn＞ ，那么 α 的子序列 γ=＜mi+1，mi+2，…，mn＞稱(chēng)為α關(guān)于mi方法的后綴序列。

掃描測(cè)試用例庫(kù)T中的所有方法調(diào)用序列，可識(shí)別出方法調(diào)用序列包含的頻繁1-序列集合S1（即長(zhǎng)度為1且出現(xiàn)頻率不小于最小支持度θ的子序列）。對(duì)于S1中的每個(gè)頻繁1-序列s1而言，由于s1在T中出現(xiàn)至少θ ||T次，因此從T中能夠找到不止一個(gè)關(guān)于s1的前綴序列和后綴序列。由此可以得到關(guān)于s1的前綴序列集合以及后綴序列集合，分別記為Ps1和Ss1。

對(duì)于每個(gè)頻繁1-序列s1而言，嘗試在s1前逐個(gè)插入其前綴序列中的方法，以求反向擴(kuò)展s1得到更長(zhǎng)的頻繁序列。具體來(lái)說(shuō)，首先將前綴序列ps1=＜ m1，…ml-1，ml＞ ∈ Ps1的最后一個(gè)方法ml插入到s1之前，如果所得序列＜ml，s1＞在T中出現(xiàn)至少θ ||T 次，那么就到了一個(gè)頻繁2-序列＜ml，s1＞，記為s2。然后嘗試將ml-1方法插入到s2之前，從而反向擴(kuò)展s2以得到一個(gè)頻繁3-序列。通過(guò)這種迭代操作不斷擴(kuò)展序列的長(zhǎng)度，直到結(jié)果序列在T中出現(xiàn)的次數(shù)少于θ ||T次。于是，便得到了反向擴(kuò)展s1后的頻繁序列s'。

然后，嘗試在s'后逐個(gè)添加s1后綴序列中的方法，正向擴(kuò)展s'以得到更長(zhǎng)的頻繁序列。將后綴序列 ss1=＜mf，mf+1，…，mn＞∈Ss1的第一個(gè)方法mf添加到s'之后，如果所得序列＜s'，mf＞在T中仍然出現(xiàn)至少θ ||T次，那么就嘗試將mf+1方法添加到＜s'，mf＞之后。依此迭代，直到結(jié)果序列在T中出現(xiàn)次數(shù)不足θ ||T次，便得到了一個(gè)完整的頻繁序列s。

如上文所述，對(duì)于每個(gè)頻繁1-序列來(lái)說(shuō)，都有若干個(gè)前綴序列和后綴序列。因此，最終能夠從中得到一批完整的頻繁序列，即頻繁序列模式集合S。算法1給出了由測(cè)試用例庫(kù)T得到頻繁序列模式集合S的偽代碼描述。

需要說(shuō)明的是，挖掘測(cè)試用例庫(kù)T得到頻繁序列模式的過(guò)程中，最小支持度θ是一個(gè)關(guān)鍵參數(shù)。為根據(jù)T的特點(diǎn)選取適當(dāng)?shù)摩戎担疚亩x平均方法調(diào)用頻率如下。

定義3：平均方法調(diào)用頻率（Averaged Method Invocation Frequency，AMIF）。假設(shè)測(cè)試用例庫(kù)T包含 ||T個(gè)測(cè)試用例，其共調(diào)用了n個(gè)不同的方法并且每個(gè)方法mi被調(diào)用了 ||mi次，那么該測(cè)試用例庫(kù)的平均方法調(diào)用頻率可以表示為

AMIF值反映了測(cè)試用例庫(kù)中各方法被調(diào)用的平均頻度。如果一個(gè)測(cè)試用例庫(kù)的AMIF值較小，就意味著該測(cè)試用例庫(kù)中各方法被調(diào)用的平均頻度比較低，因而該測(cè)試用例庫(kù)中包含的頻繁序列模式相對(duì)較少。與之相反，對(duì)于一個(gè)AMIF值較大的測(cè)試用例庫(kù)而言，其方法被調(diào)用的平均頻度較高，因此通常會(huì)包含大量的頻繁序列模式。

為以合理的花費(fèi)從測(cè)試用例庫(kù)中得到數(shù)量適當(dāng)?shù)男蛄心Ｊ?，我們根?jù)測(cè)試用例庫(kù)的AMIF值設(shè)定不同的最小支持度θ。具體來(lái)說(shuō)，如果一個(gè)測(cè)試用例庫(kù)的AMIF較低，那么就選取一個(gè)比較小的θ值；若一個(gè)測(cè)試用例庫(kù)的AMIF較高時(shí)，則采用一個(gè)比較大的θ值。

2.2 基于序列模式的測(cè)試用例再生成算法

對(duì)于面向?qū)ο筌浖?p而言，利用上述方法從測(cè)試用例庫(kù)中獲得頻繁序列模式集合S后，就能夠以S為基礎(chǔ)，利用遺傳算法再生成新的測(cè)試用例。換言之，就是以被測(cè)軟件 p以及頻繁序列模式集合S作為輸入，根據(jù)指定的測(cè)試覆蓋準(zhǔn)則c，采用遺傳算法尋找一批新的方法調(diào)用序列作為p的測(cè)試用例。

具體來(lái)說(shuō)，首先通過(guò)靜態(tài)分析得到被測(cè)軟件p包含的方法集合M以及分支集合B，并且在程序中的分支語(yǔ)句前后插裝測(cè)試探針代碼，以記錄 p的動(dòng)態(tài)執(zhí)行路徑。然后，以分支集合B中的任意一個(gè)尚未覆蓋的分支b作為目標(biāo)，根據(jù)序列模式集合S構(gòu)建初始種群P，其中每個(gè)個(gè)體i是一個(gè)以序列模式s∈S為基礎(chǔ)構(gòu)建的可執(zhí)行方法調(diào)用序列。

為確保i是可執(zhí)行的，需要為s中的參數(shù)賦值。如果需要賦值的arg參數(shù)是一個(gè)基本類(lèi)型變量（例如整型變量），那么就為其賦一個(gè)隨機(jī)值；如果arg參數(shù)是一個(gè)對(duì)象類(lèi)型變量，則搜索M集合以求找到一個(gè)m*方法，其返回類(lèi)型Tm*與arg參數(shù)的聲明類(lèi)型Targ相同或者是Targ的子類(lèi)（即），然后將m*方法返回的對(duì)象賦給arg。如果m*方法仍然含有需要賦值的參數(shù)，同樣采用上述方式為m*的參數(shù)賦值。以此類(lèi)推，直到不再需要為參數(shù)賦值為止，這樣就生成了一個(gè)可執(zhí)行方法調(diào)用序列個(gè)體。算法2描述了為個(gè)體所需參數(shù)賦值的偽代碼。

初始種群P構(gòu)建完畢后，動(dòng)態(tài)執(zhí)行P中的每個(gè)個(gè)體i并利用測(cè)試探針代碼記錄個(gè)體的執(zhí)行路徑。如果i達(dá)到了b分支，那么就生成了一個(gè)新的測(cè)試用例，繼續(xù)以分支集合B中尚未覆蓋的分支b'作為目標(biāo)生成新的測(cè)試用例。如果b沒(méi)有被P中的任何個(gè)體覆蓋到，則計(jì)算P中每個(gè)個(gè)體的執(zhí)行路徑與目標(biāo)分支b的距離：

其中，“approach_level”表示個(gè)體實(shí)際執(zhí)行路徑距離到達(dá)目標(biāo)分支仍相差的控制流節(jié)點(diǎn)數(shù)；“branch_distance”則表示在首個(gè)造成實(shí)際執(zhí)行路徑偏離目標(biāo)分支的條件謂詞處距離滿(mǎn)足該條件謂詞的差值，采用如下公式進(jìn)行歸一化：

然后從P中選出兩個(gè)適應(yīng)度值最高的優(yōu)秀個(gè)體i1和i2，執(zhí)行交叉和變異操作以產(chǎn)生子代個(gè)體。其中單點(diǎn)交叉操作（將i1的一段子序列與i2的一段子序列互換）的概率為 pc、替換變異操作（從頻繁序列模式集合S中隨機(jī)選擇兩個(gè)頻繁序列模式1和2，并分別將 i1和 i2的一段子序列替換為1和2）的概率為概率為 pm。執(zhí)行替換變異操作后，根據(jù)算法2分別為子代個(gè)體i1'和i2'的參數(shù)賦值，這樣便得到兩個(gè)可執(zhí)行的子代個(gè)體。

最后，將P中兩個(gè)適應(yīng)度值較低的個(gè)體替換為i1'和i2'，從而產(chǎn)生一個(gè)新種群P'，并評(píng)估P'中每個(gè)個(gè)體的適應(yīng)度值。依此循環(huán)執(zhí)行種群再生和適應(yīng)度評(píng)估過(guò)程，直到滿(mǎn)足指定的終止條件（全部目標(biāo)分支都被覆蓋或者時(shí)間預(yù)算耗盡），退出循環(huán)，這樣便生成了一批新的測(cè)試用例T'。算法3以偽代碼形式描述了上述基于頻繁序列模式的測(cè)試用例再生成流程。

3 測(cè)試用例自動(dòng)再生成實(shí)驗(yàn)及結(jié)果分析

本文以上述測(cè)試用例再生成策略為基礎(chǔ)，實(shí)現(xiàn)了SPM-RGN原型工具，并通過(guò)實(shí)驗(yàn)為4個(gè)具有不同特點(diǎn)和用途的Java開(kāi)源項(xiàng)目（總計(jì)包含超過(guò)4萬(wàn)行代碼）生成測(cè)試用例，以評(píng)估該策略的有效性。

實(shí)驗(yàn)中首先檢驗(yàn)了從測(cè)試用例庫(kù)挖掘序列模式集合的效果，包括：

1）挖掘測(cè)試用例庫(kù)獲得序列模式的數(shù)量；

2）序列模式挖掘的時(shí)間開(kāi)銷(xiāo)和空間開(kāi)銷(xiāo)。

然后，對(duì)比分析了SPM-RGN與現(xiàn)有隨機(jī)測(cè)試生成工具Randoop［7］和演化測(cè)試生成工具EvoSuite［8］以及本研究開(kāi)發(fā)的基于搜索的測(cè)試用例再生成工具RND-RGN（直接隨機(jī)選取現(xiàn)有測(cè)試用例作為初始種群）的測(cè)試生成效果。具體而言，主要從兩個(gè)方面比較這4種工具的測(cè)試生成效果：

1）取得的分支覆蓋率；

2）所生成測(cè)試用例的長(zhǎng)度。

*實(shí)驗(yàn)對(duì)象

實(shí)驗(yàn)中以4個(gè)著名的Java開(kāi)源項(xiàng)目作為被測(cè)軟件：

其中CC和CP來(lái)自Apache Commons Proper庫(kù)，該庫(kù)主要用于提供各種可復(fù)用的Java組件；JT和NX來(lái)自Software-artifact Infrastructure Repository庫(kù)，該庫(kù)主要用于提供各種Java對(duì)比實(shí)驗(yàn)程序。這4個(gè)Java項(xiàng)目中，程序?qū)崿F(xiàn)最為復(fù)雜的CC有超過(guò)2萬(wàn)行代碼、近400個(gè)類(lèi)、超過(guò)3千個(gè)方法以及6千多個(gè)分支。4個(gè)項(xiàng)目合計(jì)近4萬(wàn)5千行代碼。此外，實(shí)驗(yàn)中采用隨這4個(gè)項(xiàng)目發(fā)布的人工測(cè)試用例集作為相應(yīng)的測(cè)試用例庫(kù)。

被測(cè)軟件的基本統(tǒng)計(jì)特征如表1所示，包括各被測(cè)軟件所含的類(lèi)數(shù)（#Classes）、方法數(shù)（#Methods）、分支數(shù)（#Branches）、非注釋代碼行數(shù)（LOC）、測(cè)試用例庫(kù)中包含的測(cè)試用例個(gè)數(shù)（#Tests）及測(cè)試用例庫(kù)的AMIF值。

表1 被測(cè)軟件的基本信息

*實(shí)驗(yàn)參數(shù)設(shè)置

如第2節(jié)所述，基于序列模式挖掘的測(cè)試用例再生成策略主要分2個(gè)階段實(shí)現(xiàn)，即：1）序列模式挖掘階段，2）測(cè)試用例再生成階段。在這2個(gè)階段中，都有一些參數(shù)需要設(shè)置。

在序列模式挖掘階段，最小支持度θ是一個(gè)關(guān)鍵參數(shù)。由于不同被測(cè)軟件的測(cè)試用例庫(kù)彼此之間特點(diǎn)各不相同，因此沒(méi)有通用的最小支持度。為此，實(shí)驗(yàn)中根據(jù)相應(yīng)測(cè)試用例庫(kù)的AMIF值選取最小支持度，以合理的時(shí)間和空間開(kāi)銷(xiāo)挖掘出適量的序列模式。

由表1可見(jiàn)，本文選取的4個(gè)實(shí)驗(yàn)對(duì)象中，第一個(gè)被測(cè)軟件CC的測(cè)試用例庫(kù)AMIF值不到0.5%，因此采用1%到5%這樣較低的最小支持度來(lái)挖掘測(cè)試用例庫(kù)。第二個(gè)被測(cè)軟件CP的測(cè)試用例庫(kù)AMIF值同樣較低（0.4%），因此同樣采用1%～5%的最小支持度來(lái)挖掘測(cè)試用例庫(kù)。與前兩個(gè)被測(cè)軟件的測(cè)試用例庫(kù)不同，第三個(gè)被測(cè)軟件JT的測(cè)試用例庫(kù)AMIF值高達(dá)7.6%，較前兩個(gè)測(cè)試用例庫(kù)提高了一個(gè)數(shù)量級(jí)，于是實(shí)驗(yàn)中采用10%到50%這樣較高的最小支持度來(lái)挖掘測(cè)試用例庫(kù)。最后一個(gè)被測(cè)軟件NX的測(cè)試用例庫(kù)AMIF值適中（2.4%），實(shí)驗(yàn)中分別將最小支持度設(shè)置為1%～50%不等，以更為全面地考察從測(cè)試用例庫(kù)挖掘序列模式集合的效果。

在測(cè)試用例再生成階段，EvoSuite、RND-RGN以及本研究提出的SPM-RGN原型工具均采用了文獻(xiàn)［12］推薦的演化測(cè)試參數(shù)設(shè)置。具體來(lái)說(shuō)，每個(gè)類(lèi)的測(cè)試生成時(shí)間上限為600秒，種群中共包括100個(gè)體，采用輪盤(pán)賭選擇策略、單點(diǎn)交叉重組策略（交叉概率為0.75）以及替換變異策略（變異概率為0.3）。

3.1 挖掘測(cè)試用例庫(kù)獲得序列模式的數(shù)量

圖1給出了采用不同最小支持度時(shí)，從測(cè)試用例庫(kù)挖掘出的序列模式的數(shù)量。由圖1可見(jiàn)，從這些測(cè)試用例庫(kù)中可以挖掘出大量的序列模式。最小支持度取值增加時(shí)，從各測(cè)試用例庫(kù)挖掘出的序列模式數(shù)量呈對(duì)數(shù)級(jí)減少。

具體來(lái)說(shuō)，對(duì)于方法使用頻率較低的測(cè)試用例集，如CC的測(cè)試用例集和CP的測(cè)試用例集，以比較低的最小支持度才能挖掘出序列模式。例如，最小支持度設(shè)置為1%時(shí)，從CC的測(cè)試用例集可以挖掘得到3181個(gè)序列模式。然而，對(duì)于方法使用頻率較高的測(cè)試用例集，如JT的測(cè)試用例集，以比較高的最小支持度也能挖掘出大量序列模式。例如，最小支持度設(shè)置為10%時(shí)，從JT的測(cè)試用例集挖掘出了48603個(gè)序列模式。對(duì)于方法使用頻率相對(duì)適中的測(cè)試用例集，比如NX的測(cè)試用例集，最小支持度分別設(shè)置為1%到20%時(shí)，都能挖掘得到序列模式。

3.2 序列模式挖掘的時(shí)間開(kāi)銷(xiāo)和空間消耗

圖2和圖3分別給出了采用不同最小支持度時(shí)，從測(cè)試用例庫(kù)挖掘序列模式集合的相應(yīng)時(shí)間開(kāi)銷(xiāo)和空間開(kāi)銷(xiāo)。

由圖2和圖3可以看出，最小支持度取值增加時(shí)，從各測(cè)試用例庫(kù)挖掘序列模式集合的時(shí)間開(kāi)銷(xiāo)和空間開(kāi)銷(xiāo)同樣呈對(duì)數(shù)級(jí)減少。此外，最小支持度取值相同時(shí)，從方法使用頻率較低的測(cè)試用例庫(kù)比從方法使用頻率較高的測(cè)試用例庫(kù)挖掘頻繁方法調(diào)用序列模式集合的開(kāi)銷(xiāo)更小。

通常來(lái)說(shuō)，最小支持度取值越小，從測(cè)試用例庫(kù)挖掘出的序列模式越多，而進(jìn)行序列模式挖掘所需的時(shí)間和空間開(kāi)銷(xiāo)也就越大。因此，需要根據(jù)AMIF指標(biāo)來(lái)針對(duì)測(cè)試用例庫(kù)的方法使用特點(diǎn)，選擇合適的最小支持度取值，從而在所挖掘出的序列模式的數(shù)量以及進(jìn)行序列模式挖掘的開(kāi)銷(xiāo)間做出一個(gè)良好的折衷。

3.3 再生成測(cè)試用例的分支覆蓋效果

對(duì)于每個(gè)被測(cè)面向?qū)ο筌浖?，?給出了上述測(cè)試生成工具分別取得的分支覆蓋率（重復(fù)實(shí)驗(yàn)30次取平均值），其中粗體數(shù)值表示對(duì)每個(gè)被測(cè)軟件取得的最大分支覆蓋率。表2底部給出了每個(gè)測(cè)試生成工具所取得的平均分支覆蓋率。

表2 不同自動(dòng)測(cè)試生成工具取得的分支覆蓋率（%）

由表2可見(jiàn)，對(duì)于全部4個(gè)被測(cè)軟件，SPM-RGN工具都比Randoop、EvoSuite和RND-RGN取得了更高的分支覆蓋率。SPM-RGN所取得的分支覆蓋率高達(dá)70%～95%，平均而言，較Randoop、EvoSuite和RND-RGN取得的分支覆蓋率分別提高了47%、11%以及4%。并且單邊Mann-Whitney U檢驗(yàn)結(jié)果表明：在95%置信水平上，SPM-RGN較Randoop、Evo-Suite和RND-RGN取得的分支覆蓋率提升顯著。

具體來(lái)說(shuō)，在30次重復(fù)實(shí)驗(yàn)中，Randoop，Evo-Suite，RND-RGN和SPM-RGN這4個(gè)自動(dòng)測(cè)試生成工具對(duì)于被測(cè)軟件所取得的分支覆蓋率分布情況如圖4所示。由圖4可以發(fā)現(xiàn)，Randoop在30次重復(fù)實(shí)驗(yàn)中取得的分支覆蓋率波動(dòng)很大，而EvoSuite、RND-RGN以及本研究提出的SPM-RGN在30次重復(fù)實(shí)驗(yàn)中取得的分支覆蓋率相對(duì)穩(wěn)定得多。

3.4 再生成測(cè)試用例的可讀性

對(duì)比分析上述測(cè)試生成工具所生成測(cè)試用例的平均長(zhǎng)度，實(shí)驗(yàn)結(jié)果如表3所示。其中對(duì)于每個(gè)被測(cè)軟件，所生成的測(cè)試用例平均長(zhǎng)度最短的用粗體表示。

由表3可以發(fā)現(xiàn)，在上述測(cè)試生成工具中，本研究提出的SPM-RGN生成的測(cè)試用例平均長(zhǎng)度最短。SPM-RGN生成的測(cè)試用例平均包含大約20行代碼，比Randoop生成的測(cè)試用例平均縮短了大約85%，比EvoSuite和RND-RGN生成的測(cè)試用例分別平均縮短了大約28%。

表3 不同測(cè)試生成工具所生成測(cè)試用例的平均長(zhǎng)度

具體來(lái)說(shuō)，圖5顯示了在30次重復(fù)實(shí)驗(yàn)中，每個(gè)測(cè)試生成工具所生成測(cè)試用例平均長(zhǎng)度的分布情況。由此可以看出，在30次重復(fù)實(shí)驗(yàn)中，Randoop生成的測(cè)試用例其長(zhǎng)度變化最大，而SPM-RGN生成的測(cè)試用例其長(zhǎng)度變化最小。

上述實(shí)驗(yàn)結(jié)果表明，SPM-RGN可以實(shí)現(xiàn)基于序列模式挖掘的測(cè)試用例再生成?？傮w而言，SPM-RGN可以取得比較良好的分支覆蓋率，并且SPM-RGN生成的測(cè)試用例相對(duì)比較短，更有利于測(cè)試人員理解。

4 結(jié)語(yǔ)

面向?qū)ο筌浖臏y(cè)試用例自動(dòng)生成極具挑戰(zhàn)。與現(xiàn)有完全從被測(cè)軟件出發(fā)生成測(cè)試用例的方法不同，本文提出了一種基于序列模式挖掘技術(shù)的測(cè)試用例再生成方法，通過(guò)挖掘測(cè)試用例庫(kù)中的方法調(diào)用序列模式，為面向?qū)ο筌浖阉鞲哔|(zhì)量的新測(cè)試用例。如果測(cè)試用例庫(kù)為人工創(chuàng)建的測(cè)試用例集，則該方法生成的新測(cè)試用例與完全從被測(cè)軟件出發(fā)生成的測(cè)試用例相比，更易于測(cè)試人員理解。后續(xù)研究工作可以考慮針對(duì)軟件中涉及多線程特性的代碼探討如何自動(dòng)生成測(cè)試用例，以進(jìn)一步提高測(cè)試的有效性。

［1］郭滔.面向?qū)ο筌浖y(cè)試技術(shù)研究［J］，科技信息，2011，3：3945-3947.

［2］賈冀婷.軟件測(cè)試中測(cè)試用例自動(dòng)生成方法研究［J］，電腦知識(shí)與技術(shù)，499-500.

［3］Yoo S，Harman M.Test data regeneration：generating new test data from existing test data［J］.Software Testing Verification and Reliability.2012，22（3）：171-201.

［4］Arcuri A，Yao X.On test data generation of object-oriented software［C］//In：Proceedings of the Testing：Academic and Industrial Conference Practice and Research Techniques-MUTATION.Los Alamitos，CA：IEEE Computer Society，2007，72-76.

［5］俞東進(jìn)，鄭蘇杭，李萬(wàn)清，等.基于BIDE的多核并行閉合序列模式挖掘［J］. 計(jì)算機(jī)工程，2012，38（12）：55-59.

［6］管恩政.序列模式挖掘算法研究［D］.長(zhǎng)春：吉林大學(xué)，2005.

［7］Pacheco C，Lahiri S K，Ernst M D，Ball T.Feedback-directed random test generation［C］//In：Proceedings of the 29thInternational Conference on Software Engineering.Los Alamitos，CA：IEEE Computer Society，2007，75-84.

［8］Fraser G，Arcuri A.EvoSuite：automatic test suite generation for object-oriented software［C］//In：Proceedings of the 19thACM SIGSOFT Symposium and the 13thEuropean Conference on Foundations of Software Engineering.New York，NY：ACM，2011，416-419.

［9］Commons Collections.［CP/OL］.http：//commons.apache.org/proper/commons-collections/.

［10］Commons Primitives.［CP/OL］.http：//commons.apache.org/proper/commons-primitives/.

［11］Do H，Elbaum S G，Rothermel G.Supporting controlled experimentation with testing techniques：An infrastructure and its potential impact［J］.Empirical Software Engineering，2005，10（4）：405-435.

［12］Arcuri A，F(xiàn)raser G.On parameter tuning in search based software engineering［C］//In：Proceedings of the 3rdInternational Conference on Search Based Software Engineering.Berlin，Germany：Springer，2011，33-47.