Running the “Reflections on Trusting Trust” Compiler Posted on Wednesday, October 25, 2023.
Supply chain security is a hot topic today, but it is a very old problem. In October 1983, 40 years ago this week, Ken Thompson chose supply chain security as the topic for his Turing award lecture, although the specific term wasn’t used back then. (The field of computer science was still young and small enough that the ACM conference where Ken spoke was the “Annual Conference on Computers.”) Ken’s lecture was later published in Communications of the ACM under the title “Reflections on Trusting Trust.” It is a classic paper, and a short one (3 pages); if you haven’t read it yet, you should. This post will still be here when you get back.
In the lecture, Ken explains in three steps how to modify a C compiler binary to insert a backdoor when compiling the “login” program, leaving no trace in the source code. In this post, we will run the backdoored compiler using Ken’s actual code. But first, a brief summary of the important parts of the lecture.
Step 1: Write a Self-Reproducing Program
Step 1 is to write a program that prints its own source code. Although the technique was not widely known in 1975, such a program is now known in computing as a “quine,” popularized by Douglas Hofstadter in Gödel, Escher, Bach. Here is a Python quine, from this collection:
s= ’s=%r;print(s%%s)’ ;print(s%s)
And here is a slightly less cryptic Go quine:
package main func main() { print(q + "\x60" + q + "\x60") } var q = `package main func main() { print(q + "\x60" + q + "\x60") } var q = `
The general idea of the solution is to put the text of the program into a string literal, with some kind of placeholder where the string itself should be repeated. Then the program prints the string literal, substituting that same literal for the placeholder. In the Python version, the placeholder is %r ; in the Go version, the placeholder is implicit at the end of the string. For more examples and explanation, see my post “Zip Files All The Way Down,” which uses a Lempel-Ziv quine to construct a zip file that contains itself.
Step 2: Compilers Learn
... continue reading