整数オーバーフロー

**整数オーバーフロー**（せいすうオーバーフロー、）とは、コンピュータプログラミングにおいて、整数に対する算術演算によって、その結果を格納するために割り当てられた空間で表現可能な範囲外の数値（最大値より大きい、または最小値より小さい）を作成しようとしたときに発生する現象である。

現代の計算における整数の算術演算のほとんどは整数のバイナリ（二進法）表現を使用しているが、十進法表現も存在する。本記事では主にバイナリ表現について扱うが、他のケースでも同様の考慮事項が当てはまる。

コンピュータ内でビットパターンとして表現される整数は、「符号なし整数」（値が0からある最大値まで）または「符号あり整数」（値が正または負）のいずれかとして解釈できる。最も一般的には、符号あり整数は2の補数形式で表現され、最上位ビットが符号（0なら+、1なら-）として解釈される。

例えば、32ビットワードにおいて、符号なし整数の値は0から232-1 = 4,294,967,295までであるが、符号あり整数の値は-231 = -2,147,483,648から231-1 = 2,147,483,647までである。

整数オーバーフローが発生すると、実行された演算が示す数学的な値とは異なる値が格納される結果となる。最も一般的には、結果のビットパターンは、演算が2*W*（*W*はビット単位のワードサイズ）を法（modulo）として実行された場合と同じになる。また、演算によってオーバーフローが発生したことを示すフラグが設定（セット）または解除（アンセット）されることもある。GPUやデジタルシグナルプロセッサ（DSP）などの一部のプロセッサでは、飽和演算をサポートしており、オーバーフローした結果は「クランプ」される。すなわち、結果が最小値を下回る場合は表現可能な範囲の最小値に、最大値を上回る場合は最大値に設定される。

プログラマが予期していない場合、整数オーバーフローはプログラムの信頼性やセキュリティに悪影響を及ぼす可能性がある。共通脆弱性タイプでは、CWE-190に分類される。

## 発生原因
整数オーバーフローは、整数に対する算術演算が、指定された桁数で表現できる範囲外の数値を作成しようとしたときに発生する。コンピュータプログラミングの文脈では整数はバイナリであるが、桁（ポジション）が制限されている場合、どのような位取り記数法のシステムであっても算術演算の結果が無効になる可能性がある。オドメーターの例で示したように、十進法を使用し、6桁（数字）の制約がある場合、次の演算は無効な結果となる：。同様に、4桁（ビット）に制限されたバイナリシステムでは、次の演算が無効な結果となる：。どちらの例でも、結果は制約によって表現可能な範囲を超える値となる。この問題を別の視点から見ると、最上位の桁の演算において桁上がりが発生し、割り当てが必要な別の桁/ビットを必要とするため、制約が破られるということである。

コンピュータプログラミングにおけるすべての整数には、最大値と最小値の制約がある。範囲を決定する主な要因は、ビットの割り当てと、それが符号付きか符号なしかである。標準的な整数は、プラットフォームやプログラミング言語によって異なる。標準よりも小さい、あるいは大きい整数の表現も可能である。例としては、それぞれショート整数やロング整数がある。任意精度演算も存在するが、これはあらかじめ設定された精度や利用可能なシステムメモリによって制限される。

符号なし算術演算がNビット整数の最大値を超える結果を生成すると、オーバーフローによって結果は2のN乗を法とする剰余に減じられ、結果の最下位ビットのみが保持される。これは事実上ラップアラウンドを引き起こす。

特に、2つの整数を乗算または加算すると、予想外に小さな値になる可能性があり、小さな整数から減算すると、大きな正の値にラップする可能性がある（例えば、8ビット整数の加算 255 + 2 の結果は1となり、これはである。同様に、減算 0 − 1 の結果は255となり、これは−1の2の補数表現である）。

このようなラップアラウンドは、セキュリティ上の損害を引き起こす可能性がある。オーバーフローした値がバッファ確保のためのバイト数として使用されると、バッファが予想外に小さく割り当てられ、潜在的にバッファオーバーフローにつながる可能性がある。バッファの使用方法によっては、これがさらに任意のコード実行を引き起こす恐れがある。

変数が符号あり整数型の場合、プログラムはその変数が常に正の値を保持していると仮定することがある。整数オーバーフローによって値がラップして負になると、プログラムの仮定に違反し、予期しない動作につながる可能性がある（例えば、8ビット整数の加算 127 + 1 の結果は−128となり、これは128の2の補数である）。（この特定の問題の解決策は、プログラムが負になることはないと期待・仮定する値に対しては、符号なし整数型を使用することである。）

