NUM00-J. 整数オーバーフローを検出あるいは防止する

プログラムでは、プリミティブ整数型が提供する整数の範囲を越えるような数学的演算を行ってはならない。『Java 言語仕様』§4.2.2 整数演算 [JLS 2015] には、以下のように記述されている。

いかなる場合であっても、組み込みの整数演算子がオーバーフローやアンダーフローの発生を知らせることはない。整数演算子は、null参照のアンボクシング変換が要求された場合、NullPointerExceptionをスローすることができる。それ以外の場合、例外をスローできる演算子は、右手側オペランドがゼロである場合にArithmeticExceptionをスローする整数除算演算子/と整数剰余演算子%、および、ボクシング変換を必要とするものの、変換を実行するためのメモリが足りない場合にOutOfMemoryErrorをスローするインクリメントおよびデクリメント演算子++と--のみである。

Java 言語仕様の §4.2.1 整数型とその値の記述をもとにした以下の表には、Java における整数型、その表現形式、表現できる範囲について示されている。

型	表現形式	表現できる範囲
byte	8ビット符号付き2の補数表現	−128 から 127
short	16ビット符号付き2の補数表現	−32,768 から 32,767
int	32ビット符号付き2の補数表現	−2,147,483,648 から 2,147,483,647
long	64ビット符号付き2の補数表現	−9,223,372,036,854,775,808 から 9,223,372,036,854,775,807
char	UTF-16のコードユニットを表現する16ビット符号無し整数	\u0000 から \uffff (0 から 65,535)

以下の表は整数演算子と整数オーバーフローの関係についてまとめたものである。

演算子	オーバーフロー		演算子	オーバーフロー		演算子	オーバーフロー		演算子	オーバーフロー
+	Yes		-=	Yes		<<	No		<	No
-	Yes		*=	Yes		>>	No		>	No
*	Yes		/=	Yes		&	No		>=	No
/	Yes		%=	No		|	No		<=	No
%	No		<<=	No		^	No		==	No
++	Yes		>>=	No		~	No		!=	No
--	Yes		&=	No		!	No
=	No		|=	No		Unary +	No
+=	Yes		^=	No		Unary -	Yes

Java の型において表現できる値の範囲は非対称 (最小値の符号を反転させた値は、最大値より1大きい) であるため、単項マイナス演算子を最小値に適用した場合には整数オーバーフローが発生する。引数の絶対値を返すメソッド java.lang.math.abs() に int 型や long 型の最小値を与えた場合にも、整数オーバーフローが発生する。

数学的演算の結果が与えられた整数型で表現できない場合、Java のビルトイン演算子は、オーバーフローの発生を示すことなく演算結果をラップアラウンドさせる。この動作は、間違った計算結果や予期せぬ結果を招く可能性がある。たとえば、実際のシステムにおいて、オーバーフローを適切に扱わなかったために compareTo() メソッドの実装で問題となった例がある。compareTo() メソッドの返り値は、ゼロであるか、符号が正負のどちらであるかにだけ意味があり、その絶対値には意味がない。そのため、思いつきやすいが間違った最適化として、引数同士の引き算の結果を返すという方法が考えられる。しかし、符号の異なる2つの引数に対しては、整数オーバーフローが発生する可能性があり、compareTo() の契約に違反する [Bloch 2008]。

整数オーバーフローを検出するための手法の比較

以下に、意図しない整数オーバーフローを検出するための主な手法を3つ挙げる。

• 事前条件テスト. 各演算子に渡す入力が整数オーバーフローを発生させない範囲に収まっていることを逐一検査する。演算を行った場合に整数オーバーフローが発生することを検出したら、ArithmeticException をスローする。それ以外の場合は演算を実行する。

• アップキャスト. 入力値を、一つ大きなプリミティブ整数型にキャストし、その型で演算を行う。計算途中の値が元の整数型で表現できる範囲に収まっているかを検査し、範囲外の値であれば ArithmeticException をスローする。範囲検査は各演算の後で逐一行わなくてはならないことに注意。複雑な式では、各演算結果の範囲検査を行わないと、アップキャストした型において整数オーバーフローが発生するかもしれない。計算結果は、元の小さい型の変数に代入する前にダウンキャストする。このアプローチは long 型に対しては使えない。なぜならば、long 型はすでに最も大きなプリミティブ整数型であるからである。

