Fri 20 Jan 2023 16:45 - 17:10 at Square - Relational & Automated Verification Chair(s): Christoph Matheja

Relational verification encompasses information flow security, regression verification, translation validation for compilers, and more. Effective alignment of the programs and computations to be related facilitates use of simpler relational invariants and relational procedure specs, which in turn enables automation and modular reasoning. Alignment has been explored in terms of trace pairs, deductive rules of relational Hoare logics (RHL), and several forms of product automata. This article shows how a simple extension of Kleene Algebra with Tests (KAT), called BiKAT, subsumes prior formulations, including alignment witnesses for forall-exists properties, which brings to light new RHL-style rules for such properties. Alignments can be discovered algorithmically or devised manually but, in either case, their adequacy with respect to the original programs must be proved; an explicit algebra enables constructive proof by equational reasoning. Furthermore our approach inherits algorithmic benefits from existing KAT-based techniques and tools, which are applicable to a range of semantic models.

Fri 20 Jan

Displayed time zone: Eastern Time (US & Canada) change

16:45 - 18:00
Relational & Automated VerificationPOPL at Square
Chair(s): Christoph Matheja DTU
16:45
25m
Talk
An Algebra of Alignment for Relational Verification
POPL
Timos Antonopoulos Yale University, Eric Koskinen Stevens Institute of Technology, Ton Chanh Le Stevens Institute of Technology, Ramana Nagasamudram Stevens Institute of Technology, David Naumann Stevens Institute of Technology, Minh Ngo Stevens Institute of Technology
DOI
17:10
25m
Talk
Grisette: Symbolic Compilation as a Functional Programming Library
POPL
Sirui Lu University of Washington, Rastislav Bodík Google Research
DOI
17:35
25m
Talk
HFL(Z) Validity Checking for Automated Program Verification
POPL
Naoki Kobayashi University of Tokyo, Kento Tanahashi University of Tokyo, Ryosuke Sato University of Tokyo, Takeshi Tsukada Chiba University
DOI