Browse Prior Art Database

Minimal Length Test Sequences for Protocol Conformance

IP.com Disclosure Number: IPCOM000037110D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 4 page(s) / 63K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+3]

Abstract

This article describes a new algorithmic technique for generating a minimal length test sequence to determine if an implementation of a protocol conforms to its deterministic Finite State Machine (FSM) specification. The disclosed technique is an improvement over techniques proposed in 1,2.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 4

Minimal Length Test Sequences for Protocol Conformance

This article describes a new algorithmic technique for generating a minimal length test sequence to determine if an implementation of a protocol conforms to its deterministic Finite State Machine (FSM) specification. The disclosed technique is an improvement over techniques proposed in 1,2.

The FSM protocol specification is represented as a directed graph with nodes and edges representing states and legal transitions in the FSM. The graph is assumed to be strongly connected, i.e., any state can be reached from any other state. A special state in the FSM is designated as the initial state. Also, there is the special reset command, e.g., power off/on, which brings the implementation immediately from any state to the initial state. The reset command generates null output.

(Image Omitted)

An implementation is a black box with input and output ports.

The state of the implementation cannot be controlled or observed. A Unique Input/Output (UIO) sequence of a state, denoted as Ui for state i, is a sequence of inputs and outputs exhibited only in a sequence of transitions starting from the state 2. To test if an edge is correctly implemented, the technique is to apply the input portion of a segment, which is the concatenation of the edge and the UIO of the ending state of the edge, and examine if the expected outputs are generated. Hence, a test sequence generation procedure in general is
1. generate Ui for all i,
2. establish one segment for each edge in the FSM graph,

and
3. find a minimal length sequence containing all segments.

A UIO generation procedure is given in 2, and establishing segments is straightforward. The only open issue is to find the shortest sequence that includes all segments. Sabnani et al. [2] propose a straightforward procedure which flanks each segment by a transfer path, which is a path from the initial state to the starting state of the segment, and a reset. Aho et al. [1] propose a modified procedure which finds the shortest connection from the end of one segment to the beginning of another. The procedure is the same as the classical Rural Chinese Postman problem [3], if one virtual segment link is added for each segment to the original FSM graph.

The new procedure to be disclosed further shortens the test sequence by taking advantage of overlapping among segments. Segment Si is said to overlap with segment Sj if the final portion of Si is identical to the initial portion of Sj. Overlapping can be included in a formulation leading to the Rural Chinese Postman problem and a matching problem in a bipartite graph [1] as follows:
1. Add a virtual segment link to the FSM graph for each

segment.
2. Add a virtual overlap link from the end of Si to the

1

Page 2 of 4

beginning of Sj if Si overlaps with Sj .
3. Add two virtual segment nodes to start and terminate

each segment link.
4. Add a zero cost virtual link to a starting segment node

from the corresponding real...