research-article

PrORAM: dynamic prefetcher for oblivious RAM

Authors:

Syed Kamran Haider,

Christopher Fletcher,

Marten van Dijk,

Srinivas DevadasAuthors Info & Claims

ISCA '15: Proceedings of the 42nd Annual International Symposium on Computer Architecture

Pages 616 - 628

https://doi.org/10.1145/2749469.2750413

Published: 13 June 2015 Publication History

Abstract

Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system. With ORAM, a curious adversary cannot tell what address the user is accessing when observing the bits moving between the user and the storage system. All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses. Such redundancy incurs a large performance overhead.

Although traditional data prefetching techniques successfully hide memory latency in DRAM based systems, it turns out that they do not work well for ORAM because ORAM does not have enough memory bandwidth available for issuing prefetch requests. In this paper, we exploit ORAM locality by taking advantage of the ORAM internal structures. While it might seem apparent that obliviousness and locality are two contradictory concepts, we challenge this intuition by exploiting data locality in ORAM without sacrificing security. In particular, we propose a dynamic ORAM prefetching technique called PrORAM (Dynamic Prefetcher for ORAM) and comprehensively explore its design space. PrORAM detects data locality in programs at runtime, and exploits the locality without leaking any information on the access pattern.

Our simulation results show that with PrORAM, the performance of ORAM can be significantly improved. PrORAM achieves an average performance gain of 20% over the baseline ORAM for memory intensive benchmarks among Splash2 and 5.5% for SPEC06 workloads. The performance gain for YCSB and TPCC in DBMS benchmarks is 23.6% and 5% respectively. On average, PrORAM offers twice the performance gain than that offered by a static super block scheme.

References

[1]

W. Arbaugh, D. Farber, and J. Smith, "A Secure and Reliable Bootstrap Architecture," in Proceedings of the 1997 IEEE Symposium on Security and Privacy, May 1997, pp. 65--71. {Online}. Available: citeseer.nj.nec.com/arbaugh97secure.html

Digital Library

[2]

D. Boneh, D. Mazieres, and R. A. Popa, "Remote oblivious storage: Making oblivious RAM practical," Manuscript, http://dspace.mit.edu/bitstream/handle/1721.1/62006/MIT-CSAIL-TR-2011-018.pdf, 2011.

[3]

T.-F. Chen and J.-L. Baer, "Effective hardware-based data prefetching for high-performance processors," Computers, IEEE Transactions on, vol. 44, no. 5, pp. 609--623, 1995.

Digital Library

[4]

T.-F. Chen and J.-L. Baer, "Effective hardware-based data prefetching for high-performance processors," Computers, IEEE Transactions on, vol. 44, no. 5, pp. 609--623, 1995.

Digital Library

[5]

B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, "Benchmarking cloud serving systems with YCSB," in SoCC'10, pp. 143--154.

Digital Library

[6]

F. Dahlgren, M. Dubois, and P. Stenstrom, "Fixed and adaptive sequential prefetching in shared memory multiprocessors," in Parallel Processing, 1993. ICPP 1993. International Conference on, vol. 1. IEEE, 1993, pp. 56--63.

Digital Library

[7]

I. Damgård, S. Meldgaard, and J. B. Nielsen, "Perfectly secure oblivious RAM without random oracles," in TCC, 2011.

[8]

C. Fletcher, L. Ren, A. Kwon, M. van Dijk, and S. Devadas, "Freecursive oram: {nearly} free recursion and integrity verification for position-based oblivious ram," in Proceedings of the 20^th Int'l Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2015.

Digital Library

[9]

C. Fletcher, L. Ren, X. Yu, M. Van Dijk, O. Khan, and S. Devadas, "Suppressing the oblivious ram timing channel while making information leakage and program efficiency trade-offs," in Proceedings of the Int'l Symposium On High Performance Computer Architecture, 2014.

[10]

