基于二階Markov模型的改進(jìn)相對(duì)熵測(cè)試充分性準(zhǔn)則

張 凡，李福川，陳麗容，呂中凱

(1.中國(guó)航天科工集團(tuán)第二研究院 七〇六所，北京 100854；2.中國(guó)人民解放軍 93160部隊(duì)，北京 100166)

0 引 言

近年來，國(guó)內(nèi)外軟件測(cè)試充分性技術(shù)的研究方向主要集中在測(cè)試充分性模型，測(cè)試充分性準(zhǔn)則、測(cè)試用例自動(dòng)生成等方面，其中軟件測(cè)試充分性準(zhǔn)則是研究軟件測(cè)試充分性的基礎(chǔ)和前提，因?yàn)檐浖斎肟臻g是無窮性的，測(cè)試空間是有限的，不可能對(duì)軟件進(jìn)行窮舉測(cè)試，只能在滿足一定的充分性準(zhǔn)則的前提下進(jìn)行相對(duì)充分的測(cè)試。Markov過程因其具有對(duì)動(dòng)態(tài)隨機(jī)過程刻畫的先天優(yōu)勢(shì)，被眾多國(guó)內(nèi)外學(xué)者用于描述軟件測(cè)試模型和軟件測(cè)試充分性準(zhǔn)則的研究，并取得了一系列的研究效果[2]，逐漸成為軟件測(cè)試充分性研究方向的重要熱點(diǎn)[1]。

本文首先介紹了Markov鏈模型的定義及其特性，對(duì)現(xiàn)有的基于Markov模型的軟件測(cè)試充分性判定準(zhǔn)則進(jìn)行研究分析，針對(duì)現(xiàn)有方法可能出現(xiàn)的“早熟”問題等缺陷，提出了一種基于二階Markov模型的改進(jìn)相對(duì)熵軟件測(cè)試充分性準(zhǔn)則。通過數(shù)值實(shí)驗(yàn)對(duì)比驗(yàn)證了充分性評(píng)價(jià)指標(biāo)的有效性，實(shí)驗(yàn)結(jié)果表明，該充分性判別準(zhǔn)則能較為準(zhǔn)確地評(píng)估測(cè)試用例集對(duì)單元測(cè)試的測(cè)試充分程度，有效地解決了測(cè)試用例生成過程過早收斂的問題、增強(qiáng)了測(cè)試充分性判定的穩(wěn)定性。

1 Markov鏈模型概述

Markov鏈模型最早是由Andrey. Markov于1906年提出的，它是基于統(tǒng)計(jì)理論且可以描述軟件使用情況的一種統(tǒng)計(jì)模型，Whittaker于1994年將Markov鏈模型用于軟件統(tǒng)計(jì)測(cè)試[3]。由于Markov鏈模型是具有遷移概率屬性的一種有限狀態(tài)機(jī)，軟件在狀態(tài)之間的轉(zhuǎn)換過程中存在著轉(zhuǎn)移概率，該轉(zhuǎn)移概率可以通過相鄰的前序狀態(tài)推算出來，這個(gè)特性稱為“無后效性”。同時(shí)，Markov鏈模型不僅能夠依據(jù)各個(gè)狀態(tài)之間的狀態(tài)轉(zhuǎn)移概率自動(dòng)生成測(cè)試用例，而且可以通過充分性測(cè)試對(duì)軟件的測(cè)試充分程度進(jìn)行評(píng)估[4]。

Markov鏈模型是表示軟件從起始運(yùn)行到結(jié)束運(yùn)行狀態(tài)的隨機(jī)過程，它可以用帶狀態(tài)轉(zhuǎn)移概率的遷移圖或者隨機(jī)遷移矩陣來描述軟件的使用[5]。一階Markov鏈模型可以用一個(gè)四元組Markov來進(jìn)行形式化表述[6]

Markov=〈S,T,E,σ〉

(1)

式中的符號(hào)和解釋見表1。

表1 一階Markov鏈模型的四元組表示

