КаталогИндекс раздела


Кен Томпсон
Критика доверчивости

Речь при получении премии Тьюринга.

Ken Thompson
Reflections on Trusting Trust
Communication of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763.
Copyright © 1984, Association for Computing Machinery, Inc.


Введение

Я благодарен ACM за эту премию. Я не могу этого доказать, но я чувствую, что удостоен этой чести за своевременность и прозорливость в такой же степени, как и за технические заслуги. UNIX приобрел популярность во всем спектре индустрий от централизованных мейнфреймов до различных мини-машин. Подозреваю, что Дениел Бобров (1) должен был бы быть здесь вместо меня, если бы он не мог позволить себе PDP-10 и вынужден был бы "поселиться" на PDP-11. Более того, текущее состояние UNIX является результатом работы большого числа людей.

Есть старая поговорка: "Танцуй с тем, кто тебя привел", это означает, что я должен говорить о UNIX. Я не работал в главном потоке UNIX много лет, но все еще продолжаю получать незаслуженные кредиты для других работ. Следовательно, я не вправе говорить о UNIX, но я хочу поблагодарить всех, кто внес свой вклад.

Это подводит меня к Деннису Ритчи. Наше сотрудничество было прекрасным. За те десять лет, что мы работали вместе, я не могу вспомнить не одного случая несогласованности в работе. В одном случае я обнаружил, что мы написали одинаковые 20-строчные ассемблерные программы. Я сравнил исходники и был поражен, найдя, что они соответствуют друг другу символ в символ. Результат нашей совместной работы был много больше, чем вклад каждого по отдельности.

Я программист. В моей "форме 1040" я указываю это как свой род занятий. Как программист, я пишу программы. Мне хочется показать вам самые изящные тексты программ, которые я когда-либо писал. Я сделаю это в три этапа и попытаюсь в конце собрать их вместе.

Этап I

В колледже, до видеоигр, мы развлекались созданием программных упражнений. Одним из любимых было написание кратчайшей самовоспроизводящейся программы. Поскольку это упражнение, оторванное от действительности, обычным средством был FORTRAN. В действительности, FORNTAN был выбран по той же причине, по которой на скачках популярна трехногая лошадь. Формулируя строже, задача состояла в написании исходной программы, которая при компиляции и выполнении вырабатывала бы на выходе точную копию своего исходного текста. Если вы никогда не делали этого, я рекомендую вам попробовать сделать это самостоятельно. Открытие того, как это сделать, является откровением, которое превосходит любые выгоды, получаемые от того, что вам расскажут, как это сделать. Условие про "кратчайшую" было введено только для демонстрации мастерства и определения победителя.


      chars s[]={
            '\t',
            '0',
            '\n',
            '|',
            ':',
            '\n',
            '\n',
            '/',
            '*',
            '\n',
            (213 строк пропущено)
            0
      };
     /*
      * Строка s является
      * представлением тела
      * этой программы от '0'
      * до конца
      */
     main()
     {
            int i;

            printf("chars\t[]={\n");
            for(i=0; s[i]; i++);
                  printf("\t%d,\n",s[i]);
            printf("%s",s);
      }
     Вот некоторые простые транслитерации, позволяющие
     не-C-программисту прочитать этот код
     =      присваивание
     ==     равно, то же, что .EQ.
     !=     не равно, то же, что .NE.
     ++     инкркмент
     'x'    односимвольная константа
     'xxx'  многосимвольная константа
     %d     формат преобразования в десятичное число
     %s     формат преобразования в строку
     \t     символ табуляции
     \n     символ новой строки

Рисунок 1

Рисунок 1 показывает самовоспроизводящуюся программу на языке программирования С. (Пуристы заметят, что это программа не строго самовоспроизводящаяся, а вырабатывающая самовоспроизводящуюся программу.) Этот вариант слишком велик, чтобы выиграть приз, но демонстрирует прием и имеет два важные свойства, которые мне нужны для полноты моего рассказа: (1) Эта программа может быть легко написана другой программой. (2) Эта программа может содержать произвольное количество дополнительного багажа, который будет воспроизведен вместе с главным алгоритмом. В примере воспроизводятся даже комментарии.

Этап II

Компилятор C написан на C. Я готов объяснить эту одну из многих "проблем курицы и яйца", которая возникает, когда компилятор написан на своем собственном языке. Для простоты я использую специфический пример компилятора C. C допускает строковую конструкцию для инициализации массива символов. Отдельные символы в строке могут опущены для представления непечатаемых символов. Например ,


    "Hello world\n" 

представляет строку с символом "\n", представляющим символ новой строки.


    ...
    c=next();
    if(c!='\\')
          return(c);
    c=next();
    if(c=='\\')
          return('\\');
    if(c=='n')
          return('\n');
    ...

Рисунок 2

Рисунок 2 является идеализацией кода компилятора C, который интерпретирует последовательность символов перехода (экскейп-символов). Это удивительный фрагмент кода. Он "знает" полностью переносимый способ, которым символьный код компилируется для новой строки в любом наборе символов. Акт знания этого позволяет компилировать себя самого, воспроизводя, таким образом, это знание.


    ...
    c=next();
    if(c!='\\')
          return(c);
    c=next();
    if(c=='\\')
          return('\\');
    if(c=='n')
          return('\n');
    if(c=='v')
          return('\v');
    ...

Рисунок 3

