Method and apparatus for merging hierarchical test subsequence and finite state machine (FSM) model graphs

• US 5,630,051 A
• Filed: 03/06/1995
• Issued: 05/13/1997
• Est. Priority Date: 03/06/1995
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Sun, Xiao, Hull, Carmie A.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): DECADY, ALBERT
• Application Number:
  US08/399,307
• Time in Patent Office: 799 Days
• Field of Search: 395/183.13, 395/183.01, 395/183.08, 371/27
• US Class Current: 714/32
• 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 30/3323 using formal methods, e.g. equivalence checking or property checking

Abstract

Hierarchical Test Subsequence (TS) subgraphs and Finite State Machine (FSM) subgraphs are merged.

Hierarchical FSM subgraphs are merged (82) by connecting FSM model (33) child subgraph transitions or graph edges with states or vertices in the FSM parent subgraph. Matching is done based on Input/Output sequences. This merging (82) is repeated until all FSM child subgraphs are merged into FSM childless subgraphs. FSM childless subgraphs are Merged FSM graphs (83).

Hierarchical Test Subsequence (TS) subgraphs (65) are merged (38) by finding peer subgraphs for TS child subgraphs. TS micro-edges from module entry and to module exit are connected to peer level FSM model states or vertices identified by matching Input/Output sequences. This merging (38) is repeated until all TS child subgraphs are merged into TS childless subgraphs. TS childless subgraphs are Merged TS graphs (39).

Claims

1. A method utilizing a computer for merging Hierarchical Test Subsequence (TS) Subgraphs into a merged Test Subsequence (TS) Graph, the merged Test Subsequence (TS) Graph being used to generate test sequences utilized in testing a Machine Under Test (MUT) for conformance against a Hierarchical Finite State Machine (FSM) model, wherein:

each said Test Subsequence (TS) Subgraph is a Directed Graph stored in a Memory with one or more Test Subsequence (TS) Subgraph Vertices and one or more Test Subsequence (TS) Subgraph Micro-Edges between the Test Subsequence (TS) Subgraph Vertices;

each of said Test Subsequence (TS) Subgraph Micro-Edges corresponds to a Test Subsequence (TS);

each Test Subsequence (TS) comprises an Ordered Sequence of Input/Output (I/O) Sequences; and

all said Test Subsequence (TS) Subgraphs are hierarchically related to each other, wherein;

at least one Test Subsequence (TS) Subgraph is a Parent Test Subsequence (TS) Subgraph,

at least one Test Subsequence (TS) Subgraph is a Child Test Subsequence (TS) Subgraph,

each Child Test Subsequence (TS) Subgraph has one Parent Test Subsequence (TS) Subgraph,

at least one Parent Test Subsequence (TS) Subgraph is a Parentless Test Subsequence (TS) Subgraph,

Parentless Test Subsequence (TS) Subgraphs do not have Parent Test Subsequence (TS) Subgraphs, and

each Child Test Subsequence (TS) Subgraph has an Incoming Test Subsequence (TS) Subgraph Micro-Edge and an Outgoing Test Subsequence (TS) Subgraph Micro-Edge;

said method comprising the steps of;

(a) identifying the Parent Test Subsequence (TS) Subgraph for each Child Test Subsequence (TS) Subgraph;

(b) identifying all Incoming Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges for Each Child Test Subsequence (TS) Subgraph;

(c) merging all Child Test Subsequence (TS) Subgraphs with their corresponding Parent Test Subsequence (TS) Subgraphs by connecting all Incoming Child Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Child Test Subsequence (TS) Subgraph Micro-Edges to Test Subsequence (TS) Subgraph Vertices in Test Subsequence (TS) Subgraphs other than the Child Test Subsequence (TS) Subgraph;

(d) sequentially repeating steps (a)-(c) until all Child Test Subsequence (TS) Subgraphs have been merged with their Parent Test Subsequence (TS) Subgraph to form one or more Merged Parentless Test Subsequence (TS) Subgraph; and

(e) forming the Merged Test Subsequence (TS) Graph for storage in the Memory by combining all of the one or more Merged Parentless Test Subsequence (TS) Subgraphs.

