Certified Compilation based on Gödel Numbers
Guilherme de Oliveira Silva, Fernando Magno Quintão Pereira · 2025
Read Certified Compilation based on Gödel Numbers by Guilherme de Oliveira Silva, Fernando Magno Quintão Pereira (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-2508-12054.txt.
Introduction
Guilherme de Oliveira Silva and Fernando Magno Quintao Pereira tackle a trust problem in software in their two thousand twenty-five paper. A compiler turns source code into a program, but a hacked compiler can hide back doors in what it builds. Worse, it can pass the trick on to the next compiler it builds.
They propose a proof, in the form of a single whole number, that a built program matches its source code. The number can be worked out from both the source and the program by the same short rules. Their test compiler, Charon, handles a small part of the C language. It is strong enough to build a real crypto language called FaCT.
Catalog record
| CREATOR | Guilherme de Oliveira Silva, Fernando Magno Quintão Pereira |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-12054
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Certified Compilation based on Gödel Numbers Guilherme de Oliveira Silva, Fernando Magno Quintão Pereira Abstract . In his 1984 Turing Award lecture, Ken Thompson showed that a compiler could be maliciously altered to insert backdoors into programs it compiles and perpetuate this behavior by modifying any compiler it subsequently builds. Thompson’s hack has been reproduced in real-world systems for demonstration purposes. Several countermeasures have been proposed to defend against Thompson-style backdoors, including the well-known Diverse Double-Compiling (DDC) technique, as well as methods like translation validation and CompCert-style compilation. However, these approaches ultimately circle back to the fundamental question: “ How can we trust the compiler used to compile the tools we rely on? ” In this paper, we introduce a novel approach to generating certificates to guarantee that a binary image faithfully represents the source code. These certificates ensure that the binary contains all and only the statements from the source code, preserves their order, and maintains equivalent def-use dependencies. The certificate is represented as an integer derivable from both the source code and the binary using a concise set of derivation rules, each applied in constant time. To demonstrate the practicality of our method, we present Charon , a compiler designed to handle a subset of C expressive enough to compile FaCT , the Flexible and Constant Time cryptographic programming language. 1. Introduction In his Turing Award lecture, “ Reflections on Trusting Trust” ( Thompson 1984 ) , Ken Thompson introduced an influential concept in cybersecurity: he described an attack in which a compiler is modified to insert a backdoor into the UNIX login command. The brilliance of this attack lies in its ability to self-propagate: the compromised compiler not only injects the backdoor but also recognizes and reinserts it into new compiler versions, even if the malicious code is removed from the source. The concrete implementation of the attach is relatively simple ( Cox 2023 ) , something noticeable, given how hard is to prevent it. Thompson’s work highlights two critical truths: software tools can be compromised in ways that evade traditional inspection, and trust must extend beyond source code to include the entire toolchain. By exposing this hidden vulnerability, Thompson laid the groundwork for understanding and addressing software supply chain attacks ( Cesarano et al. 2024 ; Ladisa et al. 2023 ; Ohm et al. 2020 ; Okafor et al. 2024 ) , a concern that remains relevant today. The Challenge of Building Trust In Thompson’s word, instead of trusting that a program is free of Trojan horses, “ Perhaps it is more important to trust the people who wrote the software ” ( Thompson 1984 ) . Nevertheless, various techniques have been developed to enhance trust in software and mitigate the risks of Thompson-style backdoors. One prominent approach specifically addressing this issue is the Diverse Double-Compiling technique, proposed by David A. Wheeler in his PhD dissertation ( Wheeler 2005 ; Wheeler 2010 ) . As Section 5.1 further explains, this method compares binaries produced by different compilers to identify malicious behavior in a potentially compromised compiler. Going beyond Wheeler’s certification methodology, programming language techniques provide broader mechanisms to build trust in software. Translation validation ( Pnueli et al. 1998 ; Necula 2000 ) verifies that the output of a compiler faithfully preserves the semantics of the input program by validating each individual compilation rather than the entire compiler. Proof-carrying code (PCC) ( Necula 1997 ) allows a program consumer to ensure that code provided by an untrusted producer satisfies specific safety properties without needing to trust the producer. Ultimately, compilers can be fully verified. For instance, CompCert ( Leroy 2009 ) is a compiler whose correctness is formally guaranteed via the Coq proof assistant. Together, these techniques strengthen the foundations of trust in the software ecosystem. And yet, the fundamental issue of “ who we trust ” still plagues them all. The aforementioned techniques – certified compilation (as in CompCert), Proof-Carrying Code (PCC), Translation Validation, and Diverse Double-Compiling (DDC) – each have limitations in addressing the fundamental challenge raised by Thompson’s “Trusting Trust” attack. These limitations arise primarily because demonstrating that a binary faithfully implements the semantics of arbitrary source code requires solving the problem of semantic equivalence, which is undecidable in general due to its relationship to the Halting Problem ( Church 1936 ; Turing 1936 ) . Proof-Carrying Code:: PCC is designed to demonstrate specific safety properties, such as the absence of out-of-bounds memory accesses (e.g., ensuring all array accesses \mathtt{arr[i]} satisfy 0\leq\mathtt{i}<\mathtt{size} ). While effective at verifying certain well-defined properties, PCC does not address the presence of malicious behavior, such as Trojan horses, in the binary. Translation Validation:: The validator verifies the correctness of individual compiler transformations, such as register allocation ( Rideau and Leroy 2010 ) or constant propagation ( Pnueli et al. 1999 ) , rather than the entire compiler. By focusing on specific transformations, translation validation avoids undecidability. However, it is inherently limited to the scope of the program and transformations being validated. If validation fails, it may indicate a limitation in the validation technique rather than an actual error in the compiler. Verified Compilation:: Unlike PCC, a verified compiler such as CompCert does not produce standalone certificates that users can independently verify. Instead, CompCert provides strong semantic correctness guarantees for the programs it compiles, but it does not address the problem of trusting the compiler binary itself. If the binary of the verified compiler is compromised, all guarantees it provides are invalid. Diverse Double-Compiling:: As Section 5.1 explains, DDC relies on the assumption that at least one trusted compiler exists. While this technique reduces the likelihood of an undetected backdoor, it cannot eliminate the possibility entirely. If both compilers used in the DDC process are compromised, then Thompson’s backdoor may still persist. Therefore, each of these techniques represents a step toward building trust in software, but none can completely eliminate the risks highlighted by Thompson’s seminal work. The Contribution of This Work: This paper proposes a technique to certify that a target (low-level) program was produced as the result of translating a source (high-level) program. Said technique is based on the famous encoding Kurt Gödel used in the proof of his incompleteness theorems ( Gödel 1931 ) . As explained in Section 3 , the certificate of faithful compilation is embedded within the structure of the high-level program and in the structure of the low-level program, rather than existing as a separate artifact, as is the case with proof-carrying code. Figure 1 illustrates the proposed methodology. Overview of the proposed certification methodology. Figure 1 . Overview of the proposed certification methodology. Overview of the proposed certification methodology. In Figure 1 , p_{h} is a program written in a high-level source language \mathit{Lang}_{H} , and p_{\ell} is the program written in a low-level target language \mathit{Lang}_{L} , produced by a compiler \mathit{Comp} , i.e., p_{\ell}=\mathit{Comp}(p_{h}) . Figure 1 defines two mapping algorithms, H:\mathit{Lang}_{H}\mapsto\mathbb{N} and L:\mathit{Lang}_{L}\mapsto\mathbb{N} . If \mathit{Cert}_{H}(p_{h})=\mathit{Cert}_{L}(\mathit{Comp}(p_{h})) , then \mathit{Comp} has not modified the compilation contract, meaning that \mathit{Comp} has generated only the instructions necessary to implement in p_{\ell} the semantics of p_{h} . Example 1.1 will clarify these ideas. Example 1.1. Figure 2 shows how we produce a