Abstract:

The problem of enforcing correct usage of array and pointer references in C and C++ programs remains unsolved. The approach proposed by Jones and Kelly (extended by Ruwase and Lam) is the only one we know of that does not require significant manual changes to programs, but it has extremely high overheads of 5x-6x and 11x--12x in the two versions. In this paper, we describe a collection of techniques that dramatically reduce the overhead of this approach, by exploiting a fine-grain partitioning of memory called Automatic Pool Allocation. Together, these techniques bring the average overhead checks down to only 12\% for a set of benchmarks (but 69\% for one case). We show that the memory partitioning is key to bringing down this overhead. We also show that our technique successfully detects all buffer overrun violations in a test suite modeling reported violations in some important real-world programs.

Published:

"Backwards-Compatible Array Bounds Checking for C with Very Low Overhead", Dinakar Dhurjati and Vikram Adve.
Proceedings of the 28th International Conference on Software Engineering (ICSE '06), Shanghai, China, 2006.

Download:

• Backwards-Compatible Array Bounds Checking for C with Very Low Overhead (PDF)
• Backwards-Compatible Array Bounds Checking for C with Very Low Overhead (PPT)

BibTeX Entry:

@techreport{da06icse,
  author = {Dinakar Dhurjati and Vikram Adve},
  title = "{Backwards-Compatible Array Bounds Checking for C with Very Low Overhead}",
  booktitle = "{Proceedings of the 2006 International Conference on Software Engineering (ICSE'06)}",
  address   = {Shanghai, China},
  month     = {May},
  year      = {2006}
  url       = {http://llvm.org/pubs/2006-05-24-SAFECode-BoundsCheck.html}
}