铁路信号系统软件测试建模方法

李 耀 ，张晓霞 ，郭 进 ，张亚东

（1. 电子科技大学光电科学与工程学院, 四川 成都 611731；2. 西南交通大学信息科学与技术学院, 四川 成都611756）

截止2019年底，我国高速铁路营业里程已达到3.5万公里，位居世界第一. 我国已成为世界上高铁运营里程最长、运输密度最高、运营场景最复杂的国家. 铁路信号系统软件测试是保障高铁信号系统安全运行的重要方法，能够有效地预防列车追尾和出轨等行车事故，避免造成人员伤亡及重大财产损失[1]，对保障我国高铁的安全运行具有重要意义.

目前，高铁信号系统软件测试的研究热点之一为基于形式化模型的测试案例自动编制方法，其首先建立软件的测试模型，然后研究算法自动生成满足特定目标的测试案例. 铁路信号系统软件测试中常用的建模方法包括UML状态图（UML statechart）、时间自动机（timed automata，TA）和有色Petri网（colored Petri net，CPN）等. 文献[2]以CPN为测试建模理论基础，以无线闭塞中心切换功能为例，研究基于全路径覆盖和序列优选的测试案例自动编制方法，降低测试案例的重复度. 文献[3]以CTCS-3（Chinese Train Control System 3）级ATP （automatic train protection）设备模式转换功能为例，基于CPN建模理论，解决状态空间爆炸等问题，生成满足全路径覆盖准则的测试序列. 文献[4]以TA为基础进行测试建模，提出一种满足全状态和全变迁覆盖准则的测试案例生成方法，提高测试案例的生成效率和重用性. 文献[5]研究CTCS-3故障特点，提出了一种基于输入输出时间自动机变异模型的测试案例生成方法. 文献[6]以轨道电路编码功能为研究对象，提出图覆盖、组合覆盖和文法分析相结合的方式自动从UML状态图模型生成测试案例. 文献[7]以UML顺序图为研究基础，利用深度优先算法和网络组合算法对计算机联锁系统测试案例进行组合优化，降低测试案例的重复度. 文献[8]针对铁路信号系统软件的测试度量方法，提出对信号系统软件进行风险分级，按照风险等级递减顺序进行安全性测试的测试策略，指出了以铁路信号系统软件风险等级为基础测试的必要性. 文献[9]对CTCS-3系统安全软件进行接口危险辨识，评估危险事件的风险等级，提出列控系统安全软件黑盒测试的危险分析方法，但未对软件测试建模理论进行研究. 文献[10-12]针对铁路信号系统的形式化描述和验证，分别从时钟约束、风险等级和安全约束等几个方面提出铁路信号系统的建模方法，但这些方法结构复杂，测试模型解析和测试案例搜索算法难以展开，不易直接应用于铁路信号系统软件测试建模.

目前，铁路信号系统软件测试的研究重点是如何以既有的测试建模方法为基础生成覆盖全面且高效的测试案例，研究提高了测试活动的自动化程度和测试效率. 但现有测试建模方法不能完整地描述软件所有的行为特征，如UML状态图和CPN等方法不能描述软件的时间约束，导致测试案例不能反映软件的时间特性. TA能够描述软件的时间约束，但不具有层次结构，对复杂功能逻辑的描述能力较差，容易出现模型难以理解，甚至错误的问题. 同时，UML状态图、CPN和TA等方法均不能描述软件测试模型中的风险特性.

本文通过分析铁路信号软件的领域特点，总结铁路信号软件测试的建模需求，结合Z规格说明语言（简称Z语言）提出风险时间状态机建模方法，满足铁路信号软件测试的建模需求.

1 建模概述

铁路信号系统软件测试通常采用基于模型的测试（model-based testing，MBT）[13]理论，主要包括分析软件需求、建立测试模型、生成测试案例和执行测试4个阶段，如图1所示. 首先，基于被测软件的需求规格等文件对软件功能和结构进行抽象，采用形式化建模方法建立软件的测试模型；然后，依据测试模型，采用“平坦化”和状态组合等方法对测试模型进行解析，通过广度优先等搜索算法自动生成测试案例；最后，将测试案例加载到测试环境中执行测试，观察测试结果.

图1 铁路信号系统软件测试主要过程Fig. 1 Main testing process of railway signal system software

测试模型是编制测试案例和评判测试结果时的重要依据，直接关系到软件测试过程的全面性和有效性，铁路信号软件测试建模方法需要尽可能系统、全面地描述铁路信号系统软件的所有需求.

2 建模需求

