0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

セキュリティ・キャンプ 2018 (Cコンパイラ自作ゼミ) に参加してきました

8/14〜8/18の期間でセキュリティ・キャンプ2018のCコンパイラ自作ゼミに参加させていただきました。 なんと4泊5日で1日3食が用意されるというQoLの高い環境で、集中して開発ができ最高でした。

Cコンパイラ自作ゼミは「セルフホスト可能なCコンパイラ」の開発を目標にコンパイラを自作するという内容でした。 講師の @rui134 さんと @hikalium (実は大学の同期です！) 、チューターの @retrage01 さんがどんな質問にも建設的に答えをくださって、非常に多くの学びが得られました。 最終的には自作Cコンパイラのセルフホストも達成でき、自分の技術スキルを何段階も成長させられたと感じています。

以下のリポジトリが今回のセキュリティ・キャンプの成果物です。

github.com

前置きが長くなりましたが、この記事では以下のことについて書きたいと思います。

来年以降もCコンパイラ自作ゼミが開講された時に「どんなことをするんだろう？」と疑問に思った方の参考になれば幸いです。

ちなみに、ここで開発したCコンパイラで Ken Thompson のログインハックを再現してみた話もあるので、よろしければどうぞ。 本当はセキュリティ・キャンプの会場でデモをしてみたかったんですが、ちょっと間に合いませんでした。

0x19f.hatenablog.com

Cコンパイラ自作ゼミに参加して学んだこと

このゼミに参加する前に何冊か言語処理系を自作してみようという感じの本を読んだ作ってみたことがあるのですが、題材がオリジナルの言語であることが多くなんだか味気なさを感じていました。 完全な自作言語だと実装の難しいところは作らないという選択ができてしまうのが原因じゃないかと感じ、自分でCコンパイラを自作しようと構想を練っていた矢先にこのゼミの存在を知り応募することに決めました。 このゼミのコンセプトはまさに自分が求めていたものでした。 結果的にひとりで作るよりも遥かに多くのことが学べたと思っています。

C言語の基本的なコーディングや再帰下降型の構文解析テクニックはもちろんのこと、アセンブリ、スタックのレイアウトなど普段あまり意識しないコンパイラというブラックボックスの中身についての理解も深まりました。 加えて「大きなプログラムをインクリメンタルに開発する」というコンパイラに限らずどんなものにでも適応できる考え方を身につけることができました。

このCコンパイラ自作ゼミは想像以上に素晴らしい内容でした。 来年のセキュリティ・キャンプでも同様のゼミがあるのであれば、かなりオススメです。 セキュリティっぽさが前面に押し出されていない内容なので、単純に自分の技術力を上げたいという人にもちょうど良いと思います。

Cコンパイラのセルフホストまでの道のり

7月の頭にキックオフミーティングがあり、そこから開発が始まりました。 1番最初のコミットはこんな感じです。

#include <stdio.h>

int main(void) {
  int n;
  scanf("%d", &n);

  printf("  .global main\n");
  printf("main:\n");
  printf("  mov $%d, %%eax\n", n);
  printf("  ret\n");

  return 0;
}

標準入力から1つ数字を読んでその数を戻り値として返す main 関数をアセンブリとして出力するだけです。 ここからだんだんと機能を足してC言語に近づけていきます。

まずは式のコンパイルからです。 +, - 演算子を足し、*, / 演算子を足し、比較演算子(==, !=, <, >, <=, >=)を足し......という感じでだんだん式のコンパイルをできるようにしていきます。 いくつか演算子がコンパイルできるようになってきたころのコードが以下のような感じです。

seccamp2018/main.c at 22c97fb89eb04e28ab2add96f0c2022ed88e3f46 · ShinyaKato/seccamp2018 · GitHub

ここからさらに以下のような機能を足していきます。 コミットのハイライトを見ていただくとだんだんコードが増えて機能も増えていってるのがなんとなくわかると思います。 ちなみに、機能によっては C11 の言語仕様よりも大幅に簡易化して実装しています。 最初から作り込みすぎないのが重要です。

このあたりまでできてくると、Nクイーン問題のソルバがコンパイルできたり、自分自身のソースコードの一部のファイルがコンパイルできるようになってきます。 そして後述するミスコンパイルのバグを直し、簡単なプリプロセッサを足し、最後にシステムのヘッダを自前のものに置き換えてセルフホストが可能になりました。

