基于變異點(diǎn)的選擇性變異測試

劉海陸

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

0 引言

隨著計(jì)算機(jī)與互聯(lián)網(wǎng)的快速發(fā)展，各類軟件廣泛應(yīng)用于社會(huì)生活的各個(gè)領(lǐng)域，其重要性不言而喻。作為保證軟件質(zhì)量的重要手段，軟件測試受到了學(xué)術(shù)界和產(chǎn)業(yè)界的高度重視。變異測試是一種基于錯(cuò)誤的軟件測試方法，自20世紀(jì)70年代產(chǎn)生以來，經(jīng)過近50年的發(fā)展，變異測試技術(shù)日趨成熟，大量實(shí)證研究表明[1-4]，相對(duì)于路徑分析、數(shù)據(jù)流分析和域分析等測試方法，變異測試能夠更為有效地檢測軟件故障。

變異測試通過向待測程序注入微小的語法錯(cuò)誤，得到大量被稱為變異體的錯(cuò)誤程序，從原程序生成變異體的轉(zhuǎn)換規(guī)則被稱為變異算子，變異算子主要通過替換、刪除和插入三種方式更改程序中的變量或表達(dá)式，從而生成變異體，而變異發(fā)生的位置被稱為變異點(diǎn)。變異測試以測試集甄別原程序與變異體的能力來衡量測試集的有效性，如果一個(gè)變異體被測試集甄別出來，則稱該變異體被測試集“殺死”，否則稱該變異體“存活”。由于變異體數(shù)量巨大，在降低測試效率的同時(shí)，帶來了高昂的測試成本，嚴(yán)重影響了變異測試的廣泛應(yīng)用。大量研究表明，在所有變異體中，存在大量冗余變異體，這些冗余變異體并不能為提高測試集質(zhì)量做出任何貢獻(xiàn)。本文通過分析變異體之間的冗余關(guān)系，發(fā)現(xiàn)絕大部分非冗余變異體出現(xiàn)在條件和循環(huán)等控制語句，因此提出一種基于變異點(diǎn)的選擇性變異測試方法，僅對(duì)控制語句進(jìn)行變異，在降低較少測試有效性的前提下，大幅減少測試成本。另外，在現(xiàn)有研究中，多使用變異得分來衡量不同測試方法的有效性，沒有考慮冗余變異體和冗余測試用例對(duì)變異得分的影響，使變異得分無法準(zhǔn)確衡量不同測試方法的有效性，本文提出一種僅考慮非冗余變異體的評(píng)估指標(biāo)MMS（Modified Mutation Score）,能夠更為有效地評(píng)估變異測試的有效性。

1 相關(guān)工作

本文提出的方法屬于變異體約減技術(shù)，現(xiàn)有變異體約減技術(shù)主要可分為四類，第一類為變異體采樣技術(shù)，在生成的全部變異體中，按照一定比例隨機(jī)選取變異體進(jìn)行測試，該方法首先由Acree[2]和Budd[3]提出，在Wong和Mathur[5-6]的研究中，選取10%的變異體僅降低16%的測試有效性，DeMillo[7]、King和 Offutt[8]等人的研究也取得了相似的結(jié)果；第二類為變異體聚類技術(shù)，根據(jù)變異體在測試集上的表現(xiàn)對(duì)變異體進(jìn)行聚類，從每一類中選擇出典型的變異體進(jìn)行測試，Hussain[9]采用K-means和層次聚類算法在不降低測試有效性的情況下，較變異體采樣技術(shù)選出的變異體數(shù)量更少；第三類為選擇性變異技術(shù)，通過對(duì)變異算子的約減來減少生成變異體的數(shù)量，Mathur[10]首先提出可將變異測試工具M(jìn)othra中的ASR和SCR算子省略，Offutt[11]等人進(jìn)一步將其發(fā)展為2-selective、4-selective和6-selective變異測試，其中6-selective變異測試能夠在平均保證88.71%測試有效性的情況下，約減60%的變異體；第四類為高階變異測試技術(shù)，首先由Jia和Harman[12]提出，通過將多個(gè)一階變異體組合成一個(gè)高階變異體的方式，在減少變異體的數(shù)量的同時(shí)，能夠更好地模擬實(shí)際軟件開發(fā)過程中的真實(shí)錯(cuò)誤。

