CTCS-2级列控车载ATP组合测试用例集生成方法

饶 畅，郭 进，张亚东，查 志

(西南交通大学 信息科学与技术学院，四川 成都 611756)

CTCS-2级列控系统(Chinese Train Control System, Level-2)基于轨道电路和点式应答器传输列车行车许可信息，采用目标-距离速度防护模式监控列车运行，是保证列车安全、高效运行的重要系统之一[1]。CTCS-2级列控系统由地面设备和车载设备组成，其中车载ATP(Automatic Train Protection)设备承担着监控列车速度、防止列车越过行车许可终点等安全功能，为SIL-4级(Safety Integrity Level-4)安全关键设备，若发生失效，轻则影响行车效率，重则导致严重的行车事故，其安全性要求非常高。

严格的测试能够有效保证车载ATP的功能安全，其中核心问题之一是如何生成精简有效的测试用例。现有针对列控系统(包括车载ATP)的测试用例生成方法，如文献[2-6]等，普遍从功能模型和场景模型等角度入手开展研究。然而，车载设备的各种输入接口对设备安全性也会产生重要影响[7]，不同输入接口之间的交互组合往往会引发设备相关的软件故障[8]，严重影响行车安全。因此，对车载ATP输入接口进行组合测试具有重要意义。但在实际测试中，车载ATP接口输入情况复杂，如果采用穷举组合交互测试，往往不可行，而采用人工经验进行组合交互测试，其效率低且测试效果有限。

组合测试理论针对该类问题，能在保证检错率的前提下，用较少测试用例高效完成测试工作[9]。文献[10]提出一种基于回溯的城轨车载ATP的组合测试生成方法，测试效果显著，但该方法效率较低，且不支持参数约束。通常，组合测试大都基于覆盖数组进行[11]，其中生成精简有效的覆盖数组是一个重要的研究方向。最优覆盖数组代表组合测试中，目前已知最精简的覆盖数组，其覆盖极为紧凑。采用最优覆盖数组完成组合测试，能够在最大程度上控制测试成本。Torres等[12]采用模拟退火算法找到了若干目前已知最优的覆盖数组，为基于最优覆盖数组进行测试提供了可行性。然而，车载ATP输入复杂，存在诸多输入约束，限制了最优覆盖数组在车载ATP测试中的直接应用。

针对该问题，本文提出了一种间接利用最优覆盖数组的优势，精简生成车载ATP组合测试用例集的方法。首先，提出了参数映射算法，通过将车载ATP输入参数映射到最优覆盖数组的不同列，重构最优覆盖数组，以提高对其的利用程度；其次，提出了覆盖数组扩展算法，扩展重构后的数组，使之满足约束条件且达到规定的组合强度；最后，基于以上算法进行了CTCS-2级列控车载ATP测试用例生成，并根据结果分析了本方法的可行性和有效性。

1 CTCS-2级列控车载ATP简介

1.1 车载ATP及其测试环境

CTCS-2级列控车载ATP设备主要包含车载安全计算机、应答器传输模块、安全输入/输出接口、轨道电路信息读取器、测速测距单元和人机界面(DMI)等部分。其主要功能为界面显示、列车速度测量、列车定位、静态曲线比较、动态曲线计算以及行车许可和速度监控等。根据地面提供的轨道电路信息、线路静态参数、临时限速信息等，并结合动车组相关数据，生成目标-距离模式曲线，监控列车运行，保证列车的运行安全[13]。在实际运行中，车载ATP主要的运行场景有追踪运行、等级切换和模式转换等。车载ATP具有多种工作模式，用于支持不同的运行场景，包括待机模式(SB)、完全监控模式(FS)、调车模式(SH)及目视行车模式(OS)等。

由于CTCS-2级列控系统构成设备众多，功能结构复杂，因此针对列控系统设备的测试通常被划分在不同的阶段进行。对于车载ATP，其测试过程包括实验室仿真测试、互联互通测试和现场联调联试等不同阶段[14]。本文主要关注实验室仿真测试阶段，围绕车载ATP的各项功能仿真测试展开研究，所构建的测试环境见图1。

图1 CTCS-2级车载ATP实验室仿真测试环境

