Selection of initial states for formal verification

Details Selection of initial states for formal verification Selection of initial states for formal verification

2003-01-10

2008-11-18

Rodriguez, Paul L (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Simulating electronic device or electrical system

Circuit simulation

C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

07454324

ABSTRACT:
A computer is programmed to automatically select a state or a set of states of a digital circuit that are visited during simulation, for use as one or more initial states by a formal verification tool. Such automatic selection of one or more simulation states reduces the set of all simulation states to a small subset, thereby to address the state space explosion problem. Depending on the embodiment, the programmed computer uses one or more criteria provided by a library and/or by the user, in making its selection of states. Such criteria may be based on a property (assertion/checker) of the digital circuit and/or a signal generated during simulation. Furthermore, after such criteria (also called “primary criteria”) are applied, the selected states may be pruned by application of additional criteria (also called “secondary criteria”) prior to formal analysis.

REFERENCES:
patent: 5202889 (1993-04-01), Aharon et al.
patent: 5465216 (1995-11-01), Rotem et al.
patent: 5479414 (1995-12-01), Keller et al.
patent: 5539652 (1996-07-01), Tegethoff
patent: 5555270 (1996-09-01), Sun et al.
patent: 5600787 (1997-02-01), Underwood et al.
patent: 5623499 (1997-04-01), Ko et al.
patent: 5630051 (1997-05-01), Sun et al.
patent: 5638381 (1997-06-01), Cho et al.
patent: 5654657 (1997-08-01), Pearce
patent: 5680332 (1997-10-01), Raimi et al.
patent: 5724504 (1998-03-01), Aharon et al.
patent: 5729554 (1998-03-01), Weir et al.
patent: 5862149 (1999-01-01), Carpenter et al.
patent: 6102959 (2000-08-01), Hardin et al.
patent: 6175946 (2001-01-01), Ly et al.
patent: 6192505 (2001-02-01), Beer et al.
patent: 6292765 (2001-09-01), Ho et al.
patent: 6311293 (2001-10-01), Kurshan et al.
patent: 6356858 (2002-03-01), Malka et al.
patent: 6408262 (2002-06-01), Leerberg et al.
patent: 6484088 (2002-11-01), Reimer
patent: 6609229 (2003-08-01), Ly et al.
patent: 6745160 (2004-06-01), Gupta et al.
patent: 6751582 (2004-06-01), Andersen et al.
patent: 6848088 (2005-01-01), Levitt et al.
patent: 6885983 (2005-04-01), Ho et al.
patent: 6915248 (2005-07-01), Ip
patent: 6957404 (2005-10-01), Geist et al.
patent: 6985840 (2006-01-01), Hsu et al.
patent: 7007249 (2006-02-01), Garbowski et al.
patent: 2003/0206730 (2003-11-01), Singhal et al.
patent: 2004/0093571 (2004-05-01), Jain et al.
patent: 2005/0081169 (2005-04-01), Levitt et al.
Burch et al., (Automatic Verification of Pipelined Microprocessor Control, 1994).
Bhagwati et al., (Automatic Verification of Pipelined Microprocessors, 1995).
CheckerWare Data Book, Version 1.4.1, May 2002.
Clarke, et al. “Automatic Verification of finite-state concurrent systems using temporal logic specifications”1986, pp. 244-263, vol. 8, No. 2, ACM Transactions on Programming Languages and Systems, ISSN: 0164-0925.
Clarke, et al. “Bounded Model Checking Using Satisfiability Solving”, 2001, pp. 7-34, Formal Methods in System Design, vol. 19, Issue 1 (Jul. 2001) ISSN: 0925-9856.
Hoskote, et al. “Coverage Estimation for Symbolic Model Checking”, Jun. 1999, pp. 300-305, Annual ACM IEEE Design Automation Conference, Proceedings of the 36th ACM/IEEE conference on Design automation, New Orleans, Louisiana, United States, ISBN: 1-58133-109-7.
U.S. Appl. No. 09/849,005, filed Jun. 16, 2005, Ho, Chian-Min Richard et al.
U.S. Appl. No. 09/635,598, filed Oct. 23, 2003, Ly, Tal An et al.
U.S. Appl. No. 10/340,555, filed Jan. 10, 2003, Levitt, J. et al.
Yatin Hoskote, et al., “Coverage Estimation for Symbolic Model Checking”, Annual ACM IEEE Design Automation Conference, Proceedings of the 38th ACM/IEEE conference on Design automation, New Orleans, Louisiana, United States, pp. 300-305, 1999, ISBN:1-58133-109-7.
Jerry R. Burch, et al., “Automatic Verification of Pipelined Microprocessor Control”, Lecture Notes In Computer Science; vol. 818, Proceedings of the 6th International Conference on Computer Aided Verification, pp. 68-80, 1994, ISBN:3-540-58179-0.
C. Kern, et al. “Formal Verification in Hardware Design: A Survey”, ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 4 , Issue 2 (Apr. 1999), pp. 123-193, ISSN:1084-4309.
Burch et al.; “Symbolic Model Checking: 1020States and Beyond”, Information and Computation, vol. 98, No. 2, Jun. 1992.
Moskewicz, M. et al.; “chaff Engineering and Efficient SAT Solver”; Proceedings of the 38thDesign Automation Conference, Jun. 2001.
Devadas, S., et al.; “An Observability-Based Code Coverage Metric Fro Functional Simulation”; IEEE/ACM International conference on Computer-Aided Design; Nov. 10-14, 1996; pp. 418-425.
Ho, R. et al.; “Validation Coverage Analysis for Complex Digital Designs”; IEE/ACM International Conference on Computer-Aided Design; San Jose, CA; Digest of Technical Papers; Nov. 10-14, 1996.
Geist, D. et al.; “Coverage-Directed Test Generation Using Symbolic Techniques”; Format Methods in Computer-Aided Design, First International Conference; FMCAD.96; Palo Alto, CA; No. 6-8, 1996; pp. 142-159.
Thomas, D. et al.; “The Verilog Hardware Description Language”; Third Edition, Kluwer Academic Publishers; 1996.
http://www.haifa.il.ibm.com/projects/verification/sugar/; 1 page.
http://www.cs.cmu.edu/˜modelcheck/smv.html; 4 pages.
http://www.gnu.org/software/ggc.html; 2 pages.
http://embedded.eecs.berkeley.edu/Respep/Research/vis/; 2 pages.
http://www.mentor.com/products/fv/cdv/checkerware/; 1 page.
U.S. Appl. No. 10/340,555, filed Jan. 10, 2003, Levitt et al.
U.S. Appl. No. 10/340,500, filed Jan. 10, 2003, Seawright et al.
Abdulla, P.A., et al. “Symbolic Rachability Analysis Based on SAT Solvers” TACAS '00, 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), Springer-Verlag, 2000, pp. 411-425.
Amato, et al., “Checking Linked Data Structures” IEEE, pp. 164-173 (1994).
Benso, et al., “Exploiting HLDs for Circuits Fault Tolerance Assessments” 1997, no page number.
Biere, A., et al., “Symbolic Model Checking Using SAT Procedures Instead of BDDs” Proceedings of the Design Automation Conference (DAC '99) Jun. 1999.
Burch, J.R., et al., “Symbolic Model Checkintg: 10.sup.20 States and Beyond” Information and Computation, 1998, pp. 428-439.
Burch, Jerry R., et al., “Automatic Verification of Pipelined Microprocessor Control” published in the proceedings of International Conference on Computer-Aided Verification, LNCS 818, Springer-Verlag, Jun. 1994, pp. 1-17.
Caporossi, et al., “Rule Checking at the Register Level” IEEE Spectrum, pp. 72-73 (1996).
Clarke, E.M., et al., “Automatic Verification of Finite-state Concurrent systems Using Temporal Logic Specifications” published in aCM Transactions on Programming Languages and Systems, 8(2):244-263, 1986.
Devadas, S., et al., “An Observability-Based Code Coverage Metric for Functional Simulation” IEEE/ACM International Conference on Computer-Aided Design, Nov. 10-14, 1996, pp. 418-425.
Dill, David, et al., “Protocol Verification as a Howard Design Aid” published in Proceedings of the International Conference on Computer Design, Oct. 1992, pp. 1-4.
Ganai, M., et al., “Improved SAT-Based Bounded Reachability Analysis” Proceedings of the 15.sup.th International Conference on VLSI Design (VLSID '02), Mar. 2002, 6 pages.
Geist, D., et al., “Coverage-Directed Test Generation Using Symbolic Techniques” Formal Methods in Computer-Aided Design, First International Conf., FMCAD 96, Palo Alto, CA, Nov. 6-8, 1996, pp. 142-159.
Goering, R., et al., “Tool Vendors Attach Verification Logjam” Mar. 4, 2002; http://www.eedesign.com/story/OEG20020304S0018, pp. 1-4.
Gu, J., et al., “Algorithms for the Satisfiability (SAT) Problem: A Survey” DIAMACA Series on Discrete Mathematics and Theoretical Computer Science 35:0-131, American Mathematical Society, 1997, http://C

Affiliated with

Also associated with

Rating

Selection of initial states for formal verification does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Selection of initial states for formal verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selection of initial states for formal verification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4023401