Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: wordsmithing from JPCERT comments

...

Programs

...

must

...

not

...

allow

...

mathematical

...

operations

...

to exceed the integer ranges provided by their primitive integer data types. According to the Java Language Specification (JLS),

...

§4.2.2,

...

"Integer

...

Operations"

The built-in

...

integer

...

operators

...

do

...

not

...

indicate

...

overflow

...

or

...

underflow

...

in

...

any

...

way.

...

Integer

...

operators

...

can

...

throw

...

a

...

NullPointerException

...

if

...

unboxing

...

conversion

...

of

...

a

...

null

...

reference

...

is

...

required.

...

Other

...

than

...

that,

...

the

...

only

...

integer

...

operators

...

that

...

can

...

throw

...

an

...

exception

...

are

...

the

...

integer

...

divide

...

operator

...

/

...

and

...

the

...

integer

...

remainder

...

operator

...

%

...

,

...

which

...

throw

...

an

...

ArithmeticException

...

if

...

the

...

right-hand

...

operand

...

is

...

zero,

...

and

...

the

...

increment

...

and

...

decrement

...

operators

...

+

...

+

...

and

...

-

...

-

...

which

...

can

...

throw

...

an

...

OutOfMemoryError

...

if

...

boxing

...

conversion

...

is

...

required

...

and

...

there

...

is

...

not

...

sufficient

...

memory

...

available

...

to

...

perform

...

the

...

conversion.

...

The integral types in Java, representation, and inclusive ranges are shown in the following table JLS §4.2.1,

...

"Integral

...

Types

...

and

...

Values"

...

:

Type

Representation

Inclusive Range

byte

8-bit signed two's-complement

...

-128

...

to

...

127

short

16-bit

...

signed

...

two's-complement

...

-32,768

...

to

...

32,767

...

int

32-bit

...

signed

...

two's-complement

...

-2,147,483,648

...

to

...

2,147,483,647

...

long

64-bit

...

signed

...

two's-complement

...

-9,223,372,036,854,775,808

...

to

...

9,223,372,036,854,775,807

...

char

16-bit

...

unsigned

...

unsigned

...

integers

...

representing

...

UTF-16

...

code

...

units

...

\u0000

...

to

...

\uffff

...

(0

...

to

...

65,535)

...

The

...

table

...

below

...

shows

...

the

...

integer

...

overflow

...

behavior

...

of

...

the

...

integral

...

operators.

...

Operator

Overflow

 

Operator

Overflow

 

Operator

Overflow

 

Operator

Overflow

+

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

Because the ranges of Java types are not symmetrical (the negation of minimum value is one more than each maximum value), even operations like unary negation can overflow, if applied to a minimum value. Because the java.lang.math.abs()

...

function returns

...

the

...

absolute

...

value

...

on

...

any

...

number,

...

it

...

can

...

also

...

overflow

...

if

...

given

...

the

...

minimum

...

int

...

or

...

long

...

as

...

an

...

argument.

...

Wiki Markup
When a mathematical operation cannot be represented using the supplied integer types, Java's built-in integer operators silently wrap the result, without indicating overflow. This can result in incorrect computations and unanticipated outcomes. Failure to account for integer overflow has resulted in failures of real systems, for example, when implementing the {{compareTo()}} method. The meaning of the return value of the {{compareTo()}} method is defined only in terms of its sign and whether it is zero; the magnitude of the return value is irrelevant. Consequently, an apparent but incorrect optimization would be to subtract the operands and return the result. For operands of opposite signs, this can result in integer overflow, consequently violating the {{compareTo()}} contract \[[Bloch 2008, Item 12|AA. Bibliography#Bloch 08]\].

...

Comparison

...

of

...

Compliant

...

Techniques

...

The

...

three

...

main

...

techniques

...

for

...

detecting

...

unintended

...

integer

...

overflow

...

are

...

  • Pre-condition

