列控中心自动化测试测试用例生成方法

王 硕，张亚东，郭 进，李 耀，兰 浩

(1.西南交通大学 信息科学与技术学院，成都 611756；2.电子科技大学 光电科学与工程学院，成都 611731)

列控中心(Train Control Centre, TCC)是高速铁路CTCS-2(Chinese Train Control System Level 2)和CTCS-3(Chinese Train Control System Level 3)级列控系统核心的地面设备之一，主要完成轨道电路编码、区间信号机点灯控制、区间方向控制等安全苛求功能.其功能逻辑的失效将危及行车安全，造成严重的事故.为了保证TCC功能的安全性，在投入使用前必须进行一系列严格的测试.近年来，随着自动化测试的兴起，我国主要TCC厂家陆续研发了自动化测试平台，但自动生成测试用例的问题仍未得到有效解决，成为TCC自动化测试的瓶颈.

基于模型的测试(Model Based Testing，MBT)通过建立被测系统或所处环境的模型设计或执行测试用例，实现软件或系统的测试[1].MBT生成测试用例的一般流程为：

1)基于测试需求和测试计划建立测试模型；

2)利用模型生成抽象测试用例，形成抽象测试集；

3)将抽象测试集中的抽象测试用例转化为可执行测试用例，形成可执行测试集[1].近年来，MBT方法被引入到列控系统设备测试中，文献[2-3]利用有色Petri网分别对车地通信和车载模式转换场景生成测试用例.文献[4-7]利用UPPAAL建立相应的时间自动机模型，结合CoVer工具自动生成测试用例集.文献[8]利用输入等价类划分测试理论建立有限状态机，通过W-method生成测试用例集.文献[2-8]所生的测试集为抽象测试集，实际应用时仍需将其实例化为可执行测试集.文献[9]提出了一种输入空间划分和逻辑覆盖相结合的抽象测试用例实例化方法.

以上研究在测试用例生成方面做了大量工作，但均未考虑接口通信时机的问题，无法满足TCC自动化测试的需求.因为在自动化测试中，为了实现测试连续自动的执行，测试用例不仅需要提供通信的数据内容，还需提供通信的时机.此外，对于TCC中带有时间约束的功能场景，通信时机也是对时间特性的测试.

基于此，本文作者提出带有输入输出时间的确定性有限状态机(Deterministic Finite State Machine with Input and Output Time，DFSM-T)来实现通信时机的表达，并对其搜索测试路径.再利用边界值分析及控制条件覆盖测试生成算法(Test Generation Algorithm of Control Condition Coverage，CGA)生成带有通信时机的测试用例，形成可执行测试集，以满足TCC自动化测试的需求.

1 模型与测试路径

1.1 DFSM-T模型定义

为了更好的描述通信时机和通信内容，扩展了 确定性有限状态机(Deterministic Finite State Machine，DFSM)的输入输出动作，提出了DFSM-T模型.

定义1(DFSM-T) 一个DFSM-T是一个6元组(S,s0,I,O,δ,λ)，其中：S是有限状态集合;s0是其中的初始状态；I是有限输入集合，其中每个输入in=(a，G(x))是一个二元组，a表示输入的内容，G(x)表示输入的时机，用于描述相对上一次交互的时间约束；O是有限输出集合，其中每个输出out=(a′，G′(x))是一个二元组，a′表示输出的内容，G′(x)表示输出的时机，用于描述相对上一次交互的时间约束；δ：S×I→S是一个变迁函数；λ：S×I→O是一个输出函数.

