基于二階Markov模型的改進相對熵測試充分性準則

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

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

0 引 言

近年來，國內外軟件測試充分性技術的研究方向主要集中在測試充分性模型，測試充分性準則、測試用例自動生成等方面，其中軟件測試充分性準則是研究軟件測試充分性的基礎和前提，因為軟件輸入空間是無窮性的，測試空間是有限的，不可能對軟件進行窮舉測試，只能在滿足一定的充分性準則的前提下進行相對充分的測試。Markov過程因其具有對動態隨機過程刻畫的先天優勢，被眾多國內外學者用于描述軟件測試模型和軟件測試充分性準則的研究，并取得了一系列的研究效果[2]，逐漸成為軟件測試充分性研究方向的重要熱點[1]。

本文首先介紹了Markov鏈模型的定義及其特性，對現有的基于Markov模型的軟件測試充分性判定準則進行研究分析，針對現有方法可能出現的“早熟”問題等缺陷，提出了一種基于二階Markov模型的改進相對熵軟件測試充分性準則。通過數值實驗對比驗證了充分性評價指標的有效性，實驗結果表明，該充分性判別準則能較為準確地評估測試用例集對單元測試的測試充分程度，有效地解決了測試用例生成過程過早收斂的問題、增強了測試充分性判定的穩定性。

1 Markov鏈模型概述

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

Markov鏈模型是表示軟件從起始運行到結束運行狀態的隨機過程，它可以用帶狀態轉移概率的遷移圖或者隨機遷移矩陣來描述軟件的使用[5]。一階Markov鏈模型可以用一個四元組Markov來進行形式化表述[6]

Markov=〈S,T,E,σ〉

(1)

式中的符號和解釋見表1。

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

任一Markov鏈模型的狀態集合S可表示為：S={S1,S2,…,SN}。 令S1為軟件的初始狀態，SN為軟件的結束狀態，且S1∈S，SN∈S， 狀態Si轉移到狀態Sj(1≤i≤N, 1≤j≤N) 的邊激勵信息可以表示為eij，一步轉移概率σ(i,j) 可以表示為pij。設隨機過程為 {X(t),t∈T}， 其中時間序列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過程中的定義可理解為時刻tN的狀態只與前一個時刻tN-1有關，而與過去時刻t1,…,tN-2都沒有關系，且條件概率P{X(k)=Sj|X(l)=Si}=pij定義為Markov過程中從狀態Si到狀態Sj的轉移概率分布。設P表示轉移概率pij所組成的一階轉移概率矩陣，對于N個狀態，一階轉移概率矩陣P為N*N的矩陣，其數學定義表示如下

(3)

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

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

(4)

為Markov鏈模型在時刻m到時刻m+n從狀態Si到狀態Sj的n步轉移概率，記為P(n)。當n=1時即為Markov鏈的一步轉移概率。Kolmogorov在前人的基礎上研究了離散參數Markov鏈的轉移規律[7]。設pij(k)表示狀態Si經k步轉移到狀態Sj的概率，則有

(5)

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

2 基于Markov模型的測試充分性準則

基于軟件的Markov鏈模型，在測試執行過程中可以通過人工或者自動生成無限數量的測試用例，所以理論上軟件測試過程可以不受限制地進行。但由于人力和物力等開銷的限制，所以有必要在適當的時間點停止執行測試過程，這就是測試充分性判別準則所需考慮的內容[9]。同時，基于Markov模型的測試充分性準則適用于黑盒測試，更注重評估需求實現的充分程度，因此，當代碼不可見時，便可選擇基于Markov模型的測試充分性準則來對系統的測試充分程度進行評估。

在Markov使用模型中，測試的充分性是通過比較測試過程中使用鏈和測試鏈的差異程度來衡量的[10]。Markov初始使用模型被稱為使用鏈，而測試鏈是通過執行測試過程從使用鏈中產生的。測試之初首先用一個初值為0的計數器來替換使用鏈中各遷移邊所對應的狀態轉移概率。依次執行所有的測試用例，每當一個測試用例覆蓋了其中的某條遷移邊時，對應于該遷移邊的計數器就遞增1，并根據每條邊相應的計數器的值所占比例計算出該邊的相對轉移概率，從而形成一個測試鏈。如果測試空間和預期使用空間的差異度滿足規定的閾值，那么通過測試空間得出的測試充分性就能代表在實際應用過程中的測試充分性，即認為軟件測試已充分執行了[11]。

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

2.1 歐氏距離

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

(6)

Markov使用模型可以看作是一個包含狀態轉移概率的遷移邊組成的有向圖，因此對測試鏈和使用鏈吻合性的度量，可以轉化為對兩個有向圖中轉移概率之間的差異程度的度量，進而根據差異的大小來衡量測試的充分性。因此可以用歐氏距離來衡量兩者之間的差異，其計算方法表述如下

(7)

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

圖1 Markov模型使用鏈

現假設兩個不同的測試鏈A、B有很大的差異，是由兩組獨立的測試實驗產生的。在測試鏈A中，狀態Start的兩條遷移邊的轉移概率與使用鏈中的對應邊的轉移概率相同，而圖1云結構中包含使用鏈大量其它狀態和遷移邊的轉移概率與測試鏈A中的相應狀態存在較大差異。

