基于通信的列车控制系统的协议一致性测试研究
摘要
基于通信的列车控制(Communications Based Train Control,CBTC)系统,通信协议是整个系统安全的基础,也是各子系统间可靠地进行数据通信的保证。为了保证网络中各实体间能够可靠、正确地通信,必须根据通信协议规范对协议进行一致性测试。因此,对CBTC系统通信协议的一致性测试成为协议测试的研究重点。
本文在研究CBTC系统通信协议的规范和相关文档的基础上,进一步研究了一致性测试技术的不同理论方法,结合CBTC系统通信协议的特点,采用UIO_E (Extended Unique Input/Output Sequences)算法和扩展有限状态机(Extended Finite State Machine,EFSM)的建模方法,对CBTC系统通信协议的一致性测试进行了研究。
本文介绍了CBTC系统通信协议的基本原理;根据CBTC系统通信协议的特点以及EFSM建模方法,建立了CBTC通信协议的EFSM模型;分析了FSM与EFSM模型一致性测试的序列生成算法;根据通信协议的需求及特点,提出了基于UIO_E算法和EFSM模型的CBTC通信协议测试序列的生成算法,并生成了CBTC通信协议的一致性测试序列;最后,按照生成的测试序列,对CBTC系统通信协议的被测实现(Implementation Under Test,IUT)进行一致性测试,并对测试结果进行分析,一致性结果判决表明协议实现达到了协议规范的需求。
In the Communication Based Train Control (CBTC) system, communication protocol is not only the foundation of the whole system’s safety, but also the guarantee of data communicate reliably between subsystems. To make sure that these devices in network can communicate with each others reliably and correctly, we must execute conformance test according to their specifications. Therefore, conformance test of CBTC communication protocol has become the research focus of the communication protocol testing.
In this paper, On the basis of research CBTC communication protocol specifications and standards, lots of conformance testing technologies and theories have been studied, the Extended UniqueInput/Output Sequences ( UIO_E ) algorithm and the Extended Finite State Machine(EFSM) model have been applied on the CBTC communication protocol according to its characteristic.
In this paper, firstly, the basic principle of CBTC communication protocol were expatiated. Secondly, the CBTC communication protocol model was built according to the characteristic of CBTC communication protocol and the method based on EFSM, Then, test sequence generating algorithm of FSM and EFSM model have been described particularly, and a test sequence generating algorithm for CBTC communication protocol have been proposed based on UIO_E algorithm and EFSM model. Using UIO_E algorithm, CBTC communication protocol conformance test sequence has been generated. At last, a simulation platform has been established according to the conformance test sequence. Through the analysis of the result, the conformance adjudgement has indicated that the Implementation Under Test (IUT) can meet the requirements of CBTC communication protocol specification.
本文在研究CBTC系统通信协议的规范和相关文档的基础上,进一步研究了一致性测试技术的不同理论方法,结合CBTC系统通信协议的特点,采用UIO_E (Extended Unique Input/Output Sequences)算法和扩展有限状态机(Extended Finite State Machine,EFSM)的建模方法,对CBTC系统通信协议的一致性测试进行了研究。
本文介绍了CBTC系统通信协议的基本原理;根据CBTC系统通信协议的特点以及EFSM建模方法,建立了CBTC通信协议的EFSM模型;分析了FSM与EFSM模型一致性测试的序列生成算法;根据通信协议的需求及特点,提出了基于UIO_E算法和EFSM模型的CBTC通信协议测试序列的生成算法,并生成了CBTC通信协议的一致性测试序列;最后,按照生成的测试序列,对CBTC系统通信协议的被测实现(Implementation Under Test,IUT)进行一致性测试,并对测试结果进行分析,一致性结果判决表明协议实现达到了协议规范的需求。
In the Communication Based Train Control (CBTC) system, communication protocol is not only the foundation of the whole system’s safety, but also the guarantee of data communicate reliably between subsystems. To make sure that these devices in network can communicate with each others reliably and correctly, we must execute conformance test according to their specifications. Therefore, conformance test of CBTC communication protocol has become the research focus of the communication protocol testing.
In this paper, On the basis of research CBTC communication protocol specifications and standards, lots of conformance testing technologies and theories have been studied, the Extended UniqueInput/Output Sequences ( UIO_E ) algorithm and the Extended Finite State Machine(EFSM) model have been applied on the CBTC communication protocol according to its characteristic.
In this paper, firstly, the basic principle of CBTC communication protocol were expatiated. Secondly, the CBTC communication protocol model was built according to the characteristic of CBTC communication protocol and the method based on EFSM, Then, test sequence generating algorithm of FSM and EFSM model have been described particularly, and a test sequence generating algorithm for CBTC communication protocol have been proposed based on UIO_E algorithm and EFSM model. Using UIO_E algorithm, CBTC communication protocol conformance test sequence has been generated. At last, a simulation platform has been established according to the conformance test sequence. Through the analysis of the result, the conformance adjudgement has indicated that the Implementation Under Test (IUT) can meet the requirements of CBTC communication protocol specification.
引文
[1] IEEE Std 1474.1-1999.IEEE Standard for Communications Based Train Control (CBTC) Performance and Functional Requirements.New York.1999,5-8
[2]杨世玉等.铁路信号安全协议一致性测试序列生成研究:[学位论文].上海:同济大学,2010
[3]郜春海.基于通信的轨道交通列车运行控制系统.现代城市轨道交通,2007(2):7-10
[4] E Nishinaga. J A Evans.Wireless Advanced Auto-matic Train Control.Proceeding of the SME/IEEE Joint Railroad Conference,Chicago.USA.1994
[5]姚学礼.网络通信协议一致性测试研究.通信技术,2009(5):172-176
[6]吴海峰.基于通信的移动闭塞列车控制系统.铁道通信信号,2007(8):60-61
[7]李春宇等.开放空间无线CBTC车地通信系统.铁路通信信号工程技术, 2006 (3-3):46-55
[8] CENELEC.EN50159-2 Railways Applications.Signalling and Communications Safety Related Communication in Open Transmission Systems.2001,56-74
[9]刘晓娟.城市轨道交通CBTC系统关键技术研究:[学位论文].兰州:兰州交通大学,2009
[10] Esposito Rosaria,Lazzaro Annando,Manno Pietro.Formal Verification of ERTMS EURORADIO Safety Critical Protocol.Ansaldo Segnalamento Ferroviario S.p.A
[11]李本刚.CBTC移动闭塞和准移动闭塞列车运行安全间隔时间的计算.铁路通信信号过程技术,2008(6)
[12]古军等.基于UIO序列的测试方法及UIO生成算法研究.计算机工程与应用, 2005(17):46-49
[13] H.Hoefstadt.Global System of Mobile Radio Communications of Railways,Electric Railways in a United EuroPe,EIEE Conefrence,1995,111-115
[14] Todd Lammle.CCNA:Cisco Certified Newtork Associate study Guide Fitfh Edition.北京:电子工业出版社,2005.4,19
[15]董焕珍.基于EFSM的UIO序列的生成研究[学位论文].青岛大学2009
[16]李艳等.基于不同形式化模型的网络通信协议验证技术的分析与比较.华中师范大学学报,2002,36(4):428-431
[17]郭朝彬等.基于扩展有限状态机的类测试用例生成方法.华北水利水电学院学报,2006,27(3):52-54
[18]陈涛等.基于FSM的协议一致性测试序列生成算法研究.计算机工程与应用,2010,46(6):60-62
[19]杨琛.学习设计一致性测试模型研究与实现:[学位论文].华中师范大学,2008
[20]马秀飞.协议一致性测试与测试序列生成算法研究:[学位论文].南京邮电学院,2005,58-6l
[21] Pang Qi-xiang,Cheng Shi-duan,Jin Yue-hui.Protocol conformance test suite generation. Communication Technology Proceedings,1996,218-222
[22]李永亮,基于EFSM模型的软件故障检测与一致性测试生成研究:[学位论文].湖南大学.2009
[23] Krishan Sabnani,Anton Dahbura,A New Technique for Generating Protocol Tests,ACM,1985,36-43
[24] Ramalingom T,Thulasiraman K,Anindya D.Context independent unique sequences generation for protocol testing,IEEE,1 996(3):114 1-1148
[25] Li X,Higashino T,Higuchi M,et a1.Automatic generation of extended UIO sequences for communication protocols in an EFSM model.Proc Seventh Int’l Workshop Protocol Test Systems,1 997,225-240
[26] G.v.Bochmami,A.Petrenko.Protocol Testing:Review of Methods and Relevance for Software Testing.Proceedings of the 1994 international symposium on Software testing and analysis,1994,109-124
[27]赵保华等.一种改进的转换可执行分析测试序列生成算法.中国科学技术大学出版社.2007,37(9):1096-1100
[28] D.Lee,M.Yarmakakis.Principles and Methods of Testing Finite State Machines-A Survey.Proceedings of the IE EE,l 996,1090-1123
[29] Duale A Y,Uyar M U.A method enabling feasible conformance test sequence generation for EFSM models.IEEE Transactions on Computers,2004,53(5):614-627
[30] Yibor Csondes,Balazs Kotnyek,Janos Zoltan Szabo.Application of heuristic methods for conformance test selection.European Journal of Operational Rearch,2002,203-218
[31] Wang Gui-lin.Universal forgery on a group signature scheme using self-certified public keys.Information Processing Letters,2004(89):227-231
[32] Shao Zu-hua.Self-certified signature scheme from pairings.The Journal of Systems and Software,2007(80):388-395
[33] Chen W H,Lu Cho-ching.Executable test sequence for the protocol control and data flow property with over lapping,Proceedings of the Seventh International Symposium on Computers and Communications,2002,251-257
[34] C.M.Christoph,G.MeGraw,M.A.Schatz.Generatiing Software Data by Evolution.IEEETrans.on Soft.Eng,2001,(12):1085-1110
[35] Sarikaya,Bochmann G,Cerny E.A test design methodology for protocol testing.IEEE Trans Software Eng,1987,13(5):518-531
[36] Miller R,Paul S.Generating conformance test sequences for combined control flow and data flow of communication protocols.Proc 12th Int’l Symp Protocol Specification, Testing,and Verification,1992,12-27
[37] Chanson S T,Zhu Jin-song.A unified approach to protocol test sequence generation.Proc lEEE INFOCOM,San Francisco,1993(1),106-114
[38] Xie Lei,Wei Jiao-long,Zhu Guang-xi.An improved FSM-based method for BGP protocol.IEEE,2008(6),557-561
[39] Derderian K,Hierons R M,Harman M,et al.Automated uniqueinput output sequence generation for conformance testing of FSM.Computer Journal,2006,49(3):331-344
[40]魏仰苏等.通信协议一致性测试序列自动生成算法研究.计算机工程与设计,2007,28(10):2312-2315.
[2]杨世玉等.铁路信号安全协议一致性测试序列生成研究:[学位论文].上海:同济大学,2010
[3]郜春海.基于通信的轨道交通列车运行控制系统.现代城市轨道交通,2007(2):7-10
[4] E Nishinaga. J A Evans.Wireless Advanced Auto-matic Train Control.Proceeding of the SME/IEEE Joint Railroad Conference,Chicago.USA.1994
[5]姚学礼.网络通信协议一致性测试研究.通信技术,2009(5):172-176
[6]吴海峰.基于通信的移动闭塞列车控制系统.铁道通信信号,2007(8):60-61
[7]李春宇等.开放空间无线CBTC车地通信系统.铁路通信信号工程技术, 2006 (3-3):46-55
[8] CENELEC.EN50159-2 Railways Applications.Signalling and Communications Safety Related Communication in Open Transmission Systems.2001,56-74
[9]刘晓娟.城市轨道交通CBTC系统关键技术研究:[学位论文].兰州:兰州交通大学,2009
[10] Esposito Rosaria,Lazzaro Annando,Manno Pietro.Formal Verification of ERTMS EURORADIO Safety Critical Protocol.Ansaldo Segnalamento Ferroviario S.p.A
[11]李本刚.CBTC移动闭塞和准移动闭塞列车运行安全间隔时间的计算.铁路通信信号过程技术,2008(6)
[12]古军等.基于UIO序列的测试方法及UIO生成算法研究.计算机工程与应用, 2005(17):46-49
[13] H.Hoefstadt.Global System of Mobile Radio Communications of Railways,Electric Railways in a United EuroPe,EIEE Conefrence,1995,111-115
[14] Todd Lammle.CCNA:Cisco Certified Newtork Associate study Guide Fitfh Edition.北京:电子工业出版社,2005.4,19
[15]董焕珍.基于EFSM的UIO序列的生成研究[学位论文].青岛大学2009
[16]李艳等.基于不同形式化模型的网络通信协议验证技术的分析与比较.华中师范大学学报,2002,36(4):428-431
[17]郭朝彬等.基于扩展有限状态机的类测试用例生成方法.华北水利水电学院学报,2006,27(3):52-54
[18]陈涛等.基于FSM的协议一致性测试序列生成算法研究.计算机工程与应用,2010,46(6):60-62
[19]杨琛.学习设计一致性测试模型研究与实现:[学位论文].华中师范大学,2008
[20]马秀飞.协议一致性测试与测试序列生成算法研究:[学位论文].南京邮电学院,2005,58-6l
[21] Pang Qi-xiang,Cheng Shi-duan,Jin Yue-hui.Protocol conformance test suite generation. Communication Technology Proceedings,1996,218-222
[22]李永亮,基于EFSM模型的软件故障检测与一致性测试生成研究:[学位论文].湖南大学.2009
[23] Krishan Sabnani,Anton Dahbura,A New Technique for Generating Protocol Tests,ACM,1985,36-43
[24] Ramalingom T,Thulasiraman K,Anindya D.Context independent unique sequences generation for protocol testing,IEEE,1 996(3):114 1-1148
[25] Li X,Higashino T,Higuchi M,et a1.Automatic generation of extended UIO sequences for communication protocols in an EFSM model.Proc Seventh Int’l Workshop Protocol Test Systems,1 997,225-240
[26] G.v.Bochmami,A.Petrenko.Protocol Testing:Review of Methods and Relevance for Software Testing.Proceedings of the 1994 international symposium on Software testing and analysis,1994,109-124
[27]赵保华等.一种改进的转换可执行分析测试序列生成算法.中国科学技术大学出版社.2007,37(9):1096-1100
[28] D.Lee,M.Yarmakakis.Principles and Methods of Testing Finite State Machines-A Survey.Proceedings of the IE EE,l 996,1090-1123
[29] Duale A Y,Uyar M U.A method enabling feasible conformance test sequence generation for EFSM models.IEEE Transactions on Computers,2004,53(5):614-627
[30] Yibor Csondes,Balazs Kotnyek,Janos Zoltan Szabo.Application of heuristic methods for conformance test selection.European Journal of Operational Rearch,2002,203-218
[31] Wang Gui-lin.Universal forgery on a group signature scheme using self-certified public keys.Information Processing Letters,2004(89):227-231
[32] Shao Zu-hua.Self-certified signature scheme from pairings.The Journal of Systems and Software,2007(80):388-395
[33] Chen W H,Lu Cho-ching.Executable test sequence for the protocol control and data flow property with over lapping,Proceedings of the Seventh International Symposium on Computers and Communications,2002,251-257
[34] C.M.Christoph,G.MeGraw,M.A.Schatz.Generatiing Software Data by Evolution.IEEETrans.on Soft.Eng,2001,(12):1085-1110
[35] Sarikaya,Bochmann G,Cerny E.A test design methodology for protocol testing.IEEE Trans Software Eng,1987,13(5):518-531
[36] Miller R,Paul S.Generating conformance test sequences for combined control flow and data flow of communication protocols.Proc 12th Int’l Symp Protocol Specification, Testing,and Verification,1992,12-27
[37] Chanson S T,Zhu Jin-song.A unified approach to protocol test sequence generation.Proc lEEE INFOCOM,San Francisco,1993(1),106-114
[38] Xie Lei,Wei Jiao-long,Zhu Guang-xi.An improved FSM-based method for BGP protocol.IEEE,2008(6),557-561
[39] Derderian K,Hierons R M,Harman M,et al.Automated uniqueinput output sequence generation for conformance testing of FSM.Computer Journal,2006,49(3):331-344
[40]魏仰苏等.通信协议一致性测试序列自动生成算法研究.计算机工程与设计,2007,28(10):2312-2315.