C. Fletcher, M. van Dijk, and S. Devadas, "Secure Processor Architecture for Encrypted Computation on Untrusted Programs," in Proceedings of the 7th ACM CCS Workshop on Scalable Trusted Computing; an extended version is located at http://csg.csail.mit.edu/pubs/memos/Memo508/memo508.pdf (Master's thesis), Oct. 2012, pp. 3--8.

Digital Library

[11]

O. Goldreich and R. Ostrovsky, "Software protection and simulation on oblivious rams," in J. ACM, 1996.

Digital Library

[12]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia, "Oblivious ram simulation with efficient worst-case access overhead," in Proceedings of the 3rd ACM workshop on Cloud computing security workshop, ser. CCSW '11. New York, NY, USA: ACM, 2011, pp. 95--100. {Online}. Available: http://doi.acm.org/10.1145/2046660.2046680

Digital Library

[13]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia, "Practical oblivious storage," in Proceedings of the second ACM conference on Data and Application Security and Privacy, ser. CODASPY '12. New York, NY, USA: ACM, 2012, pp. 13--24. {Online}. Available: http://doi.acm.org/10.1145/2133601.2133604

Digital Library

[14]

M. T. Goodrich, M. Mitzenmacher, O. Ohrimenko, and R. Tamassia, "Privacy-preserving group data access via stateless oblivious RAM simulation," in SODA, 2012.

Digital Library

[15]

D. Grawrock, The Intel Safer Computing Initiative: Building Blocks for Trusted Computing. Intel Press, 2006.

[16]

J. L. Henning, "Spec cpu2006 benchmark descriptions," ACM SIGARCH Computer Architecture News, vol. 34, no. 4, pp. 1--17, 2006.

Digital Library

[17]

D. Lie, J. Mitchell, C. Thekkath, and M. Horwitz, "Specifying and verifying hardware for tamper-resistant software," in Proceedings of the IEEE Symposium on Security and Privacy, 2003.

Digital Library

[18]

D. Lie, C. Thekkath, and M. Horowitz, "Implementing an untrusted operating system on trusted hardware," in Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 2003, pp. 178--192.

Digital Library

[19]

D. Lie, C. Thekkath, M. Mitchell, P. Lincoln, D. Boneh, J. Mitchell, and M. Horowitz, "Architectural Support for Copy and Tamper Resistant Software," in Proceedings of the 9^th Int'l Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), November 2000, pp. 168--177.

Digital Library

[20]

J. R. Lorch, J. W. Mickens, B. Parno, M. Raykova, and J. Schiffman, "Toward practical private access to data centers via parallel oram." IACR Cryptology ePrint Archive, vol. 2012, p. 133, 2012, informal publication. {Online}. Available: http://dblp.uni-trier.de/db/journals/iacr/iacr2012.html#LorchMPRS12

[21]

J. E. Miller, H. Kasture, G. Kurian, C. G. III, N. Beckmann, C. Celio, J. Eastep, and A. Agarwal, "Graphite: A Distributed Parallel Simulator for Multicores," in HPCA, 2010.

[22]

R. Ostrovsky, "Efficient computation on oblivious rams," in STOC, 1990.

Digital Library

[23]

R. Ostrovsky and V. Shoup, "Private information storage (extended abstract)," in STOC, 1997, pp. 294--303.

Digital Library

[24]

S. Palacharla and R. E. Kessler, "Evaluating stream buffers as a secondary cache replacement," in ACM SIGARCH Computer Architecture News. IEEE Computer Society Press, 1994.

Digital Library

[25]

L. Ren, X. Yu, C. Fletcher, M. van Dijk, and S. Devadas, "Design space exploration and optimization of path oblivious ram in secure processors," in Proceedings of the Int'l Symposium on Computer Architecture, June 2013, available at Cryptology ePrint Archive, Report 2013/76.

Digital Library

[26]

L. F. G. Sarmenta, M. van Dijk, C. W. O'Donnell, J. Rhodes, and S. Devadas, "Virtual Monotonic Counters and Count-Limited Objects using a TPM without a Trusted OS," in Proceedings of the 1st STC'06, Nov. 2006.

Digital Library

[27]

E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li, "Oblivious ram with o((logn)³) worst-case cost," in Asiacrypt, 2011, pp. 197--214.

