Page History

When iterating over elements of a container, the iterators used must iterate over a valid range. An iterator range is a pair of iterators that refer to the first and past-the-end elements of the range respectively.

A valid iterator range has all of the following characteristics:

• Both iterators

...

• refer into the same container

...

• .

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

• The iterator representing the start of the range precedes the iterator representing the end of the range.
• The iterators are not invalidated, in conformance with CTR51-CPP. Use valid references, pointers, and iterators to reference elements of a container.

An empty iterator range (where the two iterators are valid and equivalent) is considered to be valid.

Using a range of two iterators that are invalidated or do not refer into the same container results in undefined behavior.

Noncompliant Code Example

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

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

On  On each iteration of its internal loop, std::for_each compares () compares the first iterator (after incrementing it) with the second for equality, and as ; 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.Incrementing the iterator representing the past-the-end element of the range results in undefined behavior.

#include <algorithm>
#include <iostream>
#include <vector>
 
void f(const std::vector<int> &c) {
  std::for_each(c.end(), c.begin(), [](int i) { std::cout << i; });
}

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

Non-Compliant Code Example

Provide a valid ordering predicate for more information about comparators.

Compliant Solution

In this compliant solution, the iterator values passed to std::for_each() are passed in the proper order.The second common case arises when the iterators point into different containers:

#include <algorithm>
#include <iostream>
#include <vector>
 
void f(const std::vector<int> &c) {
  std::
for_each( c.begin(), dc.end(), Something  [](int i) { std::cout << i; });

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

}

Noncompliant Code Example

In this noncompliant code example, iterators from different containers are passed for the same iterator range. Although many STL implementations will compile this code and the program may behave as the developer expects, there is no requirement that an STL implementation treat a default-initialized iterator as a synonym for the iterator returned by end().

#include <algorithm>
#include <iostream>
#include <vector>
 
void f(const std::vector<int> &c) {
  std::vector<int>::const_iterator e;
  std::for_each(c.begin(), e, [](int i) { std::cout << i; });
}

Compliant Solution

In this compliant solution, the proper iterator generated by a call to end() is passed.

...

#include <algorithm>
#include <iostream>
#include <vector>
 
void f(const std::vector<int> &c) {
  std::for_each( c.begin(), c.end(), Something  [](int i) { std::cout << i; });
}

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|AA. C++ References#Sutter 05]\] Item 83: Use a checked STL implementation.
\[[Meyers 01|AA. C++ References#Meyers 01]\] Item 21: Always have comparison functions return false for equal values.
\[[ISO/IEC 14882-2003|AA. C++ References#ISO/IEC 14882-2003]\] Section 24: Iterators Library.

Automated Detection

Related Vulnerabilities

In Fun with erase(), Chris Rohlf discusses the exploit potential of a program that calls vector::erase() with invalid iterator ranges [Rohlf 2009].

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

Related Guidelines

Bibliography

...

Image Added Image Added Image AddedSTL30-CPP. Do not use iterators invalidated by container modification      14. Templates and the STL (STL)      STL32-CPP. Use a Valid Ordering Rule