全てのCプログラマが未定義な振る舞いについて知っておくべきこと #2/3

[原文: What Every C Programmer Should Know About Undefined Behavior #2/3]

連載のpart 1では、未定義な振る舞いとは何か、未定義な振る舞いを利用して、「安全な」言語よりもハイパフォーマンスなアプリケーションを生成するためにCとC++コンパイラが未定義な振る舞いをどのように利用しているのかを議論した。この記事では、未定義な振る舞いが引き起こす全く驚くような結果を説明し、Cがどんなに"安全でない"かを話したい。part 3では、この驚くような結果をやわらげるために、親切なコンパイラは何が出来るのか (それが必須の機能でないとしても) について話したいと思う。

今回の記事は「Cプログラマにとって、未定義な振る舞いが怖くて恐ろしいことがあるのはなぜなのか」と呼びたい。:-)

コンパイラの最適化は驚くような結果を引き起こす

近年のコンパイラオプティマイザは多くの最適化処理を行う。それらは、特定の順番に、時には繰り返し適用され、そしてコンパイラが成長するにしたがって (つまり、新しいリリースが出ると) 変化する。また、異なるコンパイラは、根本的に異なるオプティマイザを持っていることがある。最適化は異なる段階で行われるので、ある最適化が発生させる効果は、それまでの最適化によるコードの変更によって異なることがある。

もっと具体的に説明するために、馬鹿馬鹿しい例を見てみよう(Linux Kernelで見つかったセキュリティーホールになり得るバグを簡略化したもの)

void contains_null_check(int *P) {
  int dead = *P;
  if (P == 0)
    return;
  *P = 4;
}

この例では、コードは"明確に"NULLポインタをチェックしている。もしコンパイラが、"冗長なNULLチェック削除" (Redundant Null Check Elimination: RNCE)よりも先に"デッドコード削除"(Dead Code Elimination: DCE)を行ったとすると、コードはこのように展開していくだろう。

void contains_null_check_after_DCE(int *P) {
  //int dead = *P;     // オプティマイザにより削除される
  if (P == 0)
    return;
  *P = 4;
}

そして次に

void contains_null_check_after_DCE_and_RNCE(int *P) {
  if (P == 0)   // NULLチェックは冗長ではないので、削除されない
    return;
  *P = 4;
}

しかし、もしオプティマイザの構成が異なっていて、"デッドコード削除"よりも先に"冗長なNULLチェック削除"を実行したとすると、このようになるだろう。

void contains_null_check_after_RNCE(int *P) {
  int dead = *P;
  if (false)  // P はすでにデリファレンスされているので、NULLのはずがない
    return;
  *P = 4;
}

そして次に冗長なコードが削除されると

void contains_null_check_after_RNCE_and_DCE(int *P) {
  //int dead = *P;
  //if (false)
  //  return;
  *P = 4;
}

となる。

多くの (分別のある!) プログラマは、この関数からNULLチェックが削除されるととても驚くようだ (そしてほとんどの場合、コンパイラのバグとして報告される)。しかし、C標準によると、"contains_null_check_after_DCE_and_RNCE" と "contains_null_check_after_RNCE_and_DCE" との両方とも完全に有効な最適化であり、様々なアプリケーションのパフォーマンスを向上させるために、二つの最適化があることが重要なのだ。

この例は、意図的に単純に人工的に作ったものだが、似たようなことは関数のインライン化に伴ってよく起こる。関数をインライン化すると、多くの場合、たくさんの最適化の機会が派生するからだ。つまり、オプティマイザが関数をインライン化することを決定すると、多くの局所的な最適化が始まり、コードの振る舞いを変えることになる。[訳注: 原文にある "This is both perfectly..." は前パラグラフと同じ内容であり、原文のミスだと思われるので、訳さない事にする。]

未定義な振る舞いとセキュリティとは仲良くできない

CとCから派生するプログラミング言語は、セキュリティが重要なアプリケーションを書くために幅広く使われている。カーネル、setuid デーモン、ウェブブラウザ、その他にもたくさんある。これらのコードは悪意のある入力にさらされているので、バグはセキュリティホールにつながる多くの問題につながる。Cの特長としてよく知られているものに、コードを読めば何が起こるのかを理解するのが比較的簡単だ、というものがある。[訳注: 前文とのつながりが明確ではないが、おそらく、「何が起こるのかわかりやすいので、セキュリティが重要なアプリケーションを書くのに向いている (と思われている)」という意味だと思われる。]

しかし、未定義な振る舞いによって、この特長はなくなってしまう。結局のところ、ほとんどのプログラマは、前述の"contains_null_check"がNULLチェックをすると思っていたのだろう。このコードはそれほど恐ろしいものではない (というのは、この関数にNULLが渡されると、ストア時にアプリケーションはおそらくクラッシュするであろうし、それはデバッグが比較的簡単だからだ) が、"極めて妥当"に見えて実際には完全に無効なCコードはたくさん存在する。この問題は、非常に多くのプロジェクト (Linux Kernel, OpenSSL, glibc, など) に関わっていて、CERTがGCCに対して脆弱性の注意を出したりもした。(とはいえ、個人的な見解としては、GCCだけではなく、広く使われている最適化を行うCコンパイラ全てがこの脆弱性を持っていると思っている。)

例を見てみよう。注意深く書かれたこのCコードを見てほしい。

void process_something(int size) {
  // 整数のオーバーフローをキャッチする
  if (size > size+1)
    abort();
  ...
  // エラーチェックは省略している
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

このコードは、malloc で確保する領域が、ファイルから読み込むデータ(nul終端バイトを追加する必要がある)を保存するのに十分大きいかをチェックしていて、整数のオーバーフローを回避している。しかし、これはまさに私たちが前に検討した例であり、コンパイラは最適化の一環として、整数オーバーフローのチェックを(正当に)削除することが許される。つまり、コンパイラがこの関数を次のように変換することは十分に可能だということだ。

void process_something(int *data, int size) {
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

64bitプラットフォームでビルドされた場合を考えると、"size"がINT_MAX (おそらくディスク上のファイルサイズ) のときに、これはセキュリティホールにつながるバグとなる。これがどんなに悲惨なことか検討してみよう。このコードを読んだ監査人は、オーバーフローが適切にチェックされていると当然考えるだろう。このコードをテストした誰かは、エラーが発生するケースでテストしない限り、問題を見つけることはないだろう。このセキュアなコードはうまく動いているが、そのうち誰かがうまくやって脆弱性を悪用することになる。要するに、これは驚くようなそして極めて恐ろしいバグなのだ。幸いなことに、この場合の修正は簡単だ。"size == INT_MAX" か似たような条件を使えば良い。

このように、整数のオーバーフローは多くの理由でセキュリティ上の問題となる。完全に定義された整数演算 (-fwrapv や、符号無し整数) を使っていたとしても、全く別の種類 の整数オーバーフローに関わるバグが生まれる可能性はある。幸いなことに、この種のバグはコードに現れるので、知識のあるセキュリティ監査人は大抵の場合問題を見つけるだろう。

最適化済みのコードをデバッグすることは何の役にも立たない

ある種の人々 (例えば、組込み系の低レイヤプログラマで、生成されたマシンコードを見るのが好きな人々) は、最適化を有効にしたままで全ての開発を行う。開発中のコードがバグを含むことはよくあるので、こういう人たちは、デバッグするのが難しい実行時の振る舞いにつながる、驚くような最適化を無駄に多く見ることになる。例えば、最初の記事の"zero_array"の例においてうっかり "i=0" を取り除いてしまうと、未初期化変数を使用していることになるので、コンパイラはループを完全に無視する (zero_arrayを"return;"にコンパイルする) ことが許される。

もうひとつ、(グローバル) 関数ポインタを使用した、最近起こった事例を見てみよう。簡略化したコードはこんな感じだ。

static void (*FP)() = 0;
static void impl() {
  printf("hello\n");
}
void set() {
  FP = impl;
}
void call() {
  FP();
}

Clangはこれを

void set() {}
void call() {
  printf("hello\n");
}

と最適化する。[訳注: 最適化されたため、call中にFPのNULLチェックが無く、implがインライン展開されている。]

NULLポインタを呼び出すのは未定義なため、call()の前にset()が呼ばれたと仮定することが許されるので、こういう最適化をして良い。この場合、開発者は"set"を呼ぶのを忘れたが、NULLポインタデリファレンスでクラッシュすることはなく[訳注: 最適化オプションをつけて開発していたため]、他の人がデバッグビルドを使ったときにコードが壊れた。

未定義な振る舞いを使用している"動いている"コードは、コンパイラが進化したり変わったりすると"壊れる"

私たちは、"動いているように見える”アプリケーションが、新しいLLVMを使ったり、GCCからLLVMに変更して時点で、動かなくなるという事例をたくさん見てきた。LLVM にたまたまバグが一つや二つあったということもあるのだが :-) 、アプリケーションの潜在的なバグが、コンパイラによってまさに表面化したから、というのがほとんだ。これはいろいろな方法で起こり得る。2つ例を挙げると、

1. "以前"は幸運なことにゼロ初期化されていた未初期化変数が、ゼロではないレジスタを共有することになった。これはレジスタ割り当ての変更によってよく起こる。

2. スタック上の配列のオーバーフローが、重要な変数を踏みつぶすようになったが、それは今までは使われていない領域だった。これは、コンパイラが、スタック上にモノを詰め込むやり方を変えたときや、生存期間の異なる変数がスタック領域をより積極的に共有するようになったときに起こる。

認識すべき重要で恐ろしいことは、将来の任意の時点において、未定義な振る舞いに関わるいかなる最適化でも、バグを含むコードの引き金を引き得るということだ。関数のインライン化、ループアンローリング、memory promotion [訳注: 何のことだかわかりません]、その他の最適化が改良され続けていて、上で見たように、これらの重要な目的は、派生的な最適化の機会を与えることである。

私はこの事態には深く失望している。必ずコンパイラが非難されるから、という理由もあるが、多くのCコードが地雷原であり、ただ爆発するのを待っているだけだからだ。そして状況はもっと悪い。というのは、、、。

大規模なコードベースが未定義な振る舞いを含んでいるかを決定する信頼できる方法はない

地雷原をもっともっとひどくする事実として、大規模なアプリケーションに未定義な振る舞いが存在するかどうかを判定する良い方法がないということがあり、したがって将来において状況を打破できる見込みがないことがある。いくつかのバグを見つけるのに使える便利なツールは存在するが、あなたのコードは将来も絶対壊れない、という自信を与えてくれるものはない。いくつかのオプションを、長所と短所とともに見てみよう。

1. Valgrindのmemcheck toolは素晴らしいツールで、全ての未初期化変数やその他のメモリ関連バグを見つけてくれる。Valgrindは非常に遅いし、生成されたマシンコードに残っているバグしか発見出来ない (ので、オプティマイザが取り除くことは見つけられない) し、ソースコードの言語がCであることを知らない (ので、大きすぎるシフトや符号付き整数のオーバーフローバグは見つけられない) という意味で、限界がある。

2. Clangは実験的に-fcatch-undefined-behaviorモードを持っている。これは、実行時のチェックを挿入して、大きすぎるシフトや、単純な配列の範囲外アクセスエラーなどを見つけてくれる。これは、アプリケーションの実行速度を遅くするし、ランダムなポインタのデリファレンスは見つけられない (Valgrindは見つけられる) という天で限界があるが、その他の重要なバグを見つけることはできる。Clangはまた-ftrapvフラグ (-fwrapvフラグを間違えないように) を完全にサポートしているので、符号付き整数のオーバーフローを実行時にトラップする。(GCCにもこのフラグはあるが、私の経験から言うと、全く信頼できないしバグが多すぎる。) -fcatch-undefined-behaviorの簡単なデモは次のとおり。

$ cat t.c
int foo(int i) {
  int x[2];
  x[i] = 12;
  return x[i];
}

int main() {
  return foo(2);
}
$ clang t.c 
$ ./a.out 
$ clang t.c -fcatch-undefined-behavior 
$ ./a.out 
Illegal instruction

3. コンパイラの警告は、ある種のバグを見つけるのに役立つ。未初期化変数や単純な整数のオーバーフローのバグなど。これには2つの基本的な限界がある。1) コードが実行されるときの動的情報を持っていないし、2) コンパイル時間が長くならないように、非常に素早く解析しなくてはならない。

4. The Clang Static Analyzerは、バグ (未初期化変数の使用 [訳注: 原文では「未定義な振る舞いの使用」だが、それでは意味が通らないので、未初期化変数の使用に直した。] や、NULLポインタのデリファレンスなど) を見つけるために、もっと深く解析する。通常の警告のようにコンパイルタイムに制限されないので、高性能なコンパイラ警告メッセージだと思ってくれれば良い。静的アナライザの主要なデメリットとしては、1) コードが実行されるときの動的情報を持っていないし、2) 多くの開発者の通常のワークフローに組み込まれていない (ただし、Xcode 3.2 とそれ以降に組み込まれたことは素晴らしい) ことがある。

5. LLVM "Klee" Subprojectは、バグを見つけるために、シンボル解析を行ってコード断片の "全ての実行パスを試し"、テストケースを生成する。偉大な小さなプロジェクトではあるが、大きなアプリケーションに対して実行するのは現実的ではないという点で、大きな限界がある。

6. 私は試したことはないが、Chucky Ellison と Grigore RosuによるC-Semantics toolが、とても面白いツールで、ある種のバグ (sequence point violation [訳注: 日本語訳がわかりません] など) を発見できるようだ。まだ研究段階のプロトタイプだが、小さくて自己完結しているプログラムのバグを見つけるのには役立つかもしれない。詳しい情報を知りたい方には、John Regehrの記事を読むことを勧める。

結論としては、いくつかのバグを見つける道具は道具箱にたくさんあるのだが、アプリケーションに未定義な振る舞いが無いことを証明する良い方法はない、ということだ。実世界のアプリケーションにたくさんのバグがあり、重要なアプリケーションの多くにCが使われていることを考えると、これは極めて恐ろしい。最後の記事では、Clangに特に焦点をおきつつ、未定義な振る舞いを扱うためにCコンパイラが持っている様々なオプションを見ていきたい。

原著: Chris Lattner
翻訳: Ken Kawamoto