铁路信号系统软件测试建模包括功能建模需求和性能建模需求两个方面. 功能建模需求描述系统的功能逻辑（function logic），性能建模需求指与系统相关的性能约束或限制，包括时钟约束（clock constraint）和风险等级（risk level）两个方面.

1） 功能逻辑

随着铁路信号系统的规模越来越大，软件承担的功能越来越多、逻辑越来越复杂. 如CTCS-3级列控系统包括9种工作模式，14个主要运营场景，206个功能特征. 铁路信号系统已构成一个复杂的控制系统，软件存在着大量的并发、竞争、冲突等逻辑关系，控制状态转移条件复杂.

2） 时钟约束

铁路信号系统软件运算结果的正确性不仅取决于系统逻辑处理的正确性，还取决于运算过程中的时钟约束，要求软件功能需要在指定时间内完成，或在规定时限之后才能发生. 如《CTCS-3级列控系统总体技术方案》[14]要求“当列车前端距分相区还有10秒走行距离时，车载设备向司机发出提示”. 铁路信号系统软件的时钟约束通常为硬实时性（hard real-time）要求，如道岔转换时间、移动授权有效时间、目视模式确认时间等，时钟约束错误或缺失，可能造成重大安全事故.

3） 风险等级

铁路信号系统软件由安全功能（safety function）、安全相关功能（safety-related function）和非安全功能（non-safety function）组合构成. 如 《CTCS-3级列控系统测试案例（V3.0）》[15]的功能特征CTCS3-FT-71“由于超速触发紧急制动”属于安全功能，功能特征CTCS3-FT-116“记录数据的下载”属于非安全功能. 不同安全级别的功能对系统造成的安全影响差别较大，由风险等级进行描述. 风险等级的高低是铁路信号系统软件测试案例编制的重要基础，对组织测试案例优先级及分析测试需求具有重要意义.

根据以上分析，铁路信号系统软件测试建模方法需要描述系统复杂的功能逻辑、时钟约束和风险等级3个方面的特点，严密、准确地反应软件测试需求，且具有良好的可读性和可理解性.

3 风险时间状态机

为定义风险时间状态机建模方法，首先介绍有限状态机（finite state machine, FSM），然后在FSM基础上，结合Z语言，在迁移元素中扩展出时钟约束，在状态元素中扩展出风险等级，最后给出风险时间状态机的定义.

3.1 有限状态机概述

FSM采用可视化的方式描述系统的功能逻辑，具有清晰、直观的优点，其是表示有限状态以及状态之间转移和动作等行为的数学模型，具有精确性、可推导性和可验证性，是基于模型的测试理论中的经典建模方法[13-16].

定义1一个有限状态机M是一个六元组，如式（1）[17].

式中：

S为有限状态集合；

s0为初始状态，且s0∈S；

λ为状态转移函数，λ:S×I→S；

δ为输出函数，δ :S×I→O；

I为有限输入符号集合；

O为有限输出符号集合.

图2为一个FSM模型，包括s1和s2两个状态，其中s1为初始状态，A、B、C为输入，a、b、c为输出.s1接收到输入A时输出a，转移到s2状态. 模型对应的六元组如下：

图2 有限状态机模型Fig. 2 Example of finite state machine

接下来结合Z语言，在FSM描述功能逻辑基础上，增加层次结构，扩展出时钟约束和风险等级两个参数，提出风险时间状态机（risk timed statechart，RTSC）. 为描述方便，首先定义RTSC的基本元素，然后定义RTSC的层次结构，最后给出RTSC的形式化定义.

3.2 RTSC的基本元素

RTSC包括状态、时钟、信号表达式和迁移等基本元素.

1） 状态

状态是铁路信号系统软件在一定时期内的存在形式. 对RTSC的非空、有限状态集合S，Z语言描述如下：

状态包括简单状态（SIMPLE），或状态（OR）和与状态（AND）3种类型，Z语言描述如下：

OR状态由同一层次的状态和迁移组成，包含且仅包含一个初始状态. 初始状态无源状态，且是任意状态的源状态. 多个并发的OR状态组成AND状态.

2） 时钟

RTSC采用时钟描述时间的流逝，有限时钟集合记为X，Z语言描述如下：

对一个时钟变量集合X，时间约束集合定义如式（2）.

式中：σ1、σ2为时钟约束；x∈X；g∈N ；∝∈{≤,<,≥,>,=}.

RTSC时钟约束Σ的Z语言描述如下：

3） 信号

信号E具有产生和不产生两种状态，Z语言描述如下：

在某一时刻，正交组件产生的信号称为动作.

4） 信号表达式

