Similarity-based Android Malware Detection Using Hamming Distance of Static Binary Features

Rahim Taheri; Meysam Ghahramani; Reza Javidan; Mohammad Shojafar; Zahra Pooranian; Mauro Conti

Source-linked AI summary

Similarity-based Android Malware Detection Using Hamming Distance of Static Binary Features

Rahim Taheri, Meysam Ghahramani, Reza Javidan, Mohammad Shojafar, Zahra Pooranian, Mauro Conti

arXiv:1908.05759v2Aug 13, 2019cs.CRcs.LGcs.NEstat.ML

TL;DR

Android malware detection is critical because malicious apps threaten user privacy and security, while existing KNN-based approaches can be limited by fixed parameter choices. The paper proposes four Hamming-distance similarity methods using static Android features and evaluates them across three datasets and feature types, achieving strong accuracy and outperforming or matching comparison methods in reported settings.

Problem
Android malware threatens user privacy and system security, while a prior Hamming-distance KNN structure used a fixed k value that limits its design.
Method
The paper proposes four nearest-neighbor malware detectors using Hamming distance over ranked static Android application features: FNN, ANN, WANN, and KMNN.
Results
Across Drebin, Contagio, and Genome using API, intent, and permission features, the proposed methods generally outperform or compare favorably with PDME and FalDroid, reaching 99.33% accuracy for API features on Drebin.
Takeaways & Limitations
The reported results support Hamming-distance similarity methods as flexible static-feature approaches for classifying Android samples as benign or malware, including new samples.
Takeaways & Limitations
The methods rely on static features, so malware with similar functionality but substantially different features may not be recognized as similar.

Abstract

from arXiv · show

In this paper, we develop four malware detection methods using Hamming distance to find similarity between samples which are first nearest neighbors (FNN), all nearest neighbors (ANN), weighted all nearest neighbors (WANN), and k-medoid based nearest neighbors (KMNN). In our proposed methods, we can trigger the alarm if we detect an Android app is malicious. Hence, our solutions help us to avoid the spread of detected malware on a broader scale. We provide a detailed description of the proposed detection methods and related algorithms. We include an extensive analysis to asses the suitability of our proposed similarity-based detection methods. In this way, we perform our experiments on three datasets, including benign and malware Android apps like Drebin, Contagio, and Genome. Thus, to corroborate the actual effectiveness of our classifier, we carry out performance comparisons with some state-of-the-art classification and malware detection algorithms, namely Mixed and Separated solutions, the program dissimilarity measure based on entropy (PDME) and the FalDroid algorithms. We test our experiments in a different type of features: API, intent, and permission features on these three datasets. The results confirm that accuracy rates of proposed algorithms are more than 90% and in some cases (i.e., considering API features) are more than 99%, and are comparable with existing state-of-the-art solutions.

1. Introduction

The paper addresses Android malware detection using static binary features and Hamming-distance similarity. It proposes nearest-neighbor methods, evaluates them across datasets and feature types, and compares them with existing approaches.

Motivation: Android’s widespread use and malware prevalence make identifying malicious applications a critical security problem.The paper notes Android’s large market share, extensive malware activity, and risks to user privacy and mobile systems.
Open issues: Existing detection systems must recognize malware accurately while generalizing to new malicious families and operating with limited computation.The introduction highlights generalization and short-time deployment on mobile devices as important requirements.
Approach: The paper investigates Hamming distance for sparse binary Android features and develops modified nearest-neighbor methods combined with K-Medoids.The proposed framework uses static features, Random Forest feature selection, Hamming-distance neighbors, and four detection scenarios.
Evaluation: The study evaluates API, permission, and intent features on Drebin, Contagio, and Genome datasets and compares the methods with existing malware detectors.The comparisons include entropy-based PDME, FalDroid, and other state-of-the-art solutions, alongside time and space-complexity analysis.
Distance measure: For binary vectors, the paper states that Hamming distance produces the same result as Euclidean and Manhattan distance under its replacement method.This establishes the distance measure used by the proposed distance-based detection methods.

2. Related Work

