对信任“信任”的反思

图灵奖演讲

Ken Thompson

一个人应当在多大程度上相信某个程序不含特洛伊木马的声明？也许更重要的是信任编写该软件的人。

引言

感谢 ACM 将这个奖项授予我。我不禁觉得，自己获得这份荣誉，时机和机缘所占的分量并不比技术贡献少。UNIX† 走向流行，正赶上整个行业从集中式大型机转向自治小型机的变化。我猜，如果 Daniel Bobrow [1] 当年买不起 PDP-10、不得不“将就”使用 PDP-11，今天站在这里的可能就是他，而不是我。此外，UNIX 今天的状态是一大批人共同劳动的结果。

有句老话说，“和带你入场的人跳舞”，意思是我应该谈谈 UNIX。我已经多年没有从事主流 UNIX 的工作了，却仍然不断因为他人的工作得到本不该属于我的赞誉。因此，我不打算谈 UNIX，但我要感谢所有做出贡献的人。

这就要说到 Dennis Ritchie。我们的合作堪称美事。在一起工作的十年里，我只记得有过一次协调失误。那一次，我发现我们两人都写了同一个 20 行的汇编语言程序。我比较了两份源代码，惊讶地发现它们逐字符完全一致。我们共同工作的成果，远远大于我们各自贡献的简单相加。

我是一个程序员。在 1040 税表上，我填写的职业就是程序员。作为程序员，我写程序。我想向你们展示我写过的最巧妙的程序。我会分三个阶段来介绍，并在最后把它们合到一起。

阶段 I

上大学时，在电子游戏出现以前，我们会靠出编程练习题来自娱自乐。其中一个大家喜欢的题目，是编写最短的自复制程序（self-reproducing program）。由于这是一种脱离现实的练习，通常使用的语言是 FORTRAN。实际上，FORTRAN 之所以成为首选语言，理由和两人三足赛跑受欢迎的理由一样。

更精确地说，这个问题是：写一个源程序，编译并执行后，会输出一份与其源代码完全相同的副本。如果你从未做过这个练习，我建议你自己试一试。发现其做法的过程会带来一种启示，远胜于别人直接告诉你答案所能带来的收益。“最短”这部分只是一个激励，用来展示技巧并决出胜者。

代码 1 展示了一个用 C[3] 编程语言写成的自复制程序。（纯粹主义者会注意到，这个程序严格说并不是一个自复制程序，而是会产生一个自复制程序。）这个参赛作品太大，拿不到奖，但它展示了这种技术，并且具有两个对我完成这个故事很重要的性质：1）这个程序很容易由另一个程序写出来。2）这个程序可以包含任意数量的额外负载（excess baggage），这些内容会和主算法一起被复制。在这个例子中，连注释也会被复制。

代码 1。

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.
 */

main()
{
    int i;

    printf("char\ts[] = {\n");
    for(i=0; s[i]; i++)
        printf("\t%d,\n", s[i]);
    printf("%s", s);
}

下面是一些简单的转写说明，方便不懂 C 的读者阅读这段代码。

阶段 II

C 编译器（compiler）是用 C 写成的。我要描述的问题，是编译器用自身语言编写时会出现的许多“鸡和蛋”问题之一。在这里，我会使用 C 编译器中的一个具体例子。

C 允许用字符串结构来指定一个初始化的字符数组。字符串中的各个字符可以通过转义（escape）来表示不可打印字符。例如，

"Hello world\n"

表示一个包含字符“\n”的字符串，而这个字符代表换行字符。

代码 2.1 是 C 编译器中解释字符转义序列（character escape sequence）的代码的理想化版本。这是一段很了不起的代码。它以完全可移植的方式“知道”在任何字符集中，换行会被编译成什么字符编码。这种“知道”的行为又让它能够重新编译自身，从而把这种知识延续下去。

假设我们想修改 C 编译器，加入序列“\v”来表示垂直制表符（vertical tab character）。对代码 2.1 的扩展是显然的，如代码 2.2 所示。接着我们重新编译 C 编译器，但会得到一条诊断信息。原因很明显：编译器的二进制版本还不知道“\v”，所以这份源代码不是合法的 C。我们必须“训练”这个编译器。等它“知道”“\v”的含义之后，我们的新修改才会成为合法的 C。

我们查 ASCII 表，得知垂直制表符的十进制值是 11。于是把源代码改成代码 2.3 的样子。现在，旧编译器可以接受这份新源代码了。我们把生成的二进制文件安装为新的官方 C 编译器，此后就可以按照代码 2.2 那种可移植的写法来写了。

