杜畇岐 潘 婭 甘 佳

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

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

變異測(cè)試最終通過(guò)輸出變異得分來(lái)評(píng)價(jià)測(cè)試用例集的缺陷檢測(cè)能力，它是被殺死的變異體數(shù)量與變異體總數(shù)的比值，這個(gè)比值越高，代表著測(cè)試用例的缺陷檢測(cè)能力越強(qiáng)。可以看出變異得分Score的取值是在0～1之間的，變異測(cè)試的最終目標(biāo)就是希望Score能達(dá)到1，即測(cè)試用例集能殺死所有的非等價(jià)變異體。

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

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

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

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

為了讓變異測(cè)試技術(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]在足夠評(píng)估測(cè)試用例充分性的情況下從C語(yǔ)言的108種變異算子中選擇了28種變異算子，可以減少92%的變異體。用較小子集在不影響變異得分的情況下替換全集的方法，仍然是變異測(cè)試領(lǐng)域研究的熱點(diǎn)之一。

1 技術(shù)路線

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

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

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

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

Mathur在1991年提出一個(gè)解決方法，并稱之為選擇性變異(Selective Mutation)。這類方法旨在不影響變異評(píng)分的前提下，通過(guò)對(duì)變異算子進(jìn)行約簡(jiǎn)來(lái)縮小變異體的數(shù)量，從而減少變異測(cè)試的開(kāi)銷(xiāo)。

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

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

1.2 研究對(duì)象

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

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

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

1.3 待測(cè)程序

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

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

1.4 技術(shù)方案

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

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

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

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

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

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

得到的TC組保持不變，對(duì)19M組再次進(jìn)行實(shí)驗(yàn)。結(jié)果如表5所示，同樣手工排除等價(jià)變異體，沒(méi)有殺死的變異體確定為T(mén)C組無(wú)法殺死的變異體，這些變異體由6M以外的其他變異算子生成。如果要?dú)⑺肋@些變異體，需要再次進(jìn)行測(cè)試用例的擴(kuò)展，這一部分為6M組所無(wú)法覆蓋的部分。

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

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

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

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

表6 刪除任一變異算子后5M組對(duì)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)生的變異體的測(cè)試用例往往也能夠殺死刪除類產(chǎn)生的變異體，故不考慮把該類算子加入充分性集合中。

4 結(jié)論

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

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