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.