专利摘要

本发明涉及一种高速列车运行控制系统功能的动态测试方法，属于高速列车运行控制系统技术领域。本方法首先根据高速列车运行控制系统功能规范基于参数化自动机模型构造被测高速列车运行控制系统的动态测试模型；然后依据该模型对被测高速列车运行控制系统执行动态测试过程。动态测试方法是一个由“生成待测转移的测试序列”、“执行测试序列”、“测试结果分析”、“动态测试模型参数更新”四个步骤组成的循环过程。本发明方法避免了在高速列车运行控制系统测试执行之前生成一个固定测试序列集，解决了传统静态测试方法测试覆盖率低和测试结果准确率低以及传统动态测试方法测试序列生成代价和执行代价大的问题。

说明书

技术领域

本发明涉及一种高速列车运行控制系统功能的动态测试方法，属于高速列车运行控制系统技术领域。

背景技术

高速列车运行控制系统功能测试主要目的是验证被测高速列车运行控制系统是否符合系统功能规范。传统的高速列车运行控制系统功能测试以静态测试方法为主，在测试时遇到了测试覆盖率低、测试结果准确率低等问题，针对静态测试方法的问题，一些学者在协议一致性测试领域中率先提出了动态测试方法，动态测试方法通过测试执行之前生成一个更大规模的待选测试序列集，在测试执行的时候根据已执行的测试序列和测试结果动态地选择下一个要执行的测试序列，以提高测试的覆盖率和测试结果的准确率。在测试执行过程中，测试序列的选取不仅和已经执行的测试序列相关，还和已检测到的缺陷相关。现有的动态测试方法主要存在测试序列生成开销大，测试序列执行开销大等问题。

发明内容

本发明的目的是提出一种高速列车运行控制系统功能的动态测试方法，通过基于参数化自动机模型建立高速列车运行控制系统的动态测试模型，在执行测试过程中动态生成测试序列，并执行测试，提高测试覆盖率，并使测试结果更准确，而且测试序列生成和执行的开销小，便于实现。

本发明提出的高速列车运行控制系统功能的动态测试方法，包括以下步骤：

(1)建立一个高速列车运行控制系统功能的测试模型：A_p＝(M，W，B)，其中，

M为根据高速列车运行控制系统的功能规范构造的有限状态自动机，

W是有限状态自动机M的状态转移权重向量，用于表示动态测试过程中状态转移的执行代价，W＝[w₁，…，w_i，…，w_n]，其中，n是状态转移个数，w_i表示状态转移t_i的执行代价，定义：正常状态转移的执行代价为1，错误状态转移的执行代价为∞，有限状态自动机M的初始权重向量为W＝[1，…，1，…，1]，

B是有限状态自动机M的状态转移标识向量，B＝p[b₁，…，b_j，…，b_n]，b_j为{-1，0，1}中的一个值，定义b_j＝0，表示状态转移t_j已经被测试过，且可根据测试结果判断状态转移t_j的正确性，b_j＝-1，表示状态转移t_j已经被测试过，且不可根据测试结果判断状态转移t_j的正确性，b_j＝1表示状态转移t_j未被测试过，有限状态自动机M的初始标识向量为B＝[1，…，1，…，1]；

(2)将上述根据高速列车运行控制系统的功能规范构造的有限状态自动机M作为高速列车运行控制系统功能动态测试的参考模型；

(3)根据上述测试模型，对高速列车运行控制系统的功能进行动态测试，包括以下步骤：

(3-1)根据有限状态自动机M中状态转移引导序列的长度，对所有状态转移由短到长依次进行编号，得到t₁，t₂，…t_n；

(3-2)从对高速列车运行控制系统的功能进行动态测试开始至测试结束，依次进行：

(3-2-1)在测试过程的时刻k生成一个测试序列ts_k＝ts_pre；t_k；ts_post，其中t_k为被测状态转移，ts_pre为被测状态转移t_k的引导序列，ts_post为被测状态转移t_k的尾状态验证序列，

