软件Markov链使用模型生成与化简技术

冯俊池，于 磊，刘 洋

（1.信息工程大学，河南 郑州450001；2.数学工程与先进计算国家重点实验室，河南 郑州450001）

0 引 言

基于使用模型的可靠性测试［1－4］采用使用模型来代表系统可能的运行情况和所发生的概率，使测试接近软件的真实使用。在净室软件工程［5］中，采用Markov链描述软件使用模型，其主要根据软件的相关技术文档生成，通过提取软件运行中的激励、响应以及之间的交互关系来确定使用模型的状态与迁移，迁移概率可通过对早期版本使用情况进行分析等方式得到［6］。近年来，UML模型在面向对象软件设计中得到广泛应用，也逐渐被应用到使用模型生成技术中［7－9］。现有方法将软件中每个消息的发生视为状态的改变，以此生成Markov链使用模型，由于将每个消息进入的状态作为使用模型中的一个状态，生成的使用模型中存在部分冗余的状态和迁移。吴彩华等将场景的发生视为软件状态的改变，场景的执行概率作为迁移概率，生成场景级的使用模型［8］，该方法生成的使用模型状态空间较小，但状态粒度较粗，无法反映用例内部的消息交互，用例执行过程中的相关输入的依赖关系被忽略，有时不能真实体现软件的实际使用情况；李秀华为每条消息增加约束条件，通过观察消息发生前后的系统关键向量是否变化来消除使用模型中的冗余状态和迁移［9］，但该做法增加了人员的工作量，且依赖于领域知识，适应性不强。

本文将代表了用例执行情况的顺序图［10］作为用例的不同场景，对UML 模型加以扩展，加入各场景的执行概率pf 和后置条件post 以及用例执行顺序关系，通过分析UML模型中软件与外部环境的消息交互来确定使用模型中的状态，生成比较精确的Markov链使用模型。同时为了避免状态空间爆炸问题，提出了冗余状态与等价状态的概念，设计了使用模型化简算法，并给出了相关证明。

1 软件使用模型

定义1 软件Markov链使用模型定义为一个五元组（S，T，δ，q0，F），S 是软件使用模型的状态集合，每个状态s∈S 是一个三元组 （Sn，Type，Notation），其中Sn是状态编号，Type表示状态是否是初始状态或终止状态，终止状态的Notation为后置条件，在使用模型生成过程中用于识别相同的终止状态，其余状态该值为空；T 是状态之间的迁移的集合，每个迁移t∈T 是一个二元组 （Trans，pf），其中Trans是以发生时间先后为全序关系的激励响应对（sim，res）的有序集合，当其为空时代表不同场景或不同用例的模型之间的转换，激励sim 与响应res 来自消息集合；δ是状态之间的迁移关系S×T→S；q0是使用模型的初始状态，q0∈S；F 是使用模型的终止状态集合，FS。

定义2 如果使用模型中的状态s有且仅有一条入迁移t′和出迁移t″，t′的源状态和t″的目的状态之间没有直接迁移，则状态s为冗余状态。

对于图1 （a）所示的使用模型，软件由状态Si经过迁移tm到达状态Sj，又经过迁移tn到达状态Sk，状态Si和Sk之间没有直接迁移，状态Sj为冗余状态。可以通过将Sj与Sk合并来减少状态冗余。合并时，删除状态Sj，创建迁移tk连接Si和Sk，tk.Trans＝tm.Trans ∪tn.Trans，tk.pf ＝tm.pf×tn.pf，化简后如图1 （b）所示。

图1 冗余状态

在软件可靠性测试中，使用模型主要用来生成模拟真实使用情况的测试序列，根据测试序列执行测试。软件的测试序列对应于使用模型从初始状态到结束状态的一条迁移遍历路径t＝ （t1，t2，…，tL），t的执行概率为

式中：pti——路径t中第i个迁移的概率，L——路径中迁移数量。

针对图1中使用模型的冗余状态Sj，将其与Sk合并化简并不影响软件可靠性测试，下面给出证明：

软件可靠性测试与测试序列t的执行路径及执行概率p（t）相关，将冗余状态Sj化简后，路径t＝ （t1，…，tm，tn，…，tL）变为t＝ （t1，…，tk，…，tL），其中迁移tk对应执行路径等同于tm和tn的执行路径，软件执行路径并未改变。

原模型中ptm与化简后的模型中ptk相同，由于原模型中状态Sj只有一条出边，ptn＝1，由式 （1）可知路径执行概率p（t）未改变。因此冗余状态的化简对软件可靠性测试无影响。

定义3 如果使用模型的两个状态Si和Sj具有相同的迁移且迁移指向的下一状态相同，Si和Sj的源状态不同，则状态Si和Sj为等价状态。

对于图2 （a）所示的使用模型，状态Si和Sj具有相同的迁移tk指向Sk，Si和Sj的源状态不同，Si和Sj为等价状态。可将Si和Sj合并为状态Sij，其出迁移tk指向Sk，原Si和Sj的入迁移指向Sij。

