TURING AWARD LECTURE

Reflections on Trusting Trust
To what extent should one trust a statement that a program is free of Trojan
horses? Perhaps it is more important to trust the people who wrote thesoftware.

KEN THOMPSONINTRODUCTION
I thank the ACM for this award. I can't help but feelthat I am receiving this honor for timing and serendipity as much as technical merit. UNIX 1 swept into popularity with an industry-wide change from central mainframes to autonomous minis. I suspect that Daniel Bobrow [1] would be here instead of me if he could notafford a PDP-10 and had had to "settle" for a PDP-11.
Moreover, the current state of UNIX is the result of thelabors of a large number of people.
There is an old adage, "Dance with the one thatbrought you," which means that I should talk about
UNIX. I have not worked on mainstream UNIX in m a n yyears, yet I continue to get undeserved credit for thework of 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 was astounded to find that they matched character-for-character. The result of our work together has been far
greater than the work that we each contributed.
I am a programmer. On my 1040 form, that is what I
put down as m y occupation. As a programmer, I write
1 UNIX is a trademark of AT&T Bell Laboratories.
© 1 9 8 4 0001-0782/84/0800-0761 75¢

August 1984

Volume 27 Number 8programs. 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 asource program that, w h e n 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 todemonstrate skill and determine a winner.
Figure 1 shows a self-reproducing program in the C 3
programming language. (The purist will note that theprogram is not precisely a self-reproducing program,but will produce a self-reproducing program.) This entry is much too large to win a prize, but it demonstrates
the technique and has two important properties that I
need to complete m y story: 1) This program can beeasily written by another program. 2) This program cancontain an arbitrary amount of excess baggage that will
be reproduced along with the main algorithm. In theexample, even the comment is reproduced.

Communications of the ACM

781

Turing Award Lecturechar s[ ] = It011
i;i"~lllI'V,] ' ~I'~t'] l p(213 lines deleted)
01;/,• The string s is a
• representation of the body• of this program from '0'• to the end.

,/STAGE III
Again, in the C compiler, Figure 3.1 represents the highlevel control of the C compiler where the routine "com-main( ){int i;
printf("char\ts[ ] = {kn");for(i=0; s[i]; i++)printf("~t%d, \n", s[i]);printf("%s", s);I
Here are some simple transliterations to allow
a non-C programmer to read this code.
=assignment==
equal to .EQ.
!=
not equal to .NE.
++
increment'x'
single character constant"xxx" multiple character string%dformat to convert to decimal%s
format to convert to stringkt
tab characterkn
newline character
F I G U R E 1.

STAGE II
The C compiler is written in C. What I am about todescribe is one of m a n y "chicken and egg" problems
that arise when compilers are written in their own language. In this case, 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 string
can be escaped to represent unprintable characters• For
example,"Hello w o r l d \ n "represents a string with the character "\n," representing
the new line character.
Figure 2.1 is an idealization of the code in the Ccompiler that interprets the character escape sequence.
This is an amazing piece of code. It "knows" in a completely portable way what character code is compiled
for a new line in any character set. The act of knowing
762

then allows it to recompile itself, thus perpetuating theknowledge.
Suppose we wish to alter the C compiler to include
the sequence "\v" to represent the vertical tab character. The extension to Figure 2.1 is obvious and is presented in Figure 2.2. We then recompile the C compiler, but we get a diagnostic. Obviously, since the binary version of the compiler does not know about "\v,"
the source is not legal C. We must "train" the compiler.
After it "knows" what "\v" means, then our newchange will become legal C. We look up on an ASCII
chart that a vertical tab is decimal 11. We alter oursource to look like Figure 2.3. Now the old compiler
accepts the new source. We install the resulting binary
as the new official C compiler and now we can write
the portable version the way we had it in Figure 2.2.
This is a deep concept. It is as close to a "learning"
program as I have seen. You simply tell it once, then
you can use this self-referencing definition.

Communications of the ACM

c = next( );if(c != ' \ V )return(c);c = next( );if(c = = ' \ V )return('\\');
if(c = = 'n')return('kn ');F I G U R E 2.2.