任一Markov鏈模型的狀態(tài)集合S可表示為：S={S1,S2,…,SN}。 令S1為軟件的初始狀態(tài)，SN為軟件的結(jié)束狀態(tài)，且S1∈S，SN∈S， 狀態(tài)Si轉(zhuǎn)移到狀態(tài)Sj(1≤i≤N, 1≤j≤N) 的邊激勵(lì)信息可以表示為eij，一步轉(zhuǎn)移概率σ(i,j) 可以表示為pij。設(shè)隨機(jī)過程為 {X(t),t∈T}， 其中時(shí)間序列T={t1,t2,…,tN}， 且t1

P{X(tN)=SN|X(tN-1)=SN-1,…,X(t1)=S1}=P{X(tN)=SN|X(tN-1)=SN-1}

(2)

無后效性在Markov過程中的定義可理解為時(shí)刻tN的狀態(tài)只與前一個(gè)時(shí)刻tN-1有關(guān)，而與過去時(shí)刻t1,…,tN-2都沒有關(guān)系，且條件概率P{X(k)=Sj|X(l)=Si}=pij定義為Markov過程中從狀態(tài)Si到狀態(tài)Sj的轉(zhuǎn)移概率分布。設(shè)P表示轉(zhuǎn)移概率pij所組成的一階轉(zhuǎn)移概率矩陣，對(duì)于N個(gè)狀態(tài)，一階轉(zhuǎn)移概率矩陣P為N*N的矩陣，其數(shù)學(xué)定義表示如下

(3)

對(duì)于齊次Markov鏈，稱式(4)定義的條件概率

Pij(m,m+n)=P{X(m+n)=Sj|X(m)=Si}

(4)

為Markov鏈模型在時(shí)刻m到時(shí)刻m+n從狀態(tài)Si到狀態(tài)Sj的n步轉(zhuǎn)移概率，記為P(n)。當(dāng)n=1時(shí)即為Markov鏈的一步轉(zhuǎn)移概率。Kolmogorov在前人的基礎(chǔ)上研究了離散參數(shù)Markov鏈的轉(zhuǎn)移規(guī)律[7]。設(shè)pij(k)表示狀態(tài)Si經(jīng)k步轉(zhuǎn)移到狀態(tài)Sj的概率，則有

(5)

稱為Chapman-Kolmogorov方程(簡(jiǎn)稱C-K方程)，它是齊次Markov鏈模型中計(jì)算n步轉(zhuǎn)移概率的重要依據(jù)[8]。

2 基于Markov模型的測(cè)試充分性準(zhǔn)則

基于軟件的Markov鏈模型，在測(cè)試執(zhí)行過程中可以通過人工或者自動(dòng)生成無限數(shù)量的測(cè)試用例，所以理論上軟件測(cè)試過程可以不受限制地進(jìn)行。但由于人力和物力等開銷的限制，所以有必要在適當(dāng)?shù)臅r(shí)間點(diǎn)停止執(zhí)行測(cè)試過程，這就是測(cè)試充分性判別準(zhǔn)則所需考慮的內(nèi)容[9]。同時(shí)，基于Markov模型的測(cè)試充分性準(zhǔn)則適用于黑盒測(cè)試，更注重評(píng)估需求實(shí)現(xiàn)的充分程度，因此，當(dāng)代碼不可見時(shí)，便可選擇基于Markov模型的測(cè)試充分性準(zhǔn)則來對(duì)系統(tǒng)的測(cè)試充分程度進(jìn)行評(píng)估。

在Markov使用模型中，測(cè)試的充分性是通過比較測(cè)試過程中使用鏈和測(cè)試鏈的差異程度來衡量的[10]。Markov初始使用模型被稱為使用鏈，而測(cè)試鏈?zhǔn)峭ㄟ^執(zhí)行測(cè)試過程從使用鏈中產(chǎn)生的。測(cè)試之初首先用一個(gè)初值為0的計(jì)數(shù)器來替換使用鏈中各遷移邊所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移概率。依次執(zhí)行所有的測(cè)試用例，每當(dāng)一個(gè)測(cè)試用例覆蓋了其中的某條遷移邊時(shí)，對(duì)應(yīng)于該遷移邊的計(jì)數(shù)器就遞增1，并根據(jù)每條邊相應(yīng)的計(jì)數(shù)器的值所占比例計(jì)算出該邊的相對(duì)轉(zhuǎn)移概率，從而形成一個(gè)測(cè)試鏈。如果測(cè)試空間和預(yù)期使用空間的差異度滿足規(guī)定的閾值，那么通過測(cè)試空間得出的測(cè)試充分性就能代表在實(shí)際應(yīng)用過程中的測(cè)試充分性，即認(rèn)為軟件測(cè)試已充分執(zhí)行了[11]。

