Reflections on Trusting Trust

In 1984, Ken Thompson described a backdoor that hides in a compiler, survives the deletion of its own source code, and can't be found by reading any source code at all. Forty years later, there's still no complete answer to it.

The lecture

Ken Thompson co-created Unix and the B programming language, which led to C. In 1983 he and Dennis Ritchie received the Turing Award, computing's highest honour. Thompson's acceptance lecture was three pages long. It's called Reflections on Trusting Trust, and it's one of the most unsettling papers in computer science.

It ends with this:

That sounds like ordinary advice about reading code before running it. It isn't. Thompson's point is that reading the code doesn't help. To see why, we need two ideas first: programs that reproduce themselves, and compilers that compile themselves.

Programs that print themselves

A quine is a program whose output is its own source code, exactly. It isn't allowed to cheat by opening its own file. It has to contain a description of itself and know how to print that description twice: once as data and once as code.

Thompson's lecture opens with exactly this exercise. It sounds impossible, because any program that contains its own source seems to need to contain itself, forever. The trick is to write the program as a template with a hole in it, then fill the hole with the template.

How it works

Quines are named after the philosopher Willard Van Orman Quine, who studied sentences that refer to themselves. The trick is easier to see in plain English first. Read this instruction and do what it says:

Write this out twice, the second time in quotes: "Write this out twice, the second time in quotes:"

If you follow it, you write the phrase once, then again inside quotes. What you've written is the instruction itself, word for word. The instruction never had to contain itself in full. Half of it is a description (the part in quotes), and the other half is a rule for using that description.

The Python program has the same two halves:

1. Line 1 is the description It stores some text in a variable called s. That text is a template of the whole program, except that where the template itself should appear there's a placeholder, %r.
2. Line 2 is the rule s % s means “take the template s and fill its placeholder with s”. The %r inserts the text in quotes, exactly as you'd type it in code, and %% becomes a single %.
3. The output is the program The filled-in template reads s = '…' followed by print(s % s), which are exactly the two lines you started with.

The important part isn't the printing. It's that the program carries a complete description of itself, as data, which it can use however it likes. Printing it is one option. Copying it into a different program is another, and that's the heart of the attack.

How do you compile a compiler?

A compiler turns source code into a runnable program. The C compiler is itself written in C. So to build a new version of the compiler, you compile its source code using the previous version of the compiler. Every compiler binary on your machine was produced by an older compiler binary, which was produced by an older one still, back to some ancestor written by hand decades ago.

This creates something strange. A compiler can know things that appear nowhere in its source code. Thompson's example was the escape sequence \v, which means “vertical tab”. Here's part of a compiler that reads escape sequences in strings:

c = next();
if (c != '\\') return c;
c = next();
if (c == '\\') return '\\';
if (c == 'n')  return '\n';

Suppose you want to add \v. You can't write return '\v', because the compiler you're using doesn't know what \v means yet. So you write the number instead:

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

You compile this and install the new binary. Now the compiler knows that \v is 11. So you change the source to the readable version:

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

Compile it again and it works. To see why, follow each compiler in turn. Each one is built from the source of the moment, by the compiler before it:

Look closely at gen 3's source. In effect it says “\v means \v”. That's a circular definition, like a dictionary that defines a word using the word itself. It only works because the compiler reading it already knows the answer. Hand that same source to a compiler that has never been taught \v and it fails, exactly as it did in gen 1.

So the number 11 has vanished from the source code, yet every compiler still knows it. That knowledge lives only in the binaries, passed from each compiler to its successor. Thompson called this a “learned” behaviour.

A vertical tab is harmless. Now imagine teaching the compiler something else.

The attack, step by step

Thompson described adding two rules to the compiler's source:

1. When you're compiling the login program, quietly add a backdoor: accept a secret password for any account.
2. When you're compiling a compiler, quietly add both of these rules to it, using the quine trick to copy them in.

As a toy, a “compiler” can be a function that transforms text. In Python it might look like this:

BACKDOOR = '    if password == "trustme": return True\n'

def compile(source):
    if "def check_password" in source:       # compiling login
        source = add_after_first_line(source, BACKDOOR)
    if "def compile(source):" in source:      # compiling a compiler
        source = add_these_rules(source)      # the quine trick
    return translate(source)

How rule 2 copies itself

Rule 1 is an ordinary backdoor. Rule 2 is the clever one, and it's where the quine comes in.

When the infected compiler notices it's compiling a compiler, it has to add the trojan to its output. But where does it get the trojan's code from? Not from the source file, because the whole point is that the source won't contain it. So, like the quine, the trojan carries a description of itself as data: a stored copy of both rules. Rule 2 pastes that stored copy into the compiler it's building.

The pasted copy includes rule 2 itself, along with its stored description. So the new compiler can play the same trick when it builds the next one, and so on. The trojan needs nothing from outside itself. Just like the quine, it's self-contained, and that's what lets it survive.

Why deleting the source doesn't help

Follow the compilers generation by generation, just like the \v example:

The key is the gen 3 row. It's built from clean source, but the thing doing the building is gen 2, and gen 2 is infected. Rebuilding never helps, because every rebuild is done by the previous, infected compiler. From gen 3 onwards the source is spotless and the trojan is still there, forever.

To break the cycle, you'd have to build the compiler using a compiler that doesn't carry the trojan. But you can't tell which ones do by reading their source, and every compiler you own came from somewhere. Hold on to that thought. It's exactly what the defence later in this lesson does.

That's the moment people's stomachs drop. Every line of source is clean. You can audit it, rebuild it, have a hundred experts review it. The backdoor is in none of those places. It lives in a binary that only ever gets replaced by its own offspring.

