Lesson 0.5 — Bootstrapping, self-hosting and trust¶

Techniques: T-diagrams and bootstrapping, self-hosting and multi-stage builds, the "Trusting Trust" attack, diverse double-compiling · Pebble uses: pebblec is written in C++ and built by clang (no self-hosting); the Rust front end of Ch 24 is a second, diverse implementation of the same front-end contract · Lab: — (drill tdiagram) · Prerequisites: Lesson 0.1, Lesson 0.3 (Definition 0.3.1) · Time: 3–4 hours

Go's compiler is written in Go. To build Go 1.24 from source you need a Go compiler — at least Go 1.22.6, says src/cmd/dist/buildtool.go (const minBootstrap = "go1.22.6"). Which compiler compiled that one? And if the answer is "an older binary", how do you know the binary does what its source says? This lesson answers both questions: the first with an algebra of compilers (T-diagrams), the second with Thompson's attack and Wheeler's defense.

1. Problem and motivation¶

The problem. (1) Given the translators you have (compilers and interpreters, as binaries or as source), determine which new translators you can build on a given machine, and in what order. (2) Given a compiler binary and its alleged source, decide whether the binary was really built from that source — without trusting the binary.

T-diagrams and bootstrapping¶

Bratman introduced a graphical notation for compilers as three-armed "T" shapes (source, target, implementation language) in 1961 [Bra61]; Earley and Sturgis extended it to interpreters and machines ("tombstone diagrams") [ES70]. Composing diagrams answers question (1) mechanically: it is how cross-compilers, ports to new machines and bootstraps of new languages are planned.

Self-hosting and multi-stage builds¶

A compiler is self-hosting when it is written in the language it compiles. Self-hosting is a strong test (the compiler must handle a large real program: itself) and lets language developers work in their own language; the Go, Rust, OCaml, GHC and GCC compilers are self-hosting, and Clang is compiled by Clang. The price is a bootstrap problem: the first binary must come from elsewhere. Multi-stage builds (stage 1 built by an old compiler, stage 2 by stage 1, stage 3 by stage 2, then compare) turn that into a correctness check [GCC-Install, LLVM-AdvBuilds].

Trusting Trust¶

In his Turing Award lecture, Thompson showed that a compiler binary can be made to miscompile specific programs (a login program) and to reinsert that behavior whenever it compiles its own source — so the malicious logic persists after it has been removed from every source file [Tho84]. Inspecting source code, even the compiler's, cannot find it.

Diverse double-compiling¶

Wheeler showed how to detect Thompson's attack: compile the compiler's source twice — once with a different, independently developed ("diverse") trusted compiler, then again with the result — and compare the output bit for bit with the binary under test [Whe05]; his dissertation proves the conditions formally and demonstrates the method on GCC [Whe09].

2. Definitions and algorithms¶

T-diagrams and bootstrapping¶

Definition 0.5.1 (Translators and T-diagrams)

A compiler \(C(S, T, I)\) translates programs in language \(S\) into programs in language \(T\) and is itself a program written in language \(I\) (drawn as a T whose arms are \(S \to T\) and whose foot is \(I\)). An interpreter \(R(S, I)\) runs programs written in \(S\) and is written in \(I\). A machine \(H\) runs programs written in its machine language, also called \(H\). A source text and a binary of "the same" compiler are different translators: \(C(S, T, \mathrm{C})\) and \(C(S, T, \mathrm{x86})\).

Definition 0.5.2 (Correct translator)

\(C(S, T, I)\) is correct if the program it denotes (Definition 0.3.1) is a correct compiler from \(S\) to \(T\) (Definition 0.1.4); \(R(S, I)\) is correct if it denotes an interpreter for \(S\).

Definition 0.5.3 (Executable on a host)

Given a host machine \(H\) and a set \(\mathcal{A}\) of available translators, a language \(L\) is executable on \(H\) if \(L = H\), or \(\mathcal{A}\) contains an interpreter \(R(L, I)\) with \(I\) executable on \(H\) (inductively; the chain must be finite, so cycles of interpreters do not count). A translator can be used only if its implementation language is executable.

Theorem 0.5.4 (The compile rule)

If \(X\) is a translator written in \(L\) (source text of a compiler \(C(S, T, L)\) or of an interpreter \(R(S, L)\)), and \(Y = C(L, M, I)\) is correct and usable (\(I\) executable), then running \(Y\) on \(X\) yields a translator of the same kind with the same source (and target) language, written in \(M\): \(C(S, T, M)\), respectively \(R(S, M)\), and it is correct if \(X\) is.

Proof

