HOME情報セキュリティ資料・報告書・出版物調査・研究報告書情報セキュリティ技術動向調査(2008 年上期)

本文を印刷する

情報セキュリティ

情報セキュリティ技術動向調査(2008 年上期)

10 C コンパイラの最適化の問題

田中 哲

  最近のセキュリティ問題として、整数オーバーフローの問題が注目されている。そのため、プログラミング言語に関連するセキュリティの話題として「JVNVU#162289 ある種の範囲チェックを破棄するC コンパイラの最適化の問題」[1] についてその背景と関連する話題をあわせて解説する。

1 ポインタの足し算

  JVNVU#162289 [1] の問題は、以下のような話である。

char *buf;
int len;
	

  このような型宣言が行われているとき、下記の「長さチェック」が働かない可能性がある、というものである。

len = 1<<30;
[...]
if(buf+len < buf) /* 長さチェック*/
  [...オーバーフローに対処するコード...]
	

  これだけでは、どのような状況であればこのようなコードが書かれるのか明らかでないが、ARR38-C [3] にはPlan 9 の sprint() 関数におけるテストを変形したものとして下記のコードが載っている。

char *buf;
size_t len = 1 << 30;

/* Check for overflow */
if (buf + len < buf) {
  len = -(uintptr)buf-1;
}
	

  このコードの意図は、「buf + len < buf の検査により、buf + len が大きすぎてアドレス空間の終端を越えてしまうならば、アドレス空間の終端を越えないようにlen を小さくする」というものである。
  JVNVU#162289 は、直接的には、このbuf + len < buf の検査がC コンパイラの最適化によって常に偽になると判断される可能性があることを指摘している。その理由は、このbuf + len の足し算がオーバーフローしたとき、オーバーフローしたキャリービットを除いた値が結果として得られるという保証がないためである。
  この「保証がない」というのはC の規格がその保証を要求していないためであり、C コンパイラは、そのような場合にどのような振舞をするかを自由に選べる。最適化は一般に高速なオブジェクトコードを目指すわけであるから、if 文自体を削除してもC の規格には反しないとなれば、そうすることは高速かつ小さなオブジェクトコードに結びつくため、妥当な選択である。
  そのようなC コンパイラの選択を封じるための方法として、JVNVU#162289 は、下記のようにuintptr_t にキャストしてから比較するコードを紹介している24

#include <stdint.h>
[...]
if((uintptr_t)buf+len < (uintptr_t)buf)
 [...]
	

  このように変更すれば、足し算はポインタの足し算ではなく、uintptr_t の足し算になる。uintptr_t は符号無し整数型のひとつであるから、足し算においてオーバーフローが起きた場合はキャリービットを除いた値が結果となることが保証されている。このため、C コンパイラはこのif 文を除去することができなくなる。
  しかし、この修正はアドレス空間が連続的であり、ポインタをuintptr_t にキャストしたときにアドレスがそのまま整数になることを前提としている。残念ながら、この前提はC の規格では保証されない。uintptr_t について保証されているのは、void へのポインタをuintptr_t に変換し、それをさらにvoid へのポインタに変換したとき、元のポインタと等しくなるということだけである。例えば、64bit ワードマシンにおいてバイトを指すポインタを実現する手段として、ポインタ内の上位ビットにワード内のオフセットを格納する環境もある[9], [10] が、そのような環境でポインタをuintptr_t に変換した結果がその64bit ワードそのものになるとすると、uintptr_t の足し算でオーバーフローが起きることはアドレス空間の終端を越えることには対応しない。
  この例の本質的な問題は、アドレス空間の終端という概念をC 言語で扱おうとした点である。そもそもC言語では、アドレス空間がひとつの連続的な空間であることは保証しておらず、アドレス空間の終端という概念がない。実際、ハーバードアーキテクチャなど、アドレス空間の終端という概念が自明でない環境は存在するため、その概念がない事自体は不適切なことではない。しかしそのことは、アドレス空間の終端を扱おうとすれば、必然的にC 言語で保証されていない仮定を導入せざるを得ないことに結び付く。
  したがって、正しい考え方は、本当にアドレス空間の終端について判断しなければならないのかどうかを考え直すことである。カーネルのようにアドレス空間自体も処理の対象となる場合にはそのような判断が必要になることもありうるが、通常のアプリケーションではアドレス空間終端でなく、バッファの終端を越えるかどうかの判断で十分なはずである。
  ここで、Plan 9 の sprint を調べると、現在では以下のようなコードになっている。[5]

int
sprint(char *buf, char *fmt, ...)
{
  ...
  n = vsnprint(buf, 65536, fmt, args); /* big number, but sprint is deprecated anyway */
  ...
}

  この関数はC 言語のsprintf() と同様な機能を持つ。このコードでは、JVNVU#162289で指摘された問題は見つからないが、65536 という定数が使用されており、sprint はdeprecated というコメントがある。
  sprint() は sprintf() と同じく、バッファの大きさを引数で受け取らないという問題がある。このためバッファ終端はsprint() 内部では不明である。推測としては、バッファ終端が不明で判断できなかったために、アドレス空間終端についての判断を行ったという可能性が考えられる。
  しかし、正しいやりかたは、sprintf() に対してsnprintf() があるように、バッファの大きさを引数で渡すことである。実際、Plan 9 にはバッファの大きさの引数を加えたsnprint() [6]があり、sprint() は deprecated であるため、この正しい方向に向かっているといえる。
  なお、ARR38-C にはバッファの大きさを検査する場合のコードについての注意も述べられている。下記のコードには問題がある。

int process_array(char *buf, size_t n) {
  return buf + n < buf + 100;
}

  このコードはbuf が 100 バイト固定長のバッファを指すとして、buf + n がバッファ内部を指すかどうかを判断する。しかし、n が 100 よりも大きければ、buf + n はバッファの外を指すことになる。C の規格では、そのようなバッファの外を指しているポインタに関してはポインタの比較は定義されない。例えば、buf + n がオーバーフローしたときにキャリービットを無視した結果になるという素朴な環境を考えると、アドレス空間内におけるbuf の位置とn の大きさによって足し算がオーバーフローしたときには、buf + nは buf + 100 よりも小さいことになり、process_array の意図する判断に失敗してしまう。したがって、これは下記のように実装すべきである。

int process_array(char *buf, size_t n) {
  return n < 100;
}

  なお、コンパイラによっては、buf + n がオーバーフローした場合の挙動は未定義であることを利用し、buf + n < buf + 100 を n < 100 と変形して2 回の足し算を削減する可能性がある。これが可能なのはbuf + n < buf + 100 と n < 100 は定義されている範囲内においては同じ結果が得られるためである。その場合は、結果的に正しい実装と同じ結果になるが、これはコンパイラの最適化に依存する。最適化によって正しい結果が得られたり、得られなかったりする実装は、不適切である。
  一般に、C 言語におけるポインタで保証されるのは、確保されたメモリ領域の内部で済む演算だけである。(正確には、配列の最後の要素を越えた直後の場所も扱える。)その範囲を外れたポインタは、それが指す対象が存在しないため、基本的にポインタとして不適切であり、本当に必要なのかどうか熟慮すべきである。

2 符号つき整数の足し算

  ポインタの足し算と同様に、符号つき整数の足し算もオーバーフローの場合の結果は規定されていない。(なお、符号無し整数の場合は規定されているため、前述のuintptr_t の用法は問題ない。)
これは、歴史的には、負数の表現に1 の補数を使用する実装が存在したことに由来する。C の規格には、INT_MIN の絶対値が(32768 ではなく) 32767 以上となる負の値でなければならないという規定など、1 の補数に対する配慮が他にも見られる。
  現在では、負数の表現に1 の補数を使用する実装はまずない。しかし、このオーバーフローの結果が規定されていないことはコンパイラの最適化に利用される。JVNVU#162289 から参照されているMSC15-A には符号つき整数と最適化に関する問題の例が述べられている。下記のコードには問題がある。


#include <assert.h>

int foo(int a) {
  assert(a + 100 > a);
  printf("%d %d\n", a + 100, a);
  return a;
}

