bits.

Software supply chain · 1984 · Ken Thompson

Reflections on Trusting Trust

Show that source inspection is insufficient when the compiler translating the source can reproduce hidden behavior into future binaries.

How to read the original

  1. Read Stage I for the relationship between a program and its reproduced text.
  2. Read Stage II for the compiler-bootstrap example.
  3. Read Stage III and separate source inspection, compiler provenance, and binary behavior.

The translator is inside the trust boundary

Thompson’s lecture demonstrates that clean-looking source does not by itself establish what a compiler binary produces. A bootstrapped translator can preserve behavior that no longer appears in the source supplied to a later build. The important object of review is therefore a chain from source through tools to artifacts. This commentary uses a harmless watermark model to reason about that chain without constructing an authentication bypass.

Original reconstruction: a ledger of build provenance

Let S be the reviewed source of a toy translator, and let B be the translator binary used to compile it. Write Build(B,S) for the resulting binary. Suppose ordinary source S contains a rule translating a toy expression into an output string. A separate application source P should translate to the string “result=7”.

Begin with a reference translator B0 that behaves as reviewed. Building P with B0 produces the expected artifact A0. Now consider an experimental translator B1 whose behavior additionally appends the harmless metadata field watermark=lab to application artifacts. That difference is immediately visible when compiling P, even if P contains no watermark instruction. The output depends on B1 as well as P.

For the thought experiment, assume B1 also preserves this watermark-producing behavior when asked to compile translator source S. Then B2=Build(B1,S) behaves like B1 on P, and B3=Build(B2,S) does too. Every supplied copy of S can be byte-for-byte identical to the reviewed version. Rebuilding repeatedly establishes continuity within this lineage, not independence from it.

Create a table with columns source hash, builder hash, configuration, output hash, and observed behavior. Rows for B1, B2, and B3 make the hidden dependency explicit. A reviewer who records only the source hash misses the variable carrying the altered behavior. Conversely, a difference in output hashes is not automatically evidence of malicious modification: timestamps, paths, optimization choices, or nondeterministic ordering can also change bytes.

Distinguish three useful claims

Source review asks whether the examined text contains specified unwanted behavior. Reproducibility asks whether controlled inputs and a specified process produce the same artifact. Neither question alone proves that the builder faithfully implements the intended source language. A reproducibly wrong translator can produce the same wrong output on every machine.

Independent construction adds a different form of evidence. If a separately trusted translator processes the same source under compatible language semantics, comparison can challenge dependence on one builder lineage. Care is required: simply compiling a large application with two unrelated optimizing compilers and comparing binary bytes is usually meaningless because both can be correct while generating different code. A rigorous diverse-compilation argument must define the stages, deterministic conditions, and assumptions connecting the compared artifacts.

Turn distrust into a bounded investigation

For an educational test, use toy strings and visible metadata, then verify that the watermark disappears when the experimental translator is replaced by the independent reference. Keep the application meaning unchanged. This isolates the question of inherited translator behavior from questions about operating-system compromise, hardware correctness, or malicious input files.

The broader audit should identify who produced each compiler, linker, generator, and build image; how those artifacts are authenticated; which inputs are mutable; and what independent checks exist. A signed artifact proves a statement by a key holder under a verification policy, not semantic correctness of every instruction. The paper’s value is not a demand for impossible absolute certainty. It is a method for locating a trust assumption that source-level reasoning can otherwise leave invisible.

Reconstruction exercise

A team rebuilds the same reviewed translator source three times using each resulting binary for the next build. All three output hashes match. State two claims this supports and two claims it does not establish. Design a harmless experiment that would distinguish dependence on the initial builder from a watermark explicitly present in the reviewed application source.

Worked solution

Matching outputs support repeatability for the observed build chain and show that the tested inputs did not cause visible byte changes across those three stages. They do not establish that the initial builder implemented the intended semantics, nor that the resulting artifact lacks unwanted behavior. A stable transformation can reproduce an error or injected metadata indefinitely. For the experiment, keep application source P and reviewed translator source S fixed, record their hashes, and compile P with both the experimental builder and an independently obtained reference builder for the same toy language. If only the experimental lineage adds a visible watermark, the difference depends on the build path rather than an explicit watermark in P. Then inspect the toy semantics and outputs to rule out ordinary configuration differences. This is a bounded test of one behavior, not proof that either complete toolchain is trustworthy in every respect.

Test the limits and transfer the idea

1. Compiler construction trace · allow 40 minutes

Bootstrap a new escape without circular reasoning

Stage II explains how a compiler can learn a new escape convention through bootstrapping. Use an original toy language with character constants. Compiler C0 understands decimal character codes and the escapes backslash-n and backslash-backslash, but rejects backslash-v. Source S0 implements exactly that behavior. You want a new compiler to translate backslash-v to character code 11.

Define an intermediate source S1 using only constructs C0 already understands, then a cleaner source S2 that uses the new escape in its own implementation. Trace the compilers produced by building S1 and S2 in the correct order. Explain why building S2 first fails and what a successful bootstrap proves. Keep this a benign language-extension exercise, not a hidden alteration.

Get a starting hint

The semantic rule can initially be expressed as the old language's numeric value 11.

Compare your reasoning with the worked solution

S1 adds a parser branch recognizing the two-character spelling backslash-v and returning the numeric character code 11. Its implementation uses decimal 11, so C0 can compile the source without already understanding the new character constant. Let C1=Build(C0,S1). C1's execution now recognizes backslash-v because that behavior was explicitly encoded using the older language's constructs.

S2 expresses the same branch using a backslash-v character constant instead of the decimal value. C1 can translate that constant to 11, so C2=Build(C1,S2) implements the same extension. Compiling S2 directly with C0 fails at its unsupported escape; the ability of the resulting intended program to recognize a spelling does not grant the old compiler that ability while parsing the source. The stages resolve this apparent circularity.

Test both builders on literal v, backslash-n, backslash-backslash, backslash-v, and an invalid escape, checking both returned codes and rejection behavior. Record S1,S2,C0,C1,C2 and configuration so the semantic transition is reviewable. A successful bootstrap shows that this extension can be carried from an older implementation to a self-hosting one under the stated language rules. It does not prove that the initial builder was faithful on every input, or that no unrelated behavior was carried forward. Thompson uses bootstrapping to expose that broader trust dependency. Here the extension remains explicit and its observed behavior is narrowly tested.

Check your reasoning

  • Provides a C0-compatible intermediate source and the correct two-stage order.
  • Explains the distinction between compiler parsing and generated-program behavior.
  • Defines boundary tests and limits the trust conclusion.

2. Execution and reasoning · allow 35 minutes

Trace a harmless self-reproducing program

Stage I asks the reader to confront programs that reproduce their own text. Run this original Python 3 example in a clean terminal. The program reads no file and opens no network connection.

s = 's = %r\nprint(s %% s)'
print(s % s)

Explain the role of the two formatting placeholders, show the exact two-line output, and compare it with the source including the final newline. Then change the final statement to print(s) and explain why it ceases to reproduce the program. Finally identify why a quine is possible without a magical instruction that reads its own source, and why self-reproduction by itself proves nothing about whether a compiler is malicious.

Get a starting hint

At runtime s contains a template. The repr conversion quotes that template as a valid string literal, while the escaped percent preserves the next program's formatting operation.

Compare your reasoning with the worked solution

The string contains a %r placeholder, a newline, and a doubled percent in the second statement. Applying s % s substitutes repr(s) for %r, which inserts a quoted representation with the embedded newline escaped. The doubled %% becomes a literal percent in the generated program. The output is exactly:

s = 's = %r\nprint(s %% s)'
print(s % s)

The print call adds the final newline, matching the supplied source when it ends with a newline. If the final statement becomes print(s), the output is just the unexpanded template: its first line still contains %r and its second line still contains %%. The data needed for reproduction remains present, but the operation that embeds that data into its own template has been removed.

The program stores a representation of a template and uses ordinary string operations to connect data with executable syntax. It does not need to inspect the running file. Changing whitespace or quote style in the source can break byte-for-byte agreement unless the template changes accordingly; the claim is about this exact source. Self-reproduction is a neutral computational construction. The security issue in Thompson's later stages involves what transformations a trusted builder preserves and whether the reviewed source explains its output. A harmless quine establishes neither compromise nor the absence of compromise.

Check your reasoning

  • Explains %r and %% and reproduces the exact output including the newline.
  • Shows why removing the substitution breaks self-reproduction.
  • Separates ordinary representation from compiler provenance and malicious intent.

Check your understanding

Repeated clean-source rebuilds all preserve a watermark absent from the source. What remains a possible cause?

  • A transformation retained in the builder lineage.
  • A proof that the inspected source explicitly requests the watermark.
  • A guarantee that every rebuild used an independent implementation.
  • Evidence that matching hashes establish source-to-binary correspondence.
Explanation

The builder is an input to the build, and its behavior can persist across self-compilation.

Why is comparing arbitrary binaries from two optimizing compilers insufficient by itself?

  • Equivalent source semantics require byte-identical compiler output.
  • A cryptographic digest automatically ignores benign optimization differences.
  • Different outputs prove at least one compiler is malicious.
  • Different correct implementations can emit different machine code.
Explanation

The comparison needs a defined construction and semantic assumptions; raw byte differences can be benign.

Original paper and sources

Ken Thompson. Reflections on Trusting Trust. Communications of the ACM, 1984.

Read the original paper →

Read the primary paper: University of Waterloo, ACM classic mirror