• BigInteger. 入力を BigInteger クラスのオブジェクトに変換し、すべての整数演算を BigInteger のメソッドを用いて行う。BigInteger クラスは、Java 標準ライブラリが提供する任意精度の整数型である。このクラスのメソッドで実装されている算術演算はオーバーフローせず、正しい計算結果を返す。そのため、本ルールに適合するには、計算結果を元の小さい整数型に変換するときに1回だけ範囲検査すればよく、計算結果が元の小さい整数型に収まらない場合には ArithmeticException をスローする。

事前条件テストの手法では、算術演算ごとに異なる事前条件を検証する必要がある。その他2つの手法と比較すると、その実装や正しさの検証は難しくなる。

可能な場合にはアップキャストを適用することが推奨される。他の2つの手法と比較して検証内容はより簡潔であり、BigInteger を用いるよりも効率的である。残念ながら、この手法は long 型を含む演算には適用できない。long 型にはアップキャストすべきより大きな整数型が存在しないからである。

3つの手法のなかでは BigInteger が概念的に最も単純である。BigInteger の算術演算はオーバーフローしないからだ。しかし、プリミティブ整数型の演算をすべて、対応するメソッド呼び出しに置き換える必要がある。これは元のコードの意図を分かりにくくするかもしれない。また、BigInteger クラスのオブジェクトに対する操作は元のプリミティブ整数型の演算よりも大幅に効率の悪いものとなる可能性がある。

事前条件テスト

以下のコード例は、int 型の引数に対する算術演算において要求される事前条件テストを示している。int 型以外の整数型に対する事前条件テストも同様である。このコード例では、整数オーバーフローが起こる場合には例外を投げている。適合するエラー処理方法は、これ以外にも考えられる。ArithmeticException は RuntimeException を継承しているため、throws 節を宣言する必要はない。

static final int safeAdd(int left, int right) {
  if (right > 0 ? left > Integer.MAX_VALUE - right
                : left < Integer.MIN_VALUE - right) {
    throw new ArithmeticException("Integer overflow");
  }
  return left + right;
}

static final int safeSubtract(int left, int right) {
  if (right > 0 ? left < Integer.MIN_VALUE + right
                : left > Integer.MAX_VALUE + right) {
    throw new ArithmeticException("Integer overflow");
  }
  return left - right;
}

static final int safeMultiply(int left, int right) {
  if (right > 0 ? left > Integer.MAX_VALUE/right
                  || left < Integer.MIN_VALUE/right
                : (right < -1 ? left > Integer.MIN_VALUE/right
                                || left < Integer.MAX_VALUE/right
                              : right == -1
                                && left == Integer.MIN_VALUE) ) {
    throw new ArithmeticException("Integer overflow");
  }
  return left * right;
}

static final int safeDivide(int left, int right) {
  if ((left == Integer.MIN_VALUE) && (right == -1)) {
    throw new ArithmeticException("Integer overflow");
  }
  return left / right;
}

static final int safeNegate(int a) {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
  return -a;
}
static final int safeAbs(int a) {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
  return Math.abs(a);
}

これらのメソッド呼び出しは、ほとんどの just-in-time (JIT) システムでインライン化されるだろう。

char 型の場合にはこれらの検査を簡素化できる。char 型の取り得る値の範囲は正の値のみであるため、負の値に対する比較演算はすべて省略できる。

違反コード

以下の違反コード例における2つの算術演算はどちらも整数オーバーフローを引き起こす可能性がある。オーバーフローが発生した場合、得られる結果は正しくない。

public static int multAccum(int oldAcc, int newVal, int scale) {
  // オーバーフローが発生するかもしれない
  return oldAcc + (newVal * scale);
}

適合コード (事前条件テスト)

以下の適合コードでは、前述の「事前条件テスト」のセクションで定義した safeAdd() と safeMultiply() メソッドを使って安全な整数演算を行い、計算結果がオーバーフローする場合には ArithmeticException 例外をスローしている。

public static int multAccum(int oldAcc, int newVal, int scale) {
  return safeAdd(oldAcc, safeMultiply(newVal, scale));
}

適合コード (Java 8, Math.*Exact())