信号之间的与（and）关系、或（or）关系、非（not）关系构成信号表达式，记为ex如note表示未产生信号e.

用Π为表示信号永远发生的常量.

5） 迁移

迁移是RTSC从源状态转移到目标状态的方式，包括源状态sc、时钟约束σ、信号表达式ex、转移时产生的信号e、重置的时钟x及目标状态st. 迁移的Z语言描述如下：

3.3 RTSC的层次结构

RTSC的状态层次H包括底状态γ、为状态分配子状态的有限状态层次函数ω，定义状态类型的有限状态类型函数κ，定义状态父状态的ρ函数.H满足以下性质：

1）ω为非SIMPLE类型的状态分配子状态；

2） 状态之间的层次关系不能形成循环结构；

3）γ为OR状态或AND状态，是唯一没有父状态的状态；

4） 任意非γ的状态都具有唯一的父状态，且均可以由γ通过ω传递到达.

H的Z模式定义如下：

其中：FS表示集合S的所有有限子集的集合；domω表示ω的定义域；ranρ表示ρ的值域；∀si:domρ;sj: domω表示ρ定义域中的任意状态si和ω定义域中的任意状态sj，i，j为不为0的自然数，且i≠j.

RTSC由状态层次和迁移集构成，采用风险等级函数η为SIMPLE状态分配风险等级，满足以下性质：

1）η仅为SIMPLE状态分配风险等级；

2） OR状态和AND状态的风险等级为其包含的子状态的风险等级的最大值.

3） 对任意迁移，只能有一个同层次的源状态和目标状态，源状态和目标状态可以是AND或SIMPLE状态.

RTSC的Z模式定义如下：

其中：F1T表示集合T的所有非空有限子集的集合.

4 RTSC的格局转移机制

4.1 格局

一个时钟集合X的时钟解释v是指每个时钟变量x到时间序列上的一个全映射. 某时刻，RTSC能够同时处于最大的状态集结合当前的时钟解释称为格局（configuration），记为U. 在任意时刻，RTSC只有一个活动的格局，满足以下规则：

1）U包含γ状态；

2）U包含AND状态s，则U包含s的每一个子状态；

3）U包含OR状态s，则U包含s的某一个子状态；

4）U包含非γ的状态s，则U包含s的父状态；

5）U仅包含满足规则1） ~ 4）的所有状态.

格局公理描述如下：

其中：k表示不为0的自然数.

4.2 格局转移机制

RTSC格 局 转 移 过 程 记 为 (us,v(X),E)，其 中us表示当前格局包含的状态集，v(X)表示时钟解释，E表示转移过程中产生的动作集，具体过程如下：

1） 激励. 当RTSC接受到新的时钟解释或信号时开始格局转移：(us,v(X),∅)→(us,v′(X),e).

2） 计算. 格局转移过程以SIMPLE状态为基础，从γ状态，通过OR状态和AND状态向下分解，包括以下2个规则：

规则1AND状态并行地计算其所包含的OR状态的转移.

规则2OR状态计算当前激活的SIMPLE状态的变迁t上的信号，产生t上的动作，重置t的时钟，离开变迁源状态τ.sc到达变迁状态t.st，满足：us=us .sc∪t.st，G=G∪t.e，v(t.x)=0.

3） 结束. RTSC根据状态类型迭代相应规则直至转移稳定，保留时钟解释，清空转移期间的信号.

RTSC从初始格局开始，根据产生的信号或时钟的更新激活格局转移过程；依据层次结构，迭代AND状态和OR状态的规则，直到计算出下一组稳定的状态. 格局转移时，迁移的触发信号均发生，且时钟解释满足迁移上的时钟约束，同时产生迁移上的动作，重置迁移上的时钟变量.

4.3 RTSC的操作语义

RTSC的语义可以由其对应的时间标记迁移系统（timed transition system，TTS）进行定义.

定义2一个时间标记迁移系统TTS是一个4元组：

式中：L为状态集合；

l0为初始状态，l0∈L；

→⊆L×(Σ∪R)×L为转移关系，且满足：1） 如果，则l=l′； 2） 如果，且，d,d′∈R，则； 3） 如果则0 ≤d′≤d，则有l′′∈L，满足且

在时钟解释v下，如果时钟约束σ为真，则称时钟解释v满足时钟约束σ，记为v|=σ.

定义3对任意RTSC，其语义可以通过时间标记迁移系统 Ω=(L,l0,→,Σ)进行定义，其中：

l0=(us0,v0) ，us0为RTSC的初始状态集，且对任意x∈X，v0(x)=0；

