1. Executive Summary
Mobile malware detection can be extremely challenging in the presence of cross-cutting control and data dependencies, invisible control switches due to multithreading or event processing. Moreover, inherent ambiguities of an application’s intent make it difficult to separate malicious behavior from legitimate functionality. Given that provable automation is not possible in all cases, our proposed novel comprehension-driven graph-based approach enables an iterative refinement process capable of quickly discovering sophisticated malware. We were the top-performing Blue team in Phase I and among the top 3 performers in Phase II. We exceeded Phase I and Phase II BAA goals in terms of analysis time, and also in terms accuracy in Phase I. The Red team, however, has clearly shown that malware detection is still an unsolved problem and more research is needed. The program has brought to the surface some of the hard problems of static analysis and the need for a program comprehension technology to enable humans to develop better hypotheses of potential malware.
Our success on APAC is directly attributable to the identification of, and novel solutions for, the following research questions:
- How should a software analysis platform be built to facilitate both automation and human comprehension?
- How can a man-machine analysis system detect novel, sophisticated, and domain-specific malware?
- How can expressive, compact information flow summaries be mined from a library for accurate and scalable partial program analysis?
How should a software analysis platform be built to facilitate both automation and human comprehension?
Existing frameworks were insufficient for our purposes, providing either automation or static visualizations, but we required a flexible and interactive query-model-refine paradigm. To overcome the limitations of prior work and address this research question, we commissioned our subcontractor, ENSOFT, to advance Atlas and its graph schema to meet our need. Atlas employs a graph-based mathematical abstraction of software. It preprocesses the Abstract Syntax Tree (AST) of a program into a rich, attributed graph data structure in an in-memory graph database. This software graph can be queried in automated and interactive ways. Automation is supported through an embedded Java DSL, allowing automated analyzers to be written on top of Atlas using very few lines of code. Interaction and comprehension are supported in several ways. First, analysis results can be viewed using intuitive graph visualizations that have a one-to-one correspondence with the matching source or byte code. Second, Atlas provides a Shell View that allows the user to compute, query, and visualize results on-demand. Third, analyzers can be invoked automatically in response to user clicks through a configurable Smart View. For example, this view can be configured to instantly display a call graph, type hierarchy, or other artifact whenever the user clicks on a source token or graph element. This potent combination of automation and interaction has the effect of amplifying the intelligence of its users, enabling use cases that would be infeasible to automation or manual effort alone.
How can a man-machine analysis system detect novel, sophisticated, and domain-specific malware?
On its own, a software analysis platform that enables automation and interaction is not sufficient for malware detection –it is a foundation upon which a man-machine detection approach can be constructed. We recognized immediately that automated tooling can be used to point out interesting program behaviors, but a human analyst is required for making domain-specific judgment calls. The design of such a hybrid system necessitates answers to new questions such as (i) what behaviors are important to detect?, (ii) what behaviors can a static analysis feasibly detect?, (iii) how can we present behaviors to an analyst in a comprehensible way?, and (iv) how can we enable an analyst to effectively pose and answer follow-up questions?
Question (iv) is particularly crucial for addressing the shortcomings of traditional, existing two-pass defect detection tools. In a traditional two-pass tool, automation performs the first pass, and then a human must manually confirm or reject its alarms. This places an unreasonable burden on the user. Today's malware detection approaches either fall into the two-pass category, or else they are fully-automated and therefore not suitable for detecting novel, sophisticated, or domain-specific malware. We used Atlas and its APIs to move beyond prior work and create the Security Toolbox. Unlike conventional two-pass approaches, the Security Toolbox uses an interactive approach. We detect malware using repeated iterations of automation and interaction; automation mines the artifacts to expose program behaviors, and the analyst synthesizes the results and formulates new questions for the automation to answer.
How can expressive, compact information flow summaries be mined from a library for accurate and scalable partial program analysis?
Android applications, like most modern software, are built on top of reusable libraries. Android provides a massive library, including the entire standard Java library, which applications can call. In addition, the Android framework itself makes callbacks into an application in response to button clicks, interprocedural communication, component lifecycle changes, and many other events. Thus, analyzing an app by itself is a form of partial program analysis, defined as the analysis of a proper subset of a program's implementation. Due to the sheer size of the Android framework (orders of magnitude larger than an app), including it in order to perform whole program analysis was infeasible. Yet failing to capture its behaviors, particularly information flows, resulted in incomplete results and missed detections from the APAC performers.
The APAC Blue teams tried divergent approaches to solve this problem. As reported in their research paper, Stanford had a small army of graduate and undergraduate students to hand-write coarse information flow specifications for “important” Android APIs, then later worked to dynamically verify them. This labor-intensive process produced succinct, but coarse, results of varying quality and coverage. At the other extreme, some performers attempted to include the entire Android framework into their analysis. This approach tackled the problems of quality and coverage, but introduced dire problems of computational scalability. Our ISU team felt that the best of both worlds could be captured by an automated, summary-based approach.
Most prior work on the topic of library summarization focused on strategies for call graph construction, and thus was unhelpful. While at least one other APAC performer, Stanford, attempted to summarize library data flows, we found that their results were too coarse to be used accurately or capture flows involved in callbacks. To aggregate the benefits of their work while avoiding the drawbacks, we designed FlowMiner, an automated tool for extracting fine-grained, compact data flow summaries of Java library byte-code. FlowMiner employs the graph-based analysis paradigm and APIs of Atlas to perform a one-time static analysis of a Java library. It outputs sound data flow summaries as an abstract data flow graph, encoded using a portable XML format. Static analysis tools can use this portable summary file to achieve complete and accurate, yet scalable, partial program analysis.