Abstract
The increasingly sophisticated Android malware calls for new defensive techniques that are capable of protecting mobile users against novel threats. In this paper, we first extract the runtime Application Programming Interface (API) call sequences from Android apps, and then analyze higher-level semantic relations within the ecosystem to comprehensively characterize the apps. To model different types of entities (i.e., app, API, device, signature, affiliation) and rich relations among them, we present a structured heterogeneous graph (HG) for modeling. To efficiently classify nodes (e.g., apps) in the constructed HG, we propose the HG-Learning method to first obtain in-sample node embeddings and then learn representations of out-of-sample nodes without rerunning/adjusting HG embeddings at the first attempt. We later design a deep neural network classifier taking the learned HG representations as inputs for real-time Android malware detection. Comprehensive experiments on large-scale and real sample collections from Tencent Security Lab are performed to compare various baselines. Promising results demonstrate that our developed system AiDroid which integrates our proposed method outperforms others in real-time Android malware detection.
Introduction
Android malware has evolved significantly, adopting complex "Command and Control" (C&C) tactics to evade traditional detection. These malicious applications often remain dormant until specific conditions are met, making static analysis insufficient. Heterogeneous Graphs (HGs) have emerged as a powerful tool to model the intricate relationships within the Android ecosystem—connecting apps through shared developers, device identifiers (IMEI), signatures, and API call sequences.
However, a significant bottleneck exists: the out-of-sample problem. Most graph embedding techniques are transductive, meaning they can only represent nodes present during the initial training phase. In a production environment where thousands of new apps are released daily, rerunning graph embeddings for every new sample is computationally prohibitive. This paper introduces AiDroid, a framework designed to solve this problem by enabling real-time classification of new nodes without retraining the entire graph.
The AiDroid Framework
AiDroid operates by first constructing a comprehensive HG that captures the semantic richness of the Android environment. It models five entity types: Apps, APIs, IMEIs, Signatures, and Affiliations. To ensure the graph captures meaningful behavioral patterns, the system utilizes six expert-defined meta-paths (PID1-PID6), such as App → API → App or App → Signature → App.
HG-Learning: Solving the Out-of-Sample Problem
The core innovation of AiDroid is the HG-Learning method, which consists of two distinct phases:
- HGiNE (In-sample Embedding): For known apps, the system performs meta-path guided random walks. These walks capture high-level semantic relationships and are processed via a skip-gram model to generate $d$-dimensional embedding vectors for each node.
- HG2Img (Out-of-sample Representation): To handle a new, unknown app, AiDroid avoids recalculating the entire graph. Instead, it constructs a $t \times d$ matrix that represents the app's "neighborhood." This matrix stacks the pre-calculated embeddings of the app's $k$-order neighbors (e.g., the APIs it invokes or its developer's signature). By treating the app as the sum of its connections, the system creates a robust representation for nodes that were not part of the original training set.
These neighborhood matrices are then fed into a Deep Neural Network (DNN) Classifier. The classifier uses a CNN-based architecture with Inception modules to identify local patterns within the neighborhood matrix, effectively determining the maliciousness of the app based on the "company it keeps."
Experimental Evaluation
The system was evaluated using a massive dataset from Tencent Security Lab, comprising over 190,000 training apps and 17,000 newly arriving test apps. The resulting graph contained over 4.1 million edges.
- Accuracy: AiDroid achieved an Accuracy (ACC) of 0.9908 and an F1 score of 0.9817, significantly outperforming traditional graph methods like DeepWalk and metapath2vec.
- Efficiency: The average detection time was a mere 4.3 ms per app, meeting the requirements for real-time mobile security scanning.
- Robustness: Interestingly, the HG2Img approach outperformed a baseline that completely reran the graph embedding for new nodes (0.9843 ACC), suggesting that the matrix-based neighborhood representation is more resilient to the noise of new samples.
Conclusion
AiDroid successfully bridges the gap between complex graph-based modeling and the requirements of real-time malware detection. By representing out-of-sample nodes through their latent neighborhood space, the system eliminates the need for costly retraining while maintaining state-of-the-art accuracy. Future work will explore the "cold start" problem for apps with no known neighbors and the optimization of dynamic analysis overhead.
Summary updated