← DARPA STAC
Sections 4.4–5

Targeted Dynamic Analysis and Challenge Applications

RULER: A System to Detect Resource Usage Vulnerabilities Within Software

Contents

4.4 Targeted Dynamic Analysis to Generate Exploits

We developed the Mockingbird framework [2] that combines static and dynamic analyses to yield an efficient and scalable approach to analyze large Java software. The framework is an innovative integration of existing static and dynamic analysis tools and a newly developed component called the Object Mocker that enables the integration. The static analyzers are used to extract potentially vulnerable parts from large software. Targeted dynamic analysis is used to analyze just the potentially vulnerable parts to check whether the vulnerability can actually be exploited.

Mockingbird framework incorporates:

  • The multitude of static analyzers built using the Atlas platform. These analyzers are used to extract the relevant code - the code that is potentially vulnerable.
  • The AFL fuzzer supplemented by the Kelinci, a tool that interfaces AFL to operate on Java programs.
  • The Object Mocker that can automatically create harnesses to apply the AFL fuzzer to dynamically analyze the relevant code extracted using the static analyzers.

The key novelty of the Mockingbird is targeted dynamic analysis (TDA). TDA performs dynamic analysis of just the relevant code using binary inputs. The framework provides the capability to mock any Java object type and produces a testing harness that transforms binary inputs to appropriate object types. For fuzzers such as AFL, users manually create a test harness that translates the binary inputs from the fuzzer to the data structures expected by the target program. Developing the harnesses manually for just the relevant code is difficult and laborious because the program state must be considered as the input. The program state is communicated to the relevant function via the stack memory using function parameters and return values or through the heap memory, using reads and writes to global variables. The harness incorporates mocked objects that mimic the program artifacts that carry the inputs into the relevant code. The Mockingbird framework creates the harnesses automatically. The framework earns its name from the term “mock objects” as used by the testing community.

The Mockingbird framework optionally allows constraints to be placed on the values of object fields that store the encapsulated program data. With this enhancement, it is possible to systematically incorporate domain-specific knowledge into automatically generated test harnesses. For example, if a program only operates on byte arrays that begin with a magic sequence, such as 0xFFD8 in the case of JPEG file formats, then the test harness can simply prefix the program input with the known sequence to increase the chances of quickly driving the program execution in meaningful ways. The Mockingbird framework supports configurable input generation constraints to be specified for test harnesses as a means for injecting domain knowledge.

An Illustrative Example: We examine a DARPA STAC challenge application called BraidIt for AC vulnerabilities. The application’s source code is available at: https://github.com/Apogee-Research/STAC. The case study demonstrates: (1) the use of Mockingbird framework to efficiently discover an algorithmic complexity vulnerability, and (2) a follow-up experiment using Mockingbird’s APIs to create a custom tool for computing program invariants that provide holistic understanding of the vulnerability. The follow-up experiment reveals not just one input but a class of inputs that cause the vulnerability; in particular, it reveals the smallest input that can cause the vulnerability.

5. Analyzing Challenge Applications

It was observed that analysts follow certain patterns in the workflow to find each type of Algorithmic Complexity (AC) or Side Channel (SC) vulnerability (AC Time, AC Space, SC Time, and SC Space). These patterns were distilled and the workflow of analysts was documented. Here are the steps taken for majority of the challenge questions:

5.1 AC Time

  1. Find App entry points using Dashboard (Entry points).
  2. Find a mapping between the app entry points and corresponding request handlers using DataFlow/Taint Analysis toolbox with the help of PCG toolbox for compact graphs.
  3. Find user-input controlled requests that the attacker can leverage using DataFlow/Taint Analysis toolbox.
  4. Find user-input controlled loops reachable from the user-input controlled requests using Loop Catalog, Loop Hierarchy Smart view, and Dataflow/Taint Analysis toolbox.
  5. Find user-input controlled loops that can inflate recursive data structure using Type and Callsite Catalog and Loop Catalog.
  6. Prioritize loops auditing based on domain knowledge, nesting depth, recursion, complexity of terminating conditions, and interaction with Java subsystems using Loop Catalog, Loop Hierarchy Smart view, and Dataflow/Taint Analysis toolbox.
  7. Verify the existence of AC time via Dynamic Analysis.

5.2 AC Space

  1. Find specific operations or types of interest based on the challenge question using Type/Callsite Catalog along with Subsystem Interaction View.
  2. Find App entry points using Dashboard (Entry points).
  3. Answer, “Are the operations or types of interest reachable from entry points (i.e., user-input controlled)?” using Dataflow/Taint Analysis toolbox.
  4. Answer, “Are these operations or types of interest governed by loops or interesting branches that are user-controlled?” using Loop Catalog.
  5. Answer, “What things are being consumed by the operations or types of interest?” using DataFlow/Taint Analysis.
  6. Answer, “Are the things being consumed user-controlled? Can they be inflated or occurs within a loop?” using DataFlow/Taint Analysis.
  7. Understand the inter-procedural relationship and call structure leading to the user-controlled objects that will be consumed using IPCG and Call Graph.
  8. Verify if the inflation in space can be done dynamically to exceed the budget using Dynamic Analysis.

5.3 SC Time

  1. Find objects corresponding to the secret.
  2. Find App entry points using Dashboard.
  3. Find a mapping between the entry points and corresponding request handlers using DataFlow/Taint Analysis with the help of PCG.
  4. Find a mapping between requests and possible responses using DataFlow/Taint Analysis with the help of PCG.
  5. For each mapping of a request to responses, find if there is a user-controlled loop/recursion, intensive operation, or throwing of unhandled exceptions using Loop/Branch Catalog, Type and CallSite View with the help of PCG.
  6. Prioritize audit of request/response mapping based on their affect/relation on revealing the secret.
  7. Check if the differential time can be observed to reveal the secret using Dynamic Analysis.

5.4 SC Space

  1. Find objects corresponding to the secret using DataFlow/Taint Analysis.
  2. Find App entry points using Dashboard.
  3. Find a mapping between requests and request handlers using DataFlow/Taint Analysis along with PCG.
  4. Find app output points using Subsystem Interaction View along with Type and Callsite Catalog.
  5. Determine if output points are, user-input controlled and has a relation to the secret using DataFlow/Taint Analysis.
  6. Study what are the possible ways that an attacker can provide input to inflate theses output controlled objects.
  7. Determine if user-input controlled output points are governed by loops and differential conditions using Loop Catalog along with IPCG and system dependency graph view.
  8. Check if the differential space can be observed to reveal the secret using Dynamic Analysis.