Browse Prior Art Database

Computer Communications Automatic Protocol Conformance Generation of Test Cases

IP.com Disclosure Number: IPCOM000121211D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 5 page(s) / 202K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+3]

Abstract

Described is a procedure for the automatic generation of protocol conformance test cases for deterministic finite state machines. The procedure explores the multiplicity of unique input/output (UIO) sequences and overlapping between test cases to generate short test sequences.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 32% of the total text.

Computer Communications Automatic Protocol Conformance Generation
of Test Cases

      Described is a procedure for the automatic generation of
protocol conformance test cases for deterministic finite state
machines.  The procedure explores the multiplicity of unique
input/output (UIO) sequences and overlapping between test cases to
generate short test sequences.

      Protocol conformance testing is critical to inter-operability
of computer communications. Inefficiencies have existed in the
current way of generating test cases in that the test cases have been
generated manually based on intuition, which, as a result, are
tedious and redundant.  Several automatic test sequence generation
procedures, based on unique I/O (UIO) sequences [1], have been
proposed.  A UIO of state i is a sequence of I/O mapping possible
only from state i.  The UIOs are used to indirectly test the states
of black box implementations. With UIOs, an edge from state i to
state j can be tested by a segment which consists of the edge itself
and a UIO of state j.  Testing a protocol consists of constructing a
segment for each edge and finding a test sequence which contains all
segments.  A straightforward procedure finds one UIO for each state
and constructs one segment for each edge, and because of
uncontrollability, flanks each segment by a transfer path from the
initial state to the starting state of the segment and a reset to
form a sub-sequence.

      The concept described herein improves on the above procedure in
three different levels.  The first level is to make the shortest
connections between segments instead of resetting to the initial
state after each segment.  This is the idea presented in (2), which
will be referred to as the procedure S, for shortest connection.  The
second level is to take advantage of the overlapping between segments
to further reduce the cost of connecting segments.  This is the
procedure presented in (3), which will be referred to as the
procedure SO, for shortest connection and overlapping.  The third
level is to go one step further by exploring the multiplicity of UIOs
to amplify the length reduction pertaining to the shortest connection
and the overlapping of segments.  The concept presents a new
procedure, which will be referred to as SOM, for shortest connection,
overlapping, and multiple UIO.

      The SOM procedure starts by generating and storing a set of
UIOs for every state.  This is different from procedures S and SO in
that these two procedures generate only one UIO for each state.  The
first edge in the test sequence must be one that is out of the
initial state.  In the main iteration, the procedure attempts to make
the best use of every edge included in the test sequence, denoted as
SEQ. For example, Fig. 1 shows a protocol for the test sequence. The
test sequence after testing the first edge is SEQ=(0-1-2), because
edge (0-1) is the first one to be tested which requires the edge
(1-2) as...