楊永國(guó)

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

0 引言

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

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

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

1 高斯混合模型

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

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

(1)

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

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

(2)

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

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

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

(3)

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

(4)

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

(5)

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

(6)

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

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

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

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

針對(duì)軟件測(cè)試用例集約簡(jiǎn)研究，為解決現(xiàn)有高斯混合模型聚類(lèi)算法只能使用經(jīng)驗(yàn)聚類(lèi)簇?cái)?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個(gè)聚類(lèi)簇，按照第1章節(jié)中的步驟(1)進(jìn)行初始化協(xié)方差矩陣Cj、每個(gè)高斯概率密度函數(shù)所占的權(quán)重φj和均值μj，并用EM算法對(duì)模型進(jìn)行優(yōu)化，計(jì)算出初始化聚類(lèi)結(jié)果。

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

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

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

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

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

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

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

表1 軟件測(cè)試用例約簡(jiǎn)用數(shù)據(jù)集

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

3.2.1 約簡(jiǎn)率

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

(8)

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

3.2.2 錯(cuò)誤檢測(cè)率

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

(9)

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

3.2.3 錯(cuò)誤檢測(cè)丟失率

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

(10)

其中:ELR為錯(cuò)誤檢測(cè)丟失率。

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

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

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

3.3.1 約簡(jiǎn)率分析

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

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

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

表3 3種算法的約簡(jiǎn)率

3.3.2 錯(cuò)誤檢測(cè)率分析

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

表4 約簡(jiǎn)后的檢測(cè)出的錯(cuò)誤數(shù)

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

表5 3種算法的錯(cuò)誤檢測(cè)率

3.3.3 錯(cuò)誤檢測(cè)丟失率分析

3種算法的錯(cuò)誤檢測(cè)丟失率如表6所示。

表6 3種算法的錯(cuò)誤檢測(cè)丟失率

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

4 結(jié)束語(yǔ)

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

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