...

  • testing.

...

  • Check

...

  • the

...

  • inputs

...

  • to

...

  • each

...

  • arithmetic

...

  • operator

...

  • to

...

  • ensure

...

  • that

...

  • overflow

...

  • cannot

...

  • occur.

...

  • Throw

...

  • an

...

  • ArithmeticException

...

  • when

...

  • the

...

  • operation

...

  • would

...

  • overflow

...

  • if

...

  • it

...

  • were

...

  • performed;

...

  • otherwise,

...

  • perform

...

  • the

...

  • operation.

...

  • Upcasting.

...

  • Cast

...

  • the

...

  • inputs

...

  • to

...

  • the

...

  • next

...

  • larger

...

  • primitive

...

  • integer

...

  • type

...

  • and

...

  • perform

...

  • the

...

  • arithmetic

...

  • in

...

  • the

...

  • larger

...

  • size.

...

  • Check

...

  • each

...

  • intermediate

...

  • result

...

  • for

...

  • overflow

...

  • of

...

  • the

...

  • original

...

  • smaller

...

  • type

...

  • and

...

  • throw

...

  • an

...

  • ArithmeticException

...

  • if

...

  • the

...

  • range

...

  • check

...

  • fails.

...

  • Note

...

  • that

...

  • the

...

  • range

...

  • check

...

  • must

...

  • be

...

  • performed

...

  • after

...

  • each

...

  • arithmetic

...

  • operation;

...

  • larger

...

  • expressions

...

  • without

...

  • per-operation

...

  • bounds

...

  • checking

...

  • can

...

  • overflow

...

  • the

...

  • larger

...

  • type.

...

  • Downcast

...

  • the

...

  • final

...

  • result

...

  • to

...

  • the

...

  • original

...

  • smaller

...

  • type

...

  • before

...

  • assigning

...

  • to

...

  • the

...

  • result

...

  • variable.

...

  • This

...

  • approach

...

  • cannot

...

  • be

...

  • used

...

  • for

...

  • type

...

  • long

...

  • because

...

  • long

...

  • is

...

  • already

...

  • the

...

  • largest

...

  • primitive

...

  • integer

...

  • type.
  • BigInteger. Convert the inputs into objects of type BigInteger and perform all arithmetic using BigInteger methods. Type BigInteger is the standard arbitrary-precision integer type provided by the Java standard libraries. The arithmetic operations implemented as methods of this type cannot overflow; instead, they produce the numerically correct result. As a consequence, compliant code only performs a single range check just before converting the final result to the original smaller type and throwing an ArithmeticException if the final result is outside the range of the original smaller type.

The pre-condition testing technique requires different pre-condition tests for each arithmetic operation. This can be somewhat more difficult to implement and to audit than either of the other two approaches.

The upcast technique is the preferred approach when applicable. The checks it requires are simpler than those of the previous technique; it is substantially more efficient than using BigInteger. Unfornately it cannot be applied to operations involving the biggest type long, as there is no bigger type to upcast to.

The BigInteger technique is conceptually the simplest of the three techniques because arithmetic operations on BigInteger cannot overflow. However, it requires the use of method calls for each operation in place of primitive arithmetic operators; this can obscure the intended meaning of the code. Operations on objects of type BigInteger can also be significantly less efficient than operations on the original primitive integer type.

Pre-Condition Testing

The following code example shows the necessary pre-condition checks required for each arithmetic operation on arguments of type int. The checks for the other integral types are analogous. In this example, we choose to throw an exception when integer overflow would occur; any other error handling is also acceptable.

Code Block
bgColor#ccccff


* {{{*}BigInteger{*}{}}}*.* Convert the inputs into objects of type {{BigInteger}} and perform all arithmetic using {{BigInteger}} methods. Type {{BigInteger}} is the standard arbitrary-precision integer type provided by the Java standard libraries. The arithmetic operations implemented as methods of this type cannot overflow; instead, they produce the numerically correct result. As a consequence, compliant code only performs a single range check just before converting the final result to the original smaller type and throwing an {{ArithmeticException}} if the final result is outside the range of the original smaller type.

