融合變異測試的路徑覆蓋測試數(shù)據(jù)進(jìn)化生成方法

黨向盈，李金鳳

(徐州工程學(xué)院信息工程學(xué)院，江蘇 徐州 221018)

dangpaper@163.com;41407770@qq.com

1 引言(Introduction)

軟件測試是保障軟件產(chǎn)品質(zhì)量的一種有效方式。隨著科學(xué)技術(shù)的飛速發(fā)展，軟件產(chǎn)品的復(fù)雜性越來越高，規(guī)模也越來越大，這也導(dǎo)致軟件缺陷越來越隱蔽，采用傳統(tǒng)的檢測方法很難檢測出軟件的頑固缺陷[1]。實施自動化軟件測試技術(shù)時，需要測試數(shù)據(jù)執(zhí)行程序，同時測試數(shù)據(jù)是檢驗程序缺陷的重要手段，因此測試數(shù)據(jù)的質(zhì)量尤為重要[2]。

變異測試是一種面向缺陷的軟件測試技術(shù)，它通過對程序語句合乎語法的改變，模擬真實的缺陷[3]。通過這種方式，對模擬的缺陷生成測試數(shù)據(jù)，保障測試數(shù)據(jù)集的充分度。在結(jié)構(gòu)覆蓋測試技術(shù)中，覆蓋率最高的是路徑覆蓋測試技術(shù)。路徑中包含的節(jié)點是程序的語句，所以覆蓋一條路徑的測試數(shù)據(jù)能覆蓋很多程序語句，那么路徑覆蓋所得的測試集規(guī)模也比較小，冗余測試數(shù)據(jù)少。

本文借鑒變異測試和路徑覆蓋技術(shù)生成能檢測缺陷的測試數(shù)據(jù)。變異測試模擬缺陷，融合原程序路徑，覆蓋路徑生成的測試數(shù)據(jù)，也能覆蓋缺陷，而且生成的測試數(shù)據(jù)集規(guī)模比較小。

2 測試數(shù)據(jù)生成方法(The proposed method of test data generation)

結(jié)構(gòu)化的路徑覆蓋測試所生成的用例是為了覆蓋目標(biāo)路徑，即使路徑覆蓋率高，也不能代表檢測缺陷率高。此外，傳統(tǒng)的方法生成測試數(shù)據(jù)效率比較低，考慮到進(jìn)化算法已經(jīng)廣泛應(yīng)用[4]，本文采用遺傳生成測試數(shù)據(jù)覆蓋融合缺陷的路徑。

變異測試和路徑覆蓋測試技術(shù)結(jié)合的測試數(shù)據(jù)生成方法的基本框架如圖1所示。首先基于變異測試技術(shù)生成變異體，并轉(zhuǎn)化為變異分支，用于模擬程序的缺陷，再將這些變異分支(缺陷)融入程序；同時，在原程序路徑集中選擇多條目標(biāo)路徑。然后，將變異分支融入原程序生成新被測程序；通過分析變異分支與原語句之前的相關(guān)性，將變異分支融入目標(biāo)路徑。最后，基于遺傳算法生成覆蓋路徑的測試數(shù)據(jù)。

圖1 變異測試和路徑覆蓋測試技術(shù)結(jié)合的測試數(shù)據(jù) 生成方法的基本框架Fig.1 Basic framework of test data generation method based on mutation testing and path coverage testing

2.1 基于變異測試技術(shù)模擬程序缺陷

變異測試技術(shù)不僅可以根據(jù)程序或語句的特征模擬真實軟件中的各種類型的缺陷，也可以基于程序的復(fù)雜情況，針對性地選擇缺陷發(fā)生位置和注入缺陷的數(shù)目[5]。因此，變異測試被認(rèn)為是一種方便、靈活、個性化的技術(shù)。

