城轨交通全自动运行系统组合测试用例生成方法

陈 争，孙可心，刘传刚，冉怡明，李任宇

全自动运行（Fully Automatic Operation，FAO）系统是基于计算机、通信、控制和系统集成等技术，实现列车运行全过程自动化的新一代城市轨道交通系统，不需要配置列车司机，能够有效地保证运行安全，提高运行效率，降低运营成本，增强对客流变化的响应能力［1］。

近年来，随着车辆、信号、通信和综合监控等核心专业自动化水平的不断提高，FAO 系统已经在我国大中城市的轨道交通中进入了实际应用阶段，代表了智慧城轨的重要发展方向。相比较传统的地铁列车控制系统，FAO 系统对可靠性、可用性、维修性、安全性指标提出了更高要求，因此在投入运营前需要进行全面测试，而覆盖全面的测试用例对保证全自动运行系统测试的完备性具有重要意义。

目前，FAO 系统的研究主要集中在系统方案设计、优化和仿真平台方面。如：文献［2］从FAO 系统的运营需求出发，提出一套满足全自动运行过程中清客控制管理的设计方案；文献［3］研究FAO 系统场景验证平台，能够在系统建设初期优化场景设计，指导功能开发；文献［4］对全自动运营场景进行梳理，研究不同运营场景对车辆、信号、通信和综合监控等关键装备的功能需求及接口关系，为工程设计人员提供参考；文献［5］研究正线休眠唤醒区域全覆盖的设计要点和运营效益，并提出相关的操作建议；文献［6］将基于数据驱动的测试方法引入到FAO 系统的测试中，简化测试平台的搭建，提高测试的有效性和完备性；文献［7-8］研究FAO 系统典型运营场景，提取功能与性能的需求，构建时间自动机网络模型，并验证其功能属性、性能属性和安全属性，为系统设计与实现奠定基础；文献［9］研究FAO系统的互联互通特点，构建适合互联互通的FAO 系统测试环境，提出完备的互联互通测试方案；文献［10］研究全自动运行外场测试的功能需求和选址条件，提出不同条件下的测试方案；文献［11］基于仿真测试平台，对全自动无人驾驶系统的关键场景进行分析，探讨室内仿真测试方案，并在上海轨道交通全自动无人驾驶18号线和15号线进行了应用。

组合测试是检测系统各种交互组合的测试理论。近年来，该理论在轨道交通领域的测试中得到了深入的研究和广泛应用，如文献［12-14］在高铁信号系统的测试中引入了组合测试技术。本文基于时间自动机建模方法和组合测试理论，提出FAO 系统的组合测试用例生成方法，对保证FAO系统测试的全面性和完备性具有重要意义。

1 时间自动机

时间自动机（Timed Automata，TA）由Stanford大学的Rajeev Alur和David Dill于20世纪90年代提出。时间自动机对有限自动机进行扩展，使用时钟变量表示有时间约束的状态转换关系，从而可以处理实时系统［15］。由Aalborg 大学和Uppsala 大学在1995年联合研发的基于时间自动机的实时系统模拟和验证工具UPPAAL，能够对实时系统进行建模、仿真、验证和生成测试用例，具有高效、简便的特点［16］。UPPAAL 对时间自动机理论进行了扩展，增加了int 变量、bool 变量、广播通道（broadcast chan）等元素［17］。

定义1时间自动机。TA 是一个六元组＜L，B，C，V，E，I＞，其中：L是状态的集合，l0∊L为初始状态；B为通道集合；C为时钟变量集合，V为有界整型变量集合，设Φ(C，V)为条件表达式的集合，R(C，V)为所有时钟变量的重置操作和整型变量赋值操作的集合；E为边的集合，E⊆L×B？！×Φ(C，V)×R(C，V)×L；B？！为操作集合，B？！={a？|a∈B}∪{a！|a∈B}；元素 (l，α，φ，γ，l')∈E描述了一条从状态l到状态l'的边，其中α为边上的操作，φ为转移条件，γ为重置操作或赋值操作；I：L→Φ(C，V)表示状态上的时间不变式。

定义2路径。设l，l'∈L，TA 的一条路径p是一个边的序列：p=(l，α1，φ1，γ1，l1) ；(l1，α2，φ2，γ2，l2) ；……；(ln-1，αn，φn，γn，l')。

