Optimal test generation for finite state machine models

• US 4,991,176 A
• Filed: 06/07/1989
• Issued: 02/05/1991
• Est. Priority Date: 06/07/1989
• Status: Expired due to Fees

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Dahbura, Anton T., Sabnani, Krishan K., Uyar, M. Umit
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Beausoliel, Robert W.
• Application Number:
  US07/362,724
• Time in Patent Office: 608 Days
• Field of Search: 371/27, 371/23, 371/22.1, 371/15.1, 324/73.1, 324/158 R, 364/489
• US Class Current: 714/738
• 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
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00

Abstract

Faster, yet, completely efficient and exhaustive testing is afforded an entity (e.g., protocol, VLSI circuit, software application) represented as finite state machines by employing the present method in which test sequences are generated according to minimum cost function rules. Minimum cost unique signatures are developed for state identification of the finite state machine. Based upon the minimum cost unique signatures, a minimum cost test sequence is generated to cover every state transition of the finite state machine. As a result, every testable aspect of the entity is guaranteed to be tested using a minimum number of steps which represents a considerable cost savings.

Claims

1. A method for developing test sequences for evaluating a design or operation of a finite state machine, said finite state machine characterized by a state diagram having states and original edges interconnecting the states, said method comprising the steps of:

evaluating unique input/output sequences for each state of said finite state machine so that the unique input/output sequence selected for each state exhibits a minimum cost among all unique input/output sequences evaluated for that state;

expanding said state diagram as a test graph including said states, said original edges, and a plurality of test edges interconnecting the states, said plurality of test edges for testing original edges of the state diagram;

evaluating said test graph for symmetry and, if not symmetric, duplicating selected test edges of said plurality to make said test graph symmetric with a minimum cost; and

generating a tour of the symmetric test graph wherein each test edge is traversed at least once, so that said tour includes said test sequence for said finite state machine at a minimum cost.