ISR
Achieving Security on the Cloud through Nature-Inspired Computing
During the past decade, USC Professor and ISR Faculty Associate, Nenad Medvidović has been looking at the role software engineering plays—and should play—in the emerging, related fields of grid computing and, more recently, cloud computing. Medvidović’s recent collaborative work with Yuriy Brun, his former Ph.D. student and currently an NSF CRA Postdoctoral Computing Innovation Fellow at the University of Washington, has focused on providing security and privacy guarantees to users of inherently insecure clouds. In this effort, which grew out of a collaborative research project with Director Richard N. Taylor at UC Irvine, funded by the National Science Foundation, Medvidović and Brun have leveraged nature-inspired computing models to provide the types of guarantees that are unattainable via traditional computing approaches.
The recent emergence of cloud computing is forcing the nature of computation to evolve. For example, users no longer run computations on private machines or machines of which they even have physical awareness. The same evolution has taken place for data storage: many users no longer keep data, such as email, on their machines, but rather allow “the cloud” to maintain and safeguard that data. This transformation has allowed ubiquitous access to computation and data with higher availability and reliability than possible with personal machines and local servers. It has also allowed us, in principle, to dispense with certain (at times, severe) limitations of traditional computing, due to the possibility of distributing highly demanding tasks onto many nodes. As a result, however, this transformation has created new security and privacy challenges.
The rapid evolution of how systems execute and how data is handled has, in fact, affected the meanings of the terms security and privacy, when referring to software systems. Security of a computation used to mean “the computer running the computation should be protected from malicious compromise,” and privacy of data used to imply “unauthorized entities could not gain access to the data.” Today, however, with computations on private data running on remote, unknown, potentially untrusted machines, security should mean “no computer, including the one(s) running the computation, may undetectably compromise it” and privacy should imply “no entity, including the one(s) executing the computation, should gain access to the data.” Cloud computing has not yet embraced these new definitions, largely due to the intellectual hurdles and costs of developing systems that conform to these high standards.
Enter sTile, Medvidović and Brun’s approach for secure and trustworthy distribution of computation on the cloud. sTile leverages an existing theoretical model of molecular assembly to construct and deploy onto the cloud large, distributed systems that solve complex computational problems while providing security and privacy guarantees. Specifically, as long as no adversary controls more than ½ of the network used by sTile for solving a problem, sTile guarantees that, with exponentially high (in size of the input) probability, no adversary can learn the data used in the computation. As a simple example, let us assume that an sTile computation is deployed on TeraGrid, which comprises around one million computers, and that an adversary has compromised about 12,000 computers (about 1/8 of TeraGrid); in that case, sTile guarantees that the adversary’s chance of “cracking” the sTile computation is 1 in 10 billion.
sTile solves a problem by:
- mapping it to the tile model of molecular assembly, where a problem is decomposed into an arrangement of computing “tiles”,
- engaging a large number of computers in a cloud to each participate in solving a tiny piece of the problem, i.e., to embody a small number of tiles, and
- virtually composing large numbers of tiles (each of which is executing on a separate physical computer) to arrive at a solution for the problem.
The underlying tile assembly model has tiles, or squares, that stick or do not stick together based on various interfaces on their four sides. Each tile has an interface on its top, right, bottom, and left side (and a “strength” parameter we will elide for simplicity). The four interfaces, elements of a finite alphabet, define the type of the tile. The placement of a set of tiles on a 2-D grid is called a crystal; a tile may attach in empty positions on the crystal if the appropriate interfaces match. Starting from a seed crystal, which is provided by sTile, tiles may attach to form new crystals. Sometimes, several tiles may satisfy the conditions necessary to attach at a position, in which case the attachment is nondeterministic; this property helps to explore the large space of possibilities for solving a complex problem. Therefore, if there exists a way to encode inputs to a computing problem as crystals, sTile will enable attachment of appropriate tiles to produce crystals that encode the output. The figure below shows one such crystal that solves a 3-SAT problem.
sTile has been implemented in a distributed framework, called Mahjong, and an accompanying simulator, called Simjong. sTile’s security and privacy guarantees have been formally proven, while its performance has been empirically assessed on private networks, supercomputing clusters, the distributed testbed PlanetLab, and many large simulated networks.
While, as with other similar approaches, sTile has shown that the computational cost of privacy is high, we have demonstrated that cost to be manageable on large clouds. Furthermore, sTile is significantly faster than today’s other comparable privacy-preserving approaches, which would require supercomputers to perform the simplest computations.
More information on Medvidović can be found at: