Research On Automatic Generation Of Conformance Test Sequences For EFSM-Specified Protocols

With the popularization and the need for diversity of communication network, network protocols become more and more complex, which faces the new challenge on the development and implementation of protocols. According to the characteristics of communication network, such as distribution, heterogeneity and real-time performance, the implementation of network protocols needs not only correct functional behaviour, but favorable consistent interconnection as well. Actually, small deviations between the implementation and the specification of network protocols are likely to bring disastrous consequences to communication network. Protocol conformance testing aims to check the degree of conformance between a protocol specification and its implementation, which is one of the important means for ensuring the quality of network communication. Traditionally, conformance testing sequences are manually generated so that it is very time consuming and expensive to obtain. Moreover, the quality of the generated test sequences is difficultly ensured. In order to avoid the above drawbacks, there have been some efforts to automatically generate protocol conformance testing sequences using the extended finite state machine (EFSM). Thus, how to automatically generate conformance testing test sequences for the protocol modeled as EFSM has been the focus in recent research.Compared with Finite-state machines model, EFSM model contains a set of additional context variables and predicates, which enhances the capability of modeling the control portion and data portion of a real-time system. Additionally, it adds the difficulty in automatic generation of conformance testing sequences (AGCTS) for EFSM-based protocols. Currently, research topics on AGCTS based on EFSM are mainly centralized as follows:1) How to generate the executable state identification sequences; 2) How to guarantee the executability of conformance testing sequences generated; 3) How to design a method enabling executable control flow and data flow conformance test sequence generation for EFSM models; 4) How to design an automatic generation tool of protocol conformance testing sequences based on EFSM. This thesis focuses on the above four problems and systematically investigates the key technique for automatic generation technique of conformance testing sequences based on EFSM. The main contributions of this thesis are the following:(1) This thesis presents a new executable state identification sequences approach (ESIS). The approach, from the aspect of state identification demand and the EFSM configure projection subspace. adopts fractional-step computation to generate the shortest ESIS in the specific identification scene through searching a Executability Analysis Tree (EAT) in bread-first-search way. Thus, it avoids the complexity incurred by computing all state identification sequences by single step in the whole state configure space.(2) Through analyzing breadth first search of EAT in the generation process of ESIS, this thesis presents an adaptive method of ESIS and describes two concepts of EAT:transition distinction degree factor and node convergence degree factor. The new algorithm considers EAT node weight function as node search engine and transforms automatic generation of ESIS into adaptive exploration of the maximum weight node from unexplored nodes in EAT. The experimental results show that adaptive generation method of ESIS has better space-time characteristic in comparison with breadth first search method.(3) This thesis presents an executable testing sequences generation method using heuristic search EFSM protocol state space. And on this basis, a new control flow test method is proposed. Instead of traditional breadth first search, the new algorithm uses the exploring strategy of heuristic state pattern to search the minimum weight path. The experimental data show that the proposed method can effectively alleviate the state space explosion problem in the executability analysis process.(4) This thesis discusses the intrinsic characteristic and dependence relations of transitions in EFSM in detail. After defining the adjacency transition dependence graph (ATDG), this thesis presents an executable testing sequences generation method of the EFSM model based on the ATDG. Then, the proposed algorithm provides a new testing sequences generation method of control flow and data flow. Specifically, the proposed algorithm first classifies transition according to its variables and predicates. Next, dependence relationship among transitions is deeply mined. Finally, the executable test sequences are generated, using executability analysis guided by an adaptive exploration function. The proposed algorithm guarantees the executability of testing sequences generated and balances the shortest length and the generation cost of testing sequences.(5) According to the proposed methods above, this thesis describes an automatic generate integration environment design of the executable conformance testing sequences based on EFSM and realizes a prototype system. This integration testing environment supports several key parts of protocol conformance testing sequences:protocol formalization modeling, automatic generation of conformance test sequences and TTCN-3 formalization description of testing sequences.