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

杜畇岐 潘 婭 甘 佳

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

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

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

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

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

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

從學(xué)術(shù)研究的角度來看，變異測試已經(jīng)是基于缺陷的成熟的測試技術(shù)，但是應(yīng)用到工業(yè)時存在一個技術(shù)難點(diǎn)，即變異測試產(chǎn)生的變異體較多，開銷較大。例如，在Delamaro等[2]的實(shí)驗(yàn)中，針對一個簡單的程序tcas(僅有137行非注釋代碼)，應(yīng)用108個變異算子生成了4 937個變異體。而在Kintis M等[3]的實(shí)驗(yàn)中，針對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è)應(yīng)用，研究人員已經(jīng)在變異體選擇優(yōu)化方向上進(jìn)行了深入研究。在Offutt等[7]的實(shí)驗(yàn)中，從Mothra系統(tǒng)的22中變異算子選擇了5種，變異得分僅降低0.5%。在Barbosa[8]的實(shí)驗(yàn)中，從Proteum系統(tǒng)中的77種變異算子選擇了10種，有效減少了65.02%的變異體，變異得分僅降低0.4%。Namin[9]在足夠評估測試用例充分性的情況下從C語言的108種變異算子中選擇了28種變異算子，可以減少92%的變異體。用較小子集在不影響變異得分的情況下替換全集的方法，仍然是變異測試領(lǐng)域研究的熱點(diǎn)之一。

1 技術(shù)路線

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

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

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

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

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

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

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

1.2 研究對象

在變異測試發(fā)展的40年中，研究人員和從業(yè)者已經(jīng)開發(fā)并使用了許多變異測試工具[3]，對ISSTA上發(fā)表的和變異測試相關(guān)的論文進(jì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%的真實(shí)Bug,是效果最佳的工具，但在2016年的實(shí)驗(yàn)中[10]使用PIT的普通版時，發(fā)現(xiàn)PIT揭露Bug的能力遠(yuǎn)遠(yuǎn)低于MuJava和Major。為了避免PIT版本之間的不確定性對實(shí)驗(yàn)結(jié)果的影響，本文選擇了得分第二的MuJava來開展變異算子的選擇實(shí)驗(yàn)。

MuJava是一個針對Java語言的變異測試工具，它提供了可選擇的19種Java類級別的變異算子，能夠自動為原程序生成變異體，測試人員只需要提供符合Junit規(guī)范的測試用例，就能使用MuJava來自動判斷是否殺死變異體并計(jì)算得分。表2展示了可操作的類級別變異算子和對應(yīng)的描述。MuJava是一個Java變異測試中有很高研究價值的工具，MuJava提出了一種MSG/Bytecode技術(shù)來處理變異體，在編譯生成和執(zhí)行變異體時實(shí)現(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)境下進(jìn)行試驗(yàn)，為避免所選程序的偶然性對實(shí)驗(yàn)結(jié)果的影響，選擇了2017 全國大學(xué)生軟件測試大賽提供的Java程序。該大賽由教育部軟件工程專業(yè)教學(xué)指導(dǎo)委員會、中國計(jì)算機(jī)學(xué)會軟件工程專業(yè)委員會、中國軟件測評機(jī)構(gòu)聯(lián)盟、中國計(jì)算機(jī)學(xué)會系統(tǒng)軟件專業(yè)委員會和中國計(jì)算機(jī)學(xué)會容錯計(jì)算專業(yè)委員會聯(lián)合舉辦，吸引了全國300余所大學(xué)的近4 000名學(xué)生參賽。由組委會提供來自開源社區(qū)的Java程序代碼，在慕測WebIDE或者Eclipse客戶端完成Junit測試腳本。待測程序?yàn)閭€人初賽和復(fù)賽的4個Java項(xiàng)目，共24個類進(jìn)行測試。如表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；第二類，表達(dá)式修改類ABS，AOR，LCR，ROR，UOI；第三類，語句修改類DER，DSA，GLR，RSR，SAN，SDL。并用實(shí)驗(yàn)證明了表達(dá)式修改類的5個變異算子ABS，AOR，LCR，ROR，UOI對于22個變異算子具有ProbSubsumes關(guān)系[7]，該關(guān)系表明表達(dá)式修改類的變異算子具有代表整個變異算子集合的能力。Offutt等的實(shí)驗(yàn)結(jié)果為表達(dá)式修改類算子對所有算子的相對變異得分為99.51。

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

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

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

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

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

得到的TC組保持不變，對19M組再次進(jìn)行實(shí)驗(yàn)。結(jié)果如表5所示，同樣手工排除等價變異體，沒有殺死的變異體確定為TC組無法殺死的變異體，這些變異體由6M以外的其他變異算子生成。如果要?dú)⑺肋@些變異體，需要再次進(jìn)行測試用例的擴(kuò)展，這一部分為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)，測試代碼也在形式上完全一致，因此只取其中一個計(jì)算。最高分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

驗(yàn)證6M組的變異算子之間的充分性結(jié)果如表6所示，可以看出在整個變異算子中，AOIS是比較重要的部分，缺少AOIS來生成測試用例會導(dǎo)致評分降低20%～30%，另外AOIU，ROR和AORB有著能影響評分10%左右的作用，AORS和LOR的刪除幾乎不影響評分，這里從充分集合中刪除LOR而保留AORS，因?yàn)锳ORS產(chǎn)生的變異體只能由自己對應(yīng)的測試用例殺死，和其他變異體幾乎沒有交互，而LOR幾乎沒有產(chǎn)生變異體，這和所選擇的初始程序的類型有關(guān)。關(guān)于LOR變異算子是否選擇的問題，測試人員可以根據(jù)所測項(xiàng)目的實(shí)際情況進(jìn)行增添刪改，實(shí)驗(yàn)證明對于一般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ù)目排序?yàn)锳OIS>SDL>ROR>AOIU>AORB>ODL>COI>COR>VDL>COD>AORS>LOI,其中刪除類變異算子SDL+VDL+CDL+ODL的占比為27.04，該類算子與表達(dá)式修改類算子有很強(qiáng)的相關(guān)性，能夠殺死表達(dá)式修改類產(chǎn)生的變異體的測試用例往往也能夠殺死刪除類產(chǎn)生的變異體，故不考慮把該類算子加入充分性集合中。

4 結(jié)論

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

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