在實施變異測試時，通過變異算子對原程序語句實施變異操作，比如原語句為“a>b”,實施變異之后，生成變異語句“a==b”。將變異語句替換原來的語句，得到新的被測程序定義為變異體。每一個模擬的缺陷對應(yīng)一個變異體。在實施變異測試時，一個程序通常會產(chǎn)生大量的變異體。某一測試數(shù)據(jù)同時執(zhí)行原程序和變異體，如果兩者的輸出結(jié)果不一致，那么該用例以強變異測試準(zhǔn)則殺死變異體。而且，為了殺死這些變異體，需要大量的測試數(shù)據(jù)執(zhí)行變異體和原程序，導(dǎo)致變異測試代價非常高昂[6]。

為了克服以上不足，文獻(xiàn)[6]提出弱變異測試思想，將變異體轉(zhuǎn)化為變異分支。具體方法是根據(jù)變異測試的必要條件，將原語句和變異語句構(gòu)建if條件語句的分支，形成變異分支。如果某一測試數(shù)據(jù)覆蓋了變異分支，那么基于弱變異測試準(zhǔn)則殺死變異體。圖2(a)為三角形類型判斷程序的部分源代碼，如果對語句實施變異，得到變異語句。然后，基于文獻(xiàn)[6]提出的方法進(jìn)行弱變異測試轉(zhuǎn)化，構(gòu)建變異分支；采用同樣的弱變異測試方法，對語句實施變異，得到圖2(b)中的16 個變異分支，分別表示為。將這些變異分支插入原語句的前面，得到新的被測程序。

圖2 示例程序Fig.2 Sample program

插入原程序的變異分支，代表一些模擬缺陷。如果某一測試數(shù)據(jù)覆蓋某一變異分支，說明基于弱變異測試準(zhǔn)則殺死了對應(yīng)的變異體，也就是說，生成的測試數(shù)據(jù)可以用于檢測這個模擬的缺陷。

2.2 基于相關(guān)性變異分支融入路徑

變異分支插入原程序后，生成新的程序?？紤]到原程序中可以通過路徑覆蓋生成測試數(shù)據(jù)，對于新程序，為了生成覆蓋變異分支的測試數(shù)據(jù)，可以將這些變異分支融入已有原程序路徑，這樣，生成的測試數(shù)據(jù)不僅滿足路徑覆蓋準(zhǔn)則，也滿足變異測試準(zhǔn)則。

為了將變異分支融入原程序路徑，首先，在原程序路徑集中選出若干目標(biāo)路徑；然后，在新程序中判斷原語句與變異分支的相關(guān)性，生成相關(guān)子路徑；最后，基于原語句所在目標(biāo)路徑將變異分支插入目標(biāo)路徑，形成新的目標(biāo)路徑。以圖2為例闡述基于相關(guān)性變異分支融入路徑的方法。在原程序路徑集中選擇目標(biāo)路徑，可以得到：

需要說明的是，路徑集中可能包含很多路徑，針對挑選目標(biāo)路徑的原則：(1)盡量選擇包含路徑節(jié)點比較少的路徑。(2)挑選的目標(biāo)只是初選，如果所有變異分支都無法融入，該路徑將被刪除。(3)目標(biāo)路徑中，還有未融入的變異分支，將從路徑集中重新挑選路徑。

2.3 基于遺傳算法生成測試數(shù)據(jù)

遺傳算法是由自然界的遺傳和進(jìn)化理論啟發(fā)而來，是一種被廣泛使用的全局搜索的優(yōu)化技術(shù)。近年來，遺傳算法已經(jīng)廣泛應(yīng)用于軟件測試中[9]。

