3. Methods, Assumptions, and Procedures
Our research focused on the challenges not addressed, novel and sophisticated malware that unlike the malware reported in the wild, pose significant program analysis challenges. Unlike the other security attacks that are immediately noticeable through their denial of service, malware apps can silently leak sensitive information without revealing themselves.
Detecting sophisticated and novel mobile malware can be extremely challenging in the presence of the following program analysis challenges:
- Non-local data and control dependencies in the malware that cut across several functions and data structures.
- Invisible control switches due to multithreading or event processing - these control switches are not directly visible in static analysis as function calls or as control statements.
- Inherent ambiguities of an application’s intent make it difficult to separate malicious behavior from legitimate functionality.
Users of existing defect analysis (not just malware detection) tools employ two passes: (1st pass) the tool works automatically to produce a list of potential problems in the code, (2nd pass) tedious manual inspection to validate the problems. This approach runs into the following difficulties. Without any on-the-fly human intelligence to guide its trajectory, the tool makes wrong or highly conservative decisions resulting in many false negatives and/or positives. Moreover, the results produced by defect analysis tools lack evidence for humans to reason with to confirm or reject the tool findings. The existing 2-pass approach is shown in Figure 1.
A tool by itself cannot deal with the program analysis challenges listed above, so we incorporate human guidance to tweak the trajectory of the tool to improve its precision in detecting malware. A human cannot guide the tool effectively without comprehending the application software. Nor can he comprehend the large and complex application software without an inordinate amount of effort, so we incorporate tool assistance by searching and extracting relevant software artifacts as evidence for the analyst to reason about the application’s intent and validate the malware detection results from the tool. In short, we proposed and researched a novel integrated comprehension-driven analysis-based approach.
As shown in Figure 1, we have a tightly coupled human-in-loop approach with iterative refinement as opposed to the existing 2-pass approach. Our approach succeeded reasonably well because it provided a viable alternative to address sophistications of attacks that make program analysis difficult.
We leveraged the Query-Model-Refine (QMR) framework developed by ENSOFT; it provides the tool mechanics necessary for our tightly coupled human-in-loop approach. Like the database language SQL, the framework incorporates a composable query language that can be used either interactively or embedded as 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. We developed Atlas, a QMR platform for Java.
Another important aspect of our approach was to develop a tool that is evolution-friendly and highly usable, i.e., it is fairly easy to refine and extend its malware detection capabilities without requiring expertise in building static analysis tools. This is the case because our approach amounts to having the malware detection capabilities incorporated as a toolbox built on top of Atlas. The low-level details of static analysis reside inside Atlas, and the malware detection capability resides inside the toolbox as compact analysis programs using Atlas queries. Refining and extending the existing detection capabilities as well as creating entirely new capabilities is relatively easy because it can be done through query-enabled analysis programs. The underlying design philosophy is similar to environments like Matlab where the heavy lifting is done behind the scenes, making it much easier for the user to develop domain-specific programs. Since creating a complete list of properties is unrealistic, it is imperative that it be relatively simple to expand the cookbook of ready-made properties through the use of adversarial thinking. An evolution-friendly technology provides a cost effective path for DoD to maintain state-of-the-art in malware detection for years to come.
3.1 Technological Advances
The DARPA APAC program gave us an opportunity to make three important technological advances that we will describe here.
3.1.1 Graph Schema and Program Analysis Platform
How should a software analysis platform be built to facilitate both automation and human comprehension?
We have made significant advances to answer this key question. We came up with a graph schema, called the eXtensible Common Software Graph (XCSG) to provide an attributed directed graph as a common medium to express rich structural and behavioral semantics of programs in Java, Java byte code, C and C++. We advanced Atlas as the graph database platform to write program analyzers based on the XCSG schema. We have advanced the Atlas platform that enables one to write software analysis verification and transformation programs in minutes or hours that otherwise would take days or months.
Atlas parses C, C++, Java, and Java bytecode to capture complex program semantics in a graph database. It provides APIs to mine, traverse, and transform the graph database. Atlas APIs and program graph visualization capabilities enable quick prototyping of tools to experiment with and advance fundamental techniques to reason about complex problems of large software. Atlas is free for academic use. The XCSG schema is available online.
Atlas decouples 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 Atlas ideal for both interaction and automation. In our ICSE 2014 paper, we describe the motivation, design, and use of Atlas. We present validation case studies, including the verification of safe synchronization of the Linux kernel, and the detection of malware in Android applications.
Demo Video: http://youtu.be/cZOWlJ-IO0k
3.1.1.1 Graphs and Queries
Graphs are a natural way to represent programs and program analysis results, where nodes typically correspond to entities such as methods and variables, and edges correspond to relationships such as control or data flow. The Atlas database extracts and stores rich program semantics as a unified graph representation that includes structural relationships (types, methods, fields, etc.) and control and data flows derived by conservative analyses as the base knowledge for writing refined path, object, context, and field sensitive analyses.
Encoding the program semantics in a unified graph has the advantage of lending itself to composable analyses. The result of a program analysis is usually another graph, which can then be used as the input to the next analysis. In Atlas, graphs can also be displayed, but the visualization is not necessarily the end; the nodes and edges can be selected, and used as inputs for the next iteration of analysis.
Many program analysis questions can be encoded as reachability queries, and so Atlas provides a query language to make these common queries easy to write. Writing queries also involves knowing the graph’s schema, or how the program and analysis information is encoded. The Atlas schema, called the eXtensible Common Software Graph (XCSG), will be discussed later.
3.1.1.2 Human Interaction
An unprecedented human interaction capability, far beyond any other existing program analysis tool, to reason about complex problems of software is enabled by: (a) a capability to visualize and interact with large program graphs in a way that fosters human comprehension of complex program semantics, (b) a correspondence with the code for program artifacts and the corresponding graphs depicting relationships between those artifacts - a correspondence that enables scalable navigation through large code, (c) a query interpreter shell that enables composition of powerful queries to mine complex cross-cutting program semantics and its visualization.
From our experiences during the first few engagements analyzing Android apps, we found that many queries were variations on data flow queries. To help accelerate the iterative analysis process, “Atlas Smart Views” were introduced to help reduce common queries to a point-and-click operation, wherein the analyst selects an analyzer from a drop-down menu and that analyzer is applied automatically and the corresponding result is shown whenever the analyst clicks on an appropriate source code entity. For example, the analyst selects the “call graph” analyzer, clicks on a method invocation in the source code being viewed, instantly the corresponding call graph is shown. As another example, the analyst selects the “data flow graph” analyzer, clicks on a parameter in for the method invocation in the source code being viewed, instantly the corresponding data flow graph is shown. New analyzers can be added to the “Atlas Smart Views.” We added Android-specific analyzers.
3.1.1.3 Extensibility
Atlas serves as a platform to build domain-specific toolboxes such as the Security Toolbox we built for the APAC project. The Security Toolbox incorporates Android semantics by extending the graph database. For example, the graph database is extended to include the Graphical User Interface (GUI) semantics derived from the Android XML files. The extension must be designed to follow the eXtensible Common Software Graph (XCSG) schema.
The XCSG schema defines a semantically rich graph representation of software (i.e. source code or binaries) to support program applications such as mining software for patterns, malware and defect detection, building static analysis tools, and code comprehension. XCSG is based on the eXtensible Common Intermediate Language (XCIL) developed by Kothari and his team for the DARPA Software Enabled Control (SEC) program [3].
Like XCIL, XCSG has semantically precise definitions for program artifacts to enable a harmonious representation of software written in different languages. Without precise semantics, analysis tools can easily develop a language bias that leads to incorrect processing of other languages, especially while analyzing software written in multiple languages. For example, the keyword “static” in C and Java have overlapping but incompatible uses, which XCSG disambiguates. XCSG improves upon XCIL by tailoring it for a graph database, and by encompassing representations of analysis results such as control flow and data flow graphs.