这是一个深刻的概念。就我所见，它已经非常接近一个“学习”程序。你只要告诉它一次，之后就可以使用这个自引用定义（self-referencing definition）。

代码 2.1。

...
c = next();
if(c != '\\')
    return(c);
c = next();
if(c == '\\')
    return('\\');
if(c == 'n')
    return('\n');
...

代码 2.2。

...
c = next();
if(c != '\\')
    return(c);
c = next();
if(c == '\\')
    return('\\');
if(c == 'n')
    return('\n');
if(c == 'v')
    return('\v');
...

代码 2.3。

...
c = next();
if(c != '\\')
    return(c);
c = next();
if(c == '\\')
    return('\\');
if(c == 'n')
    return('\n');
if(c == 'v')
    return(11);
...

阶段 III

仍然以 C 编译器为例，代码 3.1 表示 C 编译器的高层控制流程，其中例程 compile 被调用来编译下一行源代码。代码 3.2 展示了对编译器的一个简单修改：只要匹配到某个特定模式，它就会故意误编译（miscompile）源代码。如果这不是有意为之，它会被称作编译器“bug”。既然这是有意的，就应该称作“特洛伊木马”（Trojan horse）。

我实际植入编译器的那个 bug 会匹配 UNIX login 命令中的代码。替换代码会误编译 login 命令，使它既接受预期的加密密码，也接受某个已知密码。因此，如果这段代码以二进制形式安装，并且这个二进制文件被用来编译 login 命令，我就可以以任意用户身份登录那个系统。

这种明目张胆的代码不会长期逃过检测。即使只是最随意地浏览 C 编译器源代码，也会引起怀疑。

最后一步由代码 3.3 表示。它只是给已经存在的那个特洛伊木马再添加第二个特洛伊木马。第二个模式针对的是 C 编译器。替换代码是一个阶段 I 的自复制程序，它会把两个特洛伊木马都插入编译器。这需要一个像阶段 II 示例中的学习阶段。首先，我们用正常的 C 编译器编译修改后的源代码，生成一个带 bug 的二进制文件。我们把这个二进制文件安装为官方 C 编译器。现在，我们就可以从编译器源代码中移除这些 bug，而新的二进制文件会在每次被编译时重新插入这些 bug。当然，login 命令仍然会带有 bug，而且在任何源代码中都不会留下痕迹。

代码 3.1。

compile(s)
char *s;
{
    ...
}

代码 3.2。

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

代码 3.3。

compile(s)
char *s;
{
    if(match(s, "pattern 1")) {
        compile("bug 1");
        return;
    }
    if(match(s, "pattern 2")) {
        compile("bug 2");
        return;
    }
    ...
}

寓意

寓意是显然的。你不能信任并非完全由你自己创建的代码。（尤其是来自雇用了像我这样的人之公司的代码。）无论做多少源代码级别的验证或审查，都无法保护你免于使用不可信代码。在展示这种攻击的可能性时，我拿 C 编译器作例子。我也可以选择任何处理程序文本或目标的程序，比如汇编器、加载器，甚至硬件微码（microcode）。

程序所处的层级越低，这类 bug 就越难检测。一个安装得当的微码 bug 几乎不可能被发现。

在努力说服你们“我不值得信任”之后，我想做一点说教。我想批评新闻界在报道“黑客”、414 帮、Dalton 帮等群体时的处理方式。这些孩子所做的事情，往轻了说是破坏公物，往重了说很可能是非法侵入和盗窃。使黑客免于受到非常严厉起诉的，只是刑法的不完善。

容易受到这种活动影响的公司（而且大多数大公司都非常脆弱）正在大力推动刑法更新。未经授权访问计算机系统，在少数几个州已经是严重犯罪，更多州议会以及国会也正在处理这个问题。

一种爆炸性的局面正在形成。一方面，报刊、电视和电影把破坏者称作神童，把他们塑造成英雄。另一方面，这些孩子所做的行为很快就会被处以数年监禁。

我见过孩子们在国会作证。很明显，他们完全没有意识到自己行为的严重性。这里显然存在文化鸿沟。闯入计算机系统的行为，必须带有和闯入邻居家一样的社会污名。邻居家的门有没有上锁并不重要。新闻界必须明白，误用计算机并不比醉酒驾驶汽车更令人惊奇。

致谢。 我最早是在一份关于 Multics 早期实现安全性的空军批评报告 [4] 中，读到这种特洛伊木马的可能性的。我找不到关于这份文件的更具体引用。如果有人能提供这条引用，我将不胜感激。

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

† UNIX is a trademark of AT&T Bell Laboratories.