(3-2-2)根据上述测试序列，分别向上述参考模型和被测高速列车运行控制系统输入与功能测试相关的信号，分别得到参考模型的测试输出o₁，…，o_l，…，o_m和被测高速列车运行控制系统的测试输出

(3-2-3)将上述参考模型的测试输出o₁，o₂，…，o_m与被测高速列车运行控制系统的测试输出 进行比较：

若参考模型的测试输出与被测高速列车运行控制系统的测试输出相同，则判断被测状态转移为正确；

若参考模型的测试输出与被测高速列车运行控制系统的测试输出不相同，则对测试序列ts_k进行错误定位，得到被测状态转移的判断结果；

(3-2-4)根据上述判断结果，若被测状态转移为正确，则被测状态转移的权重值不变，并将被测状态转移的标识值赋值为b_k＝0，若被测状态转移为错误，则将被测状态转移的权重值赋值为无穷大w_k＝∞，并将被测状态转移的标识值赋值为b_k＝0，若被测状态转移为不可根据测试结果判断状态转移的正确性，则被测状态转移的权重值不变，并将被测状态转移的标识值赋值为b_k＝-1；

(3-2-5)若所有被测的状态转移标识值均为0，或对标识值不为0的被测的状态转移已经不存在可执行测试序列，则停止动态测试过程。

上述方法中，若参考模型的测试输出与被测高速列车运行控制系统的测试输出不相同，则对测试序列进行错误定位，错误定位方法包括以下步骤：

(1)定义：参考模型的测试输出与被测高速列车运行控制系统的测试输出不一致的情况为一个症状，即 从一个测试序列ts_k中识别出所有症状，得到一个症状集为：

S_k＝{s_k，1，…，s_k，g，…s_k，h}；

(2)对上述症状集中的每个症状s_k，g： 确定相应的冲突集为：

C_k，g＝{c¹_k，g，…，c^u_k，g，…，c^p_k，g}；

其中，c^u_k，g是一个冲突，冲突的定义为：被测高速列车运行控制系统的一个功能与参考模型中相应的状态转移不相符；

(3)根据上述冲突集得到测试序列ts_k的初始诊断候选集IDS：

IDS_k＝C_k，1∩C_k，2∩…∩C_k，h

根据冲突c^u_k，g中状态转移的历史输出，删除上述初始诊断候选集IDS中与历史输出不相符的诊断候选，并根据冲突cⁱ_k，g中状态转移的历史尾状态，删除上述初始诊断候选集IDS中与历史尾状态不相符的诊断候选，得到最终诊断集FDS，若最终诊断集FDS中存在一个诊断候选，则判断该诊断候选中包含的状态转移为错误，若最终诊断集FDS中存在多个诊断候选，则不可根据测试结果判断状态转移的正确性，采用产生症状的状态转移序列t_k，v，t_k，v+1…，t_k，v+j描述测试序列的错误信息，定义产生症状的状态转移序列Fss_k＝t_k，v，t_k，v+1…，t_k，v+j为错误子序列；

(4)若不可根据测试结果判断状态转移的正确性，则将上述错误子序列添加到错误子序列集合中：

FssS_k＝FssS_k-1∪{Fss_k}。

本发明提出的高速列车运行控制系统功能的动态测试方法，与现有的高速列车运行控制系统静态测试方法和其他领域的动态测试方法相比，具有以下优点：

1、本发明的高速列车运行控制系统功能的动态测试方法，在执行测试过程中为待测试的状态转移动态地生成测试序列。这种测试序列生成方式在增大测试序列可选范围的同时，有效地克服了传统动态测试方法需要在测试开始之前生成各个状态转移的所有可执行测试序列所造成的测试序列生成开销大的问题。

2、本发明的高速列车运行控制系统功能的动态测试方法中，错误定位是一个增量过程，在对一个状态转移进行测试的时侯不需要对该待测转移进行穷举测试，而是通过测试序列执行的过程不断地更新错误定位结果。每次错误定位的信息用来更新高速列车运行控制系统动态测试模型的参数，以标识每次执行测试之后的测试结果信息。通过该方法进一步减小了测试结果误判断的可能，同时有效地减小了测试序列执行开销。