變異體采樣技術(shù)由于采取隨機(jī)選擇的方法，一方面在較大程度上降低了測試有效性，另一方面在保持同等測試有效性的前提下，不同程序的所使用采樣率不盡相同，導(dǎo)致該方法的穩(wěn)定性較低；變異體聚類技術(shù)和高階變異測試技術(shù)均依賴于變異體在測試集上的表現(xiàn)，對(duì)初始測試集的依賴度較高；現(xiàn)有選擇性變異技術(shù)研究中，均以變異算子作為研究對(duì)象，而變異點(diǎn)對(duì)于一個(gè)變異體而言，其重要性并不亞于變異算子，因此本文以變異點(diǎn)作為研究對(duì)象，提出一種新的選擇性變異方法。

2 變異點(diǎn)選擇

變異測試一方面測試有效性較高，另一方面，其測試成本又極其昂貴，其主要矛盾在于生成的大量變異體中，存在一些不必要的變異體，即等價(jià)變異體和冗余變異體，下面給它們的定義：

冗余變異體：對(duì)于一個(gè)變異體m，如果存在另一個(gè)變異體m'，使得在測試集T上，如果m'被殺死，則m必然被殺死，就稱m為m'的一個(gè)關(guān)于測試集T的冗余變異體。

等價(jià)變異體：如果一個(gè)變異體與原程序雖然在語法上不同，但在語義上相同，則稱該變異體為原程序的等價(jià)變異體，等價(jià)變異體無法被任何測試集殺死。

本文從以往研究的基準(zhǔn)程序中，選擇了9個(gè)程序作為研究對(duì)象，之所以選擇這些程序，一是由于它們都具有明確且容易理解的功能，人工識(shí)別等價(jià)變異體的準(zhǔn)確率更高；二是由于它們涵蓋了Java程序中分支、循環(huán)和迭代等主要的控制結(jié)構(gòu)，同時(shí)在數(shù)據(jù)結(jié)構(gòu)方面，涵蓋了數(shù)組等相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；三是本文主要針對(duì)方法級(jí)的變異測試，因此未選擇更大規(guī)模的程序，在減少實(shí)驗(yàn)工作量的同時(shí)，保證了實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。

本文使用變異測試工具M(jìn)uJava進(jìn)行變異測試，獲得了完備的測試集，根據(jù)測試結(jié)果對(duì)變異體進(jìn)行了分類，分類結(jié)果如表1所示。由表中可以看出，在生成的2217個(gè)變異體中，等價(jià)變異體平均占8.80%，冗余變異體平均占88.14%，而能夠提升測試集質(zhì)量的非冗余變異體平均只占3.07%。

表1 分類結(jié)果

為進(jìn)一步分析非冗余變異體與變異點(diǎn)的關(guān)系，對(duì)非冗余變異體的變異點(diǎn)根據(jù)語句類型進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如表2所示。從統(tǒng)計(jì)結(jié)果可以看出，非冗余變異體多出現(xiàn)在條件語句和循環(huán)語句，而在Profit和Days兩個(gè)程序中，雖然部分非冗余變異體出現(xiàn)在賦值語句中，但仍然與條件語句具有很強(qiáng)的聯(lián)系，在Profit程序中非冗余變異體均出現(xiàn)在同一If語句的不同分支中，在Days程序中非冗余變異體所在語句均在SwitchCase語句中。因此，本文僅選取條件語句和循環(huán)語句進(jìn)行變異。

表2 非冗余變異體變異點(diǎn)

3 測試有效性評(píng)估

變異測試使用變異得分衡量測試用例集的有效性，其計(jì)算公式為Ms=Mk/（Mt-Me），其中Mk表示被測試集殺死的變異體數(shù)量，Mt表示全部變異體的數(shù)量，Me表示等價(jià)變異體的數(shù)量。

