Although various solutions have been proposed to subjugate the buffer overflow attacks, inoculating application programs with strict array bounds checking is considered as the best defense against this class of attacks. Despite these benefits, in practice most applications developers still choose to shy away from array bounds checking because its performance overhead is considered too high to be acceptable. Strict array bounds checking requires checking every array access to make sure the access cannot cross the upper and the lower bounds. The current method to perform array bounds checking is to insert extra instructions into an application for each array access. The minimum number of instruction required to check a reference in a C-like application against its lower and upper bounds is 6, two to load the bounds, tow comparisons, and two conditional branches. In programs that involve many array references, this bounds checking overhead could lead to serious performance penalty, even in the presence of various software optimizations. Many static analysis techniques have been employed to remove the redundant checks. However, arrays are most likely accessed through pointers in the applications written in C/C++; therefore, static analysis techniques cannot be applied due to the complexity of pointer analysis. In conclusion, the only solution to get rid of array bounds checking overhead is to perform the array bounds checking automatically using hardware.
Cash (Checking Array bounds using Segmentation Hardware) is a GCC extension that uses the segmentation hardware of Intel’s X86 architecture to automatically check the bounds when an array is accessed.
Cash exploits the segmentation support in the virtual memory hardware of Intel’s X86 architecture to perform array bounds checking without any per-reference overhead. A segment in the X86 architecture can be of arbitrary size, ranging from a single byte to an entire address space. To provide inter-segment protection, X86’s virtual memory hardware compares every memory reference with its associated segment’s base address and limit, thus essentially checking it against the segment’s lower and upper bounds. Recognizing the similarity between segment bounds checking and array bounds checking, Cash allocates a separate segment to each array, and generates the array reference instructions in such a way that X86 architecture’s segment bounds checking hardware effectively performs the required array bounds checking for free. When array bounds checking is done through segmentation hardware, there is no per-reference overhead. However, in some cases hardware bounds checking is not possible, and Cash falls back to traditional software bounds checking. Therefore, the overhead of Cash mainly comes from additional state set-up required for hardware bounds checking, and occasional software-based bounds checking.
Lap-chung Lam and Tzi-cker Chiueh. ``Checking Array Bound
Violation Using Segmentation Hardware,'' in Proceedings of 2005
International Conference on Dependable Systems and Networks (DSN 2005), June
2005.