Passive Testing Theory And Its Application In Protocol Fault Detection

Network devices may have software faults and configuration faults, which lead to network failure or low performance. Protocol fault detection is to discover errors in protocol implementations, improving the performance of network. Passive testing is the process to detect faults by monitoring the device during its normal operation. This thesis is to study passive testing theory and its application in protocol fault detection.A survey is conducted on protocol fault detection methods, including active testing, network management, and protocol analysis. We analyze the flexibilities of these methods, pointing out their deficiencies in on-line fault detection. Because passive testing is developed for on-line and realtime fault detection, it fits the need of network fault management and gains concern in recent years.In this thesis we setup the framework of passive testing. The basic fundamentals and general methods of passive testing are studied. A backward checking technique is proposed to count test coverage. Since the "reasonable environment hypothesis" in active testing is no longer valid in passive testing, an new event-driven model is brought forward for Internet protocols.An efficient passive testing algorithm is developed for protocol data portions. Event-driven extended finite state machine(EEFSM) is proposed for monitoring Internet protocols. In order to trace the configuration of the system under test, path satisfaction needs to be solved. We use integer variables to illustrate the implementation of the algorithm. Integer Linear Programming and Interval Refinement are used for precise and approximate variable tracing. After forward checking, backward checking is carried out to checking the validness of the configurations, which is a reachability analysis. A heuristic approach is proposed to improve the convergence.A test method combining passive testing and protocol simulation is proposed to facilitate network testbed. Protocol simulation is used to generate runtime environments, while passive testing fits the need of protocol analysis. The separation of protocol simulation and protocol analysis can make full use of the existing protocol simulators. We partition the stimuli into common stimuli and protocol related stimuli. A simple simulation method is proposed making use of existing protocol implementations. We show its implementation in Linux, and discuss deterministic and random injection methods.A passive testing tool is developed according to the EEFSM algorithm. Observation inaccuracy problem, which is discovered in experiments, is due to the placement of the observers. A verification method is proposed to solve the inaccuracy with real cases. Implementation errors and interoperability problems are reported from the experiments in some devices. The efficiency of passive testing is illustrated by comparing the test coverage against existing active test results. A problem of an OSPF neighbor state machine implementation is reported in an experiment using protocol simulation and passive testing in testbed. Another experiment shows a simple case of network fault location by deploying observers.Network protocol specifications may be non-deterministic due to options, while the implementations are commonly deterministic by selecting desired options. We study the problem of deriving the implementation machine from the specification machine. Non-deterministic transitions may be observable or non-observable. An implementation machine may or may not be a subautomaton of the specification machine. Thus there are four cases, from easy to difficult. On-line checking algorithms using backtracking are proposed to identify the object machine. Examples from Internet protocols are given to show their usage.