附图说明

图1状态转移编号图例说明。

图2本发明方法提出的动态测试方法的流程框图。

图3车载设备模式转换的有限状态自动机模型。

具体实施方式

本发明提出的高速列车运行控制系统功能的动态测试方法，其流程框图如图2所示，包括以下步骤：

(1)建立一个高速列车运行控制系统功能的测试模型：A_p＝(M，W，B)，其中，

M为根据高速列车运行控制系统的功能规范构造的有限状态自动机，

W是有限状态自动机M的状态转移权重向量，用于表示动态测试过程中状态转移的执行代价，W＝[w₁，…，w_i，…，w_n]，其中，n是状态转移个数，w_i表示状态转移t_i的执行代价，定义：正常状态转移的执行代价为1，错误状态转移的执行代价为∞，有限状态自动机M的初始权重向量为W＝[1，…，1，…，1]，

B是有限状态自动机M的状态转移标识向量，B＝[b₁，…，b_j，…，b_n]，b_j为{-1，0，1}中的一个值，定义b_j＝0，表示状态转移t_j已经被测试过，且可根据测试结果判断状态转移t_j的正确性，b_j＝-1，表示状态转移t_j已经被测试过，且不可根据测试结果判断状态转移t_j的正确性，b_j＝1表示状态转移t_j未被测试过，有限状态自动机M的初始标识向量为B＝[1，…，1，…，1]；

(2)将上述根据高速列车运行控制系统的功能规范构造的有限状态自动机M作为高速列车运行控制系统功能动态测试的参考模型；

(3)根据上述测试模型，对高速列车运行控制系统的功能进行动态测试，包括以下步骤：

(3-1)根据有限状态自动机M中状态转移引导序列的长度，对所有状态转移由短到长依次进行编号，得到t₁，t₂，…t_n，有限状态机的状态转移过程如图1所示，当多个状态转移的引导序列长度相同时，编号顺序任意，状态转移(2，4)和状态转移(3，5)的引导序列长度相同，因此编号为t₃的状态转移既可以是(2，4)也可以是(3，5)；

(3-2)从对高速列车运行控制系统的功能进行动态测试开始至测试结束，依次进行：

(3-2-1)在测试过程的时刻k生成一个测试序列ts_k＝ts_pre；t_k；ts_post，其中t_k为被测状态转移，ts_pre为被测状态转移t_k的引导序列，ts_post为被测状态转移t_k的尾状态验证序列，

(3-2-2)根据上述测试序列，分别向上述参考模型和被测高速列车运行控制系统输入与功能测试相关的信号，分别得到参考模型的测试输出o₁，…，o_l，…，o_m和被测高速列车运行控制系统的测试输出

(3-2-3)将上述参考模型的测试输出o₁，o₂，…，o_m与被测高速列车运行控制系统的测试输出 进行比较：

若参考模型的测试输出与被测高速列车运行控制系统的测试输出相同，则判断被测状态转移为正确；

若参考模型的测试输出与被测高速列车运行控制系统的测试输出不相同，则对测试序列tsk进行错误定位，得到被测状态转移的判断结果；

(3-2-4)根据上述判断结果，若被测状态转移为正确，则被测状态转移的权重值不变，并将被测状态转移的标识值赋值为b_k＝0，若被测状态转移为错误，则将被测状态转移的权重值赋值为无穷大w_k＝∞，并将被测状态转移的标识值赋值为b_k＝0，若被测状态转移为不可根据测试结果判断状态转移的正确性，则被测状态转移的权重值不变，并将被测状态转移的标识值赋值为b_k＝-1；

(3-2-5)若所有被测的状态转移标识值均为0，或对标识值不为0的被测的状态转移已经不存在可执行测试序列，则停止动态测试过程。

本发明用来描述高速列车运行控制系统功能规范的有限状态自动机有如下的定义和形式：

