[资讯人园地]

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

--