趙衛(wèi)東 李有俊 張麗

關(guān)鍵詞： 高階馬爾可夫使用模型; 快速輪盤賭; 二分查找; 相對(duì)熵; 軟件測(cè)試; 測(cè)試用例自動(dòng)生成

中圖分類號(hào)： TN911.23?34 ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2019）06?0026?04

Abstract： In order to solve the problem that the test case generation based on the pure Markov usage model is unstable and the test adequacy judgment is inaccurate， an improved high?order Markov test model is proposed on the basis of analyzing the existing test case automatic generation methods. According to this model， an improved test case generation method based on the binary search of the fast roulette， and a test adequacy judgment method based on the relative entropy are put forward. The practical results show that in comparison with the original methods， the improved method can effectively improve the generation stability of test cases and the judgment accuracy of test adequacy， which is suitable for large?scale software testing， and improves the efficiency of large?scale software automatic testing.

Keywords： high?order Markov usage model; fast roulette; binary search; relative entropy; software testing; test case automatic generation

0 ?引 ?言

馬爾可夫（Markov）鏈?zhǔn)歉鶕?jù)馬爾可夫性得到的一種隨機(jī)過程模型。馬爾可夫性主要體現(xiàn)在其無(wú)后效性，即后發(fā)生的狀態(tài)只跟當(dāng)前狀態(tài)有關(guān)，與過去狀態(tài)的發(fā)生無(wú)關(guān)。用MarKov鏈描述軟件的真實(shí)運(yùn)行過程即為Markov使用模型。由于Markov使用模型能夠有效地描述軟件的真實(shí)運(yùn)行過程，近年來(lái)，基于Markov使用模型的軟件測(cè)試技術(shù)是軟件測(cè)試領(lǐng)域研究的熱點(diǎn)之一。

Tetsuro Katayama等人將基于Markov模型的軟件測(cè)試研究擴(kuò)展到分布式系統(tǒng)上，就如何減少系統(tǒng)延遲進(jìn)行了深入討論[1]。文獻(xiàn)[2]針對(duì)模型建立了一個(gè)可視化的測(cè)試系統(tǒng)。M.Senne等人則構(gòu)建了一個(gè)基于Markov鏈的軟件分析系統(tǒng)，即EMMA系統(tǒng)。在國(guó)內(nèi)，夏威[3]曾研究過基于Markov模型的可靠性測(cè)試用例生成技術(shù);劉洋等研究過基于層次結(jié)構(gòu)Markov鏈的軟件可靠性建模方法，提出了一種基于層次結(jié)構(gòu)的使用模型的構(gòu)建方法[4];雷航也提出過嚴(yán)格Markov模型的軟件可靠性測(cè)試方法[5];陳麗敏曾提出改進(jìn)的二階Markov測(cè)試模型[6]。上述測(cè)試方法，要么是依賴經(jīng)驗(yàn)值來(lái)生成測(cè)試用例，要么只考慮前一狀態(tài)對(duì)當(dāng)前狀態(tài)的影響，生成的測(cè)試用例存在一定的不穩(wěn)定性，即生成的測(cè)試用例有時(shí)不能覆蓋所有的運(yùn)行狀態(tài)。且在生成測(cè)試用例時(shí)大都依賴大數(shù)定律，容易出現(xiàn)“測(cè)試用例爆炸”的情況。因此有必要研究并提出一種改進(jìn)的方法來(lái)解決已有測(cè)試用例生成不穩(wěn)定和測(cè)試用例數(shù)目爆炸的問題。

1 ?基于單純Markov鏈的測(cè)試用例生成方法

單純Markov測(cè)試方法是基于UML設(shè)計(jì)模型（用例圖、場(chǎng)景圖以及序列圖）的。由UML模型生成Markov使用模型，然后對(duì)Markov使用模型執(zhí)行單純馬爾可夫測(cè)試方法，生成測(cè)試用例和Markov測(cè)試模型，通過計(jì)算使用模型和測(cè)試模型的歐氏距離，判斷是否達(dá)到一定的測(cè)試充分性，直到滿足一定的測(cè)試充分性才停止測(cè)試[6]。其具體流程如圖1所示。

2 ?改進(jìn)的馬爾可夫測(cè)試方法

本文采用高階馬爾可夫模型對(duì)原有模型進(jìn)行改進(jìn)，借鑒趙愛華、吳彩華、徐錫山，Razib Hayat Khan等人由UML圖（用例圖、場(chǎng)景圖以及序列圖）生成Markov模型的方法[7?9]，生成Markov使用模型，提出基于高階Markov測(cè)試模型的二分查找的快速輪盤賭選擇算法，并應(yīng)用相對(duì)熵代替歐幾里得距離來(lái)作為充分性判定條件，從根本上來(lái)提高測(cè)試用例生成的穩(wěn)定性和測(cè)試結(jié)果判定的充分性。同時(shí)解決了復(fù)雜軟件在進(jìn)行測(cè)試時(shí)的測(cè)試用例爆炸現(xiàn)象，使其更適合大規(guī)模軟件的測(cè)試。

