Compact Proof Witnesses

M.-C. Jakobs, H. Wehrheim, in: C. Barrett, M. Davies, T. Kahsai (Eds.), NASA Formal Methods: 9th International Symposium, 2017, pp. 389–403.

Download
Restricted 114-chp_3A10.1007_2F978-3-319-57288-8_28.pdf 492.80 KB
Conference Paper
Author
;
Editor
; ;
Abstract
Proof witnesses are proof artifacts showing correctness of programs wrt. safety properties. The recent past has seen a rising interest in witnesses as (a) proofs in a proof-carrying-code context, (b) certificates for the correct functioning of verification tools, or simply (c) exchange formats for (partial) verification results. As witnesses in all theses scenarios need to be stored and processed, witnesses are required to be as small as possible. However, software verification tools – the prime suppliers of witnesses – do not necessarily construct small witnesses. In this paper, we present a formal account of proof witnesses. We introduce the concept of weakenings, reducing the complexity of proof witnesses while preserving the ability of witnessing safety. We develop aweakening technique for a specific class of program analyses, and prove it to be sound. Finally, we experimentally demonstrate our weakening technique to indeed achieve a size reduction of proof witnesses.
Publishing Year
Proceedings Title
NASA Formal Methods: 9th International Symposium
Page
389-403
LibreCat-ID

Cite this

Jakobs M-C, Wehrheim H. Compact Proof Witnesses. In: Barrett C, Davies M, Kahsai T, eds. NASA Formal Methods: 9th International Symposium. Lecture Notes in Computer Science. ; 2017:389-403. doi:10.1007/978-3-319-57288-8_28
Jakobs, M.-C., & Wehrheim, H. (2017). Compact Proof Witnesses. In C. Barrett, M. Davies, & T. Kahsai (Eds.), NASA Formal Methods: 9th International Symposium (pp. 389–403). https://doi.org/10.1007/978-3-319-57288-8_28
@inproceedings{Jakobs_Wehrheim_2017, series={Lecture Notes in Computer Science}, title={Compact Proof Witnesses}, DOI={10.1007/978-3-319-57288-8_28}, booktitle={NASA Formal Methods: 9th International Symposium}, author={Jakobs, Marie-Christine and Wehrheim, Heike}, editor={Barrett, Clark and Davies, Misty and Kahsai, TemesghenEditors}, year={2017}, pages={389–403}, collection={Lecture Notes in Computer Science} }
Jakobs, Marie-Christine, and Heike Wehrheim. “Compact Proof Witnesses.” In NASA Formal Methods: 9th International Symposium, edited by Clark Barrett, Misty Davies, and Temesghen Kahsai, 389–403. Lecture Notes in Computer Science, 2017. https://doi.org/10.1007/978-3-319-57288-8_28.
M.-C. Jakobs and H. Wehrheim, “Compact Proof Witnesses,” in NASA Formal Methods: 9th International Symposium, 2017, pp. 389–403.
Jakobs, Marie-Christine, and Heike Wehrheim. “Compact Proof Witnesses.” NASA Formal Methods: 9th International Symposium, edited by Clark Barrett et al., 2017, pp. 389–403, doi:10.1007/978-3-319-57288-8_28.
Main File(s)
File Name
114-chp_3A10.1007_2F978-3-319-57288-8_28.pdf 492.80 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T13:05:02Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar