劉好斌,梁旗軍,肖 鵬

(南昌航空大學(xué)軟件學(xué)院,江西 南昌 330063)

1 引言

軟件可靠性測(cè)試用例的主要作用是測(cè)試軟件的可靠性,及時(shí)發(fā)現(xiàn)軟件中存在的漏洞,以便實(shí)現(xiàn)對(duì)軟件漏洞的及時(shí)修復(fù)[1]。測(cè)試用例的數(shù)量隨著軟件規(guī)模的擴(kuò)大不斷增多,增加了軟件可靠性測(cè)試的復(fù)雜程度,因此,需要對(duì)軟件可靠性測(cè)試的需求展開分析,通過約簡(jiǎn)優(yōu)化降低測(cè)試用例的數(shù)量,提高軟件可靠性測(cè)試的精度和效率[2]。

魏偉[3]等人通過二元優(yōu)化覆蓋問題描述軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化問題,將細(xì)胞自動(dòng)機(jī)分類模型引入螢火蟲算法中,利用優(yōu)化后的算法求解優(yōu)化問題,實(shí)現(xiàn)測(cè)試用例的約簡(jiǎn)優(yōu)化。該方法約簡(jiǎn)后的測(cè)試用例數(shù)量多于需求的用例數(shù)量,表明方法的約簡(jiǎn)結(jié)果中存在冗余用例,方法的約簡(jiǎn)效果較差。楊祎巍[4]等人結(jié)合局部搜索策略與遺傳算法建立測(cè)試用例約簡(jiǎn)優(yōu)化模型,采用Memetic算法獲取模型最優(yōu)解,實(shí)現(xiàn)測(cè)試用例的約簡(jiǎn)優(yōu)化。該方法約簡(jiǎn)軟件可靠性測(cè)試用例的運(yùn)行代價(jià)較大,且約簡(jiǎn)后的測(cè)試用例在軟件可靠性測(cè)試過程中出錯(cuò)概率較高,存在丟失率高的問題。

為了解決上述方法中存在的問題,提出基于耦合度量的軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化方法。

2 軟件可靠性測(cè)試用例耦合度量

耦合度量指的是對(duì)軟件可靠性測(cè)試用例之間依賴程度的度量[5],建立耦合度量模型,度量測(cè)試用例之間的依賴程度,具體過程如下:

用七元組表示軟件可靠性測(cè)試用例耦合度量模型:

RTC={Fi,Fr,Itc,Yd,Yr,Vn,Fc}

(1)

式中,Fi代表設(shè)計(jì)軟件可靠性測(cè)試用例的思想;Fc代表用戶描述用例的方式;Fr代表設(shè)計(jì)規(guī)則;Vn代表測(cè)試步驟在軟件可靠性測(cè)試用例中的執(zhí)行方式和順序;Itc代表單元測(cè)試用例在軟件可靠性測(cè)試用例中的數(shù)量;Yr代表執(zhí)行測(cè)試用例的結(jié)果;Yd代表數(shù)據(jù)在測(cè)試用例中的數(shù)量;RTC代表軟件可靠性測(cè)試用例。

測(cè)試用例的權(quán)重直接影響耦合度量結(jié)果,采用人工方式賦予測(cè)試用例權(quán)重時(shí),會(huì)導(dǎo)致度量結(jié)果受主觀因素的影響,度量精度無法得到保證。因此本文通過特征分析法[6-7]計(jì)算測(cè)試過程中軟件可靠性測(cè)試用例的權(quán)重。

用m表示耦合資源在軟件可靠性測(cè)試用例中的數(shù)量,耦合資源表示為I1,I2,…,Im,其權(quán)重表示為W1,W2,…,Wm,存在W1+W2+…+Wm=1。采用特征分析法計(jì)算軟件可靠性測(cè)試用例的具體過程如下:

1)兩兩比較耦合資源,獲得比較結(jié)果vij:

(2)

式中,i≥1,j≤m。根據(jù)上式計(jì)算結(jié)果構(gòu)建比較矩陣V:

(3)

2)用F表示矩陣V對(duì)應(yīng)的最優(yōu)傳遞矩陣,其表達(dá)式如下:

(4)

3)用一致性判斷矩陣R代替矩陣F:

(5)

式中,rij=exp(fij)。

4)針對(duì)測(cè)試用例的權(quán)重,可通過近似解法計(jì)算得到,在上述構(gòu)建的一致性判斷矩陣的基礎(chǔ)上,獲得資源的重要性排序[8-9],即特征向量,分配權(quán)重:

①用Q表示每行元素在矩陣R中的乘積,可通過下式計(jì)算得到:

(6)

③歸一化處理L=(L1,L2,…,Lm)T,獲得W=(W1,W2,…,Wm),即軟件可靠性測(cè)試用例的權(quán)重。

通過下述公式計(jì)算用例在軟件可靠性測(cè)試用例耦合模型中的耦合度TRD:

(7)

式中,T代表用例在模型中的數(shù)量;T′代表某類用例在模型中被復(fù)用的次數(shù)。

