Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2005-09-13
2005-09-13
Thompson, A. M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S002000, C703S014000
Reexamination Certificate
active
06944838
ABSTRACT:
A design verifier includes a bounded model checker, a proof partitioner and a fixed-point detector. The bounded model checker verifies a property to a depth K and either finds a counterexample, or generates a proof in the form of a directed acyclic graph. If a counterexample is found, the bounded model checker selectively increases K and verifies the property to the new larger depth using the original constraints. If no counterexample is found, the proof partitioner provides an over-approximation of the states reachable in one or more steps using a proof generated by the bounded model checker. The fixed-point detector detects whether the over-approximation is at a fixed point. If the over-approximation is at a fixed-point, the design is verified. If the over-approximation is not at a fixed point, the bounded model checker can iteratively use over-approximations as a constraint and verify the property to a depth K.
REFERENCES:
patent: 5440568 (1995-08-01), Foster
patent: 6698003 (2004-02-01), Baumgartner et al.
patent: 6848088 (2005-01-01), Levitt et al.
patent: 2002/0138812 (2002-09-01), Johannsen
patent: 2003/0225552 (2003-12-01), Ganai et al.
patent: 2004/0019468 (2004-01-01), De Moura et al.
Liang et al., “Incremental deductive & inductive reasoning for SAT-based bounded model checking”, Nov. 7-11, 2004, Computer Aided Design, 2004. ICCAD-2004. IEEE/ACM International Conference on , pp: 502-509□□.
Gupta et al., “Iterative abstraction using SAT-based BMC with proof analysis”, Nov. 9-13, 2003, Computer Aided Design, 2003. ICCAD-2003. International Conference on , pp: 416-423.
Bjeese et al., “Using counter example guided abstraction refinement to find complex bugs”, Feb. 16-20, 2004, Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings, vol.: 1 , pp: 156-161 vol. 1.
Fraer et al., “Accelerated verification of RTL assertions based on satisfiability solvers”, Oct. 27-29, 2002, High-Level Design Validation and Test Workshop, 2002. Seventh IEEE International , , pp.: 107-110.
Jussila et al., “BMC via dynamic atomicity analysis”, Jun. 16-18, 2004 , Application of Concurrency to System Design, 2004. ACSD 2004. Proceedings. Fourth International Conference on , pp.: 197-206.
Kuehlmann et al., “Dynamic transition relation simplification for bounded”, Nov. 7-11, 2004, Computer Aided Design, 2004. ICCAD-2004. IEEE/ACM International Conference on , pp.: 50-57.
Vedula et al., “Program slicing for ATPG-based property checking”, 2004, VLSI Design, 2004. Proceedings. 17th International Conference on , pp.: 591-596.
Gupta et al., “Learning from BDDs in SAT-based bounded model checking”, Jun. 2-6, 2003, Design Automation Conference, 2003. Proceedings , pp.: 824-829.
Clarke et al., “Tree-like counterexamples in model checking”, Jul. 22-25, 2002, Logic in Computer Science, 2002. Proceedings. 17th Annual IEEE Symposium on , pp.: 19-29.
McMillan et al., “Methods for exploiting SAT solvers in unbounded model checking”, Jun. 24-26, 2003, Formal Methods and Models for Co-Design, 2003. MEMOCODE '03. Proceedings. First ACM and IEEE International Conference on, pp.:135-142.
U.S. Appl. No. 60/397,201.
McMillan et al., “Methods for exploiting SAT solvers in unbounded model checking”, Jun. 2003, First ACM and IEEE International conference, pp.: 135-142.
Cabodi et al.; “Can BDDs compete with SAT solvers on Bounded Model Checking?”, Jun. 2002, Design automation conference, Pges.: 117-122.
U.S. Appl. No. 60/397,201 filed Jul. 19, 2002.
Cabodi, Gianpiero et al., “Can BDDs Compete With SAT Solvers on Bounded Model Checking?”, DAC 2002, Jun. 10-14, 2002, New Orleans, Louisiana, USA, Copyright 2002 ACM 1-58113-461-04/02/0006, Abstract.
Biere, Armin, “Verifying Sequential Behavior with Model Checking”, Computer Systems Institute, ETH Zürich, Switzerland, Abstract.
Clarke, Edmund et al., “Bounded Model Checking Using Satisfiability Solving”, Computer Science Department, CMU, Abstract.
A. Biere, C. Artho, V. Schuppan, “Liveness Checking as Safety Checking,” Electronic Notes in Theoretical Computer Science 66 No. 2 (2002), 18 pages.
D. A. Plaisted, S. Greenbaum, “A Structure-preserving Clause Form Translation,” J. Symbolic Computation (1986) 2, Academic Press Inc. (London Ltd.), pp. 293-304.
K. L. McMillan, N. Amla, “Automatic Abstraction with Counterexamples,” Cadence Design Systems, LNCS 2619, 2003, pp. 2-17.
M. W. Moskewicz, C. F. Madigan, “Chaff: Engineering an Efficient SAT Solver,” in Design Automation Conference, 2001, pp. 530-535.
P. Pudlak, “Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations,” The Journal of Symbolic Logic, vol. 62, Number 3, Sep. 1997, pp. 981-998.
M. Sheeran, S. Singh, G. Stalmarck, “Checking Safety Properties Using Induction and a SAT-Solver,”in Formal Methods in Computer Aided Design, 2000, pp. 108-125.
L. Zhang, S. Malik, “Validating SAT Solvers Using an Independent Resolution-Based Checker: Practical Implementations and Other Applications,” In DATE '03, pp. 880-885, 2003.
J.R. Burch, E.M. Clark, K.L. McMillan, D.L. Dill, “Sequential Circuit Verification Using Symbolic Model Checking,” Proc. Design Automation Conf., Orlando, FL, Jun. 1990, pp. 46-51.
J.R. Burch, E.M. Clark, K.L. McMillan, D.L. Dill, L.J. Hwang, “Symbolic Model Checking: 1020 States and Beyond,” in Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science, pp. 1-33, Washington, D.C., 1990, IEEE Computer Society Press.
A. Gupta, Z. Yang, P. Ashar, A. Gupta, “SAT-Based Image Computation with Application in Reachability Analysis,” in FMCAD 2000, pp. 354-371, 2000.
J. Baumgartner, A. Kuehlmann, J. Abraham, “Property Checking via Structural Analysis,” in Computer-Aided Verification (CAV 2002), pp. 151-165.
A. Biere, A. Cimatti, E. Clark, Y. Zhu, “Symbolic Model Checking Without BDDs,” in TACAS '99, vol. 1579 of LNCS, pp. 193-207.
P. Bjesse, “Symbolic Model Checking with Sets of States Represented as Formulas,” Technical Report CS-1990-100, Department of Computer Science, Chalmers Technical University, Mar. 1999, 17 pages.
P.A. Abdulla, P. Bjesse, N. Een, “Symbolic Reachability Analysis Based on SAT-Solvers,” in TACAS 2000, vol. 1785 of LNCS, Springer-Verlag, pp. 411-425.
P. Bjesse, T. Leonard, A. Mokkedem, “Finding Bugs in an Alpha Microprocessor Using Satisfiability Solvers,” Chalmers University of Technology, Sweden, 2001, pp. 454-464.
R. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, vol. C-35, No. 8, Aug. 1986, pp. 677-691.
O. Courdert, C. Berthet, J. C. Madre, “Verification of Synchronous Sequential Machines Based on Symbolic Execution,” BULL Research Center, P.C. 58B, 68 Route de Varsailles, 78430 Louveciennes, France, pp. 365-373.
F. Copty, L. Fix, R. Fraer, E. Giunchiglia, G. Kamhi, A. Tacchella, M. Y. Vardi, “Benefits of Bounded Model Checking at an Industrial Setting,” Formal Property Verifications, Intel Corporation, Haifa, Israel, CAV 2001, LNCS 2102, 2001, pp. 436-453.
E. Goldberg, Y. Novikov, “BerkMin: a Fast and Robust Sat-Solver,” 2002, pp. 142-149.
O. Kupferman, M.Y. Vardi, “Model Checking of Safety Properties,” Formal Methods in System Design, 19, 2001, pp. 291-314.
J. P.M. Silva, K.A. Sakallah, “GRASP-A New Search Algorithm for Satisfiability,” 1996 IEEE, pp. 220-227.
M.Y. Vardi, P. Wolper, “An Automata-Theoretic Approach to automatic Program Verification (Preliminary Report),” IBM research, AT&T Bell Laboratories, 1986 IEEE, pp. 332-344.
P.F. Williams, A. Biere, E.M. Clarke, A. Gupta, “Combining Decision Diagrams and SAT Procedures for E
Blakely , Sokoloff, Taylor & Zafman LLP
Cadence Design Systems Inc.
Rossoshek Helen
Thompson A. M.
LandOfFree
Method and system for design verification using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for design verification using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for design verification using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3421051