That Time Ken Thompson Wrote a Backdoor into the C Compiler

Summary

When Ken Thompson won the Turing Award jointly with Dennis Ritchie for their work in UNIX, he was expected like other Turing winners to write a paper that would be published in the ACM Computer Journal. What he ended up submitting was a paper about "the cutest program [he] ever wrote"-- a sneaky undetectable self-reproducing "Trojan horse" backdoor in the C compiler that would allow him to log into affected machines as any user. Table of Contents VIDEO Thompson didn't want to write about the usual things that Turing award winners write about— in fact, according to him, he didn't want to write a paper at all. However, when he did finally write a paper (after putting it off for a year past the original deadline, see ~2:52:49 in the above video), he describes at a high level how the C compiler (itself a program written in C) parses and compiles C source code into machine code to set the stage for how the "Trojan horse" would be injected into the generated machine code while leaving the original input C source code seemingly unmodified. He explains that while in college at UC Berkeley, him and colleagues would "[amuse themselves] by posing programming exercises," one of which was "to write the shortest self-reproducing program": More precisely stated, the problem is to write a source program that, when compiled and executed, will produce as output an exact copy of its source ... The part about "shortest" was just an incentive to demonstrate skill and determine a winner. In this section, I'll try to illustrate the "Trojan horse" originally presented by Thompson through a combination of the original quasi-C pseudocode and the source code and examples from Russ Cox's article on this subject, where Cox got Thompson to actually send him the source code after seeing a talk Thompson gave in 2023. In this stage, Thompson describes a self-reproducing program (also known as a "quine"). The key insight is that a program can contain its own source code as data, which it then prints...