一种针对全自动运行系统的测试用例生成方法

梁君海，李春峰，万 里，杨毅峰，薛一鸣

（1.中车成都机车车辆有限公司西南研发中心，成都 610511；2.西南交通大学信息科学与技术学院，成都 610097）

1 概述

随着社会经济的高速发展，轨道交通正向着智能和集约的方向迅速发展[1]，全自动运行系统（Fully Automatic Operation，FAO）已成为轨道交通领域的热点研究内容。全自动运行系统基于计算机、通信和系统集成等技术，对相关设备自动进行控制，实现列车运行全过程的自动化[2]。全自动运行系统是典型的安全关键系统（Safety-Critical System），系统逻辑复杂，规模庞大，一旦失效，影响巨大。因此，在投入运营前对全自动运行系统进行全面系统的测试具有重要意义。

文献[3]提出一种城市轨道交通全自动驾驶车辆仿真测试平台方案，以测试验证车辆在全自动运营场景和人工驾驶运营场景下的正常和故障工况。文献[4]以上海轨道交通10 号线为例，对列车休眠和唤醒场景进行了深入分析。文献[5]对城市轨道交通全自动运行系统进行介绍，以典型运营场景为例对全自动运营场景进行梳理，分析关键装备的功能需求以及各设备专业之间的接口关系。文献[6]结合国际标准研究全自动运行系统典型的系统功能与安全需求，对运营场景进行分析，对国内自主研发全自动运行系统提出参考建议。文献[7]分析了CBTC-RF 信号系统驾驶模式及模式间转换应遵循的原则。

目前，全自动运行系统的研究主要集中在系统方案和仿真分析，对测试用例生成方法的研究较少。时间自动机具有严格的数学定义，在轨道交通测试建模领域取得了广泛的应用[8-10]。本文结合全自动运行系统的特点，针对全自动运行系统测试用例生成过程中存在的指定路径覆盖的需求，基于时间自动机建模理论，提出全自动运行系统的测试用例自动生成方法，对全自动运行系统的安全性保障具有一定的意义。

2 时间自动机及UPPAAL介绍

时间自动机（Timed Automata，TA） 由Stanford 大学的Rajeev Alur 和David Dill 于20世纪90 年代提出。时间自动机对有限自动机进行了扩展，使用有限个时钟变量表示有时间约束的状态转换图，进而描述系统的实时行为[11-12]。

定义1 （时间自动机）TA 定义为一个六元组〈S,S0,Σ,X,I,E〉，其中：

S是有穷位置的集合；

S0是初始事件的集合；

Σ是有穷事件的集合；

X是有穷时钟的集合；

I是每个位置的映射，对s∈S指定Φ(x)中一个时间约束δ；

E⊆S×Σ×Φ(x)×2x×S表示位置转移的集合。

〈s,a,φ,λ,s'〉 表示输入动作a时，从位置s到s'的转移；φ是X上的一个时钟约束，在转移发生时被满足；λ∈X是在该转移发生时复位的时钟集合。

UPPAAL 是由瑞典Uppsala 大学和丹麦Aalborg 大学联合开发的针对TA 理论的建模、验证和测试用例生成工具。UPPAAL 拓展了TA 理论，扩展出变量和通道等元素，UPPAAL 提供Yggdrasil从TA 模型自动生成测试用例[13]，包括3 个阶段：

1）Query File，Yggdrasil 加载验证Query文件，将可达性分析的路径转换为测试用例；

2）Depth Search，采用随机深度优先搜索算法，将搜索所得路径自动转换为测试用例；

3）Single Step，针对阶段1）和阶段2）中未覆盖的边进行可达性分析生成测试用例，直到覆盖模型中所有的边。

3 全自动运行系统测试用例生成算法

3.1 全自动运行系统测试用例生成问题

全自动运行系统的测试用例主要由测试人员依据经验人工编制，通常由测试人员根据积累的测试关键项，指定测试过程中的某几个步骤，或指定某几个环节之间需要满足的条件，然后人工编制完整的测试用例。全自动运行系统交互复杂，测试步骤较多，人工编制测试用例存在效率低、容易遗漏测试需求等问题[14]。

定义2（指定路径覆盖） 测试需求包含一个测试路径集合P，其中P以参数的形式给出。

如图1 所示，TAex模型包括6 个位置，根据测试经验，测试用例需要测试S4 →S5 →S6指定的测试路径，即指定测试路径覆盖：P＝{(S4,S5),(S5,S6)}。

图1 TAex模型示例Fig.1 TAex model example

3.2 全自动运行系统测试用例生成算法

Yggdrasil 生成测试用例时不考虑指定路径覆盖。如图1 所示的TA 模型，Yggdrasil 生成如下4条测试用例，未覆盖指定的测试需求P，不能满足全自动运行系统指定路径覆盖的要求。

1）S0 →S3 →S4；

2）S0 →S2 →S6；

3）S0 →S3 →S4 →S5；

4）S0 →S1 →S5 →S6。

基于以上问题，提出全自动运行系统测试用例生成方法。首先，在全自动运行系统功能模型的基础上增加测试标记变量，达到在模型的边或节点位置上描述测试人员指定测试需求的目的，即在全自动运行系统的功能模型中表征测试人员指定的测试路径需求，形成全自动运行系统的测试模型。测试标记变量仅用于反应测试人员指定的测试需求，不改变全自动运行系统模型的功能逻辑；然后，编制测试人员指定的测试需求的Query 文件，以Yggdrasil 的Query File 测试用例生成方法对验证文件生成测试用例，满足测试人员的指定路径覆盖；最后，针对尚未覆盖的边，利用UPPAAL 的Depth Search 和Single Step 方法生成测试用例，实现100% 边覆盖，如图2 所示。

