基于有色Petri网的车载设备模式转换测试序列生成方法

赵晓宇，杨志杰，吕旌阳

(1.中国铁道科学研究院 研究生部，北京　100081；2.中国铁道科学研究院 通信信号研究所，北京　100081；3.中国铁道科学研究院 国家铁路智能运输系统工程技术研究中心，北京　100081；4.北京邮电大学 信息与通信工程学院，北京　100876)

CTCS-3级列控系统由车载设备和地面设备组成，属于典型的安全苛求系统。为了验证其行为功能的正确性，并保证不同厂家设备的兼容性，对其系统的功能进行测试成为必不可少的环节。如何高效地自动生成覆盖车载设备所有转换路径的测试序列，是目前车载设备模式转换测试的关键性问题。现有测试方法以人工测试和现场测试为主，测试时间较长，测试费用昂贵，导致测试效率较低，并且在很多情况下已经无法满足测试的需求。在这种背景下，自动测试方法应运而生。

针对车载设备模式转换功能的测试序列生成问题，李伟[1]将其转化为中国邮路问题[2]，使用遗传算法生成测试序列；张勇[3]采用Edmonds-Johnson算法及LINGO工具解决测试序列生成问题；但文献[1,3]都未涉及具体的测试序列生成过程，仅给出了车载设备模式转换的测试顺序。测试序列的合理性验证方面，张仕雄[4]对CTCS-3级列控系统测试序列的合理性进行了验证，但仅对序列合理性进行了初步分析。近年来，基于模型的测试方法[5-7]有效地融合了形式化方法与传统测试技术，在形式化建模方法的基础上，自动生成大量可靠的测试用例，提高了人工编写测试用例的效率，缩短了与自动化程度较高的测试执行过程的距离。基于模型的列控系统测试方面，赵显琼[8]针对多端口协同测试问题提出了端口标记的时间输入输出自动机(LpTIOA)；袁磊[9]提出了1种能够满足全状态、全变迁覆盖准则的测试套自动生成算法；并且文献[8—9]均通过UPPAAL和CoVer工具生成满足相应覆盖标准的测试套，但生成的测试套抽象层次太高，无法描述系统的并发行为；姜鹏[10]根据安全苛求攸关场景建模需求，扩充了UML的事件驱动机制和时间特性描述机制，并提出了1种面向安全攸关场景的测试用例自动生成方法，但UML无法描述系统的并发行为，不能进行模型检验，具有一定的局限性。

相对于其他形式化语言，有色Petri网(CPN)[11-13]具有直观的图形表示和严密的数学基础，在描述系统的分叉、同步和并行等行为、层次化建模及处理数据方面具有很大优势；牟小玲[14]分析了目前基于Petri网的测试用例生成方法，并指出了未来研究方向。在CPN的建模方面，刘婧[15]针对BitTorrent协议的高并发性和交互行为复杂性，给出了协议的CPN层次模型，充分利用了CPN在层次建模、复杂数据处理与模型检验的优势。在CPN的模型检验方面，马国富[16]提出了1种基于ASK-CTL及模型检验理论的死标志合理性验证算法。在基于CPN的测试研究方面，Farooq[17]提出了基于控制流的测试序列生成方法，通过随机漫步算法对CPN模型的状态空间进行多次搜索，生成满足覆盖标准的测试例集合，但容易生成冗余的测试案例；刘婧[18]研究了基于CPN的输入输出一致性测试(IOCO)生成方法，并给出了1种基于CPN描述测试目的模型并驱动IOCO一致性测试选择的新方法[19]；赵显琼[20]给出了基于CPN的测试案例自动生成算法和测试序列搜索算法；郑伟[21]对测试案例生成算法[20]进行了改进，提出了基于CPN的全路径覆盖优化算法和序列优选算法，后又提出了基于改进蚁群算法的测试序列生成方法[22]，用于提高自动测试执行的效率。总体而言，这些研究均采用启发式搜索算法生成测试用例，容易造成状态空间爆炸和死循环问题。同时，车载设备模式转换的复杂性，增加了传统搜索算法实现转换路径全覆盖的困难。相比而言，基于CPN的模拟仿真，属于状态空间的动态探索分析，是解决状态空间爆炸和死循环的有效途径。因此，本文基于《CTCS-3级列控系统系统需求规范(SRS)》[23](简称《规范》)，针对车载设备模式转换的功能，提出基于CPN的车载设备模式转换测试序列生成方法。