2. The method claimed in claim 1 wherein the step of merging all Child Test Subsequence (TS) Subgraphs with their corresponding Parent Test Subsequence (TS) Subgraphs comprises the substep of:

(1) connecting all incoming Test Subsequence (TS) Subgraph Micro-Edges of Child Test Subsequence (TS) Subgraphs and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges of Child Test Subsequence (TS) Subgraph to Test Subsequence (TS) Subgraph Vertices in the Parent Test Subsequence (TS) Subgraph of the Child Test Subsequence (TS) Subgraph.

3. The method claimed in claim 1 which further comprises the step of:

(f) creating a Merged FSM Graph for storage in the Memory by merging FSM Subgraphs.

4. The method claimed in claim 1 which further comprises the step of:

(f) creating an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Merged Test Subsequence (TS) Graph.

5. The method claimed in claim 4 which further comprises the step of:

(g) creating a Verification Test Sequence (VTS) for storage in the Memory by following a Tour of the Augmented Test Subsequence (TS) Graph.

6. The method claimed in claim 5 which further comprises the step of:

(h) storing data representing the Verification Test Sequence (VTS) in the Memory.

7. A method for testing conformance of the Machine Under Test (MUT) with a Hierarchical FSM Model utilizing the method claimed in claim 5 wherein:

the Verification Test Sequence (VTS) comprises a Sequentially Ordered Series Of Input/Output (I/O) Sequences,

each I/O Sequence includes an Input Stimulus and a corresponding Output Response, and

each said Input Stimulus comprises one or more Input Stimulus Signals;

the method further comprising the steps of;

(h) driving the Machine Under Test (MUT) by sequentially supplying to the Machine Under Test (MUT) each of the Input Stimulus Signals in the Verification Test Sequence (VTS);

(i) comparing Output Responses received from the Machine Under Test (MUT) to the Output Responses associated with each Input Stimulus in the Verification Test Sequence (VTS); and

(j) verifying that the Output Responses received from the Machine Under Test (MUT) match the Output Responses in the I/O Sequences in the Verification Test Sequence (VTS).

8. The method claimed in claim 1 wherein:

said Hierarchical FSM Model has a plurality of FSM Submodels;

each said FSM Submodel has one or more FSM Submodel States and one or more FSM Submodel State Transitions between the FSM Submodel States;

each said FSM Submodel State Transition has a corresponding Input/Out-put (I/O) Sequence;

all said FSM Submodels in the Hierarchical FSM Model are hierarchically related to each other;

each said Test Subsequence (TS) Subgraph Vertex corresponds to one FSM Submodel State;

each Test Subsequence (TS) comprises an Ordered Sequence Of I/O Sequences corresponding to an Ordered Sequence Of FSM Submodel State Transitions in a corresponding FSM Submodel;

all Test Subsequence (1S) Subgraph Vertices in each Test Subsequence (TS) Subgraph correspond to FSM Submodel States in the corresponding FSM Submodel; and

each said Test Subsequence (TS) Subgraph is constructed from the FSM Submodel States and FSM Submodel State Transitions of a Single FSM Submodel.

9. A method utilizing a computer for merging Hierarchical Test Subsequence (TS) Subgraphs into a merged Test Subsequence (TS) Graph, the merged Test Subsequence (TS) Graph being used to generate test sequences utilized in testing a Machine Under Test (MUT) for conformance against a Hierarchical Finite State Machine (FSM) model, wherein:

each said Test Subsequence (TS) Subgraph is a Directed Graph stored in a Memory with one or more Test Subsequence (TS) Subgraph Vertices and one or more Test Subsequence (TS) Subgraph Micro-Edges between the Test Subsequence (TS) Subgraph Vertices;

each of said Test Subsequence (TS) Subgraph Micro-Edges corresponds to a Test Subsequence (TS);

each Test Subsequence (TS) comprises an Ordered Sequence of Input/Output (I/O) Sequences; and

all said Test Subsequence (TS) Subgraphs are hierarchically related to each other, wherein;

at least one Test Subsequence (TS) Subgraph is a Parent Test Subsequence (TS) Subgraph,

at least one Test Subsequence (TS) Subgraph is a Child Test Subsequence (TS) Subgraph,

