基于GA-SVM的測(cè)試用例生成方法研究?

潘世昊 張海波 左小凱 鄧?guó)櫜?/p>

（中國(guó)船舶集團(tuán)有限公司第七○九研究所 武漢 430205）

1 引言

測(cè)試用例的設(shè)計(jì)是軟件測(cè)試的核心步驟，一個(gè)好的測(cè)試用例集能夠以極小的測(cè)試用例數(shù)量實(shí)現(xiàn)極高的用例覆蓋率。近年來(lái)，軟件的功能日益提高導(dǎo)致其結(jié)構(gòu)越來(lái)越復(fù)雜，尤其是在進(jìn)行黑盒測(cè)試過(guò)程中，將測(cè)試用例的輸入輸出關(guān)系對(duì)應(yīng)起來(lái)更加困難，并且生成的測(cè)試用例集往往數(shù)量較大［1］。因此，許多研究人員都為生成覆蓋率高數(shù)量小的測(cè)試用例集進(jìn)行探索研究［2］。

在進(jìn)行功能測(cè)試前，首先要對(duì)規(guī)格說(shuō)明中的需求進(jìn)行約簡(jiǎn)整合。然后再通過(guò)因果圖法、等價(jià)類(lèi)劃分法等方法選取得到一組典型的測(cè)試數(shù)據(jù)，減少測(cè)試用例的數(shù)量［3］。隨著機(jī)器學(xué)習(xí)技術(shù)和理論得到了巨大的發(fā)展，機(jī)器學(xué)習(xí)也已經(jīng)逐漸應(yīng)用在了軟件測(cè)試用例集的生成和優(yōu)化方面。文獻(xiàn)［4］提出利用神經(jīng)網(wǎng)絡(luò)和程序變異的測(cè)試用例輸出預(yù)測(cè)方法；文獻(xiàn)［5］提出了通過(guò)Ranking SVM算法，對(duì)測(cè)試用例集進(jìn)行排序篩選的方法；文獻(xiàn)［6］提出通過(guò)聚類(lèi)算法實(shí)現(xiàn)對(duì)所需測(cè)試用例的自動(dòng)化識(shí)別；文獻(xiàn)［7］通過(guò)強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)測(cè)試用例集的持續(xù)優(yōu)化集成，提升測(cè)試效率。

微軟公司的pict工具廣泛應(yīng)用于測(cè)試用例的生成，它利用組合原理生成覆蓋率高數(shù)量小的測(cè)試用例集，但是生成的測(cè)試用例都缺少預(yù)期結(jié)果。如果人工進(jìn)行預(yù)測(cè)結(jié)果的填寫(xiě)，將會(huì)耗費(fèi)大量的人力，并且過(guò)程枯燥。

針對(duì)以上問(wèn)題，本文采用GA-SVM模型進(jìn)行測(cè)試用例集的自動(dòng)生成，通過(guò)GA算法選取SVM模型參數(shù)的最佳值。然后利用pict工具生成兩組合的小型輸入數(shù)據(jù)集，將此數(shù)據(jù)集進(jìn)行標(biāo)記后作為SVM模型的訓(xùn)練數(shù)據(jù)集。最后再次使用pict工具生成更高組合的輸入數(shù)據(jù)集，由SVM模型進(jìn)行預(yù)測(cè)其輸出數(shù)據(jù)集。由實(shí)驗(yàn)結(jié)果分析可知，本文中的方法在測(cè)試用例自動(dòng)生成和模型覆蓋率方面，均取得了較好的效果。

2 模型建立與訓(xùn)練

2.1 系統(tǒng)模型的建立

本文選用典型的航班查詢(xún)服務(wù)［10］，選取其中的FlightService模塊、UserService模塊、HotelService模塊和RestaService模塊。

其中FlightService包含以下三個(gè)方面的信息：航班號(hào)、出發(fā)抵達(dá)城市、起飛抵達(dá)時(shí)間。UserSer?vice包含以下兩個(gè)方面的信息：用戶(hù)名、密碼。Ho?telService包含以下信息：剩余房間數(shù)。RestaSer?vice包含以下信息：剩余餐位數(shù)。

圖1 模塊圖