1　基于CPN的车载设备模式转换测试序列生成方法

1.1　方法的总体框架

基于CPN的车载设备模式转换测试序列生成方法的总体框架如图1所示，包括如下3个部分。

(1)根据《规范》，基于CPN构建车载设备模式转换(简称为MTCPN)模型，并采用ASK-CTL公式和非标准状态空间查询法对MTCPN模型进行分析与验证。

(2)根据《规范》，采用中国邮路算法生成车载设备模式转换的测试目标序列。

(3)将生成的测试目标序列作为MTCPN模型的输入，仿真生成满足全路径覆盖准则和CPN相应覆盖准则的可执行的测试序列集和XML文件集，避免了采用启发式搜索算法导致的状态空间爆炸和死循环问题。

图1基于CPN的车载设备模式转换测试序列生成方法框架图

1.2相关定义

定义1：非层次化CPN模型采用9个元素表示，即CPN=(P,T,A,Σ,V,C,G,E,I)，其中各个元素的含义如下。

(1)P为库所的有限集合；T为变迁的有限集合；A为弧的有限集合；且满足P∩T=P∩A=T∩A=∅，A⊆P×T∩T×P。

(2)Σ为有限非空的颜色集合，用于定义模型中的数据类型；V为变量集合；且满足Type[v]⊆Σ,v∈V。

(3)C(C:P→Σ)为着色函数，用于定义库所上允许的颜色类型，即从库所P到颜色集Σ的映射。

(4)G(G:T→EXPRv)为守卫表达式函数，用于定义变迁上的守卫函数，给出了变迁的点火条件。

(5)E(E:A→EXPRv)为弧表达式函数，用于定义弧上的弧函数，满足Type[E(a)]=C(p)MS，即与弧连接的库所的着色函数约束着弧表达式的数据类型，其中CMS为集合C的多重集集合。

(6)I(I:P→EXPRΦ)为初始化赋值函数，用于定义库所的初始数据赋值，满足Type[I(p)]=C(p)MS。

定义2：CPN模块采用4个元素表示，即CPNM=(CPN,Pport,Tsub,PT)，其中各个元素的含义如下。

(1)CPN为一个非层次化CPN模型。

(2)Pport⊆P为端口位置集合；Tsub⊆T为替代变迁集合。

(3)PT:Pport→{IN,OUT,I/O}为端口类型函数，用于定义端口位置；Pport表示3种端口类型：输入端口{IN}、输出端口{OUT}和输入输出端口{I/O}。

定义3：层次化CPN模型采用4个元素表示，即CPNH=(S,SM,PS,FS)，其中各个元素的含义如下。

(2)SM:Tsub→S为子模块函数，用于关联替代变迁和对应的CPN模块。

(4)FS⊆2p是库所融合集，满足∀(p,p′)∈fs,fs∈FS,C(p)=C(p′),I(p)<>=I(p′)<>，即库所融合集中的所有库所是相通的。

定义4：ASK-CTL状态公式表示如下，其中各参数的定义见文献[24]。

A::=tt|α|┐A|A1∨A2||EU(A1,

A2)|AU(A1,A2)

=tt|α|NOT(A)|A1∪A2||EU(A1,A2)|AU(A1,A2)

定义5：ASK-CTL状态公式的语义如下，其中各参数的定义见文献[24]。

(1)og,v|=Sttt总是为真；

(2)og,v|=Stα，iifα在节点v上为真；

(3)og,v|=St┐A=NOT(A)，iif not

og,v|=StA；

(4)og,v|=StA1∨A2=A1∪A2，iifog,

v|=StA1orog,v|=StA2；

(5)og,v|=St，iif ∃a=

(s,(t,b),s′)∈A∩a|=TrB；

(6)og,v|=StEU(Ai,Aj)， iif

∃π∈vPaths(s):∃j:∀0≤i≤j:og,

π(vi)|=StA1∧∀i≥j:og,π(vi)|=StA2；

(7)og,v|=StAU(Ai,Aj)，iff

