STL31-C. Use Valid Iterator Ranges

Iterator ranges must be valid ranges.  Passing two iterators where the first doesn't precede the second or that don't both refer into the same container can result in undefined behavior equivalent to a buffer overflow.

An iterator range is a pair of iterators first and last that refer to the first element and the one-past-the-end-th element of the range, respectively. It is required that last be reachable from first by repeated increments of first.

Non-Compliant Code Example

In this non-compliant example, the two iterators that delimit the range point into the same container, but the first iterator doesn't actually precede the second.

for_each( c.end(), c.begin(), Something );

On each iteration of its internal loop, for_each compares the first iterator with the second for equality, and as long as they are not equal it will continue to increment the first iterator. Of course, no matter how many times you increment the first iterator, it will never equal the second, so the loop is essentially endless. In practice, this will, at best, fall off the end of the container c and crash immediately with a memory protection fault. At worst, it will just fall off the end into uncharted memory and possibly read or change values that aren't part of the container. It's not that much different in principle from our infamous and eminently attackable friend the buffer overrun.

Invalid iterator ranges can result from comparison functions that return true for equal values. See STL32-C. Use a Valid Ordering Rule and Meyers 01.

Non-Compliant Code Example

The second common case arises when the iterators point into different containers:

for_each( c.begin(), d.end(), Something );

The results are similar to the first non-compliant code example.

Risk Assessment

Using an invalid iterator range is similar to allowing a buffer overflow, which can lead to an attacker running arbitrary code.

References

[[Sutter 05]] Item 83: Use a checked STL implementation.
[[Meyers 01]] Item 21: Always have comparison functions return false for equal values.
[[ISO/IEC 14882-2003]] Section 24: Iterators Library.