Efficient detection of all pointer and array access errors

Abstract

We present a pointer and array access checking technique that provides complete error coverage through a simple set of program transformations. Our technique, based on an ex- tended safe pointer representation, has a number of novel aspects, Foremost, it is the first technique that detects all spatial and temporal access errors. Its use is not limited by the expressiveness of the language; that is, it can be ap- plied successfully to compiled or interpreted languages with subscripted and mutable pointers, local references, and ex- plicit and typeless dynamic storage management, e.g., C. Because it is a source level transformation, it is amenable to both compile- and run-time optimization. Finally, its per- formance, even without compile-time optimization, is quite good. We implemented a prototype translator for the C lan- guage and analyzed the checking overheads of six non-trivial, pointer intensive programs. Execution overheads range from 130% to 540%; with text and data size overheads typically below 100~0.