Sunday, February 05, 2012


Bootstrapping and Reflections on Trusting Trust

The term "Bootstrapping" comes from the term "pulling yourself up by your own bootstraps" (Wikipedia). In computing parlance, a bootstrap loader is the code that initially runs when a machine starts, whose job is to load the rest of the operating system. [I can remember (just) old mainframes where the bootstrap code was entered by hand using switches on the front panel!]

If you’ve never read Ken Thompson’s “Reflections on Trusting Trust” (his Turing Award acceptance speech), it’s definitely worth reading:

It describes a very clever backdoor mechanism based on the fact that people only review source (human-written) code, and not compiled machine code. A program called a compiler is used to create the second from the first, and the compiler is usually trusted to do an honest job.

Thompson's paper describes a modified version of the Unix C compiler that would:

  • Put an invisible backdoor in the Unix login command when it noticed that the login program was being compiled, and as a twist
  • Also add this feature undetectably to future compiler versions upon their compilation as well.

How did I get onto this topic? Someone asked the question “How can you write a compiler in it's own language?”

If you were writing a new C++ compiler, you would just write it in C++ and compile it with an existing C++ compiler. If you were creating a compiler for a completely new language, you would need to write the new compiler in another language first. Usually this would be another programming language, but it can be assembly, or even machine code.

If you want to bootstrap a compiler, you would generally write a compiler for a small subset of the language. Then in this minimal version of the language, you would write a compiler for the full language. This often occurs iteratively rather than in a single pass.

The first self-hosting compiler (excluding assemblers) was written for Lisp by Hart and Levin at MIT in 1962. They wrote a Lisp compiler in Lisp, testing it inside an existing Lisp interpreter. Once they had improved the compiler to the point where it could compile its own source code, it was self-hosting.

There is an interesting article about bootstrapping a compiler from the ground up titled Bootstrapping a simple compiler from nothing.


Powered by Blogger