整数オーバーフロー
From Wikipedia, the free encyclopedia
整数オーバーフロー（せいすうオーバーフロー、英語: integer overflow）とは、コンピュータプログラミングにおいて、整数に対する算術演算によって、その結果を格納するために割り当てられた空間で表現可能な範囲外の数値（最大値より大きい、または最小値より小さい）を作成しようとしたときに発生する現象である。
現代の計算における整数の算術演算のほとんどは整数のバイナリ（二進法）表現を使用しているが、十進法表現も存在する。本記事では主にバイナリ表現について扱うが、他のケースでも同様の考慮事項が当てはまる。
コンピュータ内でビットパターンとして表現される整数は、「符号なし整数」（値が0からある最大値まで）または「符号あり整数」（値が正または負）のいずれかとして解釈できる。最も一般的には、符号あり整数は2の補数形式で表現され、最上位ビットが符号（0なら+、1なら-）として解釈される。
例えば、32ビットワードにおいて、符号なし整数の値は0から232-1 = 4,294,967,295までであるが、符号あり整数の値は-231 = -2,147,483,648から231-1 = 2,147,483,647までである。
整数オーバーフローが発生すると、実行された演算が示す数学的な値とは異なる値が格納される結果となる。最も一般的には、結果のビットパターンは、演算が2W（Wはビット単位のワードサイズ）を法（modulo）として実行された場合と同じになる。また、演算によってオーバーフローが発生したことを示すフラグが設定（セット）または解除（アンセット）されることもある。GPUやデジタルシグナルプロセッサ（DSP）などの一部のプロセッサでは、飽和演算をサポートしており、オーバーフローした結果は「クランプ」される。すなわち、結果が最小値を下回る場合は表現可能な範囲の最小値に、最大値を上回る場合は最大値に設定される。
プログラマが予期していない場合、整数オーバーフローはプログラムの信頼性やセキュリティに悪影響を及ぼす可能性がある。共通脆弱性タイプでは、CWE-190に分類される[1]。
フラグ
現代のコンピュータの多くは、加算や減算の演算によるオーバーフロー発生時にセットされる専用のプロセッサフラグを備えている。
キャリーフラグは、加算または減算の結果を符号なし数値として考慮した場合に、指定されたビット数に収まらない場合にセットされる。これは、最上位ビットからの桁上がりまたはボローを伴うオーバーフローを示す。
オーバーフローフラグは、符号あり数値の加算または減算の結果が、オペランドの符号から予測される符号と異なる場合（例：2つの正の数を加算して負の結果になる場合）にセットされる。これはオーバーフローが発生し、2の補数形式で表現された符号付きの結果が指定されたビット数に収まらないことを示す。ADD命令の場合、これは符号ビットへのキャリーと符号ビットからのキャリーが異なっていたことを意味する。
定義のバリエーションと曖昧さ
符号なし型の場合、演算の理想的な結果がその型の表現可能な範囲外であり、返される結果がラッピングによって得られるとき、この事象は一般にオーバーフローと定義される。対照的に、C言語の標準規格では、この事象はオーバーフローではないと定義しており、「符号なしオペランドを含む計算は決してオーバーフローしない」と述べている[28]。この説明は、標準規格が符号なし整数の算術を、ワードサイズをWとしたときの2Wを法とする算術であると定義しているためである。これは数学的に明確に定義されており、表現可能な値のみを持つ。
整数演算の理想的な結果がその型の表現可能な範囲外であり、返される結果がクランプによって得られるとき、この事象は一般に飽和と定義される。飽和をオーバーフローとするか否かは、使用法によって異なる。曖昧さを排除するために、ラッピングオーバーフロー[29]および飽和オーバーフロー[30]という用語を使用することができる。
整数演算が表現可能な最小値よりも小さい値を生成するケースは、時として「整数アンダーフロー」と呼ばれることもあるが、最も一般的にはオーバーフローの一種として知られている[31]。この用法は、浮動小数点値が0に近すぎることを指す浮動小数点アンダーフローとは全く異なる。
一貫性のない動作
対処法
| 言語 | 符号なし整数 | 符号あり整数 |
|---|---|---|
| Ada | 型の法（modulus）で剰余 | raise Constraint_Error |
| C, C++ | 2の冪乗で剰余 | 未定義動作 |
| C# | uncheckedコンテキストでは2の冪乗で剰余; checkedコンテキストではSystem.OverflowExceptionが発生[33] | |
| Java | 2の冪乗で剰余 (charがJavaにおける唯一の符号なしプリミティブ型) | 2の冪乗で剰余 |
| JavaScript | 新しいBigIntを除き、すべての数値は倍精度浮動小数点数である | |
| MATLAB | 組み込み整数は飽和する。固定小数点整数はラップまたは飽和するように設定可能 | |
| Python 2 | N/A | long型 (bigint) に変換 |
| Scheme | N/A | bigNumに変換 |
| Simulink | ラップまたは飽和するように設定可能 | |
| Smalltalk | N/A | LargeIntegerに変換 |
| Swift | 特別なオーバーフロー演算子を使用しない限りエラーとなる[34] | |
検出
Cコンパイラでは、実行時のオーバーフロー検出実装であるUBSan（未定義動作サニタイザー）が利用可能である。
Java 8では、オーバーロードされたメソッド、例えばMath.addExact(int, int)があり、これはオーバーフローの場合にArithmeticExceptionをスローする。
CERTは、実行時エラー処理を使用してC/C++における整数オーバーフローと切り捨てを排除するための、ほぼ自動化されたメカニズムであるAIR (As-if Infinitely Ranged) 整数モデルを開発した[35]。
回避
計算され格納される可能性のあるすべての値を格納できる十分な大きさのデータ型を持つ変数を割り当てることで、オーバーフローを常に回避できる。プログラミング言語や環境が提供する使用可能なスペースや固定データ型が限られており、十分なサイズで変数を防御的に割り当てることができない場合でも、演算の順序を慎重に決め、オペランドを事前にチェックすることで、結果が決して格納可能な範囲を超えないことを先験的に保証できる場合が多い。静的解析ツール、形式的検証、契約プログラミング技術を使用することで、オーバーフローが誤って発生しないことをより確信を持って堅牢に保証できる。
ハンドリング
オーバーフローが発生する可能性があると予想される場合、プログラムにテストを挿入して、いつ発生するか、または発生しようとしているかを検出し、それを緩和するための他の処理を行うことができる。例えば、ユーザー入力から計算された重要な結果がオーバーフローする場合、プログラムは無効なオーバーフロー入力で処理を進めて結果として誤動作するのではなく、停止して入力を拒否し、ユーザーに別の入力を求めることができる。
CPUは通常、レジスタサイズより大きな数値の加算をサポートするために、ステータスビットを使用してこれを検出する方法を持っている。この技術は多倍長演算と呼ばれる。したがって、1バイトより広いオペランドに対してバイト単位の加算を行うことが可能である。まず下位バイトを加算して結果を格納し、オーバーフローをチェックする。次に上位バイトを加算し、必要に応じて下位バイトからの「キャリー」を加算して結果を格納する。
計算のオーバーフローの可能性を処理する際、計算を行う「前」にチェックを行うか（オーバーフローが発生するかどうかを判断するため）、計算の「後」にチェックを行うか（結果の値に基づいて発生した可能性が高いかどうかを検討するため）の選択を迫られることがある。一部の実装では整数オーバーフローでトラップ条件を生成する場合があるため、最も移植性の高いプログラムは、オーバーフローする可能性のある演算を実行する前にテストを行う。
プログラミング言語のサポート
プログラミング言語は、偶発的なオーバーフローに対するさまざまな緩和策を実装している。Adaや関数型言語の一部のバリアントは、オーバーフロー時に例外条件をトリガーするが、Python（2.4以降）は、数値の内部表現をその増加に合わせてシームレスに変換し、最終的にlongとして表現する。この能力は利用可能なメモリによってのみ制限される[36]。
任意精度演算と型安全性をネイティブにサポートする言語（Python、Smalltalk、Common Lispなど）では、オーバーフローが発生すると数値が自動的により大きなサイズに昇格するか、範囲制約が存在する場合は例外がスロー（条件が通知）される。このような言語を使用することは、この問題を緩和するのに役立つ。しかし、そのような言語であっても、整数オーバーフローが発生する可能性のある状況は依然として存在する。例としては、プロファイラによってボトルネックと見なされたコードパスの明示的な最適化がある。Common Lispの場合、変数に格納される整数のサイズがマシンサイズのワード（fixnum）に収まるとプログラマが確信できる場合、型注釈する明示的な宣言を使用し、整数の多倍長への切り替えを抑制させることが可能だが[37]、これは特定のコードブロックに対して型安全性レベルをゼロに下げることで可能になる[38][39][40][41][42]。前述のように、これは意図されたチューニングであり、オーバーフローやラップアラウンドを目的として型注釈を使用することはない(なお、この場合コードは未定義動作となる)。
C言語のような古い言語とは対照的に、Rustなどの一部の新しい言語は、オーバーフローをどのように処理するかをケースバイケースでユーザーが簡単に選択および検出できる組み込み関数を提供している。Rustでは、基本的な数学演算子の使用には当然そのような柔軟性はないが、ユーザーは代わりに整数プリミティブ型ごとに提供される一連のメソッドを介して計算を実行できる。これらのメソッドは、チェック付き演算（戻り値の型を介してオーバーフローが発生したかどうかを示す）、チェックなし演算、ラッピングを実行する演算、または数値境界で飽和を実行する演算など、いくつかの選択肢をユーザーに提供する。
飽和演算
コンピュータグラフィックスや信号処理では、0から1、または-1から1の範囲のデータを扱うのが一般的である。例えば、0が黒、1が白を表し、その間の値がグレーの濃淡を表すグレースケール画像を考える。サポートしたい演算の一つに、すべてのピクセルに定数を掛けて画像を明るくするものがある。飽和演算を使用すると、オーバーフローを心配することなく、すべてのピクセルにその定数を盲目的に掛けることができる。これは、1より大きいすべてのピクセル（つまり「白より明るい」）は単に白になり、「黒より暗い」すべての値は単に黒になるという、妥当な結果に固執することで実現される。
実例
予期せぬ算術オーバーフローは、プログラムエラーのかなり一般的な原因である。このようなオーバーフローのバグは発見や診断が難しい場合がある。なぜなら、検証テストで使用される可能性が低い非常に大きな入力データセットに対してのみ発現することがあるためである。
多くの探索アルゴリズムで行われるように、2つの数値を加算して2で割ることで算術平均を取る方法は、合計（結果の平均ではない）が表現するには大きすぎてオーバーフローする場合にエラーを引き起こす[43]。
いわゆる2038年問題は、UNIXにおける時間（UNIX時間）を表現する秒カウンタ型である「time_t型」が、古いシステムでは32bit signed int型として実装されているために発生するオーバーフローに起因するもので、演算内容によっては2038年を待たずに問題が表面化するものもある。
1985年から1987年にかけて、Therac-25放射線治療装置における算術オーバーフローは、ハードウェアの安全制御の欠如と相まって、放射線過剰投与による少なくとも6人の死亡事故を引き起こした[44]。
1996年のアリアン5ロケットの初飛行（アリアン5フライト501）の墜落の主な原因は、エンジンのステアリングソフトウェアにおける処理されていない算術オーバーフローであった[45]。このソフトウェアは以前の多くの飛行で使用されていたためバグはないと考えられていたが、それらはアリアン5よりも加速度が低い小型のロケットを使用していた。苛立たしいことに、オーバーフローエラーが発生したソフトウェア部分は、ロケットを故障させた時点ではアリアン5で実行する必要さえなかった。それは、アリアン5用に適応された際にソフトウェアに残っていた、小型の前身ロケット用の打ち上げ体制プロセスであった。さらに、失敗の真の原因は、オーバーフローが検出されたときのソフトウェアの対処方法に関する工学仕様の欠陥であった。診断ダンプをバスに出力したが、これは開発中のソフトウェアテストではテスト機器に接続されていたものの、飛行中はロケットのステアリングモーターに接続されていた。データダンプによってエンジンノズルが片側に激しく駆動され、ロケットは空力的制御を失い、空中での急速な分解を招いた[46]。
Microsoft Macro Assemblerバージョン1.00、およびおそらく同じPascalコンパイラでビルドされた他のすべてのプログラムには、スタック設定コードに整数オーバーフローと符号属性のエラーがあり、512 KiBを超えるメモリを持ついくつかの一般的な構成の下では、新しいMS-DOSマシンやエミュレータでの実行が妨げられる。プログラムはハングするか、エラーメッセージを表示して終了する[47]。
2015年4月30日、米国連邦航空局（FAA）は、電力損失やラムエア・タービンの展開につながる可能性のある整数オーバーフローを回避するために、ボーイング787の運航者に対して電気システムを定期的にリセットするよう命じると発表した。ボーイングは第4四半期にソフトウェアアップデートを展開した[48]。欧州航空安全機関も2015年5月4日にこれに続いた[49]。このエラーは231百分の一秒（約249日）後に発生し、32ビットの符号付き整数を示している。
2016年8月、Resorts Worldカジノにあるカジノマシンが、オーバーフローバグの結果として$42,949,672.76の賞金チケットを印刷した。カジノ側はこれを誤動作と呼び、支払いを拒否した。彼らの主張は、マシンの最大支払額は$10,000であると明確に記載されており、それを超える賞金はプログラミングのバグの結果でなければならないというものであった。New York State Gaming Commissionはカジノ側に有利な判決を下した[50]。
ビデオゲーム
ファミコン版『スーパーマリオブラザーズ』では、保存される残機数は符号付きバイト（-128から127の範囲）であり、プレイヤーは安全に127機まで持つことができるが、128機目に達するとカウンタが0機にロールオーバーし（数字カウンタはこれが発生する前にグリッチ表示になるが）、カウントを停止する。この状態でプレイヤーが死ぬと即座にゲームオーバーとなる。
アーケードゲーム『ドンキーコング』では、時間/ボーナス計算における整数オーバーフローのため、レベル22を超えて進むことができない。このゲームは、ユーザーがいるレベル番号に10を掛け、40を加えることで時間/ボーナスを決定する。レベル22に達すると、時間/ボーナスの数値は260になるが、これは8ビットの256値レジスタには大きすぎるため、値4にオーバーフローする。
『パックマン』における「キルスクリーン」という現象は整数オーバーフローが原因である[51]。
『Minecraft』では、Java EditionのInfdev開発期間からBeta 1.7.3まで存在した「Far Lands（最果ての地）」やBedrock Editionで整数オーバーフローが発生していたが、その後修正された[52]。