IR-ORAM: Path Access Type Based Memory Intensity Reduction for Path-ORAM

Path ORAM is an effective ORAM (Oblivious RAM) primitive for protecting memory access patterns. Path ORAM converts each off-chip memory request from user program to tens to hundreds of memory accesses. While several schemes have been proposed to mitigate the total number of memory accesses, Path ORAM remains a highly memory intensive primitive that leads to large memory bandwidth occupation and performance degradation.

In this paper, we propose IR-ORAM to reduce the memory intensity based on path access types in Path ORAM. Path accesses in Path ORAM, while being kept oblivious to ensure privacy protection, can be categorized to three types: paths for requested data blocks, paths for position map blocks, and dummy paths. We develop a set of techniques to reduce the memory intensity of each type while ensuring the obliviousness at the same time -we reduce the number of data blocks to access for each tree path, reduce the number of path accesses for position maps, and convert many dummy path accesses to early write-backs of dirty data in LLC. Our experimental results show that IR-ORAM achieves on average 42% performance improvement over the state-of-the-art while effectively enforcing the memory access obliviousness and the same level of security protection.

• PT m path. To prevent timing channel attacks, Path ORAM needs to generate path accesses at a fixed rate, e.g., one path access per T cycles [9]. When it needs to generate a path access but there is no pending real request, Path ORAM constructs a dummy one to access a random tree path. Since the high memory intensity has become the main obstacle that prevents Path ORAM from wide deployment, many schemes have been proposed to mitigate memory bandwidth usage and its impact. Maas et al. proposed to cache top tree levels on-chip to reduce the number of data blocks to access [22]. Nagarajan et al. proposed to create a smaller tree such that majority accesses can be satisfied by the smaller tree, which reduces the length of the tree and the number of blocks per node [23]. Zhang et al. proposed to exploit the dummy blocks of the same path to save shadow copies so that the processor can resume execution early [38]. Unfortunately, the memory intensity of Path ORAM remains high, which still incurs large performance degradation to the user applications.

In this paper, we propose IR-ORAM that proactively reduces the memory access intensity of each path type. IR-ORAM consists of a set of three path-type-dependent schemes with a focus on intensity reduction, i.e., it reduces the number of each type of path accesses to improve the overall performance. Our contributions are as follows.

• We propose IR-Alloc, a utilization-aware node size allocation strategy, to reduce the number of data blocks to access