直觀上，在給定變異體集合M的情況下，對(duì)于不同的測試用例集，其變異得分越高，說明其殺死變異體的能力越強(qiáng)，有效性越高。但由于冗余變異體的存在，使變異得分不能夠準(zhǔn)確的描述測試集的質(zhì)量。例如假設(shè)M中共有10個(gè)變異體其中mi（i=1,2,3,4,5）不為冗余變異體，mi（i=6,7,8,9,10）為m5的冗余變異體，T1和T2為兩個(gè)測試集，使用K（T，M）表示M中能夠被測試集T 殺死的變異體集合，其中 K（T1，M）={mi|i=1,2,3,4}，MS（T1,M）=0.4，K（T2,M）={mi|i=5,6,7,8,9,10}，MS（T2,M）=0.6。顯然T1可以偵測以m1、m2、m3和m4代表的四類錯(cuò)誤，而T2只能偵測以m5代表的一類錯(cuò)誤，T1的測試有效性明顯高于T2，但由于冗余變異體的存在，變異得分給出的結(jié)果卻恰恰相反。

在給定參考測試集的情況下，對(duì)于不同的變異體集合，其變異得分越高，說明其越容易被測試集殺死，所包含的變異體表示的錯(cuò)誤種類越少，質(zhì)量越低，但同樣由于冗余變異體的存在，變異得分同樣無法準(zhǔn)確描述變異體集合的質(zhì)量。例如將上例中的M拆分成M1和M2兩個(gè)集合，其中M1={m1,m2,m3}，M2={mi|i!=3}，給定參考測試集 T，K（T，M）={mi|i!=2}，則 Ms（T,M1）=0.67，Ms（T,M2）=0.78。M1代表了 m1、m2和m3三類錯(cuò)誤，而M2代表了m1、m2、m4和m5四種錯(cuò)誤，因此M2的質(zhì)量高于M1，但由于冗余變異體的存在，變異得分同樣給出了相反的結(jié)果。

為準(zhǔn)確檢驗(yàn)本文方法的測試有效性，消除冗余變異體對(duì)結(jié)果的影響，定義 MMS（Modified Mutation Score）用于衡量變異體集合的測試有效性。對(duì)于變異體集合M1、M2和參考測試集T，首先排除M1和M2中的冗余變異體，得到M1’和M2’，同時(shí)分別去除T中關(guān)于M1和M2的冗余測試用例，得到T1和T2，計(jì)算MS（T1，M1’∪M2‘）和 MS（T2，M1’∪M2‘），記為 MMS（T，M1）和 MMS（T，M2）。

如圖1所示，其中m1至m5表示變異體，每個(gè)橢圓形表示能夠殺死該變異體的測試用例集合，每個(gè)小三角形表示一個(gè)測試用例。設(shè)變異體集合M1={m1,m2}，M2={m2,m3,m4}，參考測試集 T={t1,t2,t3,t4,t5}，則 M1’={m1,m2}，M2’={m3,m4}，T1={t2}，T2={t5}，MMS（T，M1）=0.5，MMS（T，M2）=0.75，說明 M2 的測試有效性高于M1，其物理意義為根據(jù)M2生成的最小測試用例集在全部變異體上的變異得分為0.75，而M1僅為 0.5。而 MS（T，M1）=MS（T，M2）=1，無法體現(xiàn) M1與M2在測試有效性方面的差異。

圖1 MMS計(jì)算示例

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

表3給出了本文提出的選擇性變異方法的實(shí)驗(yàn)結(jié)果，采用本文提出的選擇性變異方法，能夠約減45.02%的冗余變異體，由于使用的是完備測試集，因此約減前和約減后的變異得分Ms均為1，使用本文提出的MMS衡量測試有效性，約減后的測試有效性降低了7.93%。由于Profit和Days兩個(gè)程序中不存在循環(huán)語句，而本文提出的方法僅對(duì)條件和循環(huán)語句進(jìn)行變異，因此這兩個(gè)程序的測試有效性下降最為明顯，這也是本文提出方法的有效性威脅之一。

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

