C++ で競技プログラミングをやっていて、整数オーバーフローに泣かされたことのない者はいないだろう。僕とてそうである。ちょっとしたケアレスミスにすぎないのだが、些細なミスであるからこそ、それを繰り返してしまうとことさら不甲斐なく感じる。

　オーバーフローを機械的に防ぐ方法はないだろうか？「気をつける」以上のシステマチックなやり方で回避することはできないか？　と、まるで障害報告書を書くような気持ちで何度も振り返るも、いつも結論はでないままだった。

　いま、 CS:APP を読んでいて、いまいっぽぼんやりしたまま寝かせていた考えに光が当てられた気がするので、今回はそれをまとめようと筆をとった。

　あらかじめ述べておくと、結論としてはありきたりな表現にすぎない。クサいところはより大きい幅を表現できる整数型を使おう、というところに着地している。それ以上でもそれ以下でもない。

　たとえば愚直に書いたこんな計算を考えてみよう。

int main()
{
  int x, y;
  cin >> x >> y;
  int answer = x * y;
  cout << answer << endl;
  return 0;
}

「x と y の定義域をはっきりさせろ！」とみずから苦情を出したくなりつつも、いったんそれはおいておく。いかにもオーバーフローしそうではある。

　多くの場合、プログラマを困らせるのは「オーバーフローが起こる」という事象そのものよりも「オーバーフローが起こってもプログラムが止まらないこと」だったりする。オーバーフローが発生するときはランタイムエラーが起こるようになっていれば、見当違いのデバッグ方針を携えて右往左往することもない。

int safe_mult(int x, int y)
{
  int p = x * y;
  if (x != 0)
  {
    assert(y, p / x);
  }
  return p;
}

int main()
{
  int x, y;
  cin >> s >> y;
  int answer = safe_mult(x, y);
  cout << answer << endl;
  return 0;
}

　この関数をライブラリとして持っておいて、乗算をしたいときはいつでもこれを呼び出すか？　いや、それも片手落ちである。なぜなら結局のところ、ランタイムエラーは出てしまうわけで、それによって誤答ペナルティが与えられてしまう。オーバーフロー時にエラーを吐いて緊急停止するのは、そうでないよりはマシではあるものの、本当にほしいものはこれではない。

　となると、結局のところは最初から64ビットを使ってこう書いてしまうのが手堅い。オーバーフローが起こったとして、まず考えられるのはこうして幅を広げることであるから、最初からクサイところはこう書くのが合理的か。逃げの一手でしかないが、僕程度の水準の競技プログラマにとってはこれで十分そうに思える。

int main()
{
  long long x, y;
  cin >> x >> y;
  long long answer = x * y;
  cout << answer << endl;
  return 0;
}

　64ビットを使ってもなおオーバーフローするような入力が与えられるときはどうしようか？　そういうケースに遭遇したことはいまだないような気がするが、そのときこそこうなるか。

long long safe_mult(long long x, long long y)
{
  long long p = x * y;
  if (x != 0)
  {
    assert(y, p / x);
  }
  return p;
}

int main()
{
  long long x, y;
  cin >> x >> y;
  long long answer = x * y;
  cout << answer << endl;
  return 0;
}

　64ビットを費やしてもなおオーバーフローが発生する計算をするなら、このときこそエラーを投げて異常終了する。計算の仕方を見直すべきである。どうしても大きな整数を扱うのであれば、可変長の幅を表現できるライブラリなり言語を使わなければならない。しかし繰り返すが、そんなユースケースは滅多にあるものだろうか？

　というわけで、なにか新しいインサイトを提供することはできず、ありきたりな議論に終始した。しかしこれまで書かずにいたものをこうして言語化したことの背後には、僕のなかでの学びがある。それはこういうことである。

　整数オーバーフローに関するこの問題意識は、以前は単なる個人的なフラストレーションを動機づけとしていた。それ以上のものではなかったので、表立って公開しようとも思いはしなかった。しかしいま CS:APP を読むことを通して、これが実に普遍的な脆弱性の問題と直結していることを手応えとして知った。

　たとえば FreeBSD の getpeername() が持っていた、符号付き整数と符号なし整数のキャスト時のオーバーフローによって、プログラムが不正なメモリ領域を読み取ることができる状態となっていた脆弱性 CVE-2002-0973。あるいはサンマイクロシステムズの XDR ライブラリが持っていた、同じく整数オーバーフローによって悪意をもってメモリ領域を破壊しうる状態になっていた脆弱性 CA-2002-25。

　いずれをとっても、有力な C プログラマをもってすら、整数オーバーフローを排除するのは困難であるし、またそれが単なるバグではなく深刻な脆弱性を生むという観点を得られたのは、怖いながらもおおいに学びとなった。

　僕はといえば、競技プログラミングをするだけの気楽な用途であるから、こう考えている。たとえば非負整数であっても int 型で宣言するのと同じような乱暴さで、 long long 型を多用して恥ずかしいことはない。実際、そのやりかたに一抹の恥ずかしさを覚えていたからこそ、 int と long long を使い分けようとしながらもうまく制御できず、不要なオーバーフローを引き起こしてフラストレーションを抱えていたわけである。恥ずかしさでいいプログラムが書けるわけではないから、合理でもって long long 型に活路を見出そうと思っている。