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

郭丹

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

0 引言

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

本文選擇Randoop 和Evosuite 這兩個(gè)積極維護(hù)的自動(dòng)化生成單元測試的工具，muJava 變異工具，以數(shù)據(jù)結(jié)構(gòu)教材中的基本數(shù)據(jù)結(jié)構(gòu)項(xiàng)目作為被測項(xiàng)目進(jìn)行變異測試，通過比較Evosuite、Randoop 生成的測試用例的變異檢測能力，以回答下面2 個(gè)研究問題：

問題1：兩個(gè)工具生成的測試用例在變異測試中的整體表現(xiàn)如何？

問題2：每個(gè)工具在檢測不同變異體方面各自有什么優(yōu)勢？

1 相關(guān)工作

為了研究自動(dòng)生成的單元測試用例是否能找到真正的缺陷，Sina Shamshiri 等人針對(duì)defects4j 上的五個(gè)項(xiàng)目，利用單元測試生成工具Randoop、Evosuite 以及AgitarOne[2]生成的測試用例，將檢測到的缺陷與實(shí)際的缺陷報(bào)告進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明：幾種測試生成工具共發(fā)現(xiàn)55.7%的缺陷，但沒有單獨(dú)的工具發(fā)現(xiàn)超過40.6%的缺陷[3]。

為了研究變異體與真實(shí)缺陷的關(guān)系，Sina Shamshiri 等人[4]針對(duì)數(shù)據(jù)集Defects4J，利用自動(dòng)化測試生成工具Randoop、Evosuite、JCrashe[5]生成測試用例，用變異工具M(jìn)ajor[6]進(jìn)行變異測試，發(fā)現(xiàn)變異體可以有效替代真實(shí)缺陷，即變異分?jǐn)?shù)可以體現(xiàn)測試用例發(fā)現(xiàn)真實(shí)缺陷的能力。

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

2 實(shí)驗(yàn)方法

圖1 是實(shí)驗(yàn)流程圖。對(duì)于每一個(gè)被測項(xiàng)目，Randoop 和Evosuite 分別對(duì)其生成測試用例；變異工具muJava 對(duì)每個(gè)被測項(xiàng)目生成變異體，之后進(jìn)行變異測試得到變異分?jǐn)?shù)。

圖1 實(shí)驗(yàn)流程圖

2.1 被測系統(tǒng)

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

2.2 自動(dòng)化單元測試工具選擇

