Randoop 和Evosuite 生成測試用例的變異檢測能力分析

郭丹

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

0 引言

單元測試是軟件測試過程的重要一環，編寫高質量的單元測試用例可以提高測試的效率，但費時費力。單元測試用例自動生成工具可以自動生成大量測試用例，但這些測試用例質量有待評估。評估測試用例質量的一種常用方法是變異測試。變異測試將人工缺陷（變異體）種植到被測代碼中，并評估測試用例是否找到它們。當一個測試用例檢測到一個變異體時，說明該變異體被殺死[1]，否則變異體仍然存活。

本文選擇Randoop 和Evosuite 這兩個積極維護的自動化生成單元測試的工具，muJava 變異工具，以數據結構教材中的基本數據結構項目作為被測項目進行變異測試，通過比較Evosuite、Randoop 生成的測試用例的變異檢測能力，以回答下面2 個研究問題：

問題1：兩個工具生成的測試用例在變異測試中的整體表現如何？

問題2：每個工具在檢測不同變異體方面各自有什么優勢？

1 相關工作

為了研究自動生成的單元測試用例是否能找到真正的缺陷，Sina Shamshiri 等人針對defects4j 上的五個項目，利用單元測試生成工具Randoop、Evosuite 以及AgitarOne[2]生成的測試用例，將檢測到的缺陷與實際的缺陷報告進行比較。實驗結果表明：幾種測試生成工具共發現55.7%的缺陷，但沒有單獨的工具發現超過40.6%的缺陷[3]。

為了研究變異體與真實缺陷的關系，Sina Shamshiri 等人[4]針對數據集Defects4J，利用自動化測試生成工具Randoop、Evosuite、JCrashe[5]生成測試用例，用變異工具Major[6]進行變異測試，發現變異體可以有效替代真實缺陷，即變異分數可以體現測試用例發現真實缺陷的能力。

M.Moein Almasi 等人[7]對自動化測試生成工具的有效性進行了評估。但是使用的數據集是工業界的項目——LifeCalc（由SEB Life＆Pension Holding AB Riga Branch 內部擁有和開發的相對復雜的金融應用程序），他們從該軟件項目的版本歷史中提取了25個真實缺陷，并應用了Evosuite 和Randoop 這兩個單元測試生成工具，分別實現了基于搜索和反饋的隨機測試生成。自動生成的測試用例檢測到這些缺陷的高達56.40%（Evosuite）和38.00%（Randoop）。

2 實驗方法

圖1 是實驗流程圖。對于每一個被測項目，Randoop 和Evosuite 分別對其生成測試用例；變異工具muJava 對每個被測項目生成變異體，之后進行變異測試得到變異分數。

圖1 實驗流程圖

2.1 被測系統

基本數據結構及其算法是程序設計和軟件項目開發的基礎，是實際項目開發中的基本組成部分。本文選擇數據結構教材Data Structures and Algorithm Analy?sis[8]中的基本數據結構項目作為被測項目，可以分析自動化單元測試工具在基本數據結構項目上的表現。該數據集包含了常用的數據結構，其中包含了鏈表、隊列、棧、二叉樹、圖，以及各類查找、排序算法等。原始數據集的類文件分布比較雜亂，個別項目中包含了與實現該種數據結構無關的類文件，經過整理后共有46個項目，共有76 個類、327 個方法。

2.2 自動化單元測試工具選擇

實驗采用目前最流行的兩個單元測試工具Randoop 和Evosuite。Randoop[9]是隨機單元測試生成工具，它實現了面向對象程序的反饋隨機測試生成。這意味著它迭代地擴展隨機選擇的方法調用序列，直到生成的序列引發未聲明的異常或違反一般代碼契約。Randoop 還執行其生成的序列，并創建捕獲被測試類行為的斷言。但是，Randoop 不能將測試中的特定類作為目標，因為它使用自底向上的方法，該方法要求方法調用的所有依賴項。因此，Randoop 需要在測試生成過程中查看所有類的列表作為輸入。本文實驗在每次運行中使用默認設置。

Evosuite[10]是基于搜索的單元測試生成工具，它是應用一個遺傳算法來發展一組測試用例，使代碼覆蓋率最大化。Evosuite 是從隨機測試用例的測試用例開始，然后迭代地應用搜索操作符（如選擇、突變和交叉）來進化它們。由于Evosuite 可以針對特定的測試類，因此可以對每個被測類生成一個測試用例。Randoop在生成測試用例時默認時間時100 秒，為了公平起見，在使用Evosuite 時，也將搜索時間也設置為100 秒，其他參數默認。

2.3 變異測試工具選擇

muJava[11]是一種用來對Java 程序產生變體，進行變異測試的一個工具。它自動為方法級別變異測試和類級變異測試生成突變體，同時在源程序和變異程序上執行測試用例（利用Junit 生成的測試用例），區分出可存活和不可存活的變異體。在本次實驗中，選擇muJava 對自動化單元測試生成工具Evosuite、Randoop生成的測試用例進行變異測試。

