On DARPA's cybersecurity radar: Algorithmic and side-channel attacks

The U.S. Defense Advanced Research Projects Agency () is working with university researchers to prepare now for next-gen in the form of “algorithmic complexity attacks,” which are nearly impossible to detect with today’s technology (and the kind most likely to be attempted by nation-states), as well as side-channel attacks, a.k.a. “spy-in-the-sandbox attacks.”

While vulnerabilities based on flawed implementations of algorithms are already popular targets and have been for years, cyberattackers are expected to shift their attention to vulnerabilities found within the algorithms themselves.

So DARPA’s Space/Time Analysis for (STAC) program is working to develop new program-analysis techniques and tools to identify vulnerabilities related to space and time resource-usage behavior of algorithms, specifically ones associated with algorithmic complexity attacks and side-channel attacks. The STAC program’s main goal is to enable analysts to detect these types of vulnerabilities at a scale and speed that can support searching for them within software that the U.S. government, military, and critical infrastructure all rely upon.

Attacks targeted by STAC

Software systems are vulnerable to algorithmic complexity attacks, which attackers can manipulate by crafting an input that forces the system to consume super-linear space or time processing it. This malicious act results in legitimate users being denied service or the system becoming disabled when it’s forced to attempt computations that require large amounts of space or time.

Side-channel attacks, on the other hand, are stealthy indirect information flows that cause software systems to give up their secrets. Attackers can uncover secret information by measuring the behavior of running software, such as how long a program runs or how much memory it uses.

Academic input

STAC work includes efforts from the Universities of Maryland, Utah, California-Irvine, Yale, and Wisconsin-Madison.

The University of Maryland team was awarded a $3.4 million grant to develop automated software-analysis tools to detect anomalies associated with algorithmic complexity attacks and side-channel attacks.

“It turns out that these two problems are related,” explains Michael Hicks, a professor of computer science affiliated with the University of Maryland Institute for Advanced Computer Science and the Maryland Cybersecurity Center. “Both depend on how inputs to the program can influence the program’s subsequent behavior. So we want to develop analysis tools that, when handed a piece of software, can determine whether that particular software might be vulnerable to either of these problems.”

A team of computer scientists at the University of Utah and University of California-Irvine won a $3 million grant from DARPA to create an analyzer to thwart algorithmic attacks targeting the set of rules or calculations that computers must follow to solve a problem.

“The military is looking ahead at what’s coming in terms of cybersecurity and it looks like algorithmic attacks,” says Matt Might, associate professor of computer science at the University of Utah. “Right now, the doors of the house are unlocked so there’s no point getting a ladder and scaling up to an unlocked window on the roof. But once all the doors are locked on the ground level, attackers are going to start buying ladders.”

Algorithmic attacks are a little unusual because they don’t require conventional vulnerabilities. “These attacks are particularly devious because they exploit weaknesses in how resources like time and space are used in the ,” notes Suresh Venkatasubramanian, an associate professor of computer science at the University of Utah.

Creating these vulnerabilities is, however, an extremely costly, complex, and time-intensive process, which so far falls within the realm of state-sponsored hackers.

The team is currently developing software capable of performing audits of computer programs to detect algorithmic vulnerabilities or “hot spots” within the code. Their analyzer will perform a mathematical simulation of the software to predict what will happen in the event of an attack. “Think of it as ‘spell check’ for cybersecurity,” says Might.

GrammaTech, Inc. (Ithaca, New York) engineers teamed up with Yale University researchers on STAC to develop technology to detect denial-of-service vulnerabilities based on the space and time complexities of code.

The company’s approach is to detect these classes of vulnerabilities in without requiring access to program source code. To do this, they teamed up with the Yale experts, who are contributing recent breakthroughs in amortized resource-bound analysis, as well as University of Wisconsin-Madison researchers who are contributing seminal work in shape analysis, which will enable the combined technology to capture the dependence of resource use on .

These three groups are a sample of the 10 currently receiving funding as part of DARPA’s STAC initiative, which launched in April 2015 and will continue for four years.