QED at Large: A Survey of Engineering of Formally Verified Software
By 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
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.
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.