5 結(jié)論及未來工作

實(shí)驗(yàn)結(jié)果表明本文提出的基于變異點(diǎn)的選擇性變異測試方法，能夠在降低較少測試有效性的情況下，大幅降低變異測試的成本。但一方面由于在實(shí)際軟件測試過程中，存在大量不包含或包含極少條件和循環(huán)語句的程序，限制了本文方法的實(shí)用性；另一方面，在實(shí)驗(yàn)過程中觀察到，即使僅對(duì)條件和循環(huán)語句進(jìn)行變異，同樣會(huì)生成大量的冗余變異體，不同類型語句的非冗余變異體與變異算子的類型存在緊密的聯(lián)系，如對(duì)條件語句進(jìn)行ROR（關(guān)系運(yùn)算符替換）和COR（條件運(yùn)算符替換）變異，生成非冗余變異體的可能性較高，而對(duì)表達(dá)式語句進(jìn)行AORB（二元運(yùn)算符替換）變異，生成非冗余變異體的可能性較高。因此，將沿著兩個(gè)研究方向開展后續(xù)研究，一是利用程序依賴圖等圖形化方式表示待測程序，將程序中的每條語句表示成圖中的一個(gè)節(jié)點(diǎn)，利用PageRank[13]和HITS[14]等算法計(jì)算各節(jié)點(diǎn)的重要程度，僅對(duì)重要程度較高的節(jié)點(diǎn)進(jìn)行變異；二是借鑒現(xiàn)有的選擇性變異測試方法，進(jìn)一步研究不同語句和不同變異算子的對(duì)應(yīng)關(guān)系，對(duì)于不同類型的重要節(jié)點(diǎn)選擇與其相適應(yīng)的變異算子。

參考文獻(xiàn)：

[1]WongW E,Mathur A P.Fault Detection Effectiveness of Mutation and Data Flow Testing[J].Software Quality Journal,1995,4（1）:69.

[2]Acree A T.On Mutation[M].Georgia Institute of Technology,1980.

[3]Budd TA.Mutation Analysis of Program Test Data[M].Yale University,1980.

[4]Walsh PJ.AMeasure of Test Case Completeness（Software,Engineering）[J]，1985.

[5]Mathur AP,WongW E.An Empirical Comparison of Mutation and Data Flow Based Test Adequacy Criteria[J]，1993,4（1）:9–31.

[6]W.E.Wong,On Mutation and Data Flow[D],Purdue University,West Lafayette,Indiana,1993.

[7]Demillo R A,GuindiDS,MccrackenW M,etal.An Extended Overview of the Mothra Software Testing Environment[C].Software Testing,Verification,and Analysis,1988.Proceedings of the Second Workshop on.IEEE,1988:142-151.

[8]King KN,OffuttA J.A Fortran Language System for Mutation-Based Software Testing[J].Software Practice&Experience,2010,21（7）:685-718.

[9]S.Hussain,Mutation Clustering[D],King's College London,UK,2008.

[10]Mathur A P.Performance,Effectiveness,and Reliability Issues in Software Testing[C].Computer Software and Applications Conference,1991.COMPSAC'91.Proceedings of the Fifteenth International.IEEE,1991:604-605.

[11]OffuttA J,RothermelG,ZapfC.An Experimental Evaluation of Selective Mutation[C].International Conference on Software Engineering,1993.Proceedings.IEEE,1993:100-107.

[12]Jia Y,Harman M.Constructing Subtle Faults Using Higher Order Mutation Testing[C].Eighth IEEE International Working Conference on Source Code Analysis and Manipulation.IEEE,2008:249-258.

[13]PAGE,L.The PageRank Citation Ranking:Bringing Order to the Web[J].Stanford Digital Libraries Working Paper,1998,9（1）:1-14.

[14]Gibson D,Kleinberg J,Raghavan P.Inferring Web Communities from Link Topology[C].ACM Conference on Hypertext and Hypermedia:Links,Objects,Time and Space-Structure in Hypermedia Systems.ACM,1998:225-234.