Analyzing an extended finite state machine system model

Details Analyzing an extended finite state machine system model Analyzing an extended finite state machine system model

1999-05-25

2004-02-17

Jones, Hugh (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Simulating electronic device or electrical system

Software program

C703S002000, C703S017000, C716S030000, C716S030000, C717S126000, C717S131000, C717S144000

Reexamination Certificate

active

06694290

ABSTRACT:

BACKGROUND OF THE INVENTION
System testing contributes significantly to system development and maintenance costs. TestMaster® software sold by Teradyne® Software and System Test, Inc. of Nashua, NH can reduce testing costs while increasing testing quality.
Referring to
FIG. 1
, TestMaster® software
100
enables a designer to create
102
an extended finite state machine model of a system. An extended finite state machine is represented by a directed graph that includes states interconnected by transitions. The software
100
provides a graphical user interface that enables the designer to “draw” the model by defining the states and connecting them together with directional lines that represent transitions. The model is independent of the system being modeled and can be created before or after the system is developed.
After the designer creates
102
the model, the software
100
detects
104
paths through the model states and transitions and generates
106
testing programs corresponding to each of the detected paths. Execution of the generated testing programs can identify system design flaws and highlight differences between the model created and the actual behavior of the underlying system.
Referring to
FIG. 2
, an extended finite state machine model
108
of a system includes states
110
-
116
interconnected by transitions
118
-
124
. For example, as shown, a model
108
includes states
110
-
116
and transitions
118
-
124
representing a bank machine system that dispenses cash to customers entering an authorized PIN (Personal Identification Number).
The TestMaster® system automatically detects different paths through the model
108
. For example, as shown in
FIG. 3
, a path through the model can include model elements A-T
AB
-B-T
BC
-C-T
CD
-D. This path corresponds to a customer correctly entering an authorized PIN and successfully withdrawing cash. As shown in
FIG. 4
, a different path through the model can include model elements A-T
AB
-B-T
BD
-D. This model path corresponds to a customer who fails to correctly enter an authorized PIN.
TestMaster® offers many different procedures for detecting paths through a model. For example, a user can select from comprehensive, transition-based, N-switch, and quick-cover path detection. Comprehensive path detection outputs a test for every possible path through the model. Transition based path detection outputs tests such that each transition is included in at least one test. N-switch path detection outputs tests such that each unique sequence of N+1 transitions are included in at least one test. Comprehensive, transition, and N-switch path detection are currently implemented using a depth-first search. In contrast, quick-cover uses a “top-down” search and can output tests such that no transition is used more than a specified number of times. U.S. patent application No. 08/658,344 entitled “Method and Apparatus for Adaptive Coverage in Test Generation” describes implementations of programs for detecting extended finite state machine paths.
Referring again to
FIG. 2
, in addition to transitions and states, a model can incorporate variables and expressions that further define the model's behavior. TestMaster® can evaluate the expressions to assign variable values (e.g., y=mx+b) or to determine whether an expression is TRUE or FALSE (e.g., A AND (B OR C)). The expressions can include operators, variables, and other elements such as the names of states, transitions, and/or sub-models. When a named state, transition, or sub-model is in included in an expression, the model element evaluates to TRUE when included in the path currently being detected. For example, in
FIG. 2
, an expression of “(A && B)” would evaluate to TRUE for path portion “A-T
AB
-B”. As shown, expressions can use a PFL (Path Flow Language) syntax that resembles the C programming language. PFL and functions that can be called from PFL are described in The TestMaster® Reference Guide published by Teradyne®.
A model designer can associate the expressions with model elements to further define model behavior. For example, a designer can associate predicates and/or constraints with different states, transitions, and/or sub-models. Both predicates and constraints are evaluated during path detection and determine which transitions can be included in a path.
When path detection instructions encounter a model element having an associated predicate, the predicate expression is evaluated. If the predicate evaluates to TRUE, the model element associated with the predicate can be used in the path. For example, as shown in
FIG. 2
, transition T
BD
124
has an associated predicate
126
(“!OKPin”) that determines when a path can include the transition. As shown, the predicate
126
is a boolean expression that permits inclusion of the transition
124
in a path being detected when the boolean variable OKPin is FALSE and the path being detected has reached state B.
Similarly, when path detection instructions encounter a model element having an associated constraint, the constraint expression is evaluated. If the constraint evaluates to FALSE, the model element associated with the constraint cannot be used in the path being detected. For example, as shown in
FIG. 2
, a transition
123
can connect a state
114
to itself. To prevent a path from including a large or possibly infinite number of the same transition in a single path, a designer can specify a constraint expression
125
that limits use of a transition in a path. The “Iterate(3)” expression associated with the transition
123
limits a path through the model to including transition
123
three times. Thus, if evaluated at state C after looping around transition T
CC
three times, the constraint would evaluate to FALSE and prevent further use of the transition in the current path. The constraint acts as a filter, eliminating generation of unwanted testing programs.
Referring to
FIG. 5
, a model can also include one or more sub-models. For example, the box labeled “EnterPIN” in
FIG. 2
may be a sub-model
112
that includes additional states
128
-
136
, transitions
138
-
150
, and expressions. As shown, the sub-model
112
sets
150
the model variable OKPin to TRUE when the customer PIN equals 1
148
; otherwise, the sub-model sets the model variable OKPin to FALSE
146
.
Sub-models encourage modular system design and increase comprehension of a model's design. Referring to
FIG. 6
, when the software
100
detects different paths through the system, the sub-model is essentially replaced with the states and transitions included in the sub-model.
Referring again to
FIG. 5
, a designer can define more than one transition
138
-
142
between states
128
,
130
. The designer can also associate expressions (e.g., PIN=1) with each transition
138
-
142
, for example, to set model variables to different values. For example, as shown, a designer has defined three transitions between the “Entry”
128
and “PINEntry”
130
states that each set a PIN variable to different value. Defining multiple transitions between states increases the number of paths through a model. For example, paths through the sub-model
112
can include I-T
IJ(1)
-J-T
JK
-K-T
KM
-M, I-T
IJ(2)
-J-T
JL
-L-T
LM
-M, and I-T
IJ(3)
-J-T
JL
-L-T
LM
-M. The use of multiple transitions enables testing of different conditions within the same model.
SUMMARY OF THE INVENTION
In general, in one aspect, a method of using a computer to analyze an extended finite state machine model of a system includes receiving at least one requirement expression, determining at least one path of states and transitions through the model, evaluating at least one of the requirement expressions based on at least one of the determined paths through the model to determine whether the path satisfies the requirement expression, and generating a report based on the evaluating.
EFSMAs are known to those of ordinary skill in the art. EFSMAs are described in detail in U.S. Pat. No. 5,918,037 (the '037 patent). As described in the '03

Affiliated with

Also associated with

Rating

Analyzing an extended finite state machine system model does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Analyzing an extended finite state machine system model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analyzing an extended finite state machine system model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3310020