Automatic test case generation of conformance testing for communication protocols specified in extended models.

摘要

A communication protocol, which is a set of rules governing the operation of a computer network, is essential for supporting the network's reliability. The written statement of these rules is called a protocol specification, which cannot function unless it is implemented. However, due to human errors or incompatibilities between the protocol and its lower layer systems, a protocol implementation may not behave as specified. Thus, conformance testing is used to ensure the consistency between a protocol specification and its implementation. An important area of conformance testing is test case generation (TCG), which automatically generates a set of test cases to discover any discrepancy between a protocol specification and its implementation.;Test case generation has been studied in the literature for protocols specified by the Finite State Machines (FSMs) model. However, many practical, real-world protocols are hard or infeasible to be specified by the FSM model because the model contains no memory. As the result, more sophisticated models with memory, called extended models, are used in practice. Although extended models can dramatically simplify a protocol specification, both the control and data flows of the specification need to be considered in order to generate a test case. Unfortunately, because of the difficulty in tracing the data flow, generating a test case for extended models remains a challenging problem, and little research has been done on this area.;In this dissertation, the test case generation problem for extended models is introduced. Because of its simplicity and generality, EFSM (Extended Finite State Machine) is used as the model in this dissertation. It is found that axiomatic semantics is a suitable technique for monitoring the data flow of an EFSM. Using axiomatic semantics as a tool, several methods for EFSM test case generation are proposed. The first method, called ATG (Axiomatic Test case Generation), generates test cases for the single-transition fault. Based on the same technique, the second method, called OAT (Optimized ATG), uses more complicated axioms to derive shorter test cases.;Next, a behavior model is proposed to describe the dynamic behavior of an EFSM. Using the model, TGF (Test case Generation for given Fault models) is used to generate a test case based on a given fault model. This method is also extended to generating test cases for an OSI standard specification language, Estelle. Finally, it is found that TGF can be transformed into a protocol validation problem. Therefore, many existing protocol validation tools can be used to generate test cases. As a result, a test case generator is implemented using an existing protocol validation tool.