黨向盈，李金鳳

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

1 引言(Introduction)

軟件測試是軟件開發(fā)生命周期中的一個重要環(huán)節(jié)，其目的是通過檢測盡可能多的缺陷以保證軟件質(zhì)量[1]。然而，傳統(tǒng)的軟件測試方法很難檢測大量潛在的缺陷。隨著人工智能技術的發(fā)展，軟件測試方法智能化程度越來越高。在進行軟件測試時，將程序的輸入作為測試用例[2]。對于程序中的缺陷，如何高效地獲得測試用例檢測它們，一直是很多學者的研究熱點。

本文借鑒人工智能中的進化算法和聚類方法，構建軟件測試平臺，生成具有檢測缺陷能力的測試用例。近年來，進化算法一直被廣泛地應用于測試用例生成[3]。進化算法的進化策略包括選擇、交叉、變異、種群競爭或合作等[3]。此外，聚類已經(jīng)成為實施數(shù)據(jù)挖掘和分析的重要方式之一[4]，它是一種無監(jiān)督機器學習的分類方法，將一些相似的對象形成一個個集合(簇)，根據(jù)數(shù)據(jù)在簇中是否有重疊數(shù)據(jù)，將聚類分為硬聚類和模糊聚類[5]。

考慮到程序中的缺陷隱蔽性較強，很多學者[5]提出變異測試概念，它是通過主動出擊的方式，模擬程序中真實的缺陷，也就是對程序中的原語句進行變異，被改動后的語句為變異語句，變異之后的程序為變異體[6]。

鑒于以上分析，本文借鑒變異測試技術[7]，以“主動出擊”的方式，在程序中植入變異語句作為潛在的缺陷；再采用進化算法和聚類方法，生成具有檢測缺陷能力的測試用例，并開發(fā)一套智能軟件測試系統(tǒng)。

2 智能軟件測試系統(tǒng)總體框架 (Framework of intelligent software test system)

圖1為本文所提智能軟件測試系統(tǒng)總體框架，測試主要分為五步，下面結合可視化“智能軟件測試平臺”(圖2)，闡述實施過程。

圖1 智能軟件測試流程Fig.1 Process of intelligent software testing

圖2 智能軟件測試平臺Fig.2 System for intelligent software testing

首先，登錄測試平臺，點擊“導入被測程序”的“缺陷注入”，可以實現(xiàn)測試對象的預處理?！叭毕葑⑷搿惫δ苁峭ㄟ^自動化變異測試工具實現(xiàn)的，對被測語句實施變異，注入一些缺陷(生成變異體)。

其次，對于注入的眾多缺陷，點擊“缺陷聚類”，啟動編程環(huán)境。如圖1所示，“缺陷聚類”可以通過四種不同的聚類策略實現(xiàn)。同時，可以采用經(jīng)典硬聚類和模糊聚類方法聚類缺陷。首先設置進化算法的參數(shù)，包括種群數(shù)目、種群規(guī)模和最大迭代次數(shù)等，單擊“生成測試用例”，啟動編程環(huán)境。算法1給出經(jīng)典模糊聚類方法實現(xiàn)缺陷聚類的步驟。然后采用進化算法生成測試用例。先設置進化算法的參數(shù)，單擊“生成測試用例”，啟動編程環(huán)境。輸出生成測試用例的時間、迭代次數(shù)和測試用例，以及成功率和缺陷檢測率。

最后，分析測試結果，主要從兩個方面評價各種方法的性能。當采用不同聚類方法和策略實現(xiàn)眾多缺陷的聚類時，通過三種指標評價聚類性能。當采用進化算法生成測試用例時，通過四種評價指標考察算法的性能。對比測試結果和性能指標，給出最優(yōu)方法并進行分析，完成軟件測試報告。

3 聚類缺陷(Faults clustering)

研究表明，缺陷之間是有關聯(lián)的，也就是檢測到一個缺陷的測試用例，同時可能檢測到其他缺陷[8]。而且缺陷的重要度不一樣，因此為了保證聚類缺陷的性能，需要考慮缺陷重要度和缺陷之間的關聯(lián)度。為了評價聚類缺陷的性能，采用四種策略聚類缺陷，分別如下。

(1)RC：首先基于缺陷重要度排序缺陷，以最重要的缺陷為聚類中心；然后基于缺陷之間的關聯(lián)，對缺陷聚類；最后采用進化算法生成測試用例。