目前現(xiàn)有的基于Markov鏈模型的軟件測(cè)試充分性準(zhǔn)則，主要依據(jù)計(jì)算歐氏距離(Euclidean distance[12])和Kullback判別式(Kullback discriminant[13])對(duì)測(cè)試鏈和使用鏈的吻合情況進(jìn)行定量分析。

2.1 歐氏距離

歐氏距離是一種常見的距離度量方法，常用于對(duì)有向圖或圖像之間的差異程度進(jìn)行度量。其表達(dá)式如下

(6)

Markov使用模型可以看作是一個(gè)包含狀態(tài)轉(zhuǎn)移概率的遷移邊組成的有向圖，因此對(duì)測(cè)試鏈和使用鏈吻合性的度量，可以轉(zhuǎn)化為對(duì)兩個(gè)有向圖中轉(zhuǎn)移概率之間的差異程度的度量，進(jìn)而根據(jù)差異的大小來衡量測(cè)試的充分性。因此可以用歐氏距離來衡量?jī)烧咧g的差異，其計(jì)算方法表述如下

(7)

式中：ui,j表示使用鏈中狀態(tài)Si到狀態(tài)Sj的轉(zhuǎn)移概率，ti,j表示測(cè)試鏈中狀態(tài)Si到狀態(tài)Sj的轉(zhuǎn)移概率。歐氏距離不是一種精確可靠的判別方法[14]。例如，考慮如圖1所示的使用鏈。

圖1 Markov模型使用鏈

現(xiàn)假設(shè)兩個(gè)不同的測(cè)試鏈A、B有很大的差異，是由兩組獨(dú)立的測(cè)試實(shí)驗(yàn)產(chǎn)生的。在測(cè)試鏈A中，狀態(tài)Start的兩條遷移邊的轉(zhuǎn)移概率與使用鏈中的對(duì)應(yīng)邊的轉(zhuǎn)移概率相同，而圖1云結(jié)構(gòu)中包含使用鏈大量其它狀態(tài)和遷移邊的轉(zhuǎn)移概率與測(cè)試鏈A中的相應(yīng)狀態(tài)存在較大差異。

在圖2所示的測(cè)試鏈B中，情況則恰恰相反。狀態(tài)Start的兩條遷移邊的轉(zhuǎn)移概率與使用鏈中的對(duì)應(yīng)邊的轉(zhuǎn)移概率差異較大，而測(cè)試鏈B云結(jié)構(gòu)中包含測(cè)試鏈A的大量其它狀態(tài)和遷移邊的轉(zhuǎn)移概率與使用鏈中的相應(yīng)狀態(tài)大致相同。

圖2 Markov模型測(cè)試鏈B

當(dāng)通過上述情況計(jì)算歐氏距離時(shí)，由于測(cè)試鏈B與測(cè)試鏈A相比較有更多的邊轉(zhuǎn)移概率和使用鏈相近，因此歐氏距離將表明創(chuàng)建測(cè)試鏈B的測(cè)試將被解釋為比測(cè)試鏈A所代表的測(cè)試經(jīng)驗(yàn)更能代表軟件的預(yù)期使用，而實(shí)際上測(cè)試鏈A更接近于使用鏈。如果以這種方式解釋歐氏距離，那么在軟件測(cè)試過程中就有可能浪費(fèi)時(shí)間來修復(fù)云結(jié)構(gòu)中發(fā)現(xiàn)的相對(duì)不重要的故障，而且有可能錯(cuò)過通過測(cè)試從Start到狀態(tài)A的過渡而暴露出的重要故障。因此，歐氏距離可能產(chǎn)生誤導(dǎo)性解釋，導(dǎo)致軟件測(cè)試充分性的誤判。

