Foundations and Trends® in Programming Languages > Vol 5 > Issue 2-3

QED at Large: A Survey of Engineering of Formally Verified Software

Talia Ringer, University of Washington, USA, tringer@cs.washington.edu Karl Palmskog, University of Texas at Austin, USA, palmskog@acm.org Ilya Sergey, Yale-NUS College and National University of Singapore, Singapore, ilya.sergey@yale-nus.edu.sg Milos Gligoric, University of Texas at Austin, USA, gligoric@utexas.edu Zachary Tatlock, University of Washington, USA, ztatlock@cs.washington.edu
 
Suggested Citation
Talia Ringer, Karl Palmskog, Ilya Sergey, Milos Gligoric and Zachary Tatlock (2019), "QED at Large: A Survey of Engineering of Formally Verified Software", Foundations and TrendsĀ® in Programming Languages: Vol. 5: No. 2-3, pp 102-281. http://dx.doi.org/10.1561/2500000045

Published: 03 Sep 2019
© 2019 T. Ringer, K. Palmskog, I. Sergey, M. Gligoric and Z. Tatlock
 
Subjects
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Proof Engineering by Example
3. Why Proof Engineering Matters
4. Foundations and Trusted Bases
5.Between the Engineer and the Kernel: Languages and Automation
6. Proof Organization and Scalability
7. Practical Proof Development and Evolution
8. Conclusion
Acknowledgements
References

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.

DOI:10.1561/2500000045
ISBN: 978-1-68083-594-6
194 pp. $99.00
Buy book
 
ISBN: 978-1-68083-595-3
194 pp. $280.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Proof Engineering by Example
3. Why Proof Engineering Matters
4. Foundations and Trusted Bases
5.Between the Engineer and the Kernel: Languages and Automation
6. Proof Organization and Scalability
7. Practical Proof Development and Evolution
8. Conclusion
Acknowledgements
References

QED at Large: A Survey of Engineering of Formally Verified Software

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.

QED at LargeQ covers the timeline and research literature concerning proof development for program verification, including theories, languages, and tools. It emphasizes challenges and breakthroughs at each stage in history and highlights challenges that are currently present due to the increasing scale of proof developments.

This monograph is intended for use by researchers and students who are new to the field. It provides the reader with an insightful overview of the work that has led to modern-day techniques for formally verifying software. In times of increasing automation, this underpins many software systems so future trends are also highlighted.

 
PGL-045