该测试环境包含仿真信息生成平台、接口仿真平台和被测车载ATP(含DMI)三部分。其中：仿真信息生成平台用于在测试过程中生成车载ATP运行所需的人工操作、车辆运动和地面设备等各种环境仿真信息；接口仿真平台用于将环境仿真信息实例化为满足车载ATP接口规格的各种信号和数据，例如轨道电路信号、应答器报文和速度传感器信号等，同时，接收来自车载ATP的输出控制信息，并反馈给仿真信息生成平台。

仿真信息生成平台由列车操纵台、车辆模拟器、地面模拟器及测试控制器等部分构成。其中：列车操纵台提供与实际列车一致的操作对象供人工操作，如前进/后退手柄、牵引/制动手柄以及紧急制动按钮等，同时还提供表示车载ATP状态的指示灯用于观测；车辆模拟器根据列车操纵台的人工操作和车载ATP设备的控制输出，实时计算列车当前的运动状态(速度、位置等)，模拟列车走行；地面模拟器根据测试控制器的控制输出，产生列车在走行过程中触发的各类地面信息，例如轨道电路编码信息、应答器信息等；测试控制器根据系统仿真状态，适时控制触发预先存储的测试用例，并实时接收和展示车载ATP的工作状态，供人工观测记录。

测试用例在测试环境中被实例化为自动触发执行和人工操作执行两部分。仿真信息生成平台根据这两部分的具体信息，并结合车载ATP输出，生成各种仿真信息，通过接口仿真平台作用于车载ATP，实现动态仿真测试。

1.2 车载ATP接口输入参数

接口输入参数表示仿真测试时，针对车载ATP的工作模式可人工操作输入。由于车载ATP处于不同工作模式时，其输入不尽相同，为便于表述，本文以车载ATP处于完全监控模式(FS模式)为例进行分析，其余的工作模式与之类似。根据车载ATP技术规范[15]及相关的功能规格，抽象出车载ATP接口输入参数，见表1。

表1 车载ATP在FS模式下的相关输入参数

鉴于技术规格和测试环境等限制，上述参数取值存在约束关系，不可忽略，否则将造成测试用例无效、测试不可行。根据车载ATP功能规格，总结出相关约束条件如下。

约束1仿真测试时驾驶台应当处于激活状态：p11=1。

约束2方向手柄不能处于既前进又后退的状态：(p1=1∧p2=1)。

约束3牵引/制动手柄不能处于既牵引又制动的状态：(p3=1∧p4=1)。

约束4实施紧急制动时，也需实施最大常用制动：p6=1→p5=1。

约束5不能同时向调车和目视行车模式转换：(p8=1∧p9=1)。

约束6完全监控模式下不能进行CTCS 0/2的等级切换：(p12=1)。

2 研究基础

2.1 相关定义

假设被测对象有n个输入参数，每个参数均有有限非空的值域，对于给定的组合覆盖强度t(t≤n)，组合测试的相关定义如下。

定义1k值模式：从n个参数中任取k个，每个参数在其取值范围内取某个值构成的k元组，称为一个k值模式。

定义2组合测试用例：对于n个输入参数，每个参数在其取值范围内取某个值构成的n元组，称为一条组合测试用例。

一条组合测试用例即为一个n值模式，一条测试需求即为一个t值模式。约束条件描述组合测试用例在参数取值方面必须满足限制关系。

定义3约束：一条约束为一个映射，将测试用例τ映射为布尔值true或false。

约束条件决定了测试用例的合法性，在组合测试实际应用中，约束条件可采用禁止元组(forbidden tuple)表示。

定义4禁止元组：为满足约束条件，禁止在测试用例中出现的k值模式，称为禁止元组。

例如要满足上述车载ATP的测试约束条件3，那么需要避免在测试用例中出现禁止元组(p3.1，p4.1)。除有特别说明外，后文提及的“组合测试用例”均默认为满足约束的组合测试用例。

定义5覆盖：对于组合测试用例τ和t值模式σ，若输入参数在τ和σ中具有相同的取值，那么称τ覆盖σ。

由组合测试用例构成的集合，称为一个组合测试用例集，简称为测试用例集。

