http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
Algorithms and techniques for unique input/output sequence generation
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 ma-chine(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 U1O sequence generation problem. UIO sequences check distinctive I/0 behaviors for the states in an FSM. This problem consists of finding the minimum length U1O sequences of the states in a protocol. We introduce new, efficient and practical approaches for finding U1O sequences in communication protocols. These approaches differ from previous approaches based on 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 suboptimal solutions. Proposed approaches include a Rule-Based Search (RBS) approach, variations of the A* Algorithms, a Genetic Algorithm, and a Simulated Annealing algorithm. These approaches assume that the FSM is deterministic, strongly connected, reduced and completely speckled. Finally, we compare all methods with the BFS algorithms, and compare the length of the UIO sequence with those of the Distinguishing Sequence and the W-set. For experiments, MCNC FSM benchmarks, randomly generated FSMS, and some commercial protocols are considered.
Issued also on microfiche from University Microfilm Inc.
Includes bibliographical references: pages 150-155.