Add self compile script · ShinyaKato/seccamp2018@d040385 · GitHub

セルフホスト可能と言っても、浮動小数点がなかったり整数リテラルも10進しかなかったりプリプロセッサが関数マクロを展開できなかったりと足りない機能はまだまだたくさんあります。 逆に言うと、セルフホスト可能なコンパイラに必要な機能は以外と少ないという見方もできます。 こういった機能も今後細々と足していこうかなと思っています。

ちなみに、最終的なコードの行数は3600行程度でした。 3600行ならCコンパイラのセルフホストも結構現実的に思えてくるんじゃないでしょうか？

ミスコンパイルに悩まされた話

セルフホストが目前になってくると結構バグが見つかるようになってきます。 というのも一部のファイルがコンパイルできるようになると、残りのファイルを gcc でコンパイルしてリンクする部分セルフホストみたいなことができるようになるのですが、この出来上がったコンパイラでテストが通らないんですね。 図にするとこんな感じです。

f:id:mizu0x19f:20180820002008p:plain
自作コンパイラで自分自身をコンパイルするイメージ図

このデバッグはかなり困難を極めました。 自作のコンパイラはデバッグ情報を出力しないので gdb でも簡単なデバッグしかできません。 さらに、第2世代コンパイラのどこがおかしなコードを生成しているのかを調べてもそこにバグがあるわけではなく、その部分をコンパイルした第1世代のコンパイラにバグがあるわけです。 デバッグしているうちにだんだんと自分が何をしているのかわからなくなるレベルです。

1つ目のバグは関数呼び出しの際に呼び出された側の関数で bool 型の引数をメモリにストアし忘れていたのが原因でした。 これによって、スタックの上にもともと残っていたゴミを読んでたまたまプログラムが動いているという状態でした。

デバッグ中に gcc と自作コンパイラでコンパイルする部分を細かく分けて原因を二分探索してみたところ、ある一行だけを gcc でコンパイルすると動くということが判明しました。 さらにこの1行だけを自作コンパイラでコンパイルし冗長な命令をしていくと、push, pop 命令を削除すると動くという奇妙な現状が起きました。 結局1日かけても原因が見つけられず、最終的にソースコードを眺めてエスパーで特定しました。 push, pop を削除すると動くのは、読み込んでいるスタック上のゴミの値が変わったことによるものでした。

2つ目のバグは x86-64 の ABIで定められている関数呼び出し時のスタックポインタの16バイト整列が三項演算子を使うとずれるというものでした。

これも結局エスパーで原因を特定したのですが gdb で見てみると vfprintf 関数でアラインメントがずれてセグフォしているっぽかったので、スタック周りがバグっていることはわかりやすかったです。 加えて、三項演算子を if 文に置き換えるとテストが通るので、原因はかなり絞りやすかったです。

ほとんどのバグというのは局所的なもので原因は近くにあるらしいのですが、コンパイラのバグというのは奇妙なバグり方をするため見つけるのが非常に難しいです。 そういった貴重な経験(？)ができるのもコンパイラ自作の面白いところだと思います。

まとめ

今回のセキュリティ・キャンプでCコンパイラの自作をしたことは非常に良い経験となりました。 何より「大きなプログラムでも少しずつ機能を足していけば良い」ことの強い裏付けになったと思っています。

今ではCコンパイラの自作は時間と気力と正しいロードマップがあればかなり実現可能だと感じています。 もちろんこれは正しいロードマップがあるからなのですが、これについては講師の Rui さんがCコンパイラの自作本を鋭意執筆中(？)のようなので、いずれいろんな人が自作Cコンパイラに気軽に挑戦できるようになるんじゃないかと楽しみにしています。

最後になりますが、セキュリティ・キャンプの講師、チューター、運営のみなさん、5日間本当にありがとうございました。 特にCコンパイラゼミの講師をしてくださった Rui さん、hikalium、チューターの retrage01 さんにはなんとお礼をしたら良いのかわかりません、本当に実りの多い時間をありがとうございました。

そして参加者のみなさん、またいつかどこかでお会いできるのを楽しみにしています。 僕はセキュリティ専門ではなく普通に開発の仕事をしている可能性が高いのでセキュアなソフトウェアを作るためにぜひみなさんの力を貸して欲しいです、よろしくお願いします。