c = next( );if(c ~= '\v)return(c);c = next( );if(c = = ' \ V )return('kV);if(c = = 'n')retum('kn');
if(c = = 'v')return('\v');F I G U R E 2.1.
c = next( );if(c != ' \ V )return(c);c = next( );if(c == '\v)return('\\');
if(c = = 'n')return('\ n');if(c = = 'v')return(11 );F I G U R E 2.3.

August 1984 Volume 27 Number 8

Turing Award Lecturepile" is called to compile the next line of source. Figure
3.2 shows a simple modification to the compiler thatwill deliberately miscompile source w h e n e v e r a particular pattern is matched. If this were not deliberate, itwould be called a compiler "bug." Since it is deliberate,
it should be called a "Trojan horse."
The actual bug I planted in the compiler would
match code in the UNIX "login" command. The replacement code would miscompile the login c o m m a n dso that it would accept either the intended encrypted
password or a particular known password. Thus if thiscode were installed in binary and the binary were used
to compile the login command, I could log into thatsystem as any user.
Such blatant code would not go undetected for long.
Even the most casual perusal of the source of the Ccompiler would raise suspicions.
The final step is represented in Figure 3.3. This simply adds a second Trojan horse to the one that alreadyexists. The second pattern is aimed at the C compiler.
The replacement code is a Stage I self-reproducing program that inserts both Trojan horses into the compiler.
This requires a learning phase as in the Stage II example. First we compile the modified source with the normal C compiler to produce a bugged binary. We install
this binary as the official C. We can now remove thebugs from the source of the compiler and the new binary will reinsert the bugs w h e n e v e r it is compiled. Of
course, the login c o m m a n d will remain bugged with notrace in source anywhere.

compile(s)char ,s;I
FIGURE 3.1.
compile(s)char ,s;Iif(match(s, "pattern")) {compUe("bug");
return;JFIGURE 3.2.
compile(s)char ,s;if(match(s, "pattern1 ")) {compile ('bug1 ");return;Iif(match(s, =pattern 2")) I
compile ('bug 2");
return;JFIGURE 3.3.
August 1984 Volume27 Number 8

MORAL
The moral is obvious. You can't trust code that you did
not totally create yourself. (Especially code from companies that employ people like me.) No amount ofsource-level verification or scrutiny will protect you
from using untrusted code. In demonstrating the possibility of this kind of attack, I picked on the C compiler.
I could have picked on any program-handling program
such as an assembler, a loader, or even hardware microcode. As the level of program gets lower, these bugs
will be harder and harder to detect. A well-installedmicrocode bug will be almost impossible to detect.
After trying to convince you that I cannot be trusted,
I wish to moralize. I would like to criticize the press in
its handling of the "hackers," the 414 gang, the Daltongang, etc. The acts performed by these kids are vandalism at best and probably trespass and theft at worst. It
is only the inadequacy of the criminal code that saves
the hackers from very serious prosecution. The companies that are vulnerable to this activity, (and most large
companies are very vulnerable) are pressing hard to
update the criminal code. Unauthorized access to computer systems is already a serious crime in a few statesand is currently being addressed in m a n y more statelegislatures as well as Congress.
There is an explosive situation brewing. On the one
hand, the press, television, and movies make heros ofvandals by calling them whiz kids. On the other hand,the acts performed by these kids will soon be punishable by years in prison.
I have watched kids testifying before Congress. It isclear that they are completely unaware of the seriousness of theft acts. There is obviously a cultural gap. The
act of breaking into a computer system has to have thesame social stigma as breaking into a neighbor's house.
It should not matter that the neighbor's door is unlocked. The press must learn that misguided use of acomputer is no more amazing than drunk driving of anautomobile.
Acknowledgment. I first read of the possibility of sucha Trojan horse in an Air Force critique [4] of the security of an early implementation of Multics. I cannot finda more specific reference to this document. I would
appreciate it if anyone who can supply this reference
would let me know.
REFERENCES
1, Bobrow, D.G., Burchfiel, J.D., Murphy, D.L., and Tomlinson, R.S.
TENEX, a paged time-sharing system for the PDP-10. Commun. ACM
15, 3 {Mar. 1972}, 135-143.
2. Kernighan, B.W., and Ritchie, D.M. The C Programming Language.
Prentice-Hall, Englewood Cliffs, N.J., 1978.
3. Ritchie, D.M., and Thompson, K. The UNIX time-sharing system.
Commun. ACM 17, 0uly 1974), 365-375.
4. Unknown Air Force Document.

Author's Present Address:Ken Thompson, AT&TBell Laboratories,
Room 2C-519, 600 Mountain Ave., Murray Hill, NJ 07974.
Permission to copy without fee all or part of this material is granted
provided that the copiesare not made or distributed for direct commercial advantage, the ACM copyrightnotice and the title of the publicationand its date appear, and notice is given that copyingis by permission ofthe Associationfor Computing Machinery.To copy otherwise, or torepublish, requires a fee and/or specificpermission.
Communications of the ACM

763