Research And Application On Heuristic Generation Of Conformance Test Sequence Based On FSM

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.