Open source is not enough

Summary

The video examines why open-source code alone cannot guarantee that software is trustworthy. Even if people inspect a program’s source, the compiler that turns it into a binary could introduce hidden behavior. The discussion connects this supply-chain problem to fundamental limits on what compilers can determine, then describes techniques for improving confidence in software and compilers.

What Compilers Can and Cannot Determine

Compiler stages differ in how much memory and computation they can use:

• Lexers use a fixed number of states and process input character by character. They cannot count arbitrarily many nested parentheses, which is why regular expressions cannot generally recognize that kind of nesting.
• Parsers can use a stack to handle nested structures. Real languages may require more: C, for instance, needs symbol-table information to distinguish declarations from expressions; C++ templates add further complexity; and Perl parsing can depend on code executed earlier.
• Semantic analysis can use arbitrary memory and computation, making it equivalent in power to a general-purpose computer. That power also brings fundamental limits.

The video uses Rice’s theorem to explain why no general method can answer every meaningful question about what an arbitrary program does. Questions such as whether a program will ever print something, divide by zero, or whether a value will ever be read again can be undecidable in general. This helps explain why compilers cannot perform every optimization perfectly: they may be unable to prove that a value is unused or that a function is safe to reuse.

Type Systems as Practical Approximations

A compiler can reliably answer many questions about a program’s text and structure, because it can inspect the syntax tree without running the program. Type systems use such tractable checks as approximations for harder questions about program behavior.

• For example, instead of proving that a function always returns a value—a question about all possible behavior—the compiler might check whether every branch visibly ends in a return.
• That structural check is decidable, but it can reject a function that would in fact always return. A conservative type checker may therefore reject valid programs.
• Alternatively, a system can allow questionable programs through and risk failures or incorrect behavior at runtime. The video presents C’s reliance on programmer assertions such as restrict or GCC’s pure attribute as examples: the compiler trusts the claim, and a false claim can produce wrong code.
• Rust’s borrow checker is presented as an example of a checker that rejects some programs in order to enforce its guarantees.
• Some type systems can themselves become powerful enough to compute arbitrary things. C++ templates can compute at the type level, so questions about them can also become undecidable; compilers impose practical limits, such as stopping after excessive nesting.
• Dynamic languages defer some checks until runtime, when the actual value is available. This avoids certain compile-time questions but gives up static guarantees and can lead to runtime errors.

The speaker also describes types as statements and programs as proofs. A function’s type states what it promises; its implementation demonstrates how to produce a value satisfying that promise; and the type checker checks the proof without running the function. In sufficiently expressive systems that require programs to terminate, this idea becomes the basis of proof assistants such as Lean and Rocq.

The “Trusting Trust” Compiler Backdoor

The central example is Ken Thompson’s 1983 demonstration of how a compiler can conceal a backdoor even when its source code looks clean.

1. A compiler can retain knowledge that is not apparent in its source. The video illustrates this with adding a new C escape sequence. A developer can first use a numeric character code to get the compiler to recognize the sequence, then update the source to use the new sequence and rebuild. The final source no longer records the original numeric workaround, but the compiler binary retains the knowledge.
2. A compiler can be taught to insert a backdoor into a target program. For example, a modified compiler could add a secret password to an OpenSSH server.
3. It can also be taught to reproduce its own modifications. When compiling itself, the compiler inserts both the target-program backdoor and the self-replicating compiler modification into the new binary.
4. The visible modifications can then be removed from the source. The source appears clean, but compilers produced by the infected binary continue to carry the hidden behavior.

The lesson is that rebuilding from readable source is not sufficient if the tool used for the rebuild may already be compromised. The same general concern applies to other tools that process programs, including assemblers and loaders.

Defenses and Ways to Increase Confidence

The video discusses several methods for detecting or reducing this risk:

• Reproducible builds: If a given source reliably produces identical binary bytes, independent parties can rebuild software and compare their result with the official release. This helps expose a compromised build machine, provided someone actually performs the rebuild and comparison. The video says Debian began promoting this effort in 2013 and that almost all of its packages now build identically.
• Independently rebuilding a compiler: David A. Wheeler proposed compiling a compiler’s source using both the compiler itself and a genuinely independent compiler. Each resulting compiler then rebuilds the source. If both results are byte-for-byte identical, that is evidence against a backdoor that only the original compiler inserts. Independence matters: a fork of the same compiler would not provide the same check.
• Testing compilers with generated programs: The video cites Csmith, which generated random C programs and tested them with several compilers. It found more than 300 bugs, including cases where compilers silently produced incorrect code.
• Verified compilers: CompCert is described as a compiler whose components come with proofs that the generated output behaves like the input, with those proofs checked by a proof checker. This can provide strong guarantees about compiler correctness, although CompCert itself still has to be built by other software.

A Real-World Infection and a Bootstrapping Chain

The video distinguishes Thompson’s theoretical attack from a related real incident. In 2009, the Induc virus infected Delphi compiler environments by patching a standard-library source file, recompiling the library, and then deleting the patched source. Programs built in that environment could carry the virus onward. Unlike Thompson’s self-reproducing compiler backdoor, the infection could be removed by reinstalling the library.

The closing example is the bootstrappable builds project, which addresses trust by building up from a tiny, auditable starting point:

1. Begin with hex0, a 357-byte machine-code program written by hand that converts hexadecimal text into bytes.
2. Use it to build a small assembler.
3. Use that assembler to build a tiny C compiler.
4. Use that compiler to build an older GCC.
5. Use the older GCC to build a modern GCC.
6. Use the modern compiler to build the rest of a Linux distribution.

The video says this chain was completed in 2023. Apart from the Linux kernel on which it runs and a helper that drives the build steps, the resulting system can be traced back to source code, with the 357-byte starting program as the bootstrap seed.

Sponsor Segment

The video includes a CodeRabbit sponsorship. The narrator describes using it to review large, AI-generated pull requests in the context of the full codebase. The sponsor’s features highlighted are automated review, one-click fixes, and “change stack,” which organizes files into a walkthrough of how a change was built. The narrator says the trial lasts 14 days and does not require a credit card.

Speakers and Sources Featured

• Narrator: Premature Abstraction, presenting the compiler series and its conclusions.
• Ken Thompson: Cited for the 1983 “Trusting Trust” compiler-backdoor demonstration.
• David A. Wheeler: Cited for a method of checking compilers through independent builds.
• CodeRabbit: Sponsor featured in a product-review segment.
• Other named projects and references: Debian and the reproducible-build effort; Induc; Csmith; CompCert; Lean; Rocq; and the bootstrappable builds project.