Programs from Proofs: A Framework for the Safe Execution of Untrusted Software

M.-C. Jakobs, H. Wehrheim, ACM Transactions on Programming Languages and Systems (2017) 7:1-7:56.

Download
Restricted 69-a7-jakobs.pdf 1.22 MB
Journal Article | English
Author
Jakobs, Marie-Christine; Wehrheim, HeikeLibreCat
Abstract
Today, software is traded worldwide on global markets, with apps being downloaded to smartphones within minutes or seconds. This poses, more than ever, the challenge of ensuring safety of software in the face of (1) unknown or untrusted software providers together with (2) resource-limited software consumers. The concept of Proof-Carrying Code (PCC), years ago suggested by Necula, provides one framework for securing the execution of untrusted code. PCC techniques attach safety proofs, constructed by software producers, to code. Based on the assumption that checking proofs is usually much simpler than constructing proofs, software consumers should thus be able to quickly check the safety of software. However, PCC techniques often suffer from the size of certificates (i.e., the attached proofs), making PCC techniques inefficient in practice.In this article, we introduce a new framework for the safe execution of untrusted code called Programs from Proofs (PfP). The basic assumption underlying the PfP technique is the fact that the structure of programs significantly influences the complexity of checking a specific safety property. Instead of attaching proofs to program code, the PfP technique transforms the program into an efficiently checkable form, thus guaranteeing quick safety checks for software consumers. For this transformation, the technique also uses a producer-side automatic proof of safety. More specifically, safety proving for the software producer proceeds via the construction of an abstract reachability graph (ARG) unfolding the control-flow automaton (CFA) up to the degree necessary for simple checking. To this end, we combine different sorts of software analysis: expensive analyses incrementally determining the degree of unfolding, and cheap analyses responsible for safety checking. Out of the abstract reachability graph we generate the new program. In its CFA structure, it is isomorphic to the graph and hence another, this time consumer-side, cheap analysis can quickly determine its safety.Like PCC, Programs from Proofs is a general framework instantiable with different sorts of (expensive and cheap) analysis. Here, we present the general framework and exemplify it by some concrete examples. We have implemented different instantiations on top of the configurable program analysis tool CPAchecker and report on experiments, in particular on comparisons with PCC techniques.
Publishing Year
Journal Title
ACM Transactions on Programming Languages and Systems
Issue
2
Page
7:1-7:56
LibreCat-ID
69

Cite this

Jakobs M-C, Wehrheim H. Programs from Proofs: A Framework for the Safe Execution of Untrusted Software. ACM Transactions on Programming Languages and Systems. 2017;(2):7:1-7:56. doi:10.1145/3014427
Jakobs, M.-C., & Wehrheim, H. (2017). Programs from Proofs: A Framework for the Safe Execution of Untrusted Software. ACM Transactions on Programming Languages and Systems, (2), 7:1-7:56. https://doi.org/10.1145/3014427
@article{Jakobs_Wehrheim_2017, title={Programs from Proofs: A Framework for the Safe Execution of Untrusted Software}, DOI={10.1145/3014427}, number={2}, journal={ACM Transactions on Programming Languages and Systems}, publisher={ACM}, author={Jakobs, Marie-Christine and Wehrheim, Heike}, year={2017}, pages={7:1-7:56} }
Jakobs, Marie-Christine, and Heike Wehrheim. “Programs from Proofs: A Framework for the Safe Execution of Untrusted Software.” ACM Transactions on Programming Languages and Systems, no. 2 (2017): 7:1-7:56. https://doi.org/10.1145/3014427.
M.-C. Jakobs and H. Wehrheim, “Programs from Proofs: A Framework for the Safe Execution of Untrusted Software,” ACM Transactions on Programming Languages and Systems, no. 2, pp. 7:1-7:56, 2017.
Jakobs, Marie-Christine, and Heike Wehrheim. “Programs from Proofs: A Framework for the Safe Execution of Untrusted Software.” ACM Transactions on Programming Languages and Systems, no. 2, ACM, 2017, pp. 7:1-7:56, doi:10.1145/3014427.
Main File(s)
File Name
69-a7-jakobs.pdf 1.22 MB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T13:15:09Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar