Structural Attack against Graph Based Android Malware Detection

Malware detection techniques achieve great success with deeper insight into the semantics of malware. Among existing detection techniques, function call graph (FCG) based methods achieve promising performance due to their prominent representations of malware's functionalities. Meanwhile, recent adversarial attacks not only perturb feature vectors to deceive classifiers (i.e., feature-space attacks) but also investigate how to generate real evasive malware (i.e., problem-space attacks). However, existing problem-space attacks are limited due to their inconsistent transformations between feature space and problem space. In this paper, we propose the first structural attack against graph-based Android malware detection techniques, which addresses the inverse-transformation problem [1] between feature-space attacks and problem-space attacks. We design a Heuristic optimization model integrated with Reinforcement learning framework to optimize our structural ATtack (HRAT). HRAT includes four types of graph modifications (i.e., inserting and deleting nodes, adding edges and rewiring) that correspond to four manipulations on apps (i.e., inserting and deleting methods, adding call relation, rewiring). Through extensive experiments on over 30k Android apps, HRAT demonstrates outstanding attack performance on both feature space (over 90% attack success rate) and problem space (up to 100% attack success rate in most cases). Besides, the experiment results show that combing multiple attack behaviors strategically makes the attack more effective and efficient.