Penn Logo
Vertical Line

Implementation of Computation Group


Low-Fat Pointers: Compact Encoding and Efficient Gate-Level Implementation of Fat Pointers for Spatial Safety and Capability-based Security

Albert Kwon, Udit Dhawan, Jonathan M. Smith, Thomas F. Knight, Jr., and André DeHon
Proceedings of the ACM Conference on Computer and Communications Security, (November 4--8, 2013)

Referencing outside the bounds of an array or buffer is a common source of bugs and security vulnerabilities in today's software. We can enforce spatial safety and eliminate these violations by inseparably associating bounds with every pointer (fat pointer) and checking these bounds on every memory access. By further adding hardware-managed tags to the pointer, we make them unforgeable. This, in turn, allows the pointers to be used as capabilities to facilitate fine-grained access control and fast security domain crossing. Dedicated checking hardware runs in parallel with the processor's normal datapath so that the checks do not slow down processor operation (0% runtime overhead). To achieve the safety of fat pointers without increasing program state, we compactly encode approximate base and bound pointers along with exact address pointers for a 46b address space into one 64-bit word with a worst-case memory overhead of 3%. We develop gate-level implementations of the logic for updating and validating these compact fat pointers and show that the hardware requirements are low and the critical paths for common operations are smaller than processor ALU operations. Specifically, we show that the fat-pointer check and update operations can run in a 4ns clock cycle on a Virtex~6 (40nm) implementation while only using 1100 6-LUTs or about the area of a double-precision, floating-point adder.

© 2013 held by authors; Publication rights licensed to ACM.

Errata: Eq. 2 should not invert (carry-1) [and correspondingly, Atop would better be named Abottom]. Fig. 6a properly shows the datapath without that inversion. The Bluespec code that accompanies the paper (link below) does not have this error, so is more authoritative.

Room# 315, 200 South 33rd Street, Electrical and Systems Engineering Department, Philadelphia , University of Pennsylvania, PA 19104.