int main(void) {
  foo(100);
  foo(INT_MAX);
}

  このコードにはa + 100 > a という条件判断があるが、ここで、a は (signed) int なので、その演算におけるオーバーフローの計算結果は規定されていない。規定されている範囲内、すなわちオーバーフローが起きない範囲内では、a + 100 > a は常に真である。そうすると最適化により(assert は引数が真ならなにもしないので) assert 全体を削除することができる。
  しかし、コードの意図はa + 100 がオーバーフローしないことの検査であり、assert が削除されるのは意図とは異なる。意図どおりの動作を保証するには、下記のように書かなければならない。


#include <assert.h>

int foo(int a) {
  assert(a < (INT_MAX - 100));
  printf("%d %d\n", a + 100, a);
  return a;
}

int main(void) {
  foo(100);
  foo(INT_MAX);
}
	

  このコードでは、100 を加えてもオーバーフローしないことをa < (INT_MAX - 100) として判断しており、この判断ではオーバーフローは起きない。
  また、ループ回数を求められると最適化に都合がいい場合がある。[7] 下記のコードを 題材に考える。


int i, n;

for (i = 0; i <= n; i++) {
  ...
}
	

  ここでn が非負であれば、i が 0 からちょうどn まで変化しながら回るから、ループ回数はn+1 回に見える。しかし、残念なことにn が INT_MAX である場合にはそうではなく、このループは終わらない。そのため、最適化においてループ回数はn+1 回という仮定は使えない。
  しかし、符号つき整数の足し算がオーバーフローする場合の挙動が規定されていないことを考えると、i++ がオーバーフローを起こす場合の挙動は最適化において変化しても許される。n が INT_MAX の場合にループが終わらないというのはi++ がオーバーフローしてしまうことが原因である。したがって、その場合は除去して考えることができ、そうすればループ回数はn+1 回と推論できる。
  このように、符号つき整数のオーバーフローの挙動が規定されていないことは、最適化に役に立つ性質である。つまり、コンパイラの開発者には、この性質を利用する動機がある。
  整数のオーバーフローの検査は、演算によってはそれほど自明でない。[8] には四則演算のオーバーフローの検査を行う方法が記載されている。

まとめ

プログラムを作成する際には、コンパイラの最適化の進歩によってプログラムの挙動が 変化しないよう、可能なかぎりC 言語の規格の範囲内で記述することが肝要である。少な くともポインタや符号つき整数の演算については実際にコンパイラが規格の範囲外の挙動 を最適化のために任意に変更することがあり、注意が必要である。


以上


参考文献

[1] JVNVU#162289: ある種の範囲チェックを破棄するC コンパイラの最適化の問題,
http://jvn.jp/cert/JVNVU162289/

[2] Vulnerability Note VU#162289: C compilers may silently discard some wraparound checks
http://www.kb.cert.org/vuls/id/162289

[3] ARR38-C. Do not add or subtract an integer to a pointer if the resulting value does not refer to a valid array element
https://www.securecoding.cert.org/confluence/display/seccode/VOID+Do+not+add+or+subtract+an+integer+to+ a+pointer+if+the+resulting+value+does+not+refer+to+a+valid+array+element

[4] MSC15-A. Do not depend on undefined behavior
https://www.securecoding.cert.org/confluence/display/seccode/MSC15-C.+Do+not+depend+on+undefined+behavior

[5] Plan 9: sprint.c<
http://plan9.bell-labs.com/sources/plan9/sys/src/libc/fmt/sprint.c
参照日時: 2008-06-15

[6] Plan 9: snprint.c
http://plan9.bell-labs.com/sources/plan9/sys/src/libc/fmt/snprint.c
参照日時: 2008-06-15

[7] GCC optimizes integer overflow: bug or feature?<
http://gcc.gnu.org/ml/gcc/2006-12/msg00459.html

[8] ヘンリー・S・ウォーレン、ジュニア,『ハッカーのたのしみ』,エスアイビー・アクセ ス発行

[9] Cray C/C++ Reference Manual: 9.1.2.2. Types
http://docs.cray.com/books/004-2179-001/html-004-2179-001/rvc5mrwh.html#ZFIXE DDICM1VZB

[10] C FAQ Q5.17: Seriously, have any actual machines really used nonzero null pointers, or different representations for pointers to different types?
http://c-faq.com/null/machexamp.html

目次へ
次へ