It gets worse

The natural response is “fine, I'll inspect the compiler binary directly”. But how? You'd use a disassembler or a debugger. Those are programs too, built by a compiler. A compiler that can recognise login can recognise a disassembler, and teach it to hide the trojan. Thompson made exactly this point:

Follow the chain down and it never quite reaches solid ground:

• Your code is built by a compiler, built by an older compiler.
• Both run on an operating system, built by a compiler.
• The OS is loaded by firmware you've never seen the source of.
• The firmware runs on a CPU whose microcode can be updated, and whose circuits were designed by software and made in a factory you'll never visit.

Every layer trusts the layer beneath it. Trust is transitive, and somewhere down the stack it rests on something nobody has examined.

It actually happens

Nobody has publicly found a pure Thompson-style self-reproducing compiler in the wild. But attacks that hide in the build process, rather than the source, are real and getting more common.

Each one is a partial echo of Thompson. The attacker didn't touch the code people review. They touched the machinery that turns code into software.

Fighting back

For 20 years, the standard answer was a shrug. Then in 2005, David A. Wheeler published a practical countermeasure.

Diverse double-compiling

The idea is to get a second opinion from a compiler with a completely different history. If the two lineages don't share an ancestor, an attacker would have had to compromise both in exactly the same way.

1. Pick an independent compiler Choose a different compiler, from different authors, ideally built on a different system. It doesn't need to be perfect, only unconnected to the one you suspect.
2. Compile the suspect compiler's source with it The result is a compiler that behaves like the source says, though its machine code looks different because a different compiler produced it.
3. Use that to compile the same source again Now the source has been compiled by something that behaves exactly like the source describes. If the source is honest, this output should be identical to the compiler you already have.
4. Compare the two binaries bit for bit If they match, your compiler really does correspond to its source. If they differ, something in your compiler isn't in its source code.

Why the comparison works

The method rests on one fact about compilers: what a compiler outputs depends on what it does, not on what its own machine code looks like. Two compilers that behave identically will turn the same source into identical bytes, even if they were built differently. (This needs builds to be deterministic, which we'll come to.)

Call the compiler's source S, the suspect compiler binary A, and the independent compiler T. There are two ways to get a compiler built from S:

What you have:    S ── compiled by A ─────────────────────▶ A

Second opinion:   S ── compiled by T ──▶ X₁
                  S ── compiled by X₁ ────────────────────▶ X₂

Compare A and X₂ byte for byte.

X₁ behaves as S describes, but looks different. T is honest, so X₁ does exactly what the source says. But T arranges machine code in its own way, so X₁'s bytes won't match A's even if A is honest. That's why you can't compare X₁ with A directly.

X₂ is what an honest A would be. X₂ was built from S by X₁, a compiler that does precisely what S says. The second compile washes T's style out of the result. What's left is S, compiled the way S itself says to compile things.

If A is honest, A and X₂ match. A is supposed to be S compiled by a compiler that does what S says. That's exactly how X₂ was made. Same input, same behaviour, same output, byte for byte.

If A is infected, they differ. A was built by an infected compiler, so its rule 2 added the trojan. X₂'s chain never touched the trojan: it isn't in S, and T didn't add it. So X₂ comes out clean and A doesn't. A single byte of difference proves that A contains something S doesn't.

The check can only be fooled if T carries the very same trojan. That's why the second compiler has to be diverse: a different code base, different authors and, ideally, a different history. A copy of your own compiler, or anything built by it, would share the infection and always agree with it.

Go back to the demo above and try it once the source is clean and the binary is infected.

Reproducible builds

DDC only works if compiling the same source twice gives byte-for-byte identical output. Most builds don't, because they stamp in timestamps, file paths or random ordering. The reproducible builds movement fixes this, project by project. Once builds are reproducible, independent volunteers can rebuild published packages and check that the results match. Debian, Arch Linux, NixOS and Guix all do this today. A SolarWinds-style build-server compromise would show up as a mismatch.

Bootstrapping from almost nothing

The most radical answer is to remove the ancestry altogether. Projects such as stage0 and GNU Mes start from a seed program a few hundred bytes long, written in hexadecimal that a person can check by hand. That seed builds a slightly more capable tool, which builds another, step by step, until a full C compiler exists. In 2023, GNU Guix announced it could build its entire system this way. Every link in the chain is small enough to inspect.

Supply-chain frameworks

Industry has turned these lessons into standards. SLSA (supply-chain levels for software artifacts, pronounced “salsa”) defines levels of build integrity, including signed records of exactly what source and build process produced each artifact. A software bill of materials (SBOM) lists every component inside a piece of software, so you know what you're trusting. Since a 2021 US executive order, many government suppliers have to provide one.

Where does your trust end?

There's no right answer to these questions. They're worth asking about any organisation, including your own.

• Who built the compiler that builds your software? Who built that one?
• Do you install software from source, or download binaries? Whose signature makes you trust them?
• Could you rebuild last month's release and get exactly the same bytes?
• If your build server were the attacker, would anyone notice?
• How many of your dependencies are maintained by one person, unpaid, who could be replaced by someone patient?
• Below your code, what's the last layer you've actually verified, and what do you simply assume?

Why this matters

• Source isn't the whole story. What runs is decided by the tools that build it, and those tools can carry behaviour that no source contains.
• Self-reference is the key. The same trick that lets a quine print itself lets a compiler re-infect its own successors.
• Trust is transitive. Every layer relies on the one below, down to hardware nobody fully inspects.
• The defence is diversity and reproducibility. Independent compilers, bit-for-bit reproducible builds and tiny auditable seeds make a hidden trojan much harder to keep hidden.