each Child Test Subsequence (TS) Subgraph has one Parent Test Subsequence (TS) Subgraph,

at least one Parent Test Subsequence (TS) Subgraph is a Parentless Test Subsequence (TS) Subgraph,

Parentless Test Subsequence (TS) Subgraphs do not have Parent Test Subsequence (TS) Subgraphs,

each Child Test Subsequence (TS) Subgraph has an Incoming Test Subsequence (TS) Subgraph Micro-Edge and an Outgoing Test Subsequence (TS) Subgraph Micro-Edge,

said Hierarchical FSM Model has a plurality of FSM Submodels,

each said FSM Submodel has one or more FSM Submodel States and one or more FSM Submodel State Transitions between the FSM Submodel States,

each said FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence,

all said FSM Submodels in the Hierarchical FSM Model are hierarchically related to each other,

each said Test Subsequence (TS) Subgraph Vertex corresponds to one FSM Submodel State,

each Test Subsequence (TS) comprises an Ordered Sequence Of I/O Sequences corresponding to an Ordered Sequence Of FSM Submodel State Transitions in a corresponding FSM Submodel,

all Test Subsequence (TS) Subgraph Vertices in each Test Subsequence (TS) Subgraph correspond to FSM Submodel States in the corresponding FSM Submodel, and

each said Test Subsequence (TS) Subgraph is constructed from the FSM Submodel States and FSM Submodel State Transitions of a Single FSM Submodel;

said method comprising the steps of;

(a) identifying the Parent Test Subsequence (TS) Subgraph for each Child Test Subsequence (TS) Subgraph;

(b) identifying all Incoming Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges for Each Child Test Subsequence (TS) Subgraph;

(c) merging all Child Test Subsequence (TS) Subgraphs with their corresponding Parent Test Subsequence (TS) Subgraphs by connecting all Incoming Child Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Child Test Subsequence (TS) Subgraph Micro-Edges to Test Subsequence (TS) Subgraph Vertices in Test Subsequence (TS) Subgraphs other than the Child Test Subsequence (TS) Subgraph, said merging comprising the substep of;

(1) connecting all incoming Test Subsequence (TS) Subgraph Micro-Edges of Child Test Subsequence (TS) Subgraphs and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges of Child Test Subsequence (TS) Subgraph to Test Subsequence (TS) Subgraph Vertices in the Parent Test Subsequence (TS) Subgraph of the Child Test Subsequence (TS) Subgraph;

(d) sequentially repeating steps (a)-(c) until all Child Test Subsequence (TS) Subgraphs have been merged with their Parent Test Subsequence (TS) Subgraph to form one or more Merged Parentless Test Subsequence (TS) Subgraph; and

(e) forming the Merged Test Subsequence (TS) Graph for storage in the Memory by combining all of the one or more Merged Parentless Test Subsequence (TS) Subgraphs.

10. An apparatus for merging Hierarchical Test Subsequence (TS) Subgraphs into a merged Test Subsequence (TS) Graph, the merged Test Subsequence (TS) Graph being used to generate test sequences utilized in testing a Machine Under Test (MUT) for conformance against a Hierarchical Finite State Machine (FSM) model, wherein:

each said Test Subsequence (TS) Subgraph is a Directed Graph with one or more Test Subsequence (TS) Subgraph Vertices and one or more Test Subsequence (TS) Subgraph Micro-Edges between the Test Subsequence (TS) Subgraph Vertices;

each of said Test Subsequence (TS) Subgraph Micro-Edges corresponds to a Test Subsequence (TS);

each Test Subsequence (TS) comprises an Ordered Sequence of Input/Output (I/O) Sequences; and

all said Test Subsequence (TS) Subgraphs are hierarchically related to each other, wherein;

at least one Test Subsequence (TS) Subgraph is a Parent Test Subsequence (TS) Subgraph,

at least one Test Subsequence (TS) Subgraph is a Child Test Subsequence (TS) Subgraph,

each Child Test Subsequence (TS) Subgraph has one Parent Test Subsequence (TS) Subgraph,

at least one Parent Test Subsequence (TS) Subgraph is a Parentless Test Subsequence (TS) Subgraph,

