License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITP.2021.2
URN: urn:nbn:de:0030-drops-138975
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13897/
Go to the corresponding LIPIcs Volume Portal

Polikarpova, Nadia

Synthesis of Safe Pointer-Manipulating Programs (Invited Talk)

pdf-format:
LIPIcs-ITP-2021-2.pdf (0.3 MB)

Abstract

Low-level pointer-manipulating code is ubiquitous in operating systems, networking stacks, and browsers, which form the backbone of our digital infrastructure. Unfortunately, this code is susceptible to many kinds of bugs, which lead to crashes and security vulnerabilities. A promising approach to eliminating bugs and reducing programmer effort at the same time is to use program synthesis technology to generate provably correct low-level code automatically from high-level specifications.
In this talk I will present a program synthesizer SuSLik, which accepts as input a specification written in separation logic, and produces as output a provably correct C program. SuSLik is the first synthesizer capable of generating a wide range of operations on linked data structures (such as singly- and doubly-linked lists, binary trees, and rose trees) without additional hints from the user. It is also the first synthesizer to automatically discover recursive auxiliary functions required for nested data structure traversal. To make this possible, SuSLik relies on a novel proof system - synthetic separation logic - to derive correct-by-construction programs directly from their specifications. Program proofs generated by SuSLik can be automatically translated into three foundational verification frameworks embedded in Coq: Hoare Type Theory (HTT), Iris, and Verified Software Toolchain (VST).

BibTeX - Entry

@InProceedings{polikarpova:LIPIcs.ITP.2021.2,
  author =	{Polikarpova, Nadia},
  title =	{{Synthesis of Safe Pointer-Manipulating Programs}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13897},
  URN =		{urn:nbn:de:0030-drops-138975},
  doi =		{10.4230/LIPIcs.ITP.2021.2},
  annote =	{Keywords: Program Synthesis, Separation Logic, Proof Search}
}

Keywords: Program Synthesis, Separation Logic, Proof Search
Collection: 12th International Conference on Interactive Theorem Proving (ITP 2021)
Issue Date: 2021
Date of publication: 21.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI