基于决策树等价的CBTC 列控车载TSM 监控曲线测试案例约简方法

2022-02-03李开成罗正伟魏国栋吕继东

北京交通大学学报 2022年5期

张芳，李开成，罗正伟，魏国栋，吕继东

（北京交通大学电子信息工程学院，北京 100044）

Communication Based Train Control 列控系统作为典型的安全苛求系统，其任何功能故障都可能造成严重的事故和生命财产的损失［1］.车载设备的目标速度监控（Target Speed Monitoring，TSM）监控曲线功能，以目标速度、目标距离、线路条件、列车特性为基础信息，生成列车安全运行的一次制动模式曲线，是实现列车超速防护功能、确保列车安全运行的关键.然而，列控车载TSM 监控曲线功能具有参数输入域规模大、故障模式复杂等特点［2］，如何进行有效测试，保障其功能的正确性至关重要.

传统的列控车载设备功能测试主要采用一致性测试方法，通过利用被测设备可观测的输入/输出一致性关系进行测试案例的生成，取得了良好的效果.文献［3］在测试列控系统时应用了基于模型的测试方法并对该系统进行建模验证了其安全功能的正确性.文献［4］提出了一种基于Petri 网（Color Petri Net CPN）的测试案例生成算法，用于在列控系统的移动授权切换场景中自动生成测试案例集.近年来基于模型的测试方法也应用于国内新型列控系统的测试上.文献［5］提出一种基于Timed Automata with Input and Output TAIO 变异分析的新型列控系统功能测试框架，基于车载模型生成上万个变异体模型和测试案例，提高了检错能力.文献［6］提出了基于在线一致性方法的CBTC 系统车载设备安全功能测试框架，实现了测试案例自动生成，且案例能够准确检测出故障，可见基于模型的测试方法可适应列控系统大部分运营场景.然而，上述研究中被测设备和测试环境构建一般基于典型的列控系统运营场景和故障模式，在实际测试时，测试案例会随着覆盖运营场景和故障模式的不同组合呈指数级增长.

近年来，组合测试受到了国内外的广泛关注，与传统一致性测试直接覆盖功能不同，组合测试是一种基于接口参数的测试，通过对输入参数的组合覆盖，间接覆盖系统的功能.其基本思想是：以用较少的、可以满足组合覆盖标准的测试案例，检测被测系统（System Under Test，SUT）中由参数交互触发的故障［7］.文献［8］采用正交拉丁方生成测试案例集，对Ada 编译器进行了测试，这也是最早将组合测试应用到软件测试中的实例.文献［9］利用组合测试方法对具有大量软硬件组合的OMX/StarMAIL 产品进行了实例研究，通过自主研发工具OATS 生成的正交表形式测试案例集案例数量少且能够检测系统软件故障，提高了测试效率.随着组合测试研究的深入，组合测试方法在兼容性测试、GUI 测试、Web 应用测试和高度可配置的系统中都有了广泛的应用.

在列控领域，组合测试也逐渐成为研究热点，文献［10］改进了基于网络模型的组合测试案例生成算法，并将其运用到CBTC 列控系统车载设备的功能测试中，满足了实际的测试需求.在保证覆盖率的前提下提高了CBTC 列控系统的测试效率.文献［11］针对实际CBTC 系统车载设备建立了组合测试模型，并利用基于解空间树的组合测试案例生成算法自动生成了覆盖多参数组合的测试案例集，实现了对系统故障的快速定位.文献［12］提出了一套适用联锁软件的组合测试框架并且设计了一套自动化组合测试系统，极大地约简了测试案例的数量和测试的操作步骤.文献［13］提出了一种基于组合测试的全自动运行（Fully Automatic Operation，FAO）系统自动测试案例生成方法，并取得了良好效果.虽然组合测试已经成功应用到车载子系统测试中，但是由于在实际测试中覆盖了没有交互的参数组合，由此会产生一定数量的冗余测试案例.因此，为了进一步提高车载设备测试的效率，需要在保证故障检测能力的前提下，尽量约简组合测试案例套件的规模.

组合测试案例套件约简的常用方法是通过参数之间的约束来移除不满足条件的测试案例.但由于约束识别通常是手工完成的，因此该方法存在效率低的问题［14］.文献［15］针对两两组合测试案例套件提出了一种基于程序不变量的约简算法，可以减少测试案例的数量.然而，为了提取程序不变量，必须预先设置一定的模板.由于模板的数量是固定的，所以目前可以检测到的不变量的形式也是固定的，这限制了该方法的实际应用.文献［16］提出了一种基于语句覆盖和变异覆盖信息的组合测试案例套件约简方法.不过，由于获取测试案例对应覆盖信息的成本较高，该方法难以应用于复杂系统.

本文作者提出了一种基于决策树等价的组合测试案例套件自动约简方法.其基本思想是每个组合测试案例套件及其系统相应输出标签可以在一定程度上捕获SUT 的某些行为.首先，结合t-way 参数覆盖的组合测试案例及其输出构造捕获SUT 行为的数据集，并采用CART 算法将数据集推理出决策树；其次，设计了改进的组合测试案例约简算法，利用决策树结构等价和误分类等价关系约简冗余的组合测试案例；最后，利用约简算法在CBTC 列控车载TSM 监控曲线功能上进行了实例分析，相关实验结果表明，该方法可以达到高达74%的约简率，同时约简前后，测试套件的低层次组合覆盖率和故障检测能力基本一致.

1 CBTC 列控车载TSM 监控曲线

CBTC 列控系统包括地面设备，车载设备和数据传输设备.CBTC 系统充分利用通信传输手段，实时或定时地进行列车与地面设备间的双向通信，区域控制器ZC 根据前车的位置信息、线路障碍物的状态信息以及联锁设备状况为后车计算行车许可（Movement Authority，MA），即行驶权限；车载设备根据地面传送的数据与预先储存的列车数据计算出列车行驶时最大允许速度，并对列车运行的实时速度进行监督和控制.系统的整体架构图如图1 所示.

图1 CBTC 列车运行控制系统整体架构Fig.1 Overall architecture diagram of CBTC

速度监控曲线是列车运行过程中所有位置的限制速度构成的速度—距离曲线，用于监控列车实时速度.该曲线可分为顶棚速度监控区、目标速度监控区和安全距离区.列车在运行过程中一旦触发速度监控曲线，应采取相应的制动措施，限制列车运行速度，保证行车安全.

根据TSM 防护曲线的生成原理，通过前方目标点位置及目标速度生成动态距离监控曲线［11］.目标速度监控区内各速度曲线的名称和关系，如图2所示.

图2 目标速度监控曲线Fig.2 Target speed monitoring curve

图2 中，根据安全制动模型首先得到紧急制动触发曲线EBI，然后再依次算出常用制动触发曲线SBI、报警曲线W和允许速度曲线P.

2 组合测试案例套件约简方法

2.1 组合测试

假设SUT 参数的pi(i=1，2，…，n)，可以表示配置参数、用户输入等.参数或它们之间的相互作用可能会影响SUT.另外，假设参数pi有来自有限集合Vi的ai个离散取值.参数间的相互作用实际上是参数值的组合所产生的交互.当这些参数的特定值一起作用时，可能会触发软件故障.为了更好地说明本文的工作，下面给出组合测试相关的定义.

定义1 值模式：对于SUT，n元组（-，，...)被称为t值模式（t＞0），其中t个参数有确定的值，而其他参数可以使用它们各自的允许值（可以表示为“-”）.当t=n时，n元组内每个参数都有确定的值，即为SUT 的测试案例［17］.

定义2 测试套件：根据组合覆盖准则生成的测试套件是多个测试案例的集合.每个测试案例tc可以是n元组，表示为(v1，v2，...，vn)(v1∈V1，v2∈V2，...，vn∈Vn).

