基于 API 调用图嵌入与深度学习的 Android 恶意软件检测

发表于 更新于

本文介绍2020年 Soft Computing 期刊的一篇文章，题目是《Deep learning for effective Android malware detection using API call graph embeddings》，DOI信息在这里。

本文提出一种新颖的伪动态分析方法，首先通过静态分析，生成 API 调用图，再使用 API 调用图表示恶意软件在运行期间所有可执行、可跟踪的路径，进行特征提取并使用深度神经网络进行分类。

概览

由于 Android App 具有较高渗透率及较多恶意软件变种，需要高效、有效的恶意软件检测方法，以构建移动平台的安全。由 API 调用图结构衍生出的 API 调用序列可以用来准确地模拟 App 行为，而且可以通过跟踪 API 调用图、分支和调用顺序来提取行为。但识别图中的相似性并使用图匹配算法进行分类，具有慢速、复杂、结果可能不准确等诸多缺点。这篇文章的研究中，作者使用 API 调用图来表示恶意软件在运行期间所有可执行、可跟踪的路径，将 API 调用图转化为低维数值向量特征集的嵌入 (embedding) ，并引入深度神经网络。文章也通过评估不同的嵌入算法、调整各种网络配置参数，以保证超参数的最佳组合，达到最高的统计指标值，从而实现网络性能的最大化。实验证明，文章提出的这一方法能够达到较高的准确率。

简介

移动设备及其 App 与 Internet 接入的渗透使人们的日常生活变得更容易，如网上银行、电子商店购物、电子邮件，同时伴随着安全问题与信息泄露的风险。2017 年第一季度，全球共生产了 3443 亿部智能手机，其中 Android 系统占据了 85% 的份额，创下了历史新高。 Android 是一个开源的操作系统，它吸引了潜在的买家，但也吸引了恶意软件开发者来执行他们的恶意意图。 Android App 可以自签名 （self-signed） ，这为追溯其开发者带来了困难，同时允许攻击者修改现有 App 、添加恶意负载并重新打包。 Symantec 公司的报告指出，于 2016 年检测到 1840 万个移动恶意软件变种，增长了105%，与上年152%的增长幅度基本持平。但是，2016 年发现了 4 个新的移动家族和 61 个不同的新移动威胁集群，而 2015 年则发现了 18 个新家族和 75 个集群。这可以解释为，恶意软件开发者一直专注于完善和修改现有的恶意软件家族，以逃避检测和执行恶意意图，而不是开发新型的恶意软件威胁。

基于机器学习方法的 Android 恶意软件检测通常依赖于较大的 App 数据集，在训练过程中，检测系统需要配置最佳的参数值，才能在预测中达到最好的效果。由于恶意软件及其变种数量众多，为减少人们的工作量，必须使用可扩展和自动化的检测系统。特征提取方法一般分为静态与动态分析两种。静态特征，如应用程序接口 （API） 调用、操作代码 （opcode） 序列、权限请求、控制流或数据流，通过应用 API 调用图发现 API 调用之间的关系。这些特征严重依赖于数据分布，采用大数据集可以实现更全面的学习，同时有望获得更可靠的检测性能。动态特征通过执行给定的 Android App 提取，主要通过日志文件，监控网络、文件系统访问、 Android 系统交互。深度神经网络 (Deep Neural Network，DNN) 是新兴的学习模型，它被训练为近似于输入和输出之间的非线性函数。 DNN 具有从构型到神经元的数量、激活函数及其参数等多种调优选项，且可以根据不同检测目标进行调优，并使统计度量结果最优化。

本文提出的方法对 Android App 进行伪动态分析，并构建各执行路径的 API 调用图。之后，使用图嵌入 （graph embedding） 的方法，将调用图转换为捕获图的结构信息的低维特征向量。 引入DNN，通过其卷积层从图嵌入矩阵中检测和提取隐含的结构相似性。使用 Android App 的大数据集提取 API 调用图，通过网络中的密集层 （dense layer） 进行二进制代码相似性检测，结合卷积层发现的所有复杂的局部特征，以有效、高效的方式判断样本是否具有恶意。在训练和测试模型时，使用了 GPU 技术支持的并行处理功能。特别地，文章对 DNN 进行了评估和测试，认为它是一种很有前景的解决方案，因为其可以通过提取的调用图从大量的 App 中揭示隐含的知识。

文章的主要贡献概括如下：

  • 捕获所有被调用 API 的执行路径，并构建每个执行路径的 API 调用图。应用伪动态分析方法，即不运行 App ，而是通过 API 调用序列来分析所有执行路径。
  • 对图嵌入方法进行了评估，将调用图的大维度缩减为低维度的特征向量，并以高效的方式捕获从大量应用集中提取的图的结构信息。
  • 对深度学习架构参数进行调优，并应用树形结构 Parzen 估计器在参数超平面上寻求最优参数。
  • 通过大量的实验，对不同的架构进行了测试和对比。保证了在检测恶意 App 时统计指标值的最高水平。