將上述信息整合到一起，形成了7個(gè)輸入?yún)?shù)。記為M=｛M1，M2，M3，M4，M5，M6，M7｝將每個(gè)參數(shù)的取值進(jìn)行離散化，例如：航班號(hào)正確為1，錯(cuò)誤為0；出發(fā)抵達(dá)城市與航班號(hào)相符合為1，不符合為0；用戶(hù)名正確為1，用戶(hù)名錯(cuò)誤為0；密碼正確為1，錯(cuò)誤為0；起飛抵達(dá)時(shí)間與航班號(hào)符合為1，不符合為0；剩余房間數(shù)取值正確為1，錯(cuò)誤為0；剩余餐位數(shù)取值正確為1，錯(cuò)誤為0。

根據(jù)每個(gè)模塊是否能正常調(diào)用，設(shè)輸出參數(shù)為Y=｛Y1，Y2，Y3，Y4｝=｛能否正常調(diào)用UserService模塊、能否正常調(diào)用FlightService模塊、能否正常調(diào)用HotelService模塊、能否正常調(diào)用RestaService模塊｝。Y1，Y2，Y3，Y4的取值為1或0，1表示能正常調(diào)用，0表示不能正常調(diào)用。

2.2 SVM模型的建立

對(duì)于圖1中的系統(tǒng)模型分析可知，其訓(xùn)練數(shù)據(jù)集較小，輸入?yún)?shù)為離散型變量，輸出參數(shù)為兩種取值，因此本文選用SVM模型進(jìn)行訓(xùn)練。SVM模型是一種普遍適用于小數(shù)據(jù)集的二分類(lèi)模型，實(shí)質(zhì)是使得兩類(lèi)數(shù)據(jù)在特征空間中距離最大，所以SVM可以看成一種非線性分類(lèi)器［11］。該算法相對(duì)于Lo?gistic回歸、決策樹(shù)、樸素貝葉斯、KNN等具有更高的準(zhǔn)確率。

在訓(xùn)練SVM模型的過(guò)程中，需要對(duì)兩個(gè)重要的參數(shù)c，g進(jìn)行優(yōu)化，以獲得好的分類(lèi)結(jié)果。c為懲罰參數(shù)，c越大，對(duì)誤分類(lèi)結(jié)果進(jìn)行的懲罰越大，對(duì)誤差的容忍性更??；c越小，對(duì)誤分類(lèi)的結(jié)果進(jìn)行的懲罰越小，對(duì)誤差的容忍性更高。但是c過(guò)大則會(huì)發(fā)生過(guò)擬合現(xiàn)象，過(guò)小則會(huì)發(fā)生欠擬合現(xiàn)象。g與支持向量的個(gè)數(shù)有關(guān)，g越大，個(gè)數(shù)越少；g越小，個(gè)數(shù)越多。但是g設(shè)得太大的話，支持向量太多，會(huì)使得模型集中作用于支持向量附件，對(duì)其他未知數(shù)據(jù)的分類(lèi)效果變差；g設(shè)得太小，支持向量太少，會(huì)使得模型的平滑性變大，無(wú)法從訓(xùn)練集中學(xué)習(xí)到足夠的規(guī)律，使得訓(xùn)練完成的模型無(wú)法正確分類(lèi)。

PSO算法、GA算法、GridSearch算法是常見(jiàn)的尋優(yōu)算法，適用于對(duì)模型參數(shù)的尋找。為了得到較好的c，g值，本文選用UCI數(shù)據(jù)集中的三個(gè)典型數(shù)據(jù)集 balance_scale、vehicle、iris進(jìn)行實(shí)驗(yàn)分析。對(duì)上述數(shù)據(jù)集按訓(xùn)練集和測(cè)試集4：1進(jìn)行劃分，然后分別利用上述三種算法進(jìn)行參數(shù)尋優(yōu)。得到c，g的最佳參數(shù)取值后，將c，g導(dǎo)入到SVM模型中，利用訓(xùn)練集對(duì)模型進(jìn)行訓(xùn)練。訓(xùn)練完成之后，利用劃分出來(lái)的測(cè)試集對(duì)模型準(zhǔn)確率進(jìn)行檢測(cè)。

表1 不同尋優(yōu)算法得到測(cè)試集準(zhǔn)確率

