Efficient Detection of All Pointer and Array Access Errors

by Todd M. Austin. (austin@cs.wisc.edu)

Abstract (from my PLDI '94 presentation):

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 extended 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 applied successfully to compiled or interpreted languages with subscripted and mutable pointers, local references, and explicit 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 performance, even without compile-time optimization, is quite good. We implemented a prototype translator for the C language 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%.

Publications:

Efficient Detection of All Pointer and Array Access Errors, Todd M. Austin, Scott E. Breach, and Gurindar S. Sohi, Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, June 1994.

Efficient Detection of All Pointer and Array Access Errors (extended version), Todd M. Austin, Scott E. Breach, and Gurindar S. Sohi, University of Wisconsin - Madison Technical Report #1197, December 1993. (A longer version of the PLDI '94 paper).

Overview:

These slides are from my PLDI '94 presentation. By clicking the thumbnail page images, you can peruse the slides. You can also grab the BIG (1.0M) postscript file which generated this tree of html and jpeg files.