Research On Passive Testing Of Communication Protocols Based On Finite State Machines

With the development of network technology, networks and communication protocols become more and more complex. The complex protocols and enlarged networks make themselves less reliable. Protocol specifications are called the core of networks and should be obeyed by different communicating entities. In order to ensure the protocol implementations conform to the specifications, it is necessary to use conformance testing techniques. There are two kinds of conformance testing methods: active testing( off-line testing) and passive testing(on-line testing). In active conformance testing, protocol specification is used to generate test sequences, the implementation under test (IUT) is then placed in a dedicated testing environment, according to the predefined test sequences, one(or more) tester sends inputs to the IUT, observes the corresponding outputs, and then analyses them by comparing them with the expected outputs. Passive testing is done by passively observing the inputs and outputs of the IUT without interrupting the normal operation of the networks, which is especially applicable to locating the system faults of running networks. The advantage of active testing lies in that it could control the input of the testing, thus much higher test coverage could be achieved; state homing and fault location are much easier. In active testing, the test sequence length depends on the protocol specifications. If a specification has a lot of states and transitions, the generation of the test sequence is difficult. Most current active testing techniques do not consider testing of the exceptional inputs of the IUT, thus could miss some potential faults. In some special environments, active testing could not be deployed. Passive testing could avoid the shortcomings mentioned above and thus become a useful complement of active testing.Finite State Machine (FSM) is the most commonly used model that describes communication protocols. This paper includes the following parts which mainly focus on the theory and method of passive testing.(1) Identification of missed observations by passive testingThe IUT is running in a network with high speed, thus it is possible that the monitor may fail to capture all packets. In network monitoring system, the missing of key observations may fail the continuous protocol analysis. Thus it is important to deduce the missed observations. In this paper, this problem is solved by constructing the shortest homing sequences between states. Passive testing method is employed to deduce the possible states before missing observation, then backtracing is utilized to get the possible states after missing observations. A consequent method of constructing forest is used to find the qualified homing sequences as the shortest missed ones.(2) Fault coverage analysis in passive testingThe objective of testing is to find the maximal faults with relatively shorter test sequence. In active testing, the test sequence is statically arranged before testing, thus test coverage is independent of actual testing. While in passive testing, the observed sequence is collected at running time. Different observed sequences have different capabilities of finding faults. In order to evaluate this capability, it is necessary to calculate the test coverage of the test sequence. In this paper, a method of analyzing the test coverage by passive testing is proposed, in which fault model is developed firstly, then all possible faults derived from the fault models are generated, finally mutant analysis is used to exclude possible faults. Theoretical and practical results show that increased test sequence and active testing could improve test coverage of passive testing.(3) Fault diagnosis by passive testingAfter detecting the difference between protocol specification and its implementation, how to analyze and locate the difference become more important. In this paper, two mehthods are proposed to sovle the problem.An incremental method of an ideal fault identification algorithm is proposed firstly, in which end states resulting from the faults are recorded during the process of fault identification, a consequent method to distinguish faults by continuing testing from the end states is also given.Secondly, model-based fault diagnosis is introduced to diagnose the faults by passive testing, in which the trace is recorded and mutant analysis method is utilized to generate fault candidates. The size of possible fault set can be reduced by passive observation, active testing can be used to locate the faults. The proposed approach could distinguish equivalent faults, repeated faults and will not be limited by observation steps. Finally this approach is extended to a kind of CFSM.(4) Identification of incremental implementation by passive testingIn internet protocols, most of the state machines are not completely specified. In active testing, traditional automatic test case generation only deals with core events of protocols without considering the non-core events, thus is called weak conformance testing. If a system implements a transition additionally, this kind of testing can not detect the difference. In this paper, an approach is proposed to detect and locate the difference, in which passive testing is employed to confirm that the system has additionally implemented transitions, the possible trace is used to find the possible additionally transitions, cross verification sequence is finally used to identify the transitions. The approach can be applicable to do some finger-printing of target OS and check the exception of the programs.(5) Design and implementation of a protocol testing system using active and passive testingA protocol testing system with high efficiency is developed, in which 1UT could be configured on-line avoiding the high cost of manually configuration, central controller controls several virtual testers to launch the test simplifying the coordination and physical testing networks, XML file is used to organize the test cases and test parameters making the continuous execution of test cases possible, dependency-based test selection method that dynamically determines test sequences and deduces test results helps to improve test efficiency, passive testing is absorbed as a useful complement aiming at improving test coverage.