一种基于高阶Markov使用模型的测试用例自动生成方法

赵卫东 李有俊 张丽

关键词： 高阶马尔可夫使用模型; 快速轮盘赌; 二分查找; 相对熵; 软件测试; 测试用例自动生成

中图分类号： TN911.23?34                     文献标识码： A                       文章编号： 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）链是根据马尔可夫性得到的一种随机过程模型。马尔可夫性主要体现在其无后效性，即后发生的状态只跟当前状态有关，与过去状态的发生无关。用MarKov链描述软件的真实运行过程即为Markov使用模型。由于Markov使用模型能够有效地描述软件的真实运行过程，近年来，基于Markov使用模型的软件测试技术是软件测试领域研究的热点之一。

Tetsuro Katayama等人将基于Markov模型的软件测试研究扩展到分布式系统上，就如何减少系统延迟进行了深入讨论[1]。文献[2]针对模型建立了一个可视化的测试系统。M.Senne等人则构建了一个基于Markov链的软件分析系统，即EMMA系统。在国内，夏威[3]曾研究过基于Markov模型的可靠性测试用例生成技术;刘洋等研究过基于层次结构Markov链的软件可靠性建模方法，提出了一种基于层次结构的使用模型的构建方法[4];雷航也提出过严格Markov模型的软件可靠性测试方法[5];陈丽敏曾提出改进的二阶Markov测试模型[6]。上述测试方法，要么是依赖经验值来生成测试用例，要么只考虑前一状态对当前状态的影响，生成的测试用例存在一定的不稳定性，即生成的测试用例有时不能覆盖所有的运行状态。且在生成测试用例时大都依赖大数定律，容易出现“测试用例爆炸”的情况。因此有必要研究并提出一种改进的方法来解决已有测试用例生成不稳定和测试用例数目爆炸的问题。

1  基于单纯Markov链的测试用例生成方法

单纯Markov测试方法是基于UML设计模型（用例图、场景图以及序列图）的。由UML模型生成Markov使用模型，然后对Markov使用模型执行单纯马尔可夫测试方法，生成测试用例和Markov测试模型，通過计算使用模型和测试模型的欧氏距离，判断是否达到一定的测试充分性，直到满足一定的测试充分性才停止测试[6]。其具体流程如图1所示。

2  改进的马尔可夫测试方法

本文采用高阶马尔可夫模型对原有模型进行改进，借鉴赵爱华、吴彩华、徐锡山，Razib Hayat Khan等人由UML图（用例图、场景图以及序列图）生成Markov模型的方法[7?9]，生成Markov使用模型，提出基于高阶Markov测试模型的二分查找的快速轮盘赌选择算法，并应用相对熵代替欧几里得距离来作为充分性判定条件，从根本上来提高测试用例生成的稳定性和测试结果判定的充分性。同时解决了复杂软件在进行测试时的测试用例爆炸现象，使其更适合大规模软件的测试。

2.1  高阶马尔可夫使用模型的引入

由于当前状态很有可能受前面状态的影响，所以引入马尔可夫的阶。[n]阶表示当前状态受其前n个可达状态的影响。为解决单纯马尔可夫测试方法的缺陷，在由Markov使用模型生成Markov测试模型时，引入一个中间链，考虑n阶状态转移对当前状态的影响，重新计算状态的转移概率[P（x）]。设[L={L0，L1，L2，…，Ln}]是有限状态取值集合[E={1，2，…，m}]的一个随机序列，任意的时间t下，若：

2.4  算  例

本文以Prowell SJ[11]公开发表在Addison ?Wesley上的卫星嵌入式控制软件系统（SCS）为例，应用改进的测试用例生成方法和测试充分性判定方法，对卫星嵌入式控制软件进行测试用例生成试验，能够得到测试用例qBA，qBCDEFGHJKL，qBCDEFGHJFGHJKL，qBCDEFGHJFGIJKL和qBCGA数量为3，6，9，3，2时，与之前的测试用例生成的结果相比较，其生成的测试用例数目减少11.54%，且能够覆盖所有的测试情况，提高了测试用例的稳定性。

3  实验验证

本文采用Java语言，应用MyEclipse编程实现上述算法，并以卫星嵌入式控制软件[11]为例进行测试用例的自动化生成，并对熵值和欧氏距离的偏差值、生成的测试用例数目、覆盖情况进行统计。

3.1  测试用例生成数据比较

根据Markov使用模型，设置阈值，进行试验，对停止准则及测试用例生成个数，和生成时间进行统计，本次试验采用进行10次试验求平均值的方法计算求得。其测试结果如表1所示。

可以看到，由于随机生成的原因，当采用单纯马尔可夫测试方法时，阈值越小需要生成的测试用例数目越多，最后趋于稳定。从实验数据可以看出当阈值取值为0.005时，不论从测试时间还是测试用例的数目，都是比较合理的取值。除此之外，从测试结果还可以看到，单纯马尔可夫测试方法可能存在测试覆盖不全的问题，测试不稳定。改进后的高阶马尔可夫测试方法阈值越小时与单纯马尔可夫方法相比，用时上基本一样，但是生成的测试用例的数目却大大减少，特别是针对较大型的软件，测试用例减少较明显，且都能够覆盖所有路径，测试更稳定。

3.2  充分性判定准则比较

考虑到欧氏距离与熵值都是计算模型的偏差来对模型的充分性进行评判的，且欧氏距离的区分度不如熵值的计算准确。针对上述Markov测试模型，采用反证法，设置阈值为0.005，并统计在得到不同测试用例数目时的相对熵和欧氏距离的偏差。由于，相对熵的计算在计算每个状态时都乘上了一个平稳分布值，为了保持欧氏距离跟熵值在同一数量级上进行比較，对欧氏距离进行适当的缩放。

从图2的结果可以看出，相对熵能更加精确地表示两个模型的偏差。当测试用例的数目逐渐增多时，欧氏距离与熵值的计算结果都快速下降，最后都到达一个相对稳定的值，但相对熵值略大于欧氏距离。所以，当反过来将相对熵作为判断条件时，可以更加充分地进行判断是否到达停止条件。

4  结  语

本文算法有效地提高了测试用例生成的稳定性和测试充分性判定的准确性，解决了大规模软件测试用例爆炸的情况。但还没有真正地达到解放手工的要求，以后将致力于应用改进的算法开发一款测试用例自动生成工具，使其能够自动地生成测试用例并对软件进行测试，真正实现测试自动化。

参考文献

[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模型的可靠性测试用例生成技术研究[D].杭州：杭州电子科技大学，2016.

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

[4] 刘洋，于磊，徐炜珊，等.基于层次结构Markov链的软件可靠性建模方法[J].信息工程大学学报，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模型的软件可靠性测试充分性问题的研究[J].电子科技大学学报，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] 陈丽敏.基于马尔可夫链模型的软件可靠性测试方法研究[D].成都：电子科技大学，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链使用模型的构建[J].计算机研究与发展，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模型的软件使用模型生成技术研究与实现[D].北京：北京交通大学，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链转移概率规律一种新表示法[J].应用数学，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.