定义3 t-way 组合覆盖：如果一个测试套件包含任意t个参数值的所有组合()，其中1 ≤t≤n，即包含所有的t值模式，则可以认为它满足t-way 组合覆盖.

定义4 SUT 模型：SUT 模型可以表示为一个4 元组：ModelSUT(P，V，R，C)，其中P是参数的集合，V是参数的取值集合，R是参数间交互关系的集合，C是不同参数值之间的约束集合.

2.2 决策树等价

决策树（Decision Tree，DT）可以表示为（N，E），由节点N和节点之间的边E组成.节点可分为决策节点和叶节点.一个决策节点代表一个决策（即一个关系方程）.每个叶节点代表一个分类，可以是一个离散的输出值.树的根节点是一个只有输出边的决策节点.

定义几个函数以便后续解释决策树等价关系.函数Rn：DT →N，返回决策树的根节点，并将整个决策树DT 考虑为输入域.函数Rc：DT →D∪C，返回一个节点的内容，范围是决策集合D和分类集合C的并集.函数Rl：DT →C，返回决策树所有叶子节点的内容，即分类.决策的结果由边的标签表示，通过函数Re：E→{T，F}访问.

文献［18］给出了5 种决策树等价关系的定义.本文中，引入结构等价和误分类等价来约简测试套件.注意，结构等价关系是误分类等价关系的一个子集.

1）结构等价：两个决策树DT1=(N1，E1)和DT2=(N2，E2)在结构上是等价的，当且仅当每一个节点n1∈N1有一个对应的节点n2∈N2，每一个边e1∈E1有一个对应的边e2∈E2，且对应边两端的节点是一一对应的.结构等价可以用函数EQUAL：N×N→{True，False}表示.对于两个决策树DT1、DT2，节点n1∈N1、n2∈N2，函数EQUAL 输出True，当且仅当：

①Rc(n1)=Rc(n2)（即相应节点的内容必须是一致的）

②|{(n1，m1)|m1是n1的子节点}|=|{(n2，m2)|m2是n2的子节点}|（即边的数量相当）

③∀(n1，m1)∃(n2，m2)，使得［（m1是n1的子节点）∧（m2是n2的子节点）∧(Re(n1，m1)=Re(n2，m2))∧EQUAL(m1，m2)]成立（即相应的输出边、子决策树必须是等价的）

否则，EQUAL 函数返回False.利用该函数，两个决策树的结构等价定义如下：

定义 5 结构等价：两个给定的决策树DT1，DT2是结构等价的，当且仅当函数EQUAL(Rn(DT1)，Rn(DT2))返回True.

图3 显示了两个在结构上等价的决策树.注意，两个决策树在相同位置的节点内容和边的标签是相同的.

图3 结构等价和误分类等价Fig.3 Structural equivalence and misclassification equivalence

2）误分类等价.误分类率（Misclassification Rate，MR）是误分类等价关系的基础，所以在引入误分类等价之前定义MR.

定义6 误分类率：决策树（N，E）的误分类率为误分类样本数与所有分类样本数之比.即错误分类的样本集的大小MDS ⊂DS 与初始数据集的大小之比.

两个决策树DT1=(N1，E1)和DT2=(N2，E2)是误分类等价的，当且仅当(N2，E2)误分类率小于或等于的误分类率(N1，E1)，并且相应分类集合C包含的元素一致.

定义7 误分类等价：当对数据集DS 进行分类时，决策树DT2=(N2，E2)与参考决策树DT1=(N1，E1)误分类等价，当且仅当

假设DS 包含两个样本s1=(8，10，2) 和s2=(2，5，2)，那么图3 误分类等价中的两个决策树误分类等价，但在结构上不是等价的.

2.3 测试套件约简算法

所提出的测试套件约简算法在很大程度上依赖于决策树推理和等价关系.在本文中，应用了广泛使用的CART 算法［19］，从数据集推理出决策树，并且采用结构等价和误分类等价来判断决策树是否等价.