Prior Android malware research uses static, dynamic, hybrid, behavioral, signature, and machine-learning approaches. The reviewed methods provide varied capabilities but also face computational, evasion, or feature-dependence limitations.

Static analysis: Static methods analyze features such as permissions, APIs, intents, URLs, byte sequences, and resource usage to classify Android applications.Examples include Drebin, StormDroid, DroidSIFT, ANASTASIA, and resource-profile-based detection.
Signature methods: Signature-oriented approaches can address some obfuscation techniques, including junk insertion, renaming, string encryption, and control-flow changes.AndroSimilar is described as generating signatures for static syntactic features while addressing these evasion techniques.
Dynamic analysis: Dynamic analysis executes applications in protected environments to observe malicious activity but can be constrained by smartphone resources.The literature also reports that triggering only on non-trivial events can miss malicious execution paths.
Hybrid analysis: Hybrid systems combine static and dynamic analysis, including permissions and sensitive APIs with runtime behavior, sometimes using deep learning.DroidDetector is presented as an example of this combined strategy.
Similarity methods: Similarity-based methods use opcode, histogram, entropy, or feature-based distances to identify related or metamorphic malware.The reviewed work includes opcode similarity, Euclidean histogram distance, entropy-based PDME, and KNN-based feature analysis.

3. Preliminaries

The paper represents Android applications as sparse binary feature vectors and organizes labeled benign and malware samples into a dataset for analysis. The sparse representation records APIs, permissions, and intents.

Sparse representation: A sparse matrix contains mostly zero elements and represents important Android application features.The paper uses this representation for APIs, permissions, and intents.
Dataset model: The dataset contains n labeled samples, with each sample represented using m feature elements.The formal dataset is written as D = {(x_i, y_i) | ∀i = 1, . . . , n}.
Binary features: Each sample vector is binary, with x_ij = 1 when feature j is present and x_ij = 0 otherwise.The labels y_i distinguish the sample classes, and the feature space is X ⊆ {0, 1}^m.

4. Proposed Approaches for Malware Detection System

The proposed system represents Android samples as binary feature vectors and uses Hamming-distance similarity to classify malware. It implements four nearest-neighbor strategies, with feature selection, voting, clustering, and sparse-set computation supporting the detection pipeline.

Distance representation: Manhattan, Minkowski, and Hamming distances produce the same result for binary vectors, so Hamming distance is selected for simpler computation.The equivalence is used to justify the proposed distance calculation.
Distance representation: Binary samples encode present features as 1 and absent features as 0, enabling distance-based identification of malware among benign samples.The paper states that Hamming distance is used to compute distances between binary sample vectors.
Proposed architecture: The architecture ranks static features with Random Forest, retains an α percentage, converts samples to binary vectors, and trains a classifier using Hamming similarities.The described pipeline selects features before binary encoding and model construction.
Detection scenarios: FNN selects one nearest training sample, whereas ANN stores all nearest samples and assigns the most frequent label.ANN voting uses label population without weighting malware features.
Detection scenarios: WANN incorporates feature-frequency weights into nearest-neighbor voting, while KMNN clusters nearest neighbors around medoids before voting.KMNN uses two clusters and ignores 10% of samples that are farther from the clusters before voting.
Complexity and implementation: O(n^2 × m) is the stated KMNN complexity under two clusters and ten repetitions, while sparse-set computation reduces a 21,492-feature distance to at most about 925 calculations.The complexity analysis assumes n samples and m features; the sparse-set example reports the tested worst case.

5. Experimental Evaluation

The experimental evaluation tests the proposed clustering-based detection algorithms under different scenarios.

Experimental evaluation: The study evaluates the proposed clustering algorithms under different experimental scenarios.The section introduces the evaluation before describing datasets, features, metrics, and comparison settings.

5.1. Simulation setup

The simulation uses three Android datasets, several static feature types, feature ranking and selection, held-out evaluation, and comparisons with established detection methods.

