Information-Flow Analysis of Android Applications in DroidSafe – Gordon et al. 2015

This is the first of three papers we’ll be looking at this week from the NDSS’15 conference that took place earlier this month.

DroidSafe is a tool that looks for potential leaks of sensitive information in Android applications. And it works incredibly well!

DroidSafe detects all malicious information flow leaks inserted into 24 real-world Android applications by three independent, hostile Red-Team organizations. The previous state-of-the art analysis, in contrast, detects less than 10% of these malicious flows.

The definition of sensitive data includes the unique device ID, sensor data (location, acceleration etc.), file data, image data and meta-data, email and SMS messages, passwords, network traffic and screen-shots.

DroidSafe is a static analysis framework that analyzes the application before it executes. Given the size, richness, and complexity of the Android API and runtime (about 1.3 million lines of code) this is a significant challenge. It’s important to detect leaks, and to be practical it’s also important not to generate too many false positives.

The Android API version 4.4.3 includes over 3,500 classes visible to an application developer. Analyzing the complete source code for the API is exceedingly difficult because it is implemented over multiple languages and some of the implementation is device-specific. Thus, static analysis frameworks rely on modelling the Android API semantics.

Beyond the sheer scale of the challenge, event dispatching, callbacks, and inter-component communication all add to the difficulty. Event dispatching can lead to many different orderings of events, and event handlers are not called directly in application code. Callback handlers can include arguments passed by the runtime to the application for processing – which could include data from the application (tainted data), depending on the execution sequence prior to the event. Inter-component communication (ICC) is via Intent objects – and the resolution of an Intent destination is complex and may be dynamically determined.

Starting with the Android Open Source Project (AOSP) source code, “it quickly became apparent that the size and complexity of the Android environment made it necessary to develop the model and the analysis together as an integrated whole, with the design decisions in the model and the analysis working together synergistically to enable an effective solution to the Android static information-flow analysis problem.” Stubs were developed to cover code outside of the AOSP Java codebase:

Examples of semantics missing in the AOSP and added via accurate analysis stubs include native methods; event callback initiation with accurate context; component life-cycle events; and hidden state maintained by the Android runtime and accessible to the application only via the Android API.

For the information flow analysis, 4051 sensitive source methods and 2116 sensitive sink methods were manually identified and classified. In addition the implementation of 117 classes in the Java standard library and Android library were carefully simplified to increase precision and decrease analysis time (on the order of 5 to 10 minutes). At the core of the model are 550 Android classes that account for over 98.1% of the total calls made by over 95K applications downloaded from the Google Play Store. These were manually reviewed to confirm that the implementation fully covered semantics for data flow, object instantiation and aliasing, and that the event callbacks defined are called explicitly by the model with the proper context.

At the core of the approach is an analysis method called ‘Points-to’ analysis:

Points-to analysis (PTA) is a foundational static program analysis that computes a static abstraction of all the heap locations that a pointer (reference) variable may point to during program execution. In addition to the points-to relation, points-to analysis also constructs a call graph as modern languages re-quire points-to results to calculate targets for dynamic dispatch and functional lambda calculations.

The PTA implementation implements object sensitivity (identifying flows that originate in different object instances). “Object sensitivity is notoriously difficult to understand and implement.” It also requires large amounts of memory. Prior to optimising, several applications could not be analysed even with 64GB of heap memory. With optimisations, all tested applications now fit in under 34GB.

The optimisation involved analysing a suite of Android applications to determine an appropriate context-depth (from 0 to 4) for each API class. (Traditional approaches use a fixed context depth).

For inter-component communication, string analysis is performed to work out possible runtime targets using the JSA String Analyzer. This creates a regular expression representing the possible values of the string value.

After JSA is run, we replace resolved string values in the application code with constants representing their computed regular expression, and perform a pass of our points-to analysis such that these values can be propagated globally.

Additional transformations are made for ICC initiation calls and Android Service components to improve model precision.

The resulting information flow analysis is built on top of the Soot Java Analysis framework and comprises approximately 70Kloc of Java code.

Our information-flow analysis computes an over-approximation of all the memory states that occur during the execution of a program. The analysis is designed as a forward data-flow analysis. For each type of statement, we define a transfer function in terms of how it changes the state of memory.

We divide memory into four separate areas that store local variables, instance fields, static fields, and arrays, reflecting the semantics of the Java programming language.

Each of the memory areas is modelled as a function whose codomain consists of a set of information values. An information value is a tuple of the type of information and the source code location where the information was first injected. Our analysis can identify not only the kind of information being exfiltrated but the code location of the source.

Results

We evaluate DroidSafe on 24 complete real-world Android applications that, as part of the DARPA Automated Program Analysis for Cybersecurity (APAC) program, have been augmented with malicious information flow leaks by three hostile Red Team organizations. The goal of these organizations was to develop information leaks that would either evade detection by static analysis tools or overwhelm static analysis tools into producing unacceptable results (by, for example, manipulating the tool into reporting an overwhelming number of false positive flows). DroidSafe accurately detects all of the 69 malicious flows in these applications (while reporting a manageable total number of flows). A current state-of-the-art Android information-flow analysis system, Flow-Droid + IccTA, in contrast, detects only 6 of the 69 malicious flows, and has a larger ratio of total flows reported to true malicious flows reported.

DroidSafe was also evaluated against the DroidBench suite and gave the highest reported accuracy and highest precision for the suite to date at 94.3% and 87.6% respectively.

Unsurprisingly, DroidSafe gets 100% accuracy and precision on its own test suite – but the next best tool could only achieve 34.9% accuracy and 79.9% precision.

As these results illustrate, DroidSafe implements an analysis of unprecedented accuracy and precision. To the best of our knowledge, DroidSafe provides the first usable information-flow analysis for Android applications.

The Secret Sauce

Our experience developing DroidSafe shows that 1) there is no substitute for an accurate and precise model of the application environment, and 2) using the model to drive the design decisions behind the analysis and supporting techniques (such as accurate analysis stubs) is one effective but (inevitably) labor-intensive way to obtain an acceptably precise and accurate analysis. As long as there are complex application frameworks, we anticipate that making an appropriate set of design decisions (such as the use of a scalable flow insensitive analysis) to successfully navigate the trade-off space that the application framework implicitly presents will be a necessary prerequisite for obtaining acceptable accuracy and precision.