该算法的约简策略是通过等价关系不断判断分别从初始数据集DS 和约简后数据集（Reduced Data Set，RDS）学习到的两个决策树模型是否等价，直到满足设置的条件为止.如果它们相等，表示测试套件TS（对应于DS）和约简后的测试套件（Reduced Test Suite，RTS）（对应于RDS）具有相同的能力覆盖系统的某些特征，那么RDS 继续随机删除一个样本s，否则重新添加s并随机删除另一个样本.注意，开始时RDS 和DS 是相同的.

此外，本文算法是对文献［21］所提算法的改进，特别是保证尽可能地最小化TS.为了达到更好的约简效果，算法中有两个循环.单次外层循环是一个完整的约简过程，会保持更新best RDS 以便取得尽可能小规模的测试套件.此外，在内层循环中，设置了DDS 记录所有可能被删除的样本.决策树是通过计算熵来构造的，反映了数据集中的某种平衡.由于在该算法中，一次最多删除一个样本，所以存在这样一种可能性：为了保持平衡，一些样本只能在其他样本被删除后才被删除.因此，每当两个决策树模型等价时，DDS 被更新为与RDS 一致，以尽可能地去除冗余样本.对内层循环的退出条件进行改进，将其设置为对剩余样本遍历判断后均无法删除.在该算法中，DS 是对应于TS 初始数据集，Iterations 声明了约简的迭代次数，FTS 是最终约简后的组合测试案例套件，M是TS 杀死的变异体集合.假设较约简前，初步约简后测试套件未杀死变异体个数为|Mu|，则补充的测试案例的个数不超过|Mu|，即可保证约简前后杀死变异体个数一致.

3 组合测试案例套件约简实验

CBTC 列控TSM 功能的组合套件约简过程如图4 所示，主要分为组合测试案例套件生成、数据预处理、测试套件约简、约简实验结果分析与比较4部分.

图4 组合测试案例套件约简流程Fig.4 Combinatorial test suite reduction process

3.1 组合测试案例套件生成

本部分主要对前期组合测试案例套件生成实验进行补充说明.本文所研究的SUT 指的是在CBTC列控车载安全计算机上运行的核心软件.车载设备有多种工作模式，其中CBTC-CM：受控人工驾驶（Code Train Operating Mode）具有最完整的速度监控功能（包括TSM）.因此，前期实验都是在CM 模式下进行的.

结合“城市轨道交通CBTC 信号系统-ATP 子系统规范”［20］，采用等价类划分和边值分析等方法，提取SUT 中涉及速度监控功能的参数及取值，如表1 所示（为了更简洁地描述测试套件生成过程，参数值仅用符号代替）.SUT 模型中，参数R的取值为2-way、3-way、4-way，且参数C暂不被考虑.基于SUT 模型和文献［21］所提出的经典的IPOG 算法，生成初始组合测试案例套件.之后，使用TS 对SUT 进行测试，并取得系统相应的输出结果.

表1 SUT 模型相关参数及取值Tab.1 SUT model related parameters and values

此外，为衡量测试套件的故障检测能力，引入了变异测试并生成了3 126 个变异体.在组合测试过程中，如果变异前后SUT 的输出不一致，可以认为对应的变异体被杀死，相反则是存活的.变异覆盖率（Mutation Coverage Rate，MCR）定义为

MCR 值越大，对应测试套件的故障检测能力越强.初始组合测试案例套件相关的数据如表3 所示.

表2 测试案例Tab.2 Test cases

表3 初始组合测试案例套件的相关信息Tab.3 Information about the initial combinatorial test suite

3.2 数据预处理

在前期实验中，收集初始组合测试案例套件在SUT 上的测试结果.结合SUT 规范和工作模式等信息，对结果进行分析，分为：触发紧急制动（O1）、触发常用制动（O2）和无制动触发（O3）三类标签.即当组合测试案例套件作为SUT 的输入时，这三类标签可象征SUT 的输出，形成标签数据集LDS.最后，结合TS 和相应的LDS，构建一个数据集DS，用来推理决策树模型.

3.3 组合测试案例套件约简

