一種針對Java程序的充分變異算子集

杜畇岐 潘 婭 甘 佳

(1. 西南科技大學計算機科學與技術(shù)學院 四川綿陽 621010；2. 西南科技大學計算機應用技術(shù)研究所 四川綿陽 621010)

變異測試[1](Mutation Testing)是一種基于缺陷的軟件測試方法，基本原理是使用變異算子(Mutants Operator)對被測程序做微小的合乎語法的變動，改變過后得到的程序被稱為變異體(Mutants)。在產(chǎn)生變異體后，分別在原程序和變異體上運行測試用例，如果二者的結(jié)果相同，則表示該變異體是存活的(Alive)，如果二者的結(jié)果不同，則表示該變異體是被殺死的(Killed)。如果一個變異體在語義上和原程序保持一致，那么它將無法被殺死，這一類變異體稱作等價變異體。

變異測試最終通過輸出變異得分來評價測試用例集的缺陷檢測能力，它是被殺死的變異體數(shù)量與變異體總數(shù)的比值，這個比值越高，代表著測試用例的缺陷檢測能力越強?？梢钥闯鲎儺惖梅諷core的取值是在0～1之間的，變異測試的最終目標就是希望Score能達到1，即測試用例集能殺死所有的非等價變異體。

變異測試總時間是變異體生成時間和變異體執(zhí)行時間之和。其中生成時間受所選工具的影響，而執(zhí)行時間的評價指標是每秒生成的變異體數(shù)量，減少生成和執(zhí)行變異體數(shù)量的方法通常遵循以下3種策略之一： (1)“更少”：尋求以最少的信息損失運行更少的變異體; (2)“更聰明”：尋求在多臺機器上并行執(zhí)行； (3)“更快”：尋求一種方法盡可能快地生成或運行每個變異體。本文主要針對第一種方法，尋找一個變異算子的子集來替換原變異算子全集。

Offutt和King在已有研究工作的基礎(chǔ)上，于1987年針對Fortran77首次定義了22種變異算子，這些變異算子的簡稱和描述如表1所示。這22種變異算子的設(shè)定為隨后其他編程語言變異算子的設(shè)定提供了重要的指導依據(jù)。

表1 F77定義的常用22種變異算子Table 1 22 commonly used mutation operators defined by F77

從學術(shù)研究的角度來看，變異測試已經(jīng)是基于缺陷的成熟的測試技術(shù)，但是應用到工業(yè)時存在一個技術(shù)難點，即變異測試產(chǎn)生的變異體較多，開銷較大。例如，在Delamaro等[2]的實驗中，針對一個簡單的程序tcas(僅有137行非注釋代碼)，應用108個變異算子生成了4 937個變異體。而在Kintis M等[3]的實驗中，針對6個程序Commons-Math，Commons-Lang，Pamvotis，XStream，Triangle，Bisect，使用了Major[4]的8種變異算子、Mujava[5]的15種變異算子、PIT[6]的23種變異算子，分別產(chǎn)生了808，1 854，3 169個變異體。因此，大量變異體的生成使得變異測試的分析和執(zhí)行階段的開銷比較昂貴。

為了讓變異測試技術(shù)適用于工業(yè)應用，研究人員已經(jīng)在變異體選擇優(yōu)化方向上進行了深入研究。在Offutt等[7]的實驗中，從Mothra系統(tǒng)的22中變異算子選擇了5種，變異得分僅降低0.5%。在Barbosa[8]的實驗中，從Proteum系統(tǒng)中的77種變異算子選擇了10種，有效減少了65.02%的變異體，變異得分僅降低0.4%。Namin[9]在足夠評估測試用例充分性的情況下從C語言的108種變異算子中選擇了28種變異算子，可以減少92%的變異體。用較小子集在不影響變異得分的情況下替換全集的方法，仍然是變異測試領(lǐng)域研究的熱點之一。

1 技術(shù)路線

1.1 技術(shù)基礎(chǔ)

對變異算子的選擇是變異測試技術(shù)中的經(jīng)典問題，對該問題進行如下描述：

假設(shè)：給定測試用例T，變異體集M，Score(T，M)代表T在M上執(zhí)行的變異得分。

問題：尋找M1∈M，使得Score(T，M)≈Score(T，M1)。

Mathur在1991年提出一個解決方法，并稱之為選擇性變異(Selective Mutation)。這類方法旨在不影響變異評分的前提下，通過對變異算子進行約簡來縮小變異體的數(shù)量，從而減少變異測試的開銷。