2.4 實驗過程

為了使用Evosuite 和Randoop，需要對原始代碼進行處理。Randoop 對于不確定性的Random（)方法會生成不穩定的測試，因此按照Randoop 手冊上的處理方法對該方法進行了填0 操作。main 函數是應用程序的入口，類似于一個測試驅動，可以對其他的方法進行調用，而本身不能被調用，所以生成的測試用例無法完全覆蓋main 函數中的代碼，就會造成覆蓋率降低。因此本實驗注釋了main 函數。

（1）測試生成

Randoop 使用的技術是隨機地為被測類生成方法或構造函數的調用序列，而Evosuite 應用遺傳算法來進化一組隨機測試用例的測試用例。為了減小這種隨機性，對Evosuite、Randoop 都生成3 組測試用例，將不可編譯的測試用例丟棄，再生成新的測試用例。

（2）去除不穩定的測試

為了使測試檢測到真正的缺陷，要求測試用例在運行時全部通過。但是，工具可能會生成不穩定測試，即在第一次執行時通過但第二次執行時卻不通過。因此，將可編譯的測試用例在被測項目上運行2-3 次。如果有不穩定的測試用例，那么就會去除這一組測試用例，重新生成，重新編譯和執行直到每次都通過測試。

（3）生成變異算子

在生成變異算子時，需要將源程序的Java 文件放在muJava 的src 文件夾下，源程序的class 文件放在muJava 的class 文件夾下，測試用例的class 文件放在muJava 的tests 文件夾下。運行GenMutants.cmd，勾選需要進行變異的Java 文件，muJava 的變異算子有方法級別和類級別的變異算子。在本實驗中，為了使自動測試生成工具Evosuite、Randoop 生成的測試用例在每次生成變異算子的過程中盡可能生成多種變異算子，將方法級別和類級別的變異算子全部選擇。

（4）變異測試

運行RunTest.cmd。因為在生成變異算子時將方法級別和類級別的變異算子全部選擇，所以在進行變異測試時應該選擇執行所有的變異算子，即：“Execute all mutants”，從而得到方法級別的變異分數即Traditional Mutants Result 和類級別的變異分數即Class Mutants Result。

3 實驗結果

在本節中，將討論實驗結果并回答第一節提出的研究問題。

Evosuite、Randoop 分別為每個測試類生成3 組測試用例并進行變異測試，對這3 組測試用例的方法級別變異分數、類級別變異分數求平均值進行分析。

3.1 兩個工具生成的測試用例在變異測試中的整體表現如何？

變異分數是被殺死變異體體與生成的變異體總數的比例[12]，變異分數越高說明測試用例殺死的變異體數量越多。對實驗過程中Evosuite、Randoop 測試用例的變異分數進行了統計，并分別繪出Evosuite、Randoop測試用例在殺死方法級別、類級別變異體時變異分數的小提琴圖，分別如圖2、圖3。

在生成方法級別變異體的68 個類：其中9 個類（占總類的8%）的Randoop 測試用例的變異分數達到100%，可以殺死所有的變異體。在圖2 方法級別小提琴圖中：Evosuite 測試用例的變異分數存在較明顯的離散值（下側須細長），中位數在50%左右，在40%—60%之間變異分數分布最密集；Randoop 測試用例的變異分數雖存在離散值，但明顯密度小于Evosuite，中位數在60%，且在40-60%、80-90%之間變異分數分布最密集。

在生成類級別變異體的53 個類中：24 個類（占總類的45%）的Evosuite 生成的測試用例的變異分數達到100%；而在Randoop 生成的測試用例中，28 個類（占總類的53%）的變異分數達到100%。觀察其小提琴圖發現：Evosuite 測試用例的變異分數中位數在60%，且變異分數密集分布在80-100%以及0-20%這兩個區間內；Randoop 測試用例的變異分數中位數在100%，在大部分變異分數密集集中在80-100%。

圖2 方法級別變異分數小提琴圖

圖3 類級別變異分數小提琴圖

對于Evosuite、Randoop 生成的測試用例，無論是在殺死方法級別的變異體還是類級別變異體，Randoop生成的測試用例的變異分數高于Evosuite，即Randoop生成的測試用例可以殺死更多的變異體。

3.2 每個工具在檢測不同變異體方面各自有什么優勢？

在本項目的68 個類中，針對muJava 生成的15 種方法級別的變異體，在進行變異測試后每種變異體分成三種情況：部分變異體存活的（live）類的個數、變異體存活率為100%（live-100%）的類的個數和變異體全部被殺死（killed-100%）的類的個數，這三種情況某種變異體類的總和是生成某種變異體類的總數。并分別統計了所有被測類生成的每種變異體在這三種情況下的數量分布。結果如圖4。

