TrustingTrust-Thompson.pdf

Reflections on Trusting TrustKen ThompsonReprinted from Communication of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763. Copyright © 1984,Association for Computing Machinery, Inc. Also appears in ACM Turing Award Lectures: The First TwentyYears 1965-1985 Copyright © 1987 by the ACM press and Computers Under Attack: Intruders, Worms, andViruses Copyright © 1990 by the ACM press.This is a digitized copy derived from an ACM copyrighted work. It is not guaranteed to be an accurate copyof the author's original work.IntroductionI thank the ACM for this award. I can't help but feel that I am receiving this honor for timing andserendipity as much as technical merit. UNIX swept into popularity with an industry-wide change fromcentral main frames to autonomous minis. I suspect that Daniel Bobrow (1) would be here instead of me ifhe could not afford a PDP-10 and ad had to "settle" for a PDP-11. Moreover, the current state of UNIX isthe result of the labors of a large number of people.There is an old adage, "Dance with the one that brought you," which means that I should talk about UNIX. Ihave not worked on mainstream UNIX in many years, yet I continue to get undeserved credit for the workof others. Therefore, I am not going to talk about UNIX, but I want to thank everyone who has contributed.That brings me to Dennis Ritchie. Our collaboration has been a thing of beauty. In the ten years that wehave worked together, I can recall only one case of miscoordination of work. On that occasion, I discoveredthat we both had written the same 20-line assembly language program. I compared the sources and wasastounded to find that they matched character-for-character. The result of our work together has been fargreater than the work that we each contributed.I am a programmer. On my 1040 form, that is what I put down as my occupation. As a programmer, I writeprograms. I would like to present to you the cutest program I ever wrote. I will do this in three stages andtry to bring it together at the end.Stage IIn college, before video games, we would amuse ourselves by posing programming exercises. One of thefavorites was to write the shortest self-reproducing program. Since this is an exercise divorced from reality,the usual vehicle was FORTRAN. Actually, FORTRAN was the language of choice for the same reason thatthree-legged races are popular.More precisely stated, the problem is to write a source program that, when compiled and executed, willproduce as output an exact copy of its source. If you have never done this, I urge you to try it on your own.The discovery of how to do it is a revelation that far surpasses any benefit obtained by being told how to doit. The part about "shortest" was just an incentive to demonstrate skill and determine a winner.FIGURE 1Figure I shows a self-reproducing program in the C programming language. (The purist will note that theprogram is not precisely a self-reproducing program, but will produce a self-reproducing program.) Thisentry is much too large to win a prize, but it demonstrates the technique and has two important propertiesthat I need to complete my story: (I) This program can be easily written by another program. (2) This pro-gram can contain an arbitrary amount of excess baggage that will be reproduced along with the mainalgorithm. In the example, even the comment is reproduced.Stage IIThe C compiler is written in C. What I am about to describe is one of many "chicken and egg" problemsthat arise when compilers are written in their own language. In this ease, I will use a specific example fromthe C compiler.C allows a string construct to specify an initialized character array. The individual characters in the stringcan be escaped to represent unprintable characters. For example,"Hello world\n"represents a string with the character "\n," representing the new line character.FIGURE 2Figure 2 is an idealization of the code in the C compiler that interprets the character escape sequence. This isan amazing piece of code. It "knows" in a completely portable way what character code is compiled for anew line in any character set. The act of knowing then allows it to recompile itself, thus perpetuating theknowledge.FIGURE 3Suppose we wish to alter the C compiler to include the sequence "\v" to represent the vertical tab character.The extension to Figure 2 is obvious and is presented in Figure 3. We then recompile the C compiler, but weget a diagnostic. Obviously, since the binary version of the compiler does not know about "\v," the source isnot legal C. We must "train" the compiler. After it "knows" what "\v" means, then our new change willbecome legal C. We look up on an ASCII chart that a vertical tab is decimal 11. We alter our source to looklike Figure 4. Now the old compiler accepts the new source. We install the resulting binary as the newofficial C compiler and now we can write the portable version the way we had it in Figure 3.FIGURE 4This is a deep concept. It is as close t。