← DARPA STAC
Section 1

Executive Summary

RULER: A System to Detect Resource Usage Vulnerabilities Within Software

Contents

1. Executive Summary

Space-Time Resource Usage (STRU) vulnerabilities are rooted in the space and time complexities of externally controlled execution paths containing loops. The STAC program considers two kinds of STRU vulnerabilities: algorithmic complexity (AC) and side channel (SC) vulnerabilities. AC vulnerabilities involve execution paths with high space or time complexity that are triggered by relatively small inputs. SC vulnerabilities involve a set of execution paths associated with a secret that can be inferred from variations in space or time complexities along those paths.

At the extreme, a completely automated detection of STRU vulnerabilities amounts to a solution of the halting problem [1], an unsolvable problem whose roots go back to the Continuum Hypothesis in 1878 by Cantor [2] that later resulted in the proofs of undecidability and incompleteness of axiomatic mathematics by Gödel [3] and Cohen [4]. The good news is that our adversaries cannot solve the halting problem either. Thus, detecting STRU vulnerabilities is a challenging, but not impossible program analysis endeavor, especially when the pragmatic goal is to surpass the capabilities of the adversaries. Our novel solution RULER (Resource Usage vuLnerability identifiER) pioneers a revolutionary machine-human integration that helps it scale to large software while maintaining accuracy in detecting sophisticated STRU vulnerabilities.

Section 6.1 gives a summary of our results in the STAC engagements. Our success on STAC is directly attributable to the identification of, and novel solutions for, the following research questions:

  1. How to mathematically model space-time complexities of novel, sophisticated, and domain-specific STRU vulnerabilities?
  2. How to statically compute a program’s relevant behaviors to deal with the path explosion problem?
  3. How to effectively leverage the strengths of both static and dynamic program analysis to verify and validate software anomalies?
  4. How can a machine-human analysis system deal with intractable problems in program analysis to detect novel, sophisticated, and domain-specific STRU vulnerabilities?

To address the above research questions, our research and technical approach to detect sophisticated resource usage vulnerabilities was focused on addressing the inherent program analysis challenges in the following categories:

  1. Loop Modeling for AC/SC vulnerabilities
  2. Execution Path Sensitive Analysis
  3. Composable Accuracy Boundary aware analysis
  4. Interaction and Programmable What-if Reasoning
  5. High level abstractions to model vulnerability mechanisms

Section 2 gives an overview of the project. Section 3 lists our technical approach. Section 4 enumerates the technological advances we have made in RULER to solve the STAC problem. Section 5 gives details on how we apply the technological advances to solve STAC engagement problems. Section 6 gives a summary of our Engagement results. This is followed by our Concluding remarks in Section 7 and a list of our publications and presentations in Section 8.