Privacy Analysis of Android Apps: Implicit Flows and Quantitative Analysis

Gianluca Barbon, Agostino Cortesi, Pietro Ferrara, Marco Pistoia, Omer TrippCISIM 2015 · DOI

TL;DR

This paper introduces a novel static analysis framework for Android apps that goes beyond tracking direct data leaks to also identify and quantify "implicit flows" – information leaks that occur through control flow decisions. This approach provides a more comprehensive understanding of privacy risks, enabling more accurate policy enforcement and user awareness.

What Problem Does This Paper Address?

Mobile applications, particularly on Android, handle a vast amount of sensitive user data (e.g., location, device ID). While Android's permission system offers some protection, it's often insufficient, and applications (or their libraries) can inadvertently leak this data. Existing static analysis methods for privacy compliance often struggle with "implicit flows," where a secret value influences program execution (e.g., a decision to send data based on a secret condition) without directly being part of the leaked data. This can lead to false negatives in security analysis, missing subtle but critical privacy vulnerabilities. The paper aims to address this by developing a method that not only tracks explicit data flows but also quantifies the information leakage through implicit flows.

Methods

The core of the paper is an extension of an existing abstract interpretation framework for static analysis. The authors introduce:

  • Extended Atomic Data Expressions: These expressions are augmented to track both explicit and implicit flows. Implicit flows are captured by including the Boolean expressions of control statements (like if and while) as part of the data expression.
  • Quantitative Semantics: This component assigns a "quantity" (expressed in bits) to the information leaked through implicit flows. This is achieved by defining a quantitative domain and a function that updates these quantities based on operations and control flow.
  • Abstract Semantics: To make the analysis computable and scalable, the authors define an abstract domain that approximates the concrete semantics. This involves abstracting data labels and, crucially, abstracting quantities as intervals to represent the range of possible information leakage.
  • While Loop Analysis: A specific technique is introduced to handle while loops by first performing an interval analysis to approximate the number of iterations, and then using this to quantify the information leaked over multiple iterations.

Datasets

The paper evaluates its framework on examples from the DroidBench application set [20]. DroidBench is a standard benchmark for testing static and dynamic analysis tools for Android applications, specifically designed to include various privacy-sensitive scenarios. The authors selected examples that specifically deal with implicit flows.

Key Insights and Ideas

  • Implicit Flows are Crucial for Privacy: The paper strongly emphasizes that ignoring implicit flows leads to significant blind spots in privacy analysis, as many subtle leaks can occur through control flow.
  • Quantifying Leakage is Powerful: Moving beyond a simple "leak or no leak" detection to quantifying the amount of leaked information provides a more nuanced understanding of risk and allows for more sophisticated policy enforcement (e.g., setting quantitative thresholds).
  • Abstract Interpretation is a Good Fit: The use of abstract interpretation provides a sound and computable way to analyze all possible program executions, making it suitable for identifying potential leaks that might not occur in every dynamic run.
  • Hybrid Policies are Enabled: The framework supports policies that can combine qualitative (e.g., "don't leak location") and quantitative (e.g., "leak no more than X bits of location data") constraints.

Key Results

The paper demonstrates the effectiveness of its framework through concrete and abstract analyses of several examples (ImplicitFlow1, ImplicitFlow2, ImplicitFlow3) from DroidBench.

  • Qualitative Analysis: The framework successfully identifies implicit flows in scenarios where other methods might fail, such as those involving custom transformations of private data or object creation based on password checks.
  • Quantitative Analysis: For ImplicitFlow1, the analysis quantifies the leakage from a loop, estimating it at 4 bits based on the number of iterations and the bit leakage per iteration. For ImplicitFlow2 and ImplicitFlow3, it identifies a 1-bit leakage from an if statement. The paper shows how these quantities are propagated through the program.

Limitations and Future Work

  • Approximation of Loop Iterations: The paper acknowledges that the number of while loop iterations is approximated using interval analysis, which can lead to over-approximation of leakage. Future work could involve more precise loop analysis.
  • Simplification of Operators: For simplicity, the paper mentions that some library functions were simplified, and certain operators were handled in a basic manner. Extending the semantics to cover a wider range of real-world library functions and operators would be beneficial.
  • Scalability: While abstract interpretation is designed for scalability, the paper doesn't provide extensive empirical results on the performance and scalability of the framework on large, real-world applications.
  • Policy Enforcement: The paper focuses on analysis and quantification. Future work could explore how to automatically enforce the identified policies based on the quantitative results.

Summary updated

BibTeX
@inproceedings{barbon2015privacy,
  author = {Gianluca Barbon and Agostino Cortesi and Pietro Ferrara and Marco Pistoia and Omer Tripp},
  title = {{Privacy Analysis of Android Apps: Implicit Flows and Quantitative Analysis}},
  booktitle = {CISIM},
  year = {2015},
  doi = {10.1007/978-3-319-24369-6\_1},
}
Figure