1983年ACM圖靈演講:關於信任信任的反思

我們應該在多大程度上信任一個關於程式沒有特洛伊木馬的說法？也許更重要的是信任編寫軟體的人。

KEN THOMPSON

引言

感謝 ACM 頒發此獎。我感覺獲得此榮譽，時機和機緣巧合的成分，與技術上的優點一樣多。UNIX 伴隨著產業從中央大型主機轉向自主小型機的變化而大受歡迎。我懷疑如果 Daniel Bobrow [1] 不是負擔不起 PDP-10 而「只能屈就」PDP-11，今天站在這裡的就會是他而不是我。此外，UNIX 現在的狀態是無數人努力的成果。

有句老話：「與帶你來的人共舞」（Dance with the one that brought you），這意味著我應該談論 UNIX。我已經很多年沒有參與主流 UNIX 的工作了，但我仍然因為別人的工作而獲得不應得的讚譽。因此，我將不談論 UNIX，但我想感謝所有做出貢獻的人。

這讓我想到了 Dennis Ritchie。我們的合作美好至極。在我們一起工作的十年裡，我只記得一次工作上的協調失誤。那次，我發現我們倆都寫了同一個 20 行組合語言程式。我比較了原始碼，驚訝地發現它們竟然一模一樣。我們共同工作的成果遠遠大於我們各自貢獻的工作。

我是一名程式設計師。在我的 1040 表格上，這就是我填寫的職業。作為一名程式設計師，我編寫程式。我想向各位介紹我寫過最巧妙的程式。我將分三個階段來介紹，並在最後將它們串聯起來。

UNIX 是 ATT&T Bell Laboratories 的商標。 (©1984 0001-0782/84/0800-0761 75¢

階段一

在大學時期，電子遊戲還不普及的時候，我們常以出程式設計練習題為樂。其中一個受歡迎的題目是編寫最短的自我複製程式。由於這是一個脫離現實的練習，通常選擇的載體是 FORTRAN。實際上，選擇 FORTRAN 的原因與三人腿競賽受歡迎的原因相同。

更精確地說，問題是編寫一個原始碼程式，當它被編譯和執行時，其輸出就是其原始碼的精確副本。如果你從未嘗試過，我強烈建議你自己試試看。發現如何做到這一點是一種啟示，遠勝於被告知如何做到這一點。關於「最短」的部分只是為了激勵大家展示技巧並決出優勝者。

圖 1 顯示了一個使用 C 程式語言寫成的自我複製程式。（純粹主義者會注意到這個程式並非精確的自我複製程式，而是會產生一個自我複製程式。）這個程式碼太長了，不足以贏得獎項，但它展示了這種技術，並且具有我完成我的故事所需的兩個重要屬性：1) 這個程式可以很容易地由另一個程式寫出。2) 這個程式可以包含任意數量的額外內容，這些內容將與主要演算法一起被複製。在這個範例中，甚至註解也被複製了。

chars[] = {
    '\t',
    /* ... (213 lines deleted) ... */
    0
};
/* The string s is a
   representation of the body
   of this program from '{'
   to the end.
*/
main()
{
    int i;
    printf("chars[] = { \n");
    for(i=0; s[i]; i++)
        printf("\t%d, \n", s[i]);
    printf("%s", s);
}

以下是一些簡單的轉換，以便非 C 程式設計師可以閱讀此程式碼。

FIGURE 1.

階段二

C 編譯器是用 C 語言寫的。我接下來要描述的是編譯器用自己的語言寫作時出現的眾多「雞生蛋，蛋生雞」問題之一。在此案例中，我將以 C 編譯器中的一個具體例子來說明。

C 語言允許使用字串結構來指定一個已初始化的字元陣列。字串中的單個字元可以使用跳脫序列來表示不可列印的字元。例如，"Hello world\n" 表示一個包含字元 "\n" 的字串，其中 "\n" 代表換行字元。

圖 2.1 是 C 編譯器中用於解析字元跳脫序列的程式碼的理想化版本。這是一段令人驚嘆的程式碼。它以一種完全可移植的方式「知道」在任何字元集中編譯換行字元所對應的字元碼。這種「知道」的行為隨後允許它重新編譯自己，從而延續這種知識。

假設我們希望修改 C 編譯器以包含序列 "\v" 來表示垂直定位字元（vertical tab character）。對圖 2.1 的擴展是顯而易見的，並呈現在圖 2.2 中。然後我們重新編譯 C 編譯器，但收到了診斷訊息。顯然，由於編譯器的二進位版本不知道 "\v" 的含義，原始碼並非合法的 C 語言。我們必須「訓練」編譯器。在它「知道」"\v" 的含義之後，我們新的修改才會成為合法的 C 語言。我們查閱 ASCII 表得知垂直定位字元是十進位的 11。我們修改原始碼使其看起來像圖 2.3。現在舊的編譯器接受了新的原始碼。我們將產生的二進位版本安裝為新的官方 C 編譯器，現在我們可以按照圖 2.2 的方式編寫可移植的版本了。

