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

潘世昊 張海波 左小凱 鄧鴻博

（中國船舶集團有限公司第七○九研究所 武漢 430205）

1 引言

測試用例的設計是軟件測試的核心步驟，一個好的測試用例集能夠以極小的測試用例數量實現極高的用例覆蓋率。近年來，軟件的功能日益提高導致其結構越來越復雜，尤其是在進行黑盒測試過程中，將測試用例的輸入輸出關系對應起來更加困難，并且生成的測試用例集往往數量較大［1］。因此，許多研究人員都為生成覆蓋率高數量小的測試用例集進行探索研究［2］。

在進行功能測試前，首先要對規格說明中的需求進行約簡整合。然后再通過因果圖法、等價類劃分法等方法選取得到一組典型的測試數據，減少測試用例的數量［3］。隨著機器學習技術和理論得到了巨大的發展，機器學習也已經逐漸應用在了軟件測試用例集的生成和優化方面。文獻［4］提出利用神經網絡和程序變異的測試用例輸出預測方法；文獻［5］提出了通過Ranking SVM算法，對測試用例集進行排序篩選的方法；文獻［6］提出通過聚類算法實現對所需測試用例的自動化識別；文獻［7］通過強化學習實現測試用例集的持續優化集成，提升測試效率。

微軟公司的pict工具廣泛應用于測試用例的生成，它利用組合原理生成覆蓋率高數量小的測試用例集，但是生成的測試用例都缺少預期結果。如果人工進行預測結果的填寫，將會耗費大量的人力，并且過程枯燥。

針對以上問題，本文采用GA-SVM模型進行測試用例集的自動生成，通過GA算法選取SVM模型參數的最佳值。然后利用pict工具生成兩組合的小型輸入數據集，將此數據集進行標記后作為SVM模型的訓練數據集。最后再次使用pict工具生成更高組合的輸入數據集，由SVM模型進行預測其輸出數據集。由實驗結果分析可知，本文中的方法在測試用例自動生成和模型覆蓋率方面，均取得了較好的效果。

2 模型建立與訓練

2.1 系統模型的建立

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

其中FlightService包含以下三個方面的信息：航班號、出發抵達城市、起飛抵達時間。UserSer?vice包含以下兩個方面的信息：用戶名、密碼。Ho?telService包含以下信息：剩余房間數。RestaSer?vice包含以下信息：剩余餐位數。

圖1 模塊圖

將上述信息整合到一起，形成了7個輸入參數。記為M=｛M1，M2，M3，M4，M5，M6，M7｝將每個參數的取值進行離散化，例如：航班號正確為1，錯誤為0；出發抵達城市與航班號相符合為1，不符合為0；用戶名正確為1，用戶名錯誤為0；密碼正確為1，錯誤為0；起飛抵達時間與航班號符合為1，不符合為0；剩余房間數取值正確為1，錯誤為0；剩余餐位數取值正確為1，錯誤為0。

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

2.2 SVM模型的建立

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

在訓練SVM模型的過程中，需要對兩個重要的參數c，g進行優化，以獲得好的分類結果。c為懲罰參數，c越大，對誤分類結果進行的懲罰越大，對誤差的容忍性更小；c越小，對誤分類的結果進行的懲罰越小，對誤差的容忍性更高。但是c過大則會發生過擬合現象，過小則會發生欠擬合現象。g與支持向量的個數有關，g越大，個數越少；g越小，個數越多。但是g設得太大的話，支持向量太多，會使得模型集中作用于支持向量附件，對其他未知數據的分類效果變差；g設得太小，支持向量太少，會使得模型的平滑性變大，無法從訓練集中學習到足夠的規律，使得訓練完成的模型無法正確分類。

PSO算法、GA算法、GridSearch算法是常見的尋優算法，適用于對模型參數的尋找。為了得到較好的c，g值，本文選用UCI數據集中的三個典型數據集 balance_scale、vehicle、iris進行實驗分析。對上述數據集按訓練集和測試集4：1進行劃分，然后分別利用上述三種算法進行參數尋優。得到c，g的最佳參數取值后，將c，g導入到SVM模型中，利用訓練集對模型進行訓練。訓練完成之后，利用劃分出來的測試集對模型準確率進行檢測。

表1 不同尋優算法得到測試集準確率

