融合智能優(yōu)化的軟件測試用例生成方法

黨向盈，李金鳳

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

1 引言(Introduction)

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

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

考慮到程序中的缺陷隱蔽性較強(qiáng)，很多學(xué)者[5]提出變異測試概念，它是通過主動(dòng)出擊的方式，模擬程序中真實(shí)的缺陷，也就是對程序中的原語句進(jìn)行變異，被改動(dòng)后的語句為變異語句，變異之后的程序?yàn)樽儺愺w[6]。

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

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

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

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

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

首先，登錄測試平臺，點(diǎn)擊“導(dǎo)入被測程序”的“缺陷注入”，可以實(shí)現(xiàn)測試對象的預(yù)處理。“缺陷注入”功能是通過自動(dòng)化變異測試工具實(shí)現(xiàn)的，對被測語句實(shí)施變異，注入一些缺陷(生成變異體)。

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

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

3 聚類缺陷(Faults clustering)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 生成測試用例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論(Conclusion)

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