Running \(Y\) is possible because \(I\) is executable. \(Y\) is a correct compiler from \(L\) to \(M\), and \(X \in L\), so its output \(X'\) is an \(M\) program with \([\![X']\!] = [\![X]\!]\) (Definition 0.3.1, deterministic case). Two programs with the same denotation translate (or interpret) the same way, so \(X'\) has the same source and target languages as \(X\) and is correct iff \(X\) is. Only the implementation language changed.

Theorem 0.5.5 (The interpreter rule)

If \(R(L, I)\) is correct and \(I\) is executable on \(H\), then every program written in \(L\) can be run on \(H\) (in particular every translator written in \(L\) can be used), with the program's own behavior.

Proof

By induction on the length of the interpreter chain of Definition 0.5.3. Length 0: \(L = H\) runs directly. Otherwise the interpreter \(R(L, I)\) is itself usable (its language \(I\) is executable by a shorter chain, induction hypothesis), and by correctness \([\![R]\!]\,(p, d) = [\![p]\!]_L(d)\) for every \(p \in L\).

Algorithm 0.5.6 (Bootstrap planning by saturation)

Input: a host \(H\); a finite set \(\mathcal{A}_0\) of available translators (binaries and source texts).
Output: every translator obtainable by repeatedly applying Theorem 0.5.4, each with a derivation (the sequence of compile steps that builds it).
Precondition: languages are named consistently (a translator's implementation language matches the source language of the compiler meant to compile it); every given translator is correct.
Postcondition: the output is closed under the compile rule; every output translator is correct (Theorem 0.5.4).
Invariant: every translator in \(\mathcal{A}\) has a derivation from \(\mathcal{A}_0\).

function Saturate(H, A0):
    A ← A0; derivation[t] ← "given" for t in A0
    repeat:
        changed ← false
        for Y in A with Y = C(L, M, I) and Executable(I, H, A):
            for X in A with impl(X) = L:
                X' ← X with impl replaced by M
                if X' ∉ A:
                    A ← A ∪ {X'}; derivation[X'] ← derivation[X] + derivation[Y] + "compile X with Y"
                    changed ← true
    until not changed
    return A, derivation

function Executable(L, H, A):              # Definition 0.5.3, with a visited set against cycles
    return ExecVisit(L, H, A, {})
function ExecVisit(L, H, A, seen):
    if L = H: return true
    if L ∈ seen: return false
    return any(ExecVisit(I, H, A, seen ∪ {L}) for R(L, I) in A)

A cross-compiler is a T-diagram you use every day

Reproduce (clang 23.1.2 on an x86-64 host):

clang-23 --target=aarch64-linux-gnu -O2 -c sum.c -o sum-arm64.o
llvm-readelf -h "$(readlink -f "$(command -v clang-23)")" | grep -E ' Machine:'
llvm-readelf -h sum-arm64.o | grep -E ' Machine:'
llvm-objdump -d --no-show-raw-insn sum-arm64.o | tail -9

Output (complete):

  Machine:                           Advanced Micro Devices X86-64
  Machine:                           AArch64
0000000000000000 <sum>:
       0:       subs    w8, w0, #0x1
       4:       b.lt    0x18 <sum+0x18>
       8:       sub w9, w0, #0x2
       c:       umull   x9, w8, w9
      10:       add x0, x8, x9, lsr #1
      14:       ret
      18:       mov w0, wzr
      1c:       ret

What to notice: with --target=aarch64-linux-gnu, the clang binary acts as \(C(\mathrm{C}, \mathrm{AArch64}, \mathrm{x86})\): an x86-64 program (usable on this host, Definition 0.5.3) whose output is AArch64 code (not usable here). One clang binary is such a T-diagram for each of its 48 targets. The object runs on an ARM machine, not here.

Self-hosting and multi-stage builds¶

Definition 0.5.7 (Stages, deterministic compiler)

Let \(s\) be the source of a compiler for language \(L\) written in \(L\), and \(b_0\) a binary that compiles \(L\) (an older release, or a compiler built from different source). The stages are \(b_{k+1} = [\![b_k]\!]\,(s)\) (the binary produced by compiling \(s\) with \(b_k\)). A compiler binary is deterministic if its output is a function of its input text and options only (no timestamps, random numbers, addresses, hash-table iteration order or environment in the output).

Algorithm 0.5.8 (Three-stage bootstrap with comparison)

Input: the compiler source \(s\); a bootstrap binary \(b_0\).
Output: a compiler binary \(b_3\) (installed), or a failure report.
Precondition: \(b_0\) compiles the subset of \(L\) that \(s\) uses (Go 1.24 requires a Go ≥ 1.22.6 bootstrap compiler); the compiler is deterministic.
Postcondition: on success \(b_2\) and \(b_3\) are bit-identical, which by Theorem 0.5.14 is evidence that \(b_1\) compiled \(s\) faithfully.
Invariant: each \(b_{k+1}\) is built only from \(s\) and \(b_k\).

function Bootstrap(s, b0):
    b1 ← b0(s)                 # stage 1: new source, old compiler (code may differ from b2's)
    b2 ← b1(s)                 # stage 2: new source, new compiler
    b3 ← b2(s)                 # stage 3
    if bytes(b2) ≠ bytes(b3):  # GCC: "comparison test of the stage2 and stage3 compilers"
        return failure("stage 2 and stage 3 differ: miscompilation or nondeterminism")
    run the test suite with b3
    return b3

Go's toolchain1, toolchain2, toolchain3

Reproduce (Go 1.24.7 installation; the comments are in the Go source that ships with it):

G=$(go env GOROOT)
grep -n 'const minBootstrap' $G/src/cmd/dist/buildtool.go
grep -n -E '^\s*//\s+toolchain[123] = mk|^\s*//\s+go_bootstrap = mk' $G/src/cmd/dist/build.go

Output (complete):

124:const minBootstrap = "go1.22.6"
1529:   //  toolchain1 = mk(new toolchain, go1.17 toolchain, go1.17 cmd/go)
1530:   //  go_bootstrap = mk(new cmd/go, toolchain1, cmd/dist)
1537:   //  toolchain2 = mk(new toolchain, toolchain1, go_bootstrap)
1568:   //  toolchain3 = mk(new toolchain, toolchain2, go_bootstrap)

What to notice: Algorithm 0.5.8 in Go's own build script: toolchain1 is the new compiler built by the old one (stage 1), toolchain2 the new compiler built by toolchain1, toolchain3 built by toolchain2. (The comment still says go1.17, the bootstrap version when it was written; minBootstrap is the current requirement.) cmd/dist/build.go explains that toolchain2 "should be semantically equivalent to toolchain1" but faster, and toolchain3 exists so build IDs are right.

Trusting Trust¶

Definition 0.5.9 (Thompson's self-reproducing compiler attack)

Let \(s_C\) be the clean source of a compiler and \(s_P\) the source of a target program (login). A trojaned binary \(b^{\ast}\) behaves like \([\![s_C]\!]\) except on two triggers: (T1) on input \(s_P\) it emits a backdoored program; (T2) on input \(s_C\) it emits a binary behaving like \(b^{\ast}\) (it inserts T1 and T2 into its own output).

Algorithm 0.5.10 (The trojaned compiler, after Thompson)

Input: a source text \(x\).
Output: the binary for \(x\) — faithfully compiled, except on the two triggers.
Precondition: the attacker can recognize \(s_P\) and \(s_C\) (by pattern), and has a quine-like self-description SELF of the trojan code.
Postcondition: \([\![b^{\ast}(s_P)]\!]\) accepts the backdoor password; \(b^{\ast}(s_C)\) is again a trojaned binary (Theorem 0.5.15).
Invariant: the trojan never appears in any source file after the first infection.

function Compile*(x):
    if Matches(x, login pattern):
        x ← x with "accept pw" replaced by "accept pw or pw = BACKDOOR"      # T1
    if Matches(x, compiler pattern):
        x ← x with the definition of Compile replaced by the text SELF       # T2
    return CleanCompile(x)
# SELF is the source of Compile* itself, embedded as data (Thompson's "Stage I":
# a program that prints its own source).

Trigger 1 with a real compiler: the source is clean, the binary is not

Reproduce (clang 23.1.2, POSIX sh and sed; a toy with only trigger T1):

cat > login.c <<'EOF'
#include <stdio.h>
#include <string.h>
int main(int argc, char **argv) {
  const char *pw = argc > 1 ? argv[1] : "";
  puts(strcmp(pw, "secret") == 0 ? "welcome" : "denied");
  return 0;
}
EOF
cat > evilcc <<'EOF'
#!/bin/sh
# A trojaned compiler driver (trigger 1 of Thompson's attack only).
for a in "$@"; do
  case "$a" in
    *login.c)
      sed 's/strcmp(pw, "secret") == 0/(strcmp(pw, "secret") == 0 || strcmp(pw, "letmein") == 0)/' "$a" > /tmp/.x.c
      set -- $(printf '%s\n' "$@" | sed "s|$a|/tmp/.x.c|")
      ;;
  esac
done
exec clang-23 "$@"
EOF
chmod +x evilcc
./evilcc login.c -o login
./login secret; ./login letmein
grep -c letmein login.c
llvm-strings login | grep -E 'secret|letmein'

Output (complete):

welcome
welcome
0
secret
letmein

What to notice: grep finds no letmein in the source, yet the binary accepts it and contains the string. Here the trojan lives in a visible script; Thompson's point is that trigger T2 lets it live in the compiler binary only, surviving recompilation of a clean compiler source (Theorem 0.5.15).

Diverse double-compiling¶

Definition 0.5.11 (DDC setup)

Let \(s_A\) be the source of compiler \(A\), \(c_A\) the binary under test (claimed to be \(A\) built from \(s_A\)), and \(c_T\) a trusted compiler: one we are willing to assume has no trojan triggered by \(s_A\) (for example developed independently — diverse). All compilations use the same options and environment.

Algorithm 0.5.12 (Diverse double-compiling)

Input: \(s_A\), \(c_A\), \(c_T\).
Output: "match" (evidence that \(c_A\) corresponds to \(s_A\)) or "mismatch".
Precondition: \(A\) is deterministic and self-hosting (\(s_A\) is written in \(A\)'s language); \(c_T\) compiles \(s_A\) to a correct program; \(c_A\) was produced by compiling \(s_A\) with some version of \(A\) (a self-regenerated binary).
Postcondition: "match" implies \(c_A\) equals the faithful compilation of \(s_A\) (Theorem 0.5.16).
Invariant: no step executes \(c_A\).

function DDC(s_A, c_A, c_T):
    stage1 ← c_T(s_A)         # A's source, compiled by the trusted compiler: correct but
                              # its CODE differs from c_A (different optimizer)
    stage2 ← stage1(s_A)      # A's source, compiled by a correct build of A: this is what
                              # a faithful A produces from s_A
    return "match" if bytes(stage2) = bytes(c_A) else "mismatch"

DDC on the Tiny C Compiler: two different stage 1s, one stage 2

Reproduce (TCC 0.9.27 source, gcc 13.3.0 and clang 23.1.2 as the two diverse compilers; Ubuntu 24.04 x86-64):

git clone -q --depth 1 --branch release_0_9_27 https://github.com/TinyCC/tinycc.git
cd tinycc && ./configure > /dev/null
gcc -O2 -o tcc-by-gcc tcc.c -ldl -lm -lpthread 2> /dev/null
clang-23 -O1 -o tcc-by-clang tcc.c -ldl -lm -lpthread 2> /dev/null   # add --gcc-install-dir=… if your clang-23 needs it
cmp tcc-by-gcc tcc-by-clang
I="-I. -Iinclude -I/usr/include/x86_64-linux-gnu"
./tcc-by-gcc $I -c tcc.c -o stage2-g.o
./tcc-by-clang $I -c tcc.c -o stage2-c.o
cmp stage2-g.o stage2-c.o && echo IDENTICAL
sha256sum stage2-g.o stage2-c.o | cut -c1-16,65-

Output (complete):

tcc-by-gcc tcc-by-clang differ: char 25, line 1
IDENTICAL
2c4e9984cf9c9823  stage2-g.o
2c4e9984cf9c9823  stage2-c.o

What to notice: the two stage-1 compilers are different binaries (gcc and clang generate different machine code for tcc.c), but both are correct builds of TCC, so both compile tcc.c to the same stage-2 object, bit for bit. That is the fact DDC rests on (Theorem 0.5.16): the stage-2 output depends only on the source \(s_A\), not on which correct compiler built stage 1. Wheeler's 2005 paper used TCC too [Whe05].

3. Worked examples¶

Running example. Bootstrapping a new language, Pebble, on an x86 host, then porting it to ARM, then checking the result.

T-diagrams and bootstrapping¶

Available: \(G_1 = C(\mathrm{C}, \mathrm{x86}, \mathrm{x86})\) (the host's C compiler), \(G_2 = C(\mathrm{Pebble}, \mathrm{x86}, \mathrm{C})\) (a first Pebble compiler written in C), \(G_3 = C(\mathrm{Pebble}, \mathrm{x86}, \mathrm{Pebble})\) (the same compiler rewritten in Pebble), \(G_4 = C(\mathrm{Pebble}, \mathrm{ARM}, \mathrm{Pebble})\) (an ARM back end, in Pebble). Host: x86. Steps, each checked against Theorem 0.5.4:

step	compile	with	\(Y\) usable?	\(X\) in \(Y\)'s source language?	result
s1	\(G_2\) (in C)	\(G_1 = C(\mathrm{C}, \mathrm{x86}, \mathrm{x86})\)	yes	yes	\(C(\mathrm{Pebble}, \mathrm{x86}, \mathrm{x86})\)
s2	\(G_3\) (in Pebble)	\(G_1\)	yes	no (C ≠ Pebble)	invalid
s3	\(G_3\)	s1	yes	yes	\(C(\mathrm{Pebble}, \mathrm{x86}, \mathrm{x86})\) — self-hosted stage 1
s4	\(G_4\)	s3	yes	yes	\(C(\mathrm{Pebble}, \mathrm{ARM}, \mathrm{x86})\) — a cross-compiler
s5	\(G_4\)	s4	yes	yes	\(C(\mathrm{Pebble}, \mathrm{ARM}, \mathrm{ARM})\) — native ARM compiler, built on x86
s6	\(G_3\)	s5	no (ARM not executable on x86)	yes	invalid

Algorithm 0.5.6 saturates the same set: from \(\{G_1, \dots, G_4\}\) it derives exactly the results of s1 (which is the same translator as s3's), s4 and s5 (plus \(C(\mathrm{Pebble}, \mathrm{ARM}, \mathrm{x86})\) applied again to \(G_3\), which gives \(C(\mathrm{Pebble}, \mathrm{x86}, \mathrm{ARM})\) — an x86 compiler that runs on ARM, another product of the same closure).

Try it

./course drill tdiagram --seed 1 --difficulty medium --solution generates a scenario of this shape; --difficulty hard adds an OCaml-style bytecode interpreter chain (Theorem 0.5.5).

Self-hosting and multi-stage builds¶

Algorithm 0.5.8 with \(b_0\) = the C-implemented compiler from s1 above:

stage	built from	by	machine code of the compiler	output on any program \(p\)
\(b_1\)	\(G_3\) (Pebble source)	\(b_0\) (compiled from C)	code generated by \(b_0\)'s back end	what \(G_3\) specifies
\(b_2\)	\(G_3\)	\(b_1\)	code generated by \(G_3\)'s back end (running inside \(b_1\))	what \(G_3\) specifies
\(b_3\)	\(G_3\)	\(b_2\)	code generated by \(G_3\)'s back end (running inside \(b_2\))	what \(G_3\) specifies

\(b_1\) and \(b_2\) compute the same function but are different machine code (the table's third column differs); \(b_2\) and \(b_3\) are produced by the same function from the same input, so if everything is correct and deterministic they are identical (Theorem 0.5.14). A difference between \(b_2\) and \(b_3\) means a bug in \(b_1\)'s compilation of \(G_3\), or nondeterminism.

Trusting Trust¶

Algorithm 0.5.10 over time (the attacker controls the compiler binary once):

event	compiler source	compiler binary	`login` binary
1	\(s_C\) + trojan code	—	—
2	(compile)	\(b^{\ast} = [\![\text{clean } b]\!]\,(s_C + \text{trojan})\)	—
3	trojan deleted: \(s_C\)	\(b^{\ast}\)	—
4	\(s_C\)	\(b^{\ast}(s_C)\) = trojaned again (T2)	—
5	\(s_C\)	trojaned	\(b^{\ast}(s_P)\) = backdoored (T1)

After event 3 every source file is clean; the trojan survives in binaries only.

Diverse double-compiling¶

Algorithm 0.5.12 on the TCC box: \(s_A\) = tcc.c, \(c_T\) = gcc (and, independently, clang). Here the "binary under test" is the other experiment's stage 2:

step	computation	result
1	stage1 ← gcc(`tcc.c`)	`tcc-by-gcc` (282 536 bytes)
1′	stage1′ ← clang(`tcc.c`)	`tcc-by-clang` (338 072 bytes, different)
2	stage2 ← stage1(`tcc.c`)	`stage2-g.o`, SHA-256 prefix `2c4e9984cf9c9823`
2′	stage2′ ← stage1′(`tcc.c`)	`stage2-c.o`, same hash
3	compare	match

A trojan in gcc triggered by tcc.c would have to be matched by an identical trojan in clang for the two stage 2s to agree — the "diversity" in DDC.

4. Invariants and correctness¶

T-diagrams and bootstrapping¶

Proposition 0.5.13 (Saturation terminates and is complete)

Algorithm 0.5.6 terminates, and its result is the least set containing \(\mathcal{A}_0\) and closed under the compile rule (Theorem 0.5.4) with usability judged by Definition 0.5.3.

Proof

Let \(\Lambda\) be the finite set of language names occurring in \(\mathcal{A}_0\). Every derived translator takes its source and target from an existing translator \(X\) and its implementation language from an existing compiler's target, so it lies in the finite set of translators over \(\Lambda\) (\(\lvert \Lambda \rvert^3\) compilers and \(\lvert \Lambda \rvert^2\) interpreters). Each non-final round adds at least one new element, so the loop runs at most that many rounds. On termination no application of the rule adds anything (closure). Every element was added by the rule from earlier elements (the invariant), so every closed superset of \(\mathcal{A}_0\) contains it (leastness). ExecVisit terminates because seen grows along each recursion and is bounded by \(\Lambda\).

Self-hosting and multi-stage builds¶

Theorem 0.5.14 (Stage 2 = stage 3)

If \(s\) is a correct compiler source (its denotation is a correct compiler whose output is deterministic) and \(b_1\) is a correct compilation of \(s\), then \(b_2 = b_3\) bit for bit. Conversely, \(b_2 \ne b_3\) implies that \(b_1\) is not a correct compilation of \(s\), or that compilation is not deterministic.

Proof

Correctness of \(b_1\) means \([\![b_1]\!] = [\![s]\!]\) as functions on source texts (Definition 0.3.1 with the compiler's source as program). Then \(b_2 = [\![b_1]\!]\,(s) = [\![s]\!]\,(s)\). \(b_2\) is the output of the correct compiler \([\![s]\!]\) on \(s\), so \([\![b_2]\!] = [\![s]\!]\) as well, and \(b_3 = [\![b_2]\!]\,(s) = [\![s]\!]\,(s) = b_2\). Determinism is needed to make "\([\![s]\!]\,(s)\)" a single byte string. The converse is the contrapositive. Note what the theorem does not say: \(b_2 = b_3\) does not prove \(s\) correct (a wrong compiler reproduces itself just as well), and it does not rule out a trojan that is present in \(b_0\) and self-reproduces (Theorem 0.5.15).

Trusting Trust¶

Theorem 0.5.15 (The trojan perpetuates itself)

If \(b^{\ast}\) satisfies Definition 0.5.9, then for every \(k \ge 1\) the stage-\(k\) binary \(b_k\) of Definition 0.5.7 with \(b_0 = b^{\ast}\) satisfies Definition 0.5.9 too, although the source \(s_C\) contains no trojan; in particular \(b_k(s_P)\) is backdoored for every \(k\), and \(b_2 = b_3\) can still hold.

Proof

By induction on \(k\). \(b_1 = b^{\ast}(s_C)\) behaves like \(b^{\ast}\) by trigger T2. If \(b_k\) behaves like \(b^{\ast}\), then \(b_{k+1} = b_k(s_C)\) behaves like \(b^{\ast}\) by T2 again. Hence every stage fires T1 on \(s_P\). If \(b^{\ast}\)'s trojan is deterministic, then \(b_2\) and \(b_3\) are both \(b^{\ast}\)-like outputs of \(b^{\ast}\)-like compilers on the same input and can be bit-identical, so the multi-stage comparison of Algorithm 0.5.8 does not detect the attack: Theorem 0.5.14's hypothesis "\(b_1\) is a correct compilation of \(s\)" is exactly what fails, invisibly.

Diverse double-compiling¶

Theorem 0.5.16 (Diverse double-compiling)

Under the precondition of Algorithm 0.5.12, if DDC returns "match", then \(c_A\) is exactly the result of faithfully compiling \(s_A\) with a correct build of \(A\) — so \(c_A\) contains no trojan that is absent from \(s_A\).

Proof sketch (full formal proof, with the assumptions formalized: the formal-proof chapter of [Whe09])

\(c_T\) is trusted, so stage1 \(= c_T(s_A)\) is a correct compilation of \(s_A\): \([\![\mathrm{stage1}]\!] = [\![s_A]\!]\). Then \(\mathrm{stage2} = [\![s_A]\!]\,(s_A)\) — the unique (by determinism) faithful self-compilation of \(s_A\), as in the proof of Theorem 0.5.14. If \(\mathrm{stage2} = c_A\) bit for bit, \(c_A\) is that faithful self-compilation. A trojan in \(c_A\) not described by \(s_A\) would make \(c_A\) differ from it. The assumption that carries the weight is the trust in \(c_T\): DDC reduces "trust \(c_A\)" to "trust \(c_T\) not to contain a trojan aimed at \(s_A\)", which is why \(c_T\) should be diverse (independently developed); using several trusted compilers strengthens it. Wheeler states the exact conditions (same environment, deterministic compilation, what "trusted" must cover — including the linker and libraries) and demonstrates DDC on GCC [Whe09].

5. Complexity¶

Variables: \(\lvert \Lambda \rvert\) = number of distinct languages, \(a\) = number of translators, \(T_c\) = time to compile the compiler once, \(\lvert b \rvert\) = binary size.

Technique	Time (worst)	Time (typical)	Space	Variables
T-diagrams and bootstrapping	saturation: \(O(\lvert\Lambda\rvert^3)\) rounds × \(O(a^2)\) pairs per round	a handful of steps for real bootstraps	\(O(\lvert\Lambda\rvert^3)\) translators	\(\Lambda, a\)
Self-hosting and multi-stage builds	\(3 T_c\) + one comparison \(O(\lvert b \rvert)\)	GCC or Clang: hours for three stages	three compiler trees	\(T_c, \lvert b \rvert\)
Trusting Trust (attack)	trigger matching adds \(O(\text{input})\) per compile	invisible	trojan code in the binary	—
Diverse double-compiling	\(2 T_c\) + comparison \(O(\lvert b \rvert)\) per trusted compiler	as a two-stage build	two builds	\(T_c, \lvert b \rvert\)

Proposition 0.5.17 (Costs of the checks)

Algorithm 0.5.8 performs three compilations of \(s\) and one byte comparison; Algorithm 0.5.12 performs two compilations and one comparison per trusted compiler; both are linear in the size of the compared binaries beyond the compile time.

Proof

By inspection of the pseudo-code: each line compiles once or compares once, and byte comparison reads each byte of both files once.

Pathological inputs. (1) Bootstrapping chains: a language whose only compiler is written in itself and has no binaries left requires a chain through historical versions (Rust's bootstrap chain goes back to the OCaml-written rustboot; the mrustc project re-created a C++ path to break the chain). (2) Nondeterminism: a compiler that embeds __DATE__, absolute paths or hash-table order makes \(b_2 \ne b_3\) and defeats DDC — the reproducible-builds effort exists to remove these (next box). (3) DDC's trusted base: if \(c_T\) and \(c_A\) share a trojaned component (the same linker, the same libc), DDC's diversity is illusory.

Determinism, the precondition of Theorems 0.5.14 and 0.5.16

Reproduce (clang 23.1.2; sleep makes the clock change between compilations):

clang-23 --target=x86_64-linux-gnu -O2 -c sum.c -o a1.o
clang-23 --target=x86_64-linux-gnu -O2 -c sum.c -o a2.o
cmp a1.o a2.o && echo "sum.o: identical"
printf 'const char *stamp = __DATE__ " " __TIME__;\n' > stamp.c
clang-23 --target=x86_64-linux-gnu -c stamp.c -o s1.o; sleep 1.1
clang-23 --target=x86_64-linux-gnu -c stamp.c -o s2.o
cmp -s s1.o s2.o || echo "stamp.o: differs"
SOURCE_DATE_EPOCH=0 clang-23 --target=x86_64-linux-gnu -c stamp.c -o s3.o; sleep 1.1
SOURCE_DATE_EPOCH=0 clang-23 --target=x86_64-linux-gnu -c stamp.c -o s4.o
cmp s3.o s4.o && echo "stamp.o with SOURCE_DATE_EPOCH=0: identical"
llvm-strings s3.o | grep 1970

Output (complete):

sum.o: identical
stamp.o: differs
stamp.o with SOURCE_DATE_EPOCH=0: identical
Jan  1 1970 00:00:00

What to notice: clang is deterministic on ordinary code, but __DATE__/__TIME__ make the program nondeterministic (clang warns with -Wdate-time). Honoring the SOURCE_DATE_EPOCH convention pins the clock and restores bit-identical output, which stage comparison and DDC require.

T-diagrams and bootstrapping¶

Half-bootstrapping / porting — to move a self-hosting compiler to a new machine, write only the new back end in the compiler's language and cross-compile (s4–s5 above); trade-off: needs an existing host.
Bootstrapping through an interpreter — OCaml ships its compiler as portable bytecode (boot/ocamlc) plus a C bytecode interpreter; any machine with a C compiler can start the chain (the drill's hard mode). Trade-off: a binary blob in the repository.

Self-hosting and multi-stage builds¶

Two-stage builds — Clang's CLANG_ENABLE_BOOTSTRAP builds stage 2 with stage 1; a stage 3 identical to stage 2 is optional [LLVM-AdvBuilds]. Trade-off: less assurance, half the time.
Profile-guided multi-stage — the stage-1 compiler is instrumented and used to build a training workload, and stage 2 is built with that profile (the LLVM docs' PGO cache files); trade-off: longer build, faster compiler.

Trusting Trust¶

Hardware and firmware trojans — the same argument one level down: microcode, or an assembler/linker; the trusted base grows.
Supply-chain attacks on build tools — real incidents (the 2015 XcodeGhost trojaned Xcode distribution, the 2009 Induc virus infecting Delphi installations) followed Thompson's pattern at the distribution level.

Diverse double-compiling¶

Bootstrappable builds (GNU Mes, stage0) — rebuild the whole toolchain from a few hundred bytes of auditable machine code, instead of trusting any existing compiler binary; trade-off: long chains of increasingly capable compilers.
Reproducible builds — make every build deterministic (as in the box above) so that independent builders can compare hashes; a prerequisite for DDC and valuable on its own.

7. In real compilers¶

T-diagrams and bootstrapping¶

Clang — every clang binary is a cross-compiler (--target=); the target list is llc --version's (Lesson 0.4). clang/lib/Driver/ToolChains/ chooses tools and libraries per target triple [CLANG-Driver].
OCaml — boot/ocamlc (bytecode) + runtime/ (the C interpreter ocamlrun) is Theorem 0.5.5 in practice.

Self-hosting and multi-stage builds¶

LLVM

llvm/docs/AdvancedBuilds.md (LLVM 23.1.2) — "Bootstrap Builds": CLANG_ENABLE_BOOTSTRAP, ninja stage2, and a stage3 "with a configuration identical to the stage2 build … that should be bit-for-bit identical" [LLVM-AdvBuilds].

GCC gcc/doc/install.texi (gcc-15.1.0): "Perform a 3-stage bootstrap of the compiler" and "Perform a comparison test of the stage2 and stage3 compilers" [GCC-Install].
Go src/cmd/dist/build.go — cmdbootstrap, toolchain½/3 (the box above) [GO-Dist].

Find where LLVM does it. Open llvm/docs/AdvancedBuilds.md at llvmorg-23.1.2. Question: which CMake option turns on a multi-stage clang build? (quiz llvm-where-bootstrap)

Trusting Trust¶

Thompson's original — the paper's three "stages" are the quine, the compiler that learns an escape sequence, and the trojan [Tho84]; no production compiler source contains it, by construction.
Mitigations in toolchains — clang records its identity in every object (.comment section, visible in Lesson 0.6's readelf -S), and -Wdate-time flags nondeterministic macros.

Diverse double-compiling¶

Wheeler's demonstrations — TCC with GCC as the trusted compiler [Whe05]; the dissertation adds a small Lisp compiler, a deliberately trojaned one that DDC catches, and GCC itself, to show the method scales to an industrial compiler [Whe09].
Reproducible Builds / Debian — independent rebuilds compared by hash, the distribution-scale version of Algorithm 0.5.12's comparison.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
T-diagrams and bootstrapping	decides what can be built from what; exact	saturation polynomial in the number of languages · instant by hand	a plan (derivations), or "impossible" with a reason	pencil and paper; `./course drill tdiagram`	planning ports, cross-compilers, new languages
Self-hosting and multi-stage builds	detects miscompilation of the compiler by itself (stage 2 ≠ 3)	\(3 T_c\) · hours for GCC/Clang	a byte-level mismatch, hard to diagnose	build-system support	GCC `make bootstrap`, Clang stage⅔, Go toolchain1–3
Trusting Trust	an attack: undetectable by source inspection or stage comparison	invisible at run time	none — that is the point	modest for a skilled attacker	the threat model for toolchains
Diverse double-compiling	detects Thompson-style trojans, assuming one trusted compiler	\(2 T_c\) per trusted compiler	match / mismatch	needs deterministic builds and a second compiler	auditing compiler binaries; reproducible-builds projects

Use T-diagrams when planning any build that crosses languages or machines. Use multi-stage builds when the compiler is self-hosting: it is the cheapest self-test there is. Assume Thompson's threat when a compiler binary's provenance matters (distributions, security-critical builds). Use DDC (and reproducible builds) when you must show that a distributed compiler binary corresponds to its source.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch00.yaml`)	Drill	Flashcard tag	Exercises
T-diagrams and bootstrapping	`tdiagram-cross`, `tdiagram-interp`	`./course drill tdiagram`	`tdiagram`	—
Self-hosting and multi-stage builds	`stage2-stage3`, `llvm-where-bootstrap`	`./course drill tdiagram --difficulty easy` (stages 1–3)	`self-hosting`	—
Trusting Trust	`trusting-trust-triggers`, `trusting-trust-stages`	— (an attack, not an algorithm to drill; the quiz traces its persistence)	`trusting-trust`	—
Diverse double-compiling	`ddc-conclusion`, `ddc-determinism`	— (the quiz computes one DDC instance)	`ddc`	—

Pitfall

"Stage 2 equals stage 3, so the compiler is correct" is false. Equality shows that the stage-1 binary compiled the source consistently with itself; a wrong compiler (or a self-reproducing trojan) reproduces itself just as well (Theorems 0.5.14 and 0.5.15).

References¶

See the chapter references.

Lesson 0.5 — Bootstrapping, self-hosting and trust¶

1. Problem and motivation¶

T-diagrams and bootstrapping¶

Self-hosting and multi-stage builds¶

Trusting Trust¶

Diverse double-compiling¶

2. Definitions and algorithms¶

T-diagrams and bootstrapping¶

Self-hosting and multi-stage builds¶

Trusting Trust¶

Diverse double-compiling¶

3. Worked examples¶

T-diagrams and bootstrapping¶

Self-hosting and multi-stage builds¶

Trusting Trust¶

Diverse double-compiling¶

4. Invariants and correctness¶

T-diagrams and bootstrapping¶

Self-hosting and multi-stage builds¶

Trusting Trust¶

Diverse double-compiling¶

5. Complexity¶

6. Variants and refinements¶

T-diagrams and bootstrapping¶

Self-hosting and multi-stage builds¶

Trusting Trust¶

Diverse double-compiling¶

7. In real compilers¶

T-diagrams and bootstrapping¶

Self-hosting and multi-stage builds¶

Trusting Trust¶

Diverse double-compiling¶

8. Comparison¶

9. Assessment¶

References¶