图2 等价状态

以图2所示模型为例，下面针对等价状态的合并不影响软件可靠性测试给出证明：

对经过状态Si的路径t＝ （t1，…，tm，tk，…，tL），合并等价状态后，由于原迁移tk相同，所以测试序列执行路径并未改变，执行概率p（t）未变化，经过状态Sj的路径也是如此。因此，等价状态的合并对软件可靠性测试无影响。

2 软件使用模型生成与化简

根据扩展UML模型生成软件Markov链使用模型，首先生成用例的使用模型，然后集成所有用例的使用模型得到软件的使用模型，最后对使用模型进行状态简化。

2.1 生成用例的使用模型

首先生成每个场景的使用模型，当软件接收外部激励消息并做出响应时，认为其状态发生了改变，因此将外部激励与软件响应作为状态间迁移，每个迁移对应着一个新状态，逐步建立使用模型。由于存在软件先后接收多条激励消息或发出多条响应消息的情况，为便于处理，将第二条及之后的每条激励或响应单独作为激励响应对，其中对应的响应或激励设为null。算法流程如图3 所示，场景执行概率为pf，执行后置条件为post，消息数量为L，这里只考虑软件与外部交互的消息。

然后通过集成场景的使用模型来构造用例的使用模型，算法如下：

步骤1 令c为第一个场景的使用模型，在c上集成其它场景的使用模型，对其它所有场景的使用模型ci做如下处理：

（1）令当前状态cs指向c 的s0，对ci的所有迁移t 进行如下处理：

图3 场景使用模型生成流程

1）如果cs的迁移t′与t的Trans 不同，新建状态s，δ（cs，t）＝s，cs指向s；

2）如果t′与t的Trans相同，令t′的迁移概率pf′叠加上t的迁移概率pf，cs指向t′的目的状态。判断是否满足如下情况：如果t是最后一条迁移，则插入新状态s，令迁移t″＝ （，pf），δ（cs，t″）＝s，将cs指向s；如果cs是终止状态，则插入新状态s，将cs的Type 和Notation 值赋给s，令t″＝ （，pf′－pf），δ（cs，t″）＝s；

（2）将ci的终止状态的Type 和Notation 值赋给cs，如果存在和cs的Type 和Notation 值相同的状态s，cs的入迁移为t，前一状态为s′，令δ（s′，t）＝s，将cs删除，继续集成下一场景；

步骤2 所有场景集成后，对各个状态出迁移的概率进行归一化，令其概率之和为1。

2.2 集成各用例的使用模型

根据用例执行顺序关系集成各用例的使用模型，用例执行顺序关系即一个用例执行完成后进入某状态并执行另一用例的概率，定义为UcSeq＝ （Uci，post，Ucj，pf），代表用例Uci执行完成的后置条件为post 时，下一个执行的用例是Ucj的概率是pf。

步骤1 遍历用例执行顺序关系UcSeq：

对Uci中状态的Notation 值为post的终止状态s1，Ucj的初始状态s2，令迁移t＝ （，pf），δ（s1，t）＝s2；

步骤2 确定软件使用模型的初始状态q0，将结束状态加入集合F。

2.3 使用模型化简

将软件使用模型的状态化简，由于合并等价状态之后会出现新的冗余状态，因此在合并等价状态之后消除冗余状态，算法如下：

步骤1 合并等价状态，对所有状态s：

（1）若s 存在多个入迁移，记s 的上一状态集合为Spre，判断是否存在集合S′preSpre，S′pre中状态数量至少两个并且满足：状态的出迁移相同；状态的上一状态不同；

（2）若存在集合S′pre，将S′pre中状态合并为新状态。标记s已遍历，转到新状态；

（3）否则，标记s已遍历，转到下一状态。

步骤2 消除冗余状态，对所有状态s：

（1）判断s是否为冗余状态；

（2）若s为冗余状态，将s删除，并修改相关迁移，转到下一状态；

（3）若s 不是冗余状态，标记s 已遍历，转到下一状态。

3 使用模型生成实例

模 拟 电 话 交 换 系 统 （telephone switching simulation system，TSSS）由交换机 （Switch）、主叫方 （PhoneA）和被叫方 （PhoneB）组成，用例包含有摘机、拨号、应答、主叫挂机、主叫遇忙挂机和被叫挂机。

部分用例执行顺序关系为： （拨号，待接通，应答，1），（应答，通话，主叫挂机，0.5）， （应答，通话，被叫挂机，0.5）。

图4、图5分别是拨号及应答两个用例的顺序图。表1是部分用例的顺序图的执行后置条件和概率。系统中消息所对应的含义为：OFK：摘机；RDT：发拨号音；DIA：拨号；SDT：停拨号音；RET：发错误音；RFR：查询空闲；FRE：返回空闲；BUY：返回忙；RBT：发忙音；RCT：发振铃音；RKT：发回铃音；NRE：无应答；SCT：停振铃音；SKT：停回铃音；ONK：挂机；SET：停错误音；SBT：停忙音。