綜上，歐氏距離在度量使用鏈和測(cè)試鏈的吻合性上存在較大偏差，且存在欠充分誤判為已充分的風(fēng)險(xiǎn)。

2.2 Kullback判別式

Kullback判別式表示兩個(gè)隨機(jī)過程的對(duì)數(shù)似然率的期望值[15]，它可以對(duì)使用鏈和測(cè)試鏈之間的相似性進(jìn)行度量，該判別式的值則稱為Discriminant值。其數(shù)學(xué)表達(dá)式如下

(8)

其中，在比較使用鏈和測(cè)試鏈的具體情況下，n表示測(cè)試用例的個(gè)數(shù)，X0,X1,…,Xn是使用鏈生成的長(zhǎng)度為n的輸入序列。由Markov鏈模型遷移邊所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移概率可知，上述公式等價(jià)于

(9)

從上式不難看出使用鏈和測(cè)試鏈的差異程度越小，K(U,T) 越趨近于0，測(cè)試也就越充分。當(dāng)它小于某個(gè)特定的閾值時(shí)，即判定測(cè)試已經(jīng)足夠充分，便可停止測(cè)試。Discriminant值所提供的判定結(jié)果較為準(zhǔn)確，但其結(jié)果并不總是可以被計(jì)算出來的[16]。當(dāng)測(cè)試鏈中的所有狀態(tài)和轉(zhuǎn)移邊仍未被未完全覆蓋時(shí)，測(cè)試鏈產(chǎn)生的序列的概率接近于零，這就導(dǎo)致了判別式計(jì)算中的除數(shù)為零，即存在i,j， 使得ti,j為0時(shí)，Discriminant值便不可計(jì)算。因此可以用一種變體計(jì)算方法來避免上述情況，使其在任何情況下K(U,T) 都可以被定義[17]

(10)

2.3 測(cè)試充分性判別方法的缺陷

雖然基于Kullback判別式的測(cè)試充分性準(zhǔn)則比基于歐氏距離的測(cè)試充分性準(zhǔn)則有更高的準(zhǔn)確度，但在一定程度上也存在測(cè)試充分性判定“早熟”的問題?？紤]圖3所示的Markov模型片段。

圖3 Markov模型片段

通過上述分析可得，基于歐氏距離和Kullback判別式的軟件測(cè)試充分性準(zhǔn)則并未滿足遷移對(duì)覆蓋準(zhǔn)則，而僅僅滿足了測(cè)試充分性判別準(zhǔn)則中的狀態(tài)和遷移覆蓋準(zhǔn)則，這就意味著會(huì)出現(xiàn)“早熟”現(xiàn)象。因此，有必要對(duì)上述兩種測(cè)試充分性判別準(zhǔn)則進(jìn)行改進(jìn)，使其滿足遷移對(duì)覆蓋準(zhǔn)則，來解決歐氏距離和Kullback判別式進(jìn)行充分性判定過程中出現(xiàn)的“早熟”現(xiàn)象，同時(shí)在確保效率的前提下提高軟件測(cè)試的充分性。

3 基于二階Markov模型的改進(jìn)相對(duì)熵測(cè)試充分性準(zhǔn)則

3.1 二階Markov模型引入

由于在一階Markov鏈模型中的“無后效性”，使得任一狀態(tài)只能被前一狀態(tài)所影響，而間隔狀態(tài)之間的相互影響則無法被涉及到。因此將單純Markov鏈模型擴(kuò)展為二階，使得改進(jìn)后的測(cè)試充分性準(zhǔn)則盡可能地覆蓋多個(gè)狀態(tài)的所有可能組合。

由式(4)可得，狀態(tài)Si經(jīng)2步轉(zhuǎn)移到狀態(tài)Sj的狀態(tài)轉(zhuǎn)移概率即為P{X(n)=Sj|X(m)=Si}=pij(2)， 稱P(2)為Markov鏈模型的二階轉(zhuǎn)移概率矩陣，其矩陣表示如下

