## Pointer-Range Analysis

*Suan Hsi Yong and Susan Horwitz*
In the 11th International
Static Analysis Symposium (SAS'04),
Verona, Italy, August 26-28, 2004.

[ PDF, 166 KB ]
[ PS, 395 KB ]
[ PPT slides, 498 KB ]

### Abstract

Array-Range Analysis computes at compile time the range
of possible index values for each array-index expression
in a program.
This information can be used to detect potential
out-of-bounds array accesses and to identify non-aliasing
array accesses.
In a language like C, where arrays can be accessed
indirectly via pointers, and where pointer arithmetic
is allowed, range analysis must be extended to compute
the range of possible values for each pointer dereference.

This paper describes a Pointer-Range Analysis algorithm
that computes a safe approximation of the set of memory
locations that may be accessed by each pointer dereference.
To properly account for non-trivial aspects of C, including
pointer arithmetic
and type-casting,
a range representation is described that separates the
identity of a pointer's target location from its type;
this separation allows a concise representation of pointers
to multiple arrays, and precise handling of mismatched-type
pointer arithmetic.