【C言語】引数なしの関数には void を書いた方がよいという話

C言語で引数なしの関数を書くときに void を書かないのと書くのとで挙動が違うなんて話を聞いたことはないでしょうか？ つまり void func() {} と void func(void) {} で挙動が違うという話ですね。 自分も話だけ聞いたことがあったものの2つがどう違うのかはわかっていなかったため、C言語の規格を読みながら何が違うのかを調べてみました。 結果だけ述べると、この2つの書き方は同じように見えて実は明確な違いがあり、引数がない関数を定義/宣言する場合には後者を使うのが適切です。 とは言え、2つの書き方で違いがあるとかほんとかよ？と思う方もいると思うので、まずはこの二つがどう違うのか見ていきましょう。

2つの関数の書き方の違い

早速ですが、以下のプログラムを見てみましょう。

// func_empty.c

void func() {}

int main(void) {
  func(1, 2, 3);
  return 0;
}

このプログラムでは void func() {} と定義した関数に対して main 関数から3つの引数を渡して呼び出しを行なっています。 おそらく多くの方はこのプログラムを見てコンパイルの結果はエラーになると予想するでしょう。 ところが、実際にコンパイルしてみると驚くべき結果が得られます。

$ gcc -std=c11 -Wall --pedantic-errors func_empty.c

なんと、エラーにならずコンパイルできてしまいました。 C言語の規格(C11)に沿った挙動にするためのオプションも指定しているので gcc の拡張機能がこの結果を引き起こしている訳ではなさそうです。 不思議な挙動ですね......

一方で、C言語では引数の括弧の中に void を書くことで明示的に引数を受け付けないことを示すこともできます。 int main(void) { … } の void はまさにこの void です。

先ほどの func_empty.c の func の定義に void を足してみましょう。

// func_void.c

void func(void) {}

int main(void) {
  func(1, 2, 3);
  return 0;
}

これを先ほどと同様にコンパイルしてみます。

$ gcc -std=c11 -Wall --pedantic-errors func_void.c
func_void.c: In function 'main':
func_void.c:4:3: error: too many arguments to function 'func'
   func(1, 2, 3);
   ^~~~
func_void.c:1:6: note: declared here
 void func(void) {}
      ^~~~

こちらは期待していた通り「引数が多すぎる」というエラーが出ます。 謎ですねぇ......

関数引数の括弧の中に void を書かないのと書いておくのではこのような挙動の違い、すなわち関数の呼び出しの時に引数がチェックされるか否かという違いがでます。 前者では呼び出し時に引数の数がチェックされません。 そのため func_empty.c では func にいくら引数が渡されていてもエラーになりません。 一方で、後者では呼び出し時に引数のチェックが行われます。 その結果、上に示したようなエラーが出てコンパイルに失敗します。

関数の引数がないときは void を書いておく方が安全

上記のような違いが出るため、関数の引数がないときは void を書いておくのがベターです。

例えば、セキュアコーディングのスタンダードの中でも void を書くことが推奨されているようです。

DCL20-C. 引数を受け付けない関数の場合も必ず void を指定する

ちなみに『プログラミング言語C』(いわゆるK&R)の第二版の中では以下のように書かれています。

古いCプログラムとの互換性のために互換性のために、標準規格では、空にリストは旧式の宣言として扱い、引数リストのチェックは一切やらないことになっている。 リストが明らかに空であるときには、予約語 void を使うべきである。 (p.41)

また、以下のようにも書かれています。

double atof(); のように、関数の宣言が引数を含まないときには、この atof の引数については何も仮定しないものと受け取られ、すべてのパラメータ・チェック機能はオフにされる。 空の引数リストが許される特別な理由は、古いCプログラムを新しいコンパイラでコンパイルできるようにすることにある。 しかし、新しいプログラムでこれを使うのはよくない。 関数に引数があるのなら、それは宣言すべきである。 もしなければ、void を使うのがよい。 (p.89)

というわけなので void を書きましょう。

なぜこんな規格になっているのか

そもそもなぜ void を書くのと書かないのとでこんな挙動の差が出るように規格が定められているんでしょうか？ 調べてみたところ、どうやらこの挙動は ANSI でC言語の規格が定められる以前の K&R 時代の関数定義/宣言との互換を保つためのもののようです。

実はC言語には標準化以前の頃からの伝統的な関数定義/宣言の方法が今でも残されています。 K&R スタイルの関数定義/宣言なんて呼ばれていたりするようです。 このスタイルでは以下のようにして関数を定義します。

int max(a, b)
int a, b;
{
  return a > b ? a : b;
}

このように、関数名の後ろの括弧の中には仮引数の識別子だけを書いておき、関数本体の前に仮引数の型を宣言するという構文になっています。 自分は以前 UNIX V6 のソースコードを眺めていた時にこの書き方を見たことがあって「昔のC言語にはこんな書き方があったのか〜」なんて思っていたので、今でもこのスタイルの書き方が規格に定められていると知ってかなり驚きました。

さらに驚くべきことに、K&R スタイルでは呼び出し側からは引数の情報が一切わかりません。 上記の max 関数を現在のスタイルで書くと int max(int a, int b) { ... } となるのですが、この場合の max関数 は「int 型の引数を2つ受け取って、int型を返す関数」という具合に型が定められます。 一方で、K&R スタイルで書かれた場合の関数 max は「引数については情報がなく、int型を返す関数」という風に型が定められます。 そして、後者ように定義された関数を呼び出す時、コンパイラは引数の数のチェックを行いません。 つまり、K&R スタイルで定義された max を以下のように呼び出してもエラーにはならないわけです。

int max(a, b)
int a, b;
{
  return a > b ? a : b;
}

int main(void) {
  max(1, 2, 3);
  return 0;
}

そして、実は引数の括弧の中を空にした関数は K&R スタイルの関数定義とみなされます。 最初の void func() {} の例がエラーにならないのはこういう理由です。

ちなみに、K&R スタイルの関数宣言は関数名を書いてその後ろの空の括弧をおいておくという記法しか用意されていません。 細かい話ですが、関数の定義と宣言は明確に違っていて、定義は関数本体を伴うもの、宣言は伴わないものです。 すなわち、上記の max 関数の宣言は int max(); となります。 当然ながらこの書き方ではコンパイラから見て引数の情報は一切わかりません。

標準化以前はこのような関数定義/宣言しか存在しなかったのですが、標準化の際に現在も使われているような引数の型を明示する構文が導入されました。 これがいわゆるプロトタイプ(関数原型)と呼ばれるものです。 おなじみの int max(int a, int b) { ... } や int max(int, int); という関数定義/宣言ですね。 これによって関数呼び出しの際の型のチェックがより強力にできるようになりました。 ただし、新しいスタイルは引数が空の時は K&R スタイルと同じ形になってしまいます。 そこで、K&R スタイルとの互換性を保つために、引数がないことを明示する機能として void を書くという記法が導入されました。 これが引数なしを明示する void が導入された歴史的な経緯のようです。

なお、この K&R スタイルの関数定義/宣言は C99 の規格で廃止予定とされていたらしいのですが、C11 の規格でもまだ廃止されずに残されています。 互換性って大変ですね......

まとめ

というわけで、引数の括弧が空の関数は古い形式の関数定義/宣言とみなされてしまい、呼び出し時の引数の数や型のチェックが行われません。 うっかり変な呼び出しが正常にコンパイルされないようにちゃんと void を書くのが安全という話でした。

なお、この記事は K&R の第二版と C11 の最終ドラフトを読み漁って書いたのですが、もしかしたら僕が勘違いしている箇所もあるかもしれないので、その辺りはご注意ください。

おまけ1

C11 の規格の 6.7.6.3.14 を読む限りだと、関数定義の時は関数宣言と挙動が違うという解釈もありえそうなのですが、今回は以下のツイートにあるような解釈をしてこの記事を書いています。 この辺りは規格の書き方が曖昧でどう解釈すればいいのか自分も迷っているのが正直なところです......

6.9.1.7にはK&Rスタイルじゃない関数定義は関数プロトタイプも与えるとあるのに対して、K&Rスタイルの関数定義にはそういった記述がないんですよね
なので、6.7.6.3.14と合わせて、定義される関数自身からは引数なしと見えるけれど、呼び出し側からは引数の情報なしと見えると解釈されるのかなぁと

— Shinya Kato (@0x19f) April 18, 2019

おまけ2

ちなみに、gcc だとコンパイル時に -Wstrict-prototypes という警告オプションをつけると関数定義/宣言ともに K&R スタイルで書かれている場合に警告を出してくれるようです。 -Wold-style-definition という警告オプションもあるんですが、こちらは関数定義に対してしか警告を出してくれないようですね。

自作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コンパイラのセルフホストまでの道のり
• ミスコンパイルに悩まされた話

来年以降も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 の言語仕様よりも大幅に簡易化して実装しています。 最初から作り込みすぎないのが重要です。

• 変数と代入文 [commit]
• 関数宣言・関数呼び出し [commit]
• 制御構文 (if, for, while, break, continue, return) [commit]
• 変数宣言・ポインタ型・配列 [commit]
• 文字列リテラル [commit]
• 構造体 [commit]

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

自作Cコンパイラ、いろいろと謎のバグに悩まされて消耗したけれどセルフホスト達成です(セルフホストしてできたコンパイラをテストにかけてもパスしてるっぽい) #seccamp https://t.co/zdLKS4oWy6

— Shinya Kato (@0x19f) 2018年8月16日

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

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

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

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

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

自作コンパイラで自分自身をコンパイルするイメージ図

このデバッグはかなり困難を極めました。 自作のコンパイラはデバッグ情報を出力しないので 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コンパイラに気軽に挑戦できるようになるんじゃないかと楽しみにしています。

セキュキャンの途中で思いついたんだけど、よいコード（GCCの1.5倍遅い程度とか）を出力するCコンパイラを8ccより簡単に書けるのでは？ と思ったので新しいバージョンを作成中。うまくいったら本をこれベースに書き直すつもり。 https://t.co/zAKsbo53n2

— Rui Ueyama (@rui314) 2018年8月19日

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

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

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

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

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

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

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

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

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

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

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

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

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

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

国内予選おつかれ会の様子です pic.twitter.com/pOgbCR3NWP

— Shinya Kato (@0x19f) July 6, 2018

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

pic.twitter.com/8OZ8SIQqBL

— Shinya Kato (@0x19f) July 6, 2018

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は再スキャンの前に全て取り除かれます。

マクロの再帰的な展開

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

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

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

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: WG14/N1570 Committee Draft
• C99: WG14/N1256 Committee Draft

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

コンパイルの処理の流れ

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

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

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

preprocessing-tokenはフェーズ3〜6で使われる字句要素、tokenはフェーズ7の構文解析で使われる字句要素です。 ふたつは若干内容が異なっている点に注意です。 イメージとしては、preprocessing-tokenはざっくりとしたトークン分けで、プリプロセッシングが行われた後により細くtokenに分けるという感じです。 例えば、数値は整数と浮動小数点をすべて含むpp-numberという字句要素に分解され、プリプロセッシングの後で整数と浮動小数点に分けられて値と型が解析されます。 余談ですが、pp-numberは0xe-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+++++yはx, ++, +, ++, yと区切ると正しいプログラムになりますが、この規則に則って字句解析が行われるのでx, ++, ++, +, yと区切られます。

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

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

文字定数を受理するオートマトン

その他の種類のトークンを受理するオートマトンは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年

1年春学期 / 1年秋学期

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

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

2年

2年春学期 / 2年秋学期

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

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

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

3年

3年春学期 / 3年秋学期

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

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

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

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

まとめ

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