The pre-condition testing technique requires different pre-condition tests for each arithmetic operation. This can be somewhat more difficult to implement and to audit than either of the other two approaches.

The upcast technique is the preferred approach for the cases to which it applies. The checks it requires are simpler than those of the previous technique; it is substantially more efficient than using {{BigInteger}}.

The {{BigInteger}} technique is conceptually the simplest of the three techniques because arithmetic operations cannot overflow. However, it requires the use of method calls for each operation in place of primitive arithmetic operators; this can obscure the intended meaning of the code. Operations on objects of type {{BigInteger}} can also be significantly less efficient than operations on the original primitive integer type.

h2. Pre-Condition Testing

The following code example shows the necessary pre-condition checks required for each arithmetic operation on arguments of type {{int}}. The checks for the other integral types are analogous. In this example, we choose to throw an exception when integer overflow would occur; any other error handling is also acceptable.

{code:bgColor=#ccccff}
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);
}
{code}

These

...

method

...

calls

...

are

...

likely

...

to

...

be

...

inlined

...

by

...

most

...

JITs.

...

These

...

checks

...

can

...

be

...

simplified

...

when

...

the

...

original

...

type

...

is

...

char

...

.

...

Because

...

the

...

range

...

of

...

type

...

char

...

includes

...

only

...

positive

...

values,

...

all

...

comparisons

...

with

...

negative

...

values

...

may

...

be

...

omitted.

Noncompliant Code Example

Either operation in this noncompliant code example could produce a result that overflows the range of int. When overflow occurs, the result will be incorrect.

Code Block
bgColor#FFcccc



h1. Noncompliant Code Example

Either operation in this noncompliant code example could produce a result that overflows the range of {{int}}. When overflow occurs, the result will be incorrect.

