基于UML状态图的列控中心软件测试路径生成方法

王秀玄

（西南交通大学 信息科学与技术学院， 成都 611756）

基于UML状态图的列控中心软件测试路径生成方法

王秀玄

（西南交通大学 信息科学与技术学院， 成都 611756）

针对列控中心测试，介绍了基于UML状态图的列控中心测试路径生成方法。根据列控中心需求规范建立UML状态图模型；采用改进的深度优先搜索算法（DFS）自动搜索有向图得到从初始节点到终止节点的所有路径集合，利用贪心算法构造超串合并测试需求；利用路径集合扩展测试需求集合，最终实现测试路径自动生成；以列控中心改变区间运行方向功能为例，给出测试路径生成方法实现。

测试路径；UML状态图；列控中心；深度优先搜索；超串

列控系统是保证列车安全运行、提高列车运行效率和行车密度的关键设备，而列控中心（TCC）是列控系统地面设备的重要组成部分，在CTCS-2级列控系统中，根据线路限速、进路信息、区段占用等信息，产生行车许可，在保证行车安全中起着重要作用。列控中心软件是典型的安全关键软件（Safety Critical Software），软件的正确性和安全性直接关系到行车安全，软件测试已成为保证列控中心质量的一项重要任务。列控中心输入输出复杂，信息交互频繁，对安全性和实时性要求严格。然而，目前对于列控中心软件的测试主要由专家或工程师根据工作经验设计测试案例，采用手工测试的方式分析软件在各种场景下的响应行为，测试工作繁重[1]，并且易出现漏编漏测，无法保证测试的完备性。

基于UML模型的软件测试技术采用UML模型对系统需求建模，由模型生成测试用例，可以降低测试工作量，并且模型具有直观性。本文根据列控中心需求规范建立UML状态图模型，将状态图转化为有向图，利用超串思想组合测试需求子路径，通过改进深度优先搜索算法遍历有向图得到遍历路径，并用来扩展组合后的测试需求子路径，得到完整测试路径。以列控中心改变区间运行方向为例，验证了该方法的可行性。

1 基于UML状态图的测试需求

测试主要包括基于代码的测试和基于规格说明的测试，其中，基于规格说明的测试主要关注软件规格说明所描述的系统功能，对系统功能描述进行验证和确认[2]。基于UML模型的测试属于基于规格说明测试。根据期望输出与实际输出的一致性，分析系统的每个功能是否符合系统需求。

1.1 UML状态图

UML模型图包括用例图、状态图、顺序图、活动图、协作图等多种图。其中，状态图能够描述一个特定对象的所有可能的状态和触发状态转移的条件，以及对象的动作行为，通常表现为一个对象所经历的状态序列，也包含引起状态转移的事件，以及状态转移伴随的动作，它可以对一个对象的生命周期建模[3]。状态图能够清晰地展示列控中心软件的逻辑、结构及功能，便于后期的软件分析与测试。

1.2 基于UML的覆盖准则

UML状态图包含诸多元素，覆盖准则应从不同程度上覆盖这些元素。不同覆盖准则会确定不同的测试需求。UML状态图主要涉及的测试覆盖准则有：状态覆盖准则、状态变迁覆盖准则、状态变迁对覆盖准则、全序列覆盖准则等。

（1）状态覆盖准则：要求测试用例必须覆盖所有的状态。

（2）状态变迁覆盖准则：要求测试用例必须满足规格说明中每个前置条件。

（3）状态变迁对覆盖准则：要求测试用例必须覆盖每个相邻的变迁对。

（4）全序列覆盖准则：要求测试必须覆盖所有可以进入状态的组合序列[2]。

第1种覆盖强度最弱，只覆盖状态。第2种包含状态覆盖。第3种主要检查状态之间的接口。第4种执行所有可能执行的路径，但对于包含回路的状态图，全序列覆盖则是无限的，实际测试中往往只考虑循环次数为0、1和2的情况。从图的角度来划分，也将覆盖准则划分为节点覆盖、边覆盖、边对覆盖、主路径覆盖等。

对于UML状态图，选择不同覆盖准则会得到不同的测试需求，最终会得到不同的测试路径。分别读取图中的状态、迁移、迁移对和状态序列，得到与覆盖准则相应的测试需求。

