A new memory-access protocol assigns every memory address to a single path (green) through a data structure known as a tree. But a given node of the tree will often lie along multiple paths (blue) has been used to illustrate the need to have a system for defending against memory-access attacks and this method was implemented in chips after they were originally proposed two years ago by a group of MIT researchers, Srini Devadas, the Edwin Sibley Webster Professor in MIT’s Department of Electrical Engineering and Computer Science.
The principle behind the scheme that was developed and implemented in hardware is that, whenever a chip needs to fetch data from a particular memory address, it should query a bunch of other addresses, too, so that an adversary can’t determine which one it’s really interested in. Naturally, this requires shipping much more data between the chip and memory than would otherwise be necessary.
“The root of the tree is a lot smaller than the bottom of tree,” says Albert Kwon, an MIT graduate student in electrical engineering and computer science and one of the papers’ co-authors. “So intuitively, you want to push down as far as you can toward the bottom, so that there’s no congestion at the top.” To minimize the amount of extra data needed, the researchers store memory addresses in a data structure known as a “tree.” A family tree is a familiar example of a tree, in which each “node” (a person’s name) is attached to only one node above it (the node representing the person’s parents) but may connect to several nodes below it (the person’s children).
The researchers stated that “Every address is randomly assigned to a path through the tree — a sequence of nodes stretching from the top of the tree to the bottom, with no backtracking. When the chip requires the data stored at a particular address, it also requests data from all the other nodes on the same path” “Sort is not easy to do in hardware,” says Chris Fletcher, another graduate student in Devadas’ group and first author on the new paper. “So by the time you’ve sorted everything, you’ve taken a real performance hit.”
This research shows that the risk of attacks is particularly acute in the cloud, where you have no control over whose applications are sharing server space with yours. An adversary could load up multiple cloud servers with small programs that do nothing but spy on other people’s data. According to the researchers, one of the advantages of their scheme is that the circuits that implement it can simply be added to existing chip designs, without much retooling. The extra layer of security can then be switched on and off as needed. Some cloud applications may use it all the time; others may opt against it entirely; still others may activate it only when handling sensitive information, such as credit card numbers.
“This is groundbreaking work,” says Elaine Shi, an assistant professor of computer science at the University of Maryland who has studied similar security schemes. “For many years, this kind of secure algorithm has been prohibitive. This is basically the first time they’ve shown that you can achieve this 2x overhead. Previously, the overhead would be ridiculous, maybe in the tens of thousands. They built this thing and show that for, a class of benchmarks, the average slowdown is only 2x.”
“If you think about Java versus C, the slowdown is probably more than 2x,” she says. “Two-x is nothing. Plus, you only have to incur it for part of the code that touches sensitive data, like credit card numbers or genomic data.”
The researchers will present this work at the IEEE International Symposium on Field-Programmable Custom Computing Machines in May, 2015 they will describe some additional improvements to the scheme, which they’ve tested on reconfigurable chips.