Time-memory tradeoff control in counterexample production

Details Time-memory tradeoff control in counterexample production Time-memory tradeoff control in counterexample production

2002-01-11

2003-12-16

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C703S002000, C703S016000, C703S017000, C703S028000, C714S045000

Reexamination Certificate

active

06665848

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to design automation and verification, and specifically to producing counterexamples in symbolic model checking.
BACKGROUND OF THE INVENTION
Model checking is a method of formal verification that is gaining in popularity as a tool for use in designing complex systems, such as integrated circuits. The method is described generally by Clarke et al. in
Model Checking
(MIT Press, 1999), which is incorporated herein by reference.
To perform model checking of the design of a device, a user reads the definition and functional specifications of the device and then, based on this information, writes a set of properties {&phgr;} (also known as a specification) that the design is expected to fulfill. The properties are written in a suitable specification language for expressing temporal logic relationships between the inputs and outputs of the device. Such languages are commonly based on Computation Tree Logic (CTL). A hardware model M (also known as an implementation) of the design, which is typically written in a hardware description language, such as VHDL or Verilog, is then tested to ascertain that the model satisfies all of the properties in the set, i.e., that M |=&phgr;, under all relevant input sequences.
One of the most useful features of model checking is its ability, when a property &phgr; is found to be false on M, to construct a sequence of states and transitions (a path) that leads to the problematic state of the design. This path is called a counterexample. It can be used by the engineer in understanding and remedying the design defect that led to the failure of the model.
Model checking is preferably carried out automatically by a symbolic model checking program, such as SMV, as described, for example, by McMillan in
Symbolic Model Checking
(Kluwer Academic Publishers, 1993), which is incorporated herein by reference. A number of practical model checking tools are available, among them RuleBase, developed by IBM Corporation. This tool is described by Beer et al. in “RuleBase: an Industry-Oriented Formal Verification Tool,” in
Proceedings of the Design Automation Conference DAC′
96 (Las Vegas, Nev., 1996), which is incorporated herein by reference.
Symbolic CTL model checking, as described by McMillan, involves computing the transition-relation (TR) of the model, and then applying the model checking algorithm to verify a given formula. In many cases, the full TR is too big to be computed. This problem is addressed by Beer et al., in “On-the-fly Model Checking of RCTL Formulas,”
Proceedings of the Tenth International Conference on Computer Aided Verification
(CAV 1998), which is incorporated here in by reference. In this paper, the authors describe a technique for solving CTL formulas of the form AG(p) on the fly, wherein p is a Boolean expression. On-the-fly model checking effectively partitions the TR in such a way as to eliminate the large expenditure of computation resources needed to compute the full TR.
An AG(p) formula states that p is true in every reachable state of the model. Therefore, to disprove this formula, it is sufficient to find one “bad” state in which p is false. On-the-fly model checking is based on the realization that if S is the set of states in which p is false, then in order to find a bad state, it is necessary only to intersect S with the set of reachable states R, and check that the intersection is not empty. Finding this intersection is computationally easy. It can therefore can be performed on the fly, i.e., after each iteration of a reachability analysis used to find R, rather than waiting until the entire extent of R has been determined. If the intersection of S and R is found at any point to be non-empty, the iterations are stopped, and AG(p) is false. A counterexample is then produced by tracing backward from the intersection region, through the states found in the iterations of the reachability analysis, back to one of the initial states. As long as no intersection is found, the process continues until the entire reachable state space has been computed, so that AG(p) is shown to be true. Thus, there is no need to compute the full transition relation. Furthermore, since counterexamples are produced on the fly, only a portion of the reachable state space must be computed when the formula fails, saving even more time and memory space.
In the above-mentioned article, Beer et al. also define a specification language RCTL, as an extension to the conventional CTL language using regular expressions, which makes it possible to translate many CTL formulas conveniently into state machines having an error state. Such formulas can then be verified by on-the-fly model checking of the formula AG(
error). More recently, Beer et al. have extended RCTL to include further expressions and syntax that are useful in creating formulas for on-the-fly model checking, as described in “The Temporal Logic Sugar,”
Proceedings of the Thirteenth International Conference on Computer Aided Verification
(CAV 2001), which is incorporated here in by reference.
SUMMARY OF THE INVENTION
Typically, the most time-consuming step in the process of on-the-fly model checking is computing the next set of states at each iteration of the reachability analysis. (These sets can be seen as a set of concentric rings in state space, and are therefore referred to as “donuts.”) It is desirable to save these donuts for reuse in producing a counterexample trace in case the tested formula is found to be false, in order to avoid having to compute all the donuts twice. Saving all the donuts for such reuse can work well for small-size models.
For model checking of large designs, however, the demand on computer resources involved in saving and maintaining all the donuts is so great that it can cause memory explosion and slow the progress of the model checker to a near standstill. As a result, model checking runs in which the tested formula is found to be true (so that no counterexample exists) are typically completed much faster when the donuts found in the reachability analysis are not saved. When the tested formula is found to be false, however, all the donuts must be recomputed in order to produce a counterexample. This recomputation is a major waste of time and effort. Therefore, neither the approach of saving all the donuts during the reachability analysis nor that of discarding all of them makes optimal use of model checker resources.
In response to this difficulty, preferred embodiments of the present invention provide a method for controlling the amount of memory used to store the donuts during the reachability analysis, so that the model checker runs at optimal speed even on very large models. In these preferred embodiments, a subset of the donuts found in the reachability analysis is saved, while the remaining donuts, between the donuts that are selected to be saved, are discarded. Preferably, a donut is saved once in every n iterations of the reachability analysis, wherein n is an adjustable parameter. When the tested formula is found to be false, and a counterexample must be produced, the saved donuts are used in reconstructing the donuts between them that were previously discarded.
The reconstruction of the donuts and tracing of the counterexample are preferably carried out piece by piece. This process begins with the group of donuts between the last donut that was saved and the final donut, which was found to intersect the target states, and then works backward toward the initial states. After each piece of the counterexample has been traced, the donuts used in producing that piece are discarded, and the next group of donuts is reconstructed. In this manner, memory explosion is avoided, by trading off memory consumption against the added computational burden of recomputing the discarded donuts. The optimal size for n is determined heuristically, based on the size of the design under test and the number of iterations of the transition relation to be used in the reachability analysis, a

Affiliated with

Also associated with

Rating

Time-memory tradeoff control in counterexample production does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Time-memory tradeoff control in counterexample production, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time-memory tradeoff control in counterexample production will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3111090