Using space-time code analysis to thwart hackers

Adam Dove

Mar 21, 2017

Computers control everything around us, from our credit cards, to our medical records, to trade and military secrets—and every day, criminals are coming up with more advanced methods of cracking these systems, putting citizens, and even whole nations at risk. In order to protect this data from hackers, Carnegie Mellon University Silicon Valley Professor Corina Pasareanu, along with her group of CMU researchers, is building tools that can stop hackers before they even get started – using the space-time analysis of code.

While space-time analysis may sound like it belongs in a science fiction film, the reality doesn’t involve going back in time or interplanetary travel. Though the group is building on NASA open-source tools, space-time analysis refers to the analysis of time and space consumption of a program written in Java, including parameters like run-time, allocated memory, file sizes, network packet sizes and so on. For instance, space-time analysis can compute how much memory a program needs or how long it takes to run.

Traditionally, when hackers are trying to find a way into a program or system, they look for implementation errors in the code. These attacks are fairly easy to defend against, as all one has to do is find the same error that the hackers found and fix it. But vulnerabilities that are created by the way that a program is supposed to run—its consumption of space and the time that it takes—these are much more difficult to find and defend against, as they are already built into the behavior of the program.

ISSTAC diagram

Source: Corina Pasareanu

Pasareanu’s research into the Integrated Symbolic Execution for Space-Time Analysis of Code (ISSTAC) aims to approach the problem using both qualitative and quantitative reasoning.

The research team has developed two methods: Worst-Case and Side-Channel Analyses. Essentially, each of these approaches the problem of finding the vulnerable points in a program from a different angle. The first takes the approach of symbolically running the program and following every possible decision it can make to determine where the vulnerabilities lie.

The second analyses the information flow to detect the leakage areas in the program. It then synthesizes the “optimal side-channel attack” using this data, which exposes the most vulnerable parts of a program. Both of these methods can point developers to where the problems are in the program, so they know which parts to fix, making hackers’ jobs much more difficult.

“As an example, we look at password checking programs which are frequently used by hackers to crack passwords,” explains Pasareanu. “By measuring how much time it takes for the program to return an answer of whether or not the password they’ve guess is correct, hackers can guess how many characters in the password match with the input. This eventually allows them to guess the full password much more quickly. Using our tool, program developers can quantify how much of this secret data has been leaked through side-channels like these.”

The project is part of a larger effort by DARPA, under the Space/Time Analysis for Cybersecurity (STAC) program, which brings together several of the top research groups in the country to work on this problem. ISSTAC is a collaborative project with Vanderbilt University and UC Santa Barbara. Along with her post-doctoral students Kasper Luckow, Rody Kersten and Quoc-Sang Phan, Pasareanu is currently looking for additional students to contribute to the project.

“Methods that are available to programmers to search for these types of vulnerabilities are currently limited to what an attacker would also do,” she says. “Experiment by running the program on various inputs and observe its behavior using tools such as debuggers, profilers, and packet-sniffers. Using our techniques, developers can stay ahead of the curve and discover vulnerabilities in their apps before distribution.”