0x19f (Shinya Kato) の日報

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

自作Cコンパイラで Ken Thompson のログインハックを再現してみた

UNIX 開発者の一人である Ken Thompson が初期の UNIXバックドアを仕掛けていたと言われている通称 Thompson hack を自作Cコンパイラで再現してみました。 Thompson hack は UNIX のログイン処理のコンパイル時にバックドアを仕掛けるようなコンパイラを作り、さらにコンパイラソースコードからその痕跡を消し去るという神業です。

元ネタは Reflections on Trusting Trust という1983年に Ken Thompson が Dennis Ritchie と共にチューリング賞を受賞した際の記念公演です。 Ken Tohmpson はこの細工をしたコンパイラを配布したことはないと主張しているそうですが、このバックドアを利用したと見られる不審なログインがあったという報告もあったとのことで、実際にはベル研究所の外部に配布されていたのではないかとも言われているようです。 軽く調べただけなので真偽はわかりません。

今回の再現は GitHub 上で閲覧可能です、詳しく見てみたい方はどうぞ。 自作のCコンパイラMac では動かないので、実際に試してみたい方は Linux 環境でお願いします。

github.com

再現に用いるCコンパイラ

この再現では随所で自分自身のソースコードコンパイルする(セルフホスト)を行うので、セルフホストが可能なコンパイラを用いる必要があります。 加えて、Cコンパイラの内部的な処理とどういうアセンブリが出力されるのかを十分に理解している必要があります。

というわけで今回はセルフホスト可能な自作のCコンパイラを用いることにします。 最初に gcc で正常なコンパイラソースコードコンパイルして cc という自作コンパイラの実行ファイルを用意しておきます。 このCコンパイラC言語のプログラムを読んでアセンブリを出力します。 アセンブリを実行ファイルに変換する部分では gcc の力を借りています。

# gcc で自作コンパイラをコンパイル
$ make cc

ターゲットとするプログラム

以下のような login.c という簡単なログイン処理を今回はターゲットにします。 実際にはこんな簡単なはずはないんですが、そこは今回の本質ではないのでご容赦ください。

/* login.c */

int scanf(char *format, ...);
int printf(char *format, ...);
int strcmp(char *s1, char *s2);

int login(char *password) {
  if (strcmp(password, "my_password") == 0) {
    printf("successfully logined.\n");
  } else {
    printf("failed.\n");
  }
}

int main() {
  char password[32];
  printf("type password: ");
  scanf("%s", password);
  login(password);
}

入力された文字列が my_password であればログイン成功、そうでなければ失敗というプログラムです。 このプログラムを正常なコンパイラコンパイルして my_password でしかログインできないことを確認します。

# cc で login.c をコンパイル
$ make login
$ ./login
# my_password を入力
type password: my_password
successfully logined.
$ ./login
# you_are_hacked を入力
type password: you_are_hacked
failed.

今ログインに失敗した you_are_hacked というパスワードでログインできるようコンパイラに仕掛けをするのが今回のゴールです。

login 関数を別の処理に置き換えるコンパイラを作る

例えば、悪い人が you_are_hacked というパスワードでもログインできるようにするために login 関数を以下のように書き換えたとします (login_evil.c)。

/* login_evil.c */

int login(char *password) {
  if (strcmp(password, "my_password") == 0 ||
      strcmp(password, "you_are_hacked") == 0) {
    printf("successfully logined.\n");
  } else {
    printf("failed.\n");
  }
}

当然これでログインできるようになるわけですが、さすがにソースコードを見れば一発でバレてしまいます。 そこでこれををコンパイルしてできるアセンブリ (login_evil.s) をコンパイラのコード生成部分に埋め込んでしまいます。 関数定義の生成を行う関数 (gen.c の gen_func_def) を書き換えて login という関数名がきたら login_evil.s の中身を printf で出力するようにします (gen_func_def_evil.c)。

/* gen_func_def_evil.c */

void gen_func_def(Node *node) {

  /* login という関数がきたら */
  /* login_evil.s のアセンブリを吐き出す */
  if (strcmp(node->identifier, "login") == 0) {
    printf(" .text\n.XLC0:\n .string \"my\\137password\\000\"\n.XLC1:\n .string ......");
    return;
  }

  /* 正常なコンパイル処理 */
  ......
}

これと他のソースコードを合わせて gccコンパイルし cc_evil という実行ファイルを生成します。 cc_evil は login 関数を不正なアセンブリで置き換え you_are_hacked でのログインを可能にするコンパイラです。

# cc_evil を gcc でコンパイル
$ make cc_evil
# login.c を cc_evil でコンパイル
$ make login_by_evil
$ ./login_by_evil
# you_are_hacked でログインできる
type password: you_are_hacked
successfully logined.