圖4 變異體檢測結果統計圖

（1）Randoop 測試用例在檢測COR（改變邏輯運算符）、ROR（改變關系運算符）類型變異體的能力與Evosuite 相同，都可以將COR 類型的變異體全部殺死，8個類的ROR 變異體被全部殺死。

（2）在檢測VDL（刪除某個變量）、CDL（刪除某個運算常數）、ODL（刪除某個變量或者運算常數）類型的變異體時，圖3 中變異體的檢測統計結果可以明顯看出Randoop 測試用例在檢測這些類型變異體的能力優于Evosuite 生成的測試用例。

（3）Randoop 測試用例在檢測SDL、COI、AOIU、LOI類型變異體的能力略優于Evosuite 生成的測試用例。

在檢測COI（改變真值運算符）、SDL（語句刪除）、AOIU（改變變量正負號）、LOI（改變位運算符）類型的變異體時，Randoop 測試用例將這些變異體全部殺死的類的數量多于Evosuite，其中SDL、AOIU、LOI 類型的變異體全部存活的類的個數Evosuite 總是比Randoop 少1 個。

（4）Evosuite、Randoop 測 試 用 例 不 善 于 檢 測AORB、AOIS 類型的變異體。

在生成AORB（改變二元運算符）類型變異體的23個類中，Evosuite 測試用例在進行變異測試時，只有一個類中的變異體被全部殺死；Randoop 測試用例僅將3個類中的AORB 變異體全部殺死。

在41 個生成AOIS（插入一元運算符）變異體的類中：Randoop 測試用例僅將一個類的AOIS 變異體全部殺死，而Evosuite 測試用例進行變異測試時，沒有一個類的AOIS 變異體被全部殺死。

（5）Evosuite 測試用例在檢測ASRS、AODU、AORS類型變異體的能力優于Randoop。

在生成了ASRS（賦值運算符替換）類型的變異體的3 個類中，Evosuite 測試用例可將其中一個類的ASRS 變異體全部殺死，但是在利用Randoop 測試用例進行變異測試時，3 個類中ASRS 變異體的存活率都為100%。

在生成AODU（改變返回值）類型變異體的6 個類中，Evosuite 測試用例可將所有的AODU 變異體全部殺死；Randoop 測試用例只將其中3 個類生成的AODU類型變異體全部殺死。

在生成AORS（算術運算符插入）類型變異體的27個類中，從有AORS 存活的類的個數，還是AORS 被全部殺死的類的個數上看，Evosuite 生成的測試用例優于Randoop 生成的測試用例。

整體來說：在檢測ASRS、AODU、AORS 這三種類型的變異體時，Evosuite 測試用例比Randoop 測試用例殺死更多數量的變異體；但在剩余的12 種類型的變異體中，Randoop 測試用例比Evosuite 測試用例殺死更多數量的變異體。

3.3 實驗有效性的局限

對于每個選定的工具，Evosuite 和Randoop 使用的都不是最新版本，并且沒有對參數進行設置，如果使用最新版本或對對某些參數進行設置，這些工具可能會表現得更好。

另外，Randoop 是為整個項目生成了測試用例，它沒有針對特定的測試類，相比之下，測試用例數量較多；而Evosuite 專門針對所選擇的單個的類生成測試用例，從而導致測試用例數量較少。在本次實驗中，Evosuite 生成的測試用例數量遠遠少于Randoop，這也有可能是導致Randoop 的變異分數明顯高于Evosuite的原因。

為了保證實驗數據的可靠性，將三組測試用例的變異分數求平均值用以分析。實驗中三組測試用例的變異分數不盡相同，如果采用變異分數中最大值或最小值，都會導致實驗結果有偏差。

4 結語

本實驗通過對自動生成的單元測試用例殺死變異體的效果、Randoop 和Evosuite 對muJava 生成的15 種方法級別變異體的檢測效果以及變異分數分析發現，對于小型項目：①Randoop 生成的測試用例的變異分數整體明顯高于Evosuite；②在檢測ASRS、AODU、AORS這三種類型的變異體時，Evosuite 測試用例比Randoop測試用例殺死更多數量的變異體；在剩余的12 種類型的變異體中，Randoop 測試用例比Evosuite 測試用例殺死更多數量的變異體。

在未來的工作中可以通過添加手工編寫的測試用例或者對Evosuite、Randoop 進行參數設置改進自動生成的測試用例，殺死更多的非等價變異體。

阻礙變異測試廣泛應用的主要障礙之一就是等價變異體的檢測問題。等價變異體不僅對提高變異分數沒有幫助，而且長期滯留在測試過程中將耗費極大的計算開銷，可以將基于約束測試技術應用于自動化測試用例生成工具，盡早地將等價變異體檢測出來，以提高變異測試的效率。