UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Protocol test sequence generation and analysis using AI techniques Ko, Kai-Chung


This thesis addresses two major issues in protocol conformance testing: test sequence generation and test result analysis. For test sequence generation, a new approach based on the constraint satisfaction problem (CSP) techniques, which is widely used in the AI community, is presented. This method constructs a unique test sequence for a given FSM by using an initial test sequence, such as a transition tour or an UIO test sequence, and incrementally generating a set of test subsequences which together represent the constraints imposed on the overall structure of the FSM. The new method not only generates test sequence with fault coverage which is at least as good as the one provided by the existing methods, but also allows the implementation under test (IUT) to have a larger number of states than that in the specification. In addition, the new method also lends itself naturally to both test result analysis and fault coverage measurement. For test result analysis, the CSP method uses the observed sequence as the initial sequence, constructs all fault models which satisfy the initial sequence and introduces additional subsequences to pinpoint the IUT fault model. In addition, a second method for test result analysis is proposed, which is originated from a model of diagnostic reasoning from first principle, another well-known AI techniques which produces all minimal diagnoses by considering the overall consistency of the system together with the observation. Unlike the first method, the second method does not require the computation of all fault models explicitly, and hence is considered to be more suitable for large systems. To our knowledge, the proposed methods in this thesis represent the first attempt in applying AI techniques to the problem of protocol test sequence generation and analysis.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.