針對(duì)軟件可靠性測(cè)試過程中用例被重復(fù)利用的程度采用耦合程度YCRD描述,可通過下式計(jì)算得到:

(8)

式中,Wi代表軟件可靠性測(cè)試用例中復(fù)用資源對(duì)應(yīng)的權(quán)重;TRDi代表某類被復(fù)用的資源在軟件可靠性測(cè)試用例中的復(fù)用程度。

設(shè)RTCARM代表某段測(cè)試時(shí)間內(nèi),某個(gè)用例的多個(gè)耦合程度的平均值,其計(jì)算公式如下:

(9)

式中,Yi代表軟件可靠性測(cè)試用例在測(cè)試時(shí)間內(nèi)被復(fù)用的次數(shù)。

通過上述公式獲得軟件可靠性測(cè)試用例的耦合程度,保留耦合度高的軟件可靠性測(cè)試用例,對(duì)剩余的冗余測(cè)試用例展開約簡(jiǎn)優(yōu)化。

3 軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化

選取K個(gè)評(píng)價(jià)指標(biāo)用于軟件可靠性測(cè)試用例的約簡(jiǎn)優(yōu)化,即在優(yōu)化過程中存在K個(gè)決策目標(biāo)。

首先計(jì)算決策目標(biāo)對(duì)應(yīng)的權(quán)重,根據(jù)計(jì)算結(jié)果對(duì)決策目標(biāo)排序H=(h1,h2,…,hk),決策目標(biāo)可表示為He、Hmax、Hmin,分別表示等值目標(biāo)、最大目標(biāo)和最小目標(biāo),建立的優(yōu)化目標(biāo)函數(shù)如下:

(10)

式中,TR代表冗余測(cè)試用例集;函數(shù)opt的取值情況如下:

1)當(dāng)Hi∈Hmin時(shí),函數(shù)opt表示為hi(tj)≤YVi;

2)當(dāng)Hi∈Hmax時(shí),函數(shù)opt表示為hi(tj)≥YVi;

3)當(dāng)Hi∈He時(shí),函數(shù)opt表示為hi(tj)=YVi。

其中,YVi代表目標(biāo)對(duì)應(yīng)的閾值。

采用分層序列算法在多目標(biāo)優(yōu)化思想的基礎(chǔ)上求解軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化目標(biāo)函數(shù),求解思想為:

1)通過耦合度量將軟件可靠性測(cè)試用例分為兩類,第一類為冗余測(cè)試用例集TR,第二類為耦合測(cè)試用例集TE;

2)通過上述建立的目標(biāo)函數(shù)獲取TE的最優(yōu)解x,設(shè)TRk代表用例在軟件可靠性測(cè)試過程中的需求構(gòu)成集合,為了獲取局部最小化的軟件可靠性測(cè)試用例,可對(duì)TRk展開最小化處理;

3)對(duì)上述過程展開迭代,當(dāng)全部冗余測(cè)試需求集Rk被約簡(jiǎn)優(yōu)化后的用例集覆蓋后停止迭代;

用As表示軟件可靠性測(cè)試過程中全部的用例集,Os表示原始用例集,Oes表示約簡(jiǎn)優(yōu)化的目標(biāo)用例集。

約簡(jiǎn)軟件可靠性測(cè)試用例的具體過程如下:

1)初始化輸入數(shù)據(jù),對(duì)輸入的用例集展開初始化處理:|As|=m、|Os|=n、|Oes|=k。

2)標(biāo)記耦合用例集,標(biāo)記通過耦合度量獲取的耦合用例集合中的冗余用例集。分別用T*和R*表示以上兩個(gè)用例集在軟件可靠性測(cè)試過程中的需求集。

3)采用蟻群優(yōu)化算法[10-11]求解軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化目標(biāo)函數(shù),獲得TRk,具體過程如下:

(11)

②評(píng)價(jià)解,計(jì)算上述螞蟻構(gòu)造解對(duì)應(yīng)的適應(yīng)度函數(shù)值。

(1) 在抗滑樁間距為最佳樁間距時(shí)，樁后土拱與樁側(cè)土拱聯(lián)合并存，聯(lián)合的土拱可分解為兩個(gè)單獨(dú)的土拱[14]。

③非支配排序,針對(duì)迭代過程中螞蟻構(gòu)建的解,通過非支配排序方法[12-13]對(duì)其展開非支配排序,獲得多個(gè)非支配解構(gòu)成的集合,選取適應(yīng)度函數(shù)值最高的解集,作為軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化目標(biāo)函數(shù)的最優(yōu)解集。

④更新解集,比較迭代過程中的最優(yōu)解集與上述生成的最優(yōu)解集,保留更好的解集。

⑤更新信息素?ij[14-15]。為了引導(dǎo)螞蟻在迭代過程中向最好的方向移動(dòng),需要對(duì)信息素?ij展開更新,引入揮發(fā)機(jī)制減少信息素?ij在搜索路徑中的值,并將優(yōu)秀的信息素添加到搜索路徑中。

將迭代過程中獲取的最優(yōu)解集用于信息素?ij的更新,讓最優(yōu)解集中的解在螞蟻搜索路徑中釋放信息素,信息素?ij的更新過程如下:

?ij=?ij(1-σ)+Δ?ij

(12)

式中,σ代表揮發(fā)因子,當(dāng)Δ?ij的值為1時(shí),表明最優(yōu)解中存在邊(i,j),當(dāng)Δ?ij的值為0時(shí),表明最優(yōu)解中不存在邊(i,j)。

4)在上述過程獲取的TRk中通過層次序列化算法[16]獲取局部最小的軟件可靠性測(cè)試用例集。

5)迭代上述步驟,當(dāng)R*=As時(shí),獲得約簡(jiǎn)后的最優(yōu)軟件可靠性測(cè)試用例集。

4 實(shí)驗(yàn)與分析

為了驗(yàn)證基于耦合度量的軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化方法的整體有效性,需要對(duì)其展開測(cè)試。本次測(cè)試所用的用例約簡(jiǎn)平臺(tái)如圖1所示。

圖1 測(cè)試用例約簡(jiǎn)平臺(tái)

針對(duì)圖1所示的平臺(tái),現(xiàn)設(shè)定軟件可靠性測(cè)試過程中需要用例數(shù)量為200個(gè),測(cè)試用例總數(shù)為223個(gè),現(xiàn)采用基于耦合度量的軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法在上述平臺(tái)中展開測(cè)試。

通過SizeCos表示約簡(jiǎn)用例的運(yùn)行代價(jià),其計(jì)算公式如下:

(13)

式中,|V′|代表約簡(jiǎn)后用例在軟件可靠性測(cè)試過程中的運(yùn)行代價(jià);|V|代表原始用例在軟件可靠性測(cè)試過程中的運(yùn)行代價(jià)。

依據(jù)式(13)計(jì)算得到三種方法的軟件可靠性測(cè)試用例約簡(jiǎn)結(jié)果,如圖2所示。

圖2 不同方法的用例約簡(jiǎn)結(jié)果

分析圖2中的數(shù)據(jù)可知,所提方法可有效將軟件可靠性測(cè)試用例的數(shù)量約簡(jiǎn)為測(cè)試需要的用例數(shù)量,而文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的約簡(jiǎn)結(jié)果中存在測(cè)試不需要的用例,即冗余用例,表明以上兩種方法的用例約簡(jiǎn)效果較差。且對(duì)比所提方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的運(yùn)行代價(jià)發(fā)現(xiàn),所提方法的運(yùn)行代價(jià)最小,因?yàn)樵撎岱椒▽?duì)軟件可靠性測(cè)試用例約簡(jiǎn)之前,度量了測(cè)試用例的耦合程度,保留耦合程度較高的用例,對(duì)剩余的用例展開約簡(jiǎn)優(yōu)化,減少了約簡(jiǎn)的用例數(shù)量,降低了運(yùn)行代價(jià)。

進(jìn)一步將丟失率FaultLoss作為評(píng)價(jià)指標(biāo)對(duì)上述方法展開測(cè)試,丟失率越高,表明約簡(jiǎn)后測(cè)試用例對(duì)軟件可靠性測(cè)試的錯(cuò)誤越多,FaultLoss的計(jì)算公式如下:

(14)

式中,|F′|代表用例約簡(jiǎn)優(yōu)化后,錯(cuò)誤測(cè)試軟件可靠性的數(shù)量;|F|代表原始用例測(cè)試軟件可靠性的出錯(cuò)數(shù)量。

所提方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的丟失率測(cè)試統(tǒng)計(jì)結(jié)果,如表1所示。

表1 不同方法的丟失率

由表1中的數(shù)據(jù)可知,在測(cè)試過程中所提方法的丟失率低于其他兩種方法,表明采用所提方法對(duì)軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化后,用例的錯(cuò)誤測(cè)試數(shù)量減少,在軟件可靠性測(cè)試過程中,所提算法表現(xiàn)出良好的用例約簡(jiǎn)能力。

5 結(jié)束語

測(cè)試用例的數(shù)量隨著軟件系統(tǒng)的更新不斷增多,如果不對(duì)其處理,會(huì)增加軟件可靠性測(cè)試的成本,因此在軟件可靠性測(cè)試過程中,需要對(duì)測(cè)試用例展開約簡(jiǎn)優(yōu)化。目前軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化方法存在約簡(jiǎn)效果差、運(yùn)行代價(jià)高和丟失率高的問題,為此提出基于耦合度量的軟件可靠性測(cè)試用例約簡(jiǎn)優(yōu)化方法,該方法通過耦合度量獲取用例中的冗余用例,建立用例約簡(jiǎn)優(yōu)化目標(biāo)函數(shù)對(duì)冗余用例展開約簡(jiǎn),實(shí)驗(yàn)結(jié)果表明,該方法可有效降低用例中存在的冗余用例,且運(yùn)行代價(jià)和丟失率較低,具有良好的應(yīng)用性能。