PaperlayerView exact revision on arXiv

Source-linked AI summary

MaMaDroid: Detecting Android Malware by Building Markov Chains of Behavioral Models

Enrico Mariconti, Lucky Onwuzurike, Panagiotis Andriotis, Emiliano De Cristofaro, Gordon Ross, Gianluca Stringhini

arXiv:1612.04433v3cs.CR

TL;DR

Android malware detection must remain effective as malware and Android APIs evolve without continual retraining. MaMaDroid abstracts API calls to packages or families, models their behavioral transitions with Markov chains, and classifies apps from the resulting features. It achieves up to 99% F-measure and retains detection performance over subsequent years, outperforming DroidAPIMiner in the reported comparison.

  • Problem

    Android malware and APIs evolve, challenging detection systems that rely on specific API calls and require frequent retraining.

  • Method

    MaMaDroid abstracts API calls to packages or families, models app-call transitions as Markov chains, and uses the resulting features for classification.

  • Results

    MaMaDroid achieves up to 99% F-measure and averages 87% after one year and 73% after two years, compared with 46% and 42% for DroidAPIMiner.

  • Takeaways & Limitations

    The results show that MaMaDroid remains effective across changing malware and Android APIs without frequent classifier retraining.

  • Takeaways & Limitations

    Package-mode classification requires substantial memory, with more than 100,000 features per sample; PCA can reduce this complexity while preserving near-comparable performance.

Abstract

from arXiv · show

The rise in popularity of the Android platform has resulted in an explosion of malware threats targeting it. As both Android malware and the operating system itself constantly evolve, it is very challenging to design robust malware mitigation techniques that can operate for long periods of time without the need for modifications or costly re-training. In this paper, we present MaMaDroid, an Android malware detection system that relies on app behavior. MaMaDroid builds a behavioral model, in the form of a Markov chain, from the sequence of abstracted API calls performed by an app, and uses it to extract features and perform classification. By abstracting calls to their packages or families, MaMaDroid maintains resilience to API changes and keeps the feature set size manageable. We evaluate its accuracy on a dataset of 8.5K benign and 35.5K malicious apps collected over a period of six years, showing that it not only effectively detects malware (with up to 99% F-measure), but also that the model built by the system keeps its detection capabilities for long periods of time (on average, 86% and 75% F-measure, respectively, one and two years after training). Finally, we compare against DroidAPIMiner, a state-of-the-art system that relies on the frequency of API calls performed by apps, showing that MaMaDroid significantly outperforms it.

I. INTRODUCTION

Android’s popularity has intensified malware threats, while changing malware and APIs challenge detection methods that require frequent retraining. MaMaDroid addresses this by modeling sequences of abstracted API calls and reports strong, durable detection performance.

  • Motivation: Android’s widespread adoption and openness have increased malware exposure, while mobile constraints make continuous, computation-heavy scanning infeasible.Centralized checking can miss malicious apps, and third-party markets may perform weaker or no malware checks.
  • Motivation: Specific API-call frequency features can become ineffective as Android APIs evolve and malware developers switch to newer calls.This creates pressure for systems such as DroidAPIMiner to retrain continually.
  • Approach: MaMaDroid models app behavior from sequences of API calls abstracted to packages or families rather than relying on raw call use or frequency.The abstraction preserves operation-level information while reducing sensitivity to individual API changes.
  • Evaluation: MaMaDroid is evaluated on almost 44K apps spanning October 2010 to May 2016, including 8.5K benign and 35.5K malware samples.The evaluation covers classification accuracy and runtime performance under changes in malware samples and APIs.
  • Results: 99% F-measure is achieved for unknown samples from the training period, while performance remains 87% after one year and 73% after two years.These figures use F-measure and describe training on older samples followed by testing on newer ones.
  • Workflow: The system’s four-stage workflow extracts call graphs, derives abstracted call sequences, builds Markov-chain features, and classifies apps as benign or malicious.Figure 1 summarizes these stages.

II. THE MAMADROID SYSTEM

MaMaDroid statically extracts app call graphs, derives abstracted API-call paths, and models transitions between package or family states with Markov chains. These transition probabilities become classifier features, while abstraction trades package-level detail for family-level lightness and keeps computation manageable.

  • Sequence Extraction: Calls are abstracted to packages or families; family abstraction is more lightweight, whereas package abstraction is more fine-grained.The two modes provide different abstraction granularities for operation.
  • Call Graph Extraction: MaMaDroid uses static analysis to extract each app’s call graph before deriving sequences of potentially callable API functions.Soot extracts call graphs, while FlowDroid preserves contexts and flows.
  • Call Graph Extraction: A running example shows malware disguised as a memory-booster app executing commands such as rm and chmod as root.The example focuses on calls in a try/catch block and omits initialization calls, return types, and parameters for presentation.
  • Sequence Extraction: MAMADROID identifies entry nodes and enumerates reachable paths, producing API-call sequences used to build behavioral models and extract features.Different executions may follow different branches of the statically extracted graph.
  • Sequence Extraction: Abstraction avoids an impractical feature space: more than 10 million unique raw API calls would make the square-sized feature representation computationally costly.The package and family representations also support resilience to Android API changes and scalability.

