基于Markov模型的Web服务软件测试用例生成

申珅 党向盈

摘要：软件测试是保证 Web 服务软件质量的重要技术之一。变异测试是一种面向缺陷的测试技术，变异测试用例生成效率将影响 Web 服务测试的效率和成本。该文针对Web服务软件，基于Markov模型高效生成变异测试用例。首先，随机生成一定样本容量的测试数据，针对每一个合约变异体，基于弱变异测试准则，执行Web 服务方法及其变异体，根据合约变异预言来判断变异体是否被杀死；然后基于Markov链预测模型，计算变异体之间的关联度；再根据变异体之间关联度，生成变异体序列，即与其他变异体关联度大的变异体排在序列的前面；最后，采用遗传算法，依次序列顺序，生成杀死合约变异体的测试用例。

关键词：Markov模型；Web服务软件；测试用例生成；变异测试

中国分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）28-0265-03

Test Data Generation for Web Service Software Based on Markov Model

SHEN Shen， DANG Xiang-ying

（ Department of Information and Electrical Engineering， Xuzhou Institute of Technology， Xuzhou 221000，China）

Abstract： Software testing is one of the important technologies to ensure the quality of Web service software. Mutation testing is a defect-oriented testing technique. The efficiency of generating test data for mutation testing will affect the cost of Web service testing. In this paper， we generating test data for Web service software by mutation testing based on Markov model. Firstly， we randomly generate test data of a certain sample size， implement the mutants and its original Web service program based on the weak mutation test criterion， and determine whether the mutants is killed according to the contract mutation prediction. Then， we calculate the correlation between the mutants， based on which we generate the mutant sequence， i.e.， the mutants that have more correlation with other mutants are in the front of the sequence. Finally， we generate test data that kill mutants by the sequential order based on GA.

Key words： Markov model； web service software； test data generation； mutation testing

1 背景

2015年3月，李克強总理在政府工作报告中提出“互联网+”行动计划，“互联网+”作为一项国家战略，为未来的各领域的发展指明了方向，软件的应用也因此迎来新的发展，但是软件的可靠性和质量却没有得到相应的提高，成为制约软件产业发展的一个重要因素。Web服务是互联网上共享数据和功能的一种有效手段，是基于通信协议、服务描述、服务发现、Web协议和开放性XML标准的新一代的分布式计算模式。

Web服务（Web Service）技术是基于互联网的电子服务的基础技术。Web服务是通过网络实现发布、查找和调用的具有自描述能力的软件构件，通过在网络上暴露的应用接口，能够方便地对其实现调用。Web服务采用Http协议进行通信，由于任何运行Web服务浏览器的机都在使用Http协议，因此，Web服务具有平台无关性。在此之前，没有一个应用程序通信标准是独立于平台、组建模型和编程语言。

Web服务测试用例自动生成，是软件测试自动化研究的核心内容之一[1]。由于无法得知服务组件的实现细节，服务接口描述信息就成为测试用例生成的重要依据。但是，仅凭接口描述直接生成的测试用例质量差，无法满足实际缺陷检测的需要。

变异测试[2]是一种基于错误的测试方法，基本原理是使用变异算子，即合乎语法规则对程序源代码做微小的改动，改动后的程序被称作为变异体。如果某条测试用例允许原程序和变异体，能够产生不同的输出结果或影响，则称其杀死了变异体，那么该测试用例是有效的，应该予以保留并利用。如果无法区分两者，则认为测试用例无法定位错误、变异代码没有被执行到。通过这种方法，可以生成杀死变异体的测试用例，从而有效扩充测试集，有利于测试用例的生成和选择。变异测试也常被用于评价测试用例集的质量，也被用于辅助生成具有很高缺陷检测能力的测试用例，而且，在服务软件测试中也已经得到了初步应用。

基于Markov预测Zuckerman 等[3]最早提出了基于 Markov 模型的用户访问预测， Markov 模型是一种简单而经典的预测模型，但高阶 Markov 模型所覆盖的状态空间十分庞大，导致计算复杂度过高；而低阶 Markov 模型预测准确率较低。邢永康等[4]提出并建立了一种基于用户分类的新模型，多Markov链预测模型提高了预测准确率，但时间复杂度较高。

