Eventually Sound Points-To Analysis with Specifications

Osbert Bastani, Rahul Sharma, Lazaro Clapp, Saswat Anand, Alex Aiken

TL;DR

This paper introduces "eventually sound" static analysis for programs with missing code, like Android apps relying on the framework. By combining optimistic static analysis with runtime checks, it guarantees that any errors are caught during execution, and the analysis eventually becomes fully sound, all while keeping runtime overhead low.

What Problem Does This Paper Address?

Modern software, especially mobile applications, heavily relies on large libraries and frameworks (like the Android framework). Analyzing these systems statically is challenging because the source code for these components is often unavailable or too complex to analyze (e.g., native code, reflection). This "missing code" forces static analyses to either make unsound, optimistic assumptions or overly pessimistic ones, rendering them imprecise or unreliable. For security-sensitive applications like malware detection, this is a critical issue: unsound analyses can miss vulnerabilities, while overly pessimistic ones produce too many false positives to be useful.

Methods

The core of the paper is the eventually sound points-to analysis implemented in a tool called Optix. Here's how it works:

  1. Optimistic Static Analysis: Optix first performs a standard points-to analysis, but it optimistically assumes all missing code (e.g., the Android framework) is empty. This is fast but potentially unsound.
  2. Runtime Monitoring: To bridge the gap, Optix instruments the available code (the app itself) with lightweight runtime checks. These checks are designed to detect the first counterexample to the optimistic assumptions that occurs during execution.
  3. Eventual Soundness: This combination provides "eventual soundness."
    • Dynamic Soundness: If an unsound assumption is violated during execution, the runtime check catches it immediately, allowing the program to be terminated to prevent harm.
  4. Static Soundness Convergence: The system guarantees that only a finite number of counterexamples will ever be reported. As these counterexamples are reported, they are fed back to the static analysis, which updates its knowledge. This process ensures that the static analysis eventually becomes sound with respect to all subsequent executions.
  5. Proxy Objects: To handle allocations within missing code, Optix introduces "proxy objects." These abstract representations allow the analysis to reason about objects created in missing code without needing their actual source.
  6. Specification Inference: Reported counterexamples are also used to infer specifications for the missing code. This helps improve the static analysis for future runs and for other applications.

Datasets

The evaluation uses a benchmark of 73 Android apps. These apps are sourced from two collections:

  • Industry Benchmark (40 apps): Primarily malware from the Google Play Store that leak sensitive information.
  • DARPA Benchmark (33 apps): Challenging malware instances developed as part of a DARPA project.

The paper notes that the DARPA benchmark apps cannot be released publicly.

Key Insights and Ideas

  • Runtime Checks as "Bug Detectors" for Static Analysis: The most striking idea is using runtime execution not just to find bugs directly, but to improve a static analysis. The runtime checks act as a feedback loop, identifying where the static analysis made incorrect assumptions.
  • "Eventual Soundness" is a Practical Compromise: Achieving full static soundness for complex, dynamic systems like Android is often intractable. "Eventual soundness" offers a pragmatic middle ground: it guarantees safety during execution and eventual correctness after sufficient observation, which is often sufficient for practical applications.
  • Low Overhead is Achievable: A major concern with runtime monitoring is performance overhead. The paper demonstrates that by carefully selecting what to monitor (e.g., function calls and allocations, not every single operation) and by leveraging the "first counterexample" principle, the overhead can be kept acceptably low for most real-world apps.
  • Proxy Objects Bridge the Gap: The introduction of proxy objects is a clever way to allow the static analysis to reason about objects allocated in missing code, enabling more precise analysis of aliasing and other properties.

Key Results

  • Manageable Runtime Overhead: For over 90% of apps, the runtime overhead was less than 20%, with a median overhead of 4.6%. Even in the worst-case scenario (no prior specifications, maximum monitoring), more than half of the apps had less than 10% overhead.
  • Reduced Overhead with Specifications: Adding specifications significantly reduced overhead. For example, adding specifications for at most 10 Android framework methods could reduce overhead below 20% for outlier apps.
  • Counterexamples Converge: The number of reported counterexamples generally decreased over time, indicating that the analysis was indeed converging towards soundness. About 45% of apps reported no counterexamples.
  • Improved Information Flow Analysis: When used with an information flow client, inferred specifications significantly increased the number of detected information flows, demonstrating the practical utility of the approach for security analysis. For instance, combining baseline specifications with inferred ones found 39 additional flows compared to just the baseline.

Limitations and Future Work

  • Assumption of No Global Variables: The current implementation assumes library functions do not access global variables. While empirically found to hold for their benchmark, extending this would require additional instrumentation.
  • No Instrumentation of Missing Code: The approach relies on instrumenting only available code. This means that if the missing code itself needs to be analyzed for properties beyond points-to (e.g., sources/sinks for information flow), it must be specified.
  • Dynamic Analysis Underapproximation: While the system aims for eventual soundness, the underlying dynamic execution is still an underapproximation. This means that some malicious behaviors might not be triggered during testing, highlighting the need for continued monitoring in production.
  • Future Work: The authors suggest extending the analysis to handle global variables, exploring more sophisticated client analyses (like information flow), and investigating object-sensitive and context-sensitive analyses. They also mention the possibility of inferring specifications for sources and sinks in missing code.

Summary updated

Abstract

Static analyses make the increasingly tenuous assumption that all source code is available for analysis; for example, large libraries often call into native code that cannot be analyzed. We propose a points-to analysis that initially makes optimistic assumptions about missing code, and then inserts runtime checks that report counterexamples to these assumptions that occur during execution. Our approach guarantees eventual soundness, which combines two guarantees: (i) the runtime checks are guaranteed to catch the first counterexample that occurs during any execution, in which case execution can be terminated to prevent harm, and (ii) only finitely many counterexamples ever occur, implying that the static analysis eventually becomes statically sound with respect to all remaining executions. We implement Optix, an eventually sound points-to analysis for Android apps, where the Android framework is missing. We show that the runtime checks added by Optix incur low overhead on real programs, and demonstrate how Optix improves a client information flow analysis for detecting Android malware.
BibTeX
@inproceedings{bastani2019eventually,
  author = {Osbert Bastani and Rahul Sharma and Lazaro Clapp and Saswat Anand and Alex Aiken},
  title = {{Eventually Sound Points-To Analysis with Specifications}},
  booktitle = {ECOOP},
  year = {2019},
  doi = {10.4230/lipics.ecoop.2019.11},
}

Loading related content...

Figure