I、O中的G(x)用于描述当最近的一次输入或输出完成后，时间x应满足的时间约束.有9种表达形式，分别为xn，x≥n，x=n，x≥m&&x≤n，x>m&&x≤n，x≥m&&xm&&xm.例如in=(a，x

由于DFSM-T的输入输出集中在变迁上，因此对DFSM-T的覆盖准则采用DFSM中常用的变迁覆盖准则[10].变迁覆盖准则是指由变迁构成的测试路径集合覆盖DFSM-T中的所有变迁至少一次.

1.2 DFSM-T模型构建

定义2(数据块) 数据块DB是一个二元组(L,S)，其中L={l(c1),l(c2),…,l(cn)}，是一组有序变量的标识，l(ci)是变量ci的唯一标识；S={V1(L),V2(L),…,Vm(L)}是有序取值组序列，其中每个取值组Vj(L)={v(c1),v(c2),…,v(cn)}是与L中变量顺序相对应的一组变量取值.

在建模过程中，输入输出的内容用DB表示.则DFSM-T模型的每个变迁表示在某个通信时机输入某个数据块中的一个取值组；然后在某个通信时机输出某个数据块中的一个取值组.

根据被测设备的通信接口协议，归纳出影响功能场景的数据块，并根据经验将最有利于发现其他条件对功能影响的取值(控制条件取值)组置于取值组序列的第1个位置.例如在测试某个选定轨道电路对其所处闭塞分区的影响时，需要将非选定轨道电路置于空闲状态，以便于测试选定轨道电路对其所处闭塞分区的影响.

为了直观的阐述DB和模型，对某抽象测试场景的DB进行归纳如表1所示，建立的DFSM-T模型如图1所示.其中，变迁上“/”左侧表示输入，右侧表示输出，默认通信时机为x=T(被测设备通信周期)，null表示输入或输出的动作为空.

表1 抽象测试场景的数据块

1.3 测试路径搜索

广度优先搜索(Breadth-First Search, BFS)和深度优先搜索(Depth-First Search, DFS)是常用的测试路径搜索算法[10].但由于深度优先搜索需要不断的回溯，以确定下一节点是否已被访问.因此，本文采用广度优先搜索对DFSM-T模型搜索测试路径，并使测试路径集合满足变迁覆盖准则，即覆盖DFSM-T模型的所有变迁至少一次.但经典BFS算法会因模型中存在自环变迁而使得某些测试路径的冗余程度较高.例如图1的模型利用BFS算法生成两条测试路径如图2所示.因模型中存在自环变迁使得两条测试路径前3个变迁是相同的，导致两条测试路径冗余程度很高.

针对该问题，提出改进BFS算法，算法具体描述如下.

输入：DFSM-T模型.

输出：满足变迁覆盖准则的测试路径集合.

1)去除DFSM-T模型中所有的自环变迁，并生成自环变迁集合L；

2)利用广度优先搜索对去除自环变迁的DFSM-T模型搜索测试路径，生成测试路径集合P；

3)对于L中的每个自环变迁，在P中搜索包含自环变迁所在状态的变迁且路径长度最短的测试路径，将自环变迁插入到该测试路径的相应位置；

4)返回插入自环变迁的测试路径集合P.

图1模型利用改进BFS生成的测试路径集合包含1条测试路径，如图3所示，该条测试路径覆盖了图1模型的所有变迁，能够替代图2中两条冗余程度较高的测试路径，减小了测试路径集的规模.

2 测试用例生成

在测试用例生成过程中，首先把测试路径中的时间约束离散化.然后，根据控制条件覆盖准则，利用CGA生成带有通信时机的测试用例.

2.1 时间约束的边界值分析

G(x)是对时间范围的约束，利用边界值分析，将时间约束离散化.边界值分析的基本思想是利用输入变量的最小值、略大于最小值的值、正常值、略小于最大值的值和最大值处的取值进行测试[11].由于TCC具有固定的运算周期，利用边界值分析思想，将时间约束离散化为运算周期的个数，提出G(x)中9种形式时间约束的离散取值，如表2所示.

表2 时间约束的离散取值

表2中M=m/T取整，N=n/T取整，m、n为时间取值且n>m.此外，下划线标记的取值是边界值分析中的控制条件取值.例如对于xn，由于不存在最大周期数，因此只取最小周期数N+1和正常周期数2N+1.

图3测试路径中从s3到s0的变迁中存在x≤3T的时间约束，其N=3，离散化取值得到T，2T，3T三个取值，其中2T为控制条件取值.

2.2 控制条件覆盖与算法

修正判定条件覆盖(Modified Condition Decision Coverage, MC/DC)，在每个判定中的每个条件都曾独立影响判定的结果至少一次(独立影响的意思是在其他条件不变的情况下，改变一个条件)[12].例如，(A||B&&C)，如果B对结果独立起作用，A必须为False、C必须为True，则B取True和False各一次对结果起独立影响.MC/DC测试已被广泛应用于列控系统设备软件的白盒测试过程中，其优势在于用很少的用例测试每个条件独立对结果的影响.

在黑盒测试中，由于不能准确获取判定条件的逻辑关系，无法应用MC/DC测试.但借鉴MC/DC测试的思想，当测试某选定条件对功能的影响时，控制其他条件处于有利于发现选定条件对功能影响的状态.

定义3(控制条件覆盖)在测试过程中，受多个条件影响的功能，每次只改变其中某一个条件的取值，而控制其他条件的取值保持不变，从而测试选定条件对功能相对独立的影响，将这种测试覆盖准则称为控制条件覆盖.

设测试条件有n个，为C={c1,c2,…，cn}，每个条件ci可在离散序列Si中取值，取值个数为mi=|Si|.其中，每个条件的控制条件取值位于Si的第1个位置.此外，每个ci具有一个标识，用于标记该条件的取值是否在其他情况下已被覆盖.CGA的具体步骤描述如下.

输入：n个测试条件C.

输出：n个测试条件的取值组集合G.

