QED at Large: A Survey of Engineering of Formally Verified Software
Open accessThe DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Abstract
Development of formal proofs of correctness of programs can increase actual and perceived reliability and facilitate better understanding of program specifications and their underlying assumptions. Tools supporting such development have been available for over 40 years, but have only recently seen wide practical use. Projects based on construction of machine-checked formal proofs are now reaching an unprecedented scale, comparable to large software projects, which leads to new challenges in proof development and maintenance. Despite its increasing importance, the field of proof engineering is seldom considered in its own right; related theories, techniques, and tools span many fields and venues. This survey of the literature presents a holistic understanding of proof engineering for program correctness, covering impact in practice, foundations, proof automation, proof organization, and practical proof development.
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
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (1931) · Monatshefte für Mathematik und Physik · doi:10.1007/bf01700692 · Cited by 2,395 · cited 1×
“However, he then subsequently established that even modest extensions of expressibility in first-order logic lead to incompleteness (Gödel, 1931): there can be no system that allows constructing proofs for all true propositions.”
BackgroundKlein, G., Elphinstone, K., Heiser, G., Andronick, J., Cock, D., Derrin, P., Elkaduwe, D., Engelhardt, K., Kolanski, R., Norrish, M., et al. (2009) · Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles · doi:10.1145/1629575.1629596 · Cited by 1,633
First draft of a report on the EDVAC
von Neumann, J. (1993) · IEEE Annals of the History of Computing · doi:10.1109/85.238389 · Cited by 1,112 · cited 1×
“At roughly the same time, a theoretical basis for computation and computer programs was given by Church (1936) in the λ-calculus, and computers were developed more practically by von Neumann and others in the 1940s (von Neumann, 1993).”
BackgroundDafny: An Automatic Program Verifier for Functional Correctness
Leino, K. R. M. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17511-4_20 · Cited by 940 · cited 2×
“…Team, 1996-2019), and Agda (Agda Development Team, 2007-2019); we do not consider program verifiers, theorem provers, and constraint solvers such as Dafny (Leino, 2010), ACL2 (ACL2 Development Team, 1990-2019), and Z3 (Z3 Development Team, 2008-2019) except when contributions carry over.”
BackgroundFinding and understanding bugs in C compilers
Yang, X., Chen, Y., Eide, E., & Regehr, J. (2011) · Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1993498.1993532 · Cited by 825 · cited 2×
“For example, the formally verified optimizing C compiler CompCert (Leroy, 2006) is empirically more reliable than GCC and LLVM: the test generation tool Csmith (Yang et al., 2011) found 79 bugs in GCC and 202 bugs in LLVM, but was unable to find any bugs in the verified parts of CompCert.”
Method(1994) · Lecture Notes in Computer Science · doi:10.1007/bfb0030541 · Cited by 612
An analysis of patch plausibility and correctness for generate-and-validate patch generation systems
Qi, Z., Long, F., Achour, S., & Rinard, M. (2015) · Proceedings of the 2015 International Symposium on Software Testing and Analysis · doi:10.1145/2771783.2771791 · Cited by 420
Using Crash Hoare logic for certifying the FSCQ file system
Chen, H., Ziegler, D., Chajed, T., Chlipala, A., Kaashoek, M. F., & Zeldovich, N. (2015) · Proceedings of the 25th Symposium on Operating Systems Principles · doi:10.1145/2815400.2815402 · Cited by 211 · cited 2×
“Verification has also reached file systems, such as FSCQ (Chen et al., 2015), a file system with guarantees about crash safety that have been verified in Coq, and DFSCQ (Chen et al., 2017), an efficient crashsafe file system with several verified optimizations.”
BackgroundMethodHistory of Interactive Theorem Proving
Harrison, J., Urban, J., & Wiedijk, F. (2014) · Handbook of the History of Logic · doi:10.1016/b978-0-444-51624-4.50004-6 · Cited by 107
Cited by
SoK: Computer-Aided Cryptography
Barbosa, M., Barthe, G., Bhargavan, K., Blanchet, B., Cremers, C., Liao, K., & Parno, B. (2021) · 2021 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40001.2021.00008 · Cited by 143
“To this end, we hope to see more interplay between proof engineering research [184], [185] and computer-aided cryptography research in the coming years.”
BackgroundTowards AI-Assisted Synthesis of Verified Dafny Methods
Misu, M. R. H., Lopes, C. V., Ma, I., & Noble, J. (2024) · Proceedings of the ACM on Software Engineering · doi:10.1145/3643763 · Cited by 38
“We manually analyzed the error logs for all unverified methods and identified two major types of errors.”
Maintaining a Library of Formal Mathematics
van Doorn, F., Ebner, G., & Lewis, R. Y. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-53518-6_16 · Cited by 29
Metadata
- Authors
- Ringer, T., Palmskog, K., Sergey, I., Milos, G., & Tatlock, Z.
- Venue
- Foundations and Trends in Programming Languages
- Publisher
- Emerald
- Published
- 2019-09-03
- Volume
- 5
- Issue
- 2-3
- Pages
- 102-281
- ISSN
- 2325-1107 (ISSN-L)
- 2325-1131
- OpenAlex
- W3104549103
- Cited by
- 49
- References
- 9
- FWCI
- 2.19
- Type
- journal article
- Language
- en
- Open access
- diamond
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.