方法概述

文章提出的 Android 恶意软件检测方法包括 6 个连续的主要阶段。

  • 第 1 阶段是对 Android App 进行伪动态分析，提取被检样本的 API 调用图。对所有执行路径的调用 API 进行捕获，并建立每个执行路径的 API 调用图。检查每一个 Android App 样本的 API 调用次数是否满足阈值，若调用次数大于或等于阈值，则其被选中，生成图嵌入；否则其被丢弃。在本研究中，生成 API 调用次数的阈值设置为60。
  • 第 2 阶段，根据构建的图计算图嵌入。
  • 第 3 阶段，由于机器学习和深度学习方法依赖于数值，因此对图嵌入特征进行预处理，对其进行数值解释。嵌入向量经过归一化处理，其中的每个值都在 0 到 255 之间。
  • 第 4 阶段，由于图嵌入的维度巨大，嵌入向量被重放缩 （rescale） 为较小的形式以便高效处理。
  • 第 5 阶段，将归一化和重新调整的特征向量（即嵌入向量）传入到 DNN 中，建立分类模型。
  • 第 6 阶段，采用超参数调优，寻找性能最好的网络配置。

最后，对所提出的方法的分类性能进行评价。流程图如下图所示。

方法流程图

背景： Android OS 与 App

Android App 一般使用 Java 语言编码，并在 Dalvik Java 虚拟机中运行。从 Android 5.0 版本开始， Google 用另一个名为 Android Runtime（ART）的应用运行环境取代了 Dalvik 虚拟机。 2017 年， Google 宣布， Kotlin 已被决定为他们未来发布的主要开发语言。事实上，Kotlin 语言与 Java 语言编译后的 App 输出均为 Java 虚拟机可执行文件 （executable，exe） ，底层运行时结构保持不变。（此处原文存在错误，混淆了 Kotlin 与 Groovy 两个技术。Kotlin on Android. Now official）

Android App 被打包为 APK （Android Package） 文件分发。 APK 文件包含 App 的 Dalvik 字节码与诸如图片、数据等的资源文件，此外还包括 manifext.xml 文件，此文件定义了 App 拥有的权限。 Android App 包含 4 个与 OS 及其它 App 交互的关键组件，当 App 在运行时，这些组件遵循不同的执行路径，相互协调运行。它们是：

  • Activity ：为用户提供与手机屏幕和任何其它用户界面的交互。
  • Service ：在没有用户交互的情况下处理后台作业。
  • Broadcast Receiver ：实现不同 App 之间的相互通信。
  • Content Provider ：访问和更改短信、联系人列表、图片等数据。

为 Android App 建立 API 调用图

研究 API 调用序列可以帮助有效地揭示 App 的意图。例如，当一个 App 想要获取设备 ID 时，它必须利用 Android 平台的相关 API 调用。控制流图 （Control Flow Graph，CFG） 是指在其运行时被调用的所有可能的执行路径的图表示。在 Android 平台上， Java 类的每个方法都可以用 CFG 来表示。而对于整体而言，整个 App 也可以通过其方法的 CFG 组合来呈现。

正式地，一个 CFG 是一个有向图 （directed graph） $G = (N, E)$ ，其中 $N$ 是一个有限的节点集合，代表 Android 的 API 调用； $E$ 是一个有限的边集合，代表连续指令之间的链接。边 $(n_1, n_2)$ 表示在一个执行路径中， $n_2$ 代表的 API 在 $n_1$ 代表的 API 调用后执行。

要构建整个 App 的控制流图，首先需要定义一个或多个入口点 （entry point） 。Android App 与传统的 Java 程序不同， Java 程序只有一个入口点（即 main 方法），但是 Android App 可以有多个入口点。入口点在处理不同类型的事件（如启动服务、触摸屏幕、改变手机音量等）中起到门户的作用，使用回调 （callback） 机制将事件移交给 App 的事件处理方法。需要将这些事件处理方法作为入口点，才能成功提取和构建 CFG 。事实上， App 的入口点是 Android 平台根据用户或 Android 操作系统发起的预定义事件发生而调用的主要功能。Android App 的这三类入口点分别是 Service 、Broadcast Receiver 和 Activity。

当提取出 Android 平台提供的一组主要入口点后，可以根据它们建立 API 调用图。如果有对其他方法的调用，则建立一个从调用者方法到其他方法的链接，以便包含 Android App 所有可能的 API 调用。所有从起始点可以到达的 API 调用都是按照调用顺序绘制的。这种方法不仅分析了 Android 的核心 API ，还分析了 Apache 等已知第三方库的 API 调用。然而，作者只关心 Android App 的基本构件，而不关心用户定义的执行任务的方法，因为这些方法随 App 的不同而存在差异，可能导致对分析结果的误导。文章使用 FlowDroid 框架作为调用图建立工具。

下两图示意了一段恶意 App 的伪代码与其对应的 API 调用图。首先，该 App 通过 TelephoneManager 对象收集设备的具体信息，包括 IMEI 、运营商名称、电话号码，从而访问手机上的电话服务。然后，该 App 检查已安装的银行 App ，然后将所有收集到的信息上传到命令和控制 （Command and Control，C&C） 服务器。这个恶意 App 以无限循环的方式运行，并在每次循环结束时休眠 3 秒。如图所示， API 调用图通过跟踪事件、意图在边（edge）与边之间的转换，提供了足够的程序功能信息。

恶意 App 源代码

示例恶意 App 源代码的调用图

图嵌入

图结构可以用来表示特征数据，适用于（包括但不限于）异常检测、节点分类、链路预测、社区检测等多种问题。有效、高效的图分析可以提供有价值的数据性质信息。然而，图分析是 NP 问题，需要耗费大量时间、空间与运算资源。图嵌入是一种有前途的解决方案，它能以一种高效和有效的方式实现图分析。图嵌入可以将各种类型的图，如有向图、无向图、归属图等转换为代表整个图或部分图（例如节点、边缘或子图）的低维特征向量或向量集，其中隐藏的图信息被保存下来。

图嵌入将每个节点转化为低维向量的同时，保留了图的结构信息。图嵌入的主要目标是从图结构数据中挖掘出潜在的信息。之后，提取出的有用向量表示可以被机器学习算法应用于分类或回归目的。具有类似 API 调用图的 App 往往会被归入同一类别，即恶意与良性的二元分类，或多个 Android 家族的多类别分类。文章测试了不同的图嵌入方法，以追求开发最优的二元分类系统。

正式地，图嵌入将给定的图 $G$ 映射为 $d$ 维特征空间 $\Phi(v)$，其中特征空间的维度 $d$ 小于 $N$ 代表的 Android 文档中 API 调用的有限节点集的维度，即 $d \ll N$。为说明图嵌入方法，引入下面两个定义。

定义 1 ： 路径 图的一个路径 （walk） 是一个有序或无序的节点序列 $v_1, v_2, \ldots, v_{k+1}$ ，其中 $v_i, v_{i + 1}$ ($ 1 \leq i \leq k)$ 。路径的长度定义为其中的边的数量，上例中路径的长度为 $k$ 。

定义 2 ： 随机路径 设 $G$ 为一个有向或无向图。图中节点 $v$ 的度 $deg(v)$ 定义为包含 $v$ 的边的数量。在有向图中，$v$ 的出度 $deg^+(v)$ 是从 $v$ 开始的边的数量。对于图中的一个节点 $v_j$ ，在每次迭代中，如果 $v_j, v_i \in G$ ，随机路径穿过一个临近节点 $v_i$ ，其概率对于有向图是 $\frac{1}{deg^+(v)}$ ，对于无向图是 $\frac{1}{deg(v)}$ （即按照相等概率随机选择一个临近节点）。否则，概率为 0 。

Skip-gram 模型已被用于自然语言处理领域的词序列建模。Skip-gram 模型最大限度地提高句子中给定窗口内出现的词的共现概率。Skip-gram 使用 softmax 函数来估计概率分布，但是由于单词语料库的规模非常大，计算邻域的概率分布非常昂贵。研究者提出了不同的算法加速这一过程。

定义 3 ： Skip-gram Skip-gram 迭代所有在固定尺寸窗口内随机路径产生的序列。在每次迭代中，此方法将节点 $v_j$ 映射为表征向量 $\Phi(v_j) \in \mathbb{R}^d$ 。之后，该方法最大限度地提高其邻居（或由 $c$ 表示的上下文单词）对由 $w$ 表示的给定目标词的概率，即 $max\sum_{w\in V}\sum_{v\in V_c}\log P(c|w)$ ，其中 $V$ 是整个单词表， $V_c$ 是上下文单词表。 $V_c$ 可认为与 $V$ 相同。Skip-gram 模型使用下面的公式计算上下文单词的似然估计：

$$
P(c|w) = \frac{\exp (\Phi(w)^T\Phi(c))}{\sum\limits_{c_i\in V}\exp \Phi(w^T)\Phi(c_i)}
$$

其中，$\Phi(\cdot)$ 表示单词表到 $d$ 维向量的映射。根据以上的定义，可以引出下面的 4 种图嵌入方法。

DeepWalk