Datasets: The experiments use Drebin, Genome, and Contagio datasets containing Android benign and malware samples.Drebin includes 118,505 applications; Genome contains about 1,200 malware samples; Contagio contains 11,960 malware and 16,800 benign samples.
Features: The evaluated static features are permissions, APIs, and intents extracted from Android applications.The paper describes permissions, API calls, and inter-component communication as the feature categories.
Parameter setting: RandomForestRegressor ranks features, and experiments evaluate 10% through 100% of higher-ranked manifest features using a train-test split.The held-out sample is used to reduce bias in estimating model skill.
Comparison methods: The proposed algorithms are compared with joint solutions, PDME, and FalDroid detection methods.PDME uses entropy-based distance, while FalDroid is included as a classification comparison.

5.2. Test metrics

The evaluation uses confusion-matrix metrics to measure classification quality, error rates, threshold discrimination, and nearest-neighbor decisions.

Classification metrics: Accuracy, precision, recall, and F1-score quantify classification performance from confusion-matrix outcomes.F1-score is defined as the harmonic mean of precision and recall.
Error metric: False Positive Rate measures negative samples incorrectly classified as positive relative to all actual negative samples.It captures the rate of false alarms among negative events.
Threshold metrics: AUC measures the trade-off between misclassification rate and false-positive rate across classification thresholds.ROC depicts detection ability as the discrimination threshold varies.
Nearest-neighbor decisions: Similarity-based predictions use the labels of the most relevant neighbors to determine the test sample’s class.The paper describes first-neighbor selection and polling among neighboring samples as alternative decision procedures.
Metric interpretation: The reported maximum-accuracy case minimizes false positives and false negatives while maximizing true positives and true negatives.The paper identifies the corresponding confusion-matrix combination as the condition for maximum accuracy.

5.3. Experimental results

The experiments compare the proposed similarity-based methods with established malware-detection algorithms across three datasets and multiple Android feature types. The proposed methods generally achieve stronger accuracy and classification performance, particularly with API features.

Experimental setup: The experiments evaluate the proposed methods on Drebin, Contagio, and Genome datasets against Mixed, Separated, PDME, and FalDroid algorithms.API, intent, and permission features are considered.
Accuracy comparison: The proposed methods achieve higher accuracy than Mixed and Separated across the tested datasets and feature types, while increasing k improves both comparison methods.Separated averages below 90% accuracy and Mixed below 98% across the evaluated settings.
Precision, recall, and F1-score: FNN has high precision on Drebin API features, whereas ANN, WANN, and KMNN generally obtain higher recall; WANN has high recall for permission features.These patterns distinguish stronger benign-sample identification from stronger malware-sample detection.
Precision, recall, and F1-score: ANN, WANN, and KMNN generally obtain higher F1-scores than the alternatives, with the highest values reported for Drebin API and intent features, especially for ANN.PDME follows these methods, while FalDroid has the lowest F1-score; API features have the highest F1-score rate.
Accuracy, FPR, and AUC: 99.33% accuracy, 98.96% AUC, and 0.004 FPR are reported for a proposed method on Drebin API features, while FalDroid reaches about 90.89% accuracy in its best API setting.Increasing feature counts generally raises accuracy and AUC while lowering FPR, although the best results are not perfect.
ROC analysis: Over around 90% TPR can be achieved below 20% FPR for several proposed-method settings, with WANN and KMNN strongest for Drebin API features.FalDroid is reported to lack acceptable performance at high TPR and low FPR.

6. Discussion and Limitations

The discussion identifies computational and analytical constraints in the similarity-based methods, especially for large datasets and malware whose behavior is not reflected in static features.

Limitations: The methods’ constraints and ongoing research directions are explicitly discussed.The paper introduces this discussion before detailing limitations and future work.
Evaluation context: Table 6 reports accuracy and false-positive-rate results across API, permission, and intent features for Drebin, Contagio, and Genome.The table also identifies feature length and comparator algorithms including Random Forest, SVM, Decision Tree, and Neural Network.
Evaluation context: Table 7 compares results using 300 selected features with results using all features across the three datasets and feature types.The comparison uses accuracy and false positive rate as evaluation measures.
Static-analysis boundary: Static-feature Hamming distance may miss malware programs with the same functionality but substantially different features.The authors state that similarity is determined from static features, limiting detection of functionally similar but feature-dissimilar malware.
Computational cost: Three proposed algorithms have o(n×m) time complexity, while KMNN has o(n^2×m), which can require substantial runtime on enormous datasets.The paper notes that this issue is less common on smartphones but becomes important as data volume grows.
Static-analysis boundary: Static analysis is faster than dynamic analysis for building models from features, but it may fail to recognize some unknown malware behaviors.The authors contrast static analysis’s speed with dynamic analysis’s ability to observe behavior during execution.