由表1對(duì)比可知，在對(duì)SVM模型中的c，g值尋優(yōu)的算法中，GA算法訓(xùn)練得到的SVM模型分類(lèi)準(zhǔn)確率最高，所以本文采用用GA算法對(duì)SVM模型進(jìn)行尋優(yōu)。

3 典型用例的設(shè)計(jì)

對(duì)軟件系統(tǒng)進(jìn)行功能測(cè)試時(shí)，輸入?yún)?shù)值和輸入?yún)?shù)之間的相互關(guān)系會(huì)影響輸出參數(shù)的結(jié)果［8］。因此，如何選擇輸入?yún)?shù)的取值能滿足輸出結(jié)果的全覆蓋是一個(gè)難題。若通過(guò)輸入?yún)?shù)組合全覆蓋產(chǎn)生測(cè)試用例，雖然會(huì)使覆蓋率變高，但是會(huì)使得測(cè)試用例集過(guò)大，增加軟件測(cè)試的成本。在實(shí)際的功能測(cè)試中，可以利用組合測(cè)試覆蓋準(zhǔn)則來(lái)平衡覆蓋率和成本，產(chǎn)生一個(gè)規(guī)模小、覆蓋率高的測(cè)試用例集。

本文利用pict工具實(shí)現(xiàn)多參數(shù)組合覆蓋。所謂多參數(shù)組合覆蓋是指選定的多個(gè)參數(shù)的所有取值出現(xiàn)在測(cè)試用例集中。而pict的實(shí)現(xiàn)原理是利用配對(duì)法（Pairwise）對(duì)輸入?yún)?shù)進(jìn)行比較排序。排序之后從中挑選分散均勻的樣本進(jìn)行實(shí)驗(yàn)，這些樣本具有很強(qiáng)的代表性，得到的試驗(yàn)結(jié)果等效于大量全面的試驗(yàn)結(jié)果。

表2 pict生成的典型用例表

經(jīng)相關(guān)研究得出的結(jié)論，兩參數(shù)組合覆蓋的測(cè)試用例集能檢測(cè)出大約70%的缺陷，三參數(shù)組合覆蓋的測(cè)試用例集能檢測(cè)出大約90%的缺陷［9］。若想達(dá)到更高的缺陷檢測(cè)率，則需要更高的參數(shù)組合，與此同時(shí)測(cè)試數(shù)據(jù)的個(gè)數(shù)也呈現(xiàn)正比例增長(zhǎng)。假設(shè)一個(gè)軟件系統(tǒng)的功能輸入域有四個(gè)參數(shù)A，B，C，D。對(duì)于參數(shù)A而言，其值域?yàn)镈a=｛a1，a2，a3，a4，a5｝；參數(shù)B，其值域?yàn)镈b=｛b1，b2，b3，b4｝；參數(shù)C，其值域?yàn)镈c=｛c1，c2，c3｝；參數(shù)D，其值域?yàn)镈d=｛d1，d2｝。若對(duì)上述輸入?yún)?shù)進(jìn)行全參數(shù)覆蓋取值，則需要5×4×3×2=240條測(cè)試數(shù)據(jù)。若使用pict工具，自動(dòng)生成兩參數(shù)覆蓋率的測(cè)試數(shù)據(jù)，則只需要20條；自動(dòng)生成三參數(shù)覆蓋率的測(cè)試數(shù)據(jù)，則只需要120條。以pict工具生成的測(cè)試數(shù)據(jù)為基礎(chǔ)，設(shè)計(jì)相應(yīng)的測(cè)試用例集，可以有效地減少測(cè)試用例的數(shù)量，防止測(cè)試數(shù)據(jù)呈正比例增長(zhǎng)的情況。

對(duì)系統(tǒng)模型中的參數(shù)M分析可知，M1，M2，M3與FlightService密切相關(guān)，M4，M5與UserService密切相關(guān)，所以將M1，M2，M3設(shè)置成三組合參數(shù)覆蓋，將M4，M5設(shè)置成兩參數(shù)組合覆蓋。

利用pict生成了32條數(shù)據(jù)，然后對(duì)這32條數(shù)據(jù)進(jìn)行整理，并按照輸出輸出關(guān)系得到其輸出參數(shù)。分析可知，輸出一共有四個(gè)參數(shù)，每個(gè)參數(shù)有兩個(gè)取值，則一共有24=16種取值。而生成的輸出參數(shù)取值只有12種取值，為達(dá)到輸出參數(shù)全覆蓋的要求，手動(dòng)添加剩余4種取值。將表2和表3的測(cè)試用例整合在一起，一共形成36條典型測(cè)試用例。這36條測(cè)試用例就是SVM模型的小型訓(xùn)練數(shù)據(jù)集。