2 基于UML状态图的测试路径生成方法

本文主要研究基于UML状态图生成列控中心软件测试路径，主要包括以下步骤：（1）基于列控中心需求规范恰当建立UML状态图模型；（2）提取UML状态图状态、转移、区域等信息，根据信息将UML状态图模型转化为有向图；（3）根据有向图各种覆盖准则生成相应测试需求；（4）结合有向图和测试需求生成测试路径。

2.1 UML状态图模型转化为有向图

状态图转化为有向图是测试的常用方法。根据需求规范，建立UML状态图模型并获取与模型相对应的XML文件，提取模型的节点、转移条件、警戒条件以及约束等信息。图1所示为简单状态图的状态信息提取映射流程。

图1 简单状态图映射流程

利用状态图模型提取的元素信息生成有向图，将状态图中状态映射为有向图中节点，将状态转移映射为边。生成有向图的步骤为：

（1）创建状态映射哈希表，键是状态，值是整数；状态逆映射哈希表，键是整数，值是状态；创建状态转移表；实现状态图的哈希表存储。

（2）创建节点映射哈希表，键是整数，值是节点；节点逆映射哈希表，键是节点，值是整数；创建边映射表；实现哈希表信息到有向图的构建。

2.2 改进深度优先搜索（DFS）遍历图

深度优先搜索是一种回溯搜索算法，本文采用改进的深度优先搜索算法得出遍历初始节点到终止节点的路径集合。

深度优先搜索算法基本思想是任选图形G的一个顶点v作为起点，访问v，然后访问该顶点邻接的未被访问的一个顶点v’，再从v’出发，继续添加边到这条路上。当某顶点所有邻接顶点都已访问过，则回到已访问顶点序列中最后拥有未被访问邻接点的顶点w。再从w出发，继续尽可能多地添加边得到以w开始的未访问过的顶点序列。当所有已访问顶点的相邻顶点都已被访问时，结束搜索[4]。

通用的深度优先搜索算法是要遍历图的所有节点，在搜索过程中，得到的子路径不会有确定的起点和终点。而本文模型有明确的初始节点和终止节点，且任意状态都是从初始状态可达的，因此，从初始节点到终止节点必然存在路径集能够遍历所有节点。本文将深度优先算法（DFS）加以改进，搜索出从初始节点到终止节点遍历图中所有节点的路径集合P。具体算法流程如图2如示。

图2 改进深度优先搜索算法遍历图

（1）将初始节点入栈，标为入栈状态；

（2）查看栈顶节点是否有未访问且未入栈的可达邻接节点，若有，将该节点入栈，标为入栈状态；若无，该栈顶节点出栈，标为未入栈状态；

（3）若栈顶节点为终止节点，则整个栈为一条路径，输出整个栈，加入路径集合P；

（4）栈顶节点出栈；

（5）重复（2）～（4），直到栈为空。

2.3 贪心算法合并测试需求为超串

将覆盖准则确定的测试需求采用超串的思想加以处理，可以减少测试花费成本。设S1和S2是两个字符串，本文用＜S1，S2＞来表示S1的后缀和S2的前缀之间重叠的最长字符序列，用S1,2表示S1和S2公共超串。贪心算法是用来构造最短公共超串的重要方法。贪心算法就是指逐步加入重叠覆盖程度最大的两个字符串Si和Sj，将其合并成Si,j，直到所有子字符串连接成一个超串[5]，如：

计算重叠字符序列和超串为：

则P1,P2,P3最短公共超串为：

同理，将测试需求集合（TR）中每条测试需求看做一个子串，利用贪心算法尽可能多地连接子串，求得连接子串最多的公共超串，得到连接后的测试需求集合TRS。

2.4 测试路径生成

由生成超串后的测试需求集合（TRS）和覆盖所有节点的路径集合P得到最终测试路径集合TP。取TRS中第i个子路径tri（tri∈TRS），查找包含子串tri首节点的路径Pm（Pm∈P）和包含tri尾节点的路径Pn（Pn∈P），用路径Pm中从初始节点到tri首节点的部分扩展tri，用路径Pn中从tri尾节点到终止节点的部分扩展tri,得到一条完整测试路径。假设：