7. Conclusions and Future Work

The paper concludes that four Hamming-distance nearest-neighbor methods detect Android malware from binary API, intent, and permission features across three public datasets. It reports high accuracy, including roughly 99% for the Drebin API setting, and proposes richer similarity measures for future work.

Conclusions: The study presents FNN, ANN, WANN, and KMNN as Hamming-distance nearest-neighborhood methods for Android malware detection.The methods use binary application features and are evaluated on Drebin, Genome, and Contagio with API, intent, and permission inputs.
Conclusions: Across Drebin permission and intent features, the proposed methods achieve accuracies from 90.05% to 98.04% and generally outperform or match the cited baselines.WANN is reported as strongest for permission and intent features, while KMNN and ANN perform strongly with API features.
Future work: Future work could define similarity measures using additional program features and correlations between features rather than only feature frequencies.The authors suggest that feature correlations may help detect similarity between malware programs.

Biographies

The biographies describe the authors’ academic backgrounds and research affiliations across computer engineering, mathematics, cryptography, network security, privacy, and related areas.

Author biographies: Rahim Taheri is a Ph.D. candidate in Computer Networks at Shiraz University of Technology and joined the University of Padua’s SPRITZ group as a visiting Ph.D. student.His stated interests include machine learning, data mining, and network security.
Author biographies: Meysam Ghahramani studied mathematics and applications, cryptography, and computer engineering, and is a Ph.D. student at Shiraz University of Technology.The biography also notes his university programming competition achievement and distinguished-student award.
Author biographies: Reza Javidan holds doctoral training in artificial intelligence and works across network security, image processing, underwater sensor networks, and software-defined networks.His degrees include a Ph.D. in Computer Engineering from Shiraz University.
Author biographies: Mohammad Shojafar is a Marie Curie Fellow and Senior Researcher in the SPRITZ Security and Privacy Research Group at the University of Padua.His research interests include network and network security and privacy.
Author biographies: Zahra Pooranian is a postdoctoral researcher in the SPRITZ group at the University of Padua and an editor and author in computer science venues.Her biography reports a Ph.D. from Sapienza University of Rome and research focused on security-related topics.
Author biographies: Mauro Conti is a professor of computer science whose research interests include network and security-related topics.His biography lists a doctorate from Sapienza University of Rome and visiting research appointments at multiple universities.

A. Toy example of presented methods

The toy example applies the four proposed methods to a binary sample dataset using Hamming distances, nearest-neighbor voting, feature and sample weights, and KMNN clustering.

Data representation: The example represents the target sample and training set as sparse binary feature vectors and matrices.Only feature locations with value 1 are stored for the sparse representation.
Distance calculation: Hamming distances from target sample X to every training sample are computed by comparing corresponding vector elements.Table 8 records these distances for the sample dataset.
FNN: FNN assigns X the label of its single closest sample, which is S2 with label 0 in the example.The example selects S2 as the first nearest sample.
ANN: ANN selects all samples tied at the nearest distance—S2, S4, S7, and S8—and assigns X the majority-vote label 1.The selected vectors have distance value 2 in the example.
WANN: WANN weights features and samples, then votes among similar samples; for X, S2, S3, S5, and S7 produce label 1.The example first derives feature weights and then calculates each sample’s total feature weight.
KMNN: KMNN clusters selected neighbors by pairwise distances, chooses cluster heads, excludes the most distant 25% in the example, and votes to label X as 1.S2 and S8 form one cluster, S4 and S7 another, with S2 and S4 serving as cluster heads.