Method and apparatus for generating tests for structures expressed as extended finite state machines

• US 5,394,347 A
• Filed: 07/29/1993
• Issued: 02/28/1995
• Est. Priority Date: 07/29/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Lynch, Thomas M., Kita, Ronald A., Tremblay, Sylvia C.
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US08/100,002
• Time in Patent Office: 579 Days
• Field of Search: 364/578, 364/579, 364/580, 364/489, 364/490, 364/488, 364/191, 395/500, 395/922, 371/19, 371/23, 371/22.2, 371/27
• US Class Current: 703/2
• CPC Class Codes: G01R 31/318357 Simulation computer simulation of digital circuits G06F30/3308
• CPC Class Codes: G01R 31/318371 Methodologies therefor, e.g. algorithms, procedures
• CPC Class Codes: G06F 11/3672 Test management
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking

Abstract

A method for generating test programs for an implementation of a specification that has been modeled as an extended finite state machine (EFSM), the EFSM including vertices and transitions, where the transitions represent functions to be performed by the implementation, including predicates and actions such as variable assignments. The method includes traversing the EFSM in a depth-first manner from a root model start state to a root model exit state, through intermediate vertices which may be normal states or models. Models include further vertices and transitions, and may be called as submodels or as go-to models, where a go-to model includes an EFSM exit state. The EFSM may be traversed exhaustively, such that all possible paths are traversed, or in a partial transition coverage mode, where a user-defined subset of the possible paths are traversed. Each traversed path is stored in a path file and converted into a test program in a predetermined language, such as C, for interfacing with the implementation to be tested and testing its functions as represented by the transitions taken. Traversal of the EFSM is made possible by the use of a model stack, a path stack and a variables stack, which keep track of all models called, transitions and vertices encountered, and variable values assigned or altered in the course of the traversal, with cross-referencing to ensure that any desired set of path files can be automatically generated while tracking all parameters necessary to conduct the traversal.

Claims

1. A method for automatically generating at least one test program in a predetermined computer language for testing an implementation of a specification for a predefined system, the specification being expressed as an extended finite state machine (EFSM), the EFSM comprising a root model having a plurality of vertices including a root model start state, a root model exit state, and at least one root model intermediate vertex, the EFSM further having a plurality of transitions, each transition connecting two said vertices and each vertex being connected to at least one other vertex by at least one said transition, the transitions representing functions of the system as defined in the specification, each said transition having zero or more correlated annotations thereto, the annotations including predicates, actions and events defined by the specification and constraints on execution defined by a user, said at least one intermediate vertex including at least one vertex comprising a submodel which itself includes a plurality of vertices including a submodel start state, a first submodel exit state and at least one submodel intermediate vertex, the method comprising traversing the EFSM through at least one path, to generate a path file as a basis for said test program, the method including the steps of:

(1) generating a model stack for tracking, at any given point in the path, the current model for the traversal, the model stack including a model frame index pointing to a current model at any given time in the traversal;

(2) generating a path stack for tracking transitions taken in said path, the path stack including a plurality of frames, each frame having a plurality of fields including at least a field storing a current vertex, a field storing a current transition, and a field storing a link count for determining the number of times a transition has been taken from the current vertex, and a field storing a flag indicating whether any variables values were changed in reaching the current vertex, the path stack further having an index for pointing to a current model stack frame;

(3) generating a variables stack for tracking assignments and value changes for variables used in the specification, the variables stack including a plurality of frames, each frame for storing in a plurality of fields each value taken by each variable in the traversal of the path;

(4) initializing the traversal, including;

pushing the root model onto a first frame of the model stack;

initializing any model parameters and variables defined in model declaration statements of said EFSM;

setting the root model start state as a current state of the traversal; and

saving current values of variables at a first frame of the variables stack;

(5) determining whether the link count for the current path stack frame is less than the number of transitions originating from the current state, and if not, proceeding to step 9;

(6) selecting a next transition from the current state;

(7) determining whether the vertex at a terminus of the current transition is a submodel, and if so, proceeding to step 8, and if not, processing the current transition, including executing any predicates, constraints and actions, updating the path stack with a new frame relating to a new transition if the current transition is taken, updating the variables stack with any changes in values of the variables, and returning to step 5;

(8) processing a submodel invocation, including executing any predicates, constraints and actions, limiting the invocation according to any recursion restraint on the current transition, and updating the model stack with the invoked submodel if the current transition is taken, updating the path stack with a new frame if the current transition is taken, and updating the variables stack if any variable values have changed, and returning to step 5;

(9) if the current state is a submodel exit and all transitions of the current state have been taken and loops from the current state have been completed, generating and taking submodel outbound transition to the calling model, restoring the model frame index to the calling model, restoring the variable values to those of the calling model, setting the current state to the vertex from which this submodel was called, and returning to step 5;

(10) if the current state is the root model exit state, proceeding to step 12;

(11) backing up one state in the path generated so far, including;

popping the most recent frame off the path stack, while maintaining the popped vertex and transition as current;

if an outbound transition from a submodel was popped, popping the path stack again, while maintaining the popped vertex and transition as current, and restoring any changed variables;

if an inbound transition to a submodel was popped, restoring the current model stack index, popping the model stack and restoring any changed variables;

for any other transition, restoring any changed variables; and

returning to step 5; and

(12) processing the path to completion, including generating a test program based upon the path taken in said traversal, the test program being in said predetermined computer language and including an interface with said predefined system.

2. The method of claim 1, where step 12 includes the step of returning to step 11, for performing steps 5 through 11 until all possible paths through the EFSM have been traversed.

3. The method of claim 1, where step 12 includes the step of returning to step 11, for performing steps 5 through 11 until a predefined subset of all possible paths through the EFSM have been traversed.

4. The method of claim 1, including the step of limiting the number of times a submodel is called recursively.

5. The method of claim 1, wherein step 7 includes the steps of:

incrementing the link count of the current path stack frame;

pushing the selected transition onto the current frame in the path stack, incrementing the path stack index to point to a new frame, and setting the link count to zero;

if there are any predicates or constraints annotated to the current transition that are false, popping the current transition and current state of the stack, decrementing the path stack index, restoring variable values if any were changed in step 7, setting the current state to the state just popped, and returning to step 5;

executing any actions annotated to the current transition;

if any variable values have changed in step 7, saving the new values in a new frame on the variables stack;

setting the current vertex to the vertex at the terminus of the current transition; and

returning to step 5.