一个典型的有限状态自动机定义为一个6元组

M＝(Q，q₀，Q_m，∑，Λ，δ，λ)

其中：

Q为有限状态自动机的状态集合；

∑为有限状态自动机的输入字符集合，其中一个字符代表被建模系统一个输入事件；

A为有限状态自动机的输出字符集合，其中一个字符代表被建模系统一个输出事件；

q₀为有限状态自动机的初始状态；

δ为有限状态自动机的状态转移函数：δ：Q×∑→Q；

λ为有限状态自动机的输出函数：λ：Q×∑→Λ。

Q_m为有限状态自动机的标识状态集合，用来标识某个事件发生或者某个事件序列发生。

基于有限状态自动机模型对高速列车运行控制系统进行功能测试有如下假设：

假设1：对于有限状态自动机没有输出的状态转移认为输出为空，即输出是空事件ε。

假设2：令t₁：I₁/O₁，t₂：I₂/O₂是顺序发生的两个状态转移，I₁，I₂是状态转移的输入事件，O₁，O₂是状态转移的输出事件。四个事件之间有如下的时间上的偏序关系为I₁＜O₁＜I₂＜O₂，其中操作符“＜”表示事件发生的时间先后顺序，操作符左边的事件先于右边的事件发生。

假设3：设对应于被测高速列车运行控制系统功能规范的有限状态自动机模型是M，高速列车运行控制系统对应的有限状态自动机模型是M′，基于有限状态自动机模型生成测试序列的假设包括以下7个子假设：

(3.1)有限状态自动机M是全连通的，即M的状态转移图是全连通的；

(3.2)有限状态自动机M是最简有限状态自动机；

(3.3)有限状态自动机M′在测试过程中不会发生改变；

(3.4)有限状态自动机M′的输入字符集与有限状态自动机M的输入字符集相同；

(3.5)有限状态自动机M′的状态数不会超过有限状态自动机M的状态数；

(3.6)对于每个输入字符，如果被测系统产生输出，那么该输出在给定的时间内产生；

(3.7)测试输入信号是在被测系统的稳定状态施加的。

上述方法中，若参考模型的测试输出与被测高速列车运行控制系统的测试输出不相同，则对测试序列进行错误定位，错误定位方法包括以下步骤：

(2-1)定义：参考模型的测试输出与被测高速列车运行控制系统的测试输出不一致的情况为一个症状，即 从一个测试序列tsk中识别出所有症状，得到一个症状集为：

S_k＝{s_k，1，…，s_k，g，…s_k，h}；

(2-2)对上述症状集中的每个症状s_k，g： 确定相应的冲突集为：

C_k，g＝{c¹_k，g，…，c^u_k，g，…，c^p_k，g}；

其中，c^u_k，g是一个冲突，冲突的定义为：被测高速列车运行控制系统的一个功能与参考模型中相应的状态转移不相符；

(2-3)根据上述冲突集得到测试序列ts_k的初始诊断候选集IDS：

IDS_k＝C_k，1∩C_k，2∩…∩C_k，h

根据冲突c^u_k，g中状态转移的历史输出，删除上述初始诊断候选集IDS中与历史输出不相符的诊断候选，并根据冲突cⁱ_k，j中状态转移的历史尾状态，删除上述初始诊断候选集IDS中与历史尾状态不相符的诊断候选，得到最终诊断集FDS，若最终诊断集FDS中存在一个诊断候选，则判断该诊断候选中包含的状态转移为错误，若最终诊断集FDS中存在多个诊断候选，则不可根据测试结果判断状态转移的正确性，采用产生症状的状态转移序列t_k，v，t_k，v+1…，t_k，v+j描述测试序列的错误信息，定义产生症状的状态转移序列Fss_k＝t_k，v，t_k，v+1…，t_k，v+j为错误子序列；

(2-4)若不可根据测试结果判断状态转移的正确性，则将上述错误子序列添加到错误子序列集合中：

 FssS_k＝FssS_k-1∪{Fss_k}。