图2 测试用例生成流程Fig.2 Test case generation process

设U表示全自动运行系统测试人员指定的路径覆盖需求集，t表示算法当前迭代生成的测试用例，R表示算法生成的测试用例集。全自动运行系统测试用例生成算法如图3 所示。算法开始时，R是一个空集。算法每次迭代生成一条测试用例，将该测试用例添加到R中，直到算法结束。

图3 测试用例生成算法Fig.3 Test case generation algorithm

以图1 所示的模型为例，指定路径覆盖为(S4,S5),(S5,S6)。对边(S4,S5)和(S5,S6)分别增加测试标记的int 变量b45 和b56。满足指定路径覆盖的验证性质为：q::＝E<>b45 andb56 。

采用算法1，Yggdrasil 生成3 条测试用例，100% 实现边覆盖，且测试用例3 覆盖指定路径覆盖的需求。

1）S0 →S1 →S5；

2）S0 →S2 →S6；

3）S0 →S3 →S4 →S5 →S6。

4 全自动运行系统模式转换

以全自动运行系统模式转换功能为例，介绍全自动运行系统的测试用例生成方法。

全自动运行系统模式转换功能包括TIAS、司机、VOBC 与列车4 个参与者，功能流程如图4 所示。全自动运行系统投入运营时，TIAS 将远程唤醒指令发送到VOBC，VOBC 与车辆进行自检，唤醒列车进入FAM 模式待命。列车以FAM 模式运行过程中出现车辆与VOBC 通信故障等情况时，系统申请进入CAM 模式，经TIAS 人工授权后，系统驾驶模式由FAM 模式转换为CAM 模式。FAM 模式运行过程中，若列车遇到特殊情况需要降级时，列车停稳后，激活相应端的司机室钥匙，车载VOBC 退出FAM 模式，进入CM 模式，转入人工驾驶[15]。

图4 全自动运行系统模式转换流程序列Fig.4 FAO mode conversion process sequence diagram

5 模式转换UPPAAL建模

根据全自动运行系统模式转换流程建立全自动运行系统的TA 模型，并采用全自动运行系统测试用例生成算法生成测试用例。

5.1 模式转换时间自动机模型

全自动运行系统模式转换流程包括TIAS、列车、司机和VOBC 4 个子系统，模式转换的TA模型MODETA为各个子系统的TA 模型的积：MODETA=TIASTA||VOBCTA||DRIVERTA||TRAINTA。

其中，TIASTA主要完成TIAS 信息的发送和接受、列车动作授权的处理等功能；VOBCTA主要执行列车在模式转换流程中的动作，包括列车上电自检、升级条件的检查、列车运行中故障信息的发送以及模式转换；DRIVERTA主要模拟司机在模式转换流程中手动操作钥匙开关和模式转换确认；TRAINTA主要输出列车速度信息和非激活端换端等操作。

MODETA如图5 所示，共含58 个位置、90 个迁移、27 个通道和13 个变量，主要变量名称及其含义如表1 所示。

表1 MODETA位置及变量含义Tab.1 MODETA location and variable meaning

5.2 测试用例生成

以CM 模式转换到FAM 模式为例，介绍测试用例生成过程。根据专家经验，模式转换具有如表2 所示的测试需求。

根据全自动运行系统测试用例生成算法，为表征测试场景，MODETA模型中包含了测试标记的int 变量，主要变量如表3 所示。

表3 测试模型中的主要变量Tab.3 Main variables in test model

测试需求1 ～4 对应的BNF 验证语句如表4所示。

表4 CM转FAM模式测试需求及验证性质Tab.4 Test requirements and verification properties of conversion of CM to FAM mode

利用UPPAAL 的Query 文件生成测试用例，针对表2 的4 个测试需求，生成4 条测试用例。以测试用例1 为例，其覆盖测试场景1，测试过程如下：测试初始为CM 模式，列车速度不为0，司机制动将列车速度降为0 后，操作方向手柄至零位，操作制动手柄至零位，VOBC 检测列车最高驾驶模式指令为全自动驾驶模式，提示司机确认模式转换，但司机未确认该信息。同时，列车超速，司机将列车速度制动为0 后，确认模式转换，列车转换至FAM 模式。

利用Yggdrasil 的Depth Search 和Single Step 方法对模型中未覆盖的边继续生成测试用例，新生成14 条测试用例，其中Depth Search 方法生成1 条测试用例，Single Step 方法生成13 条测试用例。即算法一共生成18 条测试用例，边覆盖率为100%，且完全覆盖测试人员指定的4 条测试需求。

6 结论

本文针对全自动运行系统测试用例编制过程中的指定路径覆盖问题，研究时间自动机建模理论，提出了基于Yggdrasil 的指定路径覆盖测试用例自动生成算法。以全自动运行系统的模式转换功能为例，建立模式转换的时间自动机模型，并采用论文提出的算法生成测试用例。结果表明，论文生成的测试用例100% 覆盖测试人员指定的测试需求，同时100% 覆盖时间自动机模型中所有的边，能够满足全自动运行系统指定路径覆盖的测试用例生成要求。