Analytical development and verification of control-intensive systems

• US 5,163,016 A
• Filed: 03/06/1990
• Issued: 11/10/1992
• Est. Priority Date: 03/06/1990
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Har'El, Zvi, Kurshan, Robert P.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Ramirez, Ellis B.
• Application Number:
  US07/489,438
• Time in Patent Office: 980 Days
• Field of Search: 364/578, 364/200, 364/900, 364/488, 364/489, 371/23, 371/22.2, 395/500, 395/919, 395/920
• US Class Current: 716/102
• 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

Designs are created through a high-level to low-level transformation in the form of a formal top-down development procedure based upon successive refinement. Starting with a high-level (abstract) model, such as a formal abstraction of a protocol standard, successively more detailed models are created through successive refinement, in a fashion which guarantees that properties verified at one level of abstraction hold in all successive levels of abstraction. The successive refinements end with a low-level "model" which forms the ultimate implementation of the protocol. In one embodiment of this invention, the analysis/development apparatus creates a unique C language code representation of the specified system that is guaranteed to carry out the tasks specified when executed in a stored program controlled machine. In another embodiment, the code is used to create a "net list" for manufacturing the specified system.

Claims

1. In a computer, a method for creating a sequential circuit comprising the steps of:

receiving a specification and tasks for said sequential circuit;

testing whether said tasks are performable in said sequential circuit when said circuit conforms to said specification;

forming a refined specification by adding detailed information about said specification and defining new tasks to be performed;

formally verifying that said refined specification preserves behavior of said given specification, in that the response of said circuit to input signals when it conforms to said refined specification is consonant with the response of said circuit to the same input signals when it conforms to said given specification;

replacing said tasks with said new tasks and said specification with said refined specification, and returning to said step of testing; and

developing and delivering structure information based on said specification, for effectuating said sequential circuit.

2. The method of claim 1 wherein said step of testing includes testing to determine whether to cease forming a refined specification.

3. In a computer a method for creating a sequential circuit that performs given tasks, comprising the steps of:

entering into an analyzer a specification of said sequential circuit;

forming a refined specification by adding to said analyzer detailed information absent in said specification;

formally verifying that said refined specification preserves behavior of said specification, in that the response of said circuit to input signals when it conforms to said refined specification is consonant with the response of said circuit to the same input signals when it conforms to said specification;

replacing said specification with said refined specification, and returning to said step of forming; and

developing and delivering out of said analyzer structure information based on said specification, for effectuating said sequential circuit.

4. The method of claim 3 further comprising a step of incorporating said structure information in a pattern of connections of an integrated circuit.

5. The method of claim 3 further comprising a step of incorporating said structure information in a layout of an integrated circuit.

6. The method of claim 3 wherein said structure information comprises a sequence of control signals for controlling a processor to effectuate said sequential circuit.

7. The method of claim 6 wherein said control signals are adapted for controlling a stored program processor.

8. The method of claim 7 wherein said control signals form a plurality of modules and each module forms a switch statement construct with reference to no other modules except for modules that control input and output functions of said stored program processor.

9. In a computer, a method for creating a sequential circuit that performs given tasks in accordance with a given specification, comprising the steps of:

defining a reduction of said given specification for each of said given tasks to form a reduced specification for each task;

testing that each reduced specification subsumes said given specification with respect to said task and leaves its corresponding task invariant;

testing each task to determine that it is performable in a circuit that conforms to the reduced specification corresponding to the tested task;

developing circuit structure information, based on said given specification, for effectuating said sequential circuit; and

incorporating said structure information in a pattern of connections of an integrated circuit.

10. The method of claim 9 further comprising a step of incorporating said structure information in a layout of an integrated circuit.

11. The method of claim 9 wherein said structure information comprises a sequence of control signals based on said given specification, for controlling a processor to effectuate said sequential circuit.

12. The method of claim 11 wherein said control signals are adapted for controlling a stored program processor.

13. The method of claim 12 wherein said control signals form a plurality of modules and each module forms a switch statement construct with reference to no other modules except for modules that control input and output functions of said stored program processor.

14. In a computer, a method for creating a sequential circuit comprising the steps of:

entering into an analyzer a circuit specification and tasks;

testing whether said tasks are performable in said sequential circuit when said sequential circuit conforms to said specification;

forming a refined specification by adding to said analyzer detailed information about said specification and entering a new tasks to be performed;

formally verifying that said refined specification preserves behavior of said specification, in that the response of said circuit to input signals when it conforms to said refined specification is consonant with the response of said circuit to the same input signals when it conforms to said specification;

replacing said tasks with said new tasks and said specification with said refined specification, and returning to said step of testing;

defining a reduction of said specification for each of said tasks to form a reduced specification for each task;

testing the reduced specification to determine that each reduced specification subsumes said specification and leaves its corresponding task invariant;

