This paper proposes a technique for automatically learning semantic malware
signatures for Android from very few samples of a malware family. The key idea
underlying our technique is to look for a maximally suspicious common subgraph
(MSCS) that is shared between all known instances of a malware family. An MSCS
describes the shared functionality between multiple Android applications in
terms of inter-component call relations and their semantic metadata (e.g.,
data-flow properties). Our approach identifies such maximally suspicious common
subgraphs by reducing the problem to maximum satisfiability. Once a semantic
signature is learned, our approach uses a combination of static analysis and a
new approximate signature matching algorithm to determine whether an Android
application matches the semantic signature characterizing a given malware
family.
We have implemented our approach in a tool called ASTROID and show that it
has a number of advantages over state-of-the-art malware detection techniques.
First, we compare the semantic malware signatures automatically synthesized by
ASTROID with manually-written signatures used in previous work and show that
the signatures learned by ASTROID perform better in terms of accuracy as well
as precision. Second, we compare ASTROID against two state-of-the-art malware
detection tools and demonstrate its advantages in terms of interpretability and
accuracy. Finally, we demonstrate that ASTROID's approximate signature matching
algorithm is resistant to behavioral obfuscation and that it can be used to
detect zero-day malware. In particular, we were able to find 22 instances of
zero-day malware in Google Play that are not reported as malware by existing
tools.

本文提出了一种针对 Android 恶意软件从极少量样本中自动学习语义恶意软件特征的技术，使用 ASTROID 工具实现了特征合成、检测和评估，并展示了该方法相对于现有技术的优势，包括更好的准确性和精度，以及对行为混淆的抵抗性和零日恶意软件的检测能力。