转 移 关 系 → 满 足：1） 对 (us,v)和 一 个 迁 移且v|=σ ，则对和时间增量

RTSC从初始格局开始，通过动作转移或时延转移实现格局变化.

1） 动作转移. 当前激活的信号和时钟解释满足变迁的信号表达式和时钟约束，触发动作迁移，激活变迁上的动作，重置变迁时钟为0.

2） 时延转移. 时延转移保持格局状态不变，对所有时钟增加相同的时间增量.

5 案例分析

计算机联锁系统是铁路信号系统中典型的安全关键系统. 以计算机联锁系统的道岔定位选排子系统为例建立RTSC测试模型，解释RTSC的格局转移机制.

5.1 基于RTSC的道岔转换测试模型

道岔定位选排子系统根据道岔操作命令或进路请求，检查道岔当前是否处于定位. 当道岔状态与期望不一致时，选排道岔到需求位置[18]. 该系统涉及11个信号，主要信号名称及其含义见表1.

表1 道岔子系统信号含义Tab. 1 Meaning of signals in switch subsystem

道岔定位选排子系统的RTSC模型如图3所示，记为DRTSC，其中ranη= {0, 1, 2, 3, 4}，分别对应EN 50128定义的5个安全完整度等级SIL 0～4.DRTSC包括1个时钟x1，最高风险等级为SIL 4，最低为SIL 2，底状态为s0，初始状态为 {s3,s4,s5,s6,s9,s11}，s1、s2、s3分别为SIMPLE状态、AND状态和OR状态 ，η (s1)=4 ，η (s3)=max(η(s6),η(s7),η(s8))=4，ρ(s2)=s0，ω(s2)={s3,s4,s5}.

图3 道岔子系统RTSC模型Fig. 3 RTSC model of switch subsystem

DRTSC中：迁移的表现形式为[e] [σ] / [a] [x]；e为触发转移的信号；σ为时钟约束；a为转移时产生的动作；x为重置的时钟，记为. 如表示状态s14激活时，当检测到信号e7，并满足时间约束x1<13，DRTSC迁移到s13，同时产生信号e8，并重置时钟x1.

5.2 DRTSC格局转移

DRTSC模型中，s3、s4、s5分别表示道岔转换的“安全请求”，“道岔转换”和转换的“时钟约束”状态.DRTSC主要描述以下过程：

道岔“安全请求”状态检测到定位需求后，在道岔未锁闭、无反位请求、未处于定位时，进一步检查道岔转换状态，未处于转换过程中或转换超时时，判定定位请求安全. “道岔转换”状态接受到“定位请求”信号后，如果道岔未锁闭则重置时钟x1；条件保持1 s后，请求道岔转换. “时钟约束”状态接受道岔转换动作后，重置时钟x1并开始计时，13 s内检测到道岔转换到定位则转换成功，否则转换超时. 当“道岔转换”状态接受到“时钟约束”状态的“转换成功”信号后判定道岔转换成功. 当同时处于“定位请求”和“转换成功”状态时，判定“选排一致”. 转换过程中任意时刻，道岔子系统接受到反位请求信号立即重置时钟，返回初始状态.

DRTSC的初始格局为 ((s0,s2,s3,s4,s5,s6,s9,s13),(0)) . 下面以格局 ( (s0,s3,s4,s5,s8,s11,s14),(2))，产生信号e7，v(x)=3为例，分析DRTSC的格局转移过程.

1）DRTSC接受激励信号和更新的时钟解释：((s0,s2,s3,s4,s5,s8,s11,s14),(2),(∅))→ ((s0,s2,s3,s4,s5,s8,s11,s14),(3),(e7)).

2） 由于s0为OR状态，根据规则 2，s0当前激活状态为s2.s2为AND状态，根据规则 1，s2并行计算s3,s4,s5，计算过程为

e7和v(x)=3 满 足s14迁 移 到s13的 信 号 表 达 式和时钟约束，迁移时重置时钟x1，同时产生信号e8: ((s0,s2,s3,s4,s5,s8,s11,s14),(3),(e7))→((s0,s2,s3,s4,s5,s8,s11,s13),(0),(e7,e8));

e8信号触发s4的子状态s11，并转移到状态s12：((s0,s2,s3,s4,s5,s8,s11,s13),(0),(e7,e8))→((s0,s2,s3,s4,s5,s8,s12,s13),(0),(e7,e8,e11));

s3的状态s8满足自迁移变迁：((s0,s2,s3,s4,s5,s8,s12,s13),(0),(e7,e8,e11))→((s0,s2,s3,s4,s5,s8,s12,s13), ( 0),(e7,e8,e11,e1)).