DeepWalk 由两个主要阶段组成。在第一阶段，算法生成语料库 $D$ ，通过进行一个固定长度的随机路径 $R_v$ ，从图的每个节点开始，此处称起始节点为 $i$ 。然后，在第二阶段，算法对每一个节点进行固定大小的随机行走迭代。设带有威胁的节点（即恶意代码的节点）出现在一个长度为 $w$ 的 $v_j$ 的上下文窗口内。 $\Phi(v_j)$ 为边 $v_j$ 的向量表示。第 $i$ 个顶点的条件概率和第 $j$ 个顶点的向量表示由 $P(v_i|\Phi(v_j))$ 给出。给定条件概率最大化的目标函数定义如下：

$$
\max\limits_{\Phi} \sum\limits_{i\in { j-a,\ldots,j-1,j+1, \ldots,j+a } }\log P(v_i|\Phi(v_j))
$$

其中 $w$ 是窗口的大小， $2a=w$ 。由此， DeepWalk 采用 Hierarchical Softmax 计算条件概率。

Node2vec

Node2vec是另一种基于随机路径的图嵌入方法。在提出的目标函数方面，它与 DeepWalk 类似；但在计算目标时， Node2vec 使用了负采样 （Negative Sampling） 而不是 Hierarchical Softmax 。此外，通过引入一个偏置项 $\alpha$ ， Node2vec 还提出了一种发现节点 $vj$ 的邻域的方法。此偏置项不仅考虑当前节点，还考虑了前一个节点，以此来强制算法考虑下一个要跟踪的节点。

虽然 DeepWalk 和 Node2vec 是对图进行建模的有效、高效的方法，但它们的有效性受到基于随机路径的搜索的限制。随机路径只能利用到图的局部结构，而不能保证图中潜在信息的转换和表示。由于较大的图需要更多的随机路径，它们也会受到影响。为了克服这些限制，文章引入了基于深度学习和基于因子化的方法。

结构化深度网络嵌入

最近，CNN 已被用于从图中提取隐含特征。进一步地，已有成果引入深度自编码器来降低维度，将非线性数据映射到一个较低维度的向量空间中。这些成果已被用于生成图嵌入。结构化深度网络嵌入 （Structural Deep Network Embedding，SDNE） 是一种基于自编码器的深度图嵌入，通过使用高度非线性的激活函数，来保存一阶和二阶网络的近似性。 SDNE 有两种模块模块：监督模块 （superwised module） ，在生成的嵌入空间中，对相互映射但距离较远的节点施加惩罚；无监督模块 （unsupervised module） ，本质上是一个自编码器，用于生成节点的嵌入。

高阶近似保留嵌入

高阶近似保存嵌入 （Higher-Order Proximity Preserved Embedding，HOPE） 是一种基于因子化 （factorization-based） 的算法，其中节点的连接被表示为一个矩阵，这个矩阵被因子化后产生嵌入。用于建模的表示矩阵可以根据属性的不同而不同，如节点相邻矩阵、 Katz 相似度矩阵、 Laplacian 矩阵等。例如，梯度下降法可以用来生成非结构化矩阵的图嵌入。 HOPE 的目的是通过引入高阶近似性来保存有向图的非对称转义。

DNN 的结构

深度学习指 ANN (Artificial Neural Networks) ，它是机器学习的一个子领域。“深度”一词在人工智能领域指神经网络的隐藏层数。 ANN 在生物学上的灵感来自于人类大脑的结构和功能，它可以从大规模的观察数据中学习。

随着 CNN 和 RNN 架构的引入，神经网络的有用性和适用性得到了加强。 CNN 架构设计是为了处理和编码输入数据的某些隐藏信息。输入数据一般是一个多维数组。输入数组的维度可以调整，如文本序列为 1 维、灰度图像为 2 维、彩色图像或视频为 3 维。 CNN 由三种网络层组成，分别是卷积层、池化层和全连接层。卷积层使用卷积运算，即在给定的 filter 和输入数据的局部区域之间进行点乘运算，创建卷积特征。全连接层指神经网络层，它与池化层的所有单元连接。池化层对应的功能是逐步缩小卷积特征的空间大小，降低计算成本和待调参数的大小。

本文建立的神经网络结构如下图所示。深度网络的输入经过图嵌入方法预处理，其结构类似于一个单通道的灰色图像。卷积层检测并提取图嵌入矩阵中的隐藏结构信息。第 1 个卷积层检测嵌入矩阵中的原始特征，而第 2 个卷积层通过将原始特征组合成更复杂的特征来推导更深层次的特征。在这些卷积层之后，使用最大池化来降低数据的维度。扁平层将卷积层的输出转换为一个长的一维特征向量，因为 ANN 需要一维向量来执行分类任务。最后，密集层通过结合卷积层发现的所有复杂的局部特征，对给定的特征进行分类，判断样本是恶意还是良性的。

神经网络结构示意图