Program Summary
As new defensive technologies make old classes of vulnerability difficult to exploit successfully, adversaries move to new classes of vulnerability. Vulnerabilities based on flawed implementations of algorithms have been popular targets for many years. However, once new defensive technologies make vulnerabilities based on flawed implementations less common and more difficult to exploit, adversaries will turn their attention to vulnerabilities inherent in the algorithms themselves.
The Space/Time Analysis for Cybersecurity (STAC) program aims to develop new program analysis techniques and tools for identifying vulnerabilities related to the space and time resource usage behavior of algorithms, specifically, vulnerabilities to algorithmic complexity and side channel attacks. STAC seeks to enable analysts to identify algorithmic resource usage vulnerabilities in software at levels of scale and speed great enough to support a methodical search for them in the software upon which the U.S. government, military, and economy depend.
Software systems can be vulnerable to algorithmic complexity attacks in situations where an adversary can efficiently construct an input that causes one part of that system to consume super-linear space or time processing the input. The adversary’s goal is to deny service to the system’s benign users, or to otherwise disable the system by choosing a worst-case input that causes the system to attempt a computation requiring an impractically-large amount of space or time.
Side-channels are unintended indirect information flows that cause a software system to reveal secrets to an adversary. While the software may prevent the adversary from directly observing the secret, it permits the adversary to observe outputs whose varying space and time characteristics are controlled by computations involving that secret. Given sufficient knowledge of how these computations work, the adversary can deduce the secret by observing some number of outputs.
Because algorithmic resource usage vulnerabilities are the consequence of problems inherent in algorithms themselves rather than the consequence of traditional implementation flaws, traditional defensive technologies such as Address Space Layout Randomization, Data Execution Prevention, Reference Count Hardening, Safe Unlinking, and even Type-Safe programming languages do nothing to mitigate them.
The STAC program seeks advances along two main performance axes: scale and speed. Scale refers to the need for analyses that are capable of considering larger pieces of software, from those that implement network services typically in the range of hundreds of thousands of lines of source code to even larger systems comprising millions or tens of millions of lines of code. Speed refers to the need to increase the rate at which human analysts can analyze software with the help of automated tools, from thousands of lines of code per hour to tens of thousands, hundreds of thousands or millions of lines of code per hour.
The STAC program includes four Technical Areas (TAs). Technical Area One (TA1) performers are the Research and Development (R&D) teams charged with the development of new program analysis techniques and tools to identify algorithmic resource usage vulnerabilities in software. TA2 performers are the Adversarial Challenge (AC) teams charged with producing challenge programs with known algorithmic resource usage vulnerabilities for use in testing within the STAC program. In order to measure technical progress, there will be a series of competitive engagements throughout the STAC program in which R&D teams will attempt to use their techniques and tools to find the algorithmic resource usage vulnerabilities in the challenge programs produced by the Adversarial Challenge performers. TA3 is the Control Team performer charged with applying present-day analysis techniques to the same problems as the R&D teams during engagements in order to provide a baseline for comparison. TA4 is the Experimentation Lead (EL) performer who will plan each engagement, manage the event and collect measurements of the results.
The STAC program will kick-off in April, 2015 and will be 48 months in duration.