Timing verification by successive approximation

• US 5,483,470 A
• Filed: 06/29/1992
• Issued: 01/09/1996
• Est. Priority Date: 03/06/1990
• Status: Expired due to Fees

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Alur, Rajeev, Itai, Alon, Kurshan, Robert P., Yannakakis, Mihalis
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US07/906,082
• Time in Patent Office: 1,289 Days
• Field of Search: 364/578, 364/232.3, 364/281.6, 364/933.8, 364/488, 364/489, 364/512, 364/553, 395/500, 395/66, 395/67, 395/919, 395/920, 395/921, 395/922
• US Class Current: 716/108
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking

Abstract

Apparatus for developing and verifying systems. The disclosed apparatus employs a computationally-tractable technique for verifying whether a system made up of a set of processes, each of which has at least one delay constraint associated with it, satisfies a given temporal property. The technique deals with the verification as a language inclusion problem, i.e., it represents both the set of processes and the temporal property as automata and determines whether there is a restriction of the set of processes such that the language of the automaton representing the restricted set of processes is included in the language of the automaton representing the temporal property. The technique is computationally tractable because it deals with the problem iteratively: it tests whether a current restriction of the set of processes is included, and if not, it employs a counter-example for the inclusion to either determine that the delay constraints render satisfaction of the given temporal property or to derive a new restriction of the set of processes. Further included in the disclosure are techniques for checking the timing consistency of the counter-example with respect to a delay constraint and techniques for finding the optimal delay constraint.

Claims

1. An improved method performed in a computer system for generating a machine-executable implementation specification for a system from a logical definition of an implementation of the system and a logical definition of the system'"'"'s behaviour the logical definition of the system'"'"'s behavior including a given temporal property and the logical definition of the implementation specifying a set of processes, each of which has delay constraint, the method including a step of verifying that the system will satisfy the logical definition of the system'"'"'s behavior and the improvement comprising the steps practiced in the the step of verifying of:

determining whether a test set of processes derived initially from the set of processes satisfies the given temporal property, and if the test set does, returning an indication that the system satisfies the given temporal property and terminating the method; and

otherwise providing a counter example of a sequence of behaviors of the processes of the test set which does not satisfy the given temporal property;

determining whether the counter example is timing consistent with the delay constraints and if the counter example is timing consistent, returning an indication that the system cannot satisfy the given temporal property and terminating the method; and

employing the counter example to restrict the test set of processes and repeating the steps of the method with the restricted test set as the test set.

2. The method set forth in claim 1 wherein:

the step of employing the counter example to restrict the test set further comprises the steps of;

finding the minimum subset of delay constraints for which the counter example holds and

restricting the test set of the processes as required by the minimum subset of delay constraints.

3. Improved apparatus implemented in a computer system for generating a machine-executable implementation specification for a finite state machine of practical size, the apparatus including

refinement means for receiving a model of the finite state machine and refining the model and

verification means for receiving the refined model and a task for the model which specifies a given temporal property and responding to the refined model and the task by verifying that the refined model can perform the task and

the improvement comprising:

timing verification means in the verification means for verifying that delay constraints in the refined model satisfy the given temporal property, the timing verification means remaining computationally tractable for the finite state machine.

4. The apparatus set forth in claim 3 wherein:

the model includes a set of processes, each of which has at least one of the delay constraints; and

the timing verification means comprises

means for determining whether a test set of processes derived from the set of processes satisfies the given temporal property, and if the test set does, returning an indication that the system satisfies the given temporal property; and

otherwise providing a counter example of a sequence of behaviors of the processes of the test set which does not satisfy the given temporal property;

means for determining whether the counter example is timing consistent with the delay constraints and if the counter example is timing consistent, returning an indication that the system cannot satisfy the given temporal property and terminating the method; and

means for employing the counter example to restrict the test set of processes and repeating the steps of the method with the restricted test set as the test set.

5. The apparatus set forth in claim 4 wherein:

the means for employing the counter example to restrict the test set includes

means for finding the minimum subset of delay constraints for which the counter example holds and

means for restricting the test set of the processes as required by the minimum subset of delay constraints.

6. The apparatus as set forth in claim 3 further comprising:

means for producing the finite state machine.

7. A method used in apparatus for developing a finite state machine to develop a finite state machine of practical size comprising the steps performed in the apparatus for developing the finite state machine of:

receiving a model of the finite state machine;

refining the model; and

verifying that the refined model can perform a task which specifies a given temporal property, the step of verifying including the step of

verifying for the finite state machine in a computationally tractable manner that delay constraints in the refined model satisfy the given temporal property.

8. The method set forth in claim 7 wherein:

the model includes a set of processes, each of which has at least one of the delay constraints; and

the step of verifying that the delay constraints satisfy a given temporal property includes the steps of

determining whether a test set of processes derived from the set of processes satisfies the given temporal property, and if the test set does, returning an indication that the system satisfies the given temporal property; and

otherwise providing a counter example of a sequence of behaviors of the processes of the test set which does not satisfy the given temporal property;

determining whether the counter example is timing consistent with the delay constraints and if the counter example is timing consistent, returning an indication that the system cannot satisfy the given temporal property and terminating the method; and

employing the counter example to restrict the test set of processes and repeating the steps of the method with the restricted test set as the test set.

9. The method set forth in claim 8 wherein:

the step of employing the counter example to restrict the test set includes the steps of

finding the minimum subset of delay constraints for which the counter example holds and

restricting the test set of the processes as required by the minimum subset of delay constraints.

10. The method set forth in claim 7 further comprising the step of:

producing the finite state machine.

11. Improved apparatus implemented in a computer system for generating a machine-executable implementation specification for a system from a logical definition of the implementation and a logical definition of the system'"'"'s behavior, the behavior including a given temporal property and the logical definition of the implementation specifying a set of processes with delay constraints, the apparatus including verification means for verifying that a system implemented according to the logical definition of the implementation will perform according to the logical definition of the system'"'"'s behavior, and the improvement comprising:

timing verification means in the verification means for verifying that the delay constraints satisfy the given temporal property by executing steps including

determining whether a test set of processes derived initially from the set of processes satisfies the given temporal property, and if the test set does, returning an indication that the system satisfies the given temporal property and terminating the method; and

otherwise providing a counter example of a sequence of behaviors of the processes of the test set which does not satisfy the given temporal property;

determining whether the counter example is timing consistent with the delay constraints and if the counter example is timing consistent, returning an indication that the system cannot satisfy the given temporal property and terminating the method; and

employing the counter example to restrict the test set of processes and repeating the steps of the method with the restricted test set as the test set.