Dependencies
Non-Local Data and Control
Malware’s data and control dependencies cut across several functions and data structures, so the malicious behavior never sits in one place an analyzer can point to.
ENSOFT Research · DARPA APAC · 2012–2015
Automated Program Analysis for Cybersecurity
DARPA’s APAC program set out to keep malicious apps out of DoD Android marketplaces, tested against novel malware that a Red team wrote into challenge apps. Provable automation is not possible in all cases, so from 2012 to 2015 the team put a human analyst in the loop, with the Atlas graph database and its XCSG schema, an Android Security Toolbox built on them, and FlowMiner for summarizing libraries. The team was the top-performing Blue team in Phase I and among the top three in Phase II.
Hard Problems for Static Analysis
Control
Invisible Control Switches
Multithreading and event processing switch control without a function call or a control statement that static analysis can see. The Android framework calls back into an app on button clicks, lifecycle changes, and many other events.
Intent
Ambiguous Intent
An app’s intent is ambiguous, which makes malicious behavior hard to separate from legitimate functionality. Deciding takes domain-specific judgment that automated tooling cannot make on its own.
DARPA I2O · AFRLBAA 11-63
The Program’s Goals
APAC asked for a practical program analysis tool to keep malicious Java apps out of DoD Android marketplaces: false alarms and missed detections under 30% in Phase I and under 5% in Phase II, under 160 hours of manual labor per app in Phase I and 80 in Phase II, and a tool that an analyst with basic knowledge of software development and malicious techniques could operate.
Under 5%False alarms and missed detections the program asked for in Phase II.
Comprehension-Driven Program Analysis
Human in the loopSection 3
One Loop for the Analyst and the Tool
A two-pass tool runs automation first and leaves a human to confirm or reject every alarm, an unreasonable burden. The team coupled the analyst and the tool in one loop of iterative refinement instead. The Query-Model-Refine framework, developed by ENSOFT, provides the mechanics: a composable query language, used interactively or embedded in Java, and model and refine capabilities that create effective abstractions of large software.
Figure 1 · 2-pass vs. integrated analysisRead →
Query · Model · RefineFrees the analyst from the lower-level details of static analysis to focus on malware detection strategies.
Atlas · XCSGSection 3.1.1
Graph Schema and Program Analysis Platform
XCSG, the eXtensible Common Software Graph, expresses the structure and behavior of Java, Java bytecode, C, and C++ programs as one attributed graph. Atlas indexes a program into that graph once, then answers queries from analyzers, from its shell, and from Smart Views that respond to the analyst’s clicks.
Sections 3–3.1.1Read →
Built on AtlasSection 3.1.2
Android Security Toolbox
The toolbox maps Android permissions onto the program graph, indexes the XML resources that Java analysis misses, and runs analyzers for properties, smells, confidentiality, integrity, and availability. Its Dashboard runs them in parallel and queues the results for the analyst.
Figures 2–3Read →
Library summariesSection 3.1.3
FlowMiner
An Android app runs on a massive library, so analyzing the app alone is partial program analysis. FlowMiner mines information flow summaries from Java library binaries that keep the flows that matter, with 26.89% of the nodes and 16.32% of the edges of the original library graphs on average.
Open sourceRead →
Inside the Security Toolbox
Figure 2Section 3.1.2.4
Dashboard
The automated analyzers’ results as work items the analyst filters by type, contents, and state, with the notes and colors recorded during the audit.
Figure 3Section 3.1.2.4
Dashboard Wizard
Individual analyzers and indexers on or off, and analysis strategies that trade accuracy for time.
Results
105 audits · eight engagementsSection 4
Detection, Time, and Application Size
The team audited 105 challenge apps across eight engagements, 87 of them malicious. Missed detections were 6.49% in Phase I, under the 30% goal, and 25% in Phase II as the Red team’s malware changed. Analysis averaged about an hour per app in Phase I and about nine hours in Phase II, under the 160- and 80-hour limits. Neither detection nor analysis time tracked the size of the app: the difficulty came from the malware itself.
Figure 6 · Application size vs. analysis timeRead →
AFRL-RI-RS-TR-2015-186 · ADA621995
The Final Report
- 1Executive Summary
The three research questions behind comprehension-driven program analysis, and the answer to each.
- 2Introduction
The team, the program in DARPA’s words, and its goals with the team’s progress toward each.
- 3–3.1.1Methods, Assumptions, and Procedures
The human-in-the-loop approach, Query-Model-Refine, the XCSG graph schema, and the Atlas platform.
- 3.1.2Android Security Toolbox
Permission mapping, analyzers, indexers, and the Dashboard.
- 3.1.3FlowMiner
Library summaries that balance expressiveness and compactness, their validation, and the open-source tool.
- 4Results and Discussions
The analysts and their process, the challenge applications, detection rates, and analysis times, and what the engagements showed.
- 5–6Tool Releases and Concluding Remarks
What was released to the Government and as open source, and the closing assessment.
- 7–9Publications and References
Four publications, seven references, and the acronyms.
Abstract: The DARPA APAC program gave us an opportunity to make three important technological advances: (a) A graph database program analysis platform and a graph schema for representing program semantics that together facilitate both automation and human comprehension. (b) Malware analysis techniques and its incorporation in a security toolbox to provide a man-machine analysis system to detect novel, sophisticated Android malware. (c) An innovative library summarization technique and its incorporation in the FlowMiner tool that mines expressive, compact information flow summaries from a library for accurate and scalable partial program analysis. The challenge apps were very useful in evolving our technologies and understanding its limitations. Details of technological advances, our experiences and observations are outlined in this report.
Selected Papers
IEEE/ACM ICSE · 2015Android Security Toolbox
Security Toolbox for Detecting Novel and Sophisticated Android Malware
Demonstrates the DARPA APAC Android Security Toolbox built on Atlas, enabling human-in-the-loop malware auditing across Android source and Java bytecode against Red-team adversarial applications.
Benjamin Holland, Tom Deering, Suresh Kothari, Jon Mathews, Nikhil Ranade10.1109/ICSE.2015.235
2015Comprehension-Driven Auditing
Comprehension-Driven Program Analysis for Malware Detection in Android Apps
Formulates the comprehension-driven, human-in-the-loop malware detection methodology developed under the DARPA APAC program to vet DoD and commercial mobile marketplaces against adversarial Red-team Android malware.
Suresh Kothari, Tom Deering, Ben Holland, Ahmed Tamrawi, Akshay Deepak, Sandeep Krishnan, Damanjit Singh, Vani Bojja, Ganesh Santhanam, Jeremías Sauceda, Jon Mathews, Nikhil RanadeRead the paper →
IEEE SMC · 2014Amplified Reasoning
A “Human-in-the-Loop” Approach for Resolving Complex Software Anomalies
Presents an interactive human-in-the-loop reasoning approach for diagnosing and resolving complex cross-cutting software anomalies where fully automated static analysis produces excessive false positives or fails to scale.
Suresh Kothari, Akshay Deepak, Ahmed Tamrawi, Benjamin Holland, Sandeep Krishnan10.1109/SMC.2014.6974210
ICSE · 2014Atlas Platform
Atlas: A New Way to Explore Software, Build Analysis Tools
Presents the Atlas software analysis platform, which decouples program indexing from domain-specific analysis: polynomial-time static analyzers build an attributed graph database of the program, which engineers then query interactively or through analysis scripts. Validated on Linux kernel synchronization verification and Android malware detection.
Tom Deering, Suresh Kothari, Jeremías Sauceda, Jon Mathews10.1145/2591062.2591065
ACM/IEEE MODELS (EduSymp) · 2013Simulink & Atlas Modeling
Multi-faceted Practical Modeling Education for Software Engineering
Introduces a problem-driven modeling curriculum combining domain-specific graphical modeling in Simulink and SimDiff with program-graph query modeling in Atlas—applying two-event graph models to operating-system memory leaks, Linux kernel lock pairing, and DARPA APAC Android malware detection.
Suresh Kothari, Jeremías SaucedaRead the paper →