∃π∈vPaths(v):∃j:∀0≤i≤j:og,

π(vi)|=StA1∧∀i≥j:og,π(vi)|=StA2。

ASK-CTL的变迁公式和语义也见文献[24]。

2　MTCPN模型的构建和验证

2.1　MTCPN模型的构建

根据《规范》可知：CTCS-3级列控车载设备有9种工作模式，即完全监控模式(FS)、目视行车模式(OS)、引导模式(CO)、调车模式(SH)、隔离模式(IS)、待机模式(SB)、冒进防护模式(TR)、冒进后防护模式(PT)和休眠模式(SL)；且车载设备各工作模式之间存在的转换条件(即转换路径)数量见表1。

表1　车载设备的模式转换路径数量表

根据《规范》，提出以下8条建模规则。

(1)采用分层(2层)建模规则构建MTCPN模型，上层模型只考虑各模式之间的转换路径，下层模型考虑各模式转换的具体转换流程。

(2)《规范》中的“转换条件18”是针对CTCS-2等级的，本文不做讨论。

(3)为使MTCPN模型简洁且不失普遍性，除SH，IS和SL模式外，默认其他模式均与RBC已建立通信会话，并且只考虑各模式转换流程，对模式转换后的流程不做处理。

(4)为使MTCPN模型便于分析，凡是跟应答器相关的流程，均按照单个应答器处理。

(5)建模过程严格遵守车载设备模式转换规范，暂不考虑特殊情况。

(6)MTCPN上层模型的模式转换均用替代变迁表示，具体的转换流程均在MTCPN下层模型表示。

(7)MTCPN模型中，颜色的定义、变量和库所等的命名均遵循一定的规则，以辅助算法实现。

(8)对数据内容的判断行为，均在守卫函数中体现。

由此构建出MTCPN模型。其中，上层模型如图2所示；下层模型共有39个，这里仅给出其中SB模式转FS模式的下层模型，如图3所示。

图2　MTCPN模型的上层模型

图3　SB模式转FS模式的下层模型

2.2　MTCPN模型的验证

模型验证的基本思想是用状态迁移系统表示系统的行为，用模态/时序逻辑公式描述系统的性质。Cheng等人将CPN与模型检验相结合，并在CPN Tools工具中引入了1种扩展逻辑语言ASK-CTL[24]。本节根据CPN模型检测理论，使用分支时序逻辑ASK-CTL公式及非标准状态空间查询法对构建的MTCPN模型进行验证。

针对图2进行MTCPN模型的死锁分析，其结果如图4所示，可知MTCPN模型无死标识节点，属于强连通图，说明构建的MTCPN模型满足《规范》要求的模式转换功能。

图4　MTCPN模型的死锁分析结果