2.1 ?高階馬爾可夫使用模型的引入

由于當(dāng)前狀態(tài)很有可能受前面狀態(tài)的影響，所以引入馬爾可夫的階。[n]階表示當(dāng)前狀態(tài)受其前n個(gè)可達(dá)狀態(tài)的影響。為解決單純馬爾可夫測(cè)試方法的缺陷，在由Markov使用模型生成Markov測(cè)試模型時(shí)，引入一個(gè)中間鏈，考慮n階狀態(tài)轉(zhuǎn)移對(duì)當(dāng)前狀態(tài)的影響，重新計(jì)算狀態(tài)的轉(zhuǎn)移概率[P（x）]。設(shè)[L={L0，L1，L2，…，Ln}]是有限狀態(tài)取值集合[E={1，2，…，m}]的一個(gè)隨機(jī)序列，任意的時(shí)間t下，若：

2.4 ?算 ?例

本文以Prowell SJ[11]公開發(fā)表在Addison ?Wesley上的衛(wèi)星嵌入式控制軟件系統(tǒng)（SCS）為例，應(yīng)用改進(jìn)的測(cè)試用例生成方法和測(cè)試充分性判定方法，對(duì)衛(wèi)星嵌入式控制軟件進(jìn)行測(cè)試用例生成試驗(yàn)，能夠得到測(cè)試用例qBA，qBCDEFGHJKL，qBCDEFGHJFGHJKL，qBCDEFGHJFGIJKL和qBCGA數(shù)量為3，6，9，3，2時(shí)，與之前的測(cè)試用例生成的結(jié)果相比較，其生成的測(cè)試用例數(shù)目減少11.54%，且能夠覆蓋所有的測(cè)試情況，提高了測(cè)試用例的穩(wěn)定性。

3 ?實(shí)驗(yàn)驗(yàn)證

本文采用Java語(yǔ)言，應(yīng)用MyEclipse編程實(shí)現(xiàn)上述算法，并以衛(wèi)星嵌入式控制軟件[11]為例進(jìn)行測(cè)試用例的自動(dòng)化生成，并對(duì)熵值和歐氏距離的偏差值、生成的測(cè)試用例數(shù)目、覆蓋情況進(jìn)行統(tǒng)計(jì)。

3.1 ?測(cè)試用例生成數(shù)據(jù)比較

根據(jù)Markov使用模型，設(shè)置閾值，進(jìn)行試驗(yàn)，對(duì)停止準(zhǔn)則及測(cè)試用例生成個(gè)數(shù)，和生成時(shí)間進(jìn)行統(tǒng)計(jì)，本次試驗(yàn)采用進(jìn)行10次試驗(yàn)求平均值的方法計(jì)算求得。其測(cè)試結(jié)果如表1所示。

可以看到，由于隨機(jī)生成的原因，當(dāng)采用單純馬爾可夫測(cè)試方法時(shí)，閾值越小需要生成的測(cè)試用例數(shù)目越多，最后趨于穩(wěn)定。從實(shí)驗(yàn)數(shù)據(jù)可以看出當(dāng)閾值取值為0.005時(shí)，不論從測(cè)試時(shí)間還是測(cè)試用例的數(shù)目，都是比較合理的取值。除此之外，從測(cè)試結(jié)果還可以看到，單純馬爾可夫測(cè)試方法可能存在測(cè)試覆蓋不全的問題，測(cè)試不穩(wěn)定。改進(jìn)后的高階馬爾可夫測(cè)試方法閾值越小時(shí)與單純馬爾可夫方法相比，用時(shí)上基本一樣，但是生成的測(cè)試用例的數(shù)目卻大大減少，特別是針對(duì)較大型的軟件，測(cè)試用例減少較明顯，且都能夠覆蓋所有路徑，測(cè)試更穩(wěn)定。

3.2 ?充分性判定準(zhǔn)則比較

考慮到歐氏距離與熵值都是計(jì)算模型的偏差來(lái)對(duì)模型的充分性進(jìn)行評(píng)判的，且歐氏距離的區(qū)分度不如熵值的計(jì)算準(zhǔn)確。針對(duì)上述Markov測(cè)試模型，采用反證法，設(shè)置閾值為0.005，并統(tǒng)計(jì)在得到不同測(cè)試用例數(shù)目時(shí)的相對(duì)熵和歐氏距離的偏差。由于，相對(duì)熵的計(jì)算在計(jì)算每個(gè)狀態(tài)時(shí)都乘上了一個(gè)平穩(wěn)分布值，為了保持歐氏距離跟熵值在同一數(shù)量級(jí)上進(jìn)行比較，對(duì)歐氏距離進(jìn)行適當(dāng)?shù)目s放。

