Symptom

A dependency ships a binary. You are diligent, so you read its source. It is clean. You even build it yourself rather than trusting the published artifact, and your build reproduces theirs byte for byte.

You have now verified: the source is clean, and the binary comes from that source. That feels like the end of the question. What else is there?

There is the compiler. You did not read its source. And if you had, you would have compiled it with a compiler you also did not read. There is an infinite regress at the bottom of every audit, and in 1984 Ken Thompson showed the regress is not theoretical: he built the attack, it worked, and no amount of source review at any level can detect it.

Statement

Thompson’s construction (1984). There exists a compiler binary $C’$ with the following properties simultaneously:

  1. Given the source of a target program (Thompson used login), $C’$ emits a binary containing a backdoor that is not present in that source.
  2. Given the clean, unmodified source of the compiler itself, $C’$ emits a compiler binary that again has both of these properties.
  3. The source of $C’$ — the source anyone would inspect — contains no trace of either behaviour, because $C’$ was built once from modified source that was then discarded.

Consequently, auditing the entire source tree of a system, including its compiler, is insufficient to establish that its binaries lack a backdoor.

Note the kind tag. This is a demonstration, not a theorem. It does not prove that no defence exists — one does, and it is at the end of this post. It proves, by construction, that a specific and universally-assumed defence does not work.

Argument

The attack is built in three stages, and the reason Thompson presents it that way is that each stage is separately unalarming.

Stage one: a compiler already knows things not in its source. Consider how a C compiler handles '\n'. Somewhere it contains a comparison against the character and produces the value 10. Now suppose you want to add '\v'. The natural change is:

if (c == 'v') return '\v';   /* fails: '\v' not yet known */

This does not compile, because the compiler you are compiling with does not know '\v' yet. So you write the numeric value instead:

if (c == 'v') return 11;

Build with that. Now the new binary knows '\v', and you can go back and write the self-referential version — return '\v'; — which now compiles fine. The knowledge of what '\v' means has migrated out of the source and into the binary. The source is now circular: it defines '\v' in terms of '\v', and it only works because a previous binary carried the fact forward.

This is a completely ordinary bootstrapping step. Every serious compiler is built this way. It is also the entire attack, in miniature: a property that lives in the binary and is invisible in the source, propagated forward by compilation.

Stage two: a program that prints itself. A quine. Thompson needs one because the payload must reproduce itself into each new compiler generation, and it must do so without reading its own source file from disk. The construction is the familiar one: a data section containing a representation of the code, and code that prints the data twice — once as data, once interpreted as code.

That such a program exists is not a coincidence of C. It is guaranteed for any Turing-complete language by Kleene’s recursion theorem, which says that for any computable transformation $f$ of programs, there is a program $p$ with $\varphi_p = \varphi_{f(p)}$ — a program that behaves as its own transformed self. The recursion theorem is what makes the self-reproducing payload exist in the first place, and Thompson’s construction is that theorem instantiated with hostile intent. The theorem says the fixed point is always there; Thompson walks up and takes it.

Stage three: the two-pattern compiler. Now modify the compiler source to contain two pattern-matchers, and compile it once:

compile(char *s) {
    if (match(s, "login-source-pattern")) {
        emit(backdoor_login);        /* attack 1: bug the target */
        return;
    }
    if (match(s, "compiler-source-pattern")) {
        emit(self_reproducing_payload); /* attack 2: bug the compiler */
        return;
    }
    /* ... ordinary compilation ... */
}

Attack 1 alone is a bug in the compiler, discoverable by anyone who reads the compiler source. Attack 2 is what makes it permanent: when the clean compiler source is compiled, the second matcher fires and re-inserts both matchers, including itself, into the output binary.

Now take the binary produced by this, delete the modified source, and ship. From this moment:

  • The compiler source is clean. Every audit passes.
  • The login source is clean. Every audit passes.
  • Compiling the clean compiler source with the current compiler yields a compiler that still contains the attack.
  • Compiling login with it yields a backdoored login.

The bug is a fixed point of the compilation map. It has no source representation anywhere in the system, and it survives every rebuild, including rebuilds intended to remove it. Thompson’s own summary: “No amount of source-level verification or scrutiny will protect you from using untrusted code.”