在針對表1中的22中變異算子中，ASR算子和SVR算子會生成大約30%～40%的變異體。Offutt等通過忽略ASR和SVR這兩種算子，有效減少了生成變異的數(shù)量，并將該方法命名為“2-selective mutation”[7]，同時他們又提出了“4-Selective Mutation”和“6-Selective Mutation”。他們的實驗表明應用“2-Selective Mutation”策略后，其變異評分均值為99.99%，可減少24%的變異體數(shù)量。應用“4-Selective Mutation”策略后，其變異評分均值為99.84%，可減少41%的變異體數(shù)量。而應用“6-Selective Mutation”策略后，其變異評分均值為88.71%，可減少60%的變異體數(shù)量。Offutt等在理論上將該方法擴展到了“N-Selective Mutation”。

本文基于Selective Mutation方法，從Mujava的19個java類級別變異算子忽略一些對變異得分的結(jié)果影響較小的算子，并在最后對所選算子進行充分性驗證。

1.2 研究對象

在變異測試發(fā)展的40年中，研究人員和從業(yè)者已經(jīng)開發(fā)并使用了許多變異測試工具[3]，對ISSTA上發(fā)表的和變異測試相關(guān)的論文進行調(diào)研，最常用的有3種工具：Major[4]，MuJava[5]和PIT[6]。而在Kintis[3]2017年對變異測試工具的評測中，對于相同的待測程序，MuJava，Major，PITRV三者分別會產(chǎn)生手工測試的數(shù)量為138，97，105，產(chǎn)生的變異體數(shù)量分別為203，94，382，最終依據(jù)Bug檢測能力的評分為85，80，91。PITRV是PIT的研究版本，在該測評中能揭露97%的真實Bug,是效果最佳的工具，但在2016年的實驗中[10]使用PIT的普通版時，發(fā)現(xiàn)PIT揭露Bug的能力遠遠低于MuJava和Major。為了避免PIT版本之間的不確定性對實驗結(jié)果的影響，本文選擇了得分第二的MuJava來開展變異算子的選擇實驗。

MuJava是一個針對Java語言的變異測試工具，它提供了可選擇的19種Java類級別的變異算子，能夠自動為原程序生成變異體，測試人員只需要提供符合Junit規(guī)范的測試用例，就能使用MuJava來自動判斷是否殺死變異體并計算得分。表2展示了可操作的類級別變異算子和對應的描述。MuJava是一個Java變異測試中有很高研究價值的工具，MuJava提出了一種MSG/Bytecode技術(shù)來處理變異體，在編譯生成和執(zhí)行變異體時實現(xiàn)了平均6.79倍的加速。同時，MuJava開發(fā)了19種Java類級別的變異算子并提供源代碼，測試人員可根據(jù)自己的需要自行選擇所使用的算子。

表2 MuJava的19種變異算子及其變異規(guī)則Table 2 19 mutation operators and mutation rules of MuJava

1.3 待測程序

本文在Windows操作系統(tǒng)下采用Java 1.8在eclipse+MuJava的環(huán)境下進行試驗，為避免所選程序的偶然性對實驗結(jié)果的影響，選擇了2017 全國大學生軟件測試大賽提供的Java程序。該大賽由教育部軟件工程專業(yè)教學指導委員會、中國計算機學會軟件工程專業(yè)委員會、中國軟件測評機構(gòu)聯(lián)盟、中國計算機學會系統(tǒng)軟件專業(yè)委員會和中國計算機學會容錯計算專業(yè)委員會聯(lián)合舉辦，吸引了全國300余所大學的近4 000名學生參賽。由組委會提供來自開源社區(qū)的Java程序代碼，在慕測WebIDE或者Eclipse客戶端完成Junit測試腳本。待測程序為個人初賽和復賽的4個Java項目，共24個類進行測試。如表3所示。

表3 所選待測程序和描述Table 3 Selected programs to be tested and the description

1.4 技術(shù)方案

Offutt等依據(jù)各種變異算子修改語法元素的不同將其分為了三大類[7]：第一類，操作符替換類AAR，ACR，ASR，CAR，CNR，CRP，CSR，SAR，SCR，SRC，SVR；第二類，表達式修改類ABS，AOR，LCR，ROR，UOI；第三類，語句修改類DER，DSA，GLR，RSR，SAN，SDL。并用實驗證明了表達式修改類的5個變異算子ABS，AOR，LCR，ROR，UOI對于22個變異算子具有ProbSubsumes關(guān)系[7]，該關(guān)系表明表達式修改類的變異算子具有代表整個變異算子集合的能力。Offutt等的實驗結(jié)果為表達式修改類算子對所有算子的相對變異得分為99.51。

