Loading article…
コンピュータプログラミングにおいて、整数オーバーフローとは、整数に対する算術演算が、結果を格納するために割り当てられた領域で表現できる範囲外の数値（表現可能な最大値よりも大きい値、または表現可能な最小値よりも小さい値）を生成しようとしたときに発生する現象である。
現代の計算機における整数演算のほとんどは、整数の二進数表現を用いるが、十進数表現も存在する。本稿では二進数表現に焦点を当てるが、同様の考察は他の場合にも当てはまる。
コンピュータでビットパターンとして表現される整数は、符号なし整数（値が0からある最大値まで）または符号付き整数（値が正または負）のいずれかとして解釈できます。最も一般的には、符号付き整数は2の補数形式で表現され、最上位ビットが符号（+の場合は0、-の場合は1）として解釈されます。たとえば、32ビットワードでは、符号なし整数の値は0から2³² - 1=4,294,967,295までですが、符号付き整数の値は-2³¹=-2,147,483,648から2³¹ - 1 = 2,147,483,647までです。
整数オーバーフローが発生すると、格納される値は、実行された演算によって示される数学的な値とは異なります。最も一般的には、結果として得られるビットパターンは、演算が 2 Wを法として実行された場合と同じです。ここで、Wはビット単位のワードサイズです。また、この演算では、オーバーフローが発生したかどうかを示す 1 つ以上のフラグが設定または解除されます。飽和演算をサポートするグラフィックス処理ユニット(GPU) やデジタル信号プロセッサ(DSP)などの一部のプロセッサでは、オーバーフローした結果がクランプされる場合があります。つまり、結果が表現可能な範囲の最小値より小さい場合は最小値に設定され、結果が表現可能な範囲の最大値より大きい場合は最大値に設定されます。
プログラマーが想定していない場合、整数オーバーフローはプログラムの信頼性とセキュリティに悪影響を与える可能性があります。
整数オーバーフローは、整数に対する算術演算で、指定された桁数で表現できる範囲外の数値を生成しようとしたときに発生します。コンピュータプログラミングの文脈では、整数はバイナリですが、位置が制限されている場合、任意の位置指定式では算術演算の結果が無効になる可能性があります。オドメーターの例で示されているように、 10進数システムを使用し、6桁の制約がある場合、次の演算は無効な結果になります: 999999 + 1。同様に、4桁に制限されたバイナリシステムでは、次の演算の結果が無効になります: 。どちらの例でも、結果は制約によって表現できる範囲を超える値になります。この問題を別の角度から見ると、最上位桁の演算で桁上がりが発生し、別の位置/桁/ビットを割り当てる必要があるため、制約が破られるということです。1111 + 0001
コンピュータプログラミングにおけるすべての整数には、最大値と最小値の制約があります。範囲を決定する主な要因は、ビットの割り当てと、符号付きか符号なしかです。標準整数は、プラットフォームとプログラミング言語によって異なります。標準よりも小さい、または大きい追加の整数表現も存在します。例えば、それぞれ短整数と長整数です。任意精度も存在しますが、これは事前に設定された精度または利用可能なシステムメモリによって制限されます。
符号なし算術演算の結果が、N ビット整数の上記の最大値を超える場合、オーバーフローによって結果が 2 の N 乗の法則に縮小され、結果の最下位ビットのみが保持され、実質的にラップアラウンドが発生します。
特に、2 つの整数を乗算または加算すると、予想外に小さな値になる場合があり、小さな整数から減算すると、大きな正の値にラップアラウンドする場合があります (たとえば、8 ビット整数の加算255 + 2は 1 になりますが、これは 2 を法として 257 になります。同様に、減算0 − 1は 255 になりますが、これは−1 の2 の補数表現です)。
このようなオーバーフローはセキュリティ上の問題を引き起こす可能性があります。オーバーフローした値がバッファに割り当てるバイト数として使用された場合、バッファは予想外に小さく割り当てられ、バッファオーバーフローが発生する可能性があります。バッファの使用方法によっては、これが任意のコード実行につながる可能性があります。
変数が符号付き整数型の場合、プログラムは変数が常に正の値を持つと想定することがあります。整数オーバーフローが発生すると、値がラップアラウンドして負の値になり、プログラムの想定が崩れて予期しない動作を引き起こす可能性があります（例えば、8ビット整数の加算である127 + 1は-128となり、これは128の2の補数表現です）。（この問題の解決策としては、プログラムが負の値にならないと想定する値には符号なし整数型を使用することです。）
現代のほとんどのコンピュータには、加算および減算演算によるオーバーフロー時に設定される専用のプロセッサフラグが備わっています。
キャリーフラグは、オペランドと結果を符号なし数とみなした場合、加算または減算の結果が指定されたビット数に収まらない場合に設定されます。これは、最上位ビットからのキャリーまたは借り入れを伴うオーバーフローを示しています。
オーバーフローフラグは、符号付き数の加算または減算の結果が、オペランドの符号から予測される符号と異なる場合に設定されます。たとえば、2つの正の数を加算して負の結果になった場合などです。これは、オーバーフローが発生し、2の補数形式で表された符号付き結果が指定されたビット数に収まらないことを示しています。ADD命令の場合、これは符号ビットへの桁上げと符号ビットからの桁上げが異なっていたことを意味します。
符号なし型の場合、演算の理想的な結果が型の表現可能な範囲外であり、返される結果がラップによって得られる場合、このイベントは一般的にオーバーフローとして定義されます。対照的に、C 標準では、このイベントはオーバーフローではないと定義されており、「符号なしオペランドを含む計算は決してオーバーフローしない」と述べています。[ 27 ]その理由は、標準では符号なし整数による算術演算を2Wを法とする算術演算と定義しており、Wは数学的に明確に定義され、表現可能な値のみを持つワード サイズです。
整数演算の理想的な結果が型の表現可能な範囲外であり、返される結果がクランプによって得られる場合、このイベントは一般的に飽和として定義されます。飽和がオーバーフローであるか否かについては、使用法が異なります。曖昧さを解消するために、ラッピングオーバーフロー[ 28 ]および飽和オーバーフロー[ 29 ]という用語を使用できます。
整数演算の結果、表現可能な最小値よりも小さい値が生成された場合、整数アンダーフローと呼ばれることもありますが、一般的にはオーバーフローの一種として知られています。[ 30 ]この用法は、浮動小数点値が0に近すぎる場合を指す浮動小数点アンダーフローとは全く異なります。
オーバーフロー発生時の挙動は、すべての状況で一貫しているとは限りません。たとえば、Rust言語では、ユーザーに選択と制御を与える機能が提供されていますが、数学演算子の基本的な使用時の挙動は自然に固定されています。ただし、この固定された挙動は、「デバッグ」モードでビルドされたプログラムと「リリース」モードでビルドされたプログラムで異なります。[ 31 ] C 言語では、符号なし整数オーバーフローはラップアラウンドするように定義されていますが、符号付き整数オーバーフローは未定義の挙動を引き起こします。
Cコンパイラでは、実行時オーバーフロー検出の実装UBSan（未定義動作サニタイザー）が利用可能です。
Java 8 では、オーバーロードされたメソッドがあり、たとえば、オーバーフローが発生した場合にMath.addExact(int, int)例外をスローします。ArithmeticException
コンピュータ緊急対応チーム（CERT）は、実行時エラー処理を使用してC/C++における整数オーバーフローと切り捨てを排除するための、ほぼ自動化されたメカニズムであるAs-if Infinitely Ranged（AIR）整数モデルを開発しました。[ 34 ]
計算および格納される可能性のあるすべての値を格納できる十分な大きさのデータ型を持つ変数を割り当てることで、オーバーフローを常に回避できます。利用可能なスペースやプログラミング言語または環境によって提供される固定データ型が限られているため、十分な大きさの変数を防御的に割り当てることができない場合でも、演算の順序を慎重に決定し、オペランドを事前にチェックすることで、結果が格納可能なサイズを超えることは決してないことを事前に保証できる場合が多くあります。静的解析ツール、形式検証、契約による設計手法を使用することで、オーバーフローが意図せず発生しないことをより確実かつ堅牢に保証できます。
オーバーフローが発生する可能性があると予測される場合は、プログラムにテストを挿入して、オーバーフローが発生したとき、または発生しそうになったときにそれを検知し、それを軽減するための処理を行うことができます。たとえば、ユーザー入力から計算される重要な結果がオーバーフローした場合、プログラムは停止し、入力を拒否し、場合によってはユーザーに別の入力を促すことができます。そうすることで、無効なオーバーフロー入力で処理を続行し、結果として誤動作する可能性を回避できます。
CPUは通常、レジスタサイズを超える数値の加算をサポートするために、ステータスビットなどを用いてこれを検出します。この手法は多倍長演算と呼ばれます。つまり、1バイトよりも大きいオペランドに対してバイト単位の加算を実行することが可能です。まず下位バイトを加算し、結果を格納してオーバーフローをチェックします。次に上位バイトを加算し、必要に応じて下位バイトからの桁上げを加算してから、結果を格納します。
計算でオーバーフローが発生する可能性に対処する際には、計算前にチェックを行う（オーバーフローが発生するかどうかを判断する）か、計算後にチェックを行う（結果の値に基づいてオーバーフローが発生した可能性が高いかどうかを判断する）かの選択を迫られる場合があります。実装によっては整数オーバーフロー時にトラップ条件が発生する可能性があるため、移植性の高いプログラムでは、オーバーフローが発生する可能性のある操作を実行する前にテストを行います。
プログラミング言語は、偶発的なオーバーフローに対するさまざまな緩和方法を実装しています。Adaや特定の関数型言語のバリアントは、オーバーフロー時に例外条件をトリガーしますが、Python (2.4 以降) は、数値の内部表現をシームレスに変換してその増加に対応し、最終的にはlong使用可能なメモリによってのみ制限されるような形で表現します。[ 35 ]
任意精度演算と型安全性をネイティブにサポートする言語( Python、Smalltalk、Common Lispなど) では、オーバーフローが発生すると数値は自動的により大きなサイズに昇格され、範囲制約が存在する場合は例外がスローされます (条件が通知されます)。したがって、このような言語を使用すると、この問題を軽減するのに役立つ場合があります。ただし、このような言語の中には、整数オーバーフローが発生する可能性がある状況がまだ存在する場合があります。たとえば、プロファイラによってボトルネックと見なされるコード パスの明示的な最適化です。Common Lispの場合、明示的な宣言を使用して変数をマシン サイズのワード ( fixnum) [ 36 ]に型注釈し、特定のコード ブロックの型安全性レベルをゼロ[ 37 ]に下げることで、これが可能になります。[ 38 ] [ 39 ] [ 40 ] [ 41 ]
C などの古い言語とは対照的に、Rustなどの新しい言語では、オーバーフローを簡単に検出して、ケースバイケースでどのように処理するかをユーザーが選択できる組み込み関数が提供されています。Rust では、基本的な数学演算子の使用には当然ながらそのような柔軟性はありませんが、ユーザーは代わりに、各整数プリミティブ型によって提供される一連のメソッドを使用して計算を実行できます。これらのメソッドを使用すると、チェックされた(またはオーバーフローする) 操作 (戻り値の型によってオーバーフローが発生したかどうかを示します)、チェックされていない操作、折り返しを実行する操作、または数値境界で飽和を実行する操作など、いくつかの選択肢がユーザーに提供されます。
コンピュータグラフィックスや信号処理では、0から1、または-1から1の範囲のデータを扱うのが一般的です。たとえば、 0が黒、1が白、その間の値がグレーの濃淡を表すグレースケール画像を考えてみましょう。サポートしたい操作の1つとして、各ピクセルに定数を乗算して画像を明るくすることが挙げられます。飽和演算を使用すると、オーバーフローを気にすることなく、各ピクセルに定数を無条件に乗算できます。これは、1より大きい値（「白より明るい」）のピクセルはすべて白になり、「黒より暗い」値はすべて黒になるという妥当な結果に留まるためです。
予期せぬ算術オーバーフローは、プログラムエラーのかなり一般的な原因です。このようなオーバーフローバグは、非常に大きな入力データセットでのみ発生する可能性があり、検証テストで使用される可能性が低いため、発見や診断が難しい場合があります。
多くの検索アルゴリズムで行われているように、2 つの数値を足して 2 で割って算術平均を取ると、合計 (結果として得られる平均ではない) が大きすぎて表現できずオーバーフローする場合にエラーが発生します。[ 42 ]
1985年から1987年の間に、 Therac-25放射線治療装置における演算オーバーフローとハードウェア安全制御の欠如により、少なくとも6人が放射線過剰被曝で死亡した。[ 43 ]
エンジン操舵ソフトウェアで未処理の算術オーバーフローが発生したことが、1996年のアリアン5ロケット初飛行の墜落の主な原因でした。[ 44 ]このソフトウェアは、それまでの多くの飛行で使用されていたため、バグがないと考えられていましたが、それらの飛行では、アリアン5よりも加速の低い小型ロケットが使用されていました。さらに残念なことに、オーバーフローエラーが発生したソフトウェアの部分は、ロケットの失敗を引き起こした時点でアリアン5で実行されている必要すらありませんでした。それは、アリアン5の小型の前身機の打ち上げ手順プロセスであり、新しいロケットに適合させたときにソフトウェアに残っていたものでした。さらに、失敗の真の原因は、オーバーフローが検出されたときにソフトウェアがどのように処理するかというエンジニアリング仕様の欠陥でした。ソフトウェアはバスに診断ダンプを実行しましたが、これは開発中のソフトウェアテスト中はテスト機器に接続されていましたが、飛行中はロケット操舵モーターに接続されていました。データダンプによってエンジンノズルが片側に大きく傾き、ロケットは空力制御を失い、空中での急速な分解を引き起こした。[ 45 ]
Microsoft Macro Assemblerバージョン 1.00、およびおそらく同じPascalコンパイラで作成された他のすべてのプログラムには、スタック設定コードに整数オーバーフローと符号エラーがあり、512 KiB を超えるメモリを持つ一般的な構成では、新しいMS-DOSマシンまたはエミュレータで実行できません 。プログラムはハングするか、エラー メッセージを表示して終了します。[ 46 ]
2015年4月30日、米国連邦航空局は、電力喪失やラムエアタービンの展開につながる可能性のある整数オーバーフローを回避するため、ボーイング787の運航会社に定期的に電気系統をリセットするよう命じると発表し、ボーイングは第4四半期にソフトウェアアップデートを展開した。 [ 47 ]欧州航空安全機関は2015年5月4日にこれに続いた。[ 48 ]このエラーは2 31分の1秒（約249日）後に発生し、32ビットの符号付き整数を示している。
2016年8月、リゾーツワールドカジノのカジノマシンがオーバーフローバグにより42,949,672.76ドルの賞金チケットを印刷した。カジノ側はこの金額の支払いを拒否し、機械に最大支払額が10,000ドルと明記されていたため、それを超える賞金はプログラミングバグによるものだと主張した。ニューヨーク州ゲーミング委員会はカジノ側の主張を認めた。[ 49 ]
ファミコン版『スーパーマリオブラザーズ』では、残機数は符号付きバイト（-128～127）で保存されます。つまり、プレイヤーは安全に127機まで残機を持つことができますが、128機目に達するとカウンターがゼロに戻り（ただし、その前にカウンターに不具合が生じます）、カウントが停止します。そのため、プレイヤーがそこで死亡すると即座にゲームオーバーとなります。これは、開発者が通常のプレイでこれほどの残機数を獲得できるとは想定していなかったため、プログラミング上のエラーであるデータオーバーフローが原因です。
アーケードビデオゲーム「ドンキーコング」では、タイム/ボーナス計算における整数オーバーフローのため、レベル22より先に進むことができません。このゲームでは、プレイヤーが現在いるレベル番号に10を掛け、40を足すことでタイム/ボーナスを決定します。レベル22に到達すると、タイム/ボーナスの値は260になりますが、これは8ビット256値レジスタには大きすぎるため、オーバーフローして4という値になり、レベルをクリアするには短すぎます。
オーバーフローはパックマンの「分割画面」レベルの原因です。[ 50 ]このようなバグは、 Infdev開発期間からBeta 1.7.3まで存在していたMinecraft Java EditionのFar Landsの原因でもあり、後にBeta 1.8で修正されました。同じバグはMinecraft Bedrock Editionにも存在していましたが、その後修正されました。[ 51 ]