Digital Library

[28]

A. J. Smith, "Cache memories," ACM Computing Surveys (CSUR), vol. 14, no. 3, pp. 473--530, 1982.

Digital Library

[29]

E. Stefanov, E. Shi, and D. Song, "Towards practical oblivious RAM," in NDSS, 2012.

[30]

E. Stefanov, M. van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, and S. Devadas, "Path oram: An extremely simple oblivious ram protocol," in Proceedings of the ACM Computer and Communication Security Conference, 2013.

Digital Library

[31]

G. E. Suh, D. Clarke, B. Gassend, M. van Dijk, and S. Devadas, " AEGIS: Architecture for Tamper-Evident and Tamper-Resistant Processing," in Proceedings of the 17^th ICS (MIT-CSAIL-CSG-Memo-474 is an updated version). New-York: ACM, June 2003. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-474/Memo-474.pdf(revisedone)

Digital Library

[32]

G. E. Suh, C. W. O'Donnell, I. Sachdev, and S. Devadas, "Design and Implementation of the AEGIS Single-Chip Secure Processor Using Physical Random Functions," in Proceedings of the 32^nd ISCA'05. New-York: ACM, June 2005. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-483/Memo-483.pdf

Digital Library

[33]

The Transaction Processing Council, "TPC-C Benchmark (Revision 5.9.0)," http://www.tpc.org/tpcc/spec/tpcc_current.pdf, June 2007.

[34]

Trusted Computing Group, "TCG Specification Architecture Overview Revision 1.2," http://www.trustedcomputinggroup.com/home, 2004.

[35]

S. P. Vanderwiel and D. J. Lilja, "Data prefetch mechanisms," ACM Computing Surveys (CSUR), vol. 32, no. 2, pp. 174--199, 2000.

Digital Library

[36]

P. Williams and R. Sion, "Single round access privacy on outsourced storage," in Proceedings of the 2012 ACM conference on Computer and communications security, ser. CCS '12. New York, NY, USA: ACM, 2012, pp. 293--304. {Online}. Available: http://doi.acm.org/10.1145/2382196.2382229

Digital Library

[37]

S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta, "The SPLASH-2 programs: characterization and methodological considerations," in Proceedings of the 22nd Annual International Symposium on Computer Architecture, 1995, pp. 24--36.

Digital Library

[38]

X. Yu, G. Bezerra, A. Pavlo, S. Devadas, and M. Stonebraker, "Staring into the abyss: An evaluation of concurrency control with one thousand cores," Proceedings of the VLDB Endowment, vol. 8, no. 3, pp. 209--220, 2014.

Digital Library

[39]

X. Zhuang, T. Zhang, and S. Pande, "HIDE: an infrastructure for efficiently protecting information leakage on the address bus," in Proceedings of the 11th ASPLOS, 2004.

Digital Library

Cited By