{code:bgColor=#FFcccc}
public static int multAccum(int oldAcc, int newVal, int scale) {
  // May result in overflow
  return oldAcc + (newVal * scale);
}
{code}

h2. Compliant Solution 

Compliant Solution (Pre-Condition

...

Testing)

...

This

...

compliant

...

solution

...

uses

...

the

...

safeAdd()

...

and

...

safeMultiply()

...

methods

...

defined

...

in

...

the

...

Pre-condition

...

testing

...

section

...

to

...

perform

...

secure

...

integral

...

operations

...

or

...

throw

...

ArithmeticException

...

on

...

overflow.

{:=
Code Block
bgColor
#ccccff
}
public static int multAccum(int oldAcc, int newVal, int scale) throws ArithmeticException {
  return safeAdd(oldAcc, safeMultiply(newVal, scale));
}
{code}

h2. Compliant Solution 

Compliant Solution (Upcasting)

...

This

...

compliant

...

solution

...

shows

...

the

...

implementation

...

of

...

a

...

method

...

for

...

checking

...

whether a long value falls within the representable range of an int using the upcasting technique. The implementations of range checks for the smaller primitive integer types are similar.

Code Block
bgColor#ccccff
 a {{long}} value falls within the representable range of an {{int}} using the upcasting technique. The implementations of range checks for the smaller primitive integer types are similar.

{code:bgColor=#ccccff}
public static long intRangeCheck(long value) throws ArithmeticOverflow {
  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
}
{code}

Note

...

that

...

this

...

approach

...

cannot

...

be

...

applied

...

for

...

type

...

long

...

because

...

long

...

is

...

the

...

largest

...

primitive

...

integral

...

type.

...

When

...

the

...

original

...

variables

...

are

...

of

...

type

...

long

...

,

...

use

...

the

...

BigInteger

...

technique

...

instead.

...

Compliant

...

Solution

...

(

...

BigInteger

...

)

...

This

...

compliant

...

solution

...

uses

...

the

...

BigInteger

...

technique

...

to

...

detect

...

overflow.

{:=
Code Block
bgColor
#ccccff
}
private static final BigInteger bigMaxInt = BigInteger.valueOf(Int.MAX_VALUE);
private static final BigInteger bigMinInt = BigInteger.valueOf(Int.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
}
{code}

h1. Noncompliant Code Example {{AtomicInteger}}

Operations on objects of type {{AtomicInteger}} suffer from the same overflow issues as other integer types. The solutions are generally similar to the solutions already presented; however, concurrency issues add additional complications. First, potential issues with 

Noncompliant Code Example AtomicInteger

Operations on objects of type AtomicInteger suffer from the same overflow issues as other integer types. The solutions are generally similar to the solutions already presented; however, concurrency issues add additional complications. First, potential issues with time-of-check-time-of-use

...

must

...

be

...

avoided;

...

see

...

guideline

...

VNA02-J.

...

Ensure

...

that

...

compound

...

operations

...

on

...

shared

...

variables

...

are

...

atomic

...

for

...

more

...

information.

...

Second,

...

use

...

of

...

an AtomicInteger creates happens-before

...

relationships

...

between

...

the

...

various

...

threads

...

that

...

access

...

it.

...

Consequently,

...

changes

...

to

...

the

...

number

...

of accesses or

...

order

...

of

...

accesses

...

can

...

alter

...

the

...

execution

...

of

...

the

...

overall

...

program.

...

In

...

such

...

cases,

...

you

...

must

...

either

...

choose

...

to

...

accept

...

the

...

altered

...

execution

...

or

...

carefully

...

craft

...

the

...

implementation

...

of

...

your

...

compliant

...

technique

...

to

...

preserve

...

the

...

exact

...

number

...

of accesses and

...

order

...

of

...

accesses

...

to

...

the

...

AtomicInteger

...

.

...

This

...

noncompliant

...

code

...

example

...

uses

...

an

...

AtomicInteger

...

,

...

which

...

is

...

part

...

of

...

the

...

concurrency

...

utilities.

...

The

...

concurrency

...

utilities

...

lack

...

integer

...

overflow

...

checks.

{:=
Code Block
bgColor
#FFcccc
}
class InventoryManager {
  private final AtomicInteger itemsInInventory = new AtomicInteger(100);

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

Consequently,

...

itemsInInventory

...

can

...

wrap

...

around

...

to

...

Integer.MIN_VALUE

...

when

...

itemInInventory

...

==

...

Integer.MAX_VALUE.

Compliant Solution (AtomicInteger)

This compliant solution uses the get() and compareAndSet() methods provided by AtomicInteger to guarantee successful manipulation of the shared value of itemsInInventory. This solution has the following characteristics:

  • The number and order of accesses to itemsInInventory remains unchanged from the noncompliant code example.
  • All operations on the value of itemsInInventory are performed on a temporary local copy of its value.
  • The overflow check in this example is performed in inline code, rather than encapsulated in a method call. This is an acceptable alternative implementation. The choice of method call versus inline code should be made according to your organization's standards and needs.
Code Block
bgColor#ccccff
}}.

h2. Compliant Solution ({{AtomicInteger}})

This compliant solution uses the {{get()}} and {{compareAndSet()}} methods provided by {{AtomicInteger}} to guarantee successful manipulation of the shared value of {{itemsInInventory}}. This solution has the following characteristics:
* The number and order of accesses to {{itemsInInventory}} remains unchanged from the noncompliant code example.
* All operations on the value of {{itemsInInventory}} are performed on a temporary local copy of its value.
* The overflow check in this example is performed in inline code, rather than encapsulated in a method call. This is an acceptable alternative implementation. The choice of method call versus inline code should be made according to your organization's standards and needs.

{code:bgColor=#ccccff}
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()
}
{code}

Wiki Markup
The arguments to the {{compareAndSet()}} method are the expected value of the variable when the method is invoked and the intended new value. The variable's value is updated if, and only if, the current value and the expected value are equal. (See \[[API 2006|AA. Bibliography#API 06]\] class [{{AtomicInteger}}|http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html].) Refer to guideline "[VNA02-J. Ensure that compound operations on shared variables are atomic]" for more details.

...

Exceptions

NUM16-EX0

...

:

...

Depending

...

on

...

circumstances,

...

integer

...

overflow

...

could

...

be

...

benign.

...

For

...

instance,

...

many

...

algorithms

...

for

...

computing

...

hashcodes

...

use

...

modular

...

arithmetic,

...

intentionally

...

allowing

...

overflow

...

to

...

occur.

...

Any

...

computation

...

where

...

overflow

...

is

...

expected

...

and

...

allowed

...

must

...

explicitly

...

document

...

this

...

fact.

...

Risk Assessment

Failure to perform appropriate range checking can lead to integer overflows, which can cause unexpected program control flow or unanticipated program behavior.

Guideline

Severity

Likelihood

Remediation Cost

Priority

Level

NUM16-J

medium

unlikely

medium

P4

L3

Automated Detection

Automated detection of integer operations that can potentially overflow is straightforward. Automatic determination of which potential overflows are true errors and which are intended by the programmer is infeasible. Heuristic warnings could be helpful.

Related Guidelines

C Secure Coding Standard:

"INT32-C. Ensure that operations on signed integers do not result in overflow"

C++ Secure Coding Standard:

"INT32-CPP. Ensure that operations on signed integers do not result in overflow"

MITRE CWE

CWE ID 682, "Incorrect Calculation"

 

CWE ID 190, "Integer Overflow or Wraparound"

 

CWE ID 191, "Integer Underflow (Wrap or Wraparound)"

Bibliography

<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="f61bd709-5896-47bc-ba4b-55e63d3b7242"><ac:plain-text-body><![CDATA[

[[API 2006

AA. Bibliography#API 06]]

class [AtomicInteger

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html]

...

]]></ac:plain-text-body></ac:structured-macro>

<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="8bcf304e-9e5a-45ef-a349-22dbe412d52d"><ac:plain-text-body><![CDATA[

[[Bloch 2005

AA. Bibliography#Bloch 05]]

Puzzle 27: Shifty i's

]]></ac:plain-text-body></ac:structured-macro>

<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="148e9c50-526d-4087-ad6e-539edf06b9fd"><ac:plain-text-body><![CDATA[

[[SCG 2007

AA. Bibliography#SCG 07]]

Introduction

]]></ac:plain-text-body></ac:structured-macro>

<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="bdd57b28-dab9-47e3-a313-8cd0f6e990ac"><ac:plain-text-body><![CDATA[

[[JLS 2005

AA. Bibliography#JLS 05]]

[§4.2.2, "Integer Operations"

http://java.sun.com/docs/books/jls/third_edition/html/typesValues.html#4.2.2]

]]></ac:plain-text-body></ac:structured-macro>

 

§15.22, "Bitwise and Logical Operators"

<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="b8151e6a-3f4a-49a0-ab9c-1c4d4cca0534"><ac:plain-text-body><![CDATA[

[[Seacord 2005

AA. Bibliography#Seacord 05]]

Chapter 5. Integers

]]></ac:plain-text-body></ac:structured-macro>

<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="c0bf8375-b153-491b-a4fe-54951b8e1d33"><ac:plain-text-body><![CDATA[

[[Tutorials 2008

AA. Bibliography#Tutorials 08]]

Primitive Data Types

]]></ac:plain-text-body></ac:structured-macro>

...

03. Numeric Types and Operations (NUM)      03. Numeric Types and Operations (NUM)      NUM00-J. Do not assume that the remainder operator always returns a non-negative result for integral operands