(2)R￢C：缺陷只進行排序，不進行聚類。排序好的缺陷序列中，任意選一個缺陷采用進化算法生成測試用例；判斷該測試用例是否能夠檢測其他缺陷；反復執(zhí)行此過程，直到滿足終止準則。

(3)￢RC：缺陷沒有進行排序，直接進行聚類。在缺陷集合中，首先隨機選擇某一缺陷作為簇中心，然后聚類缺陷，最后生成測試用例。

(4)￢R￢C：缺陷沒有排序和沒有聚類。從缺陷集合中，一個接一個地隨機選擇缺陷，作為優(yōu)化目標，生成檢測它們的測試用例；判斷該測試用例是否能夠檢測其他缺陷；反復執(zhí)行此過程，直到滿足終止準則。

對于以上四種策略中的聚類方法，可以采用硬聚類和模糊聚類方法對缺陷分類。此外，為了進一步考察聚類缺陷的性能，即評價不同方法的性能，選擇一些評價指標。

4 基于進化算法生成測試用例(Test case generation based on evolutionary algorithm)

4.1 優(yōu)化模型構建

為了采用進化算法生成測試用例，需要構建測試用例生成問題的優(yōu)化模型。

(1)目標函數(shù)。針對某一個缺陷Fi，生成能檢測Fi的測試用例，作為進化算法優(yōu)化的目標。因此，對于Fi，設目標函數(shù)為f(X)，其中X為決策變量，即程序的輸入，也是實驗中需要找到的測試用例。當X能檢測到Fi，f(X)=0；否則f(X)=1。因此，當且僅當f(X)=1取最小值0時，X檢測到Fi。通過這種方式，生成檢測到Fi測試用例的問題，轉(zhuǎn)化為求f(X)最小值問題，可以表示為minf(X)。

然而，f(X)的取值只有0和1兩種，顯而易見，如此目標函數(shù)很難引導種群的進化。為了提供更多的信息指導種群進化，需要為優(yōu)化模型增加一個約束。

(2)約束函數(shù)。研究表明，在檢測一個變異體之前，測試用例首先可達缺陷位置，也就是說，在檢測缺陷之前，測試用例必須先覆蓋被測語句。因此，基于分支覆蓋的約束函數(shù)，可以表示如下：

其中，Appr(θ,X)是X對于θ的層接近度，dist(θ,X)為分支距離。由式(1)可知，當且僅當g(X)=0時，X能覆蓋θ。

(3)優(yōu)化模型。根據(jù)X、f(X)和g(X)，建立生成能檢測缺陷Fi的測試用例的優(yōu)化模型如下：

其中，D為程序的輸入域。

4.2 生成測試用例

對于上面的優(yōu)化模型，采用進化算法生成測試用例。遺傳算法(GAs)已經(jīng)被廣泛地應用于測試用例生成。一般而言，單種群遺傳算法執(zhí)行一次，只能針對一個優(yōu)化目標，也就是只能為一個缺陷生成測試用例。顯然，對于多個簇的缺陷，單種群遺傳算法的效率比較低下?？紤]到缺陷已經(jīng)被劃分為多個簇，可以采用多種群遺傳算法生成測試用例。

考慮到優(yōu)化模型中包括一個目標函數(shù)和一個約束函數(shù)，適應值函數(shù)可以表示如下：

其中，φ是很小的正整數(shù)，它的作用是確保括號里的值大于0。由式(3)可知，當且僅當fit(X)=0時，X能檢測到缺陷Fi。

在多種群遺傳算法中，一個種群包含m個子種群，分別處理m個簇中缺陷的測試用例生成，所有的子種群并行進化，第i個子種群的進化個體為其中Size為子種群中進化個體個數(shù)。算法的輸出為生成的測試用例集。終止條件有兩個，一個是對于m個簇的缺陷，期望的測試用例全部找到；另一個是種群進化到最大進化代數(shù)g。

算法2為基于多種群遺傳算法生成測試用例，輸入為種群(包括m個子種群)和m個簇；輸出為測試用例集T。

首先，初始化m個子種群和算法中的各種參數(shù)，并設變量count=1；對于簇Ci，每個進化個體都執(zhí)行中心缺陷，判斷終止條件是否滿足，如果沒有滿足，再用Ci對應進化個體檢測其他簇中缺陷是否能檢測；如果能，終止第i個子種群的進化，保存測試用例；如果不滿足，進化個體進行遺傳操作，進行選擇、交叉、變異操作。其次，所有的簇采用同樣的策略，每個簇以并行方式完成對應簇內(nèi)缺陷的測試用例生成。最后，對所有簇輸出測試用例集。