图4 拨号用例的顺序

图5 应答用例的顺序

对TSSS系统构造使用模型，状态化简前如图6所示，其中以虚线表示的状态属于冗余状态，状态S18和S19互为等价状态。最终生成的模型如图7所示，其中迁移为：

在可靠性测试数据生成中，根据迁移发生概率所占的比例大小选择当前状态发生的迁移，得到由初始状态到终止状态的一条迁移路径，将其中的null去掉后的激励响应序列即为一条测试数据。对TSSS软件，迁移序列t1→t3→t5→t7→t10→t12对应的测试数据为： （OFK，RDT，DIA，RFR，FRE，RCT，RKT，OFK，SCT，SKT，ONK，RBT，ONK，SBT），表示了双方通话结束后主叫挂机的一种情况。

表1 部分用例顺序图执行后置条件和概率

图6 化简前的TSSS软件使用模型

图7 TSSS软件使用模型

4 实验及数据分析

为了验证使用模型化简算法的有效性，采用仿真方法得到若干使用模型进行化简前后的对比实验。

将每个状态的迁移限定为1～3条，随机生成状态数在300到500之间的使用模型，并对其进行化简。化简前后的使用模型状态数量对比如图8所示。

图8 使用模型状态数量

针对图8中的使用模型进行实验，统计生成10000 条测试数据所用时间，对比情况如图9所示。

图9 测试数据生成时间

由化简前后的使用模型状态数及测试数据生成时间对比可以看出，化简后的使用模型中状态数量比化简前大量减少，降低了使用模型的复杂度，在一定程度上解决了状态空间爆炸问题；生成相同数量的测试数据所需时间只占化简前所需时间的30%到50%，节省了大量测试数据生成时间。

5 结束语

本文改进了基于扩展UML模型的软件Markov链使用模型生成方法，并提出了一种使用模型化简方法。通过实验验证了该方法的有效性，采用该方法生成的使用模型在一定程度上解决了状态空间爆炸问题，有利于测试数据的自动生成与软件的可靠性测试效率的提高。

该方法中场景执行概率需要人为给出，因此如何更好地估计软件场景执行概率需要进一步的研究。

［1］Gayen Tirthankar，Misra R B.Operational profile based relia－bility assessment of COTS software［J］.International Journal of Computer Applications，2010，4 （1）：14－18.

［2］Li Qiuying，Li Xiang，Wang Jian，et al.Study on the accelerated software reliability demonstration testing for high reliability software based on strengthened operational profile ［C］／／Proceedings of the 2nd International Conference on Computer Technology and Development.Cairo：IEEE Computer Society Press，2010：655－662.

［3］Bohr Frank.Model based statistical testing of embedded systems［C］／／Proceedings of the fourth International Conference on Software Testing，Verification and Validation Workshops.Berlin：IEEE Computer Society Press，2011：18－25.

［4］CHEN Zhenhua，WANG Feng.Software reliability test and evaluation based on Markov chain usage model［J］.Computer Engineering and Design，2007，28 （12）：2768－2771 （in Chinese）.［陈振华，王峰.基于Markov链使用模型的软件可靠性测评方法研究 ［J］.计算机工程与设计，2007，28 （12）：2768－2771.］

［5］Sastry J K R，Chandra P V.A formal framework for verification and validation of external behavioral models of embedded systems represented through black box structures ［C］／／Proceedings of the 2nd International Advance Computing Conference.Patiala：IEEE Computer Society Press，2010：430－435.

［6］Feliachi Abderrahmane，Le Guen Hélène.Generating transition probabilities for automatic model－based test generation［C］／／Proceedings of the third International Conference on Software Testing，Verification and Validation，2010：99－102.

［7］WANG Xin，QIN Zheng，HAN Fengyan.UML based hybrid model for generation of software reliability test cases［J］.Journal of Xi’an Jiaotong University，2007，41 （4）：421－425 （in Chinese）.［王昕，覃征，韩峰岩.基于UML的软件可靠性测试用例生成的混合模型 ［J］.西安交通大学学报，2007，41（4）：421－425.］

［8］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 （in Chinese）. ［吴彩华，刘俊涛，彭世蕤，等.基于UML的软件Markov链使用模型的构建 ［J］.计算机研究与发展，2012，49 （8）：1811－1819.］

［9］LI Xiuhua.Research and implementation of software reliability testing technology based on UML model［D］.Chengdu：University of Electronic Science and Technology of China，2007：47－51 （in Chinese）.［李秀华.基于UML模型的软件可靠性测试技术的研究与实现［D］.成都：电子科技大学，2007：47－51.］

［10］HUANG Long，YANG Yuhang，LI Hu.Formalization description of message in UML sequence diagram and corresponding feature analysis［J］.Computer Engineering and Design，2010，31 （15）：3427－3431 （in Chinese）. ［黄陇，杨宇航，李虎.UML 顺序图中消息的形式化描述与相关特性分析［J］.计算机工程与设计，2010，31 （15）：3427－3431.］