由表1對比可知，在對SVM模型中的c，g值尋優的算法中，GA算法訓練得到的SVM模型分類準確率最高，所以本文采用用GA算法對SVM模型進行尋優。

3 典型用例的設計

對軟件系統進行功能測試時，輸入參數值和輸入參數之間的相互關系會影響輸出參數的結果［8］。因此，如何選擇輸入參數的取值能滿足輸出結果的全覆蓋是一個難題。若通過輸入參數組合全覆蓋產生測試用例，雖然會使覆蓋率變高，但是會使得測試用例集過大，增加軟件測試的成本。在實際的功能測試中，可以利用組合測試覆蓋準則來平衡覆蓋率和成本，產生一個規模小、覆蓋率高的測試用例集。

本文利用pict工具實現多參數組合覆蓋。所謂多參數組合覆蓋是指選定的多個參數的所有取值出現在測試用例集中。而pict的實現原理是利用配對法（Pairwise）對輸入參數進行比較排序。排序之后從中挑選分散均勻的樣本進行實驗，這些樣本具有很強的代表性，得到的試驗結果等效于大量全面的試驗結果。

表2 pict生成的典型用例表

經相關研究得出的結論，兩參數組合覆蓋的測試用例集能檢測出大約70%的缺陷，三參數組合覆蓋的測試用例集能檢測出大約90%的缺陷［9］。若想達到更高的缺陷檢測率，則需要更高的參數組合，與此同時測試數據的個數也呈現正比例增長。假設一個軟件系統的功能輸入域有四個參數A，B，C，D。對于參數A而言，其值域為Da=｛a1，a2，a3，a4，a5｝；參數B，其值域為Db=｛b1，b2，b3，b4｝；參數C，其值域為Dc=｛c1，c2，c3｝；參數D，其值域為Dd=｛d1，d2｝。若對上述輸入參數進行全參數覆蓋取值，則需要5×4×3×2=240條測試數據。若使用pict工具，自動生成兩參數覆蓋率的測試數據，則只需要20條；自動生成三參數覆蓋率的測試數據，則只需要120條。以pict工具生成的測試數據為基礎，設計相應的測試用例集，可以有效地減少測試用例的數量，防止測試數據呈正比例增長的情況。

對系統模型中的參數M分析可知，M1，M2，M3與FlightService密切相關，M4，M5與UserService密切相關，所以將M1，M2，M3設置成三組合參數覆蓋，將M4，M5設置成兩參數組合覆蓋。

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

表3 補充用例表

4 實驗結果和分析

通過表2和表3中的用例集對GA-SVM模型進行訓練，然后利用訓練完成后的GA-SVM模型對未知輸出結果的樣本進行預測。本實驗使用臺灣大學林智仁教授編寫的Libsvm工具箱，SVM模型采用CSCV，RBF核函數類型，GA算法參數尋優。然后對輸出參數集中的四個參數分別設計一個GA-SVM模型進行訓練，并且每個輸出參數為0或1，均為二分類模型。

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

表4 GA-SVM模型分類準確率表

本實驗通過對航班查詢服務系統的功能進行描述，確定了輸入輸出關系及輸入輸出域，然后利用pict工具生成滿足特定組合覆蓋的輸入參數集，同時考慮輸入參數和輸出參數類別全覆蓋，設計出典型的樣本集。最后將輸入數據集導入到SVM模型中，產生其對應的輸出數據。由表4的結果可知，生成的四個SVM模型能準確對輸入數據進行分類預測，很好地映射輸入輸出之間的關系。并且生成預測輸出數據，由預測的輸出和生成的輸入數據組合成覆蓋率更高的測試用例集。

5 結語

隨著近年來，機器學習領域的發展，將機器學習算法和軟件測試用例生成結合起來已經成為一個新的研究方向。尤其是在黑盒測試中，機器學習算法能夠對未知輸出結果的樣本進行較為精準的預測。本文就是通過pict工具生成未知輸出結果的樣本，然后將未知輸出結果的樣本輸入到訓練好的GA-SVM模型中進行分類，生成滿足覆蓋率要求的測試用例集。此測試用例集數量小，都是由工具自動生成的，具有很好的可維護性。但是針對不同的軟件系統，要設計不同的SVM模型來提高準確率。此過程中，需要對常用的幾種SVM模型進行對比分析，選取其中準確率最高的SVM模型。未來的工作是如何提高選取模型的效率和準確率，進一步提高生成測試用例集的覆蓋率。