定义6t路组合覆盖：给定测试用例集T，对于被测对象任意t个输入参数对应的任一t值模式σ，若T中都至少存在一条测试用例覆盖σ，那么称T满足t路组合覆盖。

满足t路组合覆盖的测试用例集可采用覆盖数组CA(Covering Array)表示。

定义7覆盖数组：覆盖数组CA(M;t,n,v)是一个M行n列的二维数组，每行可表示一条测试用例，M为覆盖数组包含的测试用例总数，t为覆盖强度，n为参数个数，v为参数取值个数。

CA具有如下性质：

(1)第i列对应的参数取值构成的集合大小为v。

(2)任意的M×t子数组包含了在相应值域上所有的t值模式。

(3)将CA的任意两列互换，CA仍然满足t路组合覆盖。

具有最小行数的覆盖数组即最优覆盖数组，记为CAN(t,n,v)，简写为CAN。

2.2 基于最优覆盖数组的组合测试

设被测对象的输入参数为p1，p2，…，pn，每个输入参数具有大小为v的值域，对于组合覆盖强度t，基于最优覆盖数组CAN进行组合测试。通常的做法是，首先找到一个覆盖强度为t、列数为n且每列具有v个不同取值的最优覆盖数组CAN(t,n,v)，然后按照下标对应关系，将参数pi映射到CAN的第i列(i=1，2，…，n)，通过参数映射，将CAN的每一行构造为一条测试用例。

车载ATP的接口输入参数具有相同大小的值域，因此可基于最优覆盖数组CAN进行测试。然而车载ATP的测试输入中存在大量约束条件，采用现有方法，有可能造成输入参数在映射到CAN的过程中，某些行出现禁止元组，导致这些行不满足约束条件，无法用于实际测试，最终只能被移除。若CAN中需要移除的行越多，那么对于CAN的利用程度将会越低，需要额外补充的测试用例将会越多，在这种情况下，控制车载ATP的测试成本将会变得越困难。

3 车载ATP组合测试用例生成方法

本文针对现有方法面临的问题，提出了一种基于最优覆盖数组的带约束组合测试用例集生成方法，其主要流程见图2。

图2 车载ATP组合测试用例生成流程

该方法包括两步：①基于参数映射算法的最优覆盖数组重构；②考虑约束的覆盖数组扩展。最优覆盖数组重构，即基于参数映射算法，采用贪婪映射策略，将车载ATP输入参数映射到最优覆盖数组CAN的不同列中，最大程度上保留满足约束条件的行，移除最少量不满足约束条件的行。覆盖数组的扩展，即采用覆盖数组扩展算法，在考虑约束的前提下，扩展前一步得到的子数组，得到满足约束和覆盖强度的测试用例集。

3.1 最优覆盖数组重构

根据覆盖数组的基本定义可知，对覆盖数组进行列交换操作，将会改变数组相应位置上元素的取值，但并不会造成组合覆盖丢失。对此，本文利用覆盖数组的这一特性，针对车载ATP约束条件，通过交换CAN的列，对每行元素的取值进行重构，力求在最大程度上削减映射过程中出现的无效行数量，从而更好地利用CAN。

进行列交换操作，可看作将输入参数按照一定关系映射到CAN的不同列。因此，重构CAN的关键在于找到一个最优的映射关系，使得映射后CAN的无效行数量最少。通过遍历所有可能的映射方式，在理论上可找到一个最优的映射关系，但在实际情况中，往往不具备可行性。例如对于车载ATP，其参数的映射方式达到了13!=13×12×…×2×1=6 227 020 800种，完全遍历不具备时间可行性。

鉴于此，本文提出了一种贪婪算法，来快速计算近似最优的列映射关系。该算法每次选择一个未映射的参数，按照贪婪方式将该参数映射到CAN的某一列，算法循环执行直至所有参数均被映射。为便于说明流程，提出如下定义。

定义8敏感元组：禁止元组f的部分参数已经被映射，但另一部分参数还未被映射，将f在已被映射的参数上的投影称为敏感元组。

例如，对于上述禁止元组(p3.1，p4.1)，若参数p3已经映射，但p4还未映射，那么称1-值模式(p3.1)为一个敏感元组。

定义9无效行：对于CAN的某一行r，若r中已经被参数所映射的那部分，包含禁止元组，那么称r为无效行。

定义10敏感行：对于CAN的某一行r，若r中已经被参数所映射的那部分，不含禁止元组但包含敏感元组，那么称r为敏感行。

敏感行在映射过程中可能会转变为无效行，造成更多行被移除。对此，本算法在映射参数时，根据无效行、禁止元组和敏感行对重构CAN的影响，按照优先考虑无效行最少，其次考虑禁止元组数量最多，最后考虑敏感行最少的原则完成参数映射，保持无效行数量最少。算法框架如下。

算法输入：参数集P={p1,p2,…,pn}，CAN(t,k,v)，禁止元组集F。

算法输出：CAN的子数组SCA，其中每一列均有参数映射。

开始

令SCA←CAN

令Q←∅

for (inti=1 ton) 执行

if (pi∉F) 执行

Q←Q∪{pi}; //Step1

else

令C←{c|c为SCA中未被参数映射的列};

基于字典序比较策略，完成映射pi→cmin，其中cmin∈C; //Step2

end if

end for

for (每个参数p∈Q) 执行

令C←{c|c为SCA中未被参数映射的列};

从C中取出一列，完成映射p→c; //Step3

end for

for (每行r∈SCA)

if (r包含禁止元组f∈F)

从SCA中移除r; //Step4

end if

end for

returnSCA;

结束

该算法主要包括以下4个步骤：

Step1参数约束性检查。逐一检查输入参数是否出现在集合F相关的禁止元组中，若不出现，则将该参数加入非约束参数集Q，否则执行下一步。

Step2映射约束参数。基于字典序比较策略，将约束参数pi映射到SCA的某一列cmin。设参数pi映射到SCA的某一列，产生的无效行数量为n1，无效行包含的禁止元组数量为n2，敏感行数量为n3，则该步骤根据字典序[n1，n2，n3]比较，完成映射pi→cmin，即

(1)若SCA中仅存在一列c1，使得pi→c1产生的n1最少，则cmin=c1。

(2)若SCA中存在多个列，pi映射到其中任一列产生的n1均相同且最少，在这种情况下，检查pi映射到其中任一列产生的n2数量。若仅存在一列c2，使得pi→c2产生的n1和n2都最少，则cmin=c2。

(3)若SCA中存在多个列，且映射pi到其中任一列产生的n1和n2均相同且都最少，在这种情况下，检查pi映射任一列时产生的n3数量。若其中仅存在一列c3，使得pi→c3产生的n1，n2，n3都最少，那么cmin=c3。

(4)若SCA中存在多个列，且映射pi到其中任一列产生的n1，n2，n3均相同且都是最少的，则从这些列中任取一列作为cmin。

循环执行Step1和Step2直至所有约束参数完成映射，然后执行下一步。

Step3映射非约束参数。由于映射非约束参数不会增加无效行，因此，算法直接取出Q中参数，依次映射到CAN还未被映射的列中，完成所有参数的映射。

Step4根据约束条件，移除SCA中的无效行。

3.2 覆盖数组扩展

重构最优覆盖数组并移除无效行，有可能造成无效行中某些合法有效t值模式丢失覆盖。设这些t值模式构成的集合为Π。为使得最终生成的车载ATP组合测试用例集既能满足约束条件，又能实现对Π的全覆盖，需要额外生成测试用例，扩展重构之后的数组。

本文提出一种基于one-test-at-a-time架构的组扩展算法，以每次构造若干候选测试用例、并选择最佳候选测试用例的方式扩展数组，通过循环执行，直至对Π实现全覆盖。设Π中t值模式对应的参数组合为Σ1，Σ2，…，Σm，Π(Σi)代表Π中属于参数组合Σi的t值模式构成的集合，i={1，2，…，m}。算法的基本框架如下。

算法输入：参数集P={p1,p2,…,pn}，覆盖强度t，集合Π，子数组SCA，禁止元组集F。

算法输出：满足约束和覆盖强度的SCA。

开始

令Σ←{Σ1,Σ2,…,Σm};

令T←∅;

while (Π!=∅) 执行

选择Σmax∈Σ，使得对于∀i∈{1,2,…,m}，Σi≠Σmax，都有|Π(Σi)|≤|Π(Σmax)|;

for (每一个σ∈Π(Σmax))

初始化候选测试用例τ←σ; //Step1

基于贪婪策略扩展τ; //Step2

T←T∪{τ};

end for

选择τb∈T，使τb覆盖Π中最多t值模式; //Step3

将τb加入SCA; //Step4

从Π中移除被τb覆盖的t值模式;

end while

returnSCA;

结束

该算法主要包括以下4个步骤。

Step1初始化候选测试用例。在候选测试用例集T中，选择|Π(Σi)|最大者完成候选测试用例的初始化。设被选中的参数组合为Σmax，算法将在T中总共构造|Π(Σmax)|条候选测试用例。对候选测试用例进行初始化，即对候选测试用例中，与Σmax相关的t个参数，由Π(Σmax)中一个t值模式进行赋值，对测试用例中其余的n-t个参数，暂不赋值。算法在该步骤初始化多个候选测试用例，目的在于通过尝试更多的组合可能性，来找到覆盖最多t值模式的最佳候选测试用例。

Step2扩展候选测试用例。对于每条候选测试用例τ∈T，算法采用贪婪策略，每次从Π中选择一个t值模式σ，使用σ为τ的参数赋值。其中，σ需同时满足以下3个条件：

(1)σ与τ的参数取值具有一致性。

(2)σ赋值给τ能够满足约束条件。

(3)σ赋值给τ能覆盖到Π中最多t值模式。

在以上3个条件中：条件(1)的取值具有一致性，指参数在σ和τ中具有相同取值，或参数在σ中有具体取值，在τ中还未被赋值；对于条件(2)的测试用例约束检查，本算法采用了文献[16]提出的最小禁止元组(Minimum Forbidden Tuple)对比法，保证τ在扩展过程中始终满足约束条件，不包含任何禁止元组和隐含元组(Implicit Tuple)；条件(3)为一个贪婪策略，目的在于快速扩展得到精简且满足要求的候选测试用例，在步骤2中将采用该策略连续扩展τ，直至τ中所有参数均被赋值，或无法再从Π中找到σ对τ赋值。

Step3选择出最佳候选测试用例τb∈T，使τb相对于其他候选测试用例而言，能够覆盖到Π中最多t值模式。

Step4将τb作为新的一行加入SCA，并从Π中移除被τb覆盖的t值模式。

重复执行Step1至Step4，直至Π为空。

4 车载ATP组合测试用例生成结果

本文基于Java平台实现上述方法，生成了CTCS-2级列控车载ATP组合测试用例集。由于车载ATP在FS模式下，既能进行模式转换，又能进行等级切换，也能维持在FS模式工作，为便于区分测试用例性质，提高测试针对性，本文按照车载ATP模式转换、等级切换、维持在FS模式3种基本场景，分别生成与输入参数相关的组合测试用例集。限于文章篇幅，这里以生成模式转换场景相关的组合测试用例集为例进行详细说明，其余2种场景与之类似，仅列出最终结果。

4.1 最优覆盖数组重构

在模式转换场景下，车载ATP的驾驶台始终处于激活状态，并且不能出现等级切换信号，此时参数p11=1，p12=0，p13=0。实际进行组合的参数为p1，p2，…，p10。图3展示了在覆盖强度t=2时，这些参数分别按照现有方法和按照本文方法完成映射后，最优覆盖数组CAN(2,10,2)≤6的变化情况。其中，图3(a)表示采用现有下标映射方式(pi→ci)构成的覆盖数组，图3(b)表示采用本文方法重新映射后构成的覆盖数组，图中灰色部分为无效行中包含的禁止元组。

图3 最优覆盖数组重构

从图3中可以看出，重构前，采用现有参数映射方式将移除4行无效行(r2，r4，r5和r6)，而采用本文方法重构后仅移除2行(r4和r5)，提高了对最优覆盖数组的利用。

4.2 覆盖数组扩展