## フラグ
現代のコンピュータの多くは、加算や減算の演算によるオーバーフロー発生時にセットされる専用のプロセッサフラグを備えている。

キャリーフラグは、加算または減算の結果を符号なし数値として考慮した場合に、指定されたビット数に収まらない場合にセットされる。これは、最上位ビットからの桁上がりまたはボローを伴うオーバーフローを示す。

オーバーフローフラグは、符号あり数値の加算または減算の結果が、オペランドの符号から予測される符号と異なる場合（例：2つの正の数を加算して負の結果になる場合）にセットされる。これはオーバーフローが発生し、2の補数形式で表現された符号付きの結果が指定されたビット数に収まらないことを示す。ADD命令の場合、これは符号ビットへのキャリーと符号ビットからのキャリーが異なっていたことを意味する。

## 定義のバリエーションと曖昧さ
符号なし型の場合、演算の理想的な結果がその型の表現可能な範囲外であり、返される結果がラッピングによって得られるとき、この事象は一般にオーバーフローと定義される。対照的に、C言語の標準規格では、この事象はオーバーフローではないと定義しており、「符号なしオペランドを含む計算は決してオーバーフローしない」と述べている。この説明は、標準規格が符号なし整数の算術を、ワードサイズを*W*としたときの2*W*を法とする算術であると定義しているためである。これは数学的に明確に定義されており、表現可能な値のみを持つ。

整数演算の理想的な結果がその型の表現可能な範囲外であり、返される結果がクランプによって得られるとき、この事象は一般に飽和と定義される。飽和をオーバーフローとするか否かは、使用法によって異なる。曖昧さを排除するために、ラッピングオーバーフローおよび飽和オーバーフローという用語を使用することができる。

整数演算が表現可能な最小値よりも小さい値を生成するケースは、時として「整数アンダーフロー」と呼ばれることもあるが、最も一般的にはオーバーフローの一種として知られている。この用法は、浮動小数点値が0に近すぎることを指す浮動小数点アンダーフローとは全く異なる。

## 一貫性のない動作
オーバーフロー発生時の動作は、すべての状況において一貫しているとは限らない。例えば、Rust言語では、ユーザーに選択と制御を与えるための機能が提供されている一方で、基本的な数学演算子の使用における動作は自然に固定されている。しかし、この固定された動作は、デバッグモードでビルドされたプログラムとリリースモードでビルドされたプログラムとで異なる。C言語では、符号なし整数のオーバーフローはラップアラウンドするように定義されているが、符号あり整数のオーバーフローは未定義動作を引き起こす。

## 対処法

### 検出
Cコンパイラでは、実行時のオーバーフロー検出実装である`UBSan`（未定義動作サニタイザー）が利用可能である。

Java 8では、オーバーロードされたメソッド、例えばがあり、これはオーバーフローの場合にをスローする。

CERTは、実行時エラー処理を使用してC/C++における整数オーバーフローと切り捨てを排除するための、ほぼ自動化されたメカニズムであるAIR (As-if Infinitely Ranged) 整数モデルを開発した。

### 回避
計算され格納される可能性のあるすべての値を格納できる十分な大きさのデータ型を持つ変数を割り当てることで、オーバーフローを常に回避できる。プログラミング言語や環境が提供する使用可能なスペースや固定データ型が限られており、十分なサイズで変数を防御的に割り当てることができない場合でも、演算の順序を慎重に決め、オペランドを事前にチェックすることで、結果が決して格納可能な範囲を超えないことを先験的に保証できる場合が多い。静的解析ツール、形式的検証、契約プログラミング技術を使用することで、オーバーフローが誤って発生しないことをより確信を持って堅牢に保証できる。

### ハンドリング
オーバーフローが発生する可能性があると予想される場合、プログラムにテストを挿入して、いつ発生するか、または発生しようとしているかを検出し、それを緩和するための他の処理を行うことができる。例えば、ユーザー入力から計算された重要な結果がオーバーフローする場合、プログラムは無効なオーバーフロー入力で処理を進めて結果として誤動作するのではなく、停止して入力を拒否し、ユーザーに別の入力を求めることができる。

