Center for Basic Research in Program Verification

Department of Computer Science, Aarhus University


About

Software systems are an integral part of modern society, and software errors and security breaches pose enormous costs and risks. Center for Basic Research in Program Verification develops fundamental mathematically based models and logics for rigorous mathematical reasoning about correctness and security of software systems.

To read more about the research center go to the official center website.

Publications

Modular Denotational Semantics for Effects with Guarded Interaction Trees
D. Frumin, A. Timany, and L. Birkedal.
In Proceedings of POPL 2024.
.pdf
Asynchronous Probabilistic Couplings in Higher-Order Separation Logic
S.O. Gregersen, A. Aguirre, P.G. Haselwarter, J. Tassarotti, and L. Birkedal.
In Proceedings of POPL 2024.
.pdf
An Axiomatic Basis for Computer Programming on the Relaxed Arm-A Architecture: The AxSL Logic
A. Hammon, Z. Liu, T. Perami, P. Sewell, L. Birkedal, and J. Pichon-Pharabod.
In Proceedings of POPL 2024.
.pdf
The Essence of Generalized Algebraic Data Types
F. Sieczkowski, S. Stepanenko, J. Sterling, and L. Birkedal.
In Proceedings of POPL 2024.
.pdf
Decalf: A Directed, Effectful Cost-Aware Logical Framework
H. Grodin, Y. Niu, J. Sterling, and R. Harper
In Proceedings of POPL 2024.
.pdf
The Logical Essence of Well-Bracketed Control Flow
A. Timany, A. Gueneau, and L. Birkedal.
In Proceedings of POPL 2024.
.pdf
Deadlock-Free Separation Logic: Linearity Yields Progress for Dependent Higher-Order Message Passing
J. Jacobs, J.K. Hinrichsen, and R. Krebbers
In Proceedings of POPL 2024.
.pdf
Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement
A. Timany, S.O. Gregersen, L. Stefanesco, J.K. Hinrichsen, L. Gondelman, A. Nieto, and L. Birkedal.
In Proceedings of POPL 2024.
.pdf
The Last Yard: Foundational End-to-End Verification of High-Speed Cryptography
Philipp G. Haselwarter, Benjamin Salling Hvass, Lasse Letager Hansen, Théo Winterhalter, Cătălin Hriţcu, Bas Spitters.
In CPP 2024: ACM SIGPLAN International Conference on Certified Proofs and Programs.
.pdf
Towards univalent reference types: The impact of univalence on denotational semantics
J. Sterling, D. Gratzer, and L. Birkedal.
In Proceedings of CSL 2024.
.pdf
Melocoton: A Program Logic for Verified Interoperability Between OCaml and C
A. Gueneau, J. Hostert, S. Spies, M. Sammler, L. Birkedal, and D. Dreyer
In Proceedings of OOPSLA 2023.
.pdf
Spirea: A Mechanized Concurrent Separation Logic for Weak Persistent Memory
S. Vindum and L. Birkedal
In Proceedings of OOPSLA 2023.
.pdf
Dependent Session Protocols in Separation Logic from First Principles (Functional Pearl)
J. Jacobs, J.K. Hinrichsen, and R. Krebbers
In Proceedings of ICFP 2023.
.pdf
Verifying Reliable Network Components in a Distributed Separation Logic with Dependent Separation Protocols
L. Gondelman, J.K. Hinrichsen, A. Timany, and L. Birkedal
In Proceedings of ICFP 2023.
.pdf
Cerise: Program Verification on a Capability Machine in the Presence of Untrusted Code
A.L. Georges, A. Gueneau, T. van Strydonck, A. Timany, A. Trieu, D. Devriese, and L. Birkedal
Journal of the ACM.
.pdf
Under Lock and Key: A Proof System for a Multimodal Logic
G. A. Kavvos, D. Gratzer
The Bulletin of Symbolic Logic 2023.
pdf
mitten: A Flexible Multimodal Proof Assistant
P. Stassen, D. Gratzer, and L. Birkedal
In Proceedings of Types 2022 (LIPIcs, Volume 269, TYPES 2022).
.pdf
Modular Verification of State-Based CRDTs in Separation Logic.
A. Nieto, A. Daby-Seesaram, L. Gondelman, A. Timany, and L. Birkedal
In Proceedings of ECOOP 2023.
.pdf
A denotationally-based program logic for higher-order store.
F.L. Aagaard, J. Sterling, and L. Birkedal
In Proceedings of MFPS 2023.
.pdf
What should a generic object be?
J. Sterling
Mathematical Structures in Computer Science.
.pdf
Iris-Wasm: Robust and Modular Verification of WebAssembly Programs
X. Rao, A.L. Georges, M. Legoupil, C. Watt, J. Pichon-Pharabod, P. Gardner, and L. Birkedal
In Proceedings of PLDI 2023.
.pdf
VMSL: A Separation Logic for Mechanised Robust Safety of Virtual Machines Communicating above FF-A.
Zongyuan Liu, Sergei Stepanenko, Jean Pichon-Pharabod, Amin Timany, Aslan Askarov, Lars Birkedal.
In Proceedings of PLDI 2023.
.pdf
Step-Indexed Logical Relations for Nondeterministic and Probabilistic Choice
A. Aguirre and L. Birkedal
In Proceedings of POPL 2023
.pdf
Unifying Cubical and Multimodal Type Theory
Frederik Lerbjerg Aagaard, Magnus Baunsgaard Kristensen, Daniel Gratzer, and Lars Birkedal
In TYPES 2022: International Conference on Types for Proofs and Programs
.pdf
Modular Verification of Op-Based CRDTs in Separation Logic
A. Nieto, L. Gondelman, A. Reynaud, A.Timany, and L. Birkedal
In Proceedings of OOPSLA 2022
.pdf
Purity of an ST monad: full abstraction by semantically typed back-translation
K. Jacobs, D. Devriese, and A. Timany
In Proceedings of OOPSLA 2022
.pdf
Le Temps des Cerises: Efficient Temporal Stack Safety on Capability Machines using Directed Capabilities
A.L. Georges, A. Trieu, and L. Birkedal
In Proceedings of OOPSLA 2022
.pdf
Weakest preconditions in fibrations
Alejandro Aguirre, Shin-ya Katsumata, and Satoshi Kura
Mathematical Constructions in Computer Science 2022
.pdf
Later Credits: Resourceful Reasoning for the Later Modality
S. Spies, L. Gaher, J. Tassarotti, R. Jung, R. Krebbers, L. Birkedal, and D. Dreyer
In Proceedings of ICFP 2022
.pdf
Classifying topoi in synthetic guarded domain theory: the universal property of multi-clock guarded recursion
Daniele Palombi, Jonathan Sterling
In MFPS 2022: Mathematical Foundations of Programming Semantics
.pdf
Characterizing Functions Mappable Over GADTs.
Patricia Johann and Pierre Cagne
In Proceedings of APLAS 2022
.pdf
Symbolic Synthesis of Indifferentiability Attacks
Itsaka Rakotonirina, Miguel Ambrona, Alejandro Aguirre, Gilles Barthe
In Proceedings of ASIA CCS 2022
.pdf
Sheaf semantics of termination-insensitive noninterference
Jonathan Sterling, Robert Harper
In FSCD 2022: Formal Structures for Computation and Deduction
.pdf
A stratified approach to Löb induction
Daniel Gratzer, Lars Birkedal
In FSCD 2022: Formal Structures for Computation and Deduction
.pdf
Normalization for multimodal type theory
Daniel Gratzer
In LICS 2022: Logic in Computer Science
.pdf
A Cubical Language for Bishop Sets
Jonathan Sterling, Carlo Angiuli, Daniel Gratzer
Logical Methods in Computer Science 2022
.pdf
Modalities and Parametric Adjoints
Daniel Gratzer, Evan Cavallo, G.A. Kavvos, Adrien Guatto, Lars Birkedal
Transactions on Computational Logic 2022
.pdf
A Cost-Aware Logical Framework
Y. Niu, J. Sterling, H. Grodin, R. Harper
In POPL 2022: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf
Mechanized Verification of a Fine-Grained Concurrent Queue from Meta’s Folly Library
S. F. Vindum, D. Frumin, L. Birkedal
In CPP 2022: ACM SIGPLAN International Conference on Certified Proofs and Programs
.pdf
Proving Full-System Security Properties under Multiple Attacker Models on Capability Machines.
T. Van Strydonck, A.L. Georges, A. Gueneau, A. Trieu, A. Timany, F. Piessens, L. Birkedal, and D. Devriese.
In CSF 2022: Computer Security Foundations
.pdf
Higher-order probabilistic adversarial computations: categorical semantics and program logics
A. Aguirre, G. Barthe, M. Gaboardi, D. Garg, S. Katsumata, and T. Sato
In ICFP 2021: ACM SIGPLAN International Conference on Functional Programming
.pdf
Theorems for Free from Separation Logic Specifications
L. Birkedal, T. Dinsdale-Young, A. Gueneau, G. Jaber, K. Svendsen and N. Tzevelekos
In ICFP 2021: ACM SIGPLAN International Conference on Functional Programming
.pdf
Client-Server Sessions in Linear Logic
Zesen Qian, G. A. Kavvos and Lars Birkedal
In ICFP 2021: ACM SIGPLAN International Conference on Functional Programming
.pdf
Multimodal Dependent Type Theory
Daniel Gratzer, G. A. Kavvos, Andreas Nuyts, and Lars Birkedal
In LMCS 2021: Logical Methods in Computer Science 17:3
.pdf
Transfinite Iris: Resolving an Existential Dilemma of Step-Indexed Separation Logic
Simon Spies, Lennard Gäher, Daniel Gratzer, Joseph Tassarotti, Robbert Krebbers, Derek Dreyer, Lars Birkedal
In PLDI 2021: ACM SIGPLAN Conference on Programming Language Design and Implementation
.pdf
Toward Complete Stack Safety for Capability Machines
Aïna Linn Georges, Armaël Guéneau, Alix Trieu, Lars Birkedal
In PRISC 2021: Principles of Secure Compilation
[abstract] .pdf
Cap’ ou pas cap’? Preuve de programmes pour une machine a capacites en presence de code inconnu
Aïna L. Georges, Armaël Gueneau, Thomas van Strydonck, Amin Timany, Alix Trieu, Dominique Devriese, Lars Birkedal
In JFLA 2021: Journees Francophones des Langages Applicatifs
.pdf
Reasoning About Monotonicity in Separation Logic
Amin Timany and Lars Birkedal
In CPP 2021: ACM SIGPLAN International Conference on Certified Proofs and Programs
.pdf
Contextual Refinement of the Michael-Scott Queue (Proof Pearl)
Simon F. Vindum and Lars Birkedal
In CPP 2021: Certified Proofs and Programs
.pdf
Distributed Causal Memory: Modular Specification and Verification in Higher-Order Distributed Separation Logic
Léon Gondelman, Simon Oddershede Gregersen, Abel Nieto, Amin Timany, Lars Birkedal
In POPL 2021: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf
Fully Abstract from Static to Gradual
Koen Jacobs, Amin Timany, and Dominique Devriese.
In POPL 2021: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf
Efficient and Provable Local Capability Revocation using Uninitialized Capabilities
Aïna L. Georges, Armaël Gueneau, Thomas van Strydonck, Amin Timany, Alix Trieu, Sander Huyghebaert, Dominique Devriese, Lars Birkedal
In POPL 2021: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf
Mechanized Logical Relations for Termination-Insensitive Noninterference
Simon Oddershede Gregersen, Johan Bay, Amin Timany, Lars Birkedal
In POPL 2021: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf Coq development
StkTokens: Enforcing Well-Bracketed Control Flow and Stack Encapsulation using Linear Capabilities
Lau Skorstengaard, Dominique Devriese, Lars Birkedal
In JFP 2021: Journal of Functional Programming
.pdf
ReLoC Reloaded: A Mechanized Relational Logic for Fine-Grained Concurrency and Logical Atomicity
Dan Frumin, Robbert Krebbers, Lars Birkedal
In LMCS 2021: Logical Methods in Computer Science 17:3
.pdf
Scala Step-by-Step: Soundness for DOT with Step-Indexed Logical Relations in Iris
Paolo G. Giarrusso, Léo Stefanesco, Amin Timany, Lars Birkedal, Robbert Krebbers
In ICFP 2020: ACM SIGPLAN International Conference on Functional Programming
.pdf website
Compositional Non-Interference for Fine-Grained Concurrent Programs
Dan Frumin, Robbert Krebbers, Lars Birkedal
In S&P 2021: Security and Privacy (Oakland)
.pdf Coq development
Multimodal Dependent Type Theory
Daniel Gratzer, G. A. Kavvos, Andreas Nuyts, and Lars Birkedal
In LICS 2020: Logic in Computer Science
.pdf
Dual-Context Calculi for Modal Logic
G. A. Kavvos
In LMCS 2020: Logical Methods in Computer Science
.pdf
Aneris: A Mechanised Logic for Modular Reasoning about Distributed Systems
Morten Krogh-Jespersen, Amin Timany, Marit Edna Ohlenbusch, Simon Oddershede Gregersen, Lars Birkedal
In ESOP 2020: European Symposium on Programming
.pdf technical appendix Coq development
Mechanized Reasoning about a Capability Machine
Aïna Linn Georges, Alix Trieu, Lars Birkedal
In PRISC 2020: Principles of Secure Compilation
[abstract] .pdf
Cubical Syntax for Reflection-Free Extensional Equality
Jonathan Sterling, Carlo Angiuli, Daniel Gratzer
In FSCD 2019: Formal Structures for Computation and Deduction,
.pdf
Implementing a Modal Dependent Type Theory
Daniel Gratzer, Jonathan Sterling, Lars Birkedal
In ICFP 2019: ACM SIGPLAN International Conference on Functional Programming
.pdf
Mechanized Relational Verification of Concurrent Programs with Continuations
Amin Timany and Lars Birkedal
In ICFP 2019: ACM SIGPLAN International Conference on Functional Programming
.pdf
Modal Dependent Type Theory and Dependent Right Adjoints
Lars Birkedal, Ranald Clouston, Bassel Mannaa, Rasmus Møgelberg, Andrew M. Pitts, Bas Spitters
In MSCS 2019: Mathematical Structures in Computer Science
.pdf
Iron: Managing Obligations in Higher-Order Concurrent Separation Logic
Aleš Bizjak, Daniel Gratzer, Robbert Krebbers, Lars Birkedal
In POPL 2019: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf
StkTokens: Enforcing Well-Bracketed Control Flow and Stack Encapsulation using Linear Capabilities
Lau Skorstengaard, Dominique Devriese, Lars Birkedal
In POPL 2019: ACM SIGPLAN Symposium on Principles of Programming Languages
.pdf
Guarded Cubical Type Theory
Lars Birkedal, Aleš Bizjak, Ranald Clouston, Hans B. Grathwohl, Bas Spitters, Andrea Vezzosi
In JAR 2019: Journal of Automated Reasoning
.pdf
Reasoning about a Capability Machine with Local Capabilities: Provably Safe Stack and Return Pointer Management
Lau Skorstengaard, Dominique Devriese, Lars Birkedal
In TOPLAS 2019: ACM Transactions on Programming Languages and Systems
.pdf

Draft papers

A Logical Approach to Type Soundness
Amin Timany, Robbert Krebbers, Derek Dreyer, and Lars Birkedal
Submitted for publication
[preprint] pdf
Controlling unfolding in type theory
D. Gratzer, J. Sterling, C. Angiuli, T. Coquand, L. Birkedal
Submitted for publication
[preprint] pdf
Denotational semantics of general store and polymorphism
J. Sterling, D. Gratzer, L. Birkedal
Submitted for publication
[preprint] pdf
Strict universes for Grothendieck topoi
D. Gratzer, M. Shulman, J. Sterling
Submitted for publication
[preprint] pdf
Syntactic categories for dependent type theory: sketching and adequacy
Daniel Gratzer, Jonathan Sterling
[preprint] pdf