重构最优覆盖数组，共造成32个合法有效的2-值模式丢失覆盖，限于文章篇幅，这里不再详细列出。

图4展示了扩展覆盖数组，覆盖所有合法2-值模式后得到的覆盖数组及完整的测试用例集。图4中覆盖数组的列顺序已调整为参数的下标顺序，虚框内绿色部分为对最优覆盖数组的利用。

图4 车载ATP模式转换场景下的组合测试用例集

图4(b)每一行代表一条测试用例，如第2行表示在FS模式下，将车载ATP方向手柄设置为向前、牵引手柄设置为牵引，模拟列车前进运行；然后在运行过程中，保持手柄状态，并施加最大常用制动，测试车载ATP能否控制列车停车；最后待停车后，保持手柄状态和最大常用制动，按压调车键，测试车载ATP能否转换为调车模式。

4.3 有效性分析

车载ATP为SIL-4级安全关键设备，其测试覆盖准则相对于通用软件而言要求更加严格[17]。本文基于最优覆盖数组，还进行了更高强度的测试用例生成(t=2，3，4，5)。同时，为验证方法的有效性，选取了以下3种方法与本文方法进行比较：①基于现有的参数映射方法生成测试用例集(以下简称为直接扩展法)；②基于主流工具PICT[18]生成测试用例集；③基于主流工具ACTS[19]生成测试用例集。基于直接扩展法生成测试用例集，即首先采用现有的参数下标映射方法，直接将参数映射到CAN并移除无效行；然后采用本文提出的扩展算法完成子数组的扩展，得到满足约束的测试用例集。基于主流工具PICT和ACTS直接生成测试用例集，即首先根据输入参数与约束条件构造组合测试的输入模型，然后基于输入模型，采用工具直接生成测试用例集。图5展示了几种方法分别在模式转换、等级切换和维持在FS模式3种场景下的测试用例集生成结果(t=2，3，4，5)。

图5 不同场景和覆盖强度下的测试用例生成结果

由于车载ATP在等级切换和维持在FS模式2种场景下的有效组合参数均为8个，且具有相同的约束条件，因此同一方法2种场景中生成的测试用例数量也相同。图5表明了在满足约束条件和组合覆盖强度的前提下，由本文方法产生的测试用例集普遍更加精简。对于总共12个测试用例集，本文方法得到的结果，比直接扩展法更为精简的达到7个，比PICT和ACTS更为精简的达到10个。

特别地，在t=5时，对于模式转换场景，采用本文方法生成的测试用例仅为96条，而在同等条件下，采用直接扩展法得到的结果为108条，采用PICT工具得到的结果为104条，采用ACTS工具得到的结果为103条。本文方法得到的结果相对于现有方法，最多可减少12条测试用例，测试用例集的规模减小幅度达到了11.11%。通过比较，验证了本文方法的有效性。

此外，为验证本文提出的参数映射算法的有效性，还比较了本文方法和直接扩展法在测试生成过程中对CAN的利用率，见图6。

图6 2种方法对于最优覆盖数组的利用率

从图6可看出，本文方法对CAN的利用率大都高于直接扩展法。尤其在t=2时，本方法对于覆盖数组的利用率最高达到了83.33%(等级切换和维持在FS模式)。而在相同条件下，直接扩展法对于覆盖数组的利用率仅为50%。在t=5时，本方法对CAN的利用率虽然仅为41.07%(模式转换)，但仍然高于直接扩展法对CAN的利用率(35.71%)。通过对比分析，验证了本文参数映射算法的有效性。

5 结论

(1)车载ATP是列控系统的核心设备之一，针对车载ATP接口输入参数的组合测试在保障功能安全方面具有重要意义。

(2)最优覆盖数组具有行数最少、覆盖紧凑等特点，基于最优覆盖数组完成组合测试，能有效控制测试成本。

(3)本文针对车载ATP的参数组合特点，提出了基于最优覆盖数组的车载ATP组合测试用例集生成方法。结果表明，本方法能够提高对于最优覆盖数组的利用，在满足约束和覆盖准则的基础上，实现了测试用例集的精简生成，有效降低了车载ATP测试成本，提高了测试效率。