【作者】 顾娟；

【导师】 高锦春；

【作者基本信息】 北京邮电大学 ， 电子科学与技术， 2013， 硕士

【摘要】 随着计算机网络的快速发展,网络协议日趋复杂和多样。通常网络协议的规范都是通过自然语言描述的,但由于自然语言的二义性,协议的实现可能不完全符合协议规范,所以对协议一致性测试技术的研究具有较大的应用价值。协议一致性测试是用来检验协议实现是否符合协议规范,其关键技术主要有形式化描述、测试序列生成等。其中,生成测试序列的时空效率以及最终总序列的长度将会影响整个一致性测试过程的实际效率。本论文在对一致性测试技术深入分析的基础上,重点研究了基于有限状态机的测试序列生成方法,尤其是基于UIO的测试序列生成方法,对其容易产生的序列长度较长、爆炸问题等情况进行了分析与优化。’本文首先介绍了一致性测试的基本原理、流程与方法,详细阐述了几种基于FSM的测试序列生成方法,分析对比了各个方法的优缺点。其次，本文介绍了几种经典的基于UIO序列生成的优化方法,在已有优化算法基础上提出了UIOv测试序列生成方法的改进算法,并给出了相应的实验分析,其结果表明,该算法能够在错误覆盖率保持不变的情况下有效缩短总测试序列的长度。然后,本文在现有的UIO序列生成方法基础上提出了一种改进的启发式测试序列生成算法,给出了算法的相关定义及详细流程,并且通过已有算法和本文算法在不同应用场景下的测试,分析了本文算法的效率；通过实验结果分析可知,该方法在估价函数的引导下能快速地找出有限状态机中各状态的UIO序列,并且对于复杂的协议能够避免爆炸问题的产生,有效地提高时空效率。最后,基于本课题的应用背景,根据需求分析给出了测试序列自动生成系统的概要设计及详细设计,编码实现了该系统中各模块的全部功能,并通过实例应用证明了该系统的可执行性。更多还原

【Abstract】 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.更多还原