(11)

3.2 改進(jìn)相對(duì)熵的定義

相對(duì)熵的概念來自于信息論和概率論，是由統(tǒng)計(jì)學(xué)家Kullback和Leibler提出的[18]，因此又稱為KL散度(Kullback-Leibler divergence)。其描述了兩個(gè)不同概率分布間差異的非對(duì)稱性度量。設(shè)狀態(tài)空間為x∈X，p(x) 是Markov使用鏈的狀態(tài)轉(zhuǎn)移概率，q(x) 是測(cè)試鏈的狀態(tài)轉(zhuǎn)移概率，則最優(yōu)編碼平均長(zhǎng)度的字符集的熵為

(12)

且擬合Markov測(cè)試鏈的平均編碼長(zhǎng)度為

(13)

由于Markov測(cè)試鏈和使用鏈存在一定的偏差，因此可以用相對(duì)熵來衡量使用鏈和測(cè)試鏈的相似程度，則其原始的相對(duì)熵的計(jì)算公式為

(14)

考慮Markov鏈中狀態(tài)的平穩(wěn)分布率πi，且Markov使用鏈的狀態(tài)轉(zhuǎn)移概率為uij,測(cè)試鏈的狀態(tài)轉(zhuǎn)移概率為tij，所以Markov鏈偏差計(jì)算公式為

(15)

其中，從Markov使用模型的任意狀態(tài)Sk到狀態(tài)Si的轉(zhuǎn)移概率近似等于狀態(tài)Si長(zhǎng)期運(yùn)行的發(fā)生概率，即狀態(tài)Si的平穩(wěn)分布率πi。

相對(duì)熵有如下兩個(gè)主要的性質(zhì)[19]：

(1)不對(duì)稱性：雖然KL散度從直觀的角度來說滿足距離度量函數(shù)的特性，但由于它不滿足對(duì)稱性，即KL(p‖q)≠KL(q‖p)， 因此它并不能被稱為真正的度量或者距離；

(2)非負(fù)性：KL(p‖q)≥0， 當(dāng)且僅當(dāng)p(x)=q(x) 時(shí)等號(hào)成立，兩個(gè)分布相差越大，相對(duì)熵越大。

由于KL(p‖q) 不滿足對(duì)稱性，即使用鏈和測(cè)試鏈的差異程度不能完全代表測(cè)試鏈和使用鏈之間的差異程度，因此KL(p‖q) 不適合作為測(cè)度，故對(duì)KL(p‖q) 進(jìn)行對(duì)稱性設(shè)計(jì)，使其變?yōu)橐粋€(gè)完全的差異度量函數(shù)，其對(duì)稱形式的相對(duì)熵公式如下

KLD(p‖q)=KL(p‖q)+KL(q‖p)

(16)

當(dāng)且僅當(dāng)p(x)=q(x) 時(shí)，KLD(p‖q)=0，KLD指標(biāo)具有無界性，可解釋性不強(qiáng)[20]，不適用于測(cè)試充分性評(píng)價(jià)測(cè)度。故提出一種基于對(duì)稱形式的改進(jìn)相對(duì)熵的測(cè)試充分性評(píng)價(jià)指標(biāo)IKLD，其計(jì)算公式如下

(17)

基于改進(jìn)后的相對(duì)熵具有如下性質(zhì)：

(1)對(duì)稱性：IKLD(p‖q)=IKLD(q‖p)；

(2)有界性： 0≤IKLD(p‖q)≤1， 當(dāng)且僅當(dāng)p(x)=q(x) 時(shí)，IKLD(p‖q)=1。 并且IKLD(p‖q) 值是不增的，保證了測(cè)試充分性判別過程的收斂。因此當(dāng)兩個(gè)分布越接近時(shí)，測(cè)試充分性評(píng)價(jià)指標(biāo)越接近1。反之，兩個(gè)分布相差越大，指標(biāo)越接近0。

因此最終的基于二階Markov模型的改進(jìn)相對(duì)熵測(cè)試充分性準(zhǔn)則的公式如下

(18)