D. Markov-chain Based Modeling

MaMaDroid models app behavior by converting abstracted API-call sequences into Markov chains. Transition probabilities become features, with package and family abstraction offering different granularity and robustness to inserted calls.

  • Markov-chain basis: Markov chains provide memoryless transition models in which the next-state probability depends only on the current state.Transition probabilities are computed from observed state-transition occurrences.
  • Model construction: Each app’s Markov chain starts at an entry state and represents transitions among package or family states.The two abstraction modes produce separate chains from the same API-call sequence.
  • Robustness: Considering all branches and single transitions makes the model less sensitive to useless API calls inserted to evade signature-based detection.Added calls do not significantly change transition probabilities between abstracted states.
  • Model construction: MaMaDroid builds feature vectors from transition probabilities in Markov chains representing each app’s abstracted API-call sequence.Each package or family is a state, and transitions encode the probability of moving between states.
  • Feature processing: PCA transforms the feature space into components ordered to retain as much variance as possible for feature selection.The components are linear combinations of the original transition features.

E. Classification

The evaluation uses large, time-spanning benign and malware datasets to study classification and dataset evolution. PCA visualizations and API-call distributions characterize how app behavior changes across datasets.

  • Datasets: The evaluation includes 43,940 apps spanning October 2010 to May 2016 to test robustness to changing malware samples and Android APIs.The dataset contains 8,447 benign and 35,493 malware samples.
  • Datasets: The benign data comprise oldbenign from 2013 and newbenign collected from Google Play in 2016.The final newbenign set contains 2,568 unique apps after download errors and category overlap.
  • Datasets: The malware data combine DREBIN samples from 2010–2012 with VirusShare samples from 2013, 2014, 2015, and 2016.The yearly VirusShare sets contain 6,228, 15,417, 5,314, and 2,974 samples, respectively.
  • Dataset characterization: Newer benign and malicious apps use more unique API calls overall, indicating increasing app complexity over time.The characterization uses cumulative distributions of API-call counts across datasets.
  • Dataset characterization: Benign and malicious apps follow similar evolutionary trends, while malware reaches legitimate-app characteristics after a delay of several years.The comparison covers complexity and the fraction of calls from selected families.
  • PCA analysis: PCA plots show benign samples in dataset-dependent regions, whereas malware occupies similar regions with different densities.The plots compare the first two PCA components for benign and malicious samples.

IV. EVALUATION

The evaluation measures contemporaneous accuracy, robustness across time, runtime performance, and comparison with DroidAPIMiner. It uses multiple classifiers, F-measure-based assessment, and repeated cross-validation on the assembled datasets.

  • Evaluation design: The evaluation covers contemporaneous classification, temporal robustness, runtime scalability, and comparison with DroidAPIMiner.These four experiment sets use the datasets summarized in Table I.
  • Classification setup: MAMADROID is evaluated with Random Forests, 1-NN, 3-NN, and SVM, although SVM results are omitted because its accuracy and speed are worse.Reported F-measure, precision, and recall results generally use Random Forests.
  • Metrics: F-measure combines precision and recall, with precision and recall defined from true-positive, false-positive, and false-negative counts.The evaluation identifies correctly classified malware and the two types of misclassification through these quantities.
  • Validation: 10-fold cross-validation merges selected benign and malicious datasets, shuffles them, and averages results across ten train-test splits.Each split trains on nine subsets and tests on the remaining subset.

B. Detection Performance

MAMADROID detects malware effectively in same-period evaluations, with package-level abstraction generally outperforming family-level abstraction. PCA reduces the feature space with only a small F-measure loss.

  • Evaluation setup: Table II reports F-measure, precision, and recall for Random Forests across dataset combinations, abstraction modes, and PCA settings.The evaluation uses 10-fold cross-validation on combined benign and malicious datasets.
  • Family mode: At least 88% F-measure is achieved in family mode with Random Forests, reaching 98% on the 2014 malware dataset.Recall remains above 91%, while lower precision contributes to reduced F-measures on some datasets.
  • Package mode: 92%–99% F-measure is achieved in package mode with Random Forests across the reported datasets.The highest value is 99% with 2014 and newbenign.
  • Package mode: 96% F-measure in package mode exceeds 88% in family mode for drebin with oldbenign.The difference is attributed to fewer false positives in package mode while recall remains high.
  • Using PCA: PCA-based features reduce F-measure by up to 3% compared with the full feature set.The reduction reflects uniform decreases in both precision and recall.

C. Detection Over Time

MAMADROID retains substantial detection performance when trained on older samples and tested on newer ones, while performance remains similar when newer training data is used for older samples. Accuracy declines as the temporal gap grows, particularly when benign behavior anticipates malware behavior.

  • Motivation and design: MAMADROID is designed to be less susceptible to Android API changes because it abstracts call sequences to packages or families rather than relying on individual-call frequency.The paper contrasts this design with systems requiring retraining after new API releases.
  • Older training, newer testing: 86% F-measure is obtained one year after training and 75% after two years in family mode on newer samples.Package mode shows no significant change in F-measure under the same older-training, newer-testing setting.
  • Older training, newer testing: MAMADROID’s accuracy drops when test samples are more than two years newer than training samples.The decline is associated with benign datasets appearing to anticipate malicious API-call usage by 1–2 years.
  • Newer training, older testing: Training on newer datasets preserves similar F-measure scores when testing samples up to four years older.Family mode ranges from 93% to 96%, while package mode ranges from 95% to 97%.

D. Case Studies of False Positives and Negatives

MAMADROID’s errors commonly arise when benign apps resemble malware, malware lacks clearly malicious behavior, or dataset labels are incorrect. The case studies connect false positives to dangerous permissions and false negatives to adware and potentially benign samples.

  • False Positives: 164 benign apps were falsely flagged, and most used dangerous permissions such as external-storage, phone-state, or fine-location access.67% wrote to external storage, 32% read phone state, and 21% accessed fine location.
  • False Positives: An emergency app was flagged because sending SMS messages to stored contacts resembled typical malware behavior in the dataset.The example illustrates how legitimate services can share behavioral patterns with malicious samples.
  • False Negatives: 18% of family-mode false negatives were not classified as malware by any VirusTotal antivirus engine.This suggests some missed samples may have been legitimate apps incorrectly included in VirusShare.
  • False Negatives: Adware accounted for 45% of family-mode false negatives and 53% of package-mode false negatives.These were typically repackaged apps whose advertising libraries had been replaced by third-party libraries.
  • Overall interpretation: The authors attribute sporadic misclassifications to malware-like benign behavior, non-obviously malicious malware, and ground-truth labeling errors.The conclusion summarizes the principal explanations identified in the case studies.

F. Runtime Performance

MAMADROID’s prototype has measurable per-app processing costs dominated by call-graph extraction, but the authors estimate that it can scale to daily Google Play submissions with sufficient parallelism.

  • Sequence extraction: 1.3s is the average family-level call-sequence extraction time, compared with 1.67s for malicious and 1.73s for benign apps in package mode.Package abstraction takes slightly longer because it uses 341 packages.
  • Modeling and features: Markov modeling and feature extraction take 0.2s for malicious family-mode samples and 2.5s for malicious package-mode samples on average.Benign-sample averages are 0.6s and 6.7s in family and package modes, respectively.
  • End-to-end performance: 10.7s and 27.3s are the average end-to-end times for malware and benign samples in family mode.Package mode averages 13.37s for malware and 33.83s for benign samples.
  • Call-graph extraction: More than 80% of processing time in both modes is spent extracting call graphs.Call-graph extraction averages 9.2s for malware and 25.4s for benign apps, excluding apps where extraction failed.
  • Deployment estimate: Less than 1.5 hours would be required to process roughly 10,000 daily submissions in both modes using 64 cores.The estimate uses average benign execution times of 27.3s in family mode and 33.83s in package mode.

V. DISCUSSION

MaMaDroid’s Markov-chain behavioral modeling captures app behavior and preserves detection accuracy as Android APIs and malware evolve. Abstraction to packages or families supports this resilience, with packages offering the best overall tradeoff.

  • Markov chains successfully capture app behavior from API-call sequences, enabling high accuracy and retention over time.The approach models transitions between abstracted API calls rather than isolated calls.
  • Benign apps use more API calls than contemporaneous malicious apps, while malicious apps adopt Android and Google APIs with a delay of several years.The delayed adoption may result from malware authors repackaging benign apps and adding malicious functionality.
  • 86% F-measure after one year and 75% after two years show that MAMADROID remains effective longer than API-dependent systems.DROIDAPIMINER achieves 46% and 42% at the corresponding intervals, while MAMADROID reaches 51% after four years.
  • Abstracting calls to families or packages improves robustness because newer classes and methods can map to already-known abstractions.The abstraction reduces sensitivity to newly introduced API calls.
  • Package abstraction provides better overall results, while family abstraction is lighter, faster, and performs better when train-test gaps exceed two years.Excessive granularity can create low-probability transitions and reduce classification accuracy; PCA reduces complexity while preserving accuracy.

B. Evasion

The discussion evaluates evasion strategies against MAMADROID’s sequence-based behavioral model. Several code-modification strategies are difficult to execute without changing the resulting Markov chain, but static-analysis blind spots remain.

  • Small malicious injections into benign apps can create atypical Markov-chain transitions, making repackaging difficult to hide.The paper reports that its memory-booster malware example was correctly classified despite sharing most functionality with the original app.
  • Embedding benign code into malware is likely ineffective because features derive from transition probabilities across the entire app.Changing call sequences to preserve benign probabilities while retaining an attack is described as difficult.
  • Creating malware from scratch with a benign-like Markov chain is difficult because malicious behavior requires different abstracted call sequences.The feasibility of this strategy remains planned future work.
  • Static analysis fails to model code loaded or determined at runtime, including dynamic code and native code.Reflection, class loaders, and package contexts may be detected, but the loaded code itself cannot be modeled; dynamic analysis can mitigate this limitation.
  • Whitelisting recognized Android, Java, and Google packages prevents self-defined package names from confusing abstraction.The proposed attack uses names such as java.lang.reflect.malware to resemble framework packages.
  • Dynamic dispatch can be addressed by tracking self-defined classes extending or implementing recognized APIs, at a small computational cost.The text describes this as an implementation adjustment rather than an inherent detection failure.
  • Obfuscated self-defined calls are labeled as obfuscated and remain part of the behavioral model, while Android framework classes cannot be obfuscated.The sample showed significantly less obfuscation in benign apps than malicious apps.
  • Package-mode classification requires more than 100,000 features per sample, although PCA can substantially reduce memory complexity with little accuracy loss.Using 10 PCA components performs almost as well as using all features.

VI. RELATED WORK

Related work spans static, dynamic, hybrid, signature-based, and machine-learning approaches to Android security and malware detection. MAMADROID differs by modeling abstracted API-call sequences as statistical behavioral models aimed at unseen malware and resilience to API evolution.

  • A. Program Analysis: Static Android security analyses decompile app code to extract features without executing the program.Examples examine API calls, permissions, security rules, malicious patterns, vulnerabilities, and data flows.
  • A. Program Analysis: Dynamic analyses execute apps in protected environments to monitor runtime behavior, but their overhead makes direct deployment on users’ devices unrealistic.DroidScope and TaintDroid apply dynamic taint analysis to machine code or personal-data flows.
  • A. Program Analysis: Hybrid systems combine static and dynamic analysis, including input generation tailored to dynamic-analysis tools.IntelliDroid is one example among several combined approaches.
  • B. Malware Detection: Signature-based methods use network traces, resource metrics, permissions, API calls, or other extracted patterns to distinguish malware.These approaches include NetworkProfiler and feature-based systems combining static and dynamic behavior.
  • B. Malware Detection: System-call signatures can be evaded through polymorphism, obfuscation, and call reordering, motivating more robust statistical behavior models.MAMADROID inherits this behavioral-modeling approach while targeting greater resistance to evasion.
  • B. Malware Detection: MAMADROID targets previously unseen malware, including new families appearing years after training, unlike approaches focused on known malware families.Its goal is broader detection rather than family-specific identification.
  • B. Malware Detection: Dynamic malware detection may miss malicious behavior when predefined inputs fail to trigger it and can be sidestepped by knowledgeable adversaries.Random fuzzing and concolic testing are alternative dynamic-analysis approaches.
  • B. Malware Detection: MAMADROID models API-call sequences as Markov chains and abstracts calls to packages or families rather than relying on specific app characteristics.This design supports operation across apps created for different Android API levels.

VII. CONCLUSION

The paper presents MAMADROID, which models abstracted API-call sequences as Markov chains to detect Android malware. It reports high contemporaneous accuracy, sustained performance over two years, and greater resilience than DROIDAPIMINER, while identifying data-access and static-analysis limitations.

  • MAMADROID models API-call sequences as Markov chains using family or package abstraction.The two modes provide different abstraction granularities.
  • 99% F-measure is achieved for unknown malware developed earlier or around the same time as training samples.The evaluation uses a large malware dataset and measures classification accuracy and runtime performance.
  • 87% F-measure after one year and 73% after two years demonstrate maintained detection performance over time.These results concern models evaluated on newer samples than those used for training.
  • MAMADROID outperforms DROIDAPIMINER on matched datasets and is more resilient to Android API changes over time.The paper presents statistical behavioral models as more robust than traditional techniques.
  • The datasets and feature vectors are available upon request rather than readily online because of their large size.The authors also plan to investigate evasion resilience, finer-grained abstractions, and dynamic analysis.
Loading 1612.04433v3…