Write a Blog >>
SPLASH 2019
Sun 20 - Fri 25 October 2019 Athens, Greece
Thu 24 Oct 2019 15:07 - 15:30 at Olympia - Specification and Certification Chair(s): Colin Gordon

We develop powerful and general techniques to mechanically verify realistic programs that manipulate heap-represented graphs. These graphs can exhibit well-known organization principles, such as being a directed acyclic graph or a disjoint-forest; alternatively, these graphs can be totally unstructured. The common thread for such structures is that they exhibit deep intrinsic sharing and can be expressed using the language of graph theory. We construct a modular and general setup for reasoning about abstract mathematical graphs and use separation logic to define how such abstract graphs are represented concretely in the heap. We develop a Localize rule that enables modular reasoning about such programs, and show how this rule can support existential quantifiers in postconditions and smoothly handle modified program variables. We demonstrate the generality and power of our techniques by integrating them into the Verified Software Toolchain and certifying the correctness of seven graph-manipulating programs written in CompCert C, including a 400-line generational garbage collector for the CertiCoq project. While doing so, we identify two places where the semantics of C is too weak to define generational garbage collectors of the sort used in the OCaml runtime. Our proofs are entirely machine-checked in Coq.

Thu 24 Oct

Displayed time zone: Beirut change

14:00 - 15:30
Specification and CertificationOOPSLA at Olympia
Chair(s): Colin Gordon Drexel University
14:00
22m
Talk
Relational Verification using Reinforcement Learning
OOPSLA
Jia Chen University of Texas at Austin, Jiayi Wei University of Texas at Austin, Yu Feng University of California, Santa Barbara, Osbert Bastani University of Pennsylvania, Isil Dillig University of Texas Austin
DOI
14:22
22m
Talk
Specification and Inference of Trace Refinement Relations
OOPSLA
Timos Antonopoulos Yale University, Eric Koskinen Stevens Institute of Technology, Ton Chanh Le Stevens Institute of Technology
DOI
14:45
22m
Talk
Specifying Concurrent Programs in Separation Logic: Morphisms and Simulations
OOPSLA
Aleksandar Nanevski IMDEA Software Institute, Anindya Banerjee IMDEA Software Institute, Germán Andrés Delbianco IRIF - Université de Paris, Ignacio Fábregas IMDEA Software Institute
Link to publication DOI
15:07
22m
Talk
Certifying Graph-Manipulating C Programs via Localizations within Data Structures
OOPSLA
Shengyi Wang National University of Singapore, Qinxiang Cao Shanghai Jiao Tong University, Anshuman Mohan National University of Singapore, Aquinas Hobor National University of Singapore
DOI Pre-print