Abstract

This thesis is concerned with developing new algorithms for solving some basic problems of conformance testing. In particular, the following problems of conformance testing are considered: (i) generation of test cases from Language Of Temporal Ordering Specification (LOTOS) and Specification and Description Language (SDL), (ii) selection of test cases which meet certain data flow coverage criteria, and (iii) representation of test cases for Local Single-layer (LS) and Remote Single-layer (RS) architectures. The algorithms presented in this thesis can be used to solve in an efficient manner these fundamental problems of conformance testing. These algorithms rely heavily on two concepts: the Extended Finite State Machine (EFSM) chart and the Input/Output (I/O) diagram. In this thesis, we introduce a unified model (using the EFSM chart and the I/O diagram) for existing protocol specification languages. Based on the new unified model, a conceptually simple, easy to implement and computationally efficient methodology is proposed in this thesis for studying conformance testing. In this thesis, the protocol specification is mapped into an EFSM chart. The structure of input/output data is modeled by hierarchical diagrams called I/O diagrams. Test cases are generated from the EFSM chart. Furthermore, a data flow graph is constructed from the chart, and used to identify the protocol functions for testing the data flow aspects of an Implementation Under Test (IUT). The zero-one integer programming technique is used to select test cases to meet the data flow coverage requirement. The selected test cases are modeled as a dependency graph and then evaluated by taking predicate slices from the test case dependency graph. Predicate slices are used to identify infeasible test cases that must be eliminated. Redundant assignments and predicates in all the feasible test cases are removed by reducing the test cases. Reduction is achieved by using the test case dependency graph as well as the data flow graph. The reduced test case dependency graph is adapted for LS and RS architectures. The tester's behaviour in each test case is obtained by a series of transformations called representation and selection. Test case representation refers to the steps of inverting the direction of events and the generation of base and dynamic constraints on the events. These constraints are generated in the form of an I/O diagram. Test case selection refers to the steps of assigning a test purpose according to the hierarchy of test cases in a test suite and then completing the tester's behaviour by assigning verdict and parameter value information.