Предположим, мы желаем изменить компилятор C, включив последовательность "\v" для представления символа вертикальной табуляции. Расширение Рисунка 2 очевидно и представлено на Рисунке 3. Затем мы перекомпилируем компилятор C, но мы получаем диагностику. Очевидно, что пока двоичная версия компилятора не знает о "\v", исходный код не является правильным для C. Мы должны "научить" компилятор. После этого он "будет знать", что означает "\v", так что наше новое изменение станет правильным для C. Мы находим по таблице ASCII, что вертикальная табуляция - это десятичное 11. Мы изменяем наш исходный код так, как показано на Рисунке 4. Теперь старый компилятор воспринимает новый исходный код. Мы устанавливаем новый двоичный код как официальный компилятор C, и теперь мы можем писать переносимую версию того, что мы имели на Рисунке 3.


    ...
    c=next();
    if(c!='\\')
          return(c);
    c=next();
    if(c=='\\')
          return('\\');
    if(c=='n')
          return('\n');
    if(c=='v')
          return(11);
    ...

Рисунок 4

Это глубокая концепция. Она настолько близка в моем представлении к "обучающейся" программе . Вы просто говорите ей один раз, затем вы можете использовать это самоссылающееся определение.

Этап III


    compile(s)
    char *s;
    {
         ...
    }

Рисунок 5

Опять-таки в компиляторе C Рисунок 5 представляет высокоуровневое управление компилятором C, где процедура "copmile" вызывается для компиляции следующей строки исходного текста. Рисунок 6 показывает простую модификацию компилятора, когда он будет сознательно ошибочно компилировать исходный текст, если он соответствует определенному шаблону. Если это сделано ненамеренно, это будет называться "багом" компилятора. Если это делается намеренно, это называется "троянским конем".


    compile(s)
    char *s;
    {
         if(match(s,"pattern")) {
                 compile("bug");
                 return
         }
         ...
    }

Рисунок 6

Баг, который я вставил в компилятор, должен соответствовать коду команды UNIX "login". Замещающий код должен неправильно компилировать команду login так, что она должна принимать либо сжатый зашифрованный пароль либо определенный известный пароль. Таким образом, если этот код будет установлен в двоичный код и двоичный код используется для компиляции команды login, я могу войти в систему как любой пользователь.

Такой очевидный код не может долго оставаться необнаруженным. Даже самое поверхностное чтение компилятора C вызовет подозрения.


    compile(s)
    char *s;
    {
         if(match(s,"pattern1")) {
                 compile("bug1");
                 return
         }
         if(match(s,"pattern2")) {
                 compile("bug2");
                 return
         }
         ...
    }

Рисунок 7

Последний этап представлен на Рисунке 2. Он просто добавляет еще одного троянского коня к уже существующему. Замещающий код является самовоспроизводящейся программой Этапа I, которая вставляет оба троянских коня в компилятор. Это требует фазы обучения, как в примере Этапа II. Сначала мы компилируем модифицированный исходный текст нормальным компилятором C для получения двоичного кода с багами. Мы устанавливаем этот двоичный код как официальный компилятор C. Мы теперь можем удалить баги из исходного текста компилятора и новый двоичный код будет вставлять баги, если он будет компилироваться. Конечно, команда login будет оставаться с багами без какого-либо следа в исходном коде.

Мораль

Мораль очевидна. Вы не можете доверять тому коду, который вы не создали полностью сами. (В особенности коду от компаний, в которых работают такие люди как я.) Никакая верификация исходников или проверка результатов не защитит вас от обманного кода. Для демонстрации этого вида атак я выбрал компилятор C. Я мог бы выбрать любую программу из системы подготовки программ, такую как ассемблер, загрузчик или даже аппаратный микрокод. По мере того, как уровень программы становится ниже, обнаружить эти баги становится все труднее и труднее. Баг, хорошо внедренный в микрокод, обнаружить почти невозможно.

После попытки убедить вас в том, что мне нельзя доверять, я хочу перейти к поучениям. Я хочу осудить прессу в ее отношении к "хакерам", банде 414, банде Дальтона и т.д. Действия этих парней являются в лучшем случае вандализмом, а в худшем - преступлением и воровством. Только недостатки криминального кодекса спасают хакеров от серьезных судебных обвинений. Компании, которые являются уязвимыми для таких преступлений (а большинство больших компаний весьма уязвимы), оказывают давление для изменения криминального кодекса. Неавторизированный доступ к компьютерным системам уже является серьезным преступлением в нескольких штатах и в настоящее время этот вопрос рассматривается в законодательстве многих других штатов и в Конгрессе.

Ситуация становится взрывоопасной. С одной стороны, пресса, телевидение и кино делает из вандалов героев, представляя их ловкими парнями. С другой стороны, действия этих парней скоро будут наказываться годами тюрьмы.

Я наблюдал за ребятами, дававшими показания в Конгрессе. Очевидно, что они совершенно не представляют себе серьезности своих действий. Они очевидно люди культурно ущербные. Акт взлома компьютерной системы должен быть настолько же социально осуждаемым, как взлом соседского дома. Не имеет значения, что дверь у соседа не заперта. Пресса должна учить, что неправильное использование компьютера не более забавно, чем пьянство за рулем.

Благодарность

Я впервые прочитал о таком троянском коне в документе ВВС (4), посвященном критике безопасности в ранней реализации Multics. Я не могу найти более точной ссылки на этот документ. Я буду благодарен тому, кто сможет предоставить мне эту ссылку.

Ссылки

  1. Bobrow, D.G., Burchfiel, J.D., Murphy, D.L., and Tomlinson, R.S. TENEX, a paged time-sharing system for the PDP-10. Commun. ACM 15, 3 (Mar. 1972), 135-143.
  2. Kernighan, B.W., and Ritchie, D.M. The C Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1978.
  3. Ritchie, D.M., and Thompson, K. The UNIX time-sharing system. Commun. ACM 17, 7(July 1974), 365-375.
  4. Unknown Air Force Document.

КаталогИндекс раздела