在约简实验中，使用前文中提出的约简算法和CPU 为i5-4210U CPU、内存为4G 的笔记本电脑作为实验平台.约简实验的可配置参数是t-way 组合覆盖、决策树等价关系和算法迭代Iterations.相关参数的具体取值如下t-way 取2，3，4；Iterations 取1～5.结构等价和错误分析等价.由于约简算法是随机删除冗余测试案例，约简结果具有不确定性，为了保证实验结果的可靠性，论文针对不同类型的配置进行了100 次重复实验.

3.4 约简实验结果分析与比较

在本文中，t-way-s 和t-way-m 分别代表了两种不同的约简类型，即结构等价和误分类等价在最小化满足t-way 组合覆盖的初始测试套件中的应用.

1）测试套件规模：组合测试案例套件的规模在缩减后发生了变化.为了衡量这种变化的程度，定义约简率（Reduction Rate，RR）为

式中：TS 是初始测试套件；RTS 是约简后测试套件.

约简实验得到的结果如图5 所示.一般情况下，在相同的条件下，Iterations（迭代次数）值越大，约简算法的循环次数越多，得到的RR 越高.当然，迭代的值并不需要很大，就可以得到一个较高的约简率.此外，初始组合测试案例套件的大小（与t-way 覆盖相关）与约简程度之间存在正相关关系.这是因为在大规模测试套件中出现冗余测试案例的可能性更大.

图5 关于约简率的实验结果Fig.5 Experimental results on reduction rate

在约简实验中，基于误分类等价的约简结果往往优于基于结构等价的约简结果.在不考虑剪枝的情况下，基于不同等价关系得到决策树模型DT2 与初始决策树模型DT1，在输入输出关系上一致（TS作为输入情况下）.然而，通过结构等价得到的模型DT2-s 的结构与DT1 完全一致，而通过误分类等价得到的模型DT2-m 的结构与DT1 并不要求相同.因此，在约简实验中，模型DT2-m 越容易被推理出现，测试案例被约简的概率越大，相应的约简程度也越高.

2）t-way 组合覆盖率.由于某些参数之间没有交互作用，优化后的组合测试案例套件可能不会有100% 的t-way 组合覆盖率（Combination Coverage Rate，CCR）.但是，CCR 作为组合测试衡量测试套件覆盖率的特定指标，仍然具有一定的参考意义，其定义如下

式中：VSTS指的是TS 里包含t值模式；TS 是初始测试套件；RTS 是约简后测试套件.

约简前后CCR 的变化如图6 所示，约简后测试套件的CCR（1-way）仍然是100%.此外，CCR（3-way）和CCR（4-way）都有很大的损失，这是由于大规模删除冗余测试案例造成的.值得注意的是，当约简类型为4-way-s 或4-way-m 时，对应的CCR（2-way）基本保持在100%左右，这反映经过约简算法得到测试套件仍然具有一定完整的低层次的组合覆盖能力.

图6 t-way 组合覆盖率的变化Fig.6 Changes in t-way combination coverage rate

3）故障检测能力.在实验中，约简后的测试套件被用来测试已植入变异体的SUT.为了更直观地衡量约简前后测试套件故障检测能力的变化，计算各种约简类型对应的MCR 值，见表4.

表4 测试套件的变异覆盖率Tab.4 Mutation coverage rate of test suite %

当约简后测试套件的MCR 值最优时，可以与初始组合测试案例套件TS 对应的值一致.当约简类型为t-way-s 时，约简后测试套件的MCR 值更高.这是由于结构等价关系是误分类等价关系的一个子集，前者要求更严格，更完整地保留了测试套件的故障检测能力.在约简实验中，约简后测试套件的MCR 损失不超过3.62%，为了使MCR无损失，根据初步约简后测试套件未杀死的变异集合，获取约简前后损失的样本集合，进一步获取可完全覆盖M的样本集合，可保证约简前后杀死变异体个数一致，这表明本文的组合测试案例套件约简算法在一定程度上是有效的.