# CTR53-CPP: Use valid iterator ranges

This query implements the CERT-C++ rule CTR53-CPP:

> Use valid iterator ranges


## Description

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.
* 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](https://wiki.sei.cmu.edu/confluence/display/cplusplus/CTR51-CPP.+Use+valid+references%2C+pointers%2C+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](https://wiki.sei.cmu.edu/confluence/display/cplusplus/BB.+Definitions#BB.Definitions-undefinedbehavior).

## Noncompliant Code Example

In this noncompliant example, the two iterators that delimit the range point into the same container, but the first iterator does not precede the second. On each iteration of its internal loop, `std::for_each()` compares the first iterator (after incrementing it) with the second for equality; as long as they are not equal, it will continue to increment the first iterator. Incrementing the iterator representing the past-the-end element of the range results in [undefined behavior](https://wiki.sei.cmu.edu/confluence/display/cplusplus/BB.+Definitions#BB.Definitions-undefinedbehavior).

```cpp
#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 result from comparison functions that return true for equal values. See [CTR57-CPP. Provide a valid ordering predicate](https://wiki.sei.cmu.edu/confluence/display/cplusplus/CTR57-CPP.+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.

```cpp
#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. Although many STL [implementations](https://wiki.sei.cmu.edu/confluence/display/cplusplus/BB.+Definitions) 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()`.

```cpp
#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.

```cpp
#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; });
}

```

## Risk Assessment

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

<table> <tbody> <tr> <th> Rule </th> <th> Severity </th> <th> Likelihood </th> <th> Remediation Cost </th> <th> Priority </th> <th> Level </th> </tr> <tr> <td> CTR53-CPP </td> <td> High </td> <td> Probable </td> <td> High </td> <td> <strong>P6</strong> </td> <td> <strong>L2</strong> </td> </tr> </tbody> </table>


## Automated Detection

<table> <tbody> <tr> <th> Tool </th> <th> Version </th> <th> Checker </th> <th> Description </th> </tr> <tr> <td> <a> Astrée </a> </td> <td> 20.10 </td> <td> <strong>overflow_upon_dereference</strong> </td> <td> </td> </tr> <tr> <td> <a> CodeSonar </a> </td> <td> 7.0p0 </td> <td> <strong>LANG.MEM.BO</strong> </td> <td> Buffer Overrun </td> </tr> <tr> <td> <a> Helix QAC </a> </td> <td> 2022.2 </td> <td> <strong>C++3802</strong> </td> <td> </td> </tr> <tr> <td> <a> Parasoft C/C++test </a> </td> <td> 2022.1 </td> <td> <strong>CERT_CPP-CTR53-a</strong> <strong>CERT_CPP-CTR53-b</strong> </td> <td> Do not use an iterator range that isn't really a range Do not compare iterators from different containers </td> </tr> <tr> <td> <a> PRQA QA-C++ </a> </td> <td> 4.4 </td> <td> <strong>3802 </strong> </td> <td> </td> </tr> <tr> <td> <a> PVS-Studio </a> </td> <td> 7.19 </td> <td> <strong>V539<a></a></strong> , <strong>V662<a></a></strong> , <strong><a>V789</a></strong> </td> <td> </td> </tr> </tbody> </table>


## 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](https://wiki.sei.cmu.edu/confluence/display/cplusplus/AA.+Bibliography#AA.Bibliography-rohlf2009)\].

Search for [vulnerabilities](https://wiki.sei.cmu.edu/confluence/display/cplusplus/BB.+Definitions) resulting from the violation of this rule on the [CERT website](https://www.kb.cert.org/vulnotes/bymetric?searchview&query=FIELD+KEYWORDS+contains+CTR53-CPP).

## Related Guidelines

<table> <tbody> <tr> <td> <a> SEI CERT C++ Coding Standard </a> </td> <td> <a> CTR51-CPP. Use valid references, pointers, and iterators to reference elements of a container </a> <a> CTR57-CPP. Provide a valid ordering predicate </a> </td> </tr> </tbody> </table>


## Bibliography

<table> <tbody> <tr> <td> \[ <a> ISO/IEC 14882-2014 </a> \] </td> <td> Clause 24, "Iterators Library" Subclause 25.3, "Mutating Sequence Operations" </td> </tr> <tr> <td> \[ <a> Meyers 2001 </a> \] </td> <td> Item 32, "Follow Remove-Like Algorithms with <code>erase</code> If You Really Want to Remove Something" </td> </tr> </tbody> </table>


## Implementation notes

None

## References

* CERT-C++: [CTR53-CPP: Use valid iterator ranges](https://wiki.sei.cmu.edu/confluence/pages/viewpage.action?pageId=88046682)
