Module AllocationToInvalidPointer

This file provides the first phase of the cpp/invalid-pointer-deref query that identifies flow from an allocation to a pointer-arithmetic instruction that constructs a pointer that is out of bounds.

Consider the following snippet:

1. char* base = (char*)malloc(size);
2. char* end = base + size;
3. for(int *p = base; p <= end; p++) {
4.   use(*p); // BUG: Should have been bounded by `p < end`.
5. }

this file identifies the flow from new int[size] to base + size.

This is done using the product-flow library. The configuration tracks flow from the pair (allocation, size of allocation) to a pair (a, b) where there exists a pointer-arithmetic instruction pai = a + r such that b is a dataflow node where b <= r. Because there will be a dataflow-path from allocation to a this means that the pai will compute a pointer that is some number of elements beyond the end position of the allocation. See pointerAddInstructionHasBounds for the implementation of this.

In the above example, the pair (a, b) is (base, size) with base and size coming from the expression base + size on line 2, which is also the pointer-arithmetic instruction. In general, the pair does not necessarily correspond directly to the operands of the pointer-arithmetic instruction. In the following example, the pair is again (base, size), but with base coming from line 3 and size from line 2, and the pointer-arithmetic instruction being base + n on line 3:

1. int* base = new int[size];
2. if(n <= size) {
3.   int* end = base + n;
4.   for(int* p = base; p <= end; ++p) {
5.     *p = 0; // BUG: Should have been bounded by `p < end`.
6.   }
7. }

Handling false positives:

Consider a snippet such as:

1. int* base = new int[size];
2. int n = condition() ? size : 0;
3. if(n >= size) return;
4. int* end = base + n;
5. for(int* p = base; p <= end; ++p) {
6.   *p = 0; // This is fine since `end < base + size`
7. }

In order to remove this false positive we define a barrier (see SizeBarrier::SizeBarrierConfig) that finds the possible guards that compares a value to the size of the allocation. In the above example, this is the (n >= size) guard on line 3. SizeBarrier::getABarrierNode then defines any node that is guarded by such a guard as a barrier in the dataflow configuration.