Adaptive and scalable Android malware detection through online learning

Annamalai Narayanan, Yang Liu, Lihui Chen, Jinliang Liu

TL;DR

This paper introduces DroidOL, a novel framework for Android malware detection that tackles the challenge of constantly evolving malware (population drift) by employing online learning. By continuously updating its detection model with each new app, DroidOL achieves superior accuracy and scalability compared to traditional batch-learning methods, making it more suitable for real-world scenarios.

What Problem Does This Paper Address?

The landscape of Android malware is dynamic and ever-changing. Malware authors constantly develop new techniques to evade detection, leading to a phenomenon known as "population drift." This means the characteristics of malware observed today may differ significantly from those seen in the future. Traditional machine learning approaches for malware detection typically rely on "batch learning," where a model is trained on a fixed dataset and then used for prediction. This approach assumes a stationary malware distribution, which is not the case in reality. Consequently, batch-learned models quickly become outdated, leading to decreased detection accuracy. Furthermore, the sheer volume of new Android apps and malware makes retraining these batch models frequently computationally impractical, posing a significant challenge for effective and scalable malware detection.

Methods

DroidOL addresses these challenges through a combination of techniques:

  • Inter-procedural Control-Flow Graphs (ICFGs): To capture the security-sensitive behaviors of Android apps, DroidOL first transforms apps into ICFG representations. These graphs model the flow of execution and are labeled with security-sensitive APIs. ICFGs are chosen because they offer a good balance between capturing fine-grained program semantics and scalability, unlike more coarse-grained call graphs or computationally expensive data-flow graphs.
  • Weisfeiler-Lehman (WL) Graph Kernel: To extract meaningful features from these ICFGs, the paper utilizes the WL graph kernel. This kernel is known for its expressiveness and efficiency in representing graphs. It works by augmenting node labels with their neighborhood information up to a certain degree, effectively capturing sub-graph structures that represent security-sensitive behaviors. This process results in explicit feature vectors for each app.
  • Online Passive-Aggressive (PA) Classifier: The core of DroidOL's adaptiveness lies in its use of an online learning classifier, specifically a Passive-Aggressive (PA) classifier. Unlike batch learning, online learning updates the model incrementally with each new labeled sample. This allows DroidOL to continuously adapt to evolving malware characteristics and concept drift without the need for computationally expensive retraining on large batches of data. The PA classifier is chosen for its ability to aggressively update when errors are large and less aggressively when errors are small, and for its efficiency.

Datasets

The paper uses a large-scale, real-world dataset of 87,257 Android apps collected from seven different Android markets (Google Play, Anzhi, AppChina, SlideMe, HiApk, FDroid, and Angeeks) between January 1, 2014, and August 13, 2014. Ground truth labels for these apps were determined using the Virus Total web portal, which aggregates results from over 40 anti-virus scanners. The dataset comprised approximately 44,347 benign and 42,910 malware apps. The authors also refer to the Drebinsk dataset (5560 malicious Android apps from 179 malware families, collected between March 2009 and October 2012) for analyzing familial similarity and understanding the impact of long-term memory in detection.

Key Insights and Ideas

  • Online Learning is Crucial for Evolving Malware: The paper strongly advocates for online learning as a necessity for effectively detecting malware that constantly evolves. The ability to adapt to "population drift" and "concept drift" in real-time is a significant advantage over static batch models.
  • Variable Feature Sets are Key to Adaptiveness: DroidOL's performance is significantly enhanced by using a "variable feature-set" training regimen. This means the feature space grows as new features emerge over time, allowing the model to incorporate new malware characteristics. Fixed feature sets, on the other hand, lead to inferior performance.
  • Long-Term Memory Matters for Malware Families: Malware families can evolve over extended periods. The paper highlights that models with "long-term memory" (i.e., those that retain information from a vast history of samples) are better equipped to detect variants that emerge years apart, explaining why larger batch sizes or continuous updates are beneficial. Online learning inherently provides this long-term memory.
  • ICFGs and WL Kernel Provide Robust Features: The combination of ICFG representations and the WL graph kernel proves effective in extracting expressive and robust features that are less susceptible to evasion techniques.

Key Results

  • Superior Accuracy: DroidOL achieved 84.29% accuracy, outperforming two state-of-the-art batch-learning techniques (Drebin and CSBD) by more than 20% in their typical batch-learning settings and more than 3% even when they were continuously re-trained.
  • Efficiency: Online learning allows DroidOL to process a large number of apps more efficiently than batch methods, especially when considering the need for frequent retraining.
  • Adaptiveness: DroidOL demonstrated a significant benefit from using a variable feature-set training regimen, showing a 3.3% lesser cumulative error rate compared to fixed feature sets.
  • Feature Space Growth: The feature space grew substantially over the evaluation period, from approximately 13,655 features on Day 1 to over 1.6 million features by the end of the dataset, underscoring the dynamic nature of malware characteristics.

Limitations and Future Work

  • Limitations: While DroidOL demonstrates superior performance, the paper acknowledges that the "ground truth" labels for malware detection are often determined by multiple anti-virus scanners, which can sometimes disagree. The dataset used, while large, represents a specific time frame.
  • Future Work: The authors suggest that further research could explore other online learning algorithms and investigate more sophisticated feature extraction techniques. They also imply that the framework's adaptability makes it a strong candidate for real-time, continuous malware detection systems.

Summary updated

BibTeX
@inproceedings{narayanan2016adaptive,
  author = {Annamalai Narayanan and Yang Liu and Lihui Chen and Jinliang Liu},
  title = {{Adaptive and scalable Android malware detection through online learning}},
  booktitle = {IJCNN},
  year = {2016},
  doi = {10.1109/ijcnn.2016.7727508},
}

Loading related content...

Figure