Compiling a Compiler

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的原文。

Ken Thomposon 現身說法 ?! Compiling a Compiler 解答篇

by 8123033 穆信成

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

　　Comp.lang.lisp 有一段時間挺混亂的. 一個Lisp討論區, 最新的 post 卻都不是什麼lisp 討論. 有人在批評 C 語言, 有人在抱 怨 UNIX 的指令太難記, 當然有人批評就有人反駁. 一些老讀者 終於看不下去了, 不得不大聲疾呼要回歸這個討論區的本來面貌, 但看大家熱烈的興頭, 要打完這許多場筆戰還有得等的呢.

　　就在這時候, 有人又想起了 Ken Thomposon 在他的圖寧獎演講中 所提及, 放在C compiler 中的那個特洛伊木馬了. 我曾在資訊人 園地 『 Compiling a Compiler 』 中談到這個故事. 『特洛伊 木馬』, 指的是外表看起來無害, 但內裡暗藏玄機的程式. 據 Ken 所說, 他在 C compiler (事實上應該是 pre-processor) 中放了一個後門, 如果compiler發現它所處理的程式是 login 的 原始程式, 它就會在裡面加入一段程式碼, 讓 Ken Thomposon 可以 login 進去. 由於 UNIX 得用 C compiler 來編譯, 這意味 著 Ken 將可以進入任何裝 UNIX 的電腦； 那麼, 我換個乾淨的 compiler 總可以吧? 但新 compiler 的原始碼也得由舊compiler 來編譯, 而為了讓這個特洛伊木馬能流傳久遠, 如果舊 com- piler 發現自己正處理的的是另一個 (正常的) C compiler, 它 就會把上面那段『如果是login, 就加入一段…』 的那段程式碼, 給插到這個compiler裡面去.

　　就在 comp.lang.lisp 正為了一些 UNIX / C 的問題吵得興高采 烈之際, 大家又回想起了這個老故事. 於是有人問了, 真有這麼 回事嗎? 抑或 Ken Thomposon 只是說說而已? 如果他真做了這麼 巧妙的一個特洛伊木馬 , 現在他已經可以進入世界上任何一台 UNIX 工作站, 如入無人之境了. 有人說, 這不過是 『一個可能 發生的假想』而已. 畢竟要寫出這樣的一個compiler, 可需要很 高的技術水準呢. 也有人說, 他當然把這個駭人聽聞的 compiler 給寫出來了, 只是沒有流出去罷了. 有人引了Ken的一段話, “ The actual bug I planted in the compiler would match code in the UNIX 'login' command”, 看到沒有, 『actual』 唷, 當然是真有其事啦. 更有人言之鑿鑿地保證, Ken 在一次 UNIX user group 集會中曾暗示著, 他已經把這個特洛伊木馬給 送出去啦!

　　終於有人在翻出Ken Thomposon的 email address後, 親自去向他 本人求證了. Ken 的回信說, 他並沒有看comp.lang.lisp 的習慣. 聽說了這個消息後, 才上去看了看相關的討論. 然而, 直接在 newsgroup 裡頭回話似乎會引起更多的誤會, 於是他就不親自出 面囉!

　　原來, Ken 在做出了這個特洛伊木馬之後, 便半哄半騙地讓 Unix Support Group 裝了他們的compiler. 大約一個月後, login程式 就如同預期地被感染了. 然而Unix Support Group 也不是等閒之 輩. 不久之後, 有人發現了, 這個C pre-processor 的 symbol table 怎麼怪怪的? 於是他們直接研究 compiler 產生的目的碼, 看看到底 Ken Thomposon 在搞什麼鬼. 最後 Ken 的計謀就曝光 啦.

　　Unix Support Group 也不急著找 Ken 算帳, 倒是用很妙的方法 解決了這個特洛伊木馬. 能直接產生目的碼的 compiler 大都有 一個 -S 的選項, 亦即要 compiler 產生組合語言檔, 而非目的 碼. 產生組合語言檔的一個理由是讓人來讀, 可以除錯用. 因此 為了避免被發現, 這個特洛伊木馬在用 -S 編譯的時候是不做壞 事的. Unix Support Group 便把所有的程式用 -S 選項編譯一次, 再另外用 assembler 產生目的檔. 於是, 這個特洛伊木馬就消失 啦!

　　Ken 說, 這個特洛伊木馬僅在他們之間被當作一個惡作劇的小把 戲, 從來沒有流出去過. 得到這個答案的 Jay R. Ashworth 很 得意地把這封 email 貼了出來, 並且告訴大家, 最好把這封信存 起來, 以備下次又有人說起這件懸案時, 就可以拿出來現寶囉! 以下是 Jay R. Ashworth 貼的原文. 檔頭和引言已經刪掉了. 

---------------------------------------------------------

Proving that the real Mrs. Robinson stood up.

It occured to me last week that ken@research.att.com is _still_ a valid address, 25 years later... so I asked. Here, from Ken himself, is the Real Story:
) From ken@plan9.att.com Sun Apr 23 14:42 EDT 1995
) Received: from plan9.att.com by IntNet.net (5.x/SMI-SVR4)
) id AA19375; Sun, 23 Apr 1995 14:42:51 -0400
) Message-Id: <9504231842.AA19375@ IntNet.net>
) From: ken@plan9.att.com
) To: jra@IntNet.net
) Date: Sun, 23 Apr 1995 14:39:39 EDT
) Content-Type: text
) Content-Length: 928
) Status: RO
) 
)

thanks for the info. i had not seen
) that newsgroup. after you pointed it
) out, i looked up the discussion.
) 
) writing to news just causes more
) misunderstandings in the future. there
) is no way to win.
[

note: I asked him if he minded my posting the reply, he had no objection ] ) fyi: the self reproducing cpp was
) installed on OUR machine and we
) enticed the "unix support group"
) (precursor to usl) to pick it up
) from us by advertising some
) non-backward compatible feature.
) that meant they had to get the
) binary and source since the source
) would not compile on their binaries.
) 
) they installed it and in a month or
) so, the login command got the trojan
) hourse. later someone there noticed
) something funny in the symbol table
) of cpp and were digging into the
) object to find out what it was. at
) some point, they compiled -S and
) assembled the output. that broke
) the self-reproducer since it was
) disabled on -S. some months later
) the login trojan hourse also went
) away.
) 
) the compiler was never released
) outside.
) 
) ken

Everyone: please save this post, so the next time the question comes up,
you can just go look. :-)

Cheers,
-- jr 'will bug legends for food' a
-- 
Jay R. Ashworth High Technology Systems Consulting Ashworth
Designer Linux: The Choice of a GNU Generation & Associates
ka1fjx/4 "I minored in babbling in college... and got +1 813 790 7592
jra@baylink.com honors in it." --Brian Heath NIC: jra3

Unix System Lab