この記事は、1984 年に発表された Ken Thompson の寄稿 "Reflections on trusting trust" を翻訳したものです。
著作権者は以下リンク先の ACM であり、原文をdownloadできます。
August 1984 Volume 27 Number 8
Communications of the ACM
チューリングアワード講演
信頼を信頼することについての考察
あるプログラムにトロイの木馬がいないという声を、人はどこまで信用すべきなのだろうか？ おそらく、ソフトウェアを書いた人々を信頼することの方が重要なのだろう。
ケン・トンプソン
はじめに
この賞をいただきACMに感謝します。この栄誉は、技術的な功績というよりも、タイミングと偶然の賜物だと感じずにはいられません。UNIX(*1) は、中央のメインフレームから自律的なミニフレームへと業界全体が変化したことで、一気に普及した。もしダニエル・ボブ・ロウ [1] が PDP-10 を買う余裕がなく、PDP-11 に「落ち着く」しかなかったら、私の代わりにここにいただろう。さらに、UNIX の現状は多くの人々の労苦の結果である。
古い格言に "Dance with the one who brought you"（訳註: 連れてきてくれた人と踊ろう 意:サポートしてくれる人を大事にしよう）)」というのがある。私はもう何年もUNIXのメインストリームに携わっていないにもかかわらず、他の人たちの仕事に対して相応しくない評価を受け続けている。したがって、UNIXについて話すつもりはないが、貢献してくれたすべての人に感謝したい。
そこで、デニス・リッチーに話を戻そう。私たちの協力関係は素晴らしいものでした。私たちが一緒に仕事をした10年間で、仕事の調整がうまくいかなかったのは、たった一度しか思い出せない。そのときは、私たち二人が同じ20行のアセンブリ言語プログラムを書いていたことがわかった。私はソースを比較し、すべての文字が完全に一致していることに驚きました。私たちが一緒に仕事をした結果は、それぞれが貢献した仕事よりもはるかに大きなものだった。
私はプログラマーだ。所得税の申告書には職業としてそう書いてある。プログラマーとして、私はプログラムを書く。私が書いたプログラムの中で最もかわいいものを紹介したい。これを3つの段階に分けて、最後にまとめてみようと思う。
*1 UNIX は AT&T ベル研究所の登録商標です。
ステージ 1
ビデオゲーム以前の大学時代、私たちはプログラミングの練習問題を出して楽しんでいた。最も短い自己再生プログラムを書くというのがお気に入りの一つだった。これは現実から切り離された練習なので、FORTRANを使うのが普通だった。実際、FORTRANが選ばれたのは、二人三脚レースが人気があるのと同じ理由である。
より正確に言えば、この問題は、コンパイルして実行すると、そのソースの正確なコピーが出力されるソース・プログラムを書くことである。これをやったことがない人は、ぜひ自分でやってみてほしい。やり方を発見することは、誰かに教えてもらうことで得られるどんな利益をもはるかに凌駕する啓示なのだ。「最短のコード」という条件は、技術を発揮して勝者を決める動機付けに過ぎない。
図1は C プログラミング言語による自己再生プログラムである。(このプログラムは正確には自己再生プログラムではないが、自己再生プログラムを生成するものであることに、ピュアリストは気づくだろう)。このentryは賞を取るには大きすぎるが、テクニックを実証し、私の話を完成させるのに必要な2つの重要な性質を持っている。
- このプログラムは、他のプログラムによって簡単に書くことができる。
- このプログラムは、再現されるメインのアルゴリズムに余分なものを付け足すことができる。
この例は、コメントまで再現している。
（訳註 表の下部にはC言語の読み方が書いてある。 = はアサイン、 ==はイコール、++はインクリメント etc）
ステージ 2
CコンパイラはC言語で書かれている。これから説明するのは、コンパイラが独自の言語で書かれている場合に発生する多くの「鶏と卵」問題の一つである。今回は、Cコンパイラの具体的な例を使って説明しよう。
C言語では、文字列構成子で初期化された文字配列を指定することができる。文字列の各文字はエスケープして、印字不可能な文字を表すことができる。
例えば、"Hello world\n" の "\n" は、改行文字を表す。
図2.1は、文字エスケープシーケンスを解釈するCコンパイラのコードを理想化したものである。これは驚くべきコードである。これは、どのような文字セットでどのような文字コードが改行用にコンパイルされるかを、完全に移植可能な方法で「知っている」のです。そして、その「知っている」という行為によって、自分自身を再コンパイルし、その知識を永続させることができるのです。
例えば、Cコンパイラに「\v」というシーケンスを追加して、垂直タブ文字を表現したいとします。図2.1への拡張は明らかであり、図2.2のようになる。次にCコンパイラを再コンパイルすると、診断結果が表示される。コンパイラを「訓練」しなければならない。縦タブが10進数11であることをASCIIチャートで調べます。図2.3のようにソースを変更する。これで古いコンパイラは新しいソースを受け入れるようになった。出来上がったバイナリを新しい公式Cコンパイラーとしてインストールすれば、図2.2のようにポータブル・バージョンを書くことができる。これは深い概念だ。これは、私がこれまで見てきた中で最も「学習」プログラムに近いものだ。一度教えれば、あとはこの自己参照定義を使うことができる。
ステージ 3
ここでも、図3.1はCコンパイラの高レベル制御を表しており、ルーチン 「compile」 が次の行のソースをコンパイルするために呼び出される。図3.2は、特定のパターンにマッチするたびに意図的にソースをミスコンパイルする、コンパイラの単純な改造を示している。これが意図的なものでなければ、コンパイラの「バグ」と呼ばれるだろう。意図的なものなので、「トロイの木馬」と呼ぶべきだろう。
私がコンパイラに仕込んだ実際のバグは、UNIXの "login" コマンドのコードにマッチする。このコードはログイン・コマンドをミスコンパイルし、暗号化された意図したパスワードか、既知の特定のパスワードのどちらかを受け入れるようにする。したがって、このコードがバイナリでインストールされ、そのバイナリがログイン・コマンドのコンパイルに使われた場合、私はどのユーザーとしてもそのシステムにログインできることになる。
このようなあからさまなコードは、長く隠しておくことはできないだろう。Cコンパイラのソースを何気なく読んだだけでも、疑念を抱くだろう。
最後のステップを図3.3に示す。これは単純に、すでに存在するトロイの木馬に2つ目のトロイの木馬を追加するだけである。2つ目のパターンはCコンパイラを標的にしている。この置換コードは、両方のトロイの木馬をコンパイラに挿入するステージ1の自己複製プログラムである。これには、ステージ2の場合と同様に学習段階が必要である。まず、修正したソースをノーマルCコンパイラでコンパイルし、バグのあるバイナリを生成する。これでコンパイラのソースからバグを取り除くことができ、新しいバイナリはコンパイルされるたびにバグを再び挿入する。もちろん、ログインコマンドはバグのままであり、ソースのどこにも痕跡は残らない。
モラル
教訓は明白だ。自分で完全に作成していないコードは信用してはいけない。(特に私のような人間を雇っている会社のコードは。）いくらソース・レベルでの検証や精査を行っても、信頼できないコードからあなたを守ることはできない。この種の攻撃の可能性を示すために、私はCコンパイラーを取り上げた。アセンブラやローダー、あるいはハードウェア・ミ クロコードなど、プログラムを処理するプログラムであれば、どのようなものでも構わない。プログラムのレベルが低くなればなるほど、このようなバグの検出は難しくなる。うまくインストールされたマイクロコードのバグを検出するのはほとんど不可能だろう。
私が信用できないことを納得させようとした後で、道徳的なことを申し上げたい。私は、「ハッカー」、414ギャング、ダルトン・ギャングなどに対するマスコミの対応を批判したい。これらの子供たちが行った行為は、よく言えば破壊行為であり、悪く言えば不法侵入や窃盗であろう。ハッカーたちを非常に重い訴追から救っているのは、刑法の不備だけである。このような行為に対して脆弱な企業（そしてほとんどの大企業は非常に脆弱である）は、刑法改正を強く求めている。コンピューター・システムへの不正アクセスは、すでにいくつかの州では重大な犯罪となっており、現在さらに多くの州議会や議会で取り上げられている。
爆発的な状況が生まれている。一方では、マスコミやテレビ、映画は、破壊者を天才児と呼んでヒーローにしている。他方で、これらの子供たちが行った行為は、やがて懲役数年で罰せられることになるだろう。
私は子供たちが議会で証言するのを見たことがある。彼らが窃盗行為の重大さをまったく認識していないのは明らかだ。明らかに文化的なギャップがある。コンピューター・システムに侵入する行為は、隣人の家に侵入するのと同じ社会的汚名を着せなくてはならない。隣の家のドアに鍵がかかっていないことは問題ではないはずだ。マスコミは、コンピューターの誤った使用は、自動車の飲酒運転と同じくらい驚くべきことではないことを学ばなければならない。
追記
私がこのようなトロイの木馬の可能性を初めて知ったのは初期の Multics 実装のセキュリティを論じる 空軍の批評[4]を読んだ時だった。この文書について、より具体的な言及を見つけることができません。この文献を提供できる方がいらっしゃいましたら、ぜひ教えていただければ幸いです。
REFERENCES
1, Bobrow, D.G., Burchfiel, J.D., Murphy, D.L., and Tomlinson, R.S. TENEX, a paged time-sharingsystem 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, 0uly 1974), 365-375.
4. Unknown Air Force Document.
©1984 0001-0782/84/0800-076175¢
訳註
ほとんど www.DeepL.com/Translator（無料版）で翻訳しました。
翻訳に苦情がある人は自分で書く or 編集リクエストを送ってくださいませ
参考
414ギャング（訳註 10代の6人がシステム侵入でメディアに広く取り上げられた）
ダルトン・ギャング（訳註 犯罪集団をメディアが持ち上げた）