International Association
for Cryptologic Research

We consider the problem of designing multi-tenant public infrastructure clouds

resistant to cross-VM attacks without relying on single-tenancy or on

assumptions about the cloud\'s servers. In a cross-VM attack (which have

been demonstrated recently in Amazon EC2) an adversary launches malicious

virtual machines (VM) that perform side-channel attacks against co-located VMs

in order to recover their contents.

We propose a formal model in which to design and analyze \\emph{secure}

VM placement algorithms, which are online vector bin packing

algorithms that simultaneously satisfy certain optimization

constraints and notions of security. We introduce and formalize several notions

of security, establishing formal connections between them. We also introduce a

new notion of efficiency for online bin packing algorithms that better captures

their cost in the setting of cloud computing.

Finally, we propose a secure placement algorithm that achieves our strong

notions of security when used with a new cryptographic mechanism we refer to as

a shared deployment scheme.