以下の適合コードでは、Math クラスに定義された addExact() と multiplyExact() メソッドを使っている。これらのメソッドは Java 8 のリリースで追加されたもので、数学的に正しい値を返すか、ArithmeticException をスローする。Math クラスは subtractExact()、negateExact()、absExact() (Java 15 以降)、divideExact() (Java 18 以降) メソッドも提供している。

public static int multAccum(int oldAcc, int newVal, int scale) {
  return Math.addExact(oldAcc, Math.multiplyExact(newVal, scale));
}

適合コード (アップキャスト)

以下の適合コードは、アップキャストの手法を用いて、long 型の値が int で表現できる範囲にあるかどうかを検査する実装を示している。より小さなプリミティブ整数型における検査も同じように実装することができる。

public static long intRangeCheck(long value) {
  if ((value < Integer.MIN_VALUE) || (value > Integer.MAX_VALUE)) {
    throw new ArithmeticException("Integer overflow");
  }
  return value;
}

public static int multAccum(int oldAcc, int newVal, int scale) {
  final long res = intRangeCheck(
   ((long) oldAcc) + intRangeCheck((long) newVal * (long) scale)
  );
  return (int) res; // 安全なダウンキャスト
}

この手法は、プリミティブ整数型の中で最も大きな型である long 型の値には適用できないことに注意。元の変数が long 型である場合は、アップキャストではなく BigInteger クラスを使った手法を採用するべきである。

適合コード (BigInteger)

以下の適合コードは BigInteger を使ってオーバーフローを検出している。

private static final BigInteger bigMaxInt =
  BigInteger.valueOf(Integer.MAX_VALUE);
private static final BigInteger bigMinInt =
  BigInteger.valueOf(Integer.MIN_VALUE);

public static BigInteger intRangeCheck(BigInteger val) {
  if (val.compareTo(bigMaxInt) == 1 ||
      val.compareTo(bigMinInt) == -1) {
    throw new ArithmeticException("Integer overflow");
  }
  return val;
}

public static int multAccum(int oldAcc, int newVal, int scale) {
  BigInteger product =
    BigInteger.valueOf(newVal).multiply(BigInteger.valueOf(scale));
  BigInteger res =
    intRangeCheck(BigInteger.valueOf(oldAcc).add(product));
  return res.intValue(); // 安全な変換
}

違反コード (AtomicInteger)

AtomicInteger クラスのオブジェクトに対する演算においても、他の整数型に対する演算の場合と同じ整数オーバーフローの問題が発生する。解決法はすでに述べたものと基本的には同じであるが、並行性の問題が対策を複雑にする。まず、time-of-check, time-of-use (TOCTOU) に関する問題を回避しなくてはならない。詳しくは「VNA02-J. 共有変数への複合操作のアトミック性を確保する」を参照のこと。次に、AtomicInteger を使用することで、それにアクセスするスレッドの間に事前発生関係 (happens-before) が発生する。それゆえ、アクセス回数やアクセス順序を変更すると、プログラム全体の実行が変更を受ける可能性がある。その影響を許容できないならば、AtomicInteger へのアクセス回数やアクセス順序が元のコードと変わらないように注意してオーバーフロー検出手法を実装する必要がある。

以下の違反コード例は並行プログラミングに関するユーティリティのコードの一部で、 AtomicInteger を使用している。このユーティリティでは、整数オーバーフローの検査を行っていない。

class InventoryManager {
  private final AtomicInteger itemsInInventory = new AtomicInteger(100);

  //...
  public final void nextItem() {
    itemsInInventory.getAndIncrement();
  }
}

itemsInInventory == Integer.MAX_VALUE の場合に nextItem() メソッドが呼び出されると、itemsInInventory はラップアラウンドして Integer.MIN_VALUE になる可能性がある。

適合コード (AtomicInteger)

以下の適合コードでは、AtomicInteger クラスの get() メソッドと compareAndSet() メソッドを使い、スレッド間で共有されている itemsInInventory の値が正しく操作されることを保証している。この方法には以下のような特徴がある。

• itemsInInventory へのアクセス回数とアクセス順序は元の違反コードと同じである。
• itemsInInventory の値に対するすべての操作は一時的なローカルコピーに対して行われる。
• このコード例でのオーバーフロー検査は、メソッド呼び出しではなくインラインコードで行っている。このように、インラインで行う方法もある。メソッド呼び出しにするかインラインコードにするかの選択は、各組織のコーディング規約や必要性に応じて行われるべきである。

class InventoryManager {
  private final AtomicInteger itemsInInventory =
      new AtomicInteger(100);

  public final void nextItem() {
    while (true) {
      int old = itemsInInventory.get();
      if (old == Integer.MAX_VALUE) {
        throw new ArithmeticException("Integer overflow");
      }
      int next = old + 1; // インクリメント
      if (itemsInInventory.compareAndSet(old, next)) {
        break;
      }
    } // while の終わり
  } // nextItem() の終わり
}

compareAndSet() メソッドの2つの引数は、メソッドを呼び出した時点で期待される値と新しく設定したい値である。変数の値は、現在の値と期待される値が一致する場合にのみ、変更される [API 2006] (詳細については「VNA02-J. 共有変数への複合操作のアトミック性を確保する」を参照のこと)。

例外

NUM00-J-EX0: 状況によるが、整数オーバーフローが発生してもよい場合もある。たとえば、ハッシュ値を計算する多くのアルゴリズムは剰余演算を行っており、オーバーフローの発生を意図的に許している。このような場合、問題がないことを明記しなければならない。

NUM00-J-EX1: ビット演算のみを行い、算術演算を行わない場合は、整数オーバーフローの発生防止は不要である (詳細は、「NUM01-J. 同一のデータに対してビット演算と算術演算の両方を行わない」を参照のこと)。

リスク評価

範囲検査を適切に行わないと、整数オーバーフローが発生し、プログラムの予期せぬ制御フローや想定外の動作を招く可能性がある。

ルール	深刻度	可能性	自動検出	自動修正	優先度	レベル
NUM00-J	中	低	不可	不可	P2	L3

自動検出

オーバーフローが発生する可能性のある整数演算の自動検出は容易である。しかし、発生しうる整数オーバーフローが、純粋なコーディングエラーなのか、プログラマが意図したものなのかを自動判別することは不可能である。ヒューリスティックな警告メッセージは役に立つかもしれない。

ツール	バージョン	チェッカー	説明
CodeSonar	9.0p0	JAVA.MATH.ABSRAND JAVA.ARITH.OFLOW	Abs on random Cast: int computation to long
Coverity	7.5	BAD_SHIFT OVERFLOW_BEFORE_WIDEN	Implemented
Klocwork	2025.2	SV.INT_OVF
Parasoft Jtest	2025.2	CERT.NUM00.ICO CERT.NUM00.BSA CERT.NUM00.CACO	Avoid calculations which result in overflow or NaN Do not use an integer outside the range of [0, 31] as the amount of a shift Avoid using compound assignment operators in cases which may cause overflow
PVS-Studio	7.40	V5308, V6117, V6130, V6131

関連ガイドライン

SEI CERT C コーディングスタンダード	INT32-C. 符号付き整数演算がオーバーフローを引き起こさないことを保証する
ISO/IEC TR 24772:2010	Wrap-around Error [XYY]
MITRE CWE	CWE-682, Incorrect Calculation CWE-190, Integer Overflow or Wraparound CWE-191, Integer Underflow (Wrap or Wraparound)

実装の詳細 (Android)

Mezzofanti for Android には整数オーバーフローにより大きい SD カードを使えない問題があった。Mezzofanti には以下のような式があった。

(int) StatFs.getAvailableBlocks() * (int) StatFs.getBlockSize()

この式は SD カードの利用可能な容量を計算するためのもので、利用可能な容量が Integer.MAX_VALUE より大きい場合に負の値を返す可能性があった。なお、これらのメソッドは API レベル18で非推奨となり、getAvailableBlocksLong() と getBlockSizeLong() に置き換えられた。

参考文献

[API 2006]	Class AtomicInteger
[Bloch 2005]	Puzzle 27, "Shifty i's"
[Bloch 2008]	Item 12, "Minimize the Accessibility of Classes and Members"
[Java Tutorials]	Primitive Data Types
[JLS 2015]	§4.2.1, "Integral Types and Values" §4.2.2, "Integer Operations" §15.22, "Bitwise and Logical Operators"
[Seacord 2005]	Chapter 5, "Integers"
[Seacord 2015]	IDS17-J. Prevent XML External Entity Attacks LiveLesson

翻訳元

これは以下のページを翻訳したものです。

NUM00-J. Detect or prevent integer overflow (revision 269)

Top へ