從圖2的結(jié)果可以看出，相對(duì)熵能更加精確地表示兩個(gè)模型的偏差。當(dāng)測(cè)試用例的數(shù)目逐漸增多時(shí)，歐氏距離與熵值的計(jì)算結(jié)果都快速下降，最后都到達(dá)一個(gè)相對(duì)穩(wěn)定的值，但相對(duì)熵值略大于歐氏距離。所以，當(dāng)反過來(lái)將相對(duì)熵作為判斷條件時(shí)，可以更加充分地進(jìn)行判斷是否到達(dá)停止條件。

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

本文算法有效地提高了測(cè)試用例生成的穩(wěn)定性和測(cè)試充分性判定的準(zhǔn)確性，解決了大規(guī)模軟件測(cè)試用例爆炸的情況。但還沒有真正地達(dá)到解放手工的要求，以后將致力于應(yīng)用改進(jìn)的算法開發(fā)一款測(cè)試用例自動(dòng)生成工具，使其能夠自動(dòng)地生成測(cè)試用例并對(duì)軟件進(jìn)行測(cè)試，真正實(shí)現(xiàn)測(cè)試自動(dòng)化。

參考文獻(xiàn)

[1] KATAYAMA T， ZHAO Z， KITA Y， et al. Proposal of a method to build Markov chain usage model from UML diagrams for communication delay testing in distributed systems [J]. Journal of robotics networking & artificial life， 2014， 1（2）： 120?124.

[2] MCGREGOR S， BUCKINGHAM H， DIETTERICH T G， et al. Facilitating testing and debugging of Markov decision processes with interactive visualization [C]// Proceedings of Symposium on Visual Languages and Human?Centric Computing. Atlanta： IEEE， 2015： 53?61.

[3] 夏威.基于Markov模型的可靠性測(cè)試用例生成技術(shù)研究[D].杭州：杭州電子科技大學(xué)，2016.

XIA Wei. Research on reliability test case generation based on Markov model [D]. Hangzhou： Hangzhou Dianzi University， 2016.

[4] 劉洋，于磊，徐煒珊，等.基于層次結(jié)構(gòu)Markov鏈的軟件可靠性建模方法[J].信息工程大學(xué)學(xué)報(bào)，2015，16（4）：477?482.

LIU Yang， YU Lei， XU Weishan， et al. Software reliability modeling based on hierarchical structure of Markov chain [J]. Journal of Information Engineering University， 2015， 16（4）： 477?482.

[5] 雷航，馬成功.Markov模型的軟件可靠性測(cè)試充分性問題的研究[J].電子科技大學(xué)學(xué)報(bào)，2010，39（1）：101?105.

LEI Hang， MA Chenggong. Testing adequacy of software reliability in Markov model [J]. Journal of University of Electronic Science and Technology of China， 2010， 39（1）： 101?105.

[6] 陳麗敏.基于馬爾可夫鏈模型的軟件可靠性測(cè)試方法研究[D].成都：電子科技大學(xué)，2010.

CHEN Limin. Research on software reliability testing method based on Markov chain model [D]. Chengdu： University of Electronic Science and Technology of China， 2010.

[7] 吳彩華，劉俊濤，彭世蕤，等.基于UML的軟件Markov鏈?zhǔn)褂媚Ｐ偷臉?gòu)建[J].計(jì)算機(jī)研究與發(fā)展，2012，49（8）：1811?1819.

WU Caihua， LIU Juntao， PENG Shirui， et al. Deriving Markov chain usage model from UML model [J]. Journal of computer research and development， 2012， 49（8）： 1811?1819.

[8] 趙愛華.基于UML模型的軟件使用模型生成技術(shù)研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué)，2017.

ZHAO Aihua. Research and implementation of software usage model generation technology based on UML model [D]. Beijing： Beijing Jiaotong University， 2017.

[9] KHAN R H， HEEGAARD P E. Translation from UML to Markov model： a performance modeling framework [M]. Dordrecht： Springer， 2010.

[10] 李俊海.高階Markov鏈轉(zhuǎn)移概率規(guī)律一種新表示法[J].應(yīng)用數(shù)學(xué)，2015，28（1）：158?164.

LI Junhai. A representation for transition probability of high?order Markov chain [J]. Mathematica applicata， 2015， 28（1）： 158?164.

[11] PROWELL S J， TRAMMELL C J， LINGER R C， et al. Cleanroom software engineering： technology and process [M]. New York： McGraw Hill， 1998.

[12] PROWELL S J. TML： a description language for Markov chain usage models [J]. Information and software technology， 2000， 42（12）： 835?844.