当然 login.c にはなんの痕跡も残っていません。 cc_evil をバイナリで配布すればバックドアがバレる可能性は低いでしょう (現代なら普通にバレそうですが実際のところはどうなんでしょう?)。 しかし、この cc_evil で元の正常なコンパイラソースコードコンパイルして置き換えられると、それ以降はバックドアを仕込めなくなってしまいます。 かと言ってコンパイラソースコードを gen_func_def_evil.c のように書き換えたままでは、ソースコードを読まれていずれバレてしまいます。

さて、ここからが Thompson hack のヤバいところです。 Ken Thompson はこの login 関数を書き換える性質がセルフコンパイル時に受け継がれるような細工を施しソースコードから痕跡を完全に消し去ったのです。

コンパイラソースコードから痕跡を完全に消し去る

ソースコードから痕跡を完全に消し去るために Ken Thompson が用いたのはクワインです。 クワインというのは、自分自身のソースコードと全く同じ文字列を出力するプログラムのことです。 Reflections on Trusting Trust の中では self-reproducing program と呼ばれています。

例えば、C言語でのクワインは以下のようなものがあります。

int main() { char *s = "int main() { char *s = %c%s%c; printf(s, 34, s, 34); }"; printf(s, 34, s, 34); }

クワイン (プログラミング) - Wikipedia より

Thompson hack ではコンパイラ自身のプログラムが現れたら自分自身と全く同じコードを埋め込むという条件付きのクワインを使うことでソースコードから痕跡を消しつつ、セルフホストしても login を書き換える性質を引き継がせる仕組みになっています。

今回の再現ではアセンブリクワインを書いてこれを実現したいと思います。 アセンブリクワインの基本形は quine.s を参照してください。

まずは gen_func_def_very_evil.c というファイルを作り以下のようなプログラムを書いておきます。

/* gen_func_def_very_evil.c */

void gen_func_def(Node *node) {

  /* login という関数がきたら */
  /* login_evil.s のアセンブリを吐き出す */
  if (strcmp(node->identifier, "login") == 0) {
    printf(" .text\n.XLC0:\n .string \"my\\137password\\000\"\n.XLC1:\n .string ......");
    return;
  }

  /* printf("quine"); */
  /* と書かれているところを */
  /* アセンブリに変換した後で書き換える */
  if (strcmp(node->identifier, "gen_func_def") == 0) {
    printf("quine"); 
    return;
  }

  /* 正常なコンパイル処理 */
  ......
}

そしてこれをコンパイルして出来たアセンブリファイル (gen_func_def_very_evil.s) をクワインになるように書き換えます。 gen_func_def という関数が出てきたら自身と全く同じ文字列を出力するというアセンブリに書き換えたものが gen_func_def_very_evil_quine.s です。 あとは他のソースコードと合わせてコンパイルします。 これで何度セルフホストしても login 関数を書き換えるような性質が受け継がれる非常に邪悪なコンパイラのバイナリ (cc_very_evil) が手に入ります。

# gen_func_def_very_evil.s と他のソースコードを
# gcc でコンパイルして cc_very_evil を生成
$ make cc_very_evil

実際に cc_very_evil を使って正常なソースコードコンパイルしてできた実行ファイル (cc_hacked) を使って login.c をコンパイルしてみます。

# cc_very_evil で元の正常なソースコードをコンパイル
$ make cc_hacked
# cc_hacked で login.c をコンパイル
$ make login_by_hacked
$ ./login_by_hacked
# you_are_hacked でログインできる
type password: you_are_hacked
successfully logined.

you_are_hacked でログインに成功しました。 さらに cc_hacked でもう一度セルフホストしてできた実行ファイル (cc_hacked_hacked) で login.c をコンパイルしてみます。

# cc_hacked で元の正常なソースコードをコンパイル
$ make cc_hacked_hacked
# cc_hacked_hacked で login.c をコンパイル
$ make login_by_hacked_hacked
$ ./login_by_hacked_hacked
# you_are_hacked でログインできる
type password: you_are_hacked
successfully logined.

セルフホストをしても login.c を不正に書き換える性質が引き継がれているのが確認できます。 当然のごとく login.c のソースコードにもコンパイラソースコードにも痕跡は残っていません。 これが Thompson hack です。

このバイナリを配布したら、当時であれば様々な UNIX システムにログインができたかもしれません。 実際に Ken Thompson がそれをやっていたかどうかは僕にはわかりません。 僕が言えるのはただひとつ、こんなことを思いつく Ken Thompson は明らかに天才だということだけです。

まとめ

Thompson hack はソースコードに痕跡を残さずに特定のプログラムを好きに書き換えられるという驚くベきテクニックです。

