Share
Embed
自作Cコンパイラ 8時間の奮闘
2024-09-07 セキュリティキャンプ アフターイベント
2024-09-14 traP & Zli 合同LT
で発表したスライドになります。
soukouki
September 14, 2024
Transcript
29 slides
-
10ccのコード 第1世代 GCC 10ccのコード 第2世代 第1世代 10ccのコード 第3世代 第2世代 達成したこと
期間中に見事 セルフホスト を達成す ることが出来ました。セルフ ホストとは、自作Cコンパイ ラ自身で、自分自身をコンパ イルすることです。図でいう 第2世代以降を作るのがセル フホストになります。 1. セルフホストの要件には、第2世代と第3世代を一致させることで不動点を 作るというのもありますが、今回は省略します。 6 -
Cコンパイラゼミで得られたこと C言語に対する深い知識 例: switch文の構文、知ってますか? → Duff's device で検索! 例: スタック領域に変数を確保するって、何が行われているの?
アセンブリの知識 わからない命令の調べ方 基本的な演算, ジャンプ, レジスタの扱いなど 難しいバグについても根気強く向き合う経験 セルフホストの際には込み入ったバグが多く発生します。 コードは全部手元にあるので、気合を入れてデバッグすれば必ず解 決できます! 7 -
フランケンコンパイル セルフホストのデバッグをする際に、いきなり全部セルフホストをす ると大変なので、「フランケンコンパイル」という手法を使います。 10cc のソースコードの一部を 10cc (第1世代)でコンパイルし、残り をGCCでコンパイルして、どのファイルがバグの原因なのかを探りま す。 GCCとの相互運用性を保つために、
10cc とGCCの出力するアセンブ リが互換性を持つようにしないといけません。今回は、構造体のアラ イメントをきちんと実装するだけで、フランケンコンパイルが出来る ようになりました。(バグが出始めてから2時間経過) 1. フランケンコンパイルという名称は、Cコンパイラゼミの講師であるhsjoihs氏が名付けたものです。 セキュキャンのCコンパイルゼミでしか使われていない独自用語らしいで す。 2. 実際には、構造体のアライメントをテストするために、 offsetof というものも実装しました。 11 -
10cc の構造 10cc は、以下のように4つの部分と、それを呼び出す main.c に別れ ています。それぞれの部分ごとにフランケンコンパイルを試していき ます。 字句解析 構文解析
意味解析 コード生成 トークン列 構文木 構文木 ソースコード アセンブリ 1. 他にも map.c というファイルがあったりしますが、ここでは省略します。 12 -
10ccのコード 第1世代 GCC 10ccのコード 第2世代 第1世代 10ccのコード 第3世代 第2世代 ここで
main.c を睨みつけた くなるのですが、実はそう上 手くは行きません。 直接 main.c に問題があるの ではなく、 main.c をコンパ イルした第1世代のどこかに 問題があるということです。 main.c をいくら睨みつけて も、 main.c のC言語のコード は正しいのです。 14 -
この時点でのエラー状況 map.cだけ自作コンパイラ、それ以外はgcc → 成功 main.cだけ自作コンパイラ、それ以外はgcc → 謎のエラー 「関数の戻り値の型がありません」!? 字句解析だけ →
失敗(セグフォ) 構文解析だけ → 成功 意味解析だけ → 成功 コード生成だけ → 成功 次に字句解析だけ 10cc のパターンを追ってみることにしました。 18 -
第1世代 (壊れている) 10ccのコード GCC 10ccのコード 第1世代(壊) 第2世代 (壊れている) この状況から、以下の形でバ グがあると予想できます。
1. 10cc のどこかにバグが あり、壊れた第1世代が 出来る。 2. その第1世代で字句解析 をコンパイルして、壊れ た第2世代が出来る。 20 -
3. 第2世代を動かすと、字句解析部分でメモリなどを壊している。 4. メモリなどが壊れた結果、第2世代の意味解析でセグフォが起き る。 構文解析 意味解析 トークン列(壊) 構文木(壊) ソースコード
字句解析(壊) セグフォ! 1. 実装していない機能があることに気づいて実装したり、16バイトアライメントを疑ったりとひと悶着あったのですが、割愛します。 21 -
memcmpが怪しい GDBでデバッグを続けると、 memcmp という標準ライブラリの関数を 呼び出した際にセグフォが起きていました。 さらに、 memcmp に渡している引数を確認すると、ヒープメモリに確 保しているはずのアドレスが 0xf7caf015
と、異様に短いことがわか りました。 メモリアドレスを処理するどこかで、64ビット必要なのに32ビット で計算してしまったのでしょう。意味解析より前の、どこかで。 1. 実は、GDBの出力を読み誤った結果、最初は memcmp ではなく strlen が原因だと思いこんでいたりしました。 2. この環境(x86_64, ArchLinux)では、正しいヒープ領域のアドレスは 0x611b3a3ca2a0 のように、16進数で12桁になります。しかし、今回の結果は8桁しかありません。 22 -
意味解析は 10cc の後半に位置する処理です。今回使ったポインタは 字句解析の箇所で生成したので、字句解析→意味解析のどこかで誤っ た処理が行われているとわかりました。 字句解析 構文解析 意味解析 コード生成 トークン列
構文木 構文木 ソースコード アセンブリ こんなふうに怪しい範囲が広いときは、皆さんどうするかおわかりで すね? 23 -
怪しい箇所を発見! cur = new_token(TK_SYMBOL, cur, p++, 1, file, line); このプログラムは正しいC言語のプログラムです。しかし、Cコンパ
イラを自作した人は分かるはずです。 インクリメントは怪しい と。 バグの匂いがプンプンします。 1. これを解いている際には、関数呼び出しとインクリメントが組み合わさったせいなのでは?と思っていました。実際は関数呼び出しは冤罪でした。 25 -
バグの原因 バグ : mov edi, [rax] 正常 : mov rdi,
[rax] アセンブリの命令が、 rdi レジスタ(64ビット)ではなく、 edi レジス タ(32ビット)を使っていました。これが原因で上位32ビットが消えて しまっていたのです。 たった1文字の違いで、8時間もデバッグをする羽目になりました。 さらに、前半の main.c のバグについても、この rdi と edi のバグが 原因になっていることがわかりました。 27