Nanopass Back-Translation of Call-Return Trees for Mechanized Secure Compilation Proofs
Jérémy Thibault, Joseph Lenormand, Cătălin Hriţcu · 2025
Read Nanopass Back-Translation of Call-Return Trees for Mechanized Secure Compilation Proofs by Jérémy Thibault, Joseph Lenormand, Cătălin Hriţcu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19609.txt.
Introduction
Jérémy Thibault, Joseph Lenormand, and Catalin Hritcu simplify, in a 2025 preprint, the hardest step in proving a compiler secure. A secure compiler must guarantee that attacks on the compiled code can be mirrored by attacks on the source. Showing that needs a back-translation: turn any attack on the target back into a source-level attacker. Their method records an attack's interaction as a set of call and return events. Those events form a tree. The tree is then rebuilt, step by step, as a source program that replays the same trace.
Each small step adds one piece of control logic to the rebuilt program. Every middle language gets its own semantics, with ghost state holding the bookkeeping. Correctness follows from several small simulation proofs. The whole construction is mechanized in the Rocq proof assistant. The authors say the nanopass style makes a formerly brutal proof manageable.
Catalog record
| CREATOR | Jérémy Thibault, Joseph Lenormand, Cătălin Hriţcu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-19609
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nanopass Back-Translation of Call-Return Trees for Mechanized Secure Compilation Proofs Jérémy Thibault, Joseph Lenormand, Cătălin Hriţcu Abstract Researchers aim to build secure compilation chains enforcing that if there is no attack a source context can mount against a source program then there is also no attack an adversarial target context can mount against the compiled program. Proving that these compilation chains are secure is, however, challenging, and involves a non-trivial back-translation step: for any attack a target context mounts against the compiled program one has to exhibit a source context mounting the same attack against the source program. We describe a novel back-translation technique, which results in simpler proofs that can be more easily mechanized in a proof assistant. Given a finite set of finite trace prefixes, capturing the interaction recorded during an attack between a target context and the compiled program, we build a call-return tree that we back-translate into a source context producing the same trace prefixes. We use state in the generated source context to record the current location in the call-return tree. The back-translation is done in several small steps, each adding to the tree new information describing how the location should change depending on how the context regains control. To prove this back-translation correct we give semantics to every intermediate call-return tree language, using ghost state to store information and explicitly enforce execution invariants. We prove several small forward simulations, basically seeing the back-translation as a verified nanopass compiler. Thanks to this modular structure, we are able to mechanize this complex back-translation and its correctness proof in the Rocq prover without too much effort. MPI-SP, Bochum, [email protected]://orcid.org/0009-0008-5112-3269 MPI-SP, Bochum, Germany and ENS Paris-Saclay, [email protected] MPI-SP, Bochum, [email protected]://orcid.org/0000-0001-8919-8081 ccs Security and privacy Logic and verification ccs Security and privacy Formal methods and theory of security ccs Software and its engineering Compilers keywords secure compilation; back-translation; machine-checked proofs; Rocq; Coq † † runningauthor: J. Thibault, J. Lenormand, and C. Hriţcu † † copyright: J. Thibault, J. Lenormand, and C. Hriţcu 1 Introduction Good programming languages provide useful abstractions for writing more secure code, such as procedures, types, modules, interfaces, or even something as basic as structured control flow. However, compiling and linking with untrusted low-level code—for instance with a library written in an unsafe language like C/C++ or assembly—doesn’t necessarily preserve the security properties of the source program. Indeed, such linked low-level code—which we call a target context —doesn’t have to respect the same abstractions as source contexts, and, if malicious or compromised, can actively attack the compiled program. Many prototype secure compilation chains [ 3 , 34 , 13 , 5 , 4 , 2 , 33 , 17 , 7 , 30 , 32 , 36 , 38 , 16 , 18 ] aim to protect a compiled program from such attacks. More precisely, they enforce that if there is no attack a source context can mount against a source program, then there can be no attack an adversarial target context can mount against the compiled program. An attack can be represented as one or multiple execution traces, often also recording the interactions between program and context. Such an attack is a witness of the violation of a security property, which can be a trace property (e.g., safety), a hyperproperty [ 12 ] (e.g., noninterference [ 20 ] ), or a relational hyperproperty [ 4 ] (e.g., trace equivalence, obtaining a well-investigated criterion called full abstraction [ 1 , 34 ] ). One may be interested in protecting various such security property classes against attacks, resulting in various formal criteria for secure compilation [ 4 ] . Achieving such secure compilation criteria is, however, challenging; and even more challenging is proving formally that it satisfies any of these criteria. Most proofs rely on a notion of back-translation [ 13 , 30 , 3 , 7 , 17 , 36 , 38 , 16 , 14 ] : given a target context performing an attack on a compiled program, often evidenced by execution traces, one must build a source context performing the same attack against the source program. Such back-translations and their corresponding proofs can be highly non-trivial, especially when the attacks are against hyperproperties and relational hyperproperties. For such classes of security properties, attacks are witnessed by several traces that the generated context must be able to produce, depending on the observable behavior of the program with which it is linked. Moreover, existing secure compilation proofs are often hard to trust, since they can span several hundred pages when carefully spelled out even for toy compilers [ 15 , 32 , 13 ] and often involve complex reasoning techniques, such as cross-language logical relations [ 30 , 13 ] . Because in practice every flaw would be potentially exploitable by the adversarial context, it is indispensable that the trust in secure compilation proofs be very high. So proof assistants are starting to be employed for such proofs [ 3 , 13 , 16 , 18 , 38 ] , yet, the problem of designing general proof techniques that are easier to mechanize in a proof assistant is still open. Recent work in the field showed that proof assistants can help scale up secure compilation proofs to a CompCert-based compilation chain for a compartmentalized variant of C [ 38 ] , by allowing the proofs to be carefully designed and engineered as if they were programs. Yet, even this recent milestone does not address the challenge of proving secure compilation for hyperproperties. Contributions As an important step towards large-scale secure compilation proofs for hyperproperties and relational hyperproperties, we propose a novel and general technique for back-translating a finite set of finite trace prefixes into a single source context, and a convenient way to prove the correctness of this back-translation in a proof assistant. We observe that the set of finite trace prefixes recording the calls and returns between the program and the context can be represented as a call-return tree branching on calls and returns from the program to the context. During the execution, the context produced by our back-translation has to deduce, from the events that have already been executed, which branch it is running (i.e., what subset of programs it could still be linked with), in order to know what event to emit next. To do so, the context produced by our back-translation maintains private state storing its last location in the tree. Every time the context gets control, it uses this information as well as the argument or the return value from the program, to decide what event to produce next, and how to update its own location. This raises two main challenges: (1) the generated context must correctly handle reentrancy , since the program can perform arbitrary callbacks ; and (2) because these callbacks can be arbitrarily nested, returns may occur arbitrarily far from their corresponding call. So the generated context manipulates a complex state that is difficult to reason about. Hence, as the authors have experienced first-hand in previous failed attempts to produce a mechanized proof, a monolithic approach leads to writing a complex back-translation function and to dealing with many invariants at the same time trying to prove this complex