1983年图灵奖演讲稿

关于可信信任的沉思

KEN THOMPSON
AT&T Bell Laboratories
Murray Hill, NJ 07974

[Ken Thompson是1983年ACM图灵奖共同获得者,是为表彰他在开发和实现UNIX操作系统中的工作。参见D. M. Ritchie的演讲稿,“关于软件研究的沉思”,163页中的介绍。]

题外话:一个人应该相信,一个程序可以免受特洛伊木马攻击的声明吗?或者信任写这个软件的人,才更重要。

简介

我感谢ACM颁发这个奖章。我不得不说,我得这个奖是因为时机和运气,而不仅是技术上的价值。UNIX的普及伴随工业界从集中式大型主机,到自治式微型系统的转变。如果Daniel Bobrwo不能提供一个PDP-10,并不得不接受PDP-11,我想在这儿的会是他而不是我。此外UNIX现在的发展,是许多人工作的结果。

一条谚语说,“与带你来的人跳舞”,这是说,我不得不谈谈UNIX。我已经很多年没有在主流UNIX上工作了,却继续获得不应得到的,因为其他人的工作带来的荣誉。所以,我不打算谈论UNIX,但我感谢作出贡献的每一个人。

那把我带到Dennis Ritchie。我们的合作是一件美好的事。在我们一起工作的十年间,我能回忆起只有一次工作上的不协调。那一次,我发现我们都写了20行相同的汇编语言程序。我比较源代码,大为吃惊,它们逐字符匹配。我们共同工作的结果,远超过了我们独自工作的贡献。

我是一个程序员。这是我在我的1040表格内,所填写的职业。作为一个程序员,我写一些程序。我将给你看,我写过的最漂亮的程序。我将分三个步骤,并在试着在最后,把它们结合到一起。

第一阶段

在有影像游戏之前,我们在大学,做一些编程练习作为娱乐。爱好之一是编写最短的自我复制程序。因为是与现实无关的练习,常用的工具是FORTRAN。事实上,FORTRAN之所以成为所选择的语言,与三腿赛跑流行的理由一样。

更准确地说,问题是写一个源程序,当编译和执行时,将产生一个它的源代码的精确拷贝,作为输出。如果你没有做过这样的练习,我劝你试一试。发现如何做,会表现出比被人告诉如何做,远远好得多。关于最短,只是处于展示技巧的动机,和用来决定获胜者的。

图1展示了一个C程序设计语言版的自我复制程序。(纯粹主义者会注意到这个程序不能严格说是一个自我复制程序,但是产生一个自我复制程序。) 这个程序太长了,以至于不能获奖。但是它展示了这个程序的技巧,还有我要谈到的、两个重要特点:(1)这个程序可以很容易用其它语言编写。(2)这个程序可以包含和主算法一起被复制产生的,任意数量的代码。在这个例子中,甚至注释也被复制产生了。

第二阶段

C编译器是用C编写的。我将要描述的,是许多“鸡和蛋”问题中的一个,比如编译器用它们本身的语言来编写。在这种情况下,我将使用C编译器中的一个特别的例子。

          +--------------------------------------------------+
          |  char s[ ] = {                                   |
          |      '\t',                                       |
          |      '0',                                        |
          |      '\n',                                       |
          |      '}',                                        |
          |      ';',                                        |
          |      '\n',                                       |
          |      '\n',                                       |
          |      '/',                                        |
          |      '*',                                        |
          |      '\n',                                       |
          |      (213 lines deleted)                         |
          |      0                                           |
          |  };                                              |
          |                                                  |
          |  /*                                              |
          |   *The string s is a                             |
          |   *representation of the body                    |
          |   *of this program from '0'                      |
          |   *to the end.                                   |
          |   */                                             |
          |                                                  |
FIGURE 1  |  main( )                                         |
          |  {                                               |
          |      int i;                                      |
          |      printf("char\ts[ ]= { \n");                 |
          |      for(i=0; s[i]; i++)                         |
          |          printf("\t%d, \n", s[i]);               |
          |      printf("%s", s);                            |
          |  }                                               |
          |                                                  |
          |  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                 |
          |  %d    format to convert to decimal              |
          |  %s    format to convert to string               |
          |  \t    tab character                             |
          |  \n    newline character                         |
          +--------------------------------------------------+

C允许一个字符串初始化给一个字符数组。串中的单个字符,可被转义表示不可打印字符。例如,

                      "Hello world\n"

表示一个串,和表示换行符的字符“\n”。

图2.1是一个C编译器中解释转义序列的理想化代码。这是一个令人吃惊的代码。它以完全可移植的方式,知道任何一个字符集中的什么字符代码,被编译为换行符。它“知道”,并允许重编译它自身,从而令知识永垂不朽。

假设我们想修改编译器,以包含序列“\v”来表示垂直制表符。对图2.1的扩展是明显的,并且它就在图2.1中。我们然后重新编译这个C编译器,但我们会得到一个表示错误的提示。显然,既然这个编译器的二进制版本不知道“\v”,源代码在C中不是合法的。我们必须训练编译器。在它“知道”了“\v”为何物后,我们新增的改变会变成合法的C代码。我们在ASCII图表中查找到,垂直制表符的数值是11。我们把我们的源代码修改为图2.3那样。现在旧编译器接受新代码。我们安装产生的二进制,作为新的正式的C编译器,现在我们我们可以写一个,像图2.2那样的可移植版本。

    +---------------------+  +---------------------+  +---------------------+
    |  ...                |  |  ...                |  |  ...                |
    |  c = next();        |  |  c = next( );       |  |  c = next( );       |
    |  if(c != '\\')      |  |  if(c != '\\')      |  |  if(c != '\\')      |
    |      return(c);     |  |      return(c);     |  |     return(c);      |
    |  c = next():        |  |  c = next( );       |  |  c = next( );       |
    |  if(c == '\\')      |  |  if(c == '\\')      |  |  if(c == '\\')      |
    |      return('\\');  |  |      return('\\');  |  |      return('\\');  |
    |  if(c == '\n')      |  |  if(c == '\n')      |  |  if(c == '\n')      |
    |      return('\n');  |  |      return('\n');  |  |      return('\n');  |
    |  ...                |  |  if(c == '\v')      |  |  if(c == '\v')      |
    |                     |  |      return('\v');  |  |      return('\v');  |
    |                     |  |  ...                |  |  ...                |
    +---------------------+  +---------------------+  +---------------------+

          FIGURE 2.1               FIGURE 2.2               FIGURE 2.3

这是更深的概念。它接近一个我看见过的学习程序。你简单地了解一次,然后你能使用这个自引用定义。

第三阶段

再次,在C编译器中,图3.1表示C编译器在“编译”例程,被调用来编译下一行源代码时的高级控制。图3.2展示了一个对于

    +--------------+  +--------------------------------+
    |  compile(s)  |  |  compile(s)                    |
    |  char *s;    |  |  char *s;                      |
    |  {           |  |  {                             |
    |      ...     |  |      if(match(s, "pattern")){  |
    |  }           |  |          compile("bug");       |
    |              |  |          return;               |
    |              |  |      }                         |
    |              |  |      ...                       |
    |              |  |  }                             |
    +--------------+  +--------------------------------+

       FIGURE 3.1               FIGURE 3.2

在匹配一个特别模式时,故意编译出错的编译器的简单修改。如果这不是有意的,它会被称为一个编译器“缺陷”。因为这是故意的,它应该被称为一个“特洛伊木马”。

这个我写在编译器中的真实的缺陷,会匹配UNIX的login程序中的代码。用于替换的代码会对login命令产生编译出错,所以它将接受一个计划好的加密口令,或一个特别的已知口令。因此如果这段代码被安装进二进制文件,并且该二进制文件被用于编译login命令,我则可以使用任何用户登录进那个系统。