1)将每个测试条件的控制条件取值(即Si的第1个取值)组成一个取值组，加入G；

2)对于C中的每个测试条件ci，如果该测试条件尚未被覆盖，则对于Si中的每个非控制条件取值，与其他测试条件的控制条件取值构成一个取值组，加入G；

3)返回n个测试条件的取值组集合G；

2.3 算法的应用

对测试路径中的每个变迁，输入动作需要转换为具体的输入时间和接口数据，作为被测设备的激励；而对于输出动作则无需转换，因为输出动作用于测试结果的检查，被测设备的输出结果只需符合输出动作的时间约束和内容即可.

将输入动作的内容作为一个条件，同时输入动作中时间约束作为另一个条件，利用CGA生成每个变迁的输入取值组集合.例如图3中，变迁s3→s0生成的输入取值组集合包含4个取值组，分别为1,0,2T，1,0,T，1,0,3T和0,1,2T.

将测试路径中每个变迁的输入取值组集合作为条件，再次利用CGA即可生成测试路径的可执行测试用例.根据图3的测试路径中每个变迁的输入取值组集合，利用CGA生成4条测试用例，其中第1条测试用例的输入部分如表3所示，另外3条测试用例仅为s3→s0的输入取值组不同.

表3 测试用例举例

3 实例分析

区间改变运行方向是TCC的重要功能之一，实现控制本站发车口到相邻主站对应发车口之间的运行方向.其中，在正常改变运行方向过程中分为接车方向改为发车方向(简称正改方)和发车方向改为接车方向(简称反改方)两个场景.下面以正改方场景为例，对本文方法进行验证.

3.1 正改方场景的DFSM-T模型

根据列控中心技术条件对正改方场景的功能需求以及接口规范对接口数据的描述，对正改方涉及的DB进行归纳，每个DB的具体含义及包含的取值组数量如表4所示.其中选取db9举例展示其所包含的取值组具体内容，如表5所示.

表4 数据块含义

表5 数据块内容举例

根据正改方场景的工作流程，建立DFSM-T模型如图4所示.其中共包括5个状态，s0～s4分别表示接车方向、等待联锁的方向控制命令、等待邻主站改方、等待本站及所辖中继站改方、发车方向状态.

3.2 正改方场景的测试路径

利用改进BFS搜索正改方DFSM-T模型，共生成10条测试路径，测试路径及每条路径所表达的含义如下：路径s0→s1→s0：所辖中继站非空闲，改方失败；s0→s1→s0：所辖区段非空闲，改方失败；s0→s1→s0：所辖中继站通信中断，改方失败；s0→s1→s0：主站间通信中断，改方失败；s0→s1→s0：所辖中继站有进路，改方失败；s0→s1→s0：主站有进路，改方失败；s0→s1→s0：邻主站非空闲，改方失败；s0→s1→s2→s0：邻主站拒绝改方请求，改方失败；s0→s1→s2→s3→s0：驱动改方超时，改方失败；s0→s1→s2→s3→s4→s4：改方成功.

3.3 正改方场景的测试用例

根据测试路径1～10，利用CGA分别生成可执行测试用例1、21、1、1、1、1、3、7、10、3条.其中以路径10所生成的可执行测试用例为例进行展示见表6.

表6 路径10的测试用例

表6中，每条测试用例的一行表示一次测试输入和测试输出；“-”表示本次输入输出未涉及或是不改变的接口数据；时间表示相对上一次测试输入或测试输出完成后的间隔时间.表6中3条测试用例交互的接口数据是相同的，不同之处在于第4个变迁中，相关继电器在13 s内动作到位的时间约束产生了0.5、7、13 s 三种不同的通信时机.

此外，依据文献[13]，本文所生成的可执行测试集满足其中对正改方场景的测试需求.

3.4 方法有效性分析

本文方法与现有方法相比，其优势在于所生成的测试用例不仅表达了接口通信的内容，同时提供了接口通信的时机，这使得自动化测试环境能够在特定的时间交互特定的内容，满足自动化测试的需求.同时，将通信时机作为一个测试条件，能够对被测系统的时间特性进行充分测试.

4 结论

1)为了描述接口通信的时机，提出DFSM-T模型，使得模型既能表达输入输出的内容，也能表达通信的时间约束.

2) 利用边界值分析，将通信的时间约束离散化，既能提供通信时机，同时也能对功能场景的时间特性进行充分测试.

3) 控制条件覆盖准则能测试选定条件对功能相对独立的影响，能覆盖影响功能场景的每个条件.

4) 利用本文方法生成的测试用例，既能表达通信内容也能表达通信时机，满足自动化测试的需求.

本文方法在归纳构造DB时依赖专家经验，且工作量相对较大，在这些方面还有待进一步研究.