该文基于Markov链使用模型，分析变异体的约束组合关系，以及生成有效覆盖所有变异体的服务测试数据生成技术。将软件测试结果的分析问题转化为一个经典概率问题，并基于马尔可夫（Markov）链模型建立变异体之间的关联，通过数学方法实现了软件测试模型的简化，加速测试用例的生成，从而降低了测试的复杂度。

2 Web服务软件变异测试过程

整个的测试过程应该由以下几个步骤组成：

1）解析0WL-S文档，提取输入信息和流程信息。

2）根据提取的输入信息，生成初始测试数据集，可以随机生成，也可采用等价划分、边界法等常规的测试用例生成方法。

3）分析流程信息，找到文档中满足变异条件的点，结合具体变异的方法，生成变异体。

4）分别执行原服务和变异后的服务，比较结果，相同则选取或设计新的测试用例。结果不同，意味着变异体被杀死，标记测试用例为有效。

5）变异充分度达到要求时，测试过程结束。

变异体生成工具主要分为两个部分：解析OWL-S文档，提取需要的输入信息和工作流信息；对OWL-S进行改动，生成变异体。通过对OWL-S进行变换可以生成变异体，变异体的生成可以通过XSLT对OWL-S进行变换完成。解析OWL-S文档需要充分利用已有的关于解析XML语言的工具包。

变异算子可根据具体的Web服务进行调整，可以包含简单的传统变异算子，也可以包含专门 针对待测Web服务所对应的OWL-S文档而设计的变异算子。利用这些变异算子生成变异体后，以杀死变异体为目标，生成测试用例，作为最后的输出。

由此可见，变异体尽早被杀死，则执行的次数越少，测试用例的选择决定了变异体是否能尽早被杀死，因此如何对测试用例进行选择，将影响着变异测试的效率。该文提出的测试用例选择策略，实质是对变异体选择策略，优先选择的变异体生成的测试用例质量越高。而且从执行的测试用例的数量进行考虑，基于Markov链模型选择的测试用例数量，最大限度地减少执行次数，降低测试代价，提高效率。

3 Markov预测模型

Markov是俄国著名数学家，由于最早提出了预测方法，命名马尔可夫方法[5]。Markov方法的基本思想来源于现实世界的这样一类事物，它的变化只与近期状态有关，而与过去的状态无关。该文中Markov的状态为变异体，变异体被杀死的状态与另一（多）个变异体被杀死之间的关联。

设初始状态为[S0]，它可以经过多中状态变化，记这些状态为[S0，S0，...，Sn-1，Sn]，到事物经过n次变化，到了状态[Sn]，该状态只与前一次状态[Sn-1]有关，而n-1次之前的状态无关，这也是状态转移的后无关性。如果多个事物在变动的状态转移过程中，每一次变动的状态都具有无后效性，那么这些事物的集合，称为马尔可夫链[6]。

马尔可夫过程体现了事物状态变化的一个特点，事物由前一种状态变化到后一种状态，虽然与以往状态无关，但在变化的过程中需要有个转移中间状态，设定事物的前一种状态为[Sn-1]，后一种状态为[Sn]，转移中间状态为D，三者关系为

[Sn=Sn-1×D] （1）

公式（1）可以递推得到

[Sn=S0×Dn-1] （2）

式（2）代表了马尔可夫本人创立的预测理论的基本推导过程。

运用马尔可夫理论对系统进行可靠性分析，首先马尔可夫过程属于随机过程，需要有三個基本的描述量[33]，即概率向量、概率矩阵和转移概率矩阵。记概率向量为[Δ（a1，a2，...，an）]，其中[a1，a2，...，an≥0，i=1nai=1]；概率矩阵为[n×n]的方阵；转移矩阵为[D]。Markov过程具有遍历性，无论在哪个状态开始，经过相当多的转移次数后，到达预定状态的概率接近一个常数。这个性质可以帮助预测系统在经过相当长的状态转移后，能够到达一个稳定的状态。

4 优先选择变异体策略

