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

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

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

0 引 言

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

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

1 Markov鏈模型概述

Markov鏈模型最早是由Andrey. Markov于1906年提出的，它是基于統計理論且可以描述軟件使用情況的一種統計模型，Whittaker于1994年將Markov鏈模型用于軟件統計測試[3]。……