Page History

Wiki MarkupThe operation of the remainder operator in Java is defined in the Java Language Specification \[[JLS 2005|AA. Bibliography#JLS 05]\], Section The definition of the Java remainder operator (see Java Language Specification, Section 15.17.3 "Remainder Operator %") states:

The remainder operation for operands that are integers after binary numeric promotion (§5.6.2) produces a result value such that (a/b)*b+(a%b) is equal to a. This identity holds even in the special case that the dividend is the negative integer of largest possible magnitude for its type and the divisor is -1 (the remainder is 0). It follows from this rule that the result of the remainder operation can be negative only if the dividend is negative, and can be positive only if the dividend is positive; moreover, the magnitude of the result is always less than the magnitude of the divisor.

Although clearly defined in the Java specification, the behavior of the remainder operator's equivalent is undefined in several early C implementations. Programmers who are unaware of this distinction might always expect a positive remainder and Programmers may incorrectly assume that the remainder operation always returns a positive result, and may code accordingly. This can result in vulnerabilities.

The result definition of the remainder operator implies specifies the following behavior:

5 % 3 produces 2
5 % (-3) produces 2
(-5) % 3 produces -2
(-5) % (-3) produces  -2

The result has the same sign as the dividend (the first operand in the expression).

Noncompliant Code Example

In this This noncompliant code example , uses the integer hashKey references as an element of index into the hash array. However, as The lookup function may fail, because the hash key is not guaranteed to be positiveinput may be negative and so yield a negative result from the remainder operator; thus, the lookup function may fail, triggering will throw a java.lang.ArrayIndexOutOfBoundsException on for all negative inputs.

private int SIZE = 16;	
public int[] hash = new int[SIZE];
	
public int lookup(int hashKey) {
  return hash[hashKey % SIZE];
}

Compliant Solution

This compliant solution calls a method that returns a modulus that is always positive.

// method imod() gives non-negative result
private int SIZE = 16;
public int[] hash = new int[SIZE];

private int imod(int i, int j) {
  int temp = i % j;
  return (itemp == Integer.MIN_VALUE< 0) ? 0-temp :
         (i < 0) ? ((-i) % j) : (i % j);
}
	
public int lookup(int hashKey) {
  return hash[imod(hashKey, size)];
}

Note that {{Integer.MIN_VALUE}} must be handled specially in the {{imod()}} method. The \[[JLS 2005|AA. Bibliography#JLS 05]\] 15.15.4 (Unary Minus Operator) says:

For integer values, negation is the same as subtraction from zero. The Java programming language uses two's-complement representation for integers, and the range of two's-complement values is not symmetric, so negation of the maximum negative int or long results in that same maximum negative number. Overflow occurs in this case, but no exception is thrown. For all integer values x, -x equals (~x)+1.

Compliant Solution

Alternatively, an explicit range check must be performed on the numerator at every susceptible point as demonstrated in this compliant solution.

 temp; // unary - will succeed without overflow  
                                    // because temp cannot be Integer.MIN_VALUE
}
	
public int lookup(int hashKey) {
  if (hashKey < 0)
    return hash[imod(-hashKey) % SIZE, size)];
  return hash[hashKey % SIZE];
}

Note that providing a well-documented imod method is a better choice as it improves readability and makes it clear that its sole purpose is to return positive values when required and not to "fix" the unintuitive behavior of the remainder operator, as defined by the specification.

Risk Assessment

Assuming a positive remainder when using the remainder operator can result in incorrect computations.

Automated Detection

Automated detection of uses of the % operator is straightforward. Sound determination of whether those uses correctly reflect the intent of the programmer is infeasible in the general case. Heuristic warnings may be useful.

Other Languages

This guideline appears in the C Secure Coding Standard as INT10-C. Do not assume a positive remainder when using the % operator.

This guideline appears in the C++ Secure Coding Standard as INT10-CPP. Do not assume a positive remainder when using the % operator,

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this guideline on the CERT website.

Bibliography

\[[JLS 2005|AA. Bibliography#JLS 05]\] [§15.15.4 Unary Minus Operator|http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.15.4] and [§15.17.3 Remainder Operators|http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.17.3]

...