Tian WJian GXu ZLi RXiao W(2024)PEO-Store: Delegation-Proof based Oblivious Storage with Secure Redundancy EliminationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.3361450(1-12)Online publication date: 2024
https://doi.org/10.1109/TDSC.2024.3361450
Hayashibara NKawabata K(2024)Caching and Prefetching for Improving ORAM Performance2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W)10.1109/DSN-W60302.2024.00016(17-20)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN-W60302.2024.00016
Rajat RWang YAnnavaram MSolihin YHeinrich M(2023)LAORAM: A Look Ahead ORAM Architecture for Training Large Embedding TablesProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589111(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589111
Show More Cited By

Index Terms

PrORAM: dynamic prefetcher for oblivious RAM
1. Hardware
  1. Hardware validation
  2. Integrated circuits
    1. Semiconductor memory

Recommendations

PrORAM: dynamic prefetcher for oblivious RAM
ISCA'15

Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system. With ORAM, a curious adversary cannot tell what address the user is accessing when observing the bits moving between the user and the storage ...
PrORAM: Fast $O (log n)$ Authenticated Shares ZK ORAM
Advances in Cryptology – ASIACRYPT 2021
Abstract
We construct a concretely efficient Zero Knowledge (ZK) Oblivious RAM (ORAM) for ZK Proof (ZKP) systems based on authenticated sharings of arithmetic values. It consumes $2 log n$ oblivious transfers (OTs) of length- $2 σ$ secrets per access of an ... $\frac{}{}^{}$
$^{}$
TLB Improvements for Chip Multiprocessors: Inter-Core Cooperative Prefetchers and Shared Last-Level TLBs

Translation Lookaside Buffers (TLBs) are critical to overall system performance. Much past research has addressed uniprocessor TLBs, lowering access times and miss rates. However, as Chip MultiProcessors (CMPs) become ubiquitous, TLB design and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '15: Proceedings of the 42nd Annual International Symposium on Computer Architecture

June 2015

768 pages

ISBN:9781450334020

DOI:10.1145/2749469

General Chair:
Debbie Marr
Intel
,
Program Chair:
David Albonesi
Cornell

ACM SIGARCH Computer Architecture News Volume 43, Issue 3S
ISCA'15
June 2015
745 pages
ISSN:0163-5964
DOI:10.1145/2872887
Editor:
Doug DeGroot
acm dot org
Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE TCCA: IEEE Computer Society Technical Committee on Computer Architecture
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ISCA '15

Sponsor:

IEEE TCCA
SIGARCH

ISCA '15: The 42nd Annual International Symposium on Computer Architecture

June 13 - 17, 2015

Oregon, Portland

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
357
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)12

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tian WJian GXu ZLi RXiao W(2024)PEO-Store: Delegation-Proof based Oblivious Storage with Secure Redundancy EliminationIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.3361450(1-12)Online publication date: 2024
https://doi.org/10.1109/TDSC.2024.3361450
Hayashibara NKawabata K(2024)Caching and Prefetching for Improving ORAM Performance2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W)10.1109/DSN-W60302.2024.00016(17-20)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN-W60302.2024.00016
Rajat RWang YAnnavaram MSolihin YHeinrich M(2023)LAORAM: A Look Ahead ORAM Architecture for Training Large Embedding TablesProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589111(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589111
Zhu JLi MZhang XBu KZhang MSong T(2023)Hitchhiker: Accelerating ORAM With Dynamic SchedulingIEEE Transactions on Computers10.1109/TC.2023.324827272:8(2321-2335)Online publication date: 1-Aug-2023
https://doi.org/10.1109/TC.2023.3248272
Raoufi MYang JTang XZhang Y(2023)AB-ORAM: Constructing Adjustable Buckets for Space Reduction in Ring ORAM2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071064(361-373)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071064
Ren L(2023)Oblivious RAM-Based Secure ProcessorsEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_1553-1(1-3)Online publication date: 30-Apr-2023
https://doi.org/10.1007/978-3-642-27739-9_1553-1
Raoufi MZhang YYang J(2022)IR-ORAM: Path Access Type Based Memory Intensity Reduction for Path-ORAM2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00034(360-372)Online publication date: Apr-2022
https://doi.org/10.1109/HPCA53966.2022.00034
Gong YGao FLi WZhang HJin ZWen Q(2022)A rORAM scheme with logarithmic bandwidth and logarithmic localityInternational Journal of Intelligent Systems10.1002/int.2292937:10(8068-8091)Online publication date: 23-May-2022
https://doi.org/10.1002/int.22929
Che YLiu GWang R(2021)Seeds of SEED: Efficient Access Pattern Obfuscation for Untrusted Hybrid Memory System2021 International Symposium on Secure and Private Execution Environment Design (SEED)10.1109/SEED51797.2021.00017(63-69)Online publication date: Sep-2021
https://doi.org/10.1109/SEED51797.2021.00017
Cao DZhang MLu HYe XFan DChe YWang R(2021)Streamline Ring ORAM Accesses through Spatial and Temporal Optimization2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA51647.2021.00012(14-25)Online publication date: Feb-2021
https://doi.org/10.1109/HPCA51647.2021.00012
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents