Delta pointers: buffer overflow checks without the checks

Highlights:

1. We can directly embed bounds information on higher bits of pointers without adding in-memory metadata tables. The bounds information indicates the upper bound of the current object that the pointer refers to and is adjusted when the pointer is moved.

2. We can use more than 16 bits in virtual address pointers to store metadata, at the cost of a shrunk virtual address space. In this case, the application binary and all its segments must be loaded at the lower end of the address space, and the rest of the unreachable address range should be disabled using mmap().

Comments:

1. The paper seems to ignore the case where a pointer is rounded up (and the round-down case is not convincing to me). How could the compiler catch the round-up case and adjust the tag accordingly?

This paper presents Delta Pointer, a memory safety mechanism that protects the application from buffer overflow attacks. Delta Pointer aims at providing efficient buffer overflow prevention while minimizing the overhead of software instrumentation, especially the branching overhead. To achieve this goal, the Delta Pointer design explicitly embed the object bound information in the upper bits of the pointer and relies on compiler instrumentation to update the tag when pointers are generated or moved, but not when pointers are dereferenced. Compared with prior works that perform pointer checks when the pointer is dereferenced, Delta Pointers demonstrate less runtime overhead on SPEC benchmark due to its ability to remove the explicit bounds check and the branching overhead on pointer dereferences.

The paper begins by noticing that prior works on software memory protection tend to embed per-object or per-type metadata at higher bits of the pointer in order to offer protection. The metadata on the higher bits are used to index an in-memory metadata structure that stores the bounds information of the pointer, which is accessed by compiler instrumented code when the pointer is dereferenced. While this approach offers functionally correct protection, they require excessive checks on every pointer dereference. In particular, the paper noted that most of them require at least two conditional branches to perform the check, one for the lower bound and the the other for the upper bound. Furthermore, certain designs may need more branches to deal with special cases such as temporarily out-of-bound pointers and uninstrumented code where the metadata is unavailable. These branch instructions are generally expensive operations for modern pipelined processors due to not only the execution cycle they occupy but also the complications of branch prediction.

In order to eliminate the conditional branches at pointer dereference time, the Delta Pointer design proposes to directly embed bounds information on higher unused bits of pointers without any accompanying metadata table in the main memory. As a result, the embedded metadata must contain all information that is necessary to perform the check and to support pointer manipulation. In Delta Pointer, the high 32 bits of a 64-bit pointer is dedicated to storing the metadata, while the lower 32 bits still function as pointers, granting a 4GB address space to the process. On 64 bit architectures, such a design requires that the binary of the protected process be loaded to a lower address within the first 4GB of the virtual address space. All the segments of the process, including those protected by ASLR, must also be moved to the lower address range. Virtual memory range above 4GB and below the kernel address space should also be reserved with user-space non-reserving mmap calls such that they will not be given out by the kernel on future mmap calls. On the other hand, the OS address space is unaffected and the kernel can still operate with normal 64-bit addressing because Delta Pointer does not instrument the kernel code.

As mentioned earlier, Delta Pointer directly embeds bounds information at the high 32 bits of a pointer. The metadata is initialized by compiler-generated instrumentation when a new object is allocated and a pointer is generated from the object. The middle 31 bits of the pointer is initialized to be the negation of object size in two’s complement form, while the highest bits of the pointer is reserved to indicate the validity of the pointer. When a pointer is moved via pointer arithmetic, the compiler also generates code to add or subtract the same value from the tag as is for the pointer. The benefit of using negation to represent object size is that if the pointer is moved out of its upper bound, then the carry bit of the tag will be set due to the value of the tag being flipped from negative to positive. Similarly, if the pointer is moved within its bound, the carry bit will become clear as the value of the tag becomes negative again. Overall, by checking the carry bit, i.e., the highest bit of the tag, the processor can determine whether the pointer is valid or not. In practice, the check can be performed implicitly by the existing MMU, as the bit pattern of an out-of-bound pointer would appear to be a non-canonical pointer on x86-64. Non-canonical pointers, when dereferenced,
will cause the hardware MMU to raise an access exception signal to the OS, which results in the termination of the process. This check is already performed by today’s MMU and therefore is essentially free.

Delta Pointer leverages static analysis at compilation time to insert instrumentation. There are several occasions that instrumentation should be inserted. First, when a pointer is dereferenced, the middle 31 bits should be masked off such that the pointer is either a valid regular pointer, or an invalid one that triggers an access fault. Second, when new pointers are generated from existing ones via pointer arithmetic, the tag bits of the new pointer should be computed such that the bound information is still correct. In particular, when a pointer is assigned the value NULL, the bound of the pointer should be set to one (represented in two’s complement as 0xFFFFFFFF), meaning that it must not be moved. Third, the compiler should also distinguish between the instrumented and uninstrumented domain and adjust the pointers when they cross the domain. For example, when a pointer is passed to shared library functions, since the library is not instrumented, the tag should be masked off from the pointer such that the library retains its normal behavior. Similarly, when an object is returned from library functions, the tag should be generated and OR’ed to the higher bits of the pointer. The bounds information of pointers returned from common library functions can be trivially identified, e.g., using the semantics of the function and/or the return object type.