PointerOverflow.qhelp

<!DOCTYPE qhelp PUBLIC
  "-//Semmle//qhelp//EN"
  "qhelp.dtd">
<qhelp>
<overview>
<p>
The expression <code>ptr + a &lt; ptr</code> is equivalent to <code>a &lt;
0</code>, and an optimizing compiler is likely to make that replacement,
thereby removing a range check that might have been necessary for security.
If `a` is known to be non-negative, the compiler can even replace <code>ptr +
a &lt; ptr</code> with <code>false</code>.
</p>

<p>
The reason is that pointer arithmetic overflow in C/C++ is undefined
behavior. The optimizing compiler can assume that the program has no
undefined behavior, which means that adding a positive number to `ptr` cannot
produce a pointer less than `ptr`.
</p>
</overview>
<recommendation>
<p>
To check whether an index <code>a</code> is less than the length of an array, 
simply compare these two numbers as unsigned integers: <code>a &lt; ARRAY_LENGTH</code>. 
If the length of the array is defined as the difference between two pointers 
<code>ptr</code> and <code>p_end</code>, write <code>a &lt; p_end - ptr</code>.
If a is <code>signed</code>, cast it to <code>unsigned</code> 
in order to guard against negative <code>a</code>. For example, write 
<code>(size_t)a &lt; p_end - ptr</code>.
</p>
</recommendation>
<example>
<p>
An invalid check for pointer overflow is most often seen as part of checking
whether a number <code>a</code> is too large by checking first if adding the
number to <code>ptr</code> goes past the end of an allocation and then
checking if adding it to <code>ptr</code> creates a pointer so large that it
overflows and wraps around.
</p>

<sample src="PointerOverflow-bad.cpp" />

<p>
In both of these checks, the operations are performed in the wrong order.
First, an expression that may lead to undefined behavior is evaluated
(<code>ptr + a</code>), and then the result is checked for being in range.
But once undefined behavior has happened in the pointer addition, it cannot
be recovered from: it's too late to perform the range check after a possible
pointer overflow.
</p>

<p>
While it's not the subject of this query, the expression <code>ptr + a &lt;
ptr_end</code> is also an invalid range check. It's undefined behavor in
C/C++ to create a pointer that points more than one past the end of an
allocation.
</p>

<p>
The next example shows how to portably check whether a number is outside the
range of an allocation between <code>ptr</code> and <code>ptr_end</code>.
</p>
<sample src="PointerOverflow-good.cpp" />
</example>
<references>
<li><a href="https://blog.regehr.org/archives/1395">Pointer Overflow Checking [Embedded in Academia]</a></li>
<li><a href="https://lwn.net/Articles/278137/">GCC and pointer overflows [LWN]</a></li>
</references>
</qhelp>