为了更好地说明错误定位方法中最短错误子序列获取过程，以下介绍错误子序列化简的相关结果：

对于错误子序列，有如下2个错误子序列化简规则：

规则1：令T是一个错误子序列，且|T|＞1(|T|代表错误子序列的长度，即其包含的转移的数目)。如果T＝t₁·T′，且t₁是一个正确实现的状态转移，则T′是比T短的错误子序列，且它们有相同的错误实现。

规则2：令T是一个错误子序列，且|T|＞1。如果T＝T′·t_l，且t_l是一个正确的实现的状态转移，则T′是比T短的错误子序列，且它们有相同的错误。

本发明中的最短错误子序列获取步骤如下：

(1)若执行测试序列并产生症状 其中 是第一个症状，且在执行状态转移t_k，i时观测到该症状，则t_k，1，t_k，2，…，t_k，i一定含有错误的状态转移，把t_k，1，t_k，2，…，t_k，i作为初始的错误子序列；

(2)使用错误子序列简化规则基于历史测试数据化简上述错误子序列，当错误子序列的头状态转移和尾状态转移都无法判定是否为正确的状态转移时，该子序列即为最短的错误子序列。

以下是本发明方法的一个实施例：本实施例通过高速列车运行控制系统车载设备模式转换测试说明本发明所述方法的优越性。本实施例对比了发明所述高速列车运行控制系统车载设备功能的动态测试方法和传统静态测试方法以及传统动态测试方法的测试性能。结合附图对车载设备模式转换动态测试过程说明如下：

1.建立一个高速列车运行控制系统车载设备功能的动态测试模型，A_p＝(M，W，B)，其中有限状态自动机模型M如附图3所示，M的状态以及输入输出事件说明如表1、表2和表3所示；A_p的初始状态转移权重向量为W＝[1，1，…，1]，初始状态转移标识向量为B＝[1，1，…，1]。

表1状态表

表2输入事件表

表3输出事件表

2.将上述根据高速列车运行控制系统车载设备的功能规范构造的有限状态自动机M作为高速列车运行控制系统车载设备功能动态测试的参考模型

3.根据上述动态测试模型，对高速列车运行控制系统车载设备的功能进行动态测试，过程如下：

假设车载设备的状态转移t8有尾状态错误(该状态转移被实现为t₈：δ′(s₆，I₈)＝s₂)，在该实现情况下车，循环执行(3-2-1)至(3-2-5)5个步骤，执行过程简述为：为所有状态转移进行编号，编号如图3所示；对于状态转移t₁，基于有限状态自动机M₀，使用UIO方法生成状态转移t₁的测试序列ts₁＝t₁，t₂，执行测试序列ts₁，没有发现症状，则说明状态转移t₁通过测试，进而状态转移t₁对应的标识值变为0，权重值不变，此后状态转移t₂，t₃，t₄，t₅，t₆，t₇也都通过了测试，此时参数化有限状态自动机模型状态转移的标识向量为B＝[0，0，0，0，0，0，0，1，1，1，1，1，1，1，1，1，1，1，1，1]，当测试状态转移t₈的时候，执行测试序列之后发现症状 对于该症状有多个诊断候选可以解释，例如DC_8，1： DC_8，2：δ(s₆，I₈)＝s₂等，因此，使用最短错误子序列描述被测车载设备的错误信息，初始的错误子序列是Fss₁＝t₁，t₇，t₈，t₂，因为状态转移t₁，t₂，t₇已经被测试过并且验证是正确的，使用错误子序列化简规则得到状态转移t₈是唯一的错误转移，且其输出为O₁，所以状态转移t₈是一个有尾状态错误的状态转移，根据该测试结果，状态转移t₈的权重值被设置为无穷，在接下来的测试中，不能生成包含该状态转移的测试序列。使用动态测试方法并不对被测试的状态转移t₈做穷举测试，而是通过推理得到错误信息，在接下来的动态测试过程中状态转移t₉，t₁₀，t₁₁，t₁₂，t₁₃，t₁₄，t₁₅，t₁₆，t₁₇，t₁₈，t₁₉，t₂₀，t₂₁都通过了测试。

