2. Introduction
This work was performed by Iowa State University (ISU) and was issued by the Air Force Research Laboratory (AFRL) under Cooperative Agreement No. FA8750-15-2-0080, Space/Time Analysis for Cybersecurity (STAC). Our team is composed of Iowa State University (ISU) as the prime and ENSOFT Corp. as a subcontractor, each of which brought a unique capability to this project.
Suresh Kothari, the principal investigator, and his team at Iowa State University have a track record of innovative advancements in applications of program analysis. Wei Le, a co-principal investigator has extensive experience in hybrid analysis of loops. Srikanta Tirthapura is also a co-principal investigator and has experience in scalable graph algorithms and databases. Finally, Jeremías Sauceda, a co-principal investigator and his team at ENSOFT have extensive experience building highly scalable static analysis tools.
As described by DARPA STAC BAA:
The STAC program seeks 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. STAC seeks new techniques and tools; efforts to merely apply existing techniques and tools to finding space/time vulnerabilities are out of scope.
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 human component of semi-automated analysis time tends to dominate the automated component, as typical automated program analysis tools require the human analyst to invest considerable initial effort in preparing the software to examine for consumption by the automated tool and later in distinguishing between reports that represent actual vulnerabilities from those that are merely false alarms. Reducing the burden of manual annotation appears likely to be a key part of increasing speed, as is reducing false alarms (that is, increasing precision) while maintaining an acceptably low missed detection rate (that is, decreasing the cases in which the analysis is unsound).
3. Technical Approach
The Space/Time Analysis for Cybersecurity (STAC) program was designed to identify vulnerabilities related to the space and time resource usage behavior of algorithms in Java bytecode applications. The goals as set in the program BAA are listed below:
- Develop automated program analysis techniques and tools that a human analyst can use to identify algorithmic resource vulnerabilities in software, with equal attention to vulnerabilities to both algorithmic complexity and side channel attacks in both space, and time-based variations. 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.
- Conduct novel research that leverages advances in program analysis to develop innovative capabilities, far beyond existing practices, to detect highly sophisticated algorithmic resource attacks that the DoD needs to be prepared for.
- It is reasonable to expect the human analysts who would ultimately use the kinds of tools developed in the STAC program to have a level of general software development expertise, equal to the developers of the target software being examined. As well as, a level of familiarity with the target software’s management and operation equal to that of a skilled user or administrator.
Our high-level technical approach to detect sophisticated resource usage vulnerabilities is driven by the following analysis guidelines:
- Full Automation to discover suspicious program segments.
- Human-on-loop Static Analysis to gather corroborating evidence.
- Human-on-loop Dynamic Analysis to understand dynamic behaviors and generate exploits.
In the next section, we will elaborate on the technological advances for each of the above analysis guidelines.