Generating Predicate Callback Summaries for the Android Framework

Danilo Dominguez Perez, Wei Le

TL;DR

This paper introduces Predicate Callback Summaries (PCSs), a novel technique to automatically model the control flow of callbacks within Android API methods. By generating these summaries, the authors enable more precise static analysis and testing of Android applications, particularly in understanding complex inter-callback sequences and identifying infeasible execution paths.

What Problem Does This Paper Address?

Debugging and analyzing Android applications is notoriously difficult due to the missing explicit control flow information for callback sequences. While GUI events are a known driver of callbacks, the authors highlight that Android API calls also play a crucial, often overlooked, role in determining callback order. Manually modeling this complex control flow within the ever-evolving Android framework is infeasible. Existing tools struggle to capture these inter-callback relationships, leading to potential bugs, vulnerabilities, and imprecise analysis results.

Methods

The core contribution is the Predicate Callback Summary (PCS), a graph-based representation that captures:

  • Callback sequences: The order in which callbacks are invoked.
  • Predicates: The conditions under which callbacks are executed.
  • Updates: Statements that modify values affecting these predicates.

The authors developed a static analysis framework called Lithium to automatically compute PCSs from Android API method source code. The process involves:

  1. Identifying Callback Nodes: Locating call sites that match known callback signatures.
  2. Computing Predicate Nodes: Identifying conditional branches that influence callback execution.
  3. Summarizing Predicate Nodes: Abstracting local variables in predicates to symbolic expressions using backward symbolic substitution.
  4. Computing Update Nodes: Finding assignments and framework calls that can alter predicate outcomes.
  5. Generating Summary Graphs: Constructing the PCS by connecting these nodes based on control flow.

These PCSs are then applied to construct inter-callback Inter-Procedural Control Flow Graphs (ICFGs) for Android apps, effectively linking API calls to their corresponding callback sequences.

Datasets

The authors analyzed 1000 Android apps from F-Droid and the Google Play market to understand API call usage. They generated PCSs for the top 500 frequently used Android API methods. For evaluation, they selected 14 random Android apps from the F-Droid repository and constructed their inter-callback ICFGs using the generated summaries. Dynamic traces were generated using manual and random testing (Monkey) to validate the static analysis results.

Key Insights and Ideas

  • Android API calls are critical for callback sequencing: The paper strongly emphasizes that focusing solely on GUI events misses a significant portion of what drives callback execution in Android apps.
  • Manual modeling is unsustainable: The sheer size and rapid evolution of the Android framework make manual control flow modeling for callbacks impractical.
  • PCSs bridge the gap: The PCS provides a concise, automated way to represent complex callback logic within API methods, making it accessible for analysis tools.
  • Predicates and updates are key to infeasibility detection: By capturing the conditions for callback execution and the factors that influence them, PCSs enable the identification of paths that can never occur in reality, reducing false positives in analysis.
  • Summaries enable scalable inter-callback analysis: The generated PCSs are significantly smaller than full ICFGs, allowing for efficient construction of app-level inter-callback ICFGs.

Key Results

  • Compact Summaries: PCSs were, on average, 99% smaller than the original ICFGs of the API methods.
  • Scalable Computation: Generating PCSs for 500 API methods took an average of 34.5 seconds, with 372 methods completing in under 10 seconds.
  • Precise Analysis: The generated PCSs allowed for the construction of inter-callback ICFGs that connected sequences of up to 44 callbacks.
  • Infeasibility Detection: The system successfully identified infeasible callback paths, improving the precision of static analysis.
  • Validation: A comparison with dynamic traces showed that the static analysis could cover, on average, 49% of callbacks and 96% of traces across 14 apps.

Limitations and Future Work

  • Call Graph Imprecision: The primary source of imprecision in PCS generation stems from the inherent complexity and potential inaccuracies of call graphs for the Android framework. Heuristics were used to mitigate this, but they can lead to false negatives.
  • Handling Internal Objects: The current analysis struggles with object receivers that are internal to the framework and not directly passed from the app.
  • Future Work: The authors plan to integrate their inter-callback ICFGs with GUI-based control flow analysis for a more comprehensive view. They also aim to use more precise call graph and points-to analysis algorithms to improve accuracy and explore better ways to handle internal objects.

Summary updated

Abstract

One of the challenges of analyzing, testing and debugging Android apps is that the potential execution orders of callbacks are missing from the apps' source code. However, bugs, vulnerabilities and refactoring transformations have been found to be related to callback sequences. Existing work on control flow analysis of Android apps have mainly focused on analyzing GUI events. GUI events, although being a key part of determining control flow of Android apps, do not offer a complete picture. Our observation is that orthogonal to GUI events, the Android API calls also play an important role in determining the order of callbacks. In the past, such control flow information has been modeled manually. This paper presents a complementary solution of constructing program paths for Android apps. We proposed a specification technique, called Predicate Callback Summary (PCS), that represents the callback control flow information (including callback sequences as well as the conditions under which the callbacks are invoked) in Android API methods and developed static analysis techniques to automatically compute and apply such summaries to construct apps' callback sequences. Our experiments show that by applying PCSs, we are able to construct Android apps' control flow graphs, including inter callback relations, and also to detect infeasible paths involving multiple callbacks. Such control flow information can help program analysis and testing tools to report more precise results. Our detailed experimental data is available at: http://www.cs.iastate.edu/~weile/toolsdata/SummarizeAndroidFramework/lithium.html.
BibTeX
@inproceedings{perez2017generating,
  author = {Danilo Dominguez Perez and Wei Le},
  title = {{Generating Predicate Callback Summaries for the Android Framework}},
  booktitle = {MOBILESoft@ICSE},
  year = {2017},
  url = {https://openreview.net/forum?id=SLCOWlZlD6},
}
Figure