在同样错误假设前提下，对比本发明的动态测试方法和传统的静态测试方法以及动态一致性测试方法(DCTM)，测试执行结果列在表4中。由于状态转移t₈是尾状态错误，所以并未影响静态测试的测试判断结果，但是对于DCTM动态测试方法，在状态转移t₈有尾状态错误时，不仅测试执行开销大，而且有错误判断的测试结果，这是因为当测试序列t₁，t₇，t₈，t₂没有通过测试时，需要对t₈进行穷举测试，同时当t₈被判断为“错误实现”后，转移t₁₅，t₁₆，t₁₇，t₁₈在测试树中已经没有可执行测试序列了，所以直接被判断为“错误实现”，显然这是虚假的测试结果。

表4当t₈错误时的实验结果

注：C表示测试执行代价；P表示通过测试的状态转移数；F表示未通过测试的状态转移数；W表示虚假的测试结果数；U表示无法测试到的状态转移数。

接着为高速列车运行控制系统车载设备的21个状态转移分别注入故障，通过仿真实验，得到被测高速列车运行控制系统车载设备在多种单错误情况下的实验结果，列在表5中。

表5单故障的实验结果

注：E表示平均值。I表示理想值。

根据故障注入仿真实验结果，从以下四个方面比较三种测试方法的测试性能：

1)测试执行开销

从实验结果可知，DCTM方法的平均测试开销最大。本发明的动态测试方法的平均测试开销和静态方法的平均测试开销比较接近。这是因为DCTM动态测试方法使用了穷举测试的测试结果判断策略，所以测试开销较大。

2)测试覆盖率

本发明的动态测试方法覆盖的状态转移数目是20.05，DCTM方法覆盖的状态转移数目是19.62，而静态测试方法覆盖的状态转移数目只有19.23。从仿真实验结果可知，本发明的动态测试方法测试覆盖率最高，比较接近理想值。DCTM动态测试方法由于采用了穷举测试的方法在一定程度上提高了测试覆盖率。静态测试方法的实际测试覆盖率最低。

3)虚假测试结果数

使用本发明的动态测试方法和DCTM动态测试方法，虚假测试结果数少于静态测试方法。本发明的动态测试方法由于采用增量测试错误定位方法，对无法判断是否错误的状态转移使用“不确定”作为测试判断的结果。

4)测试结果准确率

从仿真实验结果来看，使用本发明的动态测试方法得到的测试结果准确率最高(此讨论中认为标识“不确定”的被测状态转移也不是准确的测试结果)，这是因为本发明的动态测试方法使用增量的测试判断策略和错误定位方法。而静态测试方法由于对每个被测试的状态转移只有一个测试序列，所以一旦测试失败，对应的状态转移就被判定为“错误实现”。DCTM动态测试方法对一个待测状态转移只有它所有可执行测试序列都测试失败时，才给被测状态转移“错误实现”的测试判定。这虽然能在一定程度上提高测试的准确率，但是依然存在误判断的可能。例如当状态转移t₆是一个错误实现时，DCTM通过对状态转移t₆的穷举测试判定t₆为“错误实现”，根据DCTM测试方法状态转移t₁₉，t₂₀，t₂₁直接被判定为错误状态转移，这也是误判断的测试结果。

综上所述，本发明的动态测试方法具有比传统静态测试方法和DCTM动态测试方法更好的测试性能。本发明的动态测试方法基于高速列车运行控制系统参数化自动机模型在测试执行过程中动态地生成测试序列，并采用增量错误定位方法对错误进行增量定位，同时使用错误子序列描述局部错误定位信息，动态地更新系统参数化自动机模型的参数。本发明的动态测试方法在进一步提高测试结果准确率的同时，也保证了较小的测试执行开销，因此，本发明的方法是一种适合高速列车运行控制系统功能测试的较优的动态测试方法。

一种高速列车运行控制系统功能的动态测试方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。