Local memory via layout randomization

Randomization is used in computer security as a tool to introduce unpredictability into the software infrastructure. In this paper, we study the use of randomization to achieve the secrecy and integrity guarantees for local memory. We follow the approach set out by Abadi and Plotkin (2010). We consider the execution of an idealized language in two environments. In the strict environment, opponents cannot access local variables of the user program. In the lax environment, opponents may attempt to guess allocated memory locations and thus, with small probability, gain access the local memory of the user program. We model these environments using two novel calculi: ??hashref and ??proberef. Our contribution to the Abadi-Plotkin program is to enrich the programming language with dynamic memory allocation, first class and higher order references and call/cc-style control. On the one hand, these enhancements allow us to directly model a larger class of system hardening principles. On the other hand, the class of opponents is also enhanced since our enriched language permits natural and direct encoding of attacks that alter the control flow of programs. Our main technical result is a fully abstract translation (upto probability) of ??hashref into ??proberef. Thus, in the presence of randomized layouts, the opponent gains no new power from being able to guess local references of the user program. Our numerical bounds are similar to those of Abadi and Plotkin; thus, the extra programming language features do not cause a concomitant increase in the resources required for protection via randomization