Comprehension-Driven Program Analysis for
Malware Detection in Android Apps^∗

I. Introduction

Android commands 80% market share¹ in smartphone operating systems and has more than a million user applications (“apps”) that can run on Android-based smartphones. A report published by Public Intelligence² says that 79% of all mobile threats in 2012 targeted Android. This research to detect sophisticated malware in Android apps is funded by the Defense Advanced Research Projects Agency (DARPA) Automated Program Analysis for Cybersecurity (APAC) program³. The goal of APAC program is to develop techniques and tools to detect malware in Android apps.

¹ http://www.idc.com/getdoc.jsp?containerId=prUS24257413

² http://info.publicintelligence.net/DHS-FBI-AndroidThreats.pdf

³ http://www.darpa.mil/Our_Work/I2O/Programs/Automated_Program_Analysis_for_Cybersecurity_(APAC).aspx. We are sponsored under agreement number FA8750-12-2-0126.

The DARPA APAC program is concerned with sophisticated malware, especially complex malware resulting from insider threats. The Red teams in the DARPA APAC program are engaged in designing such malware to test the bounds of malware detection technology being developed by the Blue teams. The sophisticated malware can be divided into three broad categories: (a) confidentiality leaked (e.g. GPS location is leaked to the adversary), (b) integrity breaches (e.g. incorrect GPS location is displayed under certain conditions), (c) denial of service (e.g. malware runs loops to drain the battery). Inter-procedural data and control flow analyses are required to piece together sophisticated malware as it typically contains scattered and cleverly hidden parts. For example, the URL for the adversary’s website to which confidential information gets leaked may be assembled through scattered string concatenation operations hidden in different places in the app.

II. Research Challenges

The fundamental challenge is to design scalable and accurate analysis techniques to detect malware by taking into account the rich and complex Android runtime semantics. There are a number of other research challenges. For example, the analysis must take into account the complexity of how permissions are handled by Android’s Intent system, used extensively for inter- and intra-application communication. Some Intents can only be sent by applications with appropriate permissions.

Here, we will cover two research challenges; these are the key challenges that call for a new disruptive innovation, apart from current research practices for detecting malware in Android apps including the ones that employ static analysis [1], [2], [3], [4], [5], [6], [7], [8] and the other that use dynamic analysis [9], [10].

A. Obscure Interprocedural Flows

We call it an obscure inter-procedural flow when the control flow is altered indirectly, i.e. not through a call to an explicitly defined method. We will further refer to it as visible or invisible depending on whether it involves a visible programming mechanism (e.g. reflection or dynamic dispatch) or not. Invisible obscure flows occur due to asynchronous processing. Obscure flows pose a time consuming challenge to the analyst as the flow is not directly observable as a control flow or data flow edge in the program representation graph. In fact malware may not be completely observable in one application because it is enacted through flows between two or more collaborating apps.

Android incorporates rich and complex semantics to facilitate development of mobile apps. In particular, the Android semantics involves semantics to support asynchronous processing. For example, AsyncTask class allows to perform background operations and publish results on the UI thread without having to manipulate threads and/or handlers. Another example of obscure flows is Android Intents⁴. In Android, an Intent object is a message passing mechanism used to signal either explicitly and implicitly the transfer of control and information to another Android component (Activity, Service, Broadcast Receiver).

⁴ http://developer.android.com/reference/android/content/Intent.html

Challenge: The analysis must resolve the obscure flows as accurately as possible. In particular, the analysis must bridge the gaps due to flows through the Android APIs.

B. Minimizing the Human Effort

Current malware detection happens in two passes: (1) first pass (Machine): the detection tool works automatically to report a set of malware possibilities, (2) second pass (Human): the analyst works manually to sort out false positives. The outcomes are either vulnerabilities detected by the machine and verified by the human, or vulnerabilities detected by the machine and rejected by the human. Human verification can become labor-intensive unless machine produces good evidence that human can understand easily. Moreover, to minimize false negatives, automated analyses over-approximate and err on the side of false alarms rather than missed detections. Overall, the human effort for verifying the machine results can be very high and the paradigm does not scale to large software.

Another serious issue is that the human has no help from the machine to hypothesize, refine, and postulate application-specific malware possibilities that are not on the radar of the automated analysis.

Challenge: To minimize the human effort, the detection system must provide: (a) support cross-verification of automatically detected malware by providing good evidence to the human, (b) assist the human in performing what-if experiments to to hypothesize, refine, and postulate application-specific malware possibilities.

III. Technical Approach

The key challenges as described above are addressed as follows by our approach.

A. Human-in-Loop Coordination to Minimize Human Effort

As shown in Figure ??(b), we have a tightly coupled human-in-loop coordination as opposed to the 2-pass approach.

Our approach incorporates a Query-Model-Refine (QMR) platform developed by EnSoft; it provides the tool mechanics necessary for our tightly coupled human-in-loop approach.

Like the database language SQL, the platform provides a composable query language which can be used either interactively or embedded as a script in a Java program to create programs to analyze programs. Because of the query language, the user is freed from the lower-level details of static analysis and enabled to focus efforts on the malware detection strategies at higher-level semantics. The “model” and “refine” capabilities work in conjunction with the query language to facilitate human comprehension by creating effective abstractions of large software. The human and the machine communicate through the medium of software graphs and queries on such graphs. Analysis results and supporting evidence are presented through compact graphical visualizations.

Our approach can minimize the human effort significantly beacuse the human can use the available evidence to target her effort in performing further machine-assisted reasoning. There is greater opportunity to detect malware that is not on the radar of the automated analyzer, as the human is aided by the interactive what-if experimentation capability provided by of the machine. Thus, compared to a two-pass approach, our approach can increases automation, reduces human effort and error, and increases scalability. as it evolves, our research will scientifically quantify these benefits with empirical experimentation.

B. Modeling Obscure Flows

We are developing a variety of techniques to resolve obscure flows. We will summarize one such technique here. We have a three-event model to characterize obscure flows. The events are: (i) setup, (ii) source, and (iii) destination. The model is applicable to a variety of obscure flows encountered in Android such as BroadcastReceiver⁵, AsyncTask⁶, and Handler⁷.

⁵ http://developer.android.com/reference/android/content/BroadcastReceiver.html

⁶ http://developer.android.com/reference/android/os/AsyncTask.html

⁷ http://developer.android.com/reference/android/os/Handler.html

The following summarizes how AsyncTask obscure flow can be modeled using the source and destination events. We will illustrate it with a concrete code example in the next section shown in Listing 1.

In the source event (line 8) AsyncTask.execute() is called on object Task (of type WriteTask — an instance of AsyncTask). This asynchronously transfers the execution to the destination event (line 15): method doInBackground() in class Task. Logically, the obscure flow can be identified and connected as follows:

1) Identify source events: all invocations of AsyncTask.execute() — stored as I_e.

2) For each i_e ∈ I_e, identify the invokee object on which invocation i_e is made (as in line 8 of Listing ??).

3) Connect obscure flow represented by (i) i_e from step 2 (the source event) and (ii) the method doInBackground() in the class of the invokee object corresponding to i_e from step 2 (the destination event).

C. Obscure Flow Example

This example illustrates: (a) asynchrous processing obscure flows due to AsyncTask in Android, (b) an example evidence produced by machine to support automatically detected mlaware. This evidence is created by resolving the obscure flow and incorporating it explicitely in a program graph to show how sensitive information reaches malicious sink through the obscure flow.

Consider the sample malware activity shown in Listing 1. In the code-block corresponding to read event the malware reads the mobile phone’s device ID (lines 5-6). The device ID is then passed as argument to function execute() in class WriteTask. Class WriteTask extends AsyncTask, thus, the call to WriteTask.execute() actually calls AsyncTask.execute(). The call to Android API AsyncTask.execute() is an asynchronous call. That is, the call is returned immediately, and in a separate thread of execution, Android calls function doInBackground() in class WriteTask passing the device ID as the argument — the same argument that the API AsyncTask.execute() received in line 8 in Listing 1. In function doInBackground() the device ID is finally leaked to the hypothetical malicious URL “www.evil-URL.com”. The flow is obscure between the read event and the leak event; the call to function doInBackground() in class WriteTask (the leak event); it will not appear in the call graph of function update() in class MainActivity (the read event).

/*Malware read block*/
public class MainActivity extends Activity {

public void update(Activity activity) {
  TelephonyManager tManager = (TelephonyManager) activity
       .getSystemService(Context.TELEPHONY_SERVICE);
  String imei = tManager.getDeviceId();
  WriteTask task = new WriteTask();
  task.execute(imei);
}
}

