陳 雙 徐 望

1 引言

對于一些開發(fā)和維護周期較長的軟件項目來說，測試人員會持續(xù)不斷地為被測軟件設計和開發(fā)新的測試用例。隨著軟件測試工作的開展，一定時間后會積累下許多測試用例。軟件研發(fā)團隊通常會建立并維護一個測試用例庫將已有測試用例通過合理的分類有效地管理起來，以方便開發(fā)和測試人員查詢、執(zhí)行、共享和復用這些測試用例。

對面向對象軟件而言，每個測試用例由一個方法調用序列構成。因此，面向對象軟件的測試用例庫可以提供大量的方法調用序列［1］。如果能從如此眾多的方法調用序列中發(fā)現(xiàn)一些規(guī)律性信息，就可以利用這些信息為新的測試用例生成提供指導［2］。

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

目前，大量軟件項目采用面向對象軟件開發(fā)范型。對面向對象軟件而言，測試用例不再是一組簡單的測試輸入值，而是一系列有序執(zhí)行的方法調用序列［4］。為此，本文受現(xiàn)有測試數(shù)據(jù)再生成研究的啟發(fā)，提出了一種基于序列模式挖掘技術的面向對象軟件測試用例自動再生成策略，利用面向對象軟件測試用例庫所提供的大量已有測試用例資源，為面向對象軟件生成新的測試用例。

2 面向對象軟件的測試用例自動再生成方法

面向對象軟件的每個測試用例都是一個方法調用序列。如果被測面向對象軟件已有測試用例庫，就可以采用序列模式挖掘技術，從測試用例庫的大量方法調用序列中識別出所蘊含的序列模式。這些序列模式通常揭示了相關方法的重要用法或是慣用形式，可以用于構建新的測試用例［5～6］。

假設已知被測面向對象軟件、覆蓋準則以及用以測試的測試用例庫，其中每個測試用例是一個方法調用序列，則基于序列模式挖掘的測試用例再生成可以描述為：

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

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

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

2.1 測試用例庫的序列模式挖掘算法

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

定義1：前綴序列（prefix sequence）。假設給定面向對象軟件的方法調用序列 α= ＜m1，m2，…，mi，…，mn＞ ，那么 α 的子序列 β=＜m1，m2，…，mi-1＞ 稱為α關于mi方法的前綴序列。

定義2：后綴序列（suffix sequence）。假設給定面向對象軟件的方法調用序列 α= ＜m1，m2，…，mi，…，mn＞ ，那么 α 的子序列 γ=＜mi+1，mi+2，…，mn＞稱為α關于mi方法的后綴序列。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 測試用例自動再生成實驗及結果分析

本文以上述測試用例再生成策略為基礎，實現(xiàn)了SPM-RGN原型工具，并通過實驗為4個具有不同特點和用途的Java開源項目（總計包含超過4萬行代碼）生成測試用例，以評估該策略的有效性。

實驗中首先檢驗了從測試用例庫挖掘序列模式集合的效果，包括：

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

2）序列模式挖掘的時間開銷和空間開銷。

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

1）取得的分支覆蓋率；

2）所生成測試用例的長度。

*實驗對象

實驗中以4個著名的Java開源項目作為被測軟件：

其中CC和CP來自Apache Commons Proper庫，該庫主要用于提供各種可復用的Java組件；JT和NX來自Software-artifact Infrastructure Repository庫，該庫主要用于提供各種Java對比實驗程序。這4個Java項目中，程序實現(xiàn)最為復雜的CC有超過2萬行代碼、近400個類、超過3千個方法以及6千多個分支。4個項目合計近4萬5千行代碼。此外，實驗中采用隨這4個項目發(fā)布的人工測試用例集作為相應的測試用例庫。

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

表1 被測軟件的基本信息

*實驗參數(shù)設置

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

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

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

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

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

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

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

3.2 序列模式挖掘的時間開銷和空間消耗

圖2和圖3分別給出了采用不同最小支持度時，從測試用例庫挖掘序列模式集合的相應時間開銷和空間開銷。

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

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

3.3 再生成測試用例的分支覆蓋效果

對于每個被測面向對象軟件，表2給出了上述測試生成工具分別取得的分支覆蓋率（重復實驗30次取平均值），其中粗體數(shù)值表示對每個被測軟件取得的最大分支覆蓋率。表2底部給出了每個測試生成工具所取得的平均分支覆蓋率。

表2 不同自動測試生成工具取得的分支覆蓋率（%）

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

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

3.4 再生成測試用例的可讀性

對比分析上述測試生成工具所生成測試用例的平均長度，實驗結果如表3所示。其中對于每個被測軟件，所生成的測試用例平均長度最短的用粗體表示。

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

表3 不同測試生成工具所生成測試用例的平均長度

具體來說，圖5顯示了在30次重復實驗中，每個測試生成工具所生成測試用例平均長度的分布情況。由此可以看出，在30次重復實驗中，Randoop生成的測試用例其長度變化最大，而SPM-RGN生成的測試用例其長度變化最小。

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

4 結語

面向對象軟件的測試用例自動生成極具挑戰(zhàn)。與現(xiàn)有完全從被測軟件出發(fā)生成測試用例的方法不同，本文提出了一種基于序列模式挖掘技術的測試用例再生成方法，通過挖掘測試用例庫中的方法調用序列模式，為面向對象軟件搜索高質量的新測試用例。如果測試用例庫為人工創(chuàng)建的測試用例集，則該方法生成的新測試用例與完全從被測軟件出發(fā)生成的測試用例相比，更易于測試人員理解。后續(xù)研究工作可以考慮針對軟件中涉及多線程特性的代碼探討如何自動生成測試用例，以進一步提高測試的有效性。

［1］郭滔.面向對象軟件測試技術研究［J］，科技信息，2011，3：3945-3947.

［2］賈冀婷.軟件測試中測試用例自動生成方法研究［J］，電腦知識與技術，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］俞東進，鄭蘇杭，李萬清，等.基于BIDE的多核并行閉合序列模式挖掘［J］. 計算機工程，2012，38（12）：55-59.

［6］管恩政.序列模式挖掘算法研究［D］.長春：吉林大學，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.