もしかしたら既存のコンパイラは全てハックされていて、OSやディスアセンブラのようなセキュリティ的に重要なあらゆるプログラムが書き換えられていたりするのかもしれない............というのはさすがに陰謀論すぎですね。

セキュリティ・キャンプ 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 さんにはなんとお礼をしたら良いのかわかりません、本当に実りの多い時間をありがとうございました。

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

ICPC 2018国内予選に参加してきました

M1の@reminさん、B4の自分、B3の@9071tomatoくんの3人で、チームMohuhu UniversityとしてICPC 2018国内予選に参加しました。 なんとかA〜D問題を解いて全体で31位になることができたので、おそらく国内予選を突破できたはずです。

f:id:mizu0x19f:20180707193343p:plain

一応、問題一覧と順位表のリンクを貼っておきます。
問題一覧: All Problems
順位表: LiveSite

A問題:
n個の値が与えられるので、その平均以下の値の数を答える問題。 @reminが考察・実装。 最近の国内予選のA問題だと解きやすい方に入るのかなぁと。

B問題:
紙を横方向または縦方向に折る指示がいくつか与えられて、折った後に特定の場所に何枚紙が重なっているか答える問題。 自分が考察・実装。 パッと見ですごく解きたくない問題だったんですが、実際に解いてみるとものすごく解きたくない気持ちになりました。 少し手間取ったもののなんとか通せてよかったです。

C問題:
連続する正の整数の和がbになるような範囲のうち、範囲に含まれる数の個数が最大のものを答える問題。 @9071tomatoが最初読んでわからないようだったので一旦飛ばしてDを読んでもらいました。 自分もBを解き終えて問題を読んだのですが、なるほど確かにわからない。 昨年のC問題とかもっとずっと簡単だったのに......なんて思いつつ考察してました。 bが109程度であること、範囲の和が2乗で大きくなっていくことを考えると、何かしらがsqrt(109)に収まるんだろうなぁと話していたら、@reminが範囲の幅がsqrt(109)で抑えられることを見つけてくれました。 というわけで、Cは@reminに実装してもらいました。

D問題:
総当たり戦の対戦結果が途中まで埋められた表が与えられて、全チームの勝敗数が等しくなるような対戦結果は何通りあるかを答える問題。 チーム数が最大で9なので試合の数が9C2で36通り、全探索をしても236なので時間をかければ解けそうだし、適当に枝刈りすれば十分な速さで解けそうだなぁと思いました。 実際のところ最大ケースでも236通り試す必要はなくて、たぶん8C4 * 6C3 * 4C2 * 2C1 = 16800ぐらいになるのかな? @9071tomatoがいけそうだと言ってくれたので実装してもらいました。 @9701tomatoくんにnext_combination(next_permutationの組み合わせ版)を持ってないかと聞かれたのですが、奇跡的に持っていたので写経してもらいました。 何がいつどこで役に立つかわからないものですね。

E問題:
簡易版の浮動小数点を用いて加算をn回繰り返すプログラムの結果をシミュレーションしてくださいという問題。 nが最大で1018なのでダブリングだと思ったんですが、違いました。 実装してからダブリングだとn回加算で起きる誤差が再現できないことに気づきました。 実装する前に@reminから指摘があったとの説もありますが......。 実はサンプルの最後のケースが最大ケースになっているらしく、指数部が増えるタイミングがたかだか50回程度であることがわかるみたいです。 あとは指数が増えるところまでまとめて足すというのを50回ぐらい繰り返せばいいみたいです。 (まだ実装できてないですが......)

F〜Hは一応問題には目を通したもののどうしたらいいのかさっぱりだったので諦めました。

ちなみに、学内1位のWAsedACが選抜チーム内で14位、Mohuhu Universityが学内2位で選抜チーム内で20位、学内3位のWAsita Universityが選抜チーム内で25位なので、学内から3チームアジア地区大会に出場も夢じゃなくなってきてますね。 (学内から3チーム出場するには20位以内に入る必要があるので。)

とまぁ、なんとかアジア地区大会に出場できそうです。 国内予選を通過されたチームのみなさん、横浜でお会いできるのを楽しみにしています。

ちなみに、これは予選終了後に学内の参加者で集まって寿司を食べている様子です。 寿司が食べたいみなさん、来年はぜひICPCに参加しましょう。

(ところでなぜ僕らはコンテストが始まる前にフビライ・ハンとエビフライゴハンの話をしていたんですかね?)

Cコンパイラ自作チャレンジ(その2・プリプロセッサ編)

字句解析に続いてプリプロセッサ

前回は字句解析器を作るところまでの話でした。

