铁路信号安全协议互操作性测试序列生成研究

王 瑞，梁 艳

（1.中国铁道科学研究院 通信信号研究所， 北京 100081 2.卡斯柯信号有限公司 城交部，北京 100045）

高速铁路列车运行控制系统，其系统内部、系统与外界环境之间存在大量复杂的数据交互，这就依赖于高容量的传输系统进行数据传输[1]。其中，铁路信号安全协议-I（以下简称RSSP-I）为铁道部制订的用于列控系统封闭网络中的安全数据传输协议，是保证信息安全实时传递的有效手段，对整个系统安全起着重要作用[2]。

在协议实现投入运行之前，对其进行完整的测试可以保证协议有效安全地投入应用。协议测试包括一致性测试、互操作性测试、性能测试和鲁棒性测试，其中的互操作性测试就是检查同一协议或者同一类协议的不同被测实现之间是否可以进行正确的交互，提供期望的服务，它是对一致性测试的完善和补充。

自然语言描述的协议说明可能具有二义性或者存在可选选项，一致性测试无法做到穷尽测试，故对产品进行互操作性测试是必要的[3]。在不同厂家的产品之间进行互操作性测试，可以降低系统集成的费用，提高设备的利用率，保证系统的良好运行。

1 互操作性测试的形式化模型

为了生成协议的互操作性测试序列，需要对协议说明进行形式化建模，可以用有限状态机对协议的行为进行形式化描述。有限状态机FSM，M是一个五元组(S, s0, Lin, Lout, Tr)[4]，其中：

（1）S=(s0, s1, …sn-1)表示状态机M的状态集合；

（2）s0∈S表示状态机M的初始状态；

（3）Lin=(v1, v2, …wm)表示输入符号的集合；

（4）Lout=(U1, U2, …Uk)是输出符号向量的集合，其中Ui=(uex, uin) ，uex表示外部输出消息，uin表示内部输出消息；

（5）Tr U?{s－v/U→s'|s, s'∈S∧v∈L∧inU U?L}表示变迁的集合，其中s，s'，v ，U 分

out别表示起始状态，终止状态，输入符号，输出符号的集合。

互操作性测试把参与测试的两个或者多个实现作为整体考虑，采用组合的有限状态机对被测协议从整体上进行形式化描述，本文中研究的是1:1的互操作性测试，用II表示2个有限状态机的组合：MA和MB。可以这样定义，组合的有限状态机II是一个五元组(SII, sII,0, sII,in, LII,out, TrII)[4]：

（1）SII=(sII,0, sII,1, …sII,n-1)表示全局状态的集合，sII,i=(sA, sB), sA和 sB分别表示 MA和MB的状态。

（2）sII,0∈SII表示初始状态，即sII,0=(sA,0,sB,0) 。

（3）LII,in=(vII,1, vII,2, …vII,m)表示输入符号的集合，即，LII,in=(Lin,A,EULin,B,E) 。

（4）WII=(UII,1, UII,2, …UII,l)表示由一个外部输入所产生的一系列输出符号向量的集合，UII,i∈Lout,A∪Lout,B, UII,i+1是由UII,i的内部输出产生的，其中1≤i ≤l，并且最后一个向量UII,l的内部输出为空，或者虽然内部输出不为空，但也不会引起状态的变迁。 LII,out=(WII,1, WII,2, …WII,k)是一系列输出符号向量的集合。

（5）TrIIsII－v/U→sII'|sII, s'∈S∧IIIIIIIIIIIIII

v∈LII,in∧UU?LII,out}表示变迁的集合。

2 互操作性测试序列的生成算法

本文的互操作性测试生成算法中，主要基于单激励原则，即被测系统在同一时刻只有一个外部激励，且在系统处于稳定状态时给入，只有当被测系统处理完该激励时，外部才能输入下一个激励。同时，还假设要进行互操作性测试的被测实现已经经过了一致性测试[5]。

