Co-Location-Resistant Clouds Security
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 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 model for designing and analyzing secure VM placement algorithms, which are online vector bin packing algorithms that simultaneously satisfy certain optimization constraints and notions of security. We introduce several notions of security, establishing connections between them. We also relate the efficiency of the online algorithm to the cost in the 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. This method improves significantly the security of the system.
In a recent work, we consider the problem of cross-VM attacks in public clouds, seeking solutions that do not rely on single-tenancy or on systems-level assumptions. At a very high-level, our focus is on mitigating co-location attacks since they are a necessary first step to performing cross-VM attacks. More concretely, our approach is to assign VMs to physical servers in such a way that attack VMs are rarely co-located with target VMs. To do this, we formalize and design co-location-resistant placement algorithms which, roughly speaking, protect VMs against complete and fractional co-location attacks. Our main placement algorithm uses randomization to place VMs in a manner that is unpredictable to the adversary and that reduces its probability of successfully completing a co-location attack. We note that the naive strategy of placing VMs on servers chosen uniformly at random is not feasible in our setting since VMs cannot be placed arbitrarily in practice. Indeed, VM placement algorithms have to satisfy non-trivial optimization constraints which cannot be met by simply placing VMs at random. One of the major contributions of our work is the design of an algorithm that optimizes for these constraints while remaining co-location-resistant to the adversary.
Secure optimization. As far as we know, ours is the first work to consider the design of such “secure optimization” algorithms; that is, optimization algorithms that also provide some form of security. We believe the study of secure optimization algorithms is an interesting research direction at the intersection of algorithms, security and cryptography and could have applications, not only to cloud computing, but more generally to distributed systems.
Combining cryptography with security. Another major contribution of our work is combining cryptography with security and suggest our notion of shared deployments. Specifically, we show how to take advantage of complete and fractional co-location-resistance through the use of cryptography. At a high-level, our approach is to assume the adversary is computationally-bounded and to cryptographically “split” a tenant’s computation among a set of VMs in such a way that the tenant’s secrets can only be recovered if the adversary co-locates with all the VMs in the set. This allows us to provably improve the quality of the system security.