s3，s4和s5计算结束后，DRTSC激活的信号包括 (e7,e8,e11,e1) ，激活s2至s1的迁移：((s0,s2,s3,s4,s5,s8,s12,s13),(0),(e7,e8,e11,e1)).+→ ((s0,s1),(0),(e7,e8,e11,e1)).

3） 计算结束，DRTSC格局更新为 ( (s0，s1),(0)).

根据以上分析，DRTSC格局转移过程记为表示道岔在处于“定位安全请求”，“道岔转换”，“道岔转换计时中”状态时，检测到道岔在第3 s转移到定位，判定道岔选排一致.

5.3 DRTSC模型分析

DRTSC描述了道岔定位转移过程中的功能逻辑、时钟约束和风险等级.

5.3.1 测试需求覆盖

1） 功能逻辑

DRTSC采用16个状态，19条迁移和11个信号描述道岔转换过程的功能逻辑.

2） 时钟约束

DRTSC通过时钟x1描述道岔转换过程中信号保持时间1 s和转换超时判断时间13 s，包括时钟约束x1>1，x1<13和x1≥ 13. 如描述道岔转换超过13 s后进入超时状态s15.

3） 风险等级

DRTSC描述了道岔转换过程中风险等级的变化情况，包括风险等级升高、降低以及保持不变，风险转移矩阵如图4所示. 其中，正数表示风险等级升高，负数表示风险等级降低，0表示风险等级不变，“−”表示状态之间无转移关系.

图4 道岔子系统风险矩阵Fig. 4 Risk matrix of switch subsystem

如R78= 1描 述 了 迁 移(s8,4)，表示道岔由SIL 3的状态s7转移到SIL 4的s8，风险等级升高1个等级，软件测试时需要重点对此类变迁进行测试.

5.3.2 与TA对比

为检测RTSC模型的描述能力，选取铁路信号系统软件测试中广泛采用的TA建模方法进行对比.道岔定位选排的TA模型如图5所示，记为DTA.DTA由4个TA构件组成TA网络实现道岔定位选排的测试需求，其中，为描述DRTSC的否定信号，如未接收到信号e5，在DTA中增加en5.DTA和DRTSC均包括1个时钟，状态、变迁和信号数量方面的比较如表2所示，DRTSC比DTA节省62%的变迁数，节省54%的状态数. 其中，DRTSC的状态数为除去层次结构后的SIMPLE状态的数量.

图5 道岔子系统TA模型Fig. 5 TA model of switch subsystem

进一步，随机选取计算机联锁系统软件中的4个子功能，分别采用RTSC和TA进行建模，RTSC模型和TA模型在构件、状态和变迁3个方面的对比如图6所示.

图6 RTSC模型与TA模型对比Fig. 6 Comparison between RTSC model and TA model

通过表2和图6，相对TA建模方法，RTSC模型具有更少的构件数、状态数、变迁数和信号数. 且随着功能逻辑复杂度的增加，RTSC节省的状态数和变迁数越多，RTSC模型更为简洁、清晰，表达能力更强，可读性更高，适合描述铁路信号系统软件复杂的功能逻辑.

表2 DRTSC与DTA 对比Tab. 2 Comparison betweenDRTSC andDTA

RTSC继承了FSM可视化、直观和简介的特点，其状态转移、层次性和并发性能够描述软件的功能逻辑，时钟约束能够描述软件的时间关系，风险等级能够描述软件不同功能之间的安全性关系. 具体的，RTSC与铁路信号系统软件测试建模需求之间的关系如表3所示.

表3 RTSC与测试需求的关系Tab. 3 Relationship between RTSC and test requirements

6 结 论

1） 铁路信号系统软件测试建模方法不能很好地描述铁路信号系统软件测试的建模需求，不能同时描述软件的功能逻辑、时钟约束和风险等级3个方面的特征.

2） 以有限状态机理论为基础，扩展出时钟约束和风险等级属性，提出风险时间状态机建模方法，采用Z语言给出了风险时间状态机的定义，阐述了风险时间状态机的格局转移规则，满足铁路信号系统软件测试在功能逻辑、时钟约束和风险等级方面的建模需求.

3） 以计算机联锁系统中的道岔子系统为例，利用风险时间状态机建立了道岔子系统软件的测试模型，并选取TA建模方法进行对比，结果表明风险时间状态机描述能力更强.

4） 文章提出的方法已在计算机联锁系统的软件测试中得到应用，实践表明该方法能够满足铁路信号系统软件测试的建模需求，为铁路信号系统软件测试提供了形式化建模的理论基础.