A New High Level Model to Check CTL Properties in VHDL Environment
Subject Areas : electrical and computer engineering
1 - University of Tehran
2 - University of Tehran
Keywords: Transition relation functions integer equations solverpolynomial integer equationsBDD, Boolean satisfiability,
Abstract :
This paper describes the use of polynomial integer equations for high level model of digital circuits for property checking formal verification at this level. Most formal verification methods use low-level representations of a design like BDDs. BDD operations are not applicable to a large datapath because of large CPU time and memory usage. In our method, a behavioral state machine is represented by a list of integer equations, and RT level properties are directly applied to this representation. Furthermore, this method is applied to circuits without having to separate their data and control sections. For this implementation, we use a canonical form of integer equations, which simplifies equations instead of solving them. This paper compares our results with those of the VIS verification tool that is a BDD based program
[1] R. P. Kurshan, "Formal verification in a commercial setting," in Proc. Design Automation Conf., pp. 258-262, Jun. 1997.
[2] S. Devadas, H. T. Ma, and A. R. Newton, "On the verification of sequential machines at differing levels of abstraction," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 6, pp. 713-722, Jun. 1988.
[3] M. Yoeli, Formal Verification of Hardware Design, IEEE Computer Society Press, Los Alamos, NM, 1990.
[4] P. Camurati and P. Prinetto, "Formal verification of hardware correctness," IEEE Computer, vol. 21, no. 7, pp. 8-19, Jul. 1988.
[5] A. Gupta, S. Malik, and P. Ashar, "Toward formalizing a validation methodology using simulation coverage," in Proc. IEEE Design Automation Conf., pp. 740-745, Jun. 1997.
[6] R. Eastham and K. Thirunarayan, "Proof strategies for hardware verification," in Proc. of National Aerospace and Electronics Conf. (NAECON), vol. 2, pp. 451-458, May 1996.
[7] G. Cabodi, P. Camurati, and F. Corno, "Sequential circuit diagnosis based on formal verification techniques," in Proc. IEEE Int. Test Conf., pp. 187-196, Sep. 1992.
[8] K. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, Boston, 1993.
[9] J. Burch, E. Clarke, K. McMillan, and D. Dill, "Symbolic model checking: 1020 states and beyond," in Proc. of the Fifth Annual IEEE Symp. on Logic in Computer Science, pp. 428-439, Jun. 1990.
[10] M. C. McFarland, "Formal verification of sequential hardware," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 5, pp. 633-645, May 1993.
[11] C. Kern and M. R. Greenstreet, "Formal verification in hardware design," ACM Trans. on Design Automation of Electronic Systems, vol. 4, no. 2, pp. 123-193, Apr. 1999.1. Register transfer level 2. Symbolic simulation
. [12] J. Burch, E. Clarke, D. Long, K. McMillan, and D. Dill, "Symbolic model checking for sequential circuit verification," IEEE Trans. Computer Aided Design, vol. 13, no. 4, pp. 401-424, Apr. 1994.
[13] J. R. Burch, E. M. Clarke, and K. L. McMillan, "Sequential circuit verification using symbolic model checking," in Proc. 27th ACM/IEEE Design Automation Conf., pp. 46-51, 1990.
[14] H. Touati, H. Savoj, and B. Lin, "Implicit state enumeration of finite state machines using BDD’s," in Proc. of the 2th Int. Conf. on Computer Aided Design, pp. 130-133, Nov. 1990.
[15] A. Biere, A. Cimatti, E. M. Clarke, M. Fujita, and Y. Zhu, "Symbolic model checking using SAT procedures instead of BDDs," in Proc. of Design Automation Conf., pp. 317-320, Jun. 1999.
[16] R. Drechsler, Formal Verification of Circuits, Kluwer Academic Publishers, 2000.
[17] C. Y. Huang and K. T. Cheng, "Assertion checking by combined word-level ATPG and modular arithmetic constraint-solving techniques," in Proc. of Design Automation Conf., pp. 118-123,Jun. 2000.
[18] F. Fallah, S. Devadas, and K. Keutzer, "Functional vector generation for HDL models using linear programming and 3-satisfiability," in Proc. of 35th DAC, pp. 528-533, Jun. 1998.
[19] F. Fallah, Coverage Directed Validation of Hardware Models, Ph.D.Thesis, MIT, 1999.
[20] R. Brinkmann and R. Drechsler, "RTL-datapath verification using integer linear programming, " in Proc. of IEEE VLSI Design’01 & Asia and South Pacific Design Automation Conf., pp. 741-746, Bangalore, Jan. 2002.
[21] E. Clarke and E. Emerson, "Design and synthesis of synchronization skeletons using branching time temporal logic," in Logic of Programs Workshop, pp. 52-71, 1981.
[22] E. Clarke, R. Enders, and T. Filkorn, "Exploiting symmetry in temporal logic model checking," Formal Methods in System Design, vol. 9, no. 2, pp. 77-104, 1996.
[23] I. Beer, S. Ben-David, C. Eisner, and A. Landver, "RuleBase: an industry-oriented formal verification tool," in Proc. of the 33rd Design Automation Conf., pp. 655-660, Las Vegas, 1996.
[24] R. K. Brayton, A. Sangiovanni, A. Aziz, et al., "VIS: A system for verification and synthesis," in Proc. of the 8th Int. Conf. on Computer Aided Verification, pp. 428-432, 1996.
[25] J. C. Corbett and George S. Avrunin, "Using integer programming to verify general safety and liveness properties," in Journal of Formal Methods in System Design, vol. 6, no. 1, pp. 97-123, Jan. 1995.