MAVERIC: Modular Algebraic Verification of Compilers
MAVERIC is a research project in the Programming, Logic and Semantics group at the IT University of Copenhagen, funded by the Independent Research Fund Denmark from 2027 to 2030. Its aim is to make the formal verification of compilers simpler and more modular, by combining compiler calculation with concurrent separation logic.
We are hiring a PhD student to work on the project. Application deadline: 1 January 2027. See the official job posting for details and how to apply. If you have any questions, or are unsure whether your profile fits, feel free to contact Patrick Bahr at paba@itu.dk before applying.
Motivation
Electronic systems are ubiquitous and control an ever-increasing proportion of our lives, including many critical applications such as banking and healthcare, where failures can have disastrous consequences (e.g. fatal radiation overdoses). Formal verification is a means to avoid such failures by mathematically ensuring that these critical systems work according to their specification. To attain this assurance, all system components must be verified: its hardware and software, as well as the compiler that translates the software into the form that will eventually run on the hardware.
To verify a compiler, one must mathematically prove that it translates any program P written by a programmer into executable code C that behaves equivalently to P. This verification is highly complex and requires many person-years. The goal of this project is to develop a new mathematical theory that significantly simplifies compiler verification to make it more cost-effective to employ more broadly.
Approach
A key technique to reduce complexity is modularity, which allows us to break down complex problems into simpler ones that are easier to solve. Compiler calculation achieves such modularity by using algebraic structures that enable equational reasoning. That is, the program P is proved to be equivalent to the compiled code C in a step-by-step way that is analogous to a simple algebraic proof like 3(4x + 2y) = 12x + 6y = 2(6x + 3y), which shows that the formula 3(4x + 2y) is equal to 2(6x + 3y) in two steps. Compiler calculation has been shown to scale to a wide range of programming language features (see below).
By contrast, current state-of-the-art compiler verification projects like CompCert and CakeML rely on much more complex, non-modular proof techniques. In return, however, these techniques handle more programming language features. In particular, these more complex techniques allow for heap-allocated memory, a feature that is central to most mainstream software. Concurrent separation logic has emerged as the gold standard for modular reasoning about programs with heap-allocated memory, but has never been applied to compiler calculation.
MAVERIC is based on the hypothesis that concurrent separation logic and compiler calculation can be combined into a new mathematical foundation for compiler verification that makes verification more modular and simpler. The objective of the project is to develop the mathematical foundation for compiler calculation in concurrent separation logic, and use it to verify a compiler for a realistic programming language.
Background
Compiler verification
Proof assistants such as Rocq, Agda, and Isabelle/HOL are crucial for dealing with the complexity of formally verifying realistic compilers. The landmark CompCert project was the first such verification effort for a realistic compiler. However, this verification project relied on simulation diagrams, a non-modular reasoning technique that is the source of much of the complexity of the verification. While subsequent compiler verification projects such as CakeML and PureCake introduced more modular reasoning principles based on equational reasoning, they still relied largely on non-modular techniques based on simulation diagrams.
By contrast, compiler calculation is a compiler verification technique that forgoes simulation diagrams entirely. In particular, the direct compiler calculation method relies entirely on equational reasoning principles. This modular approach has been applied to a diverse range of target architectures and language features, but is currently limited to programming languages without heap-allocated memory.
Separation logic and Iris
Separation logic is designed for reasoning about programs with heap-allocated memory. Its key innovation is the separating conjunction that enables highly modular reasoning principles specifically for heap-allocated memory. Concurrent separation logic extends separation logic for reasoning about concurrent programs, which is notoriously difficult as it may involve different parts of a program accessing the same part of memory simultaneously.
Iris is a framework to implement and use concurrent separation logics in the Rocq proof assistant. It is parametric in the programming language being reasoned about, with HeapLang serving as the default language – a concurrent programming language with heap-allocated memory. The Iris framework has been used successfully for a wide range of verification tasks, but it has not yet been applied to compiler calculation. A key insight of this project is that Iris’s reasoning principles – in particular, its support for modular reasoning about heap-allocated data and concurrency – are precisely what is needed to extend compiler calculation to realistic programming languages.
Interaction trees
Interaction trees are an algebraic structure for formalising the semantics of programming languages in proof assistants. They provide a general framework for giving semantics to effectful programming languages while supporting equational reasoning. Interaction trees have been used to give a formal semantics to LLVM, a widely used target language for compilers. This groundwork provides a modular and compositional framework for reasoning about LLVM-based compilers. More recently, interaction trees have been extended to choice trees to enable reasoning about concurrent programming languages, and have been demonstrated to be a suitable foundation for compiler calculation. Several variants of interaction trees have been shown to be effective in Iris verification projects, making them candidates for a robust mathematical foundation for compiler calculation in Iris.
Research plan
The project is organised into five parts: Part 1 lays the foundation by developing an algebraic theory for sequential programming languages with heap allocation, and Part 2 applies this mathematical foundation to a small compiler. Part 3 extends the algebraic theory from Part 1 to handle the combination of heap allocation with concurrency, and Part 4 applies this to a small compiler. Part 5 applies the resulting methodology to a larger case study targeting a realistic concurrent language with heap allocation. The main scientific work is in the form of mechanised mathematical theory and proofs in the proof assistant Rocq.
Part 1: Algebraic theory for sequential computations
We devise a novel algebraic theory of interaction trees that accounts for heap-allocated memory with the help of separation logic. To this end, we will define a suitable separation logic and use it to extend an existing algebraic theory for interaction trees with Hoare-style conditions to enable modular reasoning about heap-allocated memory. That is, instead of equations of the form s ≅ t on interaction trees s and t, we devise an algebraic theory with conditional equations of the form {P} s ≅ t {Q}, where P and Q are separation logic pre- and post-conditions that express modular specifications about heap-allocated memory. We then prove the logical soundness of this algebraic theory in Iris.
Part 2: Verification of a simple sequential language
We use the algebraic theory from Part 1 to verify a compiler for a small sequential fragment of the HeapLang programming language. To this end, we adapt the compiler calculation methodology to account for Hoare-style conditions.
Part 3: Algebraic theory for concurrent computations
We extend the algebraic theory developed in Part 1 to account for concurrency. The key insight is that Iris’s reasoning principles for concurrency – including invariants, ghost state, and resource algebras – can be used to formulate and reason about compilers that correctly handle shared mutable state and thread interaction. Choice trees, which extend interaction trees with non-deterministic choice, provide the semantic foundation for modelling concurrent computations. We will start by considering simple concurrent primitives with fork/join parallelism, which are expressible in choice trees. We then progressively extend to richer concurrency features such as locks and compare-and-swap operations.
Part 4: Verification of a simple concurrent language
We use the algebraic theory from Part 3 to verify a compiler for a small concurrent fragment of the HeapLang programming language. To this end, we will devise a compiler correctness specification that uses Iris invariants to express the relationship between source-level and target-level shared state. A particular challenge is to ensure that the calculation methodology can account for synchronisation code that must be inserted by the compiler to correctly implement the source language’s concurrency model on the target architecture.
Part 5: Case study
We will apply the algebraic theory from Part 3 and the methodology developed in Part 4 to calculate a compiler for a substantial concurrent language with heap allocation, targeting a low-level language formalised using choice trees. A natural candidate for the source language is a variant of the Iris HeapLang, as it is a realistic language that features both concurrency and heap allocation. As a target, we will consider a low-level language modelling LLVM-style intermediate representations, building on existing work on formalising LLVM using interaction trees. This case study serves as a stress test for our algebraic theory and compiler calculation technique. We expect that further refinements to the calculation technique will become necessary and that new compilation strategies for concurrent heap-manipulating languages will be discovered in the process.
People
- Patrick Bahr, IT University of Copenhagen (principal investigator)
- Jesper Bengtson, IT University of Copenhagen (co-investigator)
- Open position, IT University of Copenhagen (PhD student)
- Robbert Krebbers, Radboud University Nijmegen (collaborator)
- Graham Hutton, University of Nottingham (collaborator)