3.3 基于二階Markov模型的改進(jìn)相對(duì)熵充分性判別流程

將基于二階Markov模型的改進(jìn)相對(duì)熵測(cè)試充分性評(píng)價(jià)指標(biāo)IKLD′應(yīng)用到實(shí)際軟件測(cè)試中時(shí)，其軟件測(cè)試充分性判別過程如圖4所示。首先設(shè)定一個(gè)用于指示測(cè)試在何時(shí)停止的無限接近于1的閾值α，根據(jù)軟件在真實(shí)場(chǎng)景中的使用方式，構(gòu)建Markov使用模型并確定模型中各條遷移邊上的狀態(tài)轉(zhuǎn)移概率。根據(jù)相應(yīng)的測(cè)試指標(biāo)來生成測(cè)試用例，最終形成一條完整的測(cè)試鏈并執(zhí)行測(cè)試[21]。最后依據(jù)測(cè)試充分性準(zhǔn)則所得出的結(jié)果來對(duì)測(cè)試執(zhí)行過程的充分性進(jìn)行評(píng)估：

圖4 軟件測(cè)試充分性判別流程

(1)當(dāng)根據(jù)式(18)計(jì)算出來的IKLD′(p‖q) 值小于或等于α?xí)r，表明測(cè)試鏈和使用鏈相差較大，測(cè)試不充分，此時(shí)應(yīng)繼續(xù)生成測(cè)試用例并執(zhí)行測(cè)試；

(2)當(dāng)IKLD′(p‖q) 值大于α?xí)r，表明測(cè)試鏈和使用鏈之間的差異性較小，測(cè)試已經(jīng)足夠充分，此時(shí)便可停止測(cè)試。

4 數(shù)值實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證基于二階Markov模型的改進(jìn)相對(duì)熵測(cè)試充分性準(zhǔn)則的有效性，并且能夠在一定程度上解決測(cè)試過程中出現(xiàn)的“早熟”現(xiàn)象等問題，本節(jié)通過數(shù)值模擬的方法進(jìn)行對(duì)比實(shí)驗(yàn)來舉例說明。

4.1 實(shí)驗(yàn)過程

考慮圖3的Markov模型片段作為該數(shù)值實(shí)驗(yàn)?zāi)Ｐ?，在測(cè)試執(zhí)行過程中分別通過歐氏距離、Kullback判別式和基于二階Markov模型的改進(jìn)相對(duì)熵3種判別方法進(jìn)行測(cè)試充分性判定。其中，在計(jì)算Kullback判別式中的Discriminant值時(shí)，需設(shè)定一個(gè)趨近于0的正數(shù)作為式(10)中ε的取值，且ε越小，判別式的計(jì)算結(jié)果越精確?？紤]到實(shí)際情況，當(dāng)ε?min(tij) 時(shí)，可以將ε對(duì)計(jì)算結(jié)果精度的影響忽略，因此令ε=0.000001(ε?0.25)。 同時(shí)為了便于說明測(cè)試過程，將模型中遷移邊a和b的狀態(tài)轉(zhuǎn)移概率分別設(shè)為1/2，其它遷移邊均保持不變。其數(shù)值實(shí)驗(yàn)結(jié)果見表2。

表2 基于Markov模型的測(cè)試充分性判定

由于基于二階Markov模型的改進(jìn)相對(duì)熵判別方法的計(jì)算結(jié)果的有界性，為了使得上述實(shí)驗(yàn)數(shù)據(jù)具有一定的可比較性，故將IKLD(p‖q) 值改寫為IKLD′(p‖q)=1-IKLD(p‖q)， 并且對(duì)3種判別方法的計(jì)算結(jié)果進(jìn)行歸一化處理，處理后的數(shù)據(jù)映射在0～1范圍之內(nèi)，以消除不同評(píng)價(jià)指標(biāo)之間的相互影響，從而便于對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行綜合對(duì)比評(píng)價(jià)。處理后的數(shù)據(jù)見表3。

表3 基于Markov模型的測(cè)試充分性判定(歸一化處理)

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

