The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Counterexample-guided abstraction refinement for symbolic model checking
Abstract
The state explosion problem remains a major hurdle in applying symbolic model checking to large hardware designs. State space abstraction, having been essential for verifying designs of industrial complexity, is typically a manual process, requiring considerable creativity and insight.In this article, we present an automatic iterative abstraction-refinement methodology that extends symbolic model checking. In our method, the initial abstract model is generated by an automatic analysis of the control structures in the program to be verified. Abstract models may admit erroneous (or "spurious") counterexamples. We devise new symbolic techniques that analyze such counterexamples and refine the abstract model correspondingly. We describe aSMV, a prototype implementation of our methodology in NuSMV. Practical experiments including a large Fujitsu IP core design with about 500 latches and 10000 lines of SMV code confirm the effectiveness of our approach.
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
(1979) · Cited by 43,841
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
Cousot, P., & Cousot, R. (1977) · Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77 · doi:10.1145/512950.512973 · Cited by 6,279
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
Self-citationClarke, 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
Self-citationSymbolic 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
Self-citationReducibility Among Combinatorial Problems
Karp, R. M. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_8 · Cited by 2,490
Design and synthesis of synchronization skeletons using branching time temporal logic
Clarke, E. M., & Emerson, E. A. (2005) · Lecture Notes in Computer Science · doi:10.1007/bfb0025774 · Cited by 2,219
Self-citationConstruction of abstract state graphs with PVS
Graf, S., & Saidi, H. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-63166-6_10 · Cited by 1,454
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
Self-citationComputer-aided verification of coordinating processes: The automata-theoretic approach
(1995) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(95)90267-8 · Cited by 786
Symbolic model checking using SAT procedures instead of BDDs
Biere, A., Cimatti, A., Clarke, E. M., Fujita, M., & Zhu, Y. (1999) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/309847.309942 · Cited by 752
Self-citationNUSMV: a new symbolic model checker
Cimatti, A., Clarke, E. M., Giunchiglia, F., et al. (2000) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s100090050046 · Cited by 726
Self-citationAutomatic predicate abstraction of C programs
Ball, T., Majumdar, R., Millstein, T., & Rajamani, S. K. (2012) · ACM SIGPLAN Notices · doi:10.1145/2442776.2442783 · Cited by 694
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 453
Computer-Aided Verification of Coordinating Processes
Kurshan, R. P. (1995) · Princeton University Press eBooks · doi:10.1515/9781400864041 · Cited by 440
Abstract interpretation of reactive systems
Dams, D. R., Gerth, R., & Grümberg, O. (1997) · ACM Transactions on Programming Languages and Systems · doi:10.1145/244795.244800 · Cited by 434
Automatic verification of finite state concurrent system using temporal logic specifications
Clarke, E. M., Emerson, E. A., & Sistla, A. P. (1983) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/567067.567080 · Cited by 416
Self-citationParametric shape analysis via 3-valued logic
Sagiv, M., Reps, T., & Wilhelm, R. (1999) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/292540.292552 · Cited by 343
Free bits, PCPs and non-approximability-towards tight results
Bellare, M., Goldreich, O., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492573 · Cited by 265
1987 Design Automation Conference
(1987) · IEEE Design & Test of Computers · doi:10.1109/mdt.1987.295161 · Cited by 240
Verification of Infinite State Systems by Compositional Model Checking
McMillan, K. L. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48153-2_17 · Cited by 176
Abstract and Model Check while You Prove
Saïdi, H., & Shankar, N. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48683-6_38 · Cited by 168
Automatic generation of invariants and intermediate assertions
Bjørner, N., Browne, A., & Manna, Z. (1997) · Theoretical Computer Science · doi:10.1016/s0304-3975(96)00191-0 · Cited by 156
Computing abstractions of infinite state systems compositionally and automatically
Bensalem, S., Lakhnech, Y., & Owre, S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028755 · Cited by 130
The 2022 International Conference on Computer-Aided Design (ICCAD)
Mitra, T. (2023) · IEEE Design and Test · doi:10.1109/mdat.2023.3238340 · Cited by 129
Tool-supported program abstraction for finite-state verification
Dwyer, M. B., Hatcliff, J., Joehanes, R., Laubach, S., Păsăreanu, C. S., Zheng, H., & Visser, W. (2001) · doi:10.5555/381473.381493 · Cited by 126
Refining Model Checking by Abstract Interpretation
Cousot, P. M., & Cousot, R. (1999) · Automated Software Engineering · doi:10.1023/a:1008649901864 · Cited by 111
Generating finite-state abstractions of reactive systems using decision procedures
Colón, M. A., & Uribe, T. E. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028753 · Cited by 95
A Performance Study of BDD-Based Model Checking
Yang, B., Bryant, R. E., O’Hallaron, D. R., Biere, A., Coudert, O., Janssen, G., Ranjan, R. K., & Somenzi, F. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49519-3_18 · Cited by 92
Complexity of problems on graphs represented as OBDDs
Feigenbaum, J., Kannan, S., Vardi, M. Y., & Viswanathan, M. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028563 · Cited by 55
Succinctness as a source of complexity in logical formalisms
Gottlob, G., Leone, N., & Veith, H. (1999) · Annals of Pure and Applied Logic · doi:10.1016/s0168-0072(98)00057-8 · Cited by 37
Self-citationSuccinct Representation, Leaf Languages, and Projection Reductions
Veith, H. (1998) · Information and Computation · doi:10.1006/inco.1997.2696 · Cited by 25
Self-citation
Cited by
Biere, A., Cimatti, A., Clarke, E. M., Strichman, O., & Zhu, Y. (2003) · Advances in Computers · doi:10.1016/s0065-2458(03)58003-2 · Cited by 952
Self-citationAlur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656
SAT-Based Model Checking without Unrolling
Bradley, A. R. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-18275-4_7 · Cited by 548
The nuXmv Symbolic Model Checker
Cavada, R., Cimatti, A., Dorigatti, M., Griggio, A., Mariotti, A., Micheli, A., Mover, S., Roveri, M., & Tonetta, S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-08867-9_22 · Cited by 545
Huang, X., Kroening, D., Ruan, W., Sharp, J., Sun, Y., Thamo, E., Wu, M., & Yi, X. (2020) · Computer Science Review · doi:10.1016/j.cosrev.2020.100270 · Cited by 532
Metadata
- Authors
- Clarke, E., Grumberg, O., Jha, S., Lu, Y., & Veith, H.
- Venue
- Journal of the ACM
- Published
- 2003-09
- Volume
- 50
- Issue
- 5
- Pages
- 752-794
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2127574686
- Cited by
- 994
- References
- 36
- FWCI
- 19.67
- 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.