compile

w1_xiao

UNIX是以C語言寫成的。使用C語言的其中一個優(yōu)點是造成了UNIX的可攜性。
另一方面，工作站的銷售對象是需要大量計算的工程師、科學(xué)家等等；因此不同
於PC，在工作站級以上的電腦上，compiler是一項附在作業(yè)系統(tǒng)中的基本配備。
UNIX系統(tǒng)中必定附有C compiler。既然要保持可攜性， UNIX系統(tǒng)里面所附的的C
compiler也得和UNIX系統(tǒng)一樣，用C寫作。
    C compiler本身，也是用C寫的。當(dāng)一個語言的compiler 也用該語言本身來
寫的時候，  便會發(fā)生一些有趣的事情。  也許您會問，  既然電腦上面已經(jīng)有
C compiler了，那麼我們要再去compile另一個compiler的source code作什麼？
答案可能是，原有的內(nèi)建C compiler可能比較簡陋或著老舊，因此我們想把新的
compiler用舊的compiler編譯，然後當(dāng)成系統(tǒng)內(nèi)建的compiler用。換句話說，我
們就這麼擴(kuò)充了系統(tǒng)的內(nèi)建compiler。
    Glasgow大學(xué)的GRASP計劃，也用這樣的過程發(fā)展他們的Haskell compiler。
Haskell是一個functional language（85級同學(xué)記得Programming Language課中
提到的functional programming嗎？）。Functional programming總是帶有較多
的學(xué)術(shù)味而缺乏實用經(jīng)驗。Haskell語言本身仍有不少需要再擴(kuò)充的空間。GRASP
計劃用 Haskell 來寫Haskell compiler：先從簡單的寫起， 產(chǎn)生一個最原始的
Haskell compiler，然後用這套原始的Haskell語言寫一個功能較強(qiáng)的 compiler
（把原來的Haskell擴(kuò)充了），再用第二版的 Haskell 語言寫第三版的compiler
....。由於都是compiler，因此并不會減低效率。一個好處是，每次擴(kuò)充語言，
接下來立刻用新的語言寫compiler，於是我們可以立刻看出新加功能是否有用處？
該怎麼用？如此累積的經(jīng)驗，正可以作Haskell語言以後發(fā)展設(shè)計的參考。GRASP
計劃的理想就是″把functional proramming帶出實驗室″。
    UNIX的創(chuàng)造人之一，Ken Thompson，在他的 Turing Award Lecture中，便
由這個主題加以發(fā)揮，說了一些有趣的故事。C 是一個被拿來寫作業(yè)系統(tǒng)的語言。
寫作業(yè)系統(tǒng)的人很難忍得住誘惑，不在系統(tǒng)里面裝些後門的。想想看，如果我寫
作業(yè)系統(tǒng)時，偷偷在login 的部份加一段程式碼，使得全世界的這套作業(yè)系統(tǒng)只
要看到我的account和密碼就讓我進(jìn)去，給我root權(quán)限，這該是多爽呀。 但是我
不能直接在 login 的 source code 里面這樣寫，否則一下就被人抓到了（既然
source code流通，就是要給人看的呀）。 該怎麼辦呢？就從compiler里面動手
腳，稱作patch1吧：在compiler中多加一道手續(xù)， 如果發(fā)現(xiàn)被compile的原始程
式″疑似″在作login動作，就把它開個漏洞，讓我進(jìn)得去。
    但是這樣也不見得行得通。Compiler以後也會改版，新版的compiler可能不
是我在寫。裝系統(tǒng)的人也不見得用我的compiler。怎麼辦呢？於是我在compiler
的source code中作第二次手腳，稱作patch2：如果這個compiler覺得在compile
的程式″疑似″另一個 compiler 的 source 的話，就加入上面的patch1和這個
patch2本身。
    好，現(xiàn)在作業(yè)系統(tǒng)推出了，CC1 是我寫的內(nèi)建compiler，其中有我動的兩個
手腳�，F(xiàn)在某人在compile UNIX, 不得不用這個compiler。然而CC1 中已經(jīng)有了
patch1，於是一旦compile到login, compile出來的login程式就被動了手腳。只
要看到我的名字，就一定讓我進(jìn)系統(tǒng)，給我root權(quán)限。
    ,--------.      +-------------+      ,-----------.
    | login  |      |  Compiled   |      |   login   |
    | source |=====>|   by CC2    |=====>|  Program  |
    | (clean)|      | patch 1作用 |      |(受感染了!)|
    `--------'      +-------------+      `-----------'
    既然 compiler CC1會作怪， 那麼自己寫 compiler 總可以了吧？ 然而，C