0x19f.hatenablog.com

今回はプリプロセッサのお話です。

先に言い訳をしておくと、WG14/N1570 Committee Draftを読みながらザクザクと実装を進めてそれっぽいマクロ展開などはできるようになってきましたが、まだ完全に作りきれてはいないです。 加えてだんだん自分でも何を書いているのかよくわからなくなってきたので、少し整理しながら書き直したいと思っています。 というわけで、まだ具体的な実装はGitHubリポジトリにpushしてないです。

そんな感じなので、一度プリプロセッサの挙動を書き起こして整理したいと思います。 僕の備忘録的な色が強いです。

プリプロセッサの概要

プリプロセッサというと、#include#defineなどがパッと思い浮かぶんじゃないかと思います。 これらはプリプロセッシング・ディレクティブと呼ばれます。

ディレクティブとマクロの展開は字句解析で得られたトークン列に対して行われます。 プリプロセッシングによって得られたトークン列は型の特定や文字列の結合などの処理が行われて構文解析されていきます。

ディレクティブの一覧は以下の通りです。

  • Conditional inclusion: #if, #ifdef, #ifndef, #elif, #else, #endif
  • Source file inclusion: #include
  • Macro replacement: #define, #undef
  • Line control: #line
  • Error directive: #error
  • Pragma directive: #pragma

#line__LINE__マクロとか__FILE__マクロとかを制御するためのものっぽい。 #errorはこのディレクティブを読むと後ろに指定されたエラーメッセージを出してくれるようです。 #pragmaコンパイラ固有・環境固有の機能とかを追加するのに使われるディレクティブという認識だけど、よくわからない。

規格に書かれているディレクティブはこれで全てなので、この他は各コンパイラ拡張機能ということになるんですかね。

ここからはプリプロセッシングの中心的な機能となるMacro replacementとSource file inclusion, Conditional inclusionについて書いていこうと思います。

Macro replacement

マクロの定義

#defineディレクティブでマクロを定義できます。

マクロの定義には2種類あって、オブジェクト型のマクロ(object-like macro)と関数型のマクロ(function-like macro)のようなものがあります。 関数型のマクロは可変長引数みたいなものを受け取ることもできて、その場合は#define function(a, b, ...)のような宣言の仕方になります。

#define identifier replacement-list
#define identifier( identifier-list ) replacement-list
#define identifier( ... ) replacement-list
#define identifier( identifier-list , ... ) replacement-list

なお、混乱を避けるために以下ではパラメータと引数を明確に区別して使います。 パラメータと言った場合は、マクロ宣言の()の間に含まれる識別子のことを指します。 引数と言った場合には、マクロ呼び出しの()の間に含まれるトークン列のことを指します。 要するにパラメータは宣言側のこと、引数は呼び出し側のことと思ってください。

マクロの置換

テキスト中にオブジェクト型のマクロの名前が出てきた場合には、対応するreplacement-listでそれを置き換えます。 置き換えが終わったら、置き換えられた部分を再度スキャンしてマクロを再帰的に展開していきます。

テキスト中に後ろに(が続く関数型のマクロの名前が出てきた場合には、対応する括弧を除いた次の)までを以下の手順で置き換えます。

  1. 1番外側の()の内側のトークン列を,で区切って関数型マクロの引数とする
    ただし、対応する括弧の中にある,を除く
  2. replacement-list中に現れるパラメータを引数で置換します
    ただし、パラメータの前に#トークンがある場合と前後に##トークンがある場合を除きます
    また、置き換えを行う前に引数に含まれるすべてのマクロを展開します
  3. #トークンの後ろに続くパラメータは文字列化されます
    ##トークンの前後のトークンは連結されます
  4. 置き換えられた部分を再スキャンしてマクロを再帰的に展開していきます

パラメータに...を持つ関数型マクロの呼び出しの際はパラメータの数以上の引数を渡すことができます。 その場合、余分な引数の部分は,を含めて__VA_ARGS__というパラメータに対応付けられたように振舞います。

# 演算子について

#は後ろに続くパラメータを引数を文字列化したもので置き換えるという演算子です。

引数の先頭と末尾の空白文字は取り除かれます。 それ以外は元のトークン列のスペリングが維持されたままひとつの文字列に変換されます。 例外として、トークン列中に現れる"\のみエスケープされます。

## 演算子について

##は前後のトークン列を連結するという演算子です。 関数型マクロだけでなくオブジェクト型のマクロでも使うことができます。

引数が空のトークン列である場合は、placemarkerという特殊なトークンで置き換えます。 トークンを連結する際、片方がplacemarkerである場合は、その結果はもう片方のトークンになります。 両方がplacemarkerの場合は、結果もplacemarkerとなります。 placemarkerは再スキャンの前に全て取り除かれます。

