基于FSM的启发式测试序列生成方法研究及其应用
|
摘要
随着计算机网络的快速发展,网络协议日趋复杂和多样。通常网络协议的规范都是通过自然语言描述的,但由于自然语言的二义性,协议的实现可能不完全符合协议规范,所以对协议一致性测试技术的研究具有较大的应用价值。协议一致性测试是用来检验协议实现是否符合协议规范,其关键技术主要有形式化描述、测试序列生成等。其中,生成测试序列的时空效率以及最终总序列的长度将会影响整个一致性测试过程的实际效率。本论文在对一致性测试技术深入分析的基础上,重点研究了基于有限状态机的测试序列生成方法,尤其是基于UIO的测试序列生成方法,对其容易产生的序列长度较长、爆炸问题等情况进行了分析与优化。’
本文首先介绍了一致性测试的基本原理、流程与方法,详细阐述了几种基于FSM的测试序列生成方法,分析对比了各个方法的优缺点。其次，本文介绍了几种经典的基于UIO序列生成的优化方法,在已有优化算法基础上提出了UIOv测试序列生成方法的改进算法,并给出了相应的实验分析,其结果表明,该算法能够在错误覆盖率保持不变的情况下有效缩短总测试序列的长度。然后,本文在现有的UIO序列生成方法基础上提出了一种改进的启发式测试序列生成算法,给出了算法的相关定义及详细流程,并且通过已有算法和本文算法在不同应用场景下的测试,分析了本文算法的效率；通过实验结果分析可知,该方法在估价函数的引导下能快速地找出有限状态机中各状态的UIO序列,并且对于复杂的协议能够避免爆炸问题的产生,有效地提高时空效率。最后,基于本课题的应用背景,根据需求分析给出了测试序列自动生成系统的概要设计及详细设计,编码实现了该系统中各模块的全部功能,并通过实例应用证明了该系统的可执行性。
With the rapid development of computer networks, the network protocols are becoming more and more complex and diverse. In general, protocol standards are made up of natural language, which may affect the conformance between the protocol and the standard because of its ambiguity. Thus, it is necessary to study the protocol conformance testing. Protocol conformance testing is used for testing whether the implementation of protocol is in line with its specification. The key technologies of the protocol conformance testing are protocol formal description, test sequence generation and so on. The time and space efficiency of test sequence generation and the final total length of the sequence will both affect the actual efficiency of the conformance testing process. Based on the analysis of the technology of conformance testing, this paper did in-depth study of test sequence generation based on FSM, particularly on those methods based on UIO, which are analysis and optimized in this paper to solve the problems of longer sequence length, explosive problem and so on.
This paper first described the principles of conformance testing and its processes and methods. Then it elaborated several test sequence generation methods based on FSM in detail, analyzed and compared their advantages and disadvantages. Secondly, this paper described several classical methods of test sequence generation based on UIO, and proposed an improved method based on UIOv on the basis of existing methods, along with the experimental analysis. The results showed while remaining the same wrong coverage, this method can effectively shorten the length of test sequence. Thirdly, this paper proposed the heuristic test sequence generation algorithm on the basis of existing methods, followed by some related definitions of this algorithm and processes in detail. Base on the test under different scenarios, this paper analysis the efficiency of this algorithm, and the result showed that under the guidance of the valuation function, this method can quickly find all the shortest UIO test sequences of all the states in the FSM, and it can avoid explosive issues for complex protocols, which effectively improved the spatial and temporal efficiency. Finally, this paper presented the preliminary design and detailed design of test sequence automatic generation system to meet the requirements of the discussed subject, as well as detailed codes to fulfill its full functionality. At last, an instance was applied to prove the enforceability of this system.
本文首先介绍了一致性测试的基本原理、流程与方法,详细阐述了几种基于FSM的测试序列生成方法,分析对比了各个方法的优缺点。其次，本文介绍了几种经典的基于UIO序列生成的优化方法,在已有优化算法基础上提出了UIOv测试序列生成方法的改进算法,并给出了相应的实验分析,其结果表明,该算法能够在错误覆盖率保持不变的情况下有效缩短总测试序列的长度。然后,本文在现有的UIO序列生成方法基础上提出了一种改进的启发式测试序列生成算法,给出了算法的相关定义及详细流程,并且通过已有算法和本文算法在不同应用场景下的测试,分析了本文算法的效率；通过实验结果分析可知,该方法在估价函数的引导下能快速地找出有限状态机中各状态的UIO序列,并且对于复杂的协议能够避免爆炸问题的产生,有效地提高时空效率。最后,基于本课题的应用背景,根据需求分析给出了测试序列自动生成系统的概要设计及详细设计,编码实现了该系统中各模块的全部功能,并通过实例应用证明了该系统的可执行性。
With the rapid development of computer networks, the network protocols are becoming more and more complex and diverse. In general, protocol standards are made up of natural language, which may affect the conformance between the protocol and the standard because of its ambiguity. Thus, it is necessary to study the protocol conformance testing. Protocol conformance testing is used for testing whether the implementation of protocol is in line with its specification. The key technologies of the protocol conformance testing are protocol formal description, test sequence generation and so on. The time and space efficiency of test sequence generation and the final total length of the sequence will both affect the actual efficiency of the conformance testing process. Based on the analysis of the technology of conformance testing, this paper did in-depth study of test sequence generation based on FSM, particularly on those methods based on UIO, which are analysis and optimized in this paper to solve the problems of longer sequence length, explosive problem and so on.
This paper first described the principles of conformance testing and its processes and methods. Then it elaborated several test sequence generation methods based on FSM in detail, analyzed and compared their advantages and disadvantages. Secondly, this paper described several classical methods of test sequence generation based on UIO, and proposed an improved method based on UIOv on the basis of existing methods, along with the experimental analysis. The results showed while remaining the same wrong coverage, this method can effectively shorten the length of test sequence. Thirdly, this paper proposed the heuristic test sequence generation algorithm on the basis of existing methods, followed by some related definitions of this algorithm and processes in detail. Base on the test under different scenarios, this paper analysis the efficiency of this algorithm, and the result showed that under the guidance of the valuation function, this method can quickly find all the shortest UIO test sequences of all the states in the FSM, and it can avoid explosive issues for complex protocols, which effectively improved the spatial and temporal efficiency. Finally, this paper presented the preliminary design and detailed design of test sequence automatic generation system to meet the requirements of the discussed subject, as well as detailed codes to fulfill its full functionality. At last, an instance was applied to prove the enforceability of this system.
引文
[1]Fujiwara, S., et al., Test selection based on finite state models. Software Engineering, IEEE Transactions on,1991.17(6):p.591-603.
[2]Lai, R., A survey of communication protocol testing. Journal of Systems and Software,2002. 62(1):p.21-46.
[3]古天龙,蔡国永,网络协议的形式化分析与设计.2003：电子工业出版社.
[4]Belina, F. and D. Hogrefe, The CCITT-specification and description language SDL. Computer Networks and ISDN Systems,1989.16(4):p.311-341.
[5]Interactions, I., ISO 8807:LOTOS—a formal description technique based on the temporal ordering of observational behaviour.1987, Elsevier, Amsterdam.
[6]ISO, I.,9074:Information Processing Systems, Open Systems Interconnection, Estelle:A Formal Description Technique Based on an Extended Finite State Transition Model. International Standards Organization, Geneva, Switzerland,1989.
[7]舒挺,EFSM模型协议一致性测试序列自动生成研究.2010.
[8]刘攀,et al.,基于FSM的测试理论,方法及评估.计算机学报,2011.34(6)：p.965-984.
[9]朱振华,许.,周曼丽,网络协议测试方法综述.计算机工程与应用,2005.15：p.5.
[10]李腊元,通信协议工程学进展.计算机研究与发展,1993.7：p.51-60.
[11]Zimmermann, H., OSI reference model--The ISO model of architecture for open systems interconnection. Communications, IEEE Transactions on,1980.28(4):p.425-432.
[12]杨家海,吴建平,史美林,协议的形式描述与自动实现.通信技术,1994.3：p.2-10.
[13]Rayner, D., OSI conformance testing. Computer Networks and ISDN Systems,1987.14(1):p. 79-98.
[14]Wu, J., X. Chen, and R. Hao, PITS-The protocol integrated test system based on formal technology. Journal of Tsinghua University,1998.38(S1):p.2629.
[15]Wang, J., R.Hao, and J. Wu. TUGEN:An automatic test case generator integrating data-flow an control-flow test methods, Session 8 paper 7. in IEEE International Conference on Communications, vl.1998.
[16]孙宇霖,基于构造类别代数协议测试理论的研究.2002,合肥：中国科学技术大学.
[17]郭雄辉,et al.,基于构造类别代数的数据流和控制流相结合的协议测试.北京邮电大学 学报,2003.26(z2).
[18]陈伟琳,周颢,赵保华,利用构造类别代数的协议安全测试方法.西安交通大学学报,2009.42(12)：p.1481-1485.
[19]余营志,赵保华,屈玉贵,基于TCL的路由协议一致性测试.北京邮电大学学报,2003.26(z2).
[20]张波,et al.,基于Tcl的BGP一致性测试系统设计.计算机应用,2003.23(11)：p.49-50.
[21]袁博,et a1.,协议测试中测试序列生成方法综述.军事通信技术,2008.1：p.012.
[22]Bourhfir, C., et al., A test case generation approach for conformance testing of SDL systems. Computer Communications,2001.24(3):p.319-333.
[23]Bourhfir, C, et al., Test cases selection from SDL specifications. Computer Networks,2001. 35(6):p.693-708.
[24]Huang, C.M., M.S. Chiang, and M.Y. Jang, UIO< i> E:a protocol test sequence generation method using the transition executability analysis (TEA). Computer Communications, 1998.21(16):p.1462-1475.
[25]赵保华,陈波,屈玉贵,一种改进的转换可执行分析测试序列生成算法.中国科学技术大学学报,2007.37(9)：p.1096-1100.
[26]Helmy, A., D. Estrin, and S. Gupta. Systematic testing of multicast routing protocols: Analysis of forward and backward search techniques, in Computer Communications and Networks,2000. Proceedings. Ninth International Conference on.2000:IEEE.
[27]Chow, T.S., Testing software design modeled by finite-state machines. Software Engineering, IEEE Transactions on,1978(3):p.178-187.
[28]谢磊,魏蛟龙,朱光喜,基于改进FSM的协议一致性测试方法.通信学报,2011.32(6)：p.172-176.
[29]Chen, W.H., An optimization technique for protocol conformance testing based on the Wp method.2003.
[30]Sabnani, K. and A. Dahbura, A protocol test generation procedure. Computer Networks and ISDN Systems,1988.15(4):p.285-297.
[31]Aho, A.V., et al., An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. Communications, IEEE Transactions on, 1991.39(11):p.1604-1615.
[32]Yu, S.S. and M.T. Liu. A new protocol test sequence generation method based on UIOS. in INFOCOM'92. Eleventh Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE.1992:IEEE.
[33]Chan, W.Y.L., C. Vuong, and M. Otp. An improved protocol test generation procedure based on UIOs. in ACM SIGCOMM Computer Communication Review.1989:ACM.
[34]Chen, W.H., C.Y. Tang, and S.T. Vuong, Improving the UIOv-method for protocol conformance testing. Computer Communications,1995.18(9):p.609-619.
[35]Lombardi, F. and Y.N. Shen, Evaluation and improvement of fault coverage of conformance testing by UIO sequences. Communications, IEEE Transactions on,1992.40(8):p.1288-1293.
[36]Shen, Y.N., F. Lombardi, and A.T. Dahbura, Protocol conformance testing using multiple UIO sequences. Communications, IEEE Transactions on,1992.40(8):p.1282-1287.
[37]Zhang, F. and R.L. Probert. Minimizing the lengths of test sequences with overlapping, in Instrumentation and Measurement Technology Conference,2005. IMTC 2005. Proceedings of the IEEE.2005:IEEE.
[38]Jones, M.T.,人工智能.2010:p.351.
[39]Guo, Q., et al., Computing unique input/output sequences using genetic algorithms. Formal Approaches to Software Testing,2004:p.1098-1100.
[40]Li, J., et al., Evolutionary generation of unique input/output sequences for class behavioral testing. Computers& Mathematics with Applications,2009.57(11):p.1800-1807.
[41]Guo, Q., et al. Constructing multiple unique input/output sequences using metaheuristic optimisation techniques.2005:IET,
[42]Lee, D. and M. Yannakakis, Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE,1996.84(8):p.1090-1123.
[43]Derderian, K., et al., Automated unique input output sequence generation for conformance testing of fsms. The Computer Journal,2006.49(3):p.331-344.
[44]严蔚敏,吴伟民,数据结构：C语言版.1997：清华大学出版社有限公司.
[45]Carl, A., Petri. Kommunikation mit Automaten.1962, Technical Report 2 (Schriften des IIM), Institut f ur Instrumentelle Mathematik, Bonn, Germany,
[46]莫伊,et al.,OSPF协议剖析.2002：中国电力出版社.
[47]汪志宾,模型驱动的协议一致性测试系统的研究与实现.2011,中国科学技术大学.
[2]Lai, R., A survey of communication protocol testing. Journal of Systems and Software,2002. 62(1):p.21-46.
[3]古天龙,蔡国永,网络协议的形式化分析与设计.2003：电子工业出版社.
[4]Belina, F. and D. Hogrefe, The CCITT-specification and description language SDL. Computer Networks and ISDN Systems,1989.16(4):p.311-341.
[5]Interactions, I., ISO 8807:LOTOS—a formal description technique based on the temporal ordering of observational behaviour.1987, Elsevier, Amsterdam.
[6]ISO, I.,9074:Information Processing Systems, Open Systems Interconnection, Estelle:A Formal Description Technique Based on an Extended Finite State Transition Model. International Standards Organization, Geneva, Switzerland,1989.
[7]舒挺,EFSM模型协议一致性测试序列自动生成研究.2010.
[8]刘攀,et al.,基于FSM的测试理论,方法及评估.计算机学报,2011.34(6)：p.965-984.
[9]朱振华,许.,周曼丽,网络协议测试方法综述.计算机工程与应用,2005.15：p.5.
[10]李腊元,通信协议工程学进展.计算机研究与发展,1993.7：p.51-60.
[11]Zimmermann, H., OSI reference model--The ISO model of architecture for open systems interconnection. Communications, IEEE Transactions on,1980.28(4):p.425-432.
[12]杨家海,吴建平,史美林,协议的形式描述与自动实现.通信技术,1994.3：p.2-10.
[13]Rayner, D., OSI conformance testing. Computer Networks and ISDN Systems,1987.14(1):p. 79-98.
[14]Wu, J., X. Chen, and R. Hao, PITS-The protocol integrated test system based on formal technology. Journal of Tsinghua University,1998.38(S1):p.2629.
[15]Wang, J., R.Hao, and J. Wu. TUGEN:An automatic test case generator integrating data-flow an control-flow test methods, Session 8 paper 7. in IEEE International Conference on Communications, vl.1998.
[16]孙宇霖,基于构造类别代数协议测试理论的研究.2002,合肥：中国科学技术大学.
[17]郭雄辉,et al.,基于构造类别代数的数据流和控制流相结合的协议测试.北京邮电大学 学报,2003.26(z2).
[18]陈伟琳,周颢,赵保华,利用构造类别代数的协议安全测试方法.西安交通大学学报,2009.42(12)：p.1481-1485.
[19]余营志,赵保华,屈玉贵,基于TCL的路由协议一致性测试.北京邮电大学学报,2003.26(z2).
[20]张波,et al.,基于Tcl的BGP一致性测试系统设计.计算机应用,2003.23(11)：p.49-50.
[21]袁博,et a1.,协议测试中测试序列生成方法综述.军事通信技术,2008.1：p.012.
[22]Bourhfir, C., et al., A test case generation approach for conformance testing of SDL systems. Computer Communications,2001.24(3):p.319-333.
[23]Bourhfir, C, et al., Test cases selection from SDL specifications. Computer Networks,2001. 35(6):p.693-708.
[24]Huang, C.M., M.S. Chiang, and M.Y. Jang, UIO< i> E:a protocol test sequence generation method using the transition executability analysis (TEA). Computer Communications, 1998.21(16):p.1462-1475.
[25]赵保华,陈波,屈玉贵,一种改进的转换可执行分析测试序列生成算法.中国科学技术大学学报,2007.37(9)：p.1096-1100.
[26]Helmy, A., D. Estrin, and S. Gupta. Systematic testing of multicast routing protocols: Analysis of forward and backward search techniques, in Computer Communications and Networks,2000. Proceedings. Ninth International Conference on.2000:IEEE.
[27]Chow, T.S., Testing software design modeled by finite-state machines. Software Engineering, IEEE Transactions on,1978(3):p.178-187.
[28]谢磊,魏蛟龙,朱光喜,基于改进FSM的协议一致性测试方法.通信学报,2011.32(6)：p.172-176.
[29]Chen, W.H., An optimization technique for protocol conformance testing based on the Wp method.2003.
[30]Sabnani, K. and A. Dahbura, A protocol test generation procedure. Computer Networks and ISDN Systems,1988.15(4):p.285-297.
[31]Aho, A.V., et al., An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. Communications, IEEE Transactions on, 1991.39(11):p.1604-1615.
[32]Yu, S.S. and M.T. Liu. A new protocol test sequence generation method based on UIOS. in INFOCOM'92. Eleventh Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE.1992:IEEE.
[33]Chan, W.Y.L., C. Vuong, and M. Otp. An improved protocol test generation procedure based on UIOs. in ACM SIGCOMM Computer Communication Review.1989:ACM.
[34]Chen, W.H., C.Y. Tang, and S.T. Vuong, Improving the UIOv-method for protocol conformance testing. Computer Communications,1995.18(9):p.609-619.
[35]Lombardi, F. and Y.N. Shen, Evaluation and improvement of fault coverage of conformance testing by UIO sequences. Communications, IEEE Transactions on,1992.40(8):p.1288-1293.
[36]Shen, Y.N., F. Lombardi, and A.T. Dahbura, Protocol conformance testing using multiple UIO sequences. Communications, IEEE Transactions on,1992.40(8):p.1282-1287.
[37]Zhang, F. and R.L. Probert. Minimizing the lengths of test sequences with overlapping, in Instrumentation and Measurement Technology Conference,2005. IMTC 2005. Proceedings of the IEEE.2005:IEEE.
[38]Jones, M.T.,人工智能.2010:p.351.
[39]Guo, Q., et al., Computing unique input/output sequences using genetic algorithms. Formal Approaches to Software Testing,2004:p.1098-1100.
[40]Li, J., et al., Evolutionary generation of unique input/output sequences for class behavioral testing. Computers& Mathematics with Applications,2009.57(11):p.1800-1807.
[41]Guo, Q., et al. Constructing multiple unique input/output sequences using metaheuristic optimisation techniques.2005:IET,
[42]Lee, D. and M. Yannakakis, Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE,1996.84(8):p.1090-1123.
[43]Derderian, K., et al., Automated unique input output sequence generation for conformance testing of fsms. The Computer Journal,2006.49(3):p.331-344.
[44]严蔚敏,吴伟民,数据结构：C语言版.1997：清华大学出版社有限公司.
[45]Carl, A., Petri. Kommunikation mit Automaten.1962, Technical Report 2 (Schriften des IIM), Institut f ur Instrumentelle Mathematik, Bonn, Germany,
[46]莫伊,et al.,OSPF协议剖析.2002：中国电力出版社.
[47]汪志宾,模型驱动的协议一致性测试系统的研究与实现.2011,中国科学技术大学.