The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Formal verification in hardware design: a survey
Abstract
In recent years, formal methods have emerged as an alternative approach to ensuring the quality and correctness of hardware designs, overcoming some of the limitations of traditional validation techniques such as simulation and testing. There are two main aspects to the application of formal methods in a design process: the formal framework used to specify desired properties of a design and the verification techniques and tools used to reason about the relationship between a specification and a corresponding implementation. We survey a variety of frameworks and techniques proposed in the literature and applied to actual designs. The specification frameworks we describe include temporal logics, predicate logic, abstraction and refinement, as well as containment between ω-regular languages. The verification techniques presented include model checking, automata-theoretic techniques, automated theorem proving, and approaches that integrate the above methods. In order to provide insight into the scope and limitations of currently available techniques, we present a selection of case studies where formal methods were applied to industrial-scale designs, such as microprocessors, floating-point hardware, protocols, memory subsystems, and communications hardware.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Computer Architecture: A Quantitative Approach
Hennessy, J. L., & Patterson, D. A. (1989) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 9,370
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
The temporal logic of programs
Pnueli, A. (1977) · 18th Annual Symposium on Foundations of Computer Science (sfcs 1977) · doi:10.1109/sfcs.1977.32 · Cited by 5,689
An axiomatic basis for computer programming
Hoare, C. A. R. (1969) · Communications of the ACM · doi:10.1145/363235.363259 · Cited by 4,002
Holzmann, G. J. (1997) · IEEE Transactions on Software Engineering · doi:10.1109/32.588521 · Cited by 3,803
Automatic verification of finite-state concurrent systems using temporal logic specifications
Clarke, E. M., Emerson, E. A., & Sistla, A. P. (1986) · ACM Transactions on Programming Languages and Systems · doi:10.1145/5397.5399 · Cited by 3,605
The Temporal Logic of Reactive and Concurrent Systems
Manna, Z., & Pnueli, A. (1992) · Springer eBooks · doi:10.1007/978-1-4612-0931-7 · Cited by 2,958
Clarke, E., McMillan, K., Campos, S., & Hartonas-Garmhausen, V. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61474-5_93 · Cited by 2,839
Symbolic model checking: 1020 States and beyond
Burch, J. R., Clarke, E. M., McMillan, K. L., Dill, D. L., & Hwang, L. J. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90017-a · Cited by 2,703
EMERSON, E. A. (1990) · Formal Models and Semantics · doi:10.1016/b978-0-444-88074-1.50021-4 · Cited by 2,585
Symbolic Boolean manipulation with ordered binary-decision diagrams
Bryant, R. E. (1992) · ACM Computing Surveys · doi:10.1145/136035.136043 · Cited by 2,015
A formulation of the simple theory of types
Church, A. (1940) · Journal of Symbolic Logic · doi:10.2307/2266170 · Cited by 1,903
A Decision Method for Elementary Algebra and Geometry
Tarski, A. (1998) · Texts and Monographs in Symbolic Computation · doi:10.1007/978-3-7091-9459-1_3 · Cited by 1,643
Parallel Program Design: A Foundation
Chandy, K. M. (1988) · Medical Entomology and Zoology · Cited by 1,539
PVS: A prototype verification system
Owre, S., Rushby, J. M., & Shankar, N. (1992) · Lecture Notes in Computer Science · doi:10.1007/3-540-55602-8_217 · Cited by 1,415
Harel, D. (1988) · Communications of the ACM · doi:10.1145/42411.42414 · Cited by 1,269
An Automata-Theoretic Approach to Automatic Program Verification
Vardi, M. Y., & Wolper, P. (1986) · ORBi (University of Liège) · Cited by 1,261
Model checking and abstraction
Clarke, E. M., Grumberg, O., & Long, D. E. (1994) · ACM Transactions on Programming Languages and Systems · doi:10.1145/186025.186051 · Cited by 1,211
The complexity of propositional linear temporal logics
Sistla, A. P., & Clarke, E. M. (1985) · Journal of the ACM · doi:10.1145/3828.3837 · Cited by 1,095
“Sometimes” and “not never” revisited: on branching versus linear time temporal logic
Emerson, E. A., & Halpern, J. Y. (1986) · Journal of the ACM · doi:10.1145/4904.4999 · Cited by 1,009
Symbolic model checking: an approach to the state explosion problem
McMillan, K. L. (1992) · Defense Technical Information Center (DTIC) · Cited by 979
Isabelle: A Generic Theorem Prover
Paulson, L. C., & Nipkow, T. (1994) · Cited by 926
Simplification by Cooperating Decision Procedures
Nelson, G., & Oppen, D. C. (1979) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357073.357079 · Cited by 908
Boyer, R. S., & Moore, J. S. (1979) · Cited by 883
Reasoning about Infinite Computations
Vardi, M. Y., & Wolper, P. (1994) · Information and Computation · doi:10.1006/inco.1994.1092 · Cited by 795
The existence of refinement mappings
Abadi, M., & Lamport, L. (1991) · Theoretical Computer Science · doi:10.1016/0304-3975(91)90224-p · Cited by 737
Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics
Leeuwen, J. V. (1994) · Cited by 620
An automata-theoretic approach to branching-time model checking
Kupferman, O., Vardi, M. Y., & Wolper, P. (2000) · Journal of the ACM · doi:10.1145/333979.333987 · Cited by 614
(1994) · Lecture Notes in Computer Science · doi:10.1007/bfb0030541 · Cited by 612
Edinburgh LCF: A mechanised logic of computation
Gordon, M. J. C. (1979) · Medical Entomology and Zoology · Cited by 580
Proving Liveness Properties of Concurrent Programs
Owicki, S., & Lamport, L. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357172.357178 · Cited by 576
Logics and models of real time: A survey
Alur, R., & Henzinger, T. A. (1992) · Lecture Notes in Computer Science · doi:10.1007/bfb0031988 · Cited by 548
Symbolic model checking for sequential circuit verification
Burch, J. R., Clarke, E. M., Long, D. E., McMillan, K. L., & Dill, D. L. (1994) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/43.275352 · Cited by 547
Synthesis of Communicating Processes from Temporal Logic Specifications
Manna, Z., & Wolper, P. (1984) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357233.357237 · Cited by 526
Automata-theoretic techniques for modal logics of programs
Vardi, M. Y., & Wolper, P. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90026-7 · Cited by 522
Pnueli, A. (1986) · Lecture Notes in Computer Science · doi:10.1007/bfb0027047 · Cited by 450
"Sometime" is sometimes "not never"
Lamport, L. (1980) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567446.567463 · Cited by 360
Kleene, S. C. (1967) · Cited by 330
Deciding Combinations of Theories
Shostak, R. E. (1984) · Journal of the ACM · doi:10.1145/2422.322411 · Cited by 298
Formal verification by symbolic evaluation of partially-ordered trajectories
Seger, C.-J. H., & Bryant, R. E. (1995) · Formal Methods in System Design · doi:10.1007/bf01383966 · Cited by 281
The Murphi Verification System
Dill, D. L. (1996) · Computer Aided Verification · Cited by 190
FM8501: A Verified Microprocessor
(1994) · Lecture notes in computer science · doi:10.1007/3-540-57960-5 · Cited by 180
A Practical Decision Procedure for Arithmetic with Function Symbols
Shostak, R. E. (1979) · Journal of the ACM · doi:10.1145/322123.322137 · Cited by 171
An integration of model checking with automated proof checking
Rajan, S. P., Shankar, N., & Srivas, M. K. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60045-0_42 · Cited by 166
A Computational Logic Handbook
(1988) · Elsevier eBooks · doi:10.1016/c2013-0-10412-6 · Cited by 157
High-density reachability analysis
Ravi, K., & Somenzi, F. (1995) · doi:10.5555/224841.224874 · Cited by 137
Principles of Automated Theorem Proving
Duffy, D. A. (1991) · Medical Entomology and Zoology · Cited by 64
Cited by
INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving
Wu, Y., Jiang, A. Q., Ba, J., & Grosse, R. (2020) · arXiv · doi:10.48550/arxiv.2007.02924 · Cited by 30
Metadata
- Authors
- Kern, C., & Greenstreet, M. R.
- Venue
- ACM Transactions on Design Automation of Electronic Systems
- Published
- 1999-04
- Volume
- 4
- Issue
- 2
- Pages
- 123-193
- ISSN
- 1084-4309 (ISSN-L)
- 1557-7309
- OpenAlex
- W2096455207
- Cited by
- 284
- References
- 49
- FWCI
- 12.86
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.