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 is a range where:

• both iterators refer into the same container,
• the iterator representing the start of the range precedes the iterator representing the end of the range,
• the elements iterated over do not have unspecified values, and
• the iterators are not invalidated, in conformance with CTR32-CPP. Use valid references, pointers, and iterators to reference elements of a container.

Accessing two iterators which do not refer into the same container or accessing invalidated iterators results in undefined behavior.

Several generic STL algorithms, such as std::remove() and std::unique(), remove instances of elements from a container without shrinking the size of the container. Instead, these algorithms return a ForwardIterator to indicate the partition within the container after which elements are no longer valid. The elements in the container that precede the returned iterator are valid elements with specified values, while the elements that succeed the returned iterator are valid but have unspecified values. Accessing unspecified values of elements iterated over results in unspecified behavior. Frequently, the erase-remove idiom is used to shrink the size of the container when using these algorithms.

Noncompliant Code Example

In this noncompliant

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  On each iteration of its internal loop, std::for_each compares () 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.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 See CTR40-CPP. Provide a valid ordering predicate and Meyers 01 for more information about comparators.

Non-Compliant Code Example

Compliant Solution

In this compliant solution, the iterator values passed to std::for_each() are passed in the proper order:

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

Noncompliant Code Example

In this noncompliant code example, iterators from different containers are passed for the same iterator range. While many STL implementations will compile this code and exhibit reasonable behavior, there is no requirement that an STL implementation treat a default-initialized iterator as a synonym for end().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::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 c.begin(), dC.end(), Something  [](int I) { std::cout << I; });
}

Noncompliant Code Example

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

In this noncompliant code example, elements matching 42 are removed from the given container. The contents of the container are then printed to the standard output stream. However, if any elements were removed from the container, the range-based for loop iterates over an invalid iterator range, resulting in unspecified behavior.

#include <algorithm>
#include <iostream>
#include <vector>
 
void f(std::vector<int> &C) {
  std::remove(C.begin(), C.end(), 42);
  for (auto V : C) {
    std::cout << "Container element: " << V << std::endl;
  }
}

Compliant Solution

In this compliant solution, elements removed by the standard algorithm are subsequently erased from the given container. This ensures that valid iterator range is used by the range-based for loop.

...

for_each( c#include <algorithm>
#include <iostream>
#include <vector>
 
void f(std::vector<int> &C) {
  C.erase(std::remove(C.begin(), cC.end(), Something );
 42), C.end());
  for (auto V : C) {
    std::cout << "Container element: " << V << std::endl;
  }
}

Risk Assessment

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

Automated Detection

Related Vulnerabilities

The The fun with erase() article  article by Chris Rohlf discusses the exploit potential of a program that calls calls vector::erase() with  with invalid iterator ranges.

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

Bibliography

...

Related Guidelines

Bibliography

...

...

...

...

CTR33-CPP. Guarantee that library functions do not form invalid iterators      06006. Containers (CTR)      CTR35-CPP. Do not allow loops to iterate beyond the end of an array or containerImage Added