testing each task to determine that it is performable in a circuit that conforms to the reduced specification corresponding to the tested task; and

developing and delivering out of said analyzer structure information based on said specification, for effectuating said sequential circuit.

15. In a computer, a method for creating a sequential machine that conforms to a given specification, which machine performs tasks, comprising the steps of:

developing a refinement specification of said sequential circuit to form a refined candidate specification and defining tasks to be performed by said sequential machine;

testing the assertion that the refined candidate specification is subsumed by said given specification and that the tasks are performable by said sequential machine when said machine conforms to said refined candidate specification;

correcting said refined candidate specification and said tasks when said testing indicates rejection of said assertion;

replacing said given specification with said refined candidate specification and returning to said step of developing a refinement when said testing indicates acceptance of said assertion.

16. The method of claim 15 wherein said steps of testing and correcting comprises the steps of:

refinement testing, to confirm the assertion that said refinement is subsumed by said refined candidate specification,

correcting errors in said refinement when said refinement testing indicates rejection of the refinement testing assertion,

task testing, to confirm the assertion that said tasks are carried out by said refinement,

correcting errors in said refinement and in said tasks when said task testing indicates rejection of task testing assertion.

17. The method of claim 16 wherein said step of testing the assertion that said tasks are carried out by said refinement comprises a step of testing the assertion that said tasks are carried out by a reduced specification of said candidate specification.

18. The method of claim 17 further comprising a step of testing said reduced specification to determine that the behavior of said reduced specification subsumes the behavior of said refined candidate specification.

19. The method of claim 15 wherein said step of specifying a refinement terminates when, for a given set of possible input signals and target output signals, said candidate specification is sufficient to process said inputs signals and develop all of said target output signals.

20. The method of claim 15 further comprising a step of developing a set of control signals for embodying said sequential machine.

21. The method of claim 20 wherein said step of developing a set of control signals comprises developing a sequence of instructions for controlling a stored program controller.

22. The method of claim 21 further including a step of incorporating said instruction in a stored program controller.

23. A sequential circuit for carrying our given tasks, having a stored program processor and a memory, with a signal set stored in said memory having a portion that is essential for performing said given tasks, and said portion consisting of a plurality of modules, with each module forming a switch construct having references to no modules other than modules that control input and output functions of said stored program processor.

24. A controller comprising:

a processor to form a finite state machine with an input port and an output port and which develops prechosen responses at said output port in consequence of input signals at said input port and the state of said finite state machine, having

an execution program for effecting said prechosen responses, and

a memory for storing said execution program,

wherein said execution program, in a portion thereof that is essential to effect said chosen responses, includes switch constructs, with branches of all of said switch constructs including commands selected strictly from a set that excludes calls to functions other than functions that interact with said input port and said output port.

25. Apparatus comprising:

a finite state machine with an input port and an output port and which develops prechosen responses at said output port in consequence of input signals at said input port and the state of said finite state machine, having

an execution program for effecting said prechosen responses,

a memory for storing said execution program, and

a processor connected to said memory and to said input port and output port,

wherein said execution program, in a portion thereof that is essential to effect said chosen responses, includes switch constructs, with branches of all of said switch constructs including commands selected strictly from a set that excludes calls to functions other than functions that interact with said input port and said output port.

26. The apparatus of claim 25 wherein said execution program includes a concatenation of switch constructs, each of which with branches including commands that are selected strictly from said set.

27. A sequential machine, formed form a plurality of interacting finite state machines and having an input port and an output port, comprising:

an execution program to effect chosen responses of said machine at said output port to input signals at said input port,

a memory for storing said execution program, and

a processor connected to said memory and to said input port and output port,

wherein said execution program includes a switch construct for each of said interacting finite state machines, with branches of all of said switch constructs that are essential to effect said chosen responses including commands selected strictly from a set that excludes calls to functions other than functions that interact with said input ports and said output ports.

28. The machine of claim 27 wherein said switch constructs are concatenated.

29. A sequential circuit for carrying our given tasks, comprising:

cooperating modules, where the structure of each of the modules forms a switch construct that is structured in accordance with an iteratively applied method comprising the steps of

developing a circuit specification to form a given specification;

testing whether said given tasks are performable in said sequential circuit when said circuit conforms to said given specification, and whether to continue to a step of forming a refined specification;

forming a refined specification by adding detailed information about said specification and defining new tasks to be performed;

verifying that said refined specification carries out said given tasks with the same responsiveness as those tasks are carried out by said given specification, in that the response of said circuit to input signals, when it conforms to said refined specification, is consonant with the response of said circuit to the same input signals when it conforms to said given specification;

replacing said given tasks with said new tasks and said given specification with said refined specification, and returning to said step of testing; and

developing said set of modules from said given specification.