组合的有限状态机的生成算法可以产生互操作性测试套，对给定输入存在多少信息交互，或对同一输入存在多少变迁都普遍适用。该算法中，首先要做全局变量的初始化工作：LII,in=(Lin,A,EULin,B,E)，sII,0=(sA,0, sB,0)，SII={sII,0}, TrII:={}。然后，从组合的有限状态机的初始状态States（初始化为sII,0）开始，通过函数choose-any()从States中任选一个状态gs_i作为当前状态，对于gs_i的每一个外部输入v，求出当前状态在输入v时的下一个状态gs_f，从而求得新的输出LII,out和TrII。把新状态gs_f并入SII和States中，可以得到新的状态集SII和States。为了得到gs_i和gs_f的内部交互序列，引入子函数interoperabilityderive (in, s, s', gs_i, v,W )，它是一个递归调用的函数，能够生成一个互操作性测试例。其算法流程图如图1所示。

图1 组合的有限状态机的生成算法流程图

3 RSSP-I协议的形式化模型建立

RSSP-I规定了铁路信号安全设备之间进行信息交互的安全层功能结构和协议，实现数据通信，适用于封闭式传输系统。该协议依照封闭式传输系统安全通信标准 EN50159-1制定，采用从接收方角度设计的保护算法，能够独立检测通信传输中的所有错误，采取相应的故障安全防范措施。

RSSP-I协议中用了3种数据帧：RSD（实时安全数据帧），SSE（时序校正请求帧）和SSR（时序校正应答帧），其安全数据交互示例如图2所示。

图2 RSSP-I安全数据交互示例

为生成RSSP-I的互操作性测试序列，需要建立该协议的发送方和接收方的有限状态机模型。由于RSSP-I协议是基于接收方的保护算法，发送方是主动的，而接收方作为跟随方是被动的，通信链路的建立和删除过程都是由发送方决定的。因此，本文在建立模型时，为发送方设计比较多的外部输入，而接收方只有内部输入，完全跟随发送方。

首先，需要确定发送方和接收方的状态机集合。发送方模型的状态集：S1={IDLE , WaitSSE ,DelaySSR, DATA }， 其中，IDLE表示链路不存在或者已删除，默认的初始状态；W aitSSE表示等待接收方的时序校正请求SSE；DelaySSR表示本方延迟发送时序校正应答SSR；DATA表示发送实时安全数据帧RSD；建立接收方模型的状态集S2={IDLE, READY , WaitSSR, DATA }。

在触发发送方模型和接收方模型的状态转化过程中，需要有相应的输入/输出事件。其中外部输入包括：Setup1正常启动发送方；Setup2启动发送方异常（不能及时发送SSR）；Conn链路连接正常；Disconn断开链路、SSRTim eout发送SSR超时；RSDDelay发送RSD延迟等。外部输出包括：Start状态机启动；C losed链路断开，回到初始状态；D isp lay被测设备将一些发送接收数据，状态的变化等显示出来，方便测试者查看。内部的输出包括：i_RSD发送RSD；i_SSE发送SSE；i_SSR发送SSR；i_RSDe发送错误的RSD；i_RSDd发送延迟的RSD；i_tim eout（i_timeout1，i_timeout2）分别表示超时时间t（t1，t2）、nu ll（输出为空）；同时一个状态机的内部输出事件是另外一个状态机的内部输入事件，用来触发相应的变迁。

本文建立的发送方模型、接收方模型如图3和图4所示。

图3 RSSP-I发送方模型

4 RSSP-I协议的互操作性测试序列生成

在对RSSP-I协议进行互操作性测试的研究中，采用前面的互操作性测试套生成算法，图5以一个RSSP-I协议中的交互实例来说明互操作性测试套的生成过程。

最开始，发送方和接收方都处于初始状态，即：States ={（IDLE, IDLE）}。图6介绍了图1中的算法生成互操作性测试例的过程。

于是，就生成了第（1）条测试例，用同样的方法可以生成下面11条互操作性测试例：

图4 RSSP-I接收方模型

图5 一个消息交互的例子

图6 测试例（1）生成的具体过程

（1）（IDLE,IDLE）—Setup1/(Start, i_RSD),(Display, i_SSE),(Display, i_SSR),(Display, null) →（DATA,DATA）；

（2）(DATA,DATA)—RSDError/(Display, i_RSDe),(Display, i_SSE),(Display, i_SSR),(Display,null) →（DATA,DATA）；

（3）(DATA,DATA)—RSDDelay/(Display, i_RSDd),(Display, i_SSE),(Display, i_SSR),(Display,null) →（DATA,DATA）；

（4）(DA TA,DA TA)—Conn/(D isp lay,i_RSD),(Display, null) →（DATA,DATA）；

（5）(DATA,DATA)—D isconn/（C losed,i_timeout），（Closed, null） →（IDLE,IDLE）；

（6）(IDLE,IDLE)—Setup2/(Start, i_RSD),(Display, i_SSE),(Display, i_timeout1),(Disp lay, null)→（DelaySSR, WaitSSR）；

（7）（DelaySSR, WaitSSR）—Disconn/(Closed,i_timeout2),(Closed, null) →（IDLE,IDLE）；

（8）（DelaySSR, WaitSSR）—SSRNormal/(Display, i_SSR),(Display, null) →（DATA,DATA）；

（9）（DelaySSR, W aitSSR）—SSRTimeout/(Display,i_timeout2),(Closed, null) →(WaitSSE,IDLE);

（10）(WaitSSE, IDLE) —Conn/(D isp lay,i_RSD),(Display, i_SSE),(Display, i_SSR),(Display,null) →(DATA,DATA);

（11）(W aitSSE, IDLE) —Disconn/(Closed,i_timeout),(Closed, null) → (IDLE,IDLE)。

变迁分别叫做 T1，T2，T3，T4，T5，T6,T7，T8，T9，T10，T11。可以生成组合的有限状态机如图7所示。在组合的有限状态机模型基础上进行对称扩展，得到欧拉图如图8所示。

图7 RSSP-I组合的有限状态机模型

图8 RSSP-I组合的有限状态机的对称扩展

对其进行欧拉遍历，可以得到最佳的测试序列为：T1’→ T5 →T6→ T9→T10’→ T2’→T3’→ T4→ T5→T6→T9’→T11’→T6 →T8’ T5’→ T6’→ T7’。

该测试序列覆盖了所有变迁，并且对每个变迁的末状态都做了检查，具有很高的错误覆盖率，序列长度在可接受的范围内保证了测试的工作量不大并具有可执行性，可以将其描述为抽象测试套，用于本协议的互操作性测试中。

5 结束语

本文介绍了互操作性测试序列的生成算法，基于该算法对RSSP-I协议进行了互操作性测试的生成研究，最后得到了其互操作性测试序列。但本文在生成测试序列时所基于的单激励原则有一定的局限性，在下一步的研究工作中，需要采用多激励原则生成互操作性测试序列，多激励原则即从外界环境可以同时向两个实现输入外部消息，它更为复杂，却更加接近实际情况。另外，在序列生成算法上也有可以改进之处[6~7]，以达到更高的错误覆盖率和更短的序列长度。

[1] 杨世玉，徐中伟.铁路信号安全协议一致性测试序列生成研究[J].计算机工程与应用，2010，46（34）：59-61.

[2]铁路信号安全协议-I（报批稿）[S]. 北京全路通信信号设计院，2009.

[3]李 华，叶新铭.协议互操作性测试综述[J].内蒙古大学学报，2008，39（5）： 590-595.

[4] Seol S，Kim M，Kang S,et al．Fully automated interoperability test suite derivation for communication protocols[J]．Computer Networks, 2003, 43(6):735-759.

[5]张 涛.边界网关协议BGP4+的互操作性测试研究[D].包头：内蒙古大学，2007.

[6] 王之梁，吴建平，尹 霞.基于通信多端口有限状态机的协议互操作性测试生成研究[J].计算机学报，2006，29（11）：1909-1919.

[7] 林华辉，赵保华，屈玉贵.基于有向图的最小完全覆盖互操作测试序列生成算法[J].中国科学技术大学学报，2006（2）：225-229.