Parentless Test Subsequence (TS) Subgraphs do not have Parent Test Subsequence (TS) Subgraphs, and

each Child Test Subsequence (TS) Subgraph has an Incoming Test Subsequence (TS) Subgraph Micro-Edge and an Outgoing Test Subsequence (TS) Subgraph Micro-Edge;

said apparatus comprising;

(a) a Memory storing data representing each of the Test Subsequence (TS) Subgraphs;

(b) means for identifying the Parent Test Subsequence (TS) Subgraph for each Child Test Subsequence (TS) Subgraph;

(c) means for identifying all Incoming Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges for Each Child Test Subsequence (TS) Subgraph;

(d) means for merging all Child Test Subsequence (TS) Subgraphs with their corresponding Parent Test Subsequence (TS) Subgraphs by connecting all Incoming Child Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Child Test Subsequence (TS) Subgraph Micro-Edges to Test Subsequence (TS) Subgraph Vertices in Test Subsequence (TS) Subgraphs other than the Child Test Subsequence (TS) Subgraph;

(e) means for sequentially repeating elements (b)-(d) until all Child Test Subsequence (TS) Subgraphs have been merged with their Parent Test Subsequence (TS) Subgraph to form one or more Merged Parentless Test Subsequence (TS) Subgraph;

(f) means for forming the Merged Test Subsequence (TS) Graph by combining all of the one or more Merged Parentless Test Subsequence (TS) Subgraphs; and

(g) means for storing the Merged Test Subsequence (TS) Graph in the Memory.

11. A method utilizing a computer for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

said Hierarchical FSM Model has a plurality of FSM Submodels;

each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;

each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;

all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein;

each said FSM Subgraph Vertex corresponds to one FSM Submodel State,

each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and

each said FSM Subgraph corresponds to one FSM Submodel; and

all said FSM Subgraphs are hierarchically related to each other, wherein;

at least one FSM Subgraph is a Parent FSM Subgraph,

at least one FSM Subgraph is a Child FSM Subgraph,

each Child FSM Subgraph has one Parent FSM Subgraph,

at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and

each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;

said method comprising the steps of;

(a) identifying the Parent FSM Subgraph for each Child FSM Subgraph, wherein;

each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;

(b) identifying all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;

(c) merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph;

(d) repeating steps (a) through (c) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph; and

(e) forming the Merged FSM Graph for storage in the Memory by combining all Merged Parentless FSM Subgraphs.

12. The method claimed in claim 11 wherein the step of merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs comprises the substep of:

(1) connecting Incoming FSM Subgraph Edges of Child FSM Subgraphs and Outgoing FSM Subgraph Edges of Child FSM Subgraphs to FSM Subgraph Vertices in the Parent FSM Subgraph of the Child FSM Subgraph.

13. The method claimed in claim 11 wherein the step of merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs comprises the substep of:

(1) connecting Incoming FSM Subgraph Edges of Child FSM Subgraphs and Outgoing FSM Subgraph Edges of Child FSM Subgraphs to FSM Subgraph Vertices in Another Child FSM Subgraph.

14. The method claimed in claim 11 which further comprises the step of:

(g) creating a Merged Test Subsequence (TS) Graph for storage in the Memory from Test Subsequences (TS) constructed from I/C) Sequences that correspond to FSM Submodel State Transitions.

15. The method claimed in claim 14 which further comprises the step of:

(h) creating an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Merged Test Subsequence (TS) Graph.

16. The method claimed in claim 15 which further comprises the step of:

(i) creating a Verification Test Sequence (VTS) for storage in the memory by touring the Augmented Test Subsequence (TS) Graph.

17. The method claimed in claim 16 which further comprises the step of:

(j) storing data representing the Verification Test Sequence (VTS) in the Memory.

18. A method for testing conformance of a Machine Under Test (MUT) with a Hierarchical FSM Model utilizing the method claimed in claim 16 wherein:

within the step of creating a Verification Test Sequence (VTS) for storage in the memory by touring the Augmented Test Subsequence (TS) Graph;

the Verification Test Sequence (VTS) comprises a Sequentially Ordered Series Of I/O Sequences,

each I/O Sequence includes an Input Stimulus and a corresponding Output Response, and

each Input Stimulus comprises one or more Input Stimulus Signals; and

the method further comprising the steps of;

(j) driving the Machine Under Test (MUT) by sequentially supplying the Input Stimulus Signals comprising each Input Stimulus in the Verification Test Sequence (VTS) to the Machine Under Test (MUT);

(k) comparing Output Responses received from the Machine Under Test (MUT) to the corresponding Output Responses in the Verification Test Sequence (VTS); and

(l) verifying that the Output Responses received from the Machine Under Test (MUT) match the corresponding Output Responses in the Verification Test Sequence (VTS).

19. A method utilizing a computer for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

said Hierarchical FSM Model has a plurality of FSM Submodels;

each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;

each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;

all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein;

each said FSM Subgraph Vertex corresponds to one FSM Submodel State,

each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and

each said FSM Subgraph corresponds to one FSM Submodel; and

all said FSM Subgraphs are hierarchically related to each other, wherein;

at least one FSM Subgraph is a Parent FSM Subgraph,

at least one FSM Subgraph is a Child FSM Subgraph,

each Child FSM Subgraph has one Parent FSM Subgraph,

at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and

each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;

said method comprising the steps of;

(a) identifying the Parent FSM Subgraph for each Child FSM Subgraph, wherein;

each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;

(b) identifying all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;

(c) merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph, said merge comprising the substeps of;

(1) connecting Incoming FSM Subgraph Edges of Child FSM Subgraphs and Outgoing FSM Subgraph Edges of Child FSM Subgraphs to FSM Subgraph Vertices in the Parent FSM Subgraph of the Child FSM Subgraph;

(d) repeating steps (a) through (c) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;

(e) forming the Merged FSM Graph by combining all Merged Parentless FSM Subgraphs; and

(f) storing data representing the Merged FSM Graph in the Memory.

20. An apparatus for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

said Hierarchical FSM Model has a plurality of FSM Submodels;

each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;

each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;

all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein;

each said FSM Subgraph Vertex corresponds to one FSM Submodel State,

each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and

each said FSM Subgraph corresponds to one FSM Submodel; and

all said FSM Subgraphs are hierarchically related to each other, wherein;

at least one FSM Subgraph is a Parent FSM Subgraph,

at least one FSM Subgraph is a Child FSM Subgraph,

each Child FSM Subgraph has one Parent FSM Subgraph,

at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and

each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;

said apparatus comprising;

(a) a Memory containing data representing all of the FSM Subgraphs;

(b) means for identifying the Parent FSM Subgraph for each Child FSM Subgraph, wherein;

each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;

(c) means for identifying all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;

(d) means for merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph;

(e) means for sequentially repeating elements (b) through (d) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;

(f) means for forming the Merged FSM Graph by combining all Merged Parentless FSM Subgraphs; and

(g) means for storing data representing the Merged FSM Graph in the Memory.

21. An apparatus for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

said Hierarchical FSM Model has a plurality of FSM Submodels;

each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;

each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;

all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein;

each said FSM Subgraph Vertex corresponds to one FSM Submodel State,

each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and

each said FSM Subgraph corresponds to one FSM Submodel; and

all said FSM Subgraphs are hierarchically related to each other, wherein;

at least one FSM Subgraph is a Parent FSM Subgraph,

at least one FSM Subgraph is a Child FSM Subgraph,

each Child FSM Subgraph has one Parent FSM Subgraph,

at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and

each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;

said apparatus comprising;

(a) a Memory containing data representing all of the FSM Subgraphs;

(b) a Computer Processor programmed to identify the Parent FSM Subgraph for each Child FSM Subgraph, wherein;

each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;

(c) the Computer Processor programmed to identify all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;

(d) the Computer Processor programmed to merge all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph;

(e) the Computer Processor programmed to sequentially repeat elements (b) through (d) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;

(f) the Computer Processor programmed to form the Merged FSM Graph by combining all Merged Parentless FSM Subgraphs; and

(g) the Computer Processor programmed to store data representing the Merged FSM Graph in the Memory.