compiler還是得用C寫，寫好了之後，用誰來compile呢？ 只有用CC1來compile。
CC1發(fā)現(xiàn)新寫的CC2是一個compiler的source code，於是 patch2 就發(fā)揮作用了。
CC1會在CC2中也加入patch1和patch2。於是CC2也被″污染″了。
    ,--------.      +-------------+      ,-----------.
    |  CC2   |      |  Compiled   |      |    CC2    |
    | source |=====>|   by CC1    |=====>|  Program  |
    | (clean)|      | patch 2作用 |      |含 patch1,2|
    `--------'      +-------------+      `-----------'
    如果再用CC2來compile一個正常的login程式，由於CC2中有了patch1，所以
compile出來的login程式也會有後門，讓我任意的login；
    ,--------.      +-----------+      ,----------.
    | login  |      | Compiled  |      |  login   |
    | source |=====>|  by CC2   |=====>| Program  |
    | (clean)|      |(patch 1,2)|      |(patched!)|
    `--------'      +-----------+      `----------'
    如果用CC2 compile另一個compiler CC3，由於CC2中已經(jīng)被加入了 patch2，
CC3又會被污染，也就是說CC3這個compiler中還是會有patch1和patch2......如
此一來，全世界的每一套UNIX都種下了這個後門，可以讓我任意login！
    然而這些patch都只在binary檔之中出現(xiàn)。CC2的source code一切正常，所以
從source code完全看不出有什麼不對勁呢！我們還可以進(jìn)一步湮滅證據(jù)。一旦裝
好一套系統(tǒng)，公開的CC1 source code中不必有動過手腳的程式碼，只要讓它被動
過手腳的compiler編譯就可以了。
    有著無辜的包裝，事實上內(nèi)容暗藏玄機(jī)的程式，稱作″特洛伊木馬″。 這個
特洛伊木馬的故事有趣嗎？（注1）
    用C語言寫C compiler，寫出來的程式會是個什麼樣子呢？ 舉個例子，一個C
compiler可能有一段前置處理程式在處理C字串中的溢出字元。比如說，compiler
需要把如下的字串：
        "Figure listings :\nFigure1\tA Complete Tree\n....."
給轉(zhuǎn)換成：
        Figure listings :Figure1A Complete.....
這段程式可能看起來像這樣（為簡單起見，這個程式從標(biāo)準(zhǔn)輸入讀進(jìn)原始碼，送到
標(biāo)準(zhǔn)輸出）：
      if ((c=getchar())=='\')
        switch (getchar()) {
                case 'n' :      putchar('\n');  break;
                case 't' :      putchar('\t');  break;
                                        :
        }
      else
        putchar(c);
    好像有點奇怪，是嗎？明明用if和switch把溢出字元'\'以及後面的'n','t',
分開了，在putchar的地方又送出'\n', '\t'。如果您見多了用某語言寫自己的
compiler的情況，對於這種程式段落也就見怪不怪了（注2)。
    C語言是個處在大家周遭而不常被注意到的例子。LISP語言只須簡單的parser，
不分程式和資料，使得用LISP寫LISP interpreter的情形更是普遍，也是常用的教
材。85級用的PL課本Chezzi & Jazayeri 的functional programming一章中，最後
附的LISP程式就是一個LISP interpreter。如果您研究一下，會發(fā)現(xiàn)一些感覺挺像
上面那個例子的段落。我自己玩了幾年的LISP，到頭來反倒除了LISP interpreter
之外，就不會寫其他什麼有用的程式了。這也是一個奇怪的現(xiàn)象呢。
參考資料： ACM Turing Award Lectures :
             the first twenty years 1966 to 1985
           QA76.24
                                                               #
注：1. 原本我以為Ken Thompson只是寫寫罷了。後來據(jù)一些人說，這完全是Ken
       Thompson 本人干過的真人真事。想像他老遠(yuǎn)到交大來參加conference,
       大搖大擺的走上二樓機(jī)房，若無其事地login成root的情況吧。你相不相
       信呢？
    2. 假設(shè)舊的compiler CC1并看不懂'\v'這個控制字元（垂直對齊）， 我們
       想要有一個具有這個字元的compiler。新compiler CC2的source code可
       能是這樣：
            switch (getchar()) {
                case 'n' :      putchar('\n');  break;
                case 't' :      putchar('\t');  break;
                case 'v' :      putchar('\v');  break;
                        :
            }
       但是compiler CC1并沒有辦法compile這段程式，因為CC1看不懂程式
       中的'\v'！這似乎是一個邏輯陷阱，在實際develop的時候得多花手續(xù)。
       詳見Ken Thompson的原文。


本文來自ChinaUnix博客，如果查看原文請點：http://blog.chinaunix.net/u2/84425/showart_2028778.html