根據(jù)上述實驗的分類方法，將MuJava中的變異算子進行分類，將其中6個表達式修改類AOIU，AOIS，ROR，AORS，AORB，LOR作為Java變異算子的子類選擇集合。將通過子集得到的變異體組合簡稱為6M組，將通過全集得到的變異體組合簡稱為19M組，刪除其中6M一個變異算子得到的變異體組合成為5M組，將對應生成的測試用例簡稱為T，手工檢測到的等價變異體(Equivalent Mutants)簡稱為EM，變異得分Socre(T，M)表示測試用例集合T在M上執(zhí)行所得的總分。技術(shù)方案如圖1所示。

圖1 技術(shù)方案Fig.1 Technical programmes

2 實驗結(jié)果

實驗步驟中的結(jié)果如表4所示，其中去掉了一些無法被測試的類(接口，main函數(shù)等)，為了縮短運行的時間，相同的測試用例會被合并，只保留一個，無法達到100%時會手工判斷剩下的變異體是否為等價變異體，判定為等價變異體的會刪除，判定為非等價變異體的會不斷擴展測試用例直到殺死，最終達到100%。

表4 6M組的變異體數(shù)目和得分Table 4 The number of mutants and scores for the 6M group

得到的TC組保持不變，對19M組再次進行實驗。結(jié)果如表5所示，同樣手工排除等價變異體，沒有殺死的變異體確定為TC組無法殺死的變異體，這些變異體由6M以外的其他變異算子生成。如果要殺死這些變異體，需要再次進行測試用例的擴展，這一部分為6M組所無法覆蓋的部分。

表5 19M組的變異體數(shù)目和得分Table 5 The number of mutants and scores for the 19M group

19M組的變異得分情況如圖2所示，考慮到Predicate，Value，Variable這3個類有相同的結(jié)構(gòu)，測試代碼也在形式上完全一致，因此只取其中一個計算。最高分100，最低分87.06，平均分95.01分，將AOIU，AOIS，ROR，AORS，AORB，LOR這6個算子作為Java 19個類級別的變異算子的充分子集，取得了95.01的平均分。

圖2 19M組合變異得分情況Fig. 2 Mutation Score Line Chart of the 19M group

驗證6M組的變異算子之間的充分性結(jié)果如表6所示，可以看出在整個變異算子中，AOIS是比較重要的部分，缺少AOIS來生成測試用例會導致評分降低20%～30%，另外AOIU，ROR和AORB有著能影響評分10%左右的作用，AORS和LOR的刪除幾乎不影響評分，這里從充分集合中刪除LOR而保留AORS，因為AORS產(chǎn)生的變異體只能由自己對應的測試用例殺死，和其他變異體幾乎沒有交互，而LOR幾乎沒有產(chǎn)生變異體，這和所選擇的初始程序的類型有關(guān)。關(guān)于LOR變異算子是否選擇的問題，測試人員可以根據(jù)所測項目的實際情況進行增添刪改，實驗證明對于一般Java程序選用AOIU，AOIS，ROR，AORS，AORB這5個變異算子可以滿足Java類級別的變異測試。

表6 刪除任一變異算子后5M組對6M組的得分Table 6 The score of 5M group to 6M group after deleting any mutation operator

表7 QuadTree變異體數(shù)目分布Table 7 The number of mutants in the program QuadTree

取其中QuadTree的變異體數(shù)目分布情況，如表7所示，產(chǎn)生的數(shù)目排序為AOIS>SDL>ROR>AOIU>AORB>ODL>COI>COR>VDL>COD>AORS>LOI,其中刪除類變異算子SDL+VDL+CDL+ODL的占比為27.04，該類算子與表達式修改類算子有很強的相關(guān)性，能夠殺死表達式修改類產(chǎn)生的變異體的測試用例往往也能夠殺死刪除類產(chǎn)生的變異體，故不考慮把該類算子加入充分性集合中。

4 結(jié)論

本文針對MuJava的19個類級別的變異算子對4個Java項目進行了相關(guān)實驗，選擇其中5個作為變異算子的可替換子集已經(jīng)足以有效實施變異測試，能夠在平均變異得分95.01的情況下，減少1～2倍數(shù)量的變異體。由于所選程序的局限性，并不能完全斷定LOR算子是無意義的。實驗中發(fā)現(xiàn)刪除類變異算子和表達式修改類變異算子具有強相關(guān)性，可以在Java變異測試中不使用刪除類變異算子。

變異測試作為一種面向軟件缺陷的技術(shù)，得到了國內(nèi)外軟件測試人員的關(guān)注，并取得了大量研究成果。目前，變異測試和自動化測試結(jié)合是一個待研究的新領(lǐng)域，面向變異測試的測試用例生成還是起步階段，可以進一步考慮將基于遺傳算法的測試用例生成和變異測試的思想進行結(jié)合，用變異得分來指導種群的迭代以減少種群迭代的次數(shù)并提高測試用例的生成效率。