POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom
Wed 17 Jan 2024 14:20 - 14:40 at Turing Lecture - Automated Verification Chair(s): Gregory Malecha

The formal analysis of cryptographic protocols traditionally focuses on trace and equivalence properties, for which decision procedures in the symbolic (or Dolev-Yao, or DY) model are known. However, many relevant security properties are expressed as DY hyperproperties that involve quantifications over both execution paths and attacker computations (which are constrained by the attacker’s knowledge in the underlying model of computation). DY hyperproperties generalise hyperproperties, for which many decision procedures exist, to the setting of DY models. Unfortunately, the subtle interactions between both forms of quantifications has been an obstacle for lifting decision procedures from hyperproperties to DY hyperproperties.

The central contribution of the paper is the first procedure for deciding DY hyperproperties, in the usual setting where the number of protocol sessions is bounded and where the the equational theory modelling cryptography is subterm-convergent. The main technical innovation of our procedure is the notion of proof stack, which controls the interactions between attacker computations and path quantifications. We prove that our decision procedure can decide the validity of any hyperproperty in which quantifications over messages are guarded and quantifications over attacker computations is limited to expressing attacker’s knowledge. We also establish the complexity of the decision problem for several important fragments of the hyperlogic. We illustrate the techniques and scope of our procedure through examples of smart contracts.

Wed 17 Jan

Displayed time zone: London change

13:20 - 14:40
Automated VerificationPOPL at Turing Lecture
Chair(s): Gregory Malecha BedRock Systems
13:20
20m
Talk
Regular Abstractions for Array Systems
POPL
Chih-Duo Hong National Chengchi University, Anthony Widjaja Lin TU Kaiserslautern; MPI-SWS
13:40
20m
Talk
An Infinite Needle in a Finite Haystack: Finding Infinite Counter-Models in Deductive VerificationDistinguished Paper
POPL
Neta Elad Tel Aviv University, Oded Padon VMware Research, Sharon Shoham Tel Aviv University
Link to publication DOI
14:00
20m
Talk
Mostly Automated Verification of Liveness Properties for Distributed Protocols with Ranking FunctionsRemote
POPL
Jianan Yao Columbia University, Runzhou Tao Columbia University, Ronghui Gu Columbia University, Jason Nieh Columbia University
14:20
20m
Talk
Decision and Complexity of Dolev-Yao Hyperproperties
POPL
Itsaka Rakotonirina MPI-SP, Gilles Barthe MPI-SP; IMDEA Software Institute, Clara Schneidewind MPI-SP