CPUは通常、レジスタサイズより大きな数値の加算をサポートするために、ステータスビットを使用してこれを検出する方法を持っている。この技術は多倍長演算と呼ばれる。したがって、1バイトより広いオペランドに対してバイト単位の加算を行うことが可能である。まず下位バイトを加算して結果を格納し、オーバーフローをチェックする。次に上位バイトを加算し、必要に応じて下位バイトからの「キャリー」を加算して結果を格納する。

計算のオーバーフローの可能性を処理する際、計算を行う「前」にチェックを行うか（オーバーフローが発生するかどうかを判断するため）、計算の「後」にチェックを行うか（結果の値に基づいて発生した可能性が高いかどうかを検討するため）の選択を迫られることがある。一部の実装では整数オーバーフローでトラップ条件を生成する場合があるため、最も移植性の高いプログラムは、オーバーフローする可能性のある演算を実行する前にテストを行う。

### プログラミング言語のサポート
プログラミング言語は、偶発的なオーバーフローに対するさまざまな緩和策を実装している。Adaや関数型言語の一部のバリアントは、オーバーフロー時に例外条件をトリガーするが、Python（2.4以降）は、数値の内部表現をその増加に合わせてシームレスに変換し、最終的に`long`として表現する。この能力は利用可能なメモリによってのみ制限される。

任意精度演算と型安全性をネイティブにサポートする言語（Python、Smalltalk、Common Lispなど）では、オーバーフローが発生すると数値が自動的により大きなサイズに昇格するか、範囲制約が存在する場合は例外がスロー（条件が通知）される。このような言語を使用することは、この問題を緩和するのに役立つ。しかし、そのような言語であっても、整数オーバーフローが発生する可能性のある状況は依然として存在する。例としては、プロファイラによってボトルネックと見なされたコードパスの明示的な最適化がある。Common Lispの場合、変数に格納される整数のサイズがマシンサイズのワード（fixnum）に収まるとプログラマが確信できる場合、型注釈する明示的な宣言を使用し、整数の多倍長への切り替えを抑制させることが可能だが、これは特定のコードブロックに対して型安全性レベルをゼロに下げることで可能になる。前述のように、これは意図されたチューニングであり、オーバーフローやラップアラウンドを目的として型注釈を使用することはない(なお、この場合コードは未定義動作となる)。

C言語のような古い言語とは対照的に、Rustなどの一部の新しい言語は、オーバーフローをどのように処理するかをケースバイケースでユーザーが簡単に選択および検出できる組み込み関数を提供している。Rustでは、基本的な数学演算子の使用には当然そのような柔軟性はないが、ユーザーは代わりに整数プリミティブ型ごとに提供される一連のメソッドを介して計算を実行できる。これらのメソッドは、チェック付き演算（戻り値の型を介してオーバーフローが発生したかどうかを示す）、チェックなし演算、ラッピングを実行する演算、または数値境界で飽和を実行する演算など、いくつかの選択肢をユーザーに提供する。

### 飽和演算
コンピュータグラフィックスや信号処理では、0から1、または-1から1の範囲のデータを扱うのが一般的である。例えば、0が黒、1が白を表し、その間の値がグレーの濃淡を表すグレースケール画像を考える。サポートしたい演算の一つに、すべてのピクセルに定数を掛けて画像を明るくするものがある。飽和演算を使用すると、オーバーフローを心配することなく、すべてのピクセルにその定数を盲目的に掛けることができる。これは、1より大きいすべてのピクセル（つまり「白より明るい」）は単に白になり、「黒より暗い」すべての値は単に黒になるという、妥当な結果に固執することで実現される。

## 実例
予期せぬ算術オーバーフローは、プログラムエラーのかなり一般的な原因である。このようなオーバーフローのバグは発見や診断が難しい場合がある。なぜなら、検証テストで使用される可能性が低い非常に大きな入力データセットに対してのみ発現することがあるためである。

多くの探索アルゴリズムで行われるように、2つの数値を加算して2で割ることで算術平均を取る方法は、合計（結果の平均ではない）が表現するには大きすぎてオーバーフローする場合にエラーを引き起こす。

いわゆる2038年問題は、UNIXにおける時間（UNIX時間）を表現する秒カウンタ型である「time_t型」が、古いシステムでは32bit signed int型として実装されているために発生するオーバーフローに起因するもので、演算内容によっては2038年を待たずに問題が表面化するものもある。

