Bounds checking for aliased arrays

Over the last few months we’ve been hard at work expanding our interval analysis and writing new checks for array bounds checking. I am happy to announce that we can now detect out-of-bounds array accesses for pointers to arrays, both automatic and dynamic. We also now fully handle pointers that offset arrays, allowing us to track their values and detect some extremely hard-to-find bugs.

For example:

int arr[15];

int example(int random){
  int *p = arr;
  p += 3;

  int offset = (random > 10 ? random : 10);
  return p[offset + 4];    //'p' points to 4th element, and index will be at least 14.
}

In this code sample, the pointer ‘p’ is used to alias the global, automatic array of ints, ‘arr’. This pointer is then increased by 3, making it point to the 4th element of the array.  An int, ‘offset’ , is set to be some unknown value, but we know it is at least 10. Finally, the pointer is accessed with index (offset + 4). Since the pointer already refers to the 4th element, and we are trying to access an at least 14 elements further along, Goanna will give the following warning:

8: warning: Goanna[ARR-inv-index-ptr] Array pointer `arr' is accessed with index [17,INF]
which is out of array bounds [0,14]

Similarly, we can perform the same analysis on dynamic arrays allocated with new or malloc. We also handle different syntactic forms of array access. The following example illustrates this, as well as our ability to warn for possible, as opposed to definite index violations, from a range of possible index values that may be out of bounds:

#include <malloc.h>
#include <assert.h>

int example2(int random){
  int *p = malloc(5 * sizeof(int));  //p is an array of size
  int offset = (random ? 7 : 3);
  return *(p + offset);    //'offset' will be either 7 or 3.
}

Here, ‘p’ points to a dynamic array of ints, with 5 elements. The ‘offset’ is set to be either 7 or 3. Accessing the index of value ‘offset’, by explicitly dereferencing the pointer, we know that the index may be within the bounds of the array, but it may be too large. Goanna will issue the following warning:

7: warning: Goanna[ARR-inv-index-ptr-pos] Array pointer `p' is accessed with index [3,7]
which may be out of array bounds [0,4]

Both these checks, along with some others we’ve been working on, will appear in the upcoming 2.4 release.

No Comments

Post a Comment