測(cè)試在初始狀態(tài)時(shí)，測(cè)試鏈為空，歐氏距離的計(jì)算結(jié)果達(dá)到最大值。而對(duì)于所有狀態(tài)，其平穩(wěn)分布率πi都為0，此時(shí)經(jīng)處理后的Kullback判別式和基于二階Markov模型的改進(jìn)相對(duì)熵的值均為0。當(dāng)生成測(cè)試用例ACDFG、ABDEG后，即此時(shí)的測(cè)試鏈為(ACDFG、ABDEG)，歐氏距離和Kullback判別式的計(jì)算結(jié)果為0，表示測(cè)試執(zhí)行過程已充分，而相同條件下基于二階Markov模型的改進(jìn)相對(duì)熵的值表明測(cè)試仍未充分執(zhí)行，應(yīng)繼續(xù)生成測(cè)試用例并執(zhí)行測(cè)試，因此基于歐氏距離和Kullback判別式的充分性準(zhǔn)則在此時(shí)出現(xiàn)了“早熟”現(xiàn)象。而當(dāng)測(cè)試鏈為(ACDFG、ABDEG、ACDEG、ABDFG)時(shí)，3種充分性判別準(zhǔn)則的計(jì)算結(jié)果都為0，此時(shí)則說明使用鏈和測(cè)試鏈已經(jīng)完全重合，測(cè)試過程充分執(zhí)行，即可停止生成測(cè)試用例。

從上表可以看出，歐氏距離和Kullback判別式在測(cè)試執(zhí)行未充分時(shí)就顯示計(jì)算結(jié)果為0，即在測(cè)試過程中出現(xiàn)了“早熟”問題，而基于二階Markov模型的改進(jìn)相對(duì)熵能夠很好地度量使用鏈和測(cè)試鏈之間的差異程度，大大降低了出現(xiàn)“早熟”現(xiàn)象的概率。因此，基于二階Markov模型的改進(jìn)相對(duì)熵的測(cè)試充分性準(zhǔn)則相較于傳統(tǒng)的測(cè)試充分性準(zhǔn)則有更好的有效性和穩(wěn)定性。

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

本文對(duì)Markov鏈模型的基本概念和性質(zhì)進(jìn)行了介紹，并對(duì)現(xiàn)存的基于Markov模型的軟件測(cè)試充分性判別準(zhǔn)則作了系統(tǒng)性的分析，針對(duì)現(xiàn)有測(cè)試充分性判別準(zhǔn)則存在的缺陷，給出了一種基于二階Markov模型的改進(jìn)相對(duì)熵測(cè)試充分性準(zhǔn)則作為對(duì)測(cè)試終止的判斷依據(jù)。該方法通過分析軟件單元的狀態(tài)遷移關(guān)系，進(jìn)而確定軟件單元測(cè)試的測(cè)試覆蓋因素，使得單元測(cè)試過程得以模型化描述，其單元測(cè)試的充分程度能夠得到定量的計(jì)算，對(duì)單元測(cè)試的測(cè)試用例生成策略的優(yōu)化設(shè)計(jì)存在一定的指導(dǎo)意義。同時(shí)，該方法由于對(duì)測(cè)試充分性準(zhǔn)則進(jìn)行了邊界化處理和對(duì)稱性設(shè)計(jì)，并且消除了Markov模型的“一階無后效性”的影響，因此有效解決了測(cè)試用例生成過程過早收斂即“早熟”問題，避免了測(cè)試充分性的誤判。

但是基于模型的軟件測(cè)試充分性準(zhǔn)則只能用于評(píng)估當(dāng)前測(cè)試經(jīng)歷匹配軟件預(yù)期使用的程度，而近似相等概率則可以提供關(guān)于測(cè)試鏈未來行為的量化信息，因此基于模型的軟件測(cè)試充分性準(zhǔn)則和近似相等概率可以結(jié)合使用，一旦測(cè)試收斂，測(cè)試人員便可得到關(guān)于當(dāng)前測(cè)試經(jīng)驗(yàn)和軟件預(yù)期使用的相似性的指示。后續(xù)工作中，將繼續(xù)對(duì)以上問題開展深入研究。