實(shí)驗(yàn)采用目前最流行的兩個(gè)單元測試工具Randoop 和Evosuite。Randoop[9]是隨機(jī)單元測試生成工具，它實(shí)現(xiàn)了面向?qū)ο蟪绦虻姆答侂S機(jī)測試生成。這意味著它迭代地?cái)U(kuò)展隨機(jī)選擇的方法調(diào)用序列，直到生成的序列引發(fā)未聲明的異?；蜻`反一般代碼契約。Randoop 還執(zhí)行其生成的序列，并創(chuàng)建捕獲被測試類行為的斷言。但是，Randoop 不能將測試中的特定類作為目標(biāo)，因?yàn)樗褂米缘紫蛏系姆椒?，該方法要求方法調(diào)用的所有依賴項(xiàng)。因此，Randoop 需要在測試生成過程中查看所有類的列表作為輸入。本文實(shí)驗(yàn)在每次運(yùn)行中使用默認(rèn)設(shè)置。

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

2.3 變異測試工具選擇

muJava[11]是一種用來對(duì)Java 程序產(chǎn)生變體，進(jìn)行變異測試的一個(gè)工具。它自動(dòng)為方法級(jí)別變異測試和類級(jí)變異測試生成突變體，同時(shí)在源程序和變異程序上執(zhí)行測試用例（利用Junit 生成的測試用例），區(qū)分出可存活和不可存活的變異體。在本次實(shí)驗(yàn)中，選擇muJava 對(duì)自動(dòng)化單元測試生成工具Evosuite、Randoop生成的測試用例進(jìn)行變異測試。

2.4 實(shí)驗(yàn)過程

為了使用Evosuite 和Randoop，需要對(duì)原始代碼進(jìn)行處理。Randoop 對(duì)于不確定性的Random（)方法會(huì)生成不穩(wěn)定的測試，因此按照Randoop 手冊上的處理方法對(duì)該方法進(jìn)行了填0 操作。main 函數(shù)是應(yīng)用程序的入口，類似于一個(gè)測試驅(qū)動(dòng)，可以對(duì)其他的方法進(jìn)行調(diào)用，而本身不能被調(diào)用，所以生成的測試用例無法完全覆蓋main 函數(shù)中的代碼，就會(huì)造成覆蓋率降低。因此本實(shí)驗(yàn)注釋了main 函數(shù)。

（1）測試生成

Randoop 使用的技術(shù)是隨機(jī)地為被測類生成方法或構(gòu)造函數(shù)的調(diào)用序列，而Evosuite 應(yīng)用遺傳算法來進(jìn)化一組隨機(jī)測試用例的測試用例。為了減小這種隨機(jī)性，對(duì)Evosuite、Randoop 都生成3 組測試用例，將不可編譯的測試用例丟棄，再生成新的測試用例。

（2）去除不穩(wěn)定的測試

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

（3）生成變異算子

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

（4）變異測試

運(yùn)行RunTest.cmd。因?yàn)樵谏勺儺愃阕訒r(shí)將方法級(jí)別和類級(jí)別的變異算子全部選擇，所以在進(jìn)行變異測試時(shí)應(yīng)該選擇執(zhí)行所有的變異算子，即：“Execute all mutants”，從而得到方法級(jí)別的變異分?jǐn)?shù)即Traditional Mutants Result 和類級(jí)別的變異分?jǐn)?shù)即Class Mutants Result。

3 實(shí)驗(yàn)結(jié)果

在本節(jié)中，將討論實(shí)驗(yàn)結(jié)果并回答第一節(jié)提出的研究問題。

Evosuite、Randoop 分別為每個(gè)測試類生成3 組測試用例并進(jìn)行變異測試，對(duì)這3 組測試用例的方法級(jí)別變異分?jǐn)?shù)、類級(jí)別變異分?jǐn)?shù)求平均值進(jìn)行分析。

3.1 兩個(gè)工具生成的測試用例在變異測試中的整體表現(xiàn)如何？

變異分?jǐn)?shù)是被殺死變異體體與生成的變異體總數(shù)的比例[12]，變異分?jǐn)?shù)越高說明測試用例殺死的變異體數(shù)量越多。對(duì)實(shí)驗(yàn)過程中Evosuite、Randoop 測試用例的變異分?jǐn)?shù)進(jìn)行了統(tǒng)計(jì)，并分別繪出Evosuite、Randoop測試用例在殺死方法級(jí)別、類級(jí)別變異體時(shí)變異分?jǐn)?shù)的小提琴圖，分別如圖2、圖3。

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

在生成類級(jí)別變異體的53 個(gè)類中：24 個(gè)類（占總類的45%）的Evosuite 生成的測試用例的變異分?jǐn)?shù)達(dá)到100%；而在Randoop 生成的測試用例中，28 個(gè)類（占總類的53%）的變異分?jǐn)?shù)達(dá)到100%。觀察其小提琴圖發(fā)現(xiàn)：Evosuite 測試用例的變異分?jǐn)?shù)中位數(shù)在60%，且變異分?jǐn)?shù)密集分布在80-100%以及0-20%這兩個(gè)區(qū)間內(nèi)；Randoop 測試用例的變異分?jǐn)?shù)中位數(shù)在100%，在大部分變異分?jǐn)?shù)密集集中在80-100%。

圖2 方法級(jí)別變異分?jǐn)?shù)小提琴圖

圖3 類級(jí)別變異分?jǐn)?shù)小提琴圖

對(duì)于Evosuite、Randoop 生成的測試用例，無論是在殺死方法級(jí)別的變異體還是類級(jí)別變異體，Randoop生成的測試用例的變異分?jǐn)?shù)高于Evosuite，即Randoop生成的測試用例可以殺死更多的變異體。

3.2 每個(gè)工具在檢測不同變異體方面各自有什么優(yōu)勢？

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

圖4 變異體檢測結(jié)果統(tǒng)計(jì)圖

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

（2）在檢測VDL（刪除某個(gè)變量）、CDL（刪除某個(gè)運(yùn)算常數(shù)）、ODL（刪除某個(gè)變量或者運(yùn)算常數(shù)）類型的變異體時(shí)，圖3 中變異體的檢測統(tǒng)計(jì)結(jié)果可以明顯看出Randoop 測試用例在檢測這些類型變異體的能力優(yōu)于Evosuite 生成的測試用例。

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

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

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

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

在41 個(gè)生成AOIS（插入一元運(yùn)算符）變異體的類中：Randoop 測試用例僅將一個(gè)類的AOIS 變異體全部殺死，而Evosuite 測試用例進(jìn)行變異測試時(shí)，沒有一個(gè)類的AOIS 變異體被全部殺死。

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

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

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

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

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

3.3 實(shí)驗(yàn)有效性的局限

對(duì)于每個(gè)選定的工具，Evosuite 和Randoop 使用的都不是最新版本，并且沒有對(duì)參數(shù)進(jìn)行設(shè)置，如果使用最新版本或?qū)?duì)某些參數(shù)進(jìn)行設(shè)置，這些工具可能會(huì)表現(xiàn)得更好。

另外，Randoop 是為整個(gè)項(xiàng)目生成了測試用例，它沒有針對(duì)特定的測試類，相比之下，測試用例數(shù)量較多；而Evosuite 專門針對(duì)所選擇的單個(gè)的類生成測試用例，從而導(dǎo)致測試用例數(shù)量較少。在本次實(shí)驗(yàn)中，Evosuite 生成的測試用例數(shù)量遠(yuǎn)遠(yuǎn)少于Randoop，這也有可能是導(dǎo)致Randoop 的變異分?jǐn)?shù)明顯高于Evosuite的原因。

為了保證實(shí)驗(yàn)數(shù)據(jù)的可靠性，將三組測試用例的變異分?jǐn)?shù)求平均值用以分析。實(shí)驗(yàn)中三組測試用例的變異分?jǐn)?shù)不盡相同，如果采用變異分?jǐn)?shù)中最大值或最小值，都會(huì)導(dǎo)致實(shí)驗(yàn)結(jié)果有偏差。

4 結(jié)語

本實(shí)驗(yàn)通過對(duì)自動(dòng)生成的單元測試用例殺死變異體的效果、Randoop 和Evosuite 對(duì)muJava 生成的15 種方法級(jí)別變異體的檢測效果以及變異分?jǐn)?shù)分析發(fā)現(xiàn)，對(duì)于小型項(xiàng)目：①Randoop 生成的測試用例的變異分?jǐn)?shù)整體明顯高于Evosuite；②在檢測ASRS、AODU、AORS這三種類型的變異體時(shí)，Evosuite 測試用例比Randoop測試用例殺死更多數(shù)量的變異體；在剩余的12 種類型的變異體中，Randoop 測試用例比Evosuite 測試用例殺死更多數(shù)量的變異體。

在未來的工作中可以通過添加手工編寫的測試用例或者對(duì)Evosuite、Randoop 進(jìn)行參數(shù)設(shè)置改進(jìn)自動(dòng)生成的測試用例，殺死更多的非等價(jià)變異體。

阻礙變異測試廣泛應(yīng)用的主要障礙之一就是等價(jià)變異體的檢測問題。等價(jià)變異體不僅對(duì)提高變異分?jǐn)?shù)沒有幫助，而且長期滯留在測試過程中將耗費(fèi)極大的計(jì)算開銷，可以將基于約束測試技術(shù)應(yīng)用于自動(dòng)化測試用例生成工具，盡早地將等價(jià)變異體檢測出來，以提高變異測試的效率。