在圖2所示的測試鏈B中，情況則恰恰相反。狀態Start的兩條遷移邊的轉移概率與使用鏈中的對應邊的轉移概率差異較大，而測試鏈B云結構中包含測試鏈A的大量其它狀態和遷移邊的轉移概率與使用鏈中的相應狀態大致相同。

圖2 Markov模型測試鏈B

當通過上述情況計算歐氏距離時，由于測試鏈B與測試鏈A相比較有更多的邊轉移概率和使用鏈相近，因此歐氏距離將表明創建測試鏈B的測試將被解釋為比測試鏈A所代表的測試經驗更能代表軟件的預期使用，而實際上測試鏈A更接近于使用鏈。如果以這種方式解釋歐氏距離，那么在軟件測試過程中就有可能浪費時間來修復云結構中發現的相對不重要的故障，而且有可能錯過通過測試從Start到狀態A的過渡而暴露出的重要故障。因此，歐氏距離可能產生誤導性解釋，導致軟件測試充分性的誤判。

綜上，歐氏距離在度量使用鏈和測試鏈的吻合性上存在較大偏差，且存在欠充分誤判為已充分的風險。

2.2 Kullback判別式

Kullback判別式表示兩個隨機過程的對數似然率的期望值[15]，它可以對使用鏈和測試鏈之間的相似性進行度量，該判別式的值則稱為Discriminant值。其數學表達式如下

(8)

其中，在比較使用鏈和測試鏈的具體情況下，n表示測試用例的個數，X0,X1,…,Xn是使用鏈生成的長度為n的輸入序列。由Markov鏈模型遷移邊所對應的狀態轉移概率可知，上述公式等價于

(9)

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

(10)

2.3 測試充分性判別方法的缺陷

雖然基于Kullback判別式的測試充分性準則比基于歐氏距離的測試充分性準則有更高的準確度，但在一定程度上也存在測試充分性判定“早熟”的問題。考慮圖3所示的Markov模型片段。

圖3 Markov模型片段

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

3 基于二階Markov模型的改進相對熵測試充分性準則

3.1 二階Markov模型引入

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

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

(11)

3.2 改進相對熵的定義

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

(12)

且擬合Markov測試鏈的平均編碼長度為

(13)

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

(14)

考慮Markov鏈中狀態的平穩分布率πi，且Markov使用鏈的狀態轉移概率為uij,測試鏈的狀態轉移概率為tij，所以Markov鏈偏差計算公式為

(15)

其中，從Markov使用模型的任意狀態Sk到狀態Si的轉移概率近似等于狀態Si長期運行的發生概率，即狀態Si的平穩分布率πi。

相對熵有如下兩個主要的性質[19]：

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

(2)非負性：KL(p‖q)≥0， 當且僅當p(x)=q(x) 時等號成立，兩個分布相差越大，相對熵越大。

由于KL(p‖q) 不滿足對稱性，即使用鏈和測試鏈的差異程度不能完全代表測試鏈和使用鏈之間的差異程度，因此KL(p‖q) 不適合作為測度，故對KL(p‖q) 進行對稱性設計，使其變為一個完全的差異度量函數，其對稱形式的相對熵公式如下

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

(16)

當且僅當p(x)=q(x) 時，KLD(p‖q)=0，KLD指標具有無界性，可解釋性不強[20]，不適用于測試充分性評價測度。故提出一種基于對稱形式的改進相對熵的測試充分性評價指標IKLD，其計算公式如下

(17)

基于改進后的相對熵具有如下性質：

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

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

因此最終的基于二階Markov模型的改進相對熵測試充分性準則的公式如下

(18)

3.3 基于二階Markov模型的改進相對熵充分性判別流程

將基于二階Markov模型的改進相對熵測試充分性評價指標IKLD′應用到實際軟件測試中時，其軟件測試充分性判別過程如圖4所示。首先設定一個用于指示測試在何時停止的無限接近于1的閾值α，根據軟件在真實場景中的使用方式，構建Markov使用模型并確定模型中各條遷移邊上的狀態轉移概率。根據相應的測試指標來生成測試用例，最終形成一條完整的測試鏈并執行測試[21]。最后依據測試充分性準則所得出的結果來對測試執行過程的充分性進行評估：

圖4 軟件測試充分性判別流程

(1)當根據式(18)計算出來的IKLD′(p‖q) 值小于或等于α時，表明測試鏈和使用鏈相差較大，測試不充分，此時應繼續生成測試用例并執行測試；

(2)當IKLD′(p‖q) 值大于α時，表明測試鏈和使用鏈之間的差異性較小，測試已經足夠充分，此時便可停止測試。

4 數值實驗

為了進一步驗證基于二階Markov模型的改進相對熵測試充分性準則的有效性，并且能夠在一定程度上解決測試過程中出現的“早熟”現象等問題，本節通過數值模擬的方法進行對比實驗來舉例說明。

4.1 實驗過程

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

表2 基于Markov模型的測試充分性判定

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

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

4.2 實驗結果分析

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

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

5 結束語

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

但是基于模型的軟件測試充分性準則只能用于評估當前測試經歷匹配軟件預期使用的程度，而近似相等概率則可以提供關于測試鏈未來行為的量化信息，因此基于模型的軟件測試充分性準則和近似相等概率可以結合使用，一旦測試收斂，測試人員便可得到關于當前測試經驗和軟件預期使用的相似性的指示。后續工作中，將繼續對以上問題開展深入研究。