測試時，實現(xiàn)隨機方法、單種群遺傳算法和多種群遺傳算法生成測試用例。單種群遺傳算法與多種群遺傳算法生成測試用例的不同之處在于，單種群生成測試用例時，每個簇以串行的方式，采用遺傳算法生成能檢測簇中心的測試用例。采用隨機法生成測試用例時，一個一個簇依次采用串行方式生成測試用例。

考慮到多種群遺傳算法的最大迭代次數(shù)為3,000，那么采用隨機方法時，隨機生成測試用例為3,000 次，然后執(zhí)行缺陷。單種群遺傳算法的參數(shù)設置與多種群遺傳算法相同，它們的區(qū)別在于，單種群遺傳算法只有一個子種群，一次只能優(yōu)化一個目標；多種群遺傳算法有多個子種群，一個子種群優(yōu)化一個簇中所有的缺陷。多種群遺傳算法的優(yōu)勢在于，在每一次迭代中，多種群遺傳算法執(zhí)行一次，幾個子種群能夠以并行方式檢測不同簇中的多個缺陷。相比之下，基于隨機方法和單種群遺傳算法，測試用例是一個接著一個依次生成的。

為了比較三種方法生成測試用例的性能，選擇時間消耗、迭代次數(shù)、缺陷檢測率、成功率這幾種評價指標[4]。一般而言，如果生成測試用例的時間消耗越少，則對應的方法性能越好；迭代次數(shù)越少，則對應方法的效率越高。

缺陷檢測率可以表示如下：

此外，假設某種算法運行了W次，其中V次成功地找到檢測缺陷的期望數(shù)據(jù)，那么，成功率可以定義如下：

由式(5)可知，成功率越高，對應的算法的搜索性能越好。

5 軟件測試報告(Software testing reports)

本文所提軟件測試方法，結合了人工智能算法中的聚類、遺傳算法和多種群遺傳算法，對于隱蔽性強的缺陷，采用變異測試技術，模擬真實缺陷，生成能檢測缺陷的測試用例。開發(fā)的測試平臺可以應用于一般的基準程序和工業(yè)程序，測試范圍領域廣泛且數(shù)據(jù)類型、邏輯結構、功能和規(guī)模多種多樣。

實驗中，被測程序G1—G8分別在智能軟件測試平臺(圖2)上執(zhí)行，獲得的測試結果，然后比較分析各個方法的性能，并撰寫軟件測試報告。對八個被測程序，采用四種不同聚類策略獲得的缺陷檢測率的結果如圖3所示。由圖3可知，先基于缺陷重要度排序缺陷，以最重要的缺陷為聚類中心的RC方法獲得缺陷檢測率最高；基于R￢C和￢RC方法獲得的缺陷檢測率相差不多；沒有排序和沒有聚類的￢R￢C方法獲得的缺陷檢測率最低。這說明，對缺陷進行聚類和排序，有助于缺陷檢測率的提高。

圖3 基于四種聚類策略缺陷檢測率Fig.3 Fault detection rate based on four clustering strategies

圖4和圖5為基于不同算法生成測試用例的時間消耗和迭代次數(shù)。從測試結果可以看出，進化算法中的單種群和多種群遺傳算法采用全局搜索方式，大大提升了測試用例生成的效率，而且多種群遺傳算法利用個體之間信息共享方式，能夠提高測試數(shù)據(jù)找到的速度和迭代次數(shù)。

圖4 采用三種方法生成測試用例時的時間消耗(s)Fig.4 Time consumption of generating test case by the three methods (s)

圖5 采用三種方法生成測試用例時的迭代次數(shù)Fig.5 The number of iterations of generating test case by the three methods

6 結論(Conclusion)

智能軟件測試平臺融合了機器學習中的聚類方法和進化算法中的遺傳算法，應用于八個經(jīng)典的程序和工業(yè)軟件，從實驗數(shù)據(jù)可以看出，所提方法和開發(fā)的測試系統(tǒng)，通過多種群遺傳算法能夠獲得更好的缺陷檢測率。此外，通過時間消耗和迭代次數(shù)等指標驗證了所提方法能高效、快捷地找到檢測缺陷的測試用例。由此可見，本文方法是人工智能、自動化、計算數(shù)學及計算機多學科交叉，實現(xiàn)提高軟件測試效率的目的。該平臺具有較好的擴展性，可以與其他綜合實驗靈活地融合使用，具有一定的推廣價值和應用前景。