A CodeQL library for detecting and analyzing iterator invalidation in C++ codebases.
Set up CodeQL in Visual Studio Code. We recommend using the starter workspace.
Download Itergator and add it to your workspace.
git clone https://github.com/trailofbits/itergator
Open and run the desired queries.
To use the classes in your own queries, add Itergator to your qlpack.yml
:
name: codeql-custom-queries-cpp
version: 0.0.0
libraryPathDependencies:
- codeql-cpp
- trailofbits-itergator
Then import the libraries:
import trailofbits.itergator.iterators
import trailofbits.itergator.dataflow
import trailofbits.itergator.invalidations.Destructor
import trailofbits.itergator.invalidations.STL
Returns a list of iterated types.
There may be false positives, such as when an iterator is used in an expression that is assigned to another:
iterator __pos = __position._M_const_cast()
Returns a list of potential invalidations.
Results contain the iterator that may be invalidated, the access of the iterated variable, the top-level potentially invalidating function call, and the method call on the iterated variable. There is also an integer column significance
. Lower values are expected to have less noise in their results.
This query has a high false positive rate. Analyzing the path of the function calls is useful to confirm a potential invalidation. An example of a path query can be seen in examples/LLVMPath.ql.
Classes representing iterators and invalidations in the codebase.
class Iterator extends Variable
A variable that stores an iterator.
class Iterated extends VariableAccess
The access of a container where it is being iterated over, e.g.
vec.begin()
.Member predicate
Iterator iterator()
returns a variable the resulting iterator is stored in.
class Invalidator extends InvalidatorT
A function call within the scope of an iterator that could trigger an invalidation.
Member predicate
Iterated iterated()
returns anIterated
element in the assignment of an iterator with the same scope as thisInvalidator
.Member predicate
Invalidation invalidation()
returns a function call that could invalidate an iterator in the scope of this invalidator.
class Invalidation extends InvalidatorT
A function call that is a potential invalidation and could be reached from an
Invalidator
.Member predicate
Invalidator invalidator()
returns anInvalidator
function call within the scope of a correctly typed iterator that this is reachable from.
class InvalidatorT extends FunctionCallR
A class of function call that composes the path from an
Invalidator
to anInvalidation
.This is primarily an internal class, but it may be useful in some queries. View the implementation for details.
Global data flow configurations for Itergator's classes.
class IteratorFlow extends DataFlow::Configuration
class IteratedFlow extends DataFlow::Configuration
class InvalidationFlow extends DataFlow::Configuration
class InvalidatorFlow extends DataFlow::Configuration
A framework for designating functions as potentially invalidating.
abstract class PotentialInvalidation extends Function
This class can be extended to define potential invalidations.
Member predicate
invalidates(Iterated i)
holds if a call to the function could invalidate an iterator of the type of the parameteri
.
Two potential invalidation definitions are already written:
import trailofbits.itergator.invalidations.Destructor
Destructors of the iterated type.
import trailofbits.itergator.invalidations.STL
Member functions of STL types based on the C++ specification. This does not include destructors.
These classes may be used as examples when writing custom invalidation conditions.
Itergator is licensed and distributed under the CC BY-NC-SA 4.0 license. Contact us if you're looking for an exception to the terms.