research-article

GhostRider: A Hardware-Software System for Memory Trace Oblivious Computation

Authors:

Elaine ShiAuthors Info & Claims

ACM SIGPLAN Notices, Volume 50, Issue 4

Pages 87 - 101

https://doi.org/10.1145/2775054.2694385

Published: 14 March 2015 Publication History

Abstract

This paper presents a new, co-designed compiler and architecture called GhostRider for supporting privacy preserving computation in the cloud. GhostRider ensures all programs satisfy a property called memory-trace obliviousness (MTO): Even an adversary that observes memory, bus traffic, and access times while the program executes can learn nothing about the program's sensitive inputs and outputs. One way to achieve MTO is to employ Oblivious RAM (ORAM), allocating all code and data in a single ORAM bank, and to also disable caches or fix the rate of memory traffic. This baseline approach can be inefficient, and so GhostRider's compiler uses a program analysis to do better, allocating data to non-oblivious, encrypted RAM (ERAM) and employing a scratchpad when doing so will not compromise MTO. The compiler can also allocate to multiple ORAM banks, which sometimes significantly reduces access times.We have formalized our approach and proved it enjoys MTO. Our FPGA-based hardware prototype and simulation results show that GhostRider significantly outperforms the baseline strategy.

References

[1]

Trusted Platform Module (TPM) Summary. http://www.trustedcomputinggroup.org/resources/trusted_platform_module_tpm_summary.

[2]

J. Agat. Transforming out Timing Leaks. In POPL, pages 40--53, 2000.

Digital Library

[3]

G. Barthe and T. Rezk. Non-interference for a JVM-like language. In TLDI '05, pages 103--112, 2005.

Digital Library

[4]

G. Barthe, T. Rezk, A. Russo, and A. Sabelfeld. Security of multithreaded programs by compilation. ACM Trans. Inf. Syst. Secur., 13(3):21:1--21:32, 2010.

Digital Library

[5]

G. Barthe, T. Rezk, and M. Warnier. Preventing Timing Leaks Through Transactional Branching Instructions. Electron. Notes Theor. Comput. Sci., 153(2):33--55, 2006.

Digital Library

[6]

F. Bavera and E. Bonelli. Type-based information flow analysis for bytecode languages with variable object field policies. In SAC, pages 347--351, 2008.

Digital Library

[7]

M. Blanton, A. Steele, and M. Aliasgar. Data-Oblivious Graph Algorithms for Secure Computation and Outsourcing. In ASIACCS, 2013.

Digital Library

[8]

E. Bonelli, A. Compagnoni, and R. Medel. Information flow analysis for a typed assembly language with polymorphic stacks. In CASSIS, pages 37--56, 2006.

Digital Library

[9]

R. Chow, P. Golle, M. Jakobsson, E. Shi, J. Staddon, R. Masuoka, and J. Molina. Controlling data in the cloud: outsourcing computation without outsourcing control. In ACM Cloud Computing Security Workshop (CCSW), pages 85--90, 2009.

Digital Library

[10]

C. Computer. The convey HC2 architectural overview. http://www.conveycomputer.com/files/4113/5394/7097/Convey_HC-2_Architectual_Overview.pdf.

[11]

H. Consortium. Hybrid memory cube. http://hybridmemorycube.org/.

[12]

B. Coppens, I. Verbauwhede, K. D. Bosschere, and B. D. Sutter. Practical Mitigations for Timing-Based Side-Channel Attacks on Modern x86 Processors. In IEEE S & P, pages 45--60, 2009.

Digital Library

[13]

Z. Deng and G. Smith. Lenient array operations for practical secure information flow. In CSF, pages 115--124, 2004.

Digital Library

[14]

D. Eppstein, M. T. Goodrich, and R. Tamassia. Privacy-preserving data-oblivious geometric algorithms for geographic data. In GIS, pages 13--22, 2010.

Digital Library

[15]

C. W. Fletcher, M. v. Dijk, and S. Devadas. A secure processor architecture for encrypted computation on untrusted programs. In STC, 2012.

Digital Library

[16]