這是一個深刻的概念。這是我見過最接近「學習」程式的東西。你只需告訴它一次，然後你就可以使用這個自我引用的定義了。

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

FIGURE 2.1.

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

FIGURE 2.2.

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

FIGURE 2.3.

階段三

同樣在 C 編譯器中，圖 3.1 代表了 C 編譯器的高層控制流程，其中調用例行程式 compile 來編譯下一行原始碼。圖 3.2 顯示了對編譯器的一個簡單修改，它會在匹配到特定模式時故意錯誤編譯原始碼。如果這不是故意的，就會被稱為編譯器「錯誤」（bug）。既然是故意的，就應該稱之為「特洛伊木馬」（Trojan horse）。

我實際植入編譯器中的錯誤會匹配 UNIX "login" 命令中的程式碼。替換程式碼會錯誤編譯 login 命令，使其可以接受預期的加密密碼，或者一個特定的已知密碼。因此，如果這段程式碼被安裝到二進位版本中，並且這個二進位版本被用來編譯 login 命令，我就可以以任何使用者的身份登入該系統。

如此露骨的程式碼不會長期不被發現。即使是最隨意的瀏覽 C 編譯器的原始碼，也會引起懷疑。

最後一步呈現在圖 3.3 中。這只是在已存在的特洛伊木馬基礎上增加了第二個特洛伊木馬。第二個模式針對的是 C 編譯器。替換程式碼是一個階段一的自我複製程式，它將兩個特洛伊木馬都插入到編譯器中。這需要一個類似階段二的學習階段。首先，我們使用正常的 C 編譯器編譯修改後的原始碼，產生一個帶有錯誤的二進位版本（bugged binary）。我們將這個二進位版本安裝為官方的 C 編譯器。現在我們可以從編譯器的原始碼中移除這些錯誤了，新的二進位版本在編譯時會重新插入這些錯誤。當然，login 命令將保持帶有錯誤的狀態，而且在任何地方的原始碼中都找不到痕跡。

compile(s)
char *s;
{
    /* normal compilation */
}

FIGURE 3.1.

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

FIGURE 3.2.

compile(s)
char *s;
{
    if(match(s, "pattern1")) {
        compile("bug1");
        return;
    }
    if(match(s, "pattern 2")) {
        compile("bug 2");
        return;
    }
    /* normal compilation */
}

FIGURE 3.3.

寓意

寓意是顯而易見的。你不能信任非你完全自己建立的程式碼。（特別是那些僱用了像我這樣的人的公司所提供的程式碼。）無論進行多少原始碼層級的驗證或審查，都無法保護你免受使用不受信任的程式碼的影響。在展示這種攻擊的可能性時，我選擇了 C 編譯器。我本可以選擇任何處理程式的程式，例如組合器、載入器，甚至是硬體微程式碼。程式層級越低，這些錯誤就越難檢測到。一個植入良好的微程式碼錯誤幾乎不可能被檢測到。

在試圖說服你我不能被信任之後，我想說點道理。我想批評媒體對「駭客」（hackers）、414 幫、Dalton 幫等的處理方式。這些孩子們的行為充其量是破壞公物，最壞的情況可能是侵入和偷竊。只有現行刑法的不足才使這些駭客免受非常嚴重的起訴。那些容易受到此類活動侵害的公司（大多數大公司都非常脆弱）正大力推動更新刑法。未經授權存取電腦系統在一些州已經是重罪，目前許多州議會和國會也在討論此事。

一個爆炸性的局面正在醞釀。一方面，新聞、電視和電影將破壞者稱為「神童」（whiz kids），把他們描繪成英雄。另一方面，這些孩子們的行為很快就會受到數年監禁的懲罰。

我看過孩子們在國會作證。很明顯，他們完全沒有意識到自己行為的嚴重性。這顯然存在文化差異。闖入電腦系統的行為必須與闖入鄰居家具有相同的社會恥辱感。鄰居的門沒上鎖不應該成為理由。媒體必須認識到，誤用電腦與酒駕汽車一樣不值得驚奇。

鳴謝

我第一次讀到這種特洛伊木馬可能性的文章，是一篇對早期 Multics 實作安全性進行評估的 Air Force 評論 [4]。我找不到這份文件的更具體參考資料。如果有人能提供此參考資料，我將不勝感激。

參考資料

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.

作者目前地址：Ken Thompson, AT&T Bell Laboratories, Room 2C-519, 600 Mountain Ave., Murray Hill, NJ 07974.

允許在以下條件下免費複製本材料的全部或部分內容：複製非用於直接商業利益，複製件上須出現 ACM 版權聲明、出版物標題及其日期，並註明複製已獲得 Association for Computing Machinery 的許可。否則複製或再出版需支付費用和/或獲得特定許可。

Communications of the ACM 763