[资讯人园地]
                   C o m p i l i n g   a   C o m p i l e r
                                                CIS 85
                                                穆信成

    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    |=====>|  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中已经被加入了 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 :<换行码>Figure1<TAB的码>A 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的原文。
--