基于自適應(yīng)高斯混合模型的軟件測試用例集約簡算法研究

楊永國

(中國人民解放軍91550部隊(duì)，遼寧 大連 116023)

0 引言

軟件規(guī)模越大，其邏輯復(fù)雜性越高，對這些軟件的可靠性要求也就越高。軟件的隱藏錯誤能夠造成其自身運(yùn)行的失敗。也就是說軟件的隱藏錯誤是影響軟件可靠性的最關(guān)鍵因素之一[1]。對于小規(guī)模的軟件，工程實(shí)踐中大多采用人工設(shè)置斷點(diǎn)的方法來進(jìn)行測試，以查找出錯誤。不過人工方法判斷錯誤位置較為復(fù)雜，且難度較大，不適用于大規(guī)模的軟件測試。因此，為了更加精準(zhǔn)且高效地查找和消除軟件錯誤，專家學(xué)者們開展了廣泛的研究，提出了一些解決方法，并研發(fā)出對軟件進(jìn)行單元、靜態(tài)和動態(tài)測試的工具軟件。這些方法和測試軟件，都要求測試用例集盡可能覆蓋全面，只有這樣才能精準(zhǔn)地定位錯誤，提高測試的有效性[2-4]。但測試用例集包含的用例數(shù)量應(yīng)該盡量約簡，以降低測試成本。

劉鋒等人提出基于向量相似度的測試用例集約簡方法[5]。張蕊等人提出一種基于搜索樹的用例約簡方法，求得約簡問題的全局最優(yōu)解[6]。謝經(jīng)緯在測試用例集約簡中引入需求分析，提出了兩階段用例集優(yōu)化方法，分為需求切片和用例集優(yōu)化兩個步驟[7]。張晨光等人提出一種在線測試用例集約簡方法，將測試集約簡嵌入測試生成流程內(nèi)，測試生成過程為測試集約簡提供了測試序列與測試目標(biāo)之間的滿足關(guān)系[8]。楊羊等人通過定義和合并基于ASM模型測試生成的等價遷移和等價狀態(tài)，減少了無效訪問狀態(tài)和無效遷移路徑的數(shù)量，實(shí)現(xiàn)了測試用例集空間的約簡[9]。蘇小紅等人采用面向錯誤定位需求的測試用例約簡方法，降低錯誤定位的復(fù)雜度，提高錯誤定位的精度[10]。

這些用來約簡測試用例集的方法還存在一些主要問題如下：1)如何建模測試用例集之間的關(guān)系，以提高查找軟件錯誤的準(zhǔn)確度；2)如何實(shí)現(xiàn)參數(shù)設(shè)置的簡化，或者實(shí)現(xiàn)自適應(yīng)的參數(shù)設(shè)置。為了解決這些問題，本文提出了一種基于自適應(yīng)高斯混合模型的用例約簡算法。該算法引入高斯混合模型，尋找測試用例間的關(guān)系，抽取滿足測試需求的測試用例，實(shí)現(xiàn)用例集的約簡；同時通過自適應(yīng)策略，簡化參數(shù)設(shè)置。

1 高斯混合模型

軟件測試用例集數(shù)據(jù)的概率分布通常很復(fù)雜，因此引入高斯混合模型來模擬逼近和約簡軟件測試用例集，以簡化問題[11-14]。高斯混合模型(GMM，gaussian mixture model)是M個高斯模型(聚類簇)的加權(quán)和，其對數(shù)據(jù)的M類概率密度分布進(jìn)行高斯估計(jì)。每個高斯概率密度函數(shù)都與一個類對應(yīng)。訓(xùn)練時采用了期望最大(EM，expectation maximization)算法。

設(shè)每個樣本都對應(yīng)于一個類，也就是對應(yīng)于一個高斯概率密度函數(shù)，而整個樣本集對應(yīng)M個高斯概率密度函數(shù)。但具體每個樣本xi對應(yīng)于哪個高斯概率密度函數(shù)不確定，在GMM中，每個高斯概率密度函數(shù)所占的權(quán)重φj也不確定。式(1)所示為GMM:

(1)

每一個高斯概率密度函數(shù)，也就是單高斯模型都有3個參數(shù)φj、μj、∑j。進(jìn)行高斯混合模型建模時，就要確定3N個參數(shù)。

需要通過樣本集X={x1,xi,…,xN}來估計(jì)GMM的所有參數(shù)[15]Φ=(φ1,φj,…，φM)T，樣本xj的概率如式(2)所示:

(2)

其中:Cj為協(xié)方差矩陣。

對GMM參數(shù)進(jìn)行估計(jì)，目前最多采用的是EM算法，其具體流程如下[15-19]：

2)后驗(yàn)概率估計(jì)步驟。用式(3)估計(jì)φj的后驗(yàn)概率:

(3)

3)最大化步驟。根據(jù)式(4)對權(quán)值φj進(jìn)行更新:

(4)

根據(jù)式(5)對均值μj進(jìn)行更新:

(5)

根據(jù)式(6)對方差矩陣Cj進(jìn)行更新:

(6)

4)收斂條件。迭代計(jì)算步驟2)和步驟3)，權(quán)值φj、均值μj和方差矩陣Cj會不斷地更新，當(dāng)p(X|Φ)-p(X|Φ)′<ε時停止進(jìn)行迭代。p(X|Φ)′為更新權(quán)值φj、μj均值和方差矩陣Cj后根據(jù)式(3)計(jì)算的值，ε為閾值，一般ε=10-5。

2 基于自適應(yīng)高斯混合模型

但采用的高斯混合模型聚類簇數(shù)目通常是經(jīng)驗(yàn)值，很容易造成聚類準(zhǔn)確度的降低。具體到軟件測試用例集約簡的場景，經(jīng)驗(yàn)聚類簇數(shù)目對用例集多變的適應(yīng)性較差，無法做到自適應(yīng)。因此本文對高斯混合模型進(jìn)行改進(jìn)，使其可以自適應(yīng)的確定聚類簇數(shù)目。

改進(jìn)的思想為：使用K-means初始化EM，自適應(yīng)地確定聚類簇數(shù)目，在此過程中能夠評判聚類結(jié)果，同時給出式高斯混合模型的所有參數(shù)，這些參數(shù)作為各個聚類簇進(jìn)行新一輪迭代計(jì)算的參數(shù)，最終得到的結(jié)果更趨于最優(yōu)解[15]。

針對軟件測試用例集約簡研究，為解決現(xiàn)有高斯混合模型聚類算法只能使用經(jīng)驗(yàn)聚類簇數(shù)目值的缺陷，根據(jù)上述改進(jìn)思想，本文使用了自適應(yīng)高斯混合模型算法，算法的具體實(shí)現(xiàn)步驟如下所述，實(shí)現(xiàn)流程如圖1所述。

圖1 自適應(yīng)高斯混合模型的實(shí)現(xiàn)流程

1)先按經(jīng)驗(yàn)設(shè)置M0個聚類簇，按照第1章節(jié)中的步驟(1)進(jìn)行初始化協(xié)方差矩陣Cj、每個高斯概率密度函數(shù)所占的權(quán)重φj和均值μj，并用EM算法對模型進(jìn)行優(yōu)化，計(jì)算出初始化聚類結(jié)果。

2)在后續(xù)迭代計(jì)算的過程中，計(jì)算出第i個樣本xi屬于第j個聚類簇的概率pi,j。根據(jù)式(7)計(jì)算最大的(pi,j)max與排第二的(pi,jmax-1)的比值ri。第i個樣本xi聚類到某個聚類簇，要求(pi,j)max相對于(pi,j)max-1要有明顯的差別，即(pi,j)max應(yīng)當(dāng)比(pi,j)max-1大很多。也就是可以用ri來衡量聚類結(jié)果的優(yōu)劣。ri越小，聚類結(jié)果越好；ri越大，聚類結(jié)果越差。

3)設(shè)定閾值Thr。通過給定Th的值，能夠衡量類聚類結(jié)果是否滿足要求。當(dāng)ri≤Thr時，第i個樣本xi可以歸類為(pi,j)max對應(yīng)的聚類簇；當(dāng)ri>Thr時，第i個樣本xi不適合歸類為目前的所有聚類簇，需要增加聚類簇數(shù)目。聚類簇數(shù)目不能無限的增加下去，否則就失去了聚類的意義，需要設(shè)定一個最大聚類簇數(shù)目值Mmax。當(dāng)聚類簇數(shù)目數(shù)目達(dá)到Mmax時，則第i個樣本可以歸類為(pi,j)max對應(yīng)的聚類簇，而不再新增聚類簇的數(shù)目。

4)當(dāng)聚類簇數(shù)目增加后，需要對新模型的參數(shù)進(jìn)行初始化調(diào)整。迭代的重新執(zhí)行步驟1)～3)，當(dāng)聚類簇數(shù)目不再增加，或者達(dá)到最大時，完成模型訓(xùn)練，得到模型參數(shù)。

5)當(dāng)步驟4)得到的模型中，存在φj很小的聚類簇,即φj≤Thφ時，可將該聚類簇刪除，并將該聚類簇對應(yīng)的樣本xj歸類到倒數(shù)第二次迭代時(pi,j)max對應(yīng)的聚類簇中。因?yàn)榫垲惔氐摩誮≤Thφ時，可以認(rèn)為該聚類簇的代表性不足。然后對模型進(jìn)行計(jì)算，得到最終的模型CL，及模型參數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用使用廣泛并且便于比較的西門子軟件測試用例集[1,20]。該由Siemens Corporate Research的專家開發(fā)，含有7類程序代碼Print_tokens1、Print_tokens2、Schedule1、Schedule2、Replace、tacs和tot_info，每類程序代碼有1個無錯誤版本和一些含有錯誤的版本。軟件測試用例集中每類程序代碼的行數(shù)、初始測試用例數(shù)、程序中錯誤數(shù)、測試用例數(shù)如表1所示[1]。針對每類程序代碼，該軟件測試用例集使用了5種類型編程語言進(jìn)行的代碼編寫，滿足常用編程語言需求的代碼需求。

表1 軟件測試用例約簡用數(shù)據(jù)集

3.2 評價標(biāo)準(zhǔn)

實(shí)驗(yàn)中，采用約簡率、錯誤檢測率和錯誤檢測丟失率這三個指標(biāo)來評價實(shí)驗(yàn)結(jié)果，以驗(yàn)證算法的有效性、正確性和穩(wěn)定性。

3.2.1 約簡率

約簡率計(jì)算如式(8)所示，為現(xiàn)有軟件測試用例集中的測試用例數(shù)目與約簡后軟件測試用例集中的測試用例數(shù)目的差值，比上現(xiàn)有軟件測試用例集中的測試用例數(shù)目，得到的比值[1]。

(8)

其中:RR為約簡率，|USN|表示現(xiàn)有軟件測試用例集中的測試用例數(shù)目；|USN′|表示約簡后軟件測試用例集中的測試用例數(shù)目。

3.2.2 錯誤檢測率

錯誤檢測率計(jì)算如式(9)所示，為約簡學(xué)習(xí)初始用例后，從測試用例中檢測到的程序代碼錯誤個數(shù)與測試用例中實(shí)際程序代碼錯誤個數(shù)的比值[1]。

(9)

其中：EDR為錯誤檢測率，EN表示現(xiàn)有軟件測試用例集的測試用例包含的程序代碼錯誤數(shù)；EN′表示使用約簡算法學(xué)習(xí)初始用例后，從軟件測試用例集的測試用例中檢測出的程序代碼錯誤數(shù)。

3.2.3 錯誤檢測丟失率

錯誤檢測丟失率計(jì)算如式(10)所示，為約簡學(xué)習(xí)初始用例后，從測試用例中檢測到的程序代碼錯誤個數(shù)與測試用例中實(shí)際程序代碼錯誤個數(shù)的差值，比上測試用例中實(shí)際程序代碼錯誤個數(shù)，得到的比值[1]。

(10)

其中:ELR為錯誤檢測丟失率。

由式(8)、式(9)和式(10)可以比較高斯混合模型、模糊K-Means聚類模型和本文提出算法的約簡率、錯誤檢測率和誤差檢測丟失率。

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