マクロの再帰的な展開

一通り上記の手順でマクロを展開し終えたら、置換された部分を再度スキャンして再帰的にマクロを展開します。 再帰的な展開の途中ですでに展開済みのマクロ名に出会った場合は、展開を行いません。

実装する上では、マクロ展開を終えた後に展開したマクロにフラグを立てておいて、フラグが立っているマクロを無視しながら再スキャンを行い、再スキャンが終わったらフラグを折るという感じで問題ないと思います。

この再帰的な展開を図にしてみたんですが、あんまりわかりやすくはなさそうですね...

f:id:mizu0x19f:20180528072317p:plain

Source file inclusion

#includeディレクティブでソースファイルのインクルードができます。

#include <h-char-sequence>
#include "q-char-sequence"

厄介なのが#includeの後ろに続くのが上記の2つ以外のトークン列の場合です。 この場合、トークン列を通常のテキストと同様にマクロ展開し、ひとつのヘッダー名に変換し、それが上記の2パターンに当てはまればインクルードを行います。

Conditional inclusion

#ifディレクティブなどから次の#endif#elif#elseまでが出てくるまでのことをグループ(group)と規格では呼んでいたので、以下でもそれに習ってグループという言葉を使っていきます。

#ifdef, #ifndefはマクロの定義状態によってどのグループを読むかを決めるディレクティブです。 これはおそらく実装するのも難しくないです。

#if, #elsifがやばいです。 なぜやばいのかというと、実は#ifの後に続く条件は整数定数式として評価されるからです。 この時点で結構重めの構文解析が必要です。

さらにただの整数定数式ではなく、defined演算子という後に続く識別子がマクロとして定義されているかいないかによって1/0に置き換えられる演算子があったり、マクロの展開も行われます。 なので、defined(macro) + 3 >= 4のようなトークン列を処理する必要が出てきます。

具体的には、#if#elifの後ろに続くトークン列は以下のようにして真か偽か評価されます。

  1. defined演算子がついている識別子を除いて、マクロを展開する
  2. defined演算子を0/1に置き換える
  3. 残っている識別子を全てpp-numberの0で置き換え、トークン列をtoken(pp-tokenではなく)に変換する
  4. 整数定数式として評価する
  5. 得られた結果が0でなければ真、0なら偽

else, endifはあんまりちゃんと読んでないけれど、見たとおりだと思います。

一応、読み込まれなかったグループはマクロの展開とかディレクティブの評価とかをせずに読み飛ばすっぽい?

次こそプリプロセッサ

だいたいの挙動は理解できたし実装のイメージもつかめたので、もう少しいい感じにプリプロセッサを作り直します。 空白を読み飛ばす処理が面倒でつらいなぁという気持ちになったので、そこはうまくやりたいなぁと。

Cコンパイラ自作チャレンジ(その1・字句解析編)

2018/06/05追記

続き書きました。

0x19f.hatenablog.com

Cコンパイラの自作に挑戦してみる

C言語のプログラムを書き始めたのはたしか僕が中学生か高校生の頃でした。 あの頃からなんとな〜く「プログラミング言語というのはどうやってできているんだろう」と思っていました。 どう考えてもあんな複雑なルールを持ったプログラムの構文を解釈するなんて無理やろ、既存のコンパイラはどうしているんだと思わずにいられませんでした。

そんな疑問が解決されたのは、大学に入って言語処理系の講義を受けた時でした。 字句解析や構文解析について教わりとても感動しました。 最適化の話はあんまり理解できませんでしたが。

というわけで、今ならそれなりにコンパイラの自作ができそうな気がするのでCコンパイラの自作に挑戦してみたいと思います。 最近は言語処理系の自作が流行っているみたい(?)ですし。

作るにあたって名前があったほうがいいなと思ったのですが、だいたいCコンパイラって「なんとかcc」みたいな名前がついているイメージがあるので、僕のイニシャルをとってskccという名前をつけることにします。

github.com

C言語の規格

C言語の正式な規格はANSIやISOから購入する必要があるみたいなのですが、Committee Draftであれば自由に閲覧することができます。 Committee Draftは最終決定された規格と違う部分もあるかもしれないのですが、どれくらい違うものなんですかね?

今回はC11のCommittee Draftに沿ってコンパイラを作っていこうと思います。

コンパイルの処理の流れ

