Source-linked AI summary
MaMaDroid: Detecting Android Malware by Building Markov Chains of Behavioral Models (Extended Version)
Lucky Onwuzurike, Enrico Mariconti, Panagiotis Andriotis, Emiliano De Cristofaro, Gordon Ross, Gianluca Stringhini
TL;DR
Android malware and APIs evolve quickly, challenging detection systems that depend on fixed raw-call patterns and continual retraining. MaMaDroid instead abstracts API calls and models their call-graph sequences as Markov chains, achieving strong detection in current and future samples while outperforming the evaluated frequency-based baselines. Its evaluation is bounded by static-analysis failures and acknowledged evasion and comparison gaps.
Problem
Android malware and APIs evolve, making robust detection difficult without tool modifications or costly retraining.
Method
MaMaDroid uses static analysis to abstract API calls to families, packages, or classes and models call-graph-derived sequences as Markov chains.
Results
MaMaDroid detects same-period unknown malware with up to 0.99 F-measure and averages 0.87 after one year and 0.75 after two years, outperforming DroidAPIMiner and FAM.
Takeaways & Limitations
Statistical behavioral models combining API abstraction and sequence modeling are more robust than the traditional techniques evaluated.
Takeaways & Limitations
Soot fails to extract call graphs for 4.6% of original-dataset apps, and the authors identify possible evasion and unperformed comparisons with other static-analysis tools.
Abstract
from arXiv · showhide
As Android has become increasingly popular, so has malware targeting it, thus pushing the research community to propose different detection techniques. However, the constant evolution of the Android ecosystem, and of malware itself, makes it hard to design robust tools that can operate for long periods of time without the need for modifications or costly re-training. Aiming to address this issue, we set to detect malware from a behavioral point of view, modeled as the sequence of abstracted API calls. We introduce MaMaDroid, a static-analysis based system that abstracts the API calls performed by an app to their class, package, or family, and builds a model from their sequences obtained from the call graph of an app as Markov chains. This ensures that the model is more resilient to API changes and the features set is of manageable size. We evaluate MaMaDroid using a dataset of 8.5K benign and 35.5K malicious apps collected over a period of six years, showing that it effectively detects malware (with up to 0.99 F-measure) and keeps its detection capabilities for long periods of time (up to 0.87 F-measure two years after training). We also show that MaMaDroid remarkably outperforms DroidAPIMiner, a state-of-the-art detection system that relies on the frequency of (raw) API calls. Aiming to assess whether MaMaDroid's effectiveness mainly stems from the API abstraction or from the sequencing modeling, we also evaluate a variant of it that uses frequency (instead of sequences), of abstracted API calls. We find that it is not as accurate, failing to capture maliciousness when trained on malware samples that include API calls that are equally or more frequently used by benign apps.
1 INTRODUCTION
MaMaDroid addresses Android malware detection challenges caused by evolving malware and APIs by modeling abstracted API-call sequences as Markov chains. Its evaluation reports strong accuracy, persistence over time, and advantages over frequency-based baselines.
- Motivation: Android malware detection is difficult because smartphones cannot support constant scanning and malware and APIs continually evolve.Centralized analysis is typically used, while permission-based methods can produce false positives and raw API-frequency models require retraining.
- Approach: MaMaDroid abstracts API calls to families, packages, or classes and models their sequences as Markov chains to capture app behavior.The system extracts reachable call-graph paths and uses the resulting API-call sequences to build behavioral models.
- Approach: API abstraction improves resilience to Android API changes while retaining behavioral information and keeping the feature space manageable.Families and packages change less frequently than individual calls, and abstraction avoids highly sparse vectors created by more than 10 million unique API calls.
- Evaluation: The study evaluates MaMaDroid on almost 44K apps spanning October 2010 to May 2016 and compares sequence modeling with abstracted-call frequency analysis.The dataset contains 8.5K benign and 35.5K malware samples; the FAM variant isolates the contribution of sequence modeling.
- Evaluation: 0.99 F-measure is achieved for unknown malware from the same period, while average F-measure remains 0.87 after one year and 0.75 after two years.The reported long-term averages exceed DroidAPIMiner’s 0.46 and 0.42 and FAM’s 0.81 and 0.76 at the corresponding horizons.
- Contributions: The paper extends prior work with class-level abstraction and frequency modeling, and releases code and dataset hashes publicly.APK samples, parsed call graphs, and abstracted API sequences are available on request.
2 THE MAMADROID SYSTEM
MaMaDroid statically extracts API-call paths, abstracts calls to classes, packages, or families, and models transitions between abstracted calls as Markov chains for malware classification.
- Markov-chain Based Modeling: Transition probabilities from the Markov chain form the feature vector used by a machine-learning classifier to label apps benign or malicious.The feature-vector dimensionality depends on the abstraction mode.
- Sequence Extraction and Abstraction: MaMaDroid extracts an app’s call graph with static analysis and enumerates paths reachable from entry nodes as API-call sequences.These sequences represent potentially executable branches of the call graph.
- Sequence Extraction and Abstraction: Each API call is abstracted to its class, package, or family, reducing dependence on raw API names.Family mode uses root API package names; package and class modes use documented package and class names.
- Sequence Extraction and Abstraction: The abstraction is intended to improve resilience to Android API changes and scalability while preserving information about related operations.Families and packages change less frequently than individual API calls, and packages group classes performing similar operations.
- Markov-chain Based Modeling: For each app, MaMaDroid constructs a Markov chain whose states are abstracted calls and whose transitions encode probabilities of moving between states.An entry state S0 represents the starting point of each sequence.
- Markov-chain Based Modeling: Considering all branches and transition probabilities is argued to make detection more robust to inserted useless API calls than signature-based systems.The authors argue that adding calls would not significantly change transition probabilities between abstracted states.
3 DATASET
The evaluation uses diverse benign and malware datasets spanning 2010–2016, characterizes API-call evolution, and measures classification performance across classifiers.
- Datasets: 43,940 APK files comprise 8,447 benign and 35,493 malware samples collected from October 2010 to May 2016.
- Datasets: The benign data include 5,879 older PlayDrone apps and 2,568 unique newer Google Play apps.
- Datasets: The malware data include Drebin samples from 2010–2012 and VirusShare samples from 2013, 2014, 2015, and 2016.
- Dataset characterization: Newer benign and malicious apps use more unique API calls overall, indicating increasing app complexity over time.
- Dataset characterization: Malware appears to reach legitimate apps’ complexity and API-family usage characteristics with a delay of several years.
4 MAMADROID EVALUATION
MaMaDroid evaluates abstracted API-call behavior with standard classification metrics across same-year and cross-year settings, emphasizing robustness to Android and malware evolution.
- Evaluation setup: MaMaDroid extracts call graphs, abstracts API calls, constructs Markov-chain features, and classifies apps in family or package mode.
- Evaluation setup: F-measure combines precision and recall as F = 2 · (Precision · Recall)/(Precision + Recall).
- Same-year performance: Package mode achieves F-measures of 0.92–0.99 across datasets, compared with 0.88–0.98 in family mode.
- Detection over time: 0.86 F-measure is achieved when training on samples one year older than the classified samples.
- Comparison: MaMaDroid achieves significantly higher performance than DroidAPIMiner in all but one experiment, where the malicious training set is much older.
5 FINER-GRAINED ABSTRACTION
Class-level abstraction adds little same-year accuracy and can degrade temporal robustness when older training samples face newer test samples.
- Same-year performance: Class abstraction increases F-measure over package mode by only 0.0012 on average in same-year evaluation.
- Detection over time: Class mode reaches 0.95 and 0.99 F-measure when trained on datasets one and two years newer than the test sets.
- Detection over time: Class mode reaches 0.84 and 0.59 F-measure when trained on datasets one and two years older than the test set.
- Detection over time: Finer-grained abstraction performs worse over time than coarser abstraction when older samples train the model and newer samples are tested.
- Abstraction threshold: With training samples two years newer, class, package, and family modes achieve 0.99, 0.97, and 0.95 F-measure, respectively.
- Abstraction threshold: With training samples three years newer, the corresponding F-measures are 0.97, 0.97, and 0.96.
6 FREQUENCY ANALYSIS MODEL (FAM)
FAM isolates the effect of frequency modeling by retaining API abstraction while replacing sequence-based Markov chains with abstracted-call frequencies, but it is less robust than MaMaDroid.
- Model definition: FAM is a MaMaDroid variant that uses frequencies rather than sequences of abstracted API calls.
- Same-year performance: FAM reaches at least 0.50 F-measure in family mode and 0.87 when tested on the 2014 malware dataset.
- Same-year performance: Package-mode FAM ranges from 0.53 on 2016 and newbenign to 0.89 on 2014 and newbenign.
- Detection over time: FAM achieves 0.97 F-measure when trained on samples one year older than the testing samples in family mode.
- Detection over time: With newer training and older testing, FAM ranges from 0.69 to 0.92 in family mode and 0.65 to 0.94 in package mode.
- Comparison: MaMaDroid outperforms FAM and DroidAPIMiner in same-year tests, with frequency analysis sometimes unable to build a model from abstracted calls.
- Comparison: Across older-training experiments, MaMaDroid and FAM outperform DroidAPIMiner, while MaMaDroid leads FAM in all but one recent-training experiment.
- Comparison: The Markov-chain model achieves higher detection accuracy than frequency analysis in both family and package modes across same-year and multi-year evaluations.
7 RUNTIME PERFORMANCE
MaMaDroid’s runtime is dominated by call-graph extraction, while abstraction, Markov modeling, and classification add smaller costs. Despite being slower than DroidAPIMiner, its prototype is reported as scalable enough for offline deployment.
- MaMaDroid runtime: Call-graph extraction averages 9.2s for malware apps and 25.4s for benign apps, with substantial variation across applications.The reported maxima are 13 minutes for malware samples and 18 minutes for benign samples.
- MaMaDroid runtime: More than 80% of MaMaDroid’s runtime in every mode is spent extracting the call graph.Average end-to-end times for malware and benign apps are 10.7s and 27.3s in family mode, 13.37s and 33.83s in package mode, and 21.7s and 41.12s in class mode.
- FAM runtime: FAM’s frequency-analysis and feature-extraction phase is fast, while total processing averages 2.02s, 2.39s, and 6.56s for malware in family, package, and class modes.Classification itself takes less than 0.01s per app across modes and classifiers.
- DroidAPIMiner comparison: DroidAPIMiner completes an app faster than MaMaDroid but achieves significantly lower accuracy.It takes 5.8s and 9.9s less on average for malicious and benign apps in MaMaDroid’s family mode, and 8.47s and 16.43s less in package mode.
- Deployment feasibility: Using 64 cores, the authors estimate that processing approximately 10,000 daily Google Play submissions in all modes would take less than two hours.The estimate uses benign-app averages of 27.3s, 33.83s, and 41.12s in family, package, and class modes.
8 DISCUSSION
MaMaDroid’s abstraction and Markov-chain behavioral modeling preserve malware-detection performance as Android APIs and malware evolve, while exposing operational and evaluation boundaries.
- 8.1 Lessons Learned: 0.86 F-measure after one year and 0.75 after two years show that MaMaDroid remains more effective over time than DroidAPIMiner and FAM.The cited comparison reports DroidAPIMiner at 0.46 and 0.42, and FAM at 0.81 and 0.76, after one and two years respectively.
- 8.1 Lessons Learned: Markov chains capture call ordering that frequency models miss, including operation sequences distinguishing malicious from benign use of the same API class.The paper’s example contrasts recording after getRunningTasks() with benign apps’ less constrained ordering.
- 8.1 Lessons Learned: Abstraction makes MaMaDroid less susceptible to newly introduced API calls because families and packages change less often than individual calls.New classes and methods can map to known families or packages; newly added packages require only corresponding Markov-chain states.
- 8.1 Lessons Learned: Finer-grained class abstraction becomes less effective as older training samples are used to classify newer apps, although it helps for same-year or newer test settings.Package and family abstraction therefore provide stronger temporal robustness in the reported evaluations.
- 8.2 Potential Machine Learning Bias: The evaluation does not eliminate spatial bias; testing malware prevalence ranges from 49.7% to 84.85%, which may affect Precision and Recall.The authors note that the real-world percentage of malicious Android apps is difficult to estimate.
- 8.3 Evasion: Static analysis cannot model code loaded or determined at runtime, including dynamic code and native code, though reflection and class-loader usage remain partially observable.The paper identifies these as limitations common to static analysis and suggests combining MaMaDroid with dynamic analysis.
- 8.4 Limitations: MaMaDroid may require more than 100,000 features per sample in package or class mode, but PCA with 10 components delivers nearly comparable performance with lower memory complexity.The limitation concerns classifier operation in high-dimensional feature spaces.
- 8.4 Limitations: Soot fails to extract call graphs for 4.6% of the original apps, limiting analysis coverage despite reportedly not affecting the evaluation results.The authors suggest alternative intermediate representations or call-graph extraction tools as possible remedies.
9 RELATED WORK
Related Android malware-detection work spans static, dynamic, signature-based, sequence-based, and machine-learning approaches. MaMaDroid differs by modeling all statically extracted API-call sequences with abstraction to detect previously unseen malware over time.
- Static analysis and app features: Static approaches use permissions, manifests, API calls, program logic, call graphs, and security-sensitive behaviors to distinguish or prioritize Android apps.Examples include Kirin, RiskRanker, Droidmat, DroidMiner, Drebin, TriFlow, and AppContext.
- Dynamic analysis: Dynamic systems monitor execution or taint propagation, but deployment on users’ devices is constrained by overhead and predefined inputs may fail to trigger malicious behavior.Dynamic analysis can also be sidestepped by knowledgeable adversaries.
- Signatures and sequences: Signature-based methods learn suspicious subgraphs, network profiles, or other fingerprints, while sequence signatures can be evaded through polymorphism, obfuscation, or call reordering.These approaches commonly depend on matching previously observed patterns.
- Machine learning: Machine-learning systems address training sabotage, model aging, and feature-based detection, but some reported accuracy depends critically on representative benign and malicious training samples.The related work includes Kuafudet, Transcend, and StormDroid.
- Signatures and sequences: Android sequence-based work has modeled short system-call sequences for specific malware families, whereas MaMaDroid targets previously unseen malware and later samples.MaMaDroid also uses statically extracted sequences of all API calls rather than execution traces of only three system calls.
- MaMaDroid’s position: MaMaDroid’s distinguishing design is holistic static modeling of all API-call sequences, abstracted to families, packages, or classes and represented as Markov chains.This contrasts with systems focused on permissions, selected APIs, information flows, or runtime behavior.
10 CONCLUSION
The paper concludes that MaMaDroid models abstracted API-call sequences as Markov chains to detect Android malware across granularities. Its evaluation reports strong contemporaneous detection and sustained performance over subsequent years, while motivating further evasion research.
- 10 CONCLUSION: MaMaDroid abstracts API calls to families, packages, or classes and models their sequences as Markov chains for Android malware detection.The system is evaluated for classification accuracy and runtime performance.
- 10 CONCLUSION: 0.99 F-measure detects unknown malware developed around the same time as training samples, while performance remains 0.86 after one year and 0.75 after two years.The conclusion reports these results from an extensive evaluation on a large malware dataset.
- 10 CONCLUSION: MaMaDroid outperforms DroidAPIMiner on same-year data and is more resilient over time to changes in Android APIs and malware.The paper attributes its broader robustness to abstraction and Markov-chain modeling of API-call sequences.
- 10 CONCLUSION: The authors identify abstraction and Markov-chain behavioral modeling as more robust than traditional techniques and plan further study of evasion involving repackaging and injected API calls.Future work focuses on resilience to possible evasion techniques.