Security Challenges in Cloud Computing: A Closer Look
Chang Liu
, Michael Hicks, Elaine Shi
The University of Maryland, College Park
Motivation
Cloud computing compromise users’ privacy
Transfer both code and data to the cloud provider
Threat Model
CPU and secure co-processor can be trusted
All other hardware is not trusted
Memory
Memory bus
Etc.
Encryption is not enough
Memory access trace may leak information about secret data
Scenario 1
Program
a
[
x
]:=1
Memory bus
read(x)
readarr(a,
x
)
Scenario 2
Program
if(
s
) then
x
:=1
else
y
:=1
Memory bus
read(
s
)
true branch:
write (x)
false branch:
write (y)
Scenario 3
Program
1: if(
s
) then
2:
x
:=1
3: else
4:
x
:=1
Memory bus
read(
s
)
true branch:
fetch instruction 2
false branch:
fetch instruction 4
Oblivious RAM (ORAM)
Problem with ORAM
a[] can be store in DRAM w/o
encryption
a[] can be store in DRAM w/
encryption
a[] can be stored in DRAM w/
encryption; b[] and c[] can be
stored in two ORAM banks
Observations
Some data can be stored in DRAM w/ or w/o
encryption
Some data need be stored in ORAM
We can use multiple ORAM banks to store different data
Question
ORAM
Secure
Inefficient
Normal
Program
Insecure
Efficient
Tradeoff
(This work)
Secure
Efficient
Questions: How to do this safely?
Q1: What programs are secure
Memory trace non-interference
Q2: How to check if a program is secure
A security type system with trace
Q3: How to get a secure program
A security compiler
Language Syntax
Trace
Memory
Semantics
𝑀
𝑥
𝑥
𝑥
=(𝑛, 𝑙)
𝑡=𝑒𝑣𝑡(𝑙,
𝐫𝐞𝐚𝐝
(𝑥, 𝑛))
𝑀, 𝑥
𝑀, 𝑥
𝑀, 𝑥
⇓ 𝑡
⇓
⇓ 𝑡
𝑡
⇓ 𝑡
𝑛
𝑀, 𝑒
𝑀, 𝑒
𝑀, 𝑒
⇓ 𝑡
⇓
⇓ 𝑡
𝑡
⇓ 𝑡
𝑛
𝑀
𝑥
𝑥
𝑥
=(
𝑛 ′
𝑛
𝑛 ′
′
𝑛 ′
, 𝑙)
𝑡 ′
𝑡
𝑡 ′
′
𝑡 ′
=𝑒𝑣𝑡(𝑙,
𝐰𝐫𝐢𝐭𝐞
𝑥, 𝑛
𝑥, 𝑛
𝑥, 𝑛
)
𝑀, 𝑥≔𝑒
𝑀, 𝑥≔𝑒
𝑀, 𝑥≔𝑒
⇓ 𝑡@𝑡′
⇓
⇓ 𝑡@𝑡′
𝑡@𝑡′
⇓ 𝑡@𝑡′
𝑀[𝑥↦
𝑛, 𝑙
𝑛, 𝑙
𝑛, 𝑙
]
Memory Trace Non-interference
DEF. Given a security environment
Γ
, a program
𝑆
satisfies
Γ
-memory trace obliviousness if for any two
Γ
-
valid memories
𝑀 1
𝑀
𝑀 1
1
𝑀 1
∼ 𝐿
∼
∼ 𝐿
𝐿
∼ 𝐿
𝑀 2
𝑀
𝑀 2
2
𝑀 2
if
𝑀 1 , 𝑆
𝑀 1
𝑀
𝑀 1
1
𝑀 1
, 𝑆
𝑀 1 , 𝑆
⇓ 𝑡 1
⇓
⇓ 𝑡 1
𝑡 1
𝑡
𝑡 1
1
𝑡 1
⇓ 𝑡 1
𝑀 1 ′
𝑀
𝑀 1 ′
1
𝑀 1 ′
′
𝑀 1 ′
and
𝑀 2 , 𝑆
𝑀 2
𝑀
𝑀 2
2
𝑀 2
, 𝑆
𝑀 2 , 𝑆
⇓ 𝑡 2
⇓
⇓ 𝑡 2
𝑡 2
𝑡
𝑡 2
2
𝑡 2
⇓ 𝑡 2
𝑀 2 ′
𝑀
𝑀 2 ′
2
𝑀 2 ′
′
𝑀 2 ′
, then
𝑡 1
𝑡
𝑡 1
1
𝑡 1
≡
𝑡 2
𝑡
𝑡 2
2
𝑡 2
, and
𝑀 1 ′
𝑀
𝑀 1 ′
1
𝑀 1 ′
′
𝑀 1 ′
∼ 𝐿
∼
∼ 𝐿
𝐿
∼ 𝐿
𝑀 2 ′
𝑀
𝑀 2 ′
2
𝑀 2 ′
′
𝑀 2 ′
Security Type System
Security Type System (cont’d)
Soundness
Compilation
1. Type checking
Standard
2. Allocating variables to ORAM banks
Allocate each secret variable in a separate ORAM bank
Other allocation strategy (open)
3. Insert padding instructions (for If)
Least common subsequence problem
Evaluation
Asymptotic Analysis
Simulation Results
Conclusion
Q&A
Addressing the privacy compromise in cloud computing, this research delves into the vulnerabilities of transferring code and data to cloud providers. It explores the threat model where only the CPU and secure co-processor are trusted, shedding light on how encryption alone may not suffice to prevent memory access trace leaks. The study introduces Oblivious RAM (ORAM) as a means to conceal access patterns from untrusted servers, while also highlighting the drawbacks of ORAM implementations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chang Liu, Michael Hicks, Elaine Shi The University of Maryland, College Park
Motivation Cloud computing compromise users privacy Transfer both code and data to the cloud provider Threat Model CPU and secure co-processor can be trusted All other hardware is not trusted Memory Memory bus Etc. Encryption is not enough Memory access trace may leak information about secret data
Scenario 1 Program Memory bus a[x]:=1 read(x) readarr(a, x)
Scenario 2 Program Memory bus read(s) true branch: write (x) false branch: write (y) if(s) then else x:=1 y:=1
Scenario 3 Program Memory bus read(s) true branch: fetch instruction 2 false branch: fetch instruction 4 1: if(s) then 2: 3: else 4: x:=1 x:=1
Oblivious RAM (ORAM) A primitive to hide access patterns from the untrusted server Practical implementation Ren et al. Design Space Exploration and Optimization of Path Oblivious RAM in Secure Processors, In Proc. of ISCA 13 Drawback ?(log3?) overhead for an ORAM of size ?
Problem with ORAM Program 1 a[1]:=0 a[] can be store in DRAM w/o encryption Program 2 for i=1 10 a[] can be store in DRAM w/ encryption a[i]=1 Program 3 for i=1 10 b[a[i]]=i c[a[i]]=c[a[i]]+1 end for a[] can be stored in DRAM w/ encryption; b[] and c[] can be stored in two ORAM banks
Observations Some data can be stored in DRAM w/ or w/o encryption Some data need be stored in ORAM We can use multiple ORAM banks to store different data
Question pink-question-mark Normal Program Tradeoff (This work) ORAM Secure Secure Insecure Inefficient Efficient Efficient
Questions: How to do this safely? Q1: What programs are secure Memory trace non-interference Q2: How to check if a program is secure A security type system with trace Q3: How to get a secure program A security compiler
Trace ???? ?,???????? ?,?1,?2 ????? ?,????????? ?,?1,?2 ????? ? ? ?1@?2
Memory Memory ? is a mapping, which maps a variable to a pair (?,?) ? is either a Nat or a mapping from Nat to Nat (i.e. array) ? is a security label which is either L or an ORAM A security environment is a mapping from variable to a type (i.e. Nat l, or Array l) ( -validity) ? is -valid ? = ??? ? ? ???.? ? = ?,? ? = ????? ? ? ??? ???.? ? = ?,?
Semantics ? ? = (?,?) ? = ???(?,????(?,?)) ?,? ?? ?,? ??? ? = (? ,?) ? = ???(?,????? ?,? ) ?,? ? ?@? ?[? ?,? ]
Memory Trace Non-interference DEF. Given a security environment , a program ? satisfies -memory trace obliviousness if for any two - valid memories ?1 ??2 if ?1,? ?1?1 ?2,? ?2?2 and , then ?1 ?2, and ?1 ??2
Security Type System Cannot get trace without given memory configuration Trace Pattern ???? ???????? ? ?????(?)????????(?) ????(?,?,?) ?????(?) ?@? ? ? + ?
Security Type System (contd) ?0 ? ? ?:??? ?;? ? = ??? ? ,?0 ? ?;?@??? ? ,????? ? ?:??? ?;? ? ?0 ? ?1 ??2 ? = ?1 ? ?0 ? ? = ?1+ ?2 ,? ?0 ??;?? ? = 1,2 ,?0 ?? ?,?1,?2;?@?
Soundness Theorem 1. If ,? ?;?, then ? satisfies memory trace obliviousness
Compilation 1. Type checking Standard 2. Allocating variables to ORAM banks Allocate each secret variable in a separate ORAM bank Other allocation strategy (open) 3. Insert padding instructions (for If) Least common subsequence problem
Evaluation Programs Dijstra (100 nodes, 10,000 edges) K-means (100 data points, k=2) Matrix Multiplication (40 40, 20 20) Compilation Strategies Strawman: place all secret variables in a giant ORAM bank Opt 1: Store each variable in a separate ORAM bank, but store whole array in the same ORAM bank Opt 2: store each element in an array in a different ORAM bank when possible (equivalent to encryption only)
Asymptotic Analysis Progra m Memory accesses for data Memory accesses for instructions Strawman Opt 1 Opt 2 Strawman Opt 1 Opt 2 ?(?2log2?) ?(?2log2?) ?(?2log2?) ?(?2?log??) ?(?2?) ?(?2?) Dijstra ?(???log??) ?(???log??) ?(????log??) ?(???) ?(????) ?(????) K-means Mat. mul. ?(?3logc?) ?(?3logc?) ?(?3) ?(?3?logc?) ?(?3?) ?(?3?) Find max. ?(?logc?) ?(?logc?) ?(??logc?) ?(?) ?(??) ?(??)