此时，称l通过路径p可以到达l'，简称l'从l可达。

UPPAAL 包括系统编辑器、模拟器、验证器和测试用例生成器（Yggdrasil）等模块。其中，系统编辑器用于创建和编辑TA 模型，Yggdrasil以边覆盖为覆盖准则，提供序列文件（Query File）、深度搜索（Depth Search）和单步（Single Step）3 种方法，自动从TA模型生成测试路径［18］。

2 组合测试

作为系统安全性测试中的一种重要测试方法，组合测试围绕系统输入域的交互组合，在保证组合覆盖的前提下，对系统实施高效、完备的测试。通常，组合测试重点检测系统因各种交互组合而造成的系统故障［19］。

组合测试主要包括组合测试建模、测试用例生成、测试执行、错误定位和结果评估等步骤，见图1。其中组合测试建模是根据被测系统的需求规格，辨识系统的输入参数及其取值，确定约束条件，构建系统的输入模型；测试用例生成是根据构建的输入模型，利用各种组合测试用例生成方法，构造被测系统的组合测试用例集。

图1 组合测试主要步骤

定义3t-维组合覆盖。对于路径p及其序列集T，给定组合强度t（t≤|p|），对于p的任意t-事件组合的任一t-值模式π，若T中都至少存在一条测试序列覆盖π，那么T满足t-维组合覆盖，称T为p的t-维组合测试用例集，简称t-维测试用例集。

t-维组合覆盖通过构造测试用例集，对被测系统任意t个输入参数之间所有的交互取值组合至少覆盖1次。假设某系统包括a，b，c3个输入变量，每个输入变量均包括2个取值，0和1，则全组合需要执行2×2×2=8次测试。若采用组合测试，选用2-维组合覆盖，应用组合测试用例生成工具ACTS共生成4 条测试用例，即可完全覆盖a，b，c中任意2个变量的取值组合，组合测试用例见表1。

表1 组合测试用例

3 全自动运行系统组合测试用例生成

通常采用UPPAAL 对FAO 系统进行测试建模时，主要是利用int、bool 和chan 等类型描述系统的功能流程，并依据TA 模型生成测试路径，重点关注系统的功能逻辑。在实际执行测试时，需要提取测试路径上信号或变量描述的具体工况，进而将测试路径实例化为具体的操作或测试数据。由于FAO 系统功能复杂，测试路径通常为一系列的操作流程，涉及多个变量，每个变量代表的具体工况可能为1 个或多个，如模式转换，方向手柄和制动手柄在“0位”或“非0位”等，因此为对FAO 系统进行全面测试，需要覆盖测试流程中变量值的各种组合，即：

测试需求= ｛（方向手柄0 位，制动手柄0位），（方向手柄0 位，制动手柄非0 位），（方向手柄非0 位，制动手柄0 位），（方向手柄非0 位，制动手柄非0位）｝。

由于对所有组合情况全部进行测试，在测试时间和测试开销方面是不实际的，而组合测试技术可以在保障变量组合覆盖的基础上，大大降低测试用例数量，提高测试效率，因此结合FAO 系统的TA 建模流程和组合测试理论，提出FAO 系统组合测试用例生成方法。

FAO系统组合测试用例生成流程见图2，包括时间自动机建模、基于时间自动机模型的测试路径生成和组合测试用例生成3个阶段。

图2 FAO系统组合测试用例生成流程

1）时间自动机建模。首先，基于FAO系统的需求规范，依据时间自动机语法，采用UPPAAL建立TA 模型；然后，采用UPPAAL 提供的仿真模拟和形式化验证技术，检测模型的正确性，如果模型不正确，则根据仿真和验证结果修正模型。

2）测试路径生成。利用Yggdrasil 提供的测试路径生成方法，结合形式化验证的性质文件，利用Query File、Depth Search 和Single Step 3 种方法，自动生成FAO系统的测试路径。

3）组合测试用例生成。首先，提取TA 模型中的chan 和变量，基于FAO 系统的需求规范，采用输入域建模理论［20］，对chan 和变量的输入空间进行划分，提取chan 和变量在测试执行中代表的工况，作为组合测试的输入参数值；然后，结合生成的测试路径，采用组合测试算法或工具，生成FAO系统的组合测试用例。

下面以FAO 系统的唤醒场景为例，介绍FAO系统组合测试用例的生成过程。

4 唤醒场景组合测试用例生成

4.1 唤醒场景功能逻辑

列车在投入运营前，FAO 系统需要进行唤醒，激活列车，并对列车的实际情况进行检查，达到故障预警、缓解日常运维对人力的需求、提高FAO系统运维效率的目的。

行车综合自动化系统根据运行时刻表，提前唤醒即将投入运营的车辆；车载收到唤醒命令后，车载控制器（Vehicle On Board Controller，VOBC）和车辆进行上电自检。如果自检成功，列车满足静态、动态测试条件，则由VOBC 发起、车辆配合，进行列车静态、动态测试；如果测试成功，VOBC将向行车综合自动化系统汇报唤醒成功。如果自检失败或不满足测试条件，将不进行列车静态和动态测试，列车唤醒失败［21］。FAO 系统唤醒功能动态测试序列见图3。

图3 唤醒功能动态测试序列

1）FAO 系统接收到列车唤醒命令，由列车自动防护系统（Automatic Train Protection，ATP）检查列车预设最高驾驶模式为FAO 模式、车辆方向手柄设在0 位、车辆牵引制动手柄在0 位、VOBC 头尾通信正常、司机钥匙在关闭位、检修按钮在非检修位等条件满足后，系统按预设的顺序选择驾驶端，进行静态测试。

2） 静态测试完成后，ATP 通过列车自动驾驶系统（Automatic Train Operation，ATO）向列车控制和管理系统（Train Control and Management System，TCMS）发送预设时长的鸣笛指令，车辆进行鸣笛操作，提醒库内工作人员。

3） ATP向ATO发送向前跳跃指令，ATO判断满足动态测试条件，向ATP 发送带方向的跳跃指令。该指令通过辅助驾驶单元（Assistant Operation Module，AOM）传输给车辆，车辆收到带方向的跳跃指令后，执行动态测试准备，通过TCMS 向ATO 发送跳跃反馈指令；ATO 收到跳跃反馈指令后，向车辆输出预设时长和大小的牵引。ATO 检测到车辆处于零速状态后，向ATP 发送跳跃完成标志。

4） ATP 向ATO 发送向后跳跃指令，系统处理流程与向前跳跃类似。

5） ATP 接收到跳跃完成标志后，判定完成本端动态测试，进行自动换端操作，在另一端进行静态测试和动态测试。当两端的静态、动态测试均通过后，ATP向控制中心汇报唤醒完成。

向前跳跃和向后跳跃的过程中，ATP 监督列车跳跃过程中的速度、加速度和跳跃距离，若任一项超过预定义值，ATP 判断跳跃异常，输出紧急制动；若在规定时间内未收到ATO 的跳跃完成指令，则认为跳跃失败。

4.2 唤醒场景时间自动机建模

FAO 系统列车唤醒功能时间自动机模型见图4，记为AwakeTA，包括ATP 模型（ATPTA）、ATO 模型（ATOTA）、AOM 模型（AOMTA）、TCMS模型（TCMSTA）和列车模型（TrainTA）5个部分，即AwakeTA为这5个时间自动机模型的积

图4 全自动运行系统列车唤醒功能时间自动机模型

AwakeTA包括61个节点、83条边、31个broadcast chan、10 个int 变量和1 个时钟变量，主要broadcast chan的含义见表2。

表2 AwakeTA主要broadcast chan含义

1）ATPTA模型描述ATP 与ATO、AOM 之间的交互信息，包括发送鸣笛、向前跳跃、向后跳跃等指令，接收并发送带方向的跳跃指令和接收跳跃完成标志。

2）ATOTA模型描述ATO 接收ATP 和TCMS的信息，运算后进行响应的过程。

3）AOMTA模型描述AOM 与ATP、车辆的交互信息，AOM接收由ATP发来的带方向的跳跃指令，并转发给车辆。

4）TCMSTA模型描述TCMS与ATO、车辆的交互信息，TCMS 接收来自车辆的跳跃反馈指令，并转发给ATO。

5）TrainTA模型描述车辆与AOM、TCMS 之间的交互信息，车辆接收到由AOM 发来的带方向的跳跃指令后，将跳跃反馈指令发送给TCMS。

AwakeTA唤醒过程中包括静态测试前的设备状态条件不满足、自检失败、向前跳跃异常、向后跳跃异常和跳跃超时5 类故障。AwakeTA检测到异常后，发送唤醒失败，结束唤醒操作。

4.3 唤醒场景测试路径生成

采用Yggdrasil提供的Query File、Depth Search和Single Step 3 种测试路径生成方法，结合文献［18］提出的测试路径生成算法，对AwakeTA一共生成14条测试路径，其中Query File生成测试路径8 条，Depth Search 生成测试路径1 条，Single Step生成测试路径5 条，节点覆盖率和边覆盖率均为100%。

以向前跳跃失败为例，在AwakeTA的14 条测试路径中，包括2条相关的测试路径。

1） 测试路径p1：接收唤醒命令后，FAO系统自检成功，选择激活端，进行向前跳跃，跳跃存在异常。

2） 测试路径p2：接收唤醒命令后，FAO系统自检成功，选择激活端，进行向前跳跃，跳跃成功；继续向后跳跃，跳跃成功；列车切换激活端，进行向前跳跃，但跳跃异常。

以测试路径p1为例，其通过ATPTA模型的状态为Init → WakeUp → ConPass → Header →Ready → MDing → ReadyJog → ForJog → For-Temp1 → ForJog_Fail。

4.4 唤醒场景组合测试用例生成

结合FAO 系统的需求规范，对AwakeTA模型中broadcast chan、int 变量和时钟变量进行输入域建模。以向前跳跃失败为例，组合测试用例生成过程如下。

向前跳跃失败涉及时钟变量x，以及GetHeader 和ForJogFail 2 个broadcast chan。结合测试经验，时钟变量x选取k1、k2 2 个时间值，broadcast chan 的输入域建模见表3。选用2-维组合覆盖，采用ACTS 组合测试用例生成工具，利用内置的IPOG 算法，结合向前跳跃失败的2 条测试路径，一共生成6 条组合测试用例，覆盖系统任意2 个输入之间的组合，见表4。

表3 向前跳跃失败broadcast chan输入域建模

表4 向前跳跃失败组合测试用例

以第1 条组合测试用例为例，其测试过程为：接收唤醒命令后，自检成功，FAO 系统选择前端为激活端，进行向前跳跃，跳跃时间为k2，满足跳跃时间约束，但跳跃距离异常。

通过FAO 系统测试用例生成算法，AwakeTA模型一共生成35 条组合测试用例，主要的测试用例统计见表5。

表5 全自动运行系统主要的组合测试用例统计

基于Yggdrasil的测试用例生成机制，AwakeTA的测试用例覆盖了模型中所有的节点和边；同时，基于ACTS 的IPOG 等算法，覆盖了模型中任意2 个输入之间的组合，提升了FAO 系统测试用例的全面性和完备程度。

5 结论

本文提出FAO系统的组合测试用例生成方法，首先采用时间自动机理论对FAO 系统进行建模；然后基于时间自动机模型生成测试路径，结合输入域建模方法提取测试模型描述的系统工况；最后结合组合测试理论，自动生成组合测试用例。以唤醒功能为例，采用UPPAAL 建立唤醒功能的时间自动机模型，利用Yggdrasil 插件生成唤醒功能的测试路径，并利用ACTS 采用2-维组合覆盖生成组合测试用例。结果表明，测试用例100%覆盖时间自动机模型的节点和边，同时覆盖系统任意2 个输入之间的组合，对于FAO 系统测试的研究具有一定的参考价值。