1985年から1987年にかけて、Therac-25放射線治療装置における算術オーバーフローは、ハードウェアの安全制御の欠如と相まって、放射線過剰投与による少なくとも6人の死亡事故を引き起こした。

1996年のアリアン5ロケットの初飛行（アリアン5フライト501）の墜落の主な原因は、エンジンのステアリングソフトウェアにおける処理されていない算術オーバーフローであった。このソフトウェアは以前の多くの飛行で使用されていたためバグはないと考えられていたが、それらはアリアン5よりも加速度が低い小型のロケットを使用していた。苛立たしいことに、オーバーフローエラーが発生したソフトウェア部分は、ロケットを故障させた時点ではアリアン5で実行する必要さえなかった。それは、アリアン5用に適応された際にソフトウェアに残っていた、小型の前身ロケット用の打ち上げ体制プロセスであった。さらに、失敗の真の原因は、オーバーフローが検出されたときのソフトウェアの対処方法に関する工学仕様の欠陥であった。診断ダンプをバスに出力したが、これは開発中のソフトウェアテストではテスト機器に接続されていたものの、飛行中はロケットのステアリングモーターに接続されていた。データダンプによってエンジンノズルが片側に激しく駆動され、ロケットは空力的制御を失い、空中での急速な分解を招いた。

Microsoft Macro Assemblerバージョン1.00、およびおそらく同じPascalコンパイラでビルドされた他のすべてのプログラムには、スタック設定コードに整数オーバーフローと符号属性のエラーがあり、512 KiBを超えるメモリを持ついくつかの一般的な構成の下では、新しいMS-DOSマシンやエミュレータでの実行が妨げられる。プログラムはハングするか、エラーメッセージを表示して終了する。

2015年4月30日、米国連邦航空局（FAA）は、電力損失やラムエア・タービンの展開につながる可能性のある整数オーバーフローを回避するために、ボーイング787の運航者に対して電気システムを定期的にリセットするよう命じると発表した。ボーイングは第4四半期にソフトウェアアップデートを展開した。欧州航空安全機関も2015年5月4日にこれに続いた。このエラーは231百分の一秒（約日）後に発生し、32ビットの符号付き整数を示している。

2016年8月、Resorts Worldカジノにあるカジノマシンが、オーバーフローバグの結果として$42,949,672.76の賞金チケットを印刷した。カジノ側はこれを誤動作と呼び、支払いを拒否した。彼らの主張は、マシンの最大支払額は$10,000であると明確に記載されており、それを超える賞金はプログラミングのバグの結果でなければならないというものであった。New York State Gaming Commissionはカジノ側に有利な判決を下した。

### ビデオゲーム
ファミコン版『スーパーマリオブラザーズ』では、保存される残機数は符号付きバイト（-128から127の範囲）であり、プレイヤーは安全に127機まで持つことができるが、128機目に達するとカウンタが0機にロールオーバーし（数字カウンタはこれが発生する前にグリッチ表示になるが）、カウントを停止する。そのため、その状態でプレイヤーが死ぬと即座にゲームオーバーとなる。これは、開発者が通常のプレイでそこまでの残機数が獲得されるとは考えていなかったため、プログラミングのエラーとしてデータのオーバーフローが発生したことが原因である。

アーケードゲーム『ドンキーコング』では、時間/ボーナス計算における整数オーバーフローのため、レベル22を超えて進むことができない。このゲームは、ユーザーがいるレベル番号に10を掛け、40を加えることで時間/ボーナスを決定する。レベル22に達すると、時間/ボーナスの数値は260になるが、これは8ビットの256値レジスタには大きすぎるため、値4にオーバーフローする。これはレベルをクリアするにはあまりにも短い時間である。

『パックマン』における「キルスクリーン」という現象は整数オーバーフローが原因である。

同様のバグは、『Minecraft』Java EditionのInfdev開発期間からBeta 1.7.3まで存在した「Far Lands（最果ての地）」の原因にもなった（後にBeta 1.8で修正された）。同じバグは『Minecraft』Bedrock Editionにも存在したが、その後修正された。

## 関連項目
* オーバーフロー
* 合同算術

## 外部リンク
*Phrack #60, Basic Integer Overflows
*Phrack #60, Big Loop Integer Protection
*Efficient and Accurate Detection of Integer-based Attacks
*WASC Threat Classification – Integer Overflows
*Understanding Integer Overflow in C/C++
*Binary Overflow – Binary Arithmetic
*ISO C11 Standard

## 脚注