本文采用遺傳算法時，遺傳操作包括輪盤賭選擇方法，即單點交叉和單點變異。交叉概率和變異概率分別為0.9和0.3?？紤]到目標(biāo)路徑有多條，本文采用單種群遺傳算法(Single Population Genetic Algorithm，SGA)和多種群遺傳算法(Multi-population Genetic Algorithm，MGA)生成覆蓋路徑測試數(shù)據(jù)。單種群遺傳算法生成測試數(shù)據(jù)時，一次運行算法只能針對一條路徑生成測試數(shù)據(jù)。多種群遺傳算法生成測試數(shù)據(jù)時，一次運行算法，多個種群針對多條路徑生成測試數(shù)據(jù)，多種群個數(shù)設(shè)置為目標(biāo)路徑個數(shù)。

3 實驗 (Experiments)

圖3 三條目標(biāo)路徑采用單種群遺傳算法的時間消耗 和迭代次數(shù)對比Fig.3 Comparison of time consumption and iteration number of three target paths using SGA

圖4 三條目標(biāo)路徑采用多種群遺傳算法的時間消耗 和迭代次數(shù)對比Fig.4 Comparison of time consumption and iteration number of three target paths using MGA

下面比較采用單種群和多種群生成測試數(shù)據(jù)的性能。由圖5所知，對于路徑，在時間消耗和迭代次數(shù)方面，因為實驗具有一定的偶然性，所以單種群遺傳算法偶爾優(yōu)于多種群遺傳算法，但從總體來看，多種群遺傳算法生成測試數(shù)據(jù)方法明顯優(yōu)于單種群遺傳算法。同理，由圖6可知，對于路徑，多種群遺傳算法在時間消耗和迭代次數(shù)方面的性能也高于單種群遺傳算法。由圖7可知，對于路徑，多種群遺傳算法的性能也高于單種群遺傳算法。

圖5 采用單種群和多種群覆蓋p1的時間消耗和迭代次數(shù)對比Fig.5 Comparison of time consumption and iteration number of covering p1 using SGA and MGA

圖6 采用單種群和多種群覆蓋p2時間消耗和迭代次數(shù)對比Fig.6 Comparison of time consumption and iteration number of covering p2 using SGA and MGA

圖7 采用單種群和多種群覆蓋p3時間消耗和迭代次數(shù)對比Fig.7 Comparison of time consumption and iteration number of covering p3 using SGA and MGA

對于單種群遺傳算法和多種群遺傳算法，執(zhí)行30 次的時間消耗和迭代次數(shù)平均值如表1所示。從表1中可以看出，覆蓋所有路徑時，單種群比多種群遺傳算法消耗的時間更長，迭代次數(shù)更多。多種群遺傳算法在時間消耗方面比單種群遺傳算法少用7.02 s，時間節(jié)約幅度為41.15%。多種群遺傳算法在迭代次數(shù)方面比單種群遺傳算法少1,276.2 次，迭代次數(shù)降低24.33%。此外，對比覆蓋三條目標(biāo)路徑的平均時間消耗和迭代次數(shù)可知，消耗時間最多，迭代次數(shù)也最多，說明路徑最難覆蓋；消耗時間最少，迭代次數(shù)也最少，說明路徑最容易覆蓋。

表1 單種群和多種群遺傳算法時間消耗和迭代次數(shù)的平均值Tab.1 Average of time consumption and iteration numbers using SGA and MGA

4 結(jié)論(Conclusion)

本文所提出的基于變異測試的路徑覆蓋測試數(shù)據(jù)進(jìn)化生成方法，創(chuàng)新性地將變異測試技術(shù)和路徑覆蓋測試技術(shù)結(jié)合，轉(zhuǎn)化后的變異分支模仿缺陷，融入原程序路徑，生成的測試數(shù)據(jù)不僅規(guī)模小且能夠用于檢測缺陷?？紤]到遺傳算法有利于提高測試數(shù)據(jù)生成效率，針對多條路徑，采用多種群遺傳算法，每個子種群負(fù)責(zé)一條路徑測試數(shù)據(jù)的生成。實驗結(jié)果也驗證多種群遺傳算法明顯優(yōu)于單種群遺傳算法。