Streamline Ring ORAM Accesses through Spatial and Temporal Optimization

Memory access patterns could leak temporal and spatial information in a sensitive program; therefore, obfuscated memory access patterns are desired from the security perspective. Oblivious RAM (ORAM) has been the favored candidate to eliminate the access pattern leakage through randomly remapping data blocks around the physical memory space. Meanwhile, accessing memory with ORAM protocols results in significant memory bandwidth overhead. For each memory request, after going through the ORAM obfuscation, the main memory needs to service tens of actual memory accesses, and only one real access out of them is useful for the program execution. Besides, to ensure the memory bus access patterns are indistinguishable, extra dummy blocks need to be stored and transmitted, which cause memory space waste and poor performance.

In this work, we introduce a new framework, String ORAM, that accelerates the Ring ORAM accesses with Spatial and Temporal optimization schemes. First, we identify that dummy blocks could significantly waste memory space and propose a compact ORAM organization that leverages the real blocks in memory to obfuscate the memory access pattern. Then, we identify the inefficiency of current transaction-based Ring ORAM scheduling on DRAM devices and propose an effective scheduling technique that can overlap the time spent on row buffer misses while ensuring correctness and security. With a minimal modification on the hardware and software, and negligible impact on security, the framework reduces 30.05% execution time and up to 40% memory space overhead compared to the state-of-the-art bandwidth-efficient Ring ORAM.