為了驗(yàn)證本文提出的基于自適應(yīng)高斯混合模型的軟件測試用例集簡約算法的性能，對比分析了本文提出算法、基于高斯混合模型的軟件測試用例集簡約算法和基于模糊K-Means聚類模型的軟件測試用例集簡約算法。

3.3.1 約簡率分析

使用3種算法約簡后，得到的軟件測試用例集中的測試用例數(shù)量如表2所示[1]。

表2 約簡后的初始用例數(shù)

3種算法約簡率如表3所示[1]。通過分析，基于模糊K-Means聚類模型的軟件測試用例集簡約算法的約簡率優(yōu)于基于高斯混合模型的軟件測試用例集簡約算法。本文提出算法的約簡率高于上述兩種算法，其總約簡率相對基于模糊K-Means聚類模型的軟件測試用例集簡約算法高11.46%，相對基于高斯混合模型的軟件測試用例集簡約算法高6.42%。約簡率的提升，可以在一定程度上降低軟件測試的復(fù)雜度，提高軟件測試的效率。

表3 3種算法的約簡率

3.3.2 錯誤檢測率分析

使用3種算法約簡后，從測試用例集中檢測出來的程序代碼錯誤數(shù)量如表4所示[1]。

表4 約簡后的檢測出的錯誤數(shù)

3種算法的錯誤檢測率如表5所示。從表中數(shù)據(jù)可知，基于模糊K-Means聚類模型的軟件測試用例集簡約算法的錯誤檢測率優(yōu)于基于高斯混合模型的軟件測試用例集簡約算法。本文提出算法的錯誤檢測率高于上述兩種算法，其總錯誤檢測率相對基于模糊K-Means聚類模型的軟件測試用例集簡約算法高34.53%，相對基于高斯混合模型的軟件測試用例集簡約算法高4.76%。使用本文提出算法能夠檢測出更多的錯誤數(shù)，可以提高軟件測試的可靠性，進(jìn)而提高被測軟件的正確性。

表5 3種算法的錯誤檢測率

3.3.3 錯誤檢測丟失率分析

3種算法的錯誤檢測丟失率如表6所示。

表6 3種算法的錯誤檢測丟失率

從表中數(shù)據(jù)可知，基于模糊K-Means聚類模型的軟件測試用例集簡約算法的錯誤檢測丟失率優(yōu)于基于高斯混合模型的軟件測試用例集簡約算法。本文提出算法的錯誤檢測丟失率低于上述兩種算法。錯誤檢測丟失率低，代表漏檢的少錯誤數(shù)量，錯誤檢測丟失率越低越好。相對其它兩種算法，本文提出算法的錯誤檢測丟失率最低，這體現(xiàn)了提出算法約簡得到的測試用例集對程序代碼錯誤的覆蓋度較高。

4 結(jié)束語

軟件測試用例集聚類和約簡是一個時研時新且充滿挑戰(zhàn)的研究方向。當(dāng)前軟件測試用例集聚類、約簡方法存在需要根據(jù)經(jīng)驗(yàn)給出聚類簇數(shù)目，導(dǎo)致自適應(yīng)性不強(qiáng)的問題。本文提出了一種改進(jìn)的高斯混合模型算法應(yīng)用于軟件測試用例集約簡，以自適應(yīng)的確定聚類簇的數(shù)目，并評估聚類效果的優(yōu)劣。

提出的自適應(yīng)高斯混合模型算法的優(yōu)點(diǎn)是：算法在初始化和迭代過程中無需固定聚類簇數(shù)目，可以根據(jù)不同軟件測試用例集數(shù)據(jù)的特點(diǎn)自適應(yīng)確定聚類簇數(shù)目，提升聚類的自適應(yīng)性、準(zhǔn)確性和泛化性，實(shí)現(xiàn)用例集最優(yōu)約簡化。實(shí)驗(yàn)結(jié)果表明，相對于高斯混合模型算法和模糊K-means聚類算法，提出算法的約簡率和錯誤檢測率更高。約簡后雖然軟件測試用例集規(guī)模精簡，但覆蓋率高。