【作者】 林华辉；

【导师】 赵??；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2007， 博士

【摘要】 协议测试是协议工程中的一个重要环节，其目的是为了保证协议实现按照协议描述稳定可靠地运行，对于通信产品的质量保证有着重要的意义。协议测试包括四个方面：一致性测试、互操作性测试、性能测试和坚固性测试。一致性测试是为了检测协议实现与协议规范符合的程度，互操作性测试旨在检测同一种或同一类协议的不同实现版本之间的互通互操作能力，此二者均是协议实现体可正确工作的基本保证。在过去的研究工作中，人们主要着重于一致性测试，而对互操作性测试的研究较少。虽然一致性是保证互操作性的一个必要的步骤，但通过一致性测试的协议实现体不一定能正确地互操作，对协议实现体进行直接的互操作性测试是必不可少的。测试系统设计和测试套具的产生是协议测试中要解决的两大问题。测试系统设计重点解决测试方法和测试系统结构的问题，测试套具的产生要解决测试“彻底性”和“标准化”的问题，解决测试套具自动生成问题。互操作性测试的研究工作可以大致分成两类，第一类是对互操作性测试一般概念的研究和互操作性测试的实验，第二类是系统化的互操作性测试序列生成。本文工作的重点是围互操作性测试序列的自动生成和优化、测试覆盖、测试可靠性等相关问题展开的。本文的研究工作主要集中在如下几个方面：(1)基于复合有限状态机模型的最小代价互操作性测试序列生成算法在测试序列生成算法中，测试代价是评估测试序列优劣的一个重要指标。但目前很多互操作性测试的研究工作均只讨论了对系统可以完全描述和完全控制的条件下如何生成满足转移覆盖的互操作性测试序列覆盖互操作系统的交互行为，很少考虑生成的测试序列的代价。本文将分析互操作系统中的测试代价的组成，通过对系统的可达性分析，构造复合有限状态机的加权转移图，采用带权图的边覆盖问题的算法生成最优互操作性测试序列，同时给出了该问题的一个贪心近似算法。该方法可有效地提高测试效率。(2)局部描述系统的互操作性测试序列生成互操作性测试在现实中经常会有这样的情况：需要测试待测系统和另一个现存系统的互操作能力，由于现存系统过于复杂或没有足够的信息，无法对整个互操作系统进行完整地建模描述。在这种情况下生成的测试序列需要满足路径覆盖方可保证互操作性测试的彻底性。本文讨论了在局部描述的互操作系统中基于有向图的单边互操作性测试序列生成算法，提出了互操作性测试的最小完全覆盖准则以指导测试序列的生成，并给出了相应的生成算法。采用该方法可以获得覆盖所有互操作转移序列的最小测试集，在保证测试覆盖率的前提下显著降低测试的代价。(3)测试可靠性及动态测试方法传统的测试序列生成算法都只从静态的角度考虑测试序列的效果，忽略了在测试过程中由于测试序列之间状态转移的相关性而造成的局部测试结果对测试序列执行的影响。引入动态测试方法可以在测试执行时根据测试过程绕过一些局部错误，对待测体实施更完善的测试，并可以避免一些不必要的测试执行。本文提出了基于局部错误诊断信息的动态测试方法，在测试过程中动态收集局部测试信息，采用错误诊断方法对局部错误进行准确定位，再根据诊断结果指导下一步的测试执行。该方法可以更有效地提高测试结果的可靠性和测试执行效率。更多还原

【Abstract】 Protocol Testing is a most important step in protocol engineering, its purpose is to ensure the protocol implementation executed steadily and reliably as the protocol specification, and it is significant for the quality assurance of communication production. Protocol testing includes conformance testing, interoperability testing, performance testing and robust testing. Conformance testing is to check whether the protocol implementation conforms with its specification, while interoperability testing is to check whether two implementations can interoperate properly. Both of them are the based assurance of the implementation’s correctness. In the past, research on communication protocol testing mainly concentrated on conformance test. Although conformance testing is regarded as a necessary step on the way to achieving interoperation, it is agreed that it is insufficient to ensure interoperation of communication network entities. Some sort of direct testing of interoperation is considered indispensable.Design of testing system and generation of testing suite, are the two most significant problems in protocol testing. Testing system design is to solve the problem of testing method and testing framework (or architecture), while testing suite generation is to solve the problem of "thoroughness" , "standardization" , and "automatization" . The research work on interoperability testing can be roughly classified into two categories: general concepts and experiences of interoperability testing, and systematic generation of interoperability test suites.The work in this paper is concentrated on automatically generation method of interoperability test suite, testing coverage, testing reliability, etc. The following are included in detail: (1)Generation method of minimal-cost interoperability test suite. Test cost is a most important guide line to evaluate the test suite in test sequence generation algorithm. But most current research work on interoperability test only discuss how to generate transition-covered test sequence to cover all interoperating behaviors of interactive systems, under the condition that the whole systems can be formally described and controlled, but little is considered about the cost of test sequence. This paper will analyze the composition of the interoperability test cost in detail, construct composite FSM by reachability analysis of system, then use the edge-covered problem of digraph with edge-weight to generate the minimal cost test sequences, and finally give a approximate algorithm with greedy strategy. This method can effectively enhance the test efficiency.(2) Interoperability Testing method of partial-described system.In interoperability test there always exists such a situation: we needto test one system’s interoperability with another exist system, but because we have not enough information about the specification of the existing system, or the system is too complex to be described, we can’t formally describe the whole communicating system. In this case, we should generate test sequences to cover all possible interactive sequences to ensure the thoroughness of test. This paper gives a test method for the partial described system with digraph model, so called unilateral interoperability test method. A test criteria in interoperability test call minimal complete coverage criteria is bring forward and relative test sequences generating algorithm that satisfies the criteria is given. Test suite generated by this algorithm is a minimal set that can cover all interoperating transition sequences. Thus more interoperating error can be checked by executing less test sequences.(3) Testing reliability and dynamic test method The conventional method sometimes gives wrong test results because it is based on static test sequences. That is, faulty transitions that exist in the preamble and the postamble of a static test subsequence have an effect on testing a target transition. To solve this problem, a dynamic protocol test method is introduced in this paper. Dynamic protocol test method can avoid some local error of the implementation under test and apply more sufficient test on it, but the reliability of test result may descend due to the fault of local error indication. When the local-error-diagnostic algorithm is introduced to the dynamic test method, the problem can be solved effectively, the fault coverage can be increased and the running efficiency of test activity can be improved.更多还原