变异算子是变异系统的重要部分，是产生变异体的依据。与传统的程序变异类似，通过对形式化的合约定义，做微小的语法修改来产生变异后的合约，但并未给出所采用的合约变异算子及变异预言。我们借鉴了传统程序变异中的成熟变异算子。

表1中的变异算子，可对 Web 服务方法的合约进行变异，产生合约变异体。由于合约语句比一般的程序少很多，因此它生成的变异体个数和花费的时间都低于传统的程序变异。合约变异体将与原 Web 服务组合形成 Web 服务的变异体。

在针对程序语句的变异测试中，一般采用程序的运行结果作为区分变异体与原程序的条件。由于我们变异Web服务的内部实现，Web服务的运行结果不会在变异前后发生改变，因此将合约检查结果的一致与否作为判断变异体是否被杀死的条件。

首先采用随机发生成一定样本容量的测试数据，针对每一个变异体，基于弱变异测试准则，执行Web 服务方法及其变异体，根据合约变异预言来判断变异体是否被杀死；然后再基于Markov链预测模型，计算变异体之间的关联；再根据变异体之间关联度，排序变异体，即与其他变异体关联性大的变异体排在前面；最后，采用遗传算法，依次杀死排序好的变异体。

该文基于Markov链预测模型排序变异体，那么先杀死的变异体，测试用例生成的质量越高，它们杀死其他变异体的概率越大，那么序列后面的变异体，就不用再生成测试用例，这说明，该方法可以提高变异测试的效率，降低了反复执行变异体的代价。

此外，由于变异充分度可被用于评价测试用例集的优劣，因此存在以杀死尽可能多的变异体为目标来生成测试用例生成策略。为了求解变异得分，设生成的合约变异体为的数量为[M]，等价变异体数目为[Mq]，那么生成的测试用例测试集，执行Web 服务方法及其变异体，统计杀死的变异体为[Mkill]，则变异得分为

[Qkill=MkillM-Mq] （3）

由式（3）可知，[Qkill]越大，说明测试充分性越大。

5 实验结果和分析

为了验证该文所提出方法的有效性 我们基于测试 Web 服务的原型，采用传统方法和该文方法，测试5个Web服务软件，考察生成合约变异体数目，执行次数，变异得分情况。

从该表中可以看出，针对5个被测程序，该文方法生成的测试用例数目更少，变异得分更高。说明，该文方法是高效的，有利于降低合约变异测试代价，提高Web服务测试的效率。

6 结束语

Web服务得到了广泛关注和应用，其测试需求也日益增大。但由于Web服务的源代码不对用户公开，用户只能获得包含接口信息的OWL-S文档，其该文档描述了服务组合的功能、模型和流程，增加相关信息和执行语义，可从中提取一些测试所需的信息。该文提出的方法直接以OWL-S文档合约作为变异对象，针对不同的测试需求采用不同的变异算子，基于Markov链预测模型确定变异体优先选择策略，优先生成序列前面的变异测试用例，从而降低测试的代价，提高Web服务测试的效率。

参考文献：

[1] Dalley J L. The art of software testing[J]. Aerospace & Electronics Conference， 1979， 17（2）： 757-760. vol.2.

[2] DeMillo R A， Lipton R J， Sayward F G. Hints on test data selection： help for the practicing programmer[J]. IEEE Computer， 1978， 11（4）： 34-41.

[3] Zukerman I， Albrecht D W， Nicholson A E. Predicting Users Requests on the WWW[C]// International Conference on User Modeling. Springer-Verlag New York， Inc. 1999： 275-284.

[4] 刑永康， 馬少平. 多Markov链用户浏览预测模型[J]. 计算机学报， 2003（11）： 1510-1517.

[5] Fei H， Wang Z， Wang S. A Reliability Assessment Method of Urban Mass Transport Software Based on Markov Model[C]// Fourth International Conference on Computational Intelligence and Communication Networks. IEEE， 2012： 943-947.

[6] Wang R， Ma S. Stability and stabilization for nonlinear discrete-time singular Markov jump systems with time-varying delay[C]// Control and Decision Conference. IEEE， 2013： 3874-3879.

【通联编辑：谢媛媛】