by CIS 85 穆信成

http://www.cis.nctu.edu.tw/chinese/doc/research/doc/cismagazine/cis-magazine-83-12.html

　　UNIX是以C語言寫成的。使用C語言的其中一個優點是造成了UNIX的可攜性。另一方面，工作站的銷售對象是需要大量計算的工程師﹑科學家等等；因此不同於PC，在工作站級以上的電腦上，compiler是一項附在作業系統中的基本配備。 UNIX系統中必定附有C compiler。既然要保持可攜性， UNIX系統裡面所附的的C compiler也得和UNIX系統一樣，用C寫作。

　　C compiler本身，也是用C寫的。當一個語言的compiler 也用該語言本身來寫的時候， 便會發生一些有趣的事情。 也許您會問， 既然電腦上面已經有 C compiler了，那麼我們要再去compile另一個compiler的source code作什麼？答案可能是，原有的內建C compiler可能比較簡陋或著老舊，因此我們想把新的 compiler用舊的compiler編譯，然後當成系統內建的compiler用。換句話說，我們就這麼擴充了系統的內建compiler。

　　Glasgow大學的GRASP計劃，也用這樣的過程發展他們的Haskell compiler。 Haskell是一個functional language（85級同學記得Programming Language課中提到的functional programming嗎？）。Functional programming總是帶有較多的學術味而缺乏實用經驗。Haskell語言本身仍有不少需要再擴充的空間。GRASP 計劃用 Haskell 來寫Haskell compiler：先從簡單的寫起， 產生一個最原始的 Haskell compiler，然後用這套原始的Haskell語言寫一個功能較強的 compiler （把原來的Haskell擴充了），再用第二版的 Haskell 語言寫第三版的compiler ….。由於都是compiler，因此並不會減低效率。一個好處是，每次擴充語言，接下來立刻用新的語言寫compiler，於是我們可以立刻看出新加功能是否有用處？該怎麼用？如此累積的經驗，正可以作Haskell語言以後發展設計的參考。GRASP 計劃的理想就是〞把functional proramming帶出實驗室〞。

　　UNIX的創造人之一，Ken Thompson，在他的 Turing Award Lecture中，便由這個主題加以發揮，說了一些有趣的故事。C 是一個被拿來寫作業系統的語言。寫作業系統的人很難忍得住誘惑，不在系統裡面裝些後門的。想想看，如果我寫作業系統時，偷偷在login 的部份加一段程式碼，使得全世界的這套作業系統只要看到我的account和密碼就讓我進去，給我root權限，這該是多爽呀。 但是我不能直接在 login 的 source code 裡面這樣寫，否則一下就被人抓到了（既然 source code流通，就是要給人看的呀）。 該怎麼辦呢？就從compiler裡面動手腳，稱作patch1吧：在compiler中多加一道手續， 如果發現被compile的原始程式〞疑似〞在作login動作，就把它開個漏洞，讓我進得去。

　　但是這樣也不見得行得通。Compiler以後也會改版，新版的compiler可能不是我在寫。裝系統的人也不見得用我的compiler。怎麼辦呢？於是我在compiler 的source code中作第二次手腳，稱作patch2：如果這個compiler覺得在compile 的程式〞疑似〞另一個 compiler 的 source 的話，就加入上面的patch1和這個 patch2本身。

　　好，現在作業系統推出了，CC1 是我寫的內建compiler，其中有我動的兩個手腳。現在某人在compile UNIX, 不得不用這個compiler。然而CC1 中已經有了 patch1，於是一旦compile到login, compile出來的login程式就被動了手腳。只要看到我的名字，就一定讓我進系統，給我root權限。

,----------.　　　　+---------------+　　　　,--------------. 　　
| login　|　　　　 | Compiled 　|　　　 | login　　　| 　　
| source |　=====> | by CC2 　　| =====> | Program 　|
| (clean) |　　　　 | patch 1作用 | 　　　 |(受感染了!)|
`--------- '　　　　+----------------+ 　　　　`-----------'

　　既然 compiler CC1會作怪， 那麼自己寫 compiler 總可以了吧？ 然而，C compiler還是得用C寫，寫好了之後，用誰來compile呢？ 只有用CC1來compile。 CC1發現新寫的CC2是一個compiler的source code，於是 patch2 就發揮作用了。 CC1會在CC2中也加入patch1和patch2。於是CC2也被〞污染〞了。

,------------. 　　　　　+-------------+　 　 　,------------------.
| CC2　　|　 　　　　| Compiled |　 　　　| CC2 　 　　| 　　
| source　|　=====>　 | by CC1 　| =====>　| patch 2作用 |
| Program | 　　　　　| (clean) 　 | 　　　 　|含 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中已經被加入了 patch2， CC3又會被污染，也就是說CC3這個compiler中還是會有patch1和patch2……如此一來，全世界的每一套UNIX都種下了這個後門，可以讓我任意login！

　　然而這些patch都只在binary檔之中出現。CC2的source code一切正常，所以從source code完全看不出有什麼不對勁呢！我們還可以進一步湮滅証據。一旦裝好一套系統，公開的CC1 source code中不必有動過手腳的程式碼，只要讓它被動過手腳的compiler編譯就可以了。

　　有著無辜的包裝，事實上內容暗藏玄機的程式，稱作〞特洛伊木馬〞。 這個特洛伊木馬的故事有趣嗎？（註1）

　　用C語言寫C compiler，寫出來的程式會是個什麼樣子呢？ 舉個例子，一個C compiler可能有一段前置處理程式在處理C字串中的溢出字元。比如說，compiler 需要把如下的字串：

"Figure listings :\nFigure1\tA Complete Tree\n....."

給轉換成：

Figure listings :<換行碼>Figure1A Complete.....

　　這段程式可能看起來像這樣（為簡單起見，這個程式從標準輸入讀進原始碼，送到標準輸出）：

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。如果您研究一下，會發現一些感覺挺像上面那個例子的段落。我自己玩了幾年的LISP，到頭來反倒除了LISP interpreter 之外，就不會寫其他什麼有用的程式了。這也是一個奇怪的現象呢。

參考資料： ACM Turing Award Lectures : the first twenty years 1966 to 1985 QA76.24

註：

1. 原本我以為Ken Thompson只是寫寫罷了。後來據一些人說，這完全是Ken Thompson 本人幹過的真人真事。想像他老遠到交大來參加conference, 大搖大擺的走上二樓機房，若無其事地login成root的情況吧。你相不相信呢？
2. 假設舊的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的時候得多花手續。詳見Ken Thompson的原文。