针对图3进行转换规则的验证，其结果如图5所示。实际测试的车载流程中，车载设备的初始工作模式始终为SB模式，即库所SB的初始标记为1′(6,true)(变量“6”表示M_MODE=6，即车载模式为SB模式，变量“true”表示B_WrieComm=true，即SB模式下车载设备已与无线闭塞中心RBC建立了通信连接，那么存在某条路径，使得SB模式可转入FS模式；同理，存在某条路径，使得FS模式可转入TR模式，执行ASL-CTL公式，返回执行结果“true”，如图5(a)所示；如果删除库所SB的初始标记，其返回结果如图5(b)所示，表示这种情况永远不会发生；如果设置库所FS的初始标记为1′(0,true)，其执行结果同样如图5(a)所示，说明构建的MTCPN模型符合车载设备模式转换流程。

图5　模式转换规则的验证结果

3　测试目标序列集的生成方法

对于传统的基于CPN模型的测试生成方法，大多数以空间搜索算法为基础，但这类方法容易陷入死循环，并且由于车载设备模式转换的复杂性，更加剧了模式转换测试序列实现转换路径全覆盖的困难。为了解决上述问题，针对《规范》采用中国邮路算法生成测试目标序列。

根据车载设备模式转换规则，将车载设备的工作模式映射成有向图的顶点，车载设备的模式转换路径映射成有向图的弧，则可将表1转换成有向图D，如图6所示。

图6　车载设备模式转换有向图

由图6和第2.2节可知，映射后的车载设备模式转换有向图为强连通图，即车载设备模式转换有向图存在最优邮路，因此采用中国邮路算法生成测试目标序列，算法步骤如下。

步骤3：利用Floyd算法求解各个顶点(vi,vj)间的最短距离矩阵F与最短路径矩阵P′。

步骤5：对平衡欧拉图D′进行欧拉寻址，得到最优邮路P。

其中改进Hungary算法是指改进了选取0元素的方法：通过选择0元素所在行(列)中0元素个数最少行(列)中的0元素，如果仍存在相同数量0元素的行(列)，再采用任意选取方法，从而避免了原始算法任意选取0元素而造成的死循环，也提高了算法的收敛性。

采用上述中国邮路算法对车载设备模式转换有向图D进行遍历，生成的1条最优邮路P为

P={SB→SH→SB→SH→SB→FS→

SB→OS→SB→CO→SB→CO→

SH→TR→PT→SB→CO→FS→

SH→TR→PT→SH→TR→PT→

FS→OS→SH→IS→SB→CO→

OS→FS→CO→TR→PT→FS→

CO→TR→PT→FS→TR→PT→

FS→TR→PT→FS→TR→PT→

FS→TR→PT→FS→TR→PT→

FS→TR→PT→FS→IS→SB→

CO→TR→PT→OS→CO→TR→

PT→OS→TR→PT→OS→TR→

PT→OS→TR→PT→OS→TR→

PT→OS→IS→SB→CO→TR→

PT→CO→TR→PT→IS→SB→

CO→IS→SB→SL→SB→SL→

SB→SL→IS→SB→TR→IS→

SB→IS→SB}

因为最优邮路P的路径过长，所以要对P进行二次优化，即对P进行截断工作。与文献[3]给出的二次优化方法不同，本文提出的二次优化方法只考虑对添加的重复路径进行截断。首先标记出添加的所有重复路径，根据《规范》对重复路径中的某些路径进行截断，将截断处的起点归于上一序列、终点归于下一个序列；其次，若重复路径属于重复的测试项，就删去起点和终点，否则保留；最后，保证新序列的起点和终点均为SB模式。

由此可生成9条测试目标序列，见表2。表2中：测试利用率为路径覆盖量占测试项的百分比；累计测试项为此测试目标序列之前包含的所有测试项数量；路径累计覆盖量为测试项之前包含的所有不重复的模式转换路径数量；累计测试利用率为路径累计覆盖量占累计测试项的百分比。由表2可知：测试目标序列3的测试利用率最高；随着测试目标序列号的增加，累计测试利用率越来越低，说明后续增加的测试序列中包含了很多重复的模式转换路径，降低了累计测试利用率，例如FS转TR的模式转换路径有6条，但是TR转PT的模式转换路径仅有1条，那么生成的测试目标序列不可避免地会存在多条TR转PT的模式转换路径。

表2　生成的测试目标序列

4　测试序列集的选择性生成

将生成的测试目标序列作为MTCPN模型的输入，仿真生成可执行测试序列集和XML文件集。采用该方法生成的测试序列集能够覆盖所有模式转换路径，满足全路径覆盖准则和CPN相应的覆盖标准，并且生成的测试序列容易为实际的测试执行。

以表2中测试利用率最高的测试目标序列3为例，首先约定SB模式的初始标记为1′(6,true)，然后根据测试目标序列3驱动MTCPN模型的仿真；其次更改测试目标序列所涉及的库所颜色集，即更改为积颜色集INT×MODE×WRIECOMM，增加表示测试步骤的整数颜色集INT，得到对应的测试序列，如图7所示，因测试输入数据和测试输出数据已包含于每个变迁的守卫函数和执行函数中，所以此测试序列中包含测试步骤、测试输入数据及测试输出数据等，是可执行的测试序列。图7给出的测试序列3属于CPN模型，通过CPN Tools工具内嵌的XML文件保存功能能够得到此序列的XML文件。

图7　基于CPN的测试序列3

将本文提出的车载设备转换模式测试序列生成方法与文献[9]中的2个生成方法进行对比，结果见表3。由表3可知：与文献[9]相比，本文方法生成的测试序列总数、测试项数均较少，但测试利用率较高，说明本文方法提高了测试效率。

表3　生成方法的对比

5　结束语

本文将车载设备模式转换理论与CPN建模方法有效融合，提出了基于CPN模型的车载设备模式转换测试序列生成方法。该方法根据《规范》，首先基于有色Petri网构建车载设备模式转换(MTCPN)模型，并采用ASK-CTL逻辑公式对MTCPN模型进行验证；然后根据车载设备模式转换规则，将车载设备的工作模式及其转换路径映射为有向图，采用中国邮路算法求解有向图，生成1条最优邮路，对该邮路进行二次优化，生成车载设备模式转换的测试目标序列集；将生成的测试目标序列作为MTCPN模型的输入，仿真生成满足全路径覆盖准则和CPN相应覆盖准则的可执行的测试序列集和XML文件集。该方法以实际数据驱动MTCPN模型，仿真生成测试序列，保证了测试序列的可执行性，巧妙地避开了基于遍历模型状态空间的传统生成方法所存在的状态空间爆炸和死循环问题，为基于CPN的模式转换测试研究提供了1种新的思路与解决方案。

[1]李伟, 王海峰. CTCS-3级列控系统车载设备测试序列的优化[J]. 北京交通大学学报, 2010, 34(2): 75-78.

(LI Wei, WANG Haifeng. Optimization Test Sequence of CTCS-3 On-Board Equipment [J]. Journal of Beijing Jiaotong University, 2010, 34(2): 75-78. in Chinese)

[2]徐俊明. 图论及其应用[M]. 合肥: 中国科学技术大学出版社，2010.

[3]张勇, 王超琦. CTCS-3级列控系统车载设备测试序列优化生成方法[J]. 中国铁道科学, 2011, 32(3): 100-106.

(ZHANG Yong, WANG Chaoqi. The Method for the Optimal Generation of Test Sequence for CTCS-3 On-Board Equipment [J]. China Railway Science, 2011, 32(3): 100-106. in Chinese)

[4]张仕雄. CTCS-3级列控系统测试序列合理性验证的研究[J]. 铁道标准设计, 2012(12):103-105.

(ZHANG Shixiong. Study on Rationality Verification for CTCS-3 Train Control System Test Sequences [J]. Railway Standard Design, 2012 (12):103-105. in Chinese)

[5]LEDRU Y, BOUSQUET L D, BONTRON P, et al. Test Purposes: Adapting the Notion of Specification to Testing [C]//16th IEEE International Conference on Automated Software Engineering(ASE2001). San Diego: IEEE CS Press, 2001: 127-134.

[6]颜炯, 王戟, 陈火旺. 基于模型的软件测试综述[J]. 计算机科学, 2004, 31(2): 184-187.

(YAN Jiong, WANG Ji, CHEN Huowang. Survey of Model-Based Software Testing [J]. Computer Science, 2004, 31(2): 184-187. in Chinese.)

[7]UTTING M, LEGEARD B. Practical Model-Based Testing: a Tools Approach [M]. San Francisco: Morgan Kaufmann, 2010.

[8]赵显琼, 唐涛. 多端口形式化测试自动生成方法在CTCS-3车载系统中的应用[J]. 铁道学报, 2011, 33(7): 44-51.

(ZHAO Xianqiong, TANG Tao. Multi-Port Based Automatic Formal Testing Generation and Its Application in CTCS-3 Level On-Board System [J]. Journal of the China Railway Society, 2011, 33(7): 44-51. in Chinese)

[9]袁磊, 吕继东, 刘雨, 等. 一种全覆盖的列控车载系统测试用例自动生成算法研究[J].铁道学报, 2014, 36(8): 55-62.

(YUAN Lei, LÜ Jidong, LIU Yu, et al. Research on Model-Based Test Case Generation Method of Onboard Subsystem in CTCS-3 [J]. Journal of the China Railway Society, 2014, 36(8): 55-62. in Chinese)

[10]陈鑫, 姜鹏, 张一帆, 等. 一种面向列车控制系统中安全攸关场景的测试用例自动生成方法[J]. 软件学报, 2015, 26(2): 269-278.

(CHEN Xin, JIANG Peng, ZHANG Yifan, et al. Method of the Automatic Test Case Generation for Safety-Critical Scenarios in Train Control Systems[J]. Journal of Software, 2015, 26(2): 269-278. in Chinese)

[11]JENSEN K. A Brief Introduction to Coloured Petri Nets[C]// International Workshop on Tools and Algorithms for the Construction and Analysis of Systems. Heidelberg: Springer, 1997: 2003-2008.

[12]JENSEN K, KRISTENSEN L M, WELLS L. Coloured Petri Nets and CPN Tools for Modeling and Validation of Current Systems [J]. International Journal on Software Tools for Technology Transfer, 2007, 9(3/4): 213-254.

[13]JENSEN K, KRISTENSEN L M. Coloured Petri Nets: Modeling and Validation of Concurrent Systems [M]. Heidelberg: Springer Sciences & Business Media, 2009.

[14]牟小玲, 丁晓明, 张望. 基于Petri网的测试用例生成研究进展[J]. 重庆交通大学学报:自然科学版, 2012, 31(1): 163-167.

(MU Xiaoling, DING Xiaoming, ZHANG Wang. Research Progress in Test Case Generation Based on Petri Nets [J]. Journal of Chongqing Jiaotong University:Natural Science, 2012, 31(1): 163-167. in Chinese)

[15]刘婧, 叶新铭, 李军. BitTorrent协议的Petri网建模方法研究[J]. 系统仿真学报, 2011, 23(11): 2312-2320.

(LIU Jing, YE Xinming, LI Jun. Towards Formal Modeling Methodology of BitTorrent Based on Petri Nets [J]. Journal of System Simulation, 2011, 23(11): 2312-2320. in Chinese)

[16]马国富, 刘文良, 周建勇, 等. 有色Petri网模型中死标志合理性分析与验证[J]. 计算机应用研究, 2014, 31(12): 3651-3654.

(MA Guofu, LIU Wenliang, ZHOU Jianyong, et al. Analysis and Verification of Rationality of Dead Markings in Colored Petri Net Models [J]. Application Research of Computers, 2014, 31(12): 3651-3654. in Chinese)

[17]FAROOQ U, LAM C P, LI H. Towards Automated Test Sequence Generation[C]//Proceedings of the 19th Australian Conference on Software Engineering. Perth, Australia: Conference on Software Engineering，2008:441-450.

[18]LIU Jing, YE Xinming, ZHOU Jiantao，et al. I/O Conformance Test Generation with Colored Petri Nets [J]. Applied Mathematics & Information Sciences, 2014, 8(6): 2695-2704.

[19]刘婧, 李茹, 叶新铭, 等. PN4TS:一种基于CPN模型的IOCO测试选择方法[J]. 计算机学报, 2014, 37(12): 2451-2463.

(LIU Jing, LI Ru, YE Xinming, et al. PN4TS: Test Selection Approach with IOCO Based on Colored Petri Nets [J]. Chinese Journal of Computers, 2014, 37(12): 2451-2463. in Chinese)

[20]赵显琼, 郑伟, 唐涛. 一种基于模型的形式化测试序列自动生成方法及在ETCS-2中的应用[J]. 铁道学报, 2012, 34(5): 70-74.

(ZHAO Xianqiong, ZHENG Wei, TANG Tao. Model-Based Formal Approach for Generating Test Cases and Test Sequences Automatically by Example of the ETCS-2 [J]. Journal of the China Railway Society, 2012, 34(5): 70-74. in Chinese)

[21]ZHENG Wei, LIANG Ci, WANG Rui, et al. Automated Test Approach Based on All Paths Covered Optimal Algorithm and Sequence Priority Selected Algorithm [J].IEEE Transactions on Intelligent Transportation Systems, 2014, 15(6): 2551-2559.

[22]ZHENG Wei, HU Naiwen. Automated Test Sequence Optimization Based on the Maze Algorithm and Ant Colony Algorithm [J]. International Journal of Computers Communications & Control, 2015, 10(4): 593-606.

[23]中华人民共和国铁道部. 铁科运[2008]127号 CTCS-3级列控系统系统需求规范(SRS)(V1.0)[S]. 北京: 中华人民共和国铁道部, 2008.

[24]University of Aarhus. Design/CPN ASK-CTL Manual [EB/OL]. 1996. http://www.daimi.au.dk/designCPN/libs/askctl/ASKCTLmanual.pdf.