| Communication protocols are the mechanisms for establishing communication patterns between different processes within a distributed computer system. A protocol must be checked to ensure conformance to a specified standard.;Conformance testing is based on modeling the protocol as a finite state machine (FSM), and it is usually carried out by applying a test sequence to the FSM. The FSM is tested by verifying each transition using a test subsequence. A test sequence uses a characterizing sequence (i.e. distinguishing sequence (DS), W-set and Unique Input/Output (UIO) sequence) for each state. A characterizing sequence is used to identify the arrival state of the transition under test. It has been proved that the problem of finding a characterizing sequence is NP-complete. This represents a limitation for the practical applicability of FSM-based methods to protocol testing.;In this dissertation, we address the UIO sequence generation problem. UIO sequences check distinctive I/O behaviors for the states in an FSM. This problem consists of finding the minimum length UIO sequences of the states in a protocol.;We introduce new, efficient and practical approaches for finding UIO sequences in communication protocols. These approaches differ from previous approaches based on an exhaustive approach, (such as a breadth-first search, BFS), because appropriate heuristic information is used to speed up the process of UIO generation to find sub-optimal solutions.;Proposed approaches include a Rule-Based Search (RBS) approach, variations of the A... |
