  Software security continues to be a critical concern for programs implemented
in low-level programming languages such as C and C++. Many defenses have been
proposed in the current literature, each with different trade-offs including
performance, compatibility, and attack resistance. One general class of defense
is pointer randomization or authentication, where invalid object access (e.g.,
memory errors) is obfuscated or denied. Many defenses rely on the program
termination (e.g., crashing) to abort attacks, with the implicit assumption
that an adversary cannot "brute force" the defense with multiple attack
attempts. However, such assumptions do not always hold, such as hardware
speculative execution attacks or network servers configured to restart on
error. In such cases, we argue that most existing defenses provide only weak
effective security.
  In this paper, we propose Fully Randomized Pointers (FRP) as a stronger
memory error defense that is resistant to even brute force attacks. The key
idea is to fully randomize pointer bits -- as much as possible while also
preserving binary compatibility -- rendering the relationships between pointers
highly unpredictable. Furthermore, the very high degree of randomization
renders brute force attacks impractical -- providing strong effective security
compared to existing work. We design a new FRP encoding that is: (1) compatible
with existing binary code (without recompilation); (2) decoupled from the
underlying object layout; and (3) can be efficiently decoded on-the-fly to the
underlying memory address. We prototype FRP in the form of a software
implementation (BlueFat) to test security and compatibility, and a
proof-of-concept hardware implementation (GreenFat) to evaluate performance. We
show that FRP is secure, practical, and compatible at the binary level, while a
hardware implementation can achieve low performance overheads (<10%).