The generalisation, which is the part that should worry you. Nothing here is specific to compilers. The construction works for any tool that participates in producing itself or in producing the tools that inspect it:

  • The assembler and linker. Same argument, one level down.
  • The kernel. It loads binaries and can patch on load; it also compiles.
  • The CPU microcode. Below every compiler, and not source at all.
  • The debugger and disassembler. This closes the last obvious escape: if you give up on source and inspect the binary, the tool doing the inspecting can be taught to lie about exactly these bytes. Thompson notes this explicitly.

The regress bottoms out only in silicon, and the silicon was designed with software.

Forbids

Concluding a system is backdoor-free from a source audit. Even an exhaustive one, even including the whole toolchain. The property being audited is not present in the artifact being audited.

Trusting a reproducible build to establish source-to-binary correspondence. Reproducibility proves that the same toolchain on the same source gives the same output. If the toolchain is compromised, every rebuild reproduces the compromise perfectly. Determinism and honesty are different properties, and this is the most valuable single distinction in the post.

Trusting a self-hosted compiler because it compiles its own clean source. That is precisely the operation the attack is designed to survive, and it is the only operation the attack must survive.

Believing that binary inspection settles it. The inspection tools are compiled by the same toolchain.

Does not forbid

It does not make the problem unsolvable, and the belief that it does is the single most common misreading. The lecture is regularly cited as proving trust in software is impossible. It does not. David A. Wheeler’s Diverse Double-Compiling (DDC), from his 2009 dissertation, is a practical defence with a proof of correctness, and it works like this:

Let $S_C$ be the compiler source under test and $C$ its suspect binary. Take any second, independently-produced compiler $C_2$, however slow, ugly, or old.

  1. Compile $S_C$ with $C_2$, giving $A$. (If $C_2$ is compromised, it would have to recognise $S_C$ — which it has likely never seen.)
  2. Compile $S_C$ with $A$, giving $X$.
  3. Compile $S_C$ with $C$, giving $Y$.

If $C$ is honest, $X$ and $Y$ are both the fixed point of compiling $S_C$ and must be bit-identical. If $C$ carries Thompson’s attack, $Y$ contains the payload and $X$ does not, so they differ. Detection requires only that $C$ and $C_2$ are not compromised in the same coordinated way. Wheeler applied it to tcc and to GCC; it works. So the honest statement is not “trust is impossible”, it is “trust cannot be established from source alone, and requires diversity”.

It does not mean auditing source is pointless. Source review catches the overwhelming majority of real vulnerabilities, essentially all accidental ones, and most deliberate ones — the 2024 xz/liblzma backdoor was found in a binary test fixture by someone chasing a 500 ms SSH latency regression, which is source-and-artifact review working. Thompson bounds what review can prove; he does not make it worthless.

It does not make reproducible builds worthless, which people over-correct into. Reproducibility eliminates a large and actually exploited attack class: a compromised build machine substituting a different binary for the one the source implies. It just does not eliminate this one. Debian’s Reproducible Builds project is valuable and Thompson does not diminish it; it addresses a different rung of the same ladder, and DDC composes on top of it.

It does not require the attack to be practical at today’s scale. Thompson’s matcher had to recognise one function in a small C compiler of the era. Doing this to modern GCC or LLVM — millions of lines, aggressive optimisation, source that changes daily — is enormously harder, and a brittle matcher that mis-triggers is a loud failure. The result is a statement about what proofs are available, not a claim that your compiler is bugged.

Boundary

  • Diversity defeats it. DDC needs a genuinely independent second compiler. Two compilers derived from a shared ancestor, or bootstrapped through each other, are not independent.
  • Bootstrapping from a small seed. The bootstrappable builds project builds a full toolchain from a hand-auditable seed binary of a few hundred bytes, closing the regress by making its base small enough to read by hand.
  • Formally verified compilers narrow the target. CompCert has a machine-checked proof that its output preserves source semantics — but the proof is checked by Coq, which was compiled by something. The regress moves; it does not vanish.
  • Hardware is out of scope and stays there. Nothing in software addresses a malicious CPU. Trust must terminate somewhere physical, and the honest position is to name where rather than to pretend it does not.
  • Interpreted and JIT’d languages inherit the problem through the runtime, which is compiled.

The lesson is not paranoia. It is that trust is not a property you can derive from artifacts you hold; it is a property of the process and the people that produced them, and the only technical lever is independence between them.