The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Predicate abstraction for software verification
Abstract
Software verification is an important and difficult problem. Many static checking techniques for software require annotations from the programmer in the form of method specifications and loop invariants. This annotation overhead, particularly of loop invariants, is a significant hurdle in the acceptance of static checking. We reduce the annotation burden by inferring loop invariants automatically.Our method is based on predicate abstraction, an abstract interpretation technique in which the abstract domain is constructed from a given set of predicates over program variables. A novel feature of our approach is that it infers universally-quantified loop invariants, which are crucial for verifying programs that manipulate unbounded data such as arrays. We present heuristics for generating appropriate predicates for each loop automatically; the programmer can specify additional predicates as well. We also present an efficient algorithm for computing the abstraction of a set of states in terms of a collection of predicates.Experiments on a 44KLOC program show that our approach can automatically infer the necessary predicates and invariants for all but 31 of the 396 routines that contain loops.
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
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
Dijkstra, E. W. (1976) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,733
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
Counterexample-Guided Abstraction Refinement
Clarke, E., Grumberg, O., Jha, S., Lu, Y., & Veith, H. (2000) · Lecture Notes in Computer Science · doi:10.1007/10722167_15 · Cited by 1,702
Automatic discovery of linear restraints among variables of a program
Cousot, P., & Halbwachs, N. (1978) · Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '78 · doi:10.1145/512760.512770 · Cited by 1,614
Construction 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
The Temporal Logic of Reactive and Concurrent Systems: Specification
Pnueli, A., & Manna, Z. (1991) · Cited by 1,352
Automatic 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
Automatic predicate abstraction of C programs
Ball, T., Majumdar, R., Millstein, T., & Rajamani, S. K. (2001) · Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation · doi:10.1145/378795.378846 · Cited by 442
Leino, K. R. M. (1998) · Programming Concepts and Methods PROCOMET ’98 · doi:10.1007/978-0-387-35358-6_1 · Cited by 393
Avoiding exponential explosion: generating compact verification conditions
Flanagan, C., & Saxe, J. B. (2001) · Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/360204.360220 · Cited by 220
Self-citationAbstract 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
Katz, S. M., & Manna, Z. (1976) · Communications of the ACM · doi:10.1145/360032.360048 · Cited by 137
Powerful techniques for the automatic generation of invariants
Bensalem, S., Lakhnech, Y., & Saïdi, H. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61474-5_80 · Cited by 113
Cited by
Extended static checking for Java
Flanagan, C., Leino, K. R. M., Lillibridge, M., Nelson, G., Saxe, J. B., & Stata, R. (2002) · Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation · doi:10.1145/512529.512558 · Cited by 1,340
Self-citationA survey of symbolic execution techniques
Baldoni, R., Coppa, E., D’elia, D. C., Demetrescu, C., & Finocchi, I. (2019) · ACM Computing Surveys · doi:10.1145/3182657 · Cited by 708
Jhala, R., & Majumdar, R. (2009) · ACM Computing Surveys · doi:10.1145/1592434.1592438 · Cited by 418
Metadata
- Authors
- Flanagan, C., & Qadeer, S.
- Venue
- Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- Publisher
- ACM
- Published
- 2002-01
- Pages
- 191-202
- OpenAlex
- W1972085995
- Cited by
- 284
- References
- 16
- FWCI
- 8.70
- Type
- conference paper
- 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.