C. W. Fletcher, L. Ren, A. Kwon, M. van Dijk, E. Stefanov, and S. Devadas. RAW Path ORAM: A low-latency, low-area hardware ORAM controller with integrity verification. IACR Cryptology ePrint Archive, page 431, 2014.

[17]

C. W. 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 HPCA, pages 213--224, 2014.

[18]

M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.

Digital Library

[19]

T. Gilmont, J. didier Legat, and J. jacques Quisquater. Enhancing security in the memory management unit. In EUROMICRO, 1999.

[20]

O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In STOC, 1987.

Digital Library

[21]

O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 1996.

Digital Library

[22]

M. T. Goodrich and M. Mitzenmacher. Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. In ICALP, pages 576--587, 2011.

Digital Library

[23]

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

[24]

M. T. Goodrich, O. Ohrimenko, and R. Tamassia. Data-oblivious graph drawing model and algorithms. CoRR, abs/1209.0756, 2012.

[25]

T. C. Group. Trusted computing group. http://www.trustedcomputinggroup.org/.

[26]

J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: cold-boot attacks on encryption keys. Commun. ACM, 52(5):91--98, 2009.

Digital Library

[27]

D. Hedin and D. Sands. Timing aware information flow security for a javacard-like bytecode. Electron. Notes Theor. Comput. Sci., 141(1):163--182, Dec. 2005.

Digital Library

[28]

N. Kobayashi and K. Shirane. Type-based information flow analysis for low-level languages. In APLAS, 2002.

[29]

P. C. Kocher, J. Jaffe, B. Jun, and P. Rohatgi. Introduction to differential power analysis. J. Cryptographic Engineering, 1(1):5--27, 2011.

[30]

E. Kushilevitz, S. Lu, and R. Ostrovsky. On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme. In SODA, 2012.

Digital Library

[31]

D. Lie, J. Mitchell, C. A. Thekkath, and M. Horowitz. Specifying and Verifying Hardware for Tamper-Resistant Software. In IEEE S & P, 2003.

Digital Library

[32]

C. Liu, A. Harris, M. Maas, M. Hicks, M. Tiwari, and E. Shi. GhostRider: A hardware-software system for memory trace oblivious computation. Technical Report CS-TR-5041, University of Maryland, Department of Computer Science, Jan. 2015.

[33]

C. Liu, M. Hicks, and E. Shi. Memory Trace Oblivious Program Execution. In CSF, 2013.

Digital Library

[34]

J. R. Lorch, B. Parno, J. W. Mickens, M. Raykova, and J. Schiffman. Shroud: ensuring private access to large-scale data in the data center. In FAST, 2013.

Digital Library

[35]

M. Maas, E. Love, E. Stefanov, M. Tiwari, E. Shi, K. Asanovic, J. Kubiatowicz, and D. Song. Phantom: Practical Oblivious Computation in a Secure Processor. In CCS, 2013.

Digital Library

[36]

R. Medel, A. Compagnoni, and E. Bonelli. A typed assembly language for non-interference. In ICTCS, pages 360--374, 2005.

Digital Library

[37]

G. Morrisett, D. Walker, K. Crary, and N. Glew. From system F to typed assembly language. ACM Trans. Program. Lang. Syst., 21(3):527--568, 1999.

Digital Library

[38]

A. Pnueli, M. Siegel, and E. Singerman. Translation Validation. In TACAS, 1998.

Digital Library

[39]

F. Pottier and V. Simonet. Information flow inference for ML. ACM Trans. Program. Lang. Syst., 25(1):117--158, 2003.

Digital Library

[40]

L. Ren, X. Yu, C. W. Fletcher, M. Van Dijk, and S. Devadas. Design space exploration and optimization of path oblivious ram in secure processors. In ISCA, 2013.

Digital Library

[41]

riscv.org. Launching the Open-Source Rocket Chip Generator, Oct. 2014. https://blog.riscv.org/2014/10/launching-the-open-source-rocket-chip-generator/.

[42]

B. Rogers, S. Chhabra, Y. Solihin, and M. Prvulovic. Using Address Independent Seed Encryption and Bonsai Merkle Trees to Make Secure Processors OS- and Performance- Friendly. In MICRO, pages 183--196, 2007.

Digital Library

[43]

A. Sabelfeld and A. C. Myers. Language-based information-flow security. IEEE Journal on Selected Areas in Communications, 21(1):5--19, Jan. 2003.

Digital Library

[44]

E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li. Oblivious RAM with O((logN)3) worst-case cost. In ASIACRYPT, pages 197--214, 2011.

Digital Library

[45]

S. Skorobogatov. Low temperature data remanence in static RAM. Technical Report UCAM-CL-TR-536, University of Cambridge, Computer Laboratory, June 2002.

[46]

E. Stefanov, M. van Dijk, E. Shi, T.-H. H. Chan, C. Fletcher, L. Ren, X. Yu, and S. Devadas. Path ORAM: an Extremely Simple Oblivious RAM Protocol. IACR Cryptology ePrint Archive, 2013. http://eprint.iacr.org/2013/280.

Digital Library

[47]

G. E. Suh, D. Clarke, B. Gassend, M. van Dijk, and S. Devadas. AEGIS: architecture for tamper-evident and tamper-resistant processing. In ICS, pages 160--171, 2003.

Digital Library

[48]

D. L. C. Thekkath, M. Mitchell, P. Lincoln, D. Boneh, J. Mitchell, and M. Horowitz. Architectural support for copy and tamper resistant software. SIGOPS Oper. Syst. Rev., 34(5):168--177, Nov. 2000.

Digital Library

[49]

A. Vasudevan, J. McCune, J. Newsome, A. Perrig, and L. van Doorn. CARMA: A Hardware Tamper-Resistant Isolated Execution Environment on Commodity x86 Platforms. In ASIACCS, May 2012.

Digital Library

[50]

H. Vo, Y. Lee, A. Waterman, and K. Asanovic. A Case for OS-Friendly Hardware Accelerators. In WIVOSCA, 2013.

[51]

A. Waterman, Y. Lee, D. A. Patterson, and K. Asanovic. The RISC-V Instruction Set Manual, Volume I: Base User- Level ISA. Technical Report UCB/EECS-2011-62, EECS Department, University of California, Berkeley, May 2011.

[52]

L. Whitney. Microsoft Urges Laws to Boost Trust in the Cloud. http://news.cnet.com/8301-1009_3-10437844-83.html.

[53]

P. Williams and R. Sion. Single round access privacy on outsourced storage. In CCS, 2012.

Digital Library

[54]

P. Williams, R. Sion, and B. Carbunar. Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In CCS, pages 139--148, 2008.

Digital Library

[55]

S. A. Zdancewic. Programming Languages for Information Security. PhD thesis, 2002.

Digital Library

[56]

X. Zhuang, T. Zhang, and S. Pande. Hide: an infrastructure for efficiently protecting information leakage on the address bus. SIGARCH Comput. Archit. News, 32(5):72--84, Oct. 2004.

Digital Library

Cited By

Wang ZMa PWang HWang S(2024)PP-CSA: Practical Privacy-Preserving Software Call Stack AnalysisProceedings of the ACM on Programming Languages10.1145/36498568:OOPSLA1(1264-1293)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649856
Zhang XWang JCheng YLi QSun KZheng YZhang NLi X(2024)Interface-Based Side Channel in TEE-Assisted Networked ServicesIEEE/ACM Transactions on Networking10.1109/TNET.2023.329401932:1(613-626)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNET.2023.3294019
Ahmadi MAlrahis LSinanoglu OShafique M(2024)Camo-DNN: Layer Camouflaging to Protect DNNs against Timing Side-Channel Attacks2024 IEEE 30th International Symposium on On-Line Testing and Robust System Design (IOLTS)10.1109/IOLTS60994.2024.10616065(1-7)Online publication date: 3-Jul-2024
https://doi.org/10.1109/IOLTS60994.2024.10616065
Show More Cited By

Index Terms

GhostRider: A Hardware-Software System for Memory Trace Oblivious Computation
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Very long instruction word
    2. Serial architectures
      1. Complex instruction set computing
      2. Reduced instruction set computing
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

GhostRider: A Hardware-Software System for Memory Trace Oblivious Computation
ASPLOS'15

This paper presents a new, co-designed compiler and architecture called GhostRider for supporting privacy preserving computation in the cloud. GhostRider ensures all programs satisfy a property called memory-trace obliviousness (MTO): Even an adversary ...
GhostRider: A Hardware-Software System for Memory Trace Oblivious Computation
ASPLOS '15: Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems

This paper presents a new, co-designed compiler and architecture called GhostRider for supporting privacy preserving computation in the cloud. GhostRider ensures all programs satisfy a property called memory-trace obliviousness (MTO): Even an adversary ...
Write-only oblivious RAM-based privacy-preserved access of outsourced data

Data outsourcing is plagued with several security and privacy concerns. Oblivious RAM (ORAM) can be used to address one of the many concerns, specifically to protect the privacy of data access pattern from outsourced cloud storage. This is achieved by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 50, Issue 4

ASPLOS '15

April 2015

676 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2775054

Editor:
Andy Gill
University of Kansas, Lawrence, KS

Issue’s Table of Contents

ASPLOS '15: Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems
March 2015
720 pages
ISBN:9781450328357
DOI:10.1145/2694344
General Chairs:
Ozcan Ozturk
Bilkent University, Turkey
,
Kemal Ebcioglu
Global Supercomputing, USA
,
Program Chair:
Sandhya Dwarkadas
University of Rochester, USA

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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2015

Published in SIGPLAN Volume 50, Issue 4

Check for updates

Badges

Best Paper

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

99
Total Citations
View Citations
1,110
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZMa PWang HWang S(2024)PP-CSA: Practical Privacy-Preserving Software Call Stack AnalysisProceedings of the ACM on Programming Languages10.1145/36498568:OOPSLA1(1264-1293)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649856
Zhang XWang JCheng YLi QSun KZheng YZhang NLi X(2024)Interface-Based Side Channel in TEE-Assisted Networked ServicesIEEE/ACM Transactions on Networking10.1109/TNET.2023.329401932:1(613-626)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNET.2023.3294019
Ahmadi MAlrahis LSinanoglu OShafique M(2024)Camo-DNN: Layer Camouflaging to Protect DNNs against Timing Side-Channel Attacks2024 IEEE 30th International Symposium on On-Line Testing and Robust System Design (IOLTS)10.1109/IOLTS60994.2024.10616065(1-7)Online publication date: 3-Jul-2024
https://doi.org/10.1109/IOLTS60994.2024.10616065
Hatchikian-Houdot JWilke PBesson FHiet G(2024)Formal Hardware/Software Models for Cache Locking Enabling Fast and Secure CodeComputer Security – ESORICS 202410.1007/978-3-031-70896-1_8(153-173)Online publication date: 6-Sep-2024
https://doi.org/10.1007/978-3-031-70896-1_8
Alam AChen K(2023)TEE-Graph: efficient privacy and ownership protection for cloud-based graph spectral analysisFrontiers in Big Data10.3389/fdata.2023.12964696Online publication date: 30-Nov-2023
https://doi.org/10.3389/fdata.2023.1296469
Li XLi FGao M(2023)Flare: A Fast, Secure, and Memory-Efficient Distributed Analytics FrameworkProceedings of the VLDB Endowment10.14778/3583140.358315816:6(1439-1452)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583158
Ojha DDwarkadas S(2023)Preventing Coherence State Side Channel Leaks Using TimeCacheIEEE Transactions on Computers10.1109/TC.2022.320992272:2(374-385)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TC.2022.3209922
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
Qin LJayaram RShi ESong ZZhuo DChu S(2022)AdoreProceedings of the VLDB Endowment10.14778/3574245.357426716:4(842-855)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574267
Ma PLiu ZYuan YWang S(2022)NeuralD: Detecting Indistinguishability Violations of Oblivious RAM With Neural DistinguishersIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.315527417(982-997)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3155274
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 Issue’s Table of Contents