規格の5.1.1.2 Translation phasesに処理の流れが8つのフェーズに分かれて記述されています。 ざっくり要約してまとめると以下のような感じになります。

  1. トライグラフを置換する。
  2. 改行の直前にあるバックスラッシュを削除して前後の行を1つにつなげる。
  3. 字句解析をしてソースファイルをpreprocessing-tokenに分解する。
  4. プリプロセッサの実行、マクロを展開、_Pragmaの実行を行う。
  5. 文字定数と文字列リテラルの文字を対応する実行環境用に変換する。
  6. 隣接する文字列リテラルを連結する。
  7. preprocessing-tokentokenに変換、構文解析をする。
  8. あんまり読んでないですが、リンクの話をしているっぽそう(?)。

フェーズ2で行われる処理は、複数行にわたる#defineなどの行末に置かれるバックスラッシュの処理ですね。

preprocessing-tokenはフェーズ3〜6で使われる字句要素、tokenはフェーズ7の構文解析で使われる字句要素です。 ふたつは若干内容が異なっている点に注意です。 イメージとしては、preprocessing-tokenはざっくりとしたトークン分けで、プリプロセッシングが行われた後により細くtokenに分けるという感じです。 例えば、数値は整数と浮動小数点をすべて含むpp-numberという字句要素に分解され、プリプロセッシングの後で整数と浮動小数点に分けられて値と型が解析されます。 余談ですが、pp-number0xe-8のようなinteger-constantでもfloating-constantでもないトークンを含んでおり、これらは値と型を解析するタイミングでエラーとすればよさそうです。

preprocessing-tokenの字句解析器

まずはフェーズ3の処理をする字句解析器を作っていきます。

6.4 Lexical elementsにpreprocessing-tokenの構文が書かれています。 トークンの種類はheader-name, identifier, pp-number, character-constant, string-literal, punctuator, これらのいずれにもマッチしない1文字です。

入力文字列のうちで構文に一致する最長の箇所までがひとつのトークンとなります。 例えば、x+++++yx, ++, +, ++, yと区切ると正しいプログラムになりますが、この規則に則って字句解析が行われるのでx, ++, ++, +, yと区切られます。

字句解析器を作る際にはflexなどのツールを利用することが多いと思うのですが、今回はそういった便利なものを使わずに頑張ります。 というわけで、基本的にはpreprocessing-tokenの構文を手でオートマトンに変換し、1文字ずつ読み取りながらどのトークンにマッチするのか調べていきます。

このオートマトンを作る部分が結構大変で苦労しました。 例えば、文字定数を受理するオートマトンは以下のような感じになるんですが、初めて見るプレフィックスやエスケープシーケンスが意外と多くその辺で手こずりました。

f:id:mizu0x19f:20180506204036p:plain
文字定数を受理するオートマトン

その他の種類のトークンを受理するオートマトンGitHubに置いておくので気になる方はどうぞ。 間違いがあれば指摘していただけると助かります。

skcc/diagrams at c85779b7150b75f8aef604f56dc7a7950633c479 · ShinyaKato/skcc · GitHub

あとはこの図を見ながらひたすらif文を書いていきます。 こんな感じ。

skcc/lex.c at 6a7ed86c64717b31517f5a5633fa7fbc5b784a43 · ShinyaKato/skcc · GitHub

また、これは自分の解釈があってるか自信がないのですが、最長の一致箇所を見るので途中でどこにも遷移できない場合は最後に通った受理状態まで戻ることになると思われます。 例えば、...(可変引数のアレ)を受理する途中にドットふたつという状態があるのですが、この状態は受理状態になりません。 なので仮に..というドットがふたつ連続した入力が与えられた場合は、最後に通った受理状態であるドットひとつまで戻って..という形に分割されます。 もし途中でひとつも受理状態を通っていなければ、先頭の1文字をどのトークンにもマッチしない文字としてトークンにします。 規格をよく読むと、"'がこのような1文字のトークンとして切り出された場合の挙動は未定義とされています。 このような"'が現れるのはクォーテーションの間に改行が入る場合やエスケープシーケンスが不正な場合ぐらいだと思いますが。

もう一点忘れないように書いておくと、header-nameは行頭の#, defineの後に続く場合にのみ認識されます。 すなわち、字句解析器は文脈に依存します。 正直かなり衝撃的だったのですが、規格にもそう書いてあるので仕方ないですね。

次はプリプロセッサ

次はプリプロセッサを作っていきたいと思います。 といってもある程度サボって構文解析に進んでいくつもりではありますが。 字句解析とかプリプロセッサとかあんまりTwitter映えしないし。

大学1年から大学3年までの時間割をまとめておく

ちょくちょく「3年の時間割ってどんな感じですか?」みたいなことを後輩に聞かれるので、この際全部まとめて残しておくことにした。

一応説明しておくと、早大理工は基幹理工学部先進理工学部創造理工学部の3つの学部に分かれている。 僕が所属しているのは基幹理工学部なので、1年の時はその時間割になる(細かいことをいうと、学系2だった)。 さらに、基幹理工学部は2年から数学科・応用数理学科・機械航空学科・電子物理システム学科・情報理工学科・情報通信学科・表現工学科に分かれる。 僕は情報理工学科なので、2年以降はその時間割になる。 なお、僕が大学に入学したのは2015年度だった。

まとめると、こういうことになる。

  • 1年: 2015年度の基幹理工学部(学系2)の時間割
  • 2年: 2016年度の情報理工学科の時間割
  • 3年: 2017年度の情報理工学科の時間割

後輩たちの参考になればよいけれど、僕の頃とカリキュラムが異なるかもしれないのでその辺りは注意していただけると。

1年

f:id:mizu0x19f:20180228001612p:plainf:id:mizu0x19f:20180228001643p:plain
1年春学期 / 1年秋学期

1年の時はほとんど理系の基礎みたいな科目。 この辺は全部必修な上に、時間割の選択権もないので言及することはなし。

ピンク色は教養科目みたいなやつ。 おもしろかったけれど、成績は微妙だった。

2年

f:id:mizu0x19f:20180228001701p:plainf:id:mizu0x19f:20180228001718p:plain
2年春学期 / 2年秋学期

春学期の方が色ついてなくて見辛いですがお許しを。

2年から情報理工の専門必修が入ってくる。 前期だと回ロリA・プロA・ロリ回路・実験A・情報数学A・アルゴリAが、後期だとアーキA・電子回路・情報数学B・実験B・アルゴリBが必修。 他はだいたい専門の選択か基幹理工共通の数学科目。 時間割の中に1年生の必修のCプロが入っているが、これは再履修とかではなくTAをしてただけ。

前期がかなりしんどかった記憶があるが、後期は人によってはそんなにしんどそうにしてなかった印象。 しんどいけれど、2年のうちに選択の単位を稼ぐと3年以降が楽になる。 やっぱり、実験のレポートがつらかった(共振回路とか共振回路とか共振回路とか)。

3年

f:id:mizu0x19f:20180228001753p:plainf:id:mizu0x19f:20180228001740p:plain
3年春学期 / 3年秋学期

3年になるとほとんど専門必修や専門選択になる。 前期だとプロB・OSA・情ネツA・ソフ工A・実験B・言語処理系、後期だとDB・プロ言・プロC・アーキB・実験Cが必修。 他は選択だった。 必修の数自体は少ないので選択の単位数さえ取れば結構講義は少なめ。

僕は必修以外も無意味にたくさん講義を取ったけれど、講義の難易度も上がり、成績を落とす要因になりかねないので個人的にはあまりオススメしない。 もちろん、興味があれば構わずに取れば良いと思うけれど。

あと、春学期の火曜日が1〜6限までだったけれど、正直かなりしんどかった。 1〜5でもしんどいんだから当然だとは思う。

ちなみに、3年の必修は個人的にはおもしろいものが多かった。 なんていうか「こういうのが勉強したくて大学に来たんだよなぁ」という感じ。 講義以外で勉強したことの方が多いような気もするけれど、興味を持つきっかけとしては非常にありがたかった。

まとめ

こんな感じで3年分の時間割をまとめてみたけれど、誰かの役に立ったらいいなぁと。

山本一成さんの「エレファントな解法」に対抗して動的計画法による「エレガントな解法」を考えてみた

エレファントな解法(?)

先日Ponanza開発者の山本一成さんがブログでこのような記事を書いておられました.

note.mu

この記事の中では以下の問いが投げかけられています.

問. コインを100回投げて表か裏が10回連続で出る確率は?

山本さんのブログでは「エレファントな解法」としてモンテカルロ法を用いた力任せの解法が紹介されています. つまりは, 乱数を使って100回コインを投げるというシミュレーションを何度も繰り返して条件を満たす確率を近似的に求めるというわけです. この方法ならきちんと確率を求めることができなくても, それなりに確率を正しく求められます. 困った時の最終手段としては非常に便利だと思います.

ちなみに, こういった方法が「エレファントな解法」と呼ばれているのは初めて知りました.

エレガントな解法

「エレファントな解法」のことは一旦置いておいて, 山本さんがエレガントな解法について「私は正直解ける気がしません」と言っておられたのが少し気になりました. 競プロerならぱっと見で「動的計画法で解けそう?」と感じた人も多いんじゃないでしょうか, 僕もそう感じました.

というわけで, この問題を動的計画法(DP)で解いてみたいと思います.

DPで解いてみる

先に断っておくと, 解いてみてから気づいたのですがちょっと冗長なDPをしています. あと, 答えはあったものの, 若干怪しいところがあります(おい).

基本的な考え方

DPそのものの説明はいろいろと調べてもらうのが早いと思うのですが, 僕は「コインの投げ方って2N通りあるけれど, 実はそんなに場合分けしなくても"何回コインを投げて何回連続で同じ面が出てるか"で場合分けすれば十分じゃない?」というものだと思ってます.

例えば, 10回コインを投げて最後に表が3回連続で出るような投げ方って26通りありますが, 今回の問題では最初の6回までに表裏どっちが出たかって知らなくても答えは出せます.

というわけで, これらをまとめて計算して, さらに上手に前の計算結果を利用していくことで計算量を落とすことができます.

解法

まず, コインを投げる回数をN, 求めたい確率の連続回数をMとします. そして, 以下のようなDPを考えます.

dp[i][j][k][l]:
i回コインを投げた時に, 最後にj回連続で(k = 0: 表, 1: 裏)が出て, 条件を(l = 0: 満たしていない, 1: 満たしている)確率

遷移に関しては, (k, l)の4パターンについてそれぞれ表が出た場合と裏が出た場合を考えます. 表が連続している場合に限って説明します.

まだ条件を満たしていいない場合は, 表が出たら連続回数を1増やし裏が出た場合は連続回数を1に戻してあげます. このとき, 表がM回以上連続していたらl = 1, つまり条件をすでに満たした状態に遷移してあげます.

すでに条件を満たしている場合も, 表が出たら連続回数を1増やし裏が出た場合は連続回数を1に戻してあげます.

裏が連続している場合もほぼ同様です.

最終的な答えは, N回コインを投げて最後の連続数とコインの裏表に関係なく条件を満たしている確率です. つまり, dp[N][j][k][1] (0 <= j < N, k = 0, 1)の和が答えです.

というわけで, O(N2)の時間計算量で答えが出せます.

実装

これをC++で書いてみると以下のようになります.

#include <cstdio>

int main(void) {
  const int N = 100, M = 10; // コインを投げる回数, 連続する回数
  const double P = 0.5;      // 表が出る確率

  // dp[i][j][k][l]:
  //   i回コインを投げて,
  //   最後のj回連続して(k = 0: 表, 1: 裏)が出て,
  //   (l = 0 : まだ条件を満たしていない, 1: すでに条件を満たしている)確率
  double dp[N + 1][N + 1][2][2];
  for(int i = 0; i < N + 1; i++) {
    for(int j = 0; j < N + 1; j++) {
      dp[i][j][0][0] = 0;
      dp[i][j][0][1] = 0;
      dp[i][j][1][0] = 0;
      dp[i][j][1][1] = 0;
    }
  }
  dp[0][0][0][0] = P;
  dp[0][0][1][0] = (1 - P);

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < i + 1; j++) {

      // (k, l) = (0, 0): 表が連続, 条件を満たしてない
      dp[i + 1][j + 1][0][j + 1 >= M] += dp[i][j][0][0] * P;
      dp[i + 1][1][1][0] += dp[i][j][0][0] * (1 - P);

      // (k, l) = (0, 1): 表が連続, 条件を満たした
      dp[i + 1][j + 1][0][1] += dp[i][j][0][1] * P;
      dp[i + 1][1][1][1] += dp[i][j][0][1] * (1 - P);

      // (k, l) = (1, 0): 裏が連続, 条件を満たしてない
      dp[i + 1][1][0][0] += dp[i][j][1][0] * P;
      dp[i + 1][j + 1][1][j + 1 >= M] += dp[i][j][1][0] * (1 - P);

      // (k, l) = (1, 1): 裏が連続, 条件を満たした
      dp[i + 1][1][0][1] += dp[i][j][1][1] * P;
      dp[i + 1][j + 1][1][1] += dp[i][j][1][1] * (1 - P);
    }
  }

  // 最終的な答えは, dp[N][j][k][1] (0 <= j < N, k = 0, 1)の和
  double ans = 0;
  for(int j = 0; j < N + 1; j++) {
    ans += dp[N][j][0][1];
    ans += dp[N][j][1][1];
  }
  printf("%.15lf\n", ans);
}

実行した結果「コインを100回投げて表か裏が10回連続で出る確率」は0.086659044348362となりました. 山本さんがブログの中で知人の数学者の方に「エレガントな解法」で計算してもらったという値と一致してます, やったね.

まとめ

というわけで, こんな感じでこの問題は答えが出せます. これぐらいならまだなんとか確率求められますが, 難しくなると圧倒的にエレファントな解法に分がありそうですね(無理やりまとめた).

ちなみに, 頑張るとO(NM)で答え出せるはずです. この解法はchokudaiさんが書いておられますね......プログラムみじかw