这样显眼的代码不会很久都不被察觉。设置大部分对这个C编译器源代码的偶尔阅读,就会引起猜疑。

最后的的步骤展现在图3.3中。这只简单添加了第二个特洛伊木马,到那个已存在的程序。第二个模式的目标是C编译器。用于替换的代码,是第一步中向编译器插入两个特洛伊木马的自我复制程序。

            +-----------------------------------+
            |  compile(s)                       |
            |  char *s;                         |
            |  {                                |
            |      if(match(s, "pattern1")){    |
            |          compile("bug1");         |
            |          retum;                   |
FIGURE 3.3  |      }                            |
            |      if(match(s, "pattern 2")) {  |
            |          compile ("bug 2");       |
            |          return;                  |
            |      }                            |
            |      ...                          |
            |  }                                |
            +-----------------------------------+

这需要一个像第二步中的学习阶段。首先,我们使用正常的编译器编译修改过的源代码,产生一个有缺陷的二进制文件。我们把它安装为正式的C编译器。我们现在能移去源代码中的缺陷,新的二进制文件在编译它时,将重新插入该缺陷。当然,login命令仍然有缺陷,但在源代码中却找不到。

教训

这个教训是明显的。你不能信任,不是完全由你编写的代码。(尤其是代码来自一个雇用我这种人的公司。) 不论做了多少次源代码级别或安全性检查,都不能对你使用不可信任代码起到保护作用。

在展示此类攻击可能性中,我选择了C编译器。我也可以选择程序-处理程序比如汇编器、装载器,或甚至硬件微码。程序的等级越低,这类缺陷越难以发觉。一个设置得好的微码缺陷几乎不可能被发觉。

在尝试让你确信我不可被信任后,我想要多说几句。我要责备新闻机构在“黑客”上的错误处理,414帮、道尔顿帮,等等。这些孩子的行为至多是一些破坏,最糟糕的可能是入侵和盗窃。这只是使黑客免于严重起诉的,不充分的定罪条目。那些容易受到此类活动攻击的公司(并且大多数大公司容易遭受攻击)增加压力,要求升级定罪条目。未授权登入计算机系统,在一些州已经是一项重罪,并且更多州法院,像国会一样,也在忙于这类事情。

这暴露出正在酝酿这种状况。一方面,新闻机构、电视和电影塑造破坏之王,并叫他们天才儿童。另一方面,这些孩子们的行为,将很快受到处罚,会在监狱里呆几年。在国会之前,我看过这些孩子作证。清楚的一点是,他们完全不知道他们的行为的严重性。明显存在一个教育上的缺失。闯入计算机的行为应该和闯入邻居的房子,有类似的社会罪行。不管邻居是不是没有锁门。新闻机构必须知道,误导对计算机的使用,和醉酒驾车类似,并没有更多惊奇。

致谢

我第一次读到关于这样一个特洛伊木马的可能性,是在一个空军的对早期Multics实现的安全批评。我不能找到这个文档的一个更详细的参考。我心有感激,如果有人能够提供这个参考,让我知道。

参考

  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, 7(July 1974), 365-375.
  4. Unknown Air Force Document.

分类和主题描述

D.2.5 [Software Engineering]: Testing and Debugging--debuggingaids; D.3.2 [Programming Languages]: Language Classifications--applicative languages; D.3.4 ]Programming Languages]: Processors--compilers; D.4.6 [Operating Systems]: Security and Protection--access controls

通用术语

Design, Languages, Legal Aspects

附加关键字和短语

C, UNIX


(This Chinese translation isn't confirmed by the author, and it isn't for profits.)

Translator : jhlicc@gmai1.c0m
Origin : http://awards.acm.org/turing/addl_info/articles/2678824.pdf