Что бы вы сделали, когда поняли, что написанный вами фрагмент кода не работает так, как ожидалось? Попробуйте просмотреть свой код, а затем тщательно изучить его, если вы не можете найти какую-либо ошибку или возможную причину, по которой что-то может пойти не так? Что, если проблема скрыта в месте, куда вы обычно не заглядываете, потому что доверяете этому?

Рассмотрим случай, когда вы пишете код и компилируете его в переносимый формат, чтобы его можно было отправить. Вы бы доверили компилятору создание оптимизированного и работающего двоичного файла. Но что, если сам компилятор подделан, чтобы поместить в него лазейку? Чтобы понять это, сначала нам нужно понять самовоспроизводящиеся программы.

Quines или самовоспроизводящиеся программы

Самовоспроизводящаяся программа, также называемая Quine в терминологии программирования, представляет собой программу, которая не принимает никаких входных данных и создает копию собственного исходного кода в качестве единственного вывода. Попытка написать самую короткую самовоспроизводящуюся программу — это забавное упражнение, которое также помогает понять грамматику языка программирования (Quines возможны в любом полном языке программирования Тьюринга).

Проблема курицы и яйца в компиляторах

Теперь давайте рассмотрим другую проблему, связанную с внутренностями компилятора. Компиляторы часто загружаются, что является методом создания самокомпилирующегося компилятора, то есть компилятора, написанного на исходном языке программирования, который он намеревается скомпилировать. Такие языки, как C, Pascal, Java, Haskell, были предварительно загружены, то есть первоначальный компилятор был написан на другом языке, а последующие компиляторы были написаны на том языке, который необходимо было скомпилировать. Это также известно как проблема курицы и яйца. Давайте рассмотрим эту проблему с C как рассматриваемым языком.

Возьмите инициализированный массив символов в C с символами «Hello world\n». Символ ‘\n’, также называемый управляющей последовательностью, является непечатаемым символом, который создает новую строку после «Hello world».

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

Вышеприведенное является идеализацией кода компилятора C, который интерпретирует управляющую последовательность символов. Мы могли бы изменить компилятор C, включив в него последовательность «\v», представляющую символ вертикальной табуляции.

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

Мы модифицируем код компилятора, чтобы он выглядел как в приведенном выше фрагменте, и компилируем его только для того, чтобы выдать ошибку. Компилятор не знает, что представляет собой «\v» в операторе return, потому что компилятор еще не «выучил» управляющий символ «\v». ASCII-представление ‘\v’ — десятичное число 11, поэтому мы изменим наш код, чтобы он выглядел так:

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

Эта новая версия будет скомпилирована исходным компилятором. Если мы будем использовать этот новый двоичный файл в качестве официального компилятора C, мы сможем написать код, указанный в версии 2, и компилятор его скомпилирует. Таким образом, мы заставили компилятор «выучить» процедуру, которую он ранее не знал.

Представьте, что у вас есть надежный двоичный файл компилятора и его исходный код. В качестве первого шага измените исходный код компилятора, чтобы установить лазейку, когда нужно скомпилировать конкретную команду. Затем, после компиляции исходного кода с помощью доверенного компилятора, вы получите компилятор с ошибками, который будет неправильно компилировать исходный код всякий раз, когда будет совпадать конкретный шаблон. Теперь добавьте в исходный код компилятора Quine, который будет вставлять обоих троянов (бэкдор и сам quine). Скомпилируйте этот модифицированный исходный код, чтобы получить двоичный файл с ошибками. Поскольку новый компилятор с ошибками может изменить исходный код самого компилятора, чтобы повторно вставить ошибку, ошибки из источника могут быть удалены. Поэтому, если вы позже воспользуетесь этим компилятором (или любым из его «потомков») для компиляции кода входа в систему, бэкдор будет бесследно присутствовать ни в одном исходном коде.

Эту технику описал Кен Томпсон, создатель операционной системы UNIX, когда он был награжден премией Тьюринга. В своей лекции Размышления о доверии к доверию Кен Томпсон процитировал

Насколько можно доверять заявлению о том, что программа свободна от троянских коней? Возможно, важнее доверять людям, которые написали программное обеспечение.

Такие методы, как Различные двойники-Компиляция, появились, чтобы противостоять проблеме доверия и доверия. Чтобы объяснить это проще, рассмотрим наш предыдущий сценарий, у вас есть бинарник для компилятора с ошибками (B) и исходный код компилятора с удаленными ошибками/бэкдорами (S). Теперь у вашего друга есть чистый (доверенный) двоичный файл компилятора (A). Чтобы проверить, является ли B глючным компилятором, вам необходимо:

  • Скомпилируйте S, используя B, что даст двоичный файл компилятора X
  • Скомпилируйте S с помощью доверенного компилятора A , что даст новый двоичный файл компилятора Y
  • Скомпилируйте S, используя Y, что даст новый двоичный файл компилятора Z.

Если двоичный файл X отличается от двоичного файла Z, то компилятор B является «глючным» компилятором в том смысле, в каком его описывает Томпсон. Нам нужно дважды скомпилировать S, сначала с A, затем с Y, потому что A может быть другим компилятором, поэтому у него будут разные алгоритмы для кода и оптимизации производительности.

Вывод

Это может показаться очевидным: «Вы не можете доверять коду, который не писали». Я не хочу проверять все с самого начала, у других компаний и людей своя мораль и этика. Но это доверие к морали и этике ставится под сомнение такими инцидентами, как предполагаемый бэкдор, заложенный китайским правительством в серверы SuperMicro. Траммел Хадсон, исследователь безопасности, доказал, что такие атаки возможны. Нам еще предстоит дождаться вердикта по этому делу, но до тех пор продолжайте верить в доверие.