若Vi=Vmi，Vj=Vnj；

得到完整的测试路径为：

将TRS中所有子路径扩展完毕，删除冗余路径，得到最终测试路径集合。具体算法流程如图3所示。

图3 测试路径生成流程

3 改变区间运行方向功能测试路径生成

根据列控中心技术规范，以改变区间运行方向功能为例，建立UML状态图模型并且提取与模型相对应的XML文件，通过对文件的解析提取模型信息，实现从模型到测试路径的生成过程。

3.1 列控中心改变区间运行方向功能

改变区间运行方向功能主要涉及正常改变运行方向和辅助改变运行方向，以及改变区间运行方向时异常情况处理。

（1）正常改变区间运行方向时，原接车站TCC收到本站CBI发车请求和锁闭信息后，检查条件满足，则向对方站发送请求改变运行方向信息；对方站条件满足且驱动相应方向继电器动作到位，向原接车站发送允许改变运行方向信息；原接车站收到允许改变运行方向命令，驱动相应方向继电器动作到位，向CBI发送允许发车信息，CBI控制出站信号机开放，改变运行方向成功。

（2）区间轨道电路故障占用则办理辅助改变运行方向。两站值班员确认轨道电路故障且区间空闲，由原接车站值班员按下相应按钮， CBI向TCC发送发车辅助办理请求，确认条件满足，向原发车站TCC发送辅助改变运行方向请求；原发车站值班员按下相关按钮， TCC接到辅助改变运行方向请求和辅助接车命令，检查条件满足，驱动方向继电器动作到位，向对方站发允许辅助改变运行方向信息；原接车站收到信息后，驱动方向继电器动作到位，辅助改变运行方向完成[6]。

3.2 改变区间运行方向功能状态图模型

利用Eclipse平台的UML建模工具Papyrus建立改变区间运行方向功能模型，如图4所示。

图4 改变运行方向状态图模型

主要过程如下：

（1）列控中心启动后，进行方向初始化，若本站方向继电器为接车状态或邻站为发车状态，则初始化为接车方向（RS）；若6 s未接收到邻站方向信息或本站方向继电器处于未知状态，也初始化为接车方向（RS）；当本站方向继电器为发车状态且邻站为接车状态，则初始化为发车方向（DS）。

（2）接车状态时，若收到本站CBI发车请求和发车锁闭信息，且站间空闲、本站无接发车进路、对方站无发车进路等条件满足，则转到正常接车转换准备状态（RN）；若不满足则仍处于RS状态。

（3）若在RN状态时，收到对方站允许改变运行方向命令，则转换到正常接车转换状态（RNC），若未收到允许命令则转回RS状态。

（4）对于RNC状态，若相应方向继电器转换到位则进入发车状态（DS），若13 s无法确认方向继电器转换到位则仍转为接车状态（RS）。

（5）对发车状态（DS），若收到对方站正常改变运行方向请求，且检查站间空闲、未办理发车进路，则进入正常改变发车转换状态（DNC）。

（6）对DNC状态，若13 s内确认方向继电器转换到位，则进入接车状态（RS）；否则，仍转为发车状态（DS）。

对于区间轨道电路故障占用而不能正常改变运行方向时，办理辅助改变运行方向，过程相似。

3.3 改变区间运行方向模型测试路径生成

基于以上算法进行程序实现，以状态变迁覆盖准则为例，得到如下6条测试路径。

Method of software test paths generation for train control center based on UML state chart diagram

WANG Xiuxuan
( School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China)

Aiming at testing train control center (TCC),this article introduced the method of test paths generation for TCC based on UML state chart diagram.The UML state chart diagram model was established on the requirement specifcation of TCC.An improved Depth First Search (DFS) Algorithm was used to automatically search the directed graph,and get all paths from the initial node to the end node.The Greedy Algorithm was used to construct the test requirement of super string merging,and the path set was used to extend test requirements set.Finally,the automatic generation of test path was implemented.Taking changing running direction in sections of TCC for example,the implementation of test path generation method was given.

test paths;UML state chart diagram;train control center (TCC);depth frst search;super string

U284.48：TP39

A

1005-8451（2016）08-0009-05

2016-01-12

王秀玄，在读硕士研究生 。