/*Malware leak block*/
public class WriteTask extends AsyncTask{
@Override
protected void doInBackground(String... params) {
  try {
    URL url = new URL("www.evil-URL.com");
        URLConnection connection = url.openConnection();
          OutputStreamWriter out = new OutputStreamWriter
               (
      connection.getOutputStream());
        out.write(params[0]);
        out.close()
    }
  catch(Exception e){
    }
}
}

Listing 1: An malware example using asynchronous processing.

The above obscure flow makes it a challenge to identify the corresponding leak event. Often, things get more complex because of a large number of such disconnected read and leak events. Then, the malicious flow is just one among the many other legitimate flows - rendering itself hard to be discovered. The need to keep the GUI elements always responsive to user-interactions makes it natural to offload time consuming tasks to another thread of execution and that makes asynchronous processing is so abundant in Android apps.

Obscures flows can be computed using a specified model as discussed above. For example, the obscure flow in Fig ?? can be computed and made explicit by adding a data flow edge from the arguments passed to the function call of AsyncTask.execute() in MainActivity.update() (line 8 in Listing 1) to the parameters received by WriteTask.doInBackground() (line 15 in Listing ??). The resulting connected flow is shown in Fig. 2. Similarly, a control flow edge is added from the invocation of function AsyncTask.execute() in MainActivity.update() to function WriteTask.doInBackground() representing the transfer of execution-flow on the function call.

IV. Related Work

Existing automated Android malware detection and classification methods fall into two general categories: 1) signature-based and 2) machine learning-based. Signature-based approaches can be easily evaded by bytecode-level transformation attacks. Learning based approaches extract features from application syntax, rather than program semantics, and are also subject to evasion. To perform semantically rich analysis, the paper [?] proposes a representation of source code called a code property graph that merges concepts of classic program analysis, namely abstract syntax trees, control flow graphs and program dependence graphs, into a joint data structure. Similarly, our approach also involves analysis using an overarching sematically rich program graph. However, the important differences we decouple the domain-specific analysis goal from its underlying mechanism by splitting analysis into two distinct phases. In the first phase, polynomial-time static analyzers index the software AST, building a rich graph database. In the second phase, users can explore the graph directly or run custom analysis scripts written using a convenient API. These features make our approach ideal for both interaction and automation.

Holavanalli et al. [11] address the problem of connecting asynchronous flows in Android for providing Flow Permissions. The authors use static analysis of call graphs to extract semantic information based on API calls and inform the user about the behavior of an app. In order to get a complete call graph that incorporates the obscure flows in Android (through AsyncTasks and Message Handlers), they augment the call graph to include edges corresponding to these control flows. Chen et al. [12] present a technique for checking the temporal order in which an application interacts with the Android APIs. Lu et al. [13] describe the CHEX static analysis framework for detecting malware that include hijack-enabling flows by conducting reachability tests on system dependence graphs. In order to identify the multiple entry points in the app, they model the asynchronous executions such as AsyncTasks, MessageHandlers, etc. We are advancing the modeling techniques introduced by thse researchers.

V. Conclusion

This New Ideas and Emerging Results (NIER) paper about our research recently funded by the DARPA APAC program describes the key challenges for detecting sophisticated malware that is of concern to the US Department of Defense. We present our approach to address these challenges.

Our solution pioneers a revolutionary machine-human integration that helps it scale to large software while maintaining accuracy. Innovative aspects of our research include:

• A decoupled architecture with a program analysis platform called Atlas and an Android security toolbox that includes analysis and detection scripts written using Atlas APIs.
• We estimate that implementing our analyzers in terms of these existing APIs will provide a 10× improvement in developer productivity, resulting in a faster implementation of analyzers. Atlas APIs provide the necessary raw materials to implement flow-sensitive, path-sensitive, type-sensitive, context-sensitive, and object-sensitive analyses, while allowing an analyzer to choose which combination of these aspects to utilize. Consequently, it is far less labor-intensive to implement a custom analyzer that achieves a desired time/precision trade-off.
• Atlas provides APIs to analyze Java byte code that are nearly identical to those that it provides for Java source code.
• The human and the machine communicate through the medium of software graphs and queries on such graphs. In this integrated approach, analysis results will be presented through compact graphical visualizations. This output amplifies human intelligence, minimizes human error, and allows decision-making to scale to the largest software systems.