表3 補(bǔ)充用例表

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

通過(guò)表2和表3中的用例集對(duì)GA-SVM模型進(jìn)行訓(xùn)練，然后利用訓(xùn)練完成后的GA-SVM模型對(duì)未知輸出結(jié)果的樣本進(jìn)行預(yù)測(cè)。本實(shí)驗(yàn)使用臺(tái)灣大學(xué)林智仁教授編寫(xiě)的Libsvm工具箱，SVM模型采用CSCV，RBF核函數(shù)類(lèi)型，GA算法參數(shù)尋優(yōu)。然后對(duì)輸出參數(shù)集中的四個(gè)參數(shù)分別設(shè)計(jì)一個(gè)GA-SVM模型進(jìn)行訓(xùn)練，并且每個(gè)輸出參數(shù)為0或1，均為二分類(lèi)模型。

將表2和表3中的36個(gè)數(shù)據(jù)作為訓(xùn)練集輸入到四個(gè)GA-SVM模型進(jìn)行訓(xùn)練，得到四個(gè)訓(xùn)練好的GA-SVM模型。然后，利用pict工具生成七參數(shù)組合全覆蓋的測(cè)試數(shù)據(jù)集，一共生成了128個(gè)測(cè)試數(shù)據(jù)集，利用此數(shù)據(jù)集對(duì)四個(gè)模型進(jìn)行準(zhǔn)確性測(cè)試。

表4 GA-SVM模型分類(lèi)準(zhǔn)確率表

本實(shí)驗(yàn)通過(guò)對(duì)航班查詢(xún)服務(wù)系統(tǒng)的功能進(jìn)行描述，確定了輸入輸出關(guān)系及輸入輸出域，然后利用pict工具生成滿足特定組合覆蓋的輸入?yún)?shù)集，同時(shí)考慮輸入?yún)?shù)和輸出參數(shù)類(lèi)別全覆蓋，設(shè)計(jì)出典型的樣本集。最后將輸入數(shù)據(jù)集導(dǎo)入到SVM模型中，產(chǎn)生其對(duì)應(yīng)的輸出數(shù)據(jù)。由表4的結(jié)果可知，生成的四個(gè)SVM模型能準(zhǔn)確對(duì)輸入數(shù)據(jù)進(jìn)行分類(lèi)預(yù)測(cè)，很好地映射輸入輸出之間的關(guān)系。并且生成預(yù)測(cè)輸出數(shù)據(jù)，由預(yù)測(cè)的輸出和生成的輸入數(shù)據(jù)組合成覆蓋率更高的測(cè)試用例集。

5 結(jié)語(yǔ)

隨著近年來(lái)，機(jī)器學(xué)習(xí)領(lǐng)域的發(fā)展，將機(jī)器學(xué)習(xí)算法和軟件測(cè)試用例生成結(jié)合起來(lái)已經(jīng)成為一個(gè)新的研究方向。尤其是在黑盒測(cè)試中，機(jī)器學(xué)習(xí)算法能夠?qū)ξ粗敵鼋Y(jié)果的樣本進(jìn)行較為精準(zhǔn)的預(yù)測(cè)。本文就是通過(guò)pict工具生成未知輸出結(jié)果的樣本，然后將未知輸出結(jié)果的樣本輸入到訓(xùn)練好的GA-SVM模型中進(jìn)行分類(lèi)，生成滿足覆蓋率要求的測(cè)試用例集。此測(cè)試用例集數(shù)量小，都是由工具自動(dòng)生成的，具有很好的可維護(hù)性。但是針對(duì)不同的軟件系統(tǒng)，要設(shè)計(jì)不同的SVM模型來(lái)提高準(zhǔn)確率。此過(guò)程中，需要對(duì)常用的幾種SVM模型進(jìn)行對(duì)比分析，選取其中準(zhǔn)確率最高的SVM模型。未來(lái)的工作是如何提高選取模型的效率和準(zhǔn)確率，進(jìn)一步提高生成測(cè)試用例集的覆蓋率。