JPCERT コーディネーションセンター

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

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

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

JLS §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, Item 12]。

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

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

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

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

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

事前条件テスト

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

static final int safeAdd(int left, int right) throws ArithmeticException {
   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) throws ArithmeticException {
  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) throws ArithmeticException {
  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) throws ArithmeticException {
  if ((left == Integer.MIN_VALUE) && (right == -1)) {
    throw new ArithmeticException("Integer overflow");

  }
  return left / right;
}

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

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

これらのメソッド呼び出しは、ほとんどの 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) throws ArithmeticException {
  return safeAdd(oldAcc, safeMultiply(newVal, scale));
}
適合コード (アップキャスト)

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

public static long intRangeCheck(long value) throws ArithmeticException {
  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) throws ArithmeticException {
  final long res =
    intRangeCheck(((long) oldAcc) + intRangeCheck((long) newVal * (long) scale));
  return (int) res; // safe down-cast
}

この手法は、プリミティブ整数型の中で最も大きな型である 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) throws ArithmeticException {
  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) throws ArithmeticException {
  BigInteger product =
    BigInteger.valueOf(newVal).multiply(BigInteger.valueOf(scale));
  BigInteger res = intRangeCheck(BigInteger.valueOf(oldAcc).add(product));
  return res.intValue(); // safe conversion
}
違反コード (AtomicInteger)

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

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

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

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

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

適合コード (AtomicInteger)

以下の適合コードでは、AtomicInteger クラスの get() メソッドと compareAdnSet() メソッドを使い、スレッド間で共有されている 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; // Increment
      if (itemsInInventory.compareAndSet(old, next)) {
        break;
      }
    } // end while
  } // end nextItem()
}

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

例外

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

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

リスク評価

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

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

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

関連ガイドライン
The CERT C Secure Coding Standard INT32-C. Ensure that operations on signed integers do not result in overflow
The CERT C++ Secure Coding Standard INT32-CPP. Ensure that operations on signed integers do not result in overflow
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)
参考文献
[API 2006] class AtomicInteger
[Bloch 2005] Puzzle 27. Shifty i's
[JLS 2005] §4.2.2, "Integer Operations"
  §15.22, "Bitwise and Logical Operators"
[Seacord 2005] Chapter 5. Integers
[Tutorials 2008] Primitive Data Types
翻訳元

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

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

Top へ

Topへ

最新情報（RSS｜メーリングリスト｜Twitter）