DroidFusion：多级分类器融合的 Android 恶意 APP 检测方法

本文介绍2019年 IEEE Trans. on Cybernetics 期刊的一篇文章，题目是《DroidFusion: A Novel Multilevel Classifier Fusion Approach for Android Malware Detection》，DOI信息在这里。

在这篇论文中，作者提出了一种基于多层次架构的分类器融合方法。该框架称为 DroidFusion ，通过在低层训练基础分类器生成模型，然后在高层应用一组基于排序的算法对其精度进行预测，得出最终的分类器。文章语言精炼，逻辑严密，值得认真学习。

概览

Android 恶意软件的数量和复杂性持续增长，对移动设备的安全及其所提供的服务构成重大威胁。这促使人们对利用机器学习来提高Android恶意软件检测的兴趣越来越大。在这篇论文中，作者提出了一种基于多层次架构的新型分类器融合方法，能够有效地结合机器学习算法，提高准确性。该框架（称为 DroidFusion ），通过在低层训练基础分类器生成模型，然后在高层应用一组基于排序的算法对其预测精度进行预测，得出最终的分类器。产生的多级 DroidFusion 模型可以作为 Android 恶意软件检测的改进型预测器。

文章在四个独立的数据集上展示了实验结果，以证明提出方法的有效性。此外，文章证明了 DroidFusion 方法也可以有效地实现集成学习算法以提高准确性。最后，文章展示了 DroidFusion 的预测精度，尽管在更高的层次上只利用了计算方法，但其预测精度可以优于堆栈泛化法（堆栈泛化法是一种著名的分类器融合方法，在更高的层次上采用了元分类器方法）。

简介

近几年来，Android 系统已经成为全球移动操作系统中的佼佼者，在全球市场占有率大幅提升。目前已售出超过10亿台 Android 设备，仅 Google Play 的应用下载量就达650亿次。Android 系统的普及率的增长和第三方应用市场的泛滥也使其成为恶意软件的热门目标。去年， McAfee 报告称，Android 恶意软件样本超过1200万个，每年有近250万个新样本被发现。 Android 恶意软件可以嵌入到各种 APP 中，如银行、游戏、生活、教育 APP 等。这些被恶意软件感染的应用程序可以通过允许未经授权访问隐私敏感信息、root 设备、将设备变成远程控制的傀儡机器等方式，破坏安全和隐私。

零日（zero-day） Android 恶意软件有能力躲避传统的、基于签名的防御措施。因此，迫切需要开发更有效的检测方法。最近，基于机器学习的方法越来越多地被应用到 Android 恶意软件检测中。然而，分类器融合方法并没有像在网络入侵检测等其他领域中那样得到广泛的探索。

在本文中，作者提出并研究了一种新颖的分类器融合方法，利用多级架构来提高机器学习算法的预测能力。该框架被称为 DroidFusion，其设计目的是通过在底层训练一些基础分类器来诱导一个 Android 恶意软件检测的分类模型。然后利用一组基于排序的算法在更高的层次上推导出组合方案，并选择其中的一个来建立最终的模型。 该框架不仅可以利用传统的单一学习算法，如决策树或朴素贝叶斯，还可以利用集合学习算法，如随机森林、随机子空间、Boosting 等来提高分类精度。

为了证明 DroidFusion 方法的有效性，文章对四个数据集进行了大量的实验，这些数据集是从两个公开的、广泛使用的恶意软件样本集合（即 Android Malgenome 项目和 DREBIN 项目）和英特尔安全公司（前身为 McAfee ）提供的样本集合中提取特征而得到的特征。

DroidFusion 框架

DroidFusion 框架由一个多层次的分类器融合体系结构组成。它被设计成一个通用分类器融合系统，因此，它既可以应用于传统的单一分类器，也可以应用于集合分类器。在底层，基础分类器在训练集上使用分层 N 折交叉验证技术训练，以估计其相对预测精度。这些结果被四种不同的基于排序的算法（在上层）所利用，这些算法定义了某些标准，用于选择和随后组合适用的基础分类器的子集（或全部）。排序算法的结果被组合成对，以便找到最强的一对，随后用来建立最终的 DroidFusion 模型（在对基础分类器的非加权并行组合进行测试后）。

DroidFusion 模型建立

模型的建立（即训练过程）与预测或测试阶段不同，因为前者利用训练-验证集建立一个多级集合分类器，而后在后一阶段的测试集上进行评估。下图显示了 DroidFusion 的两级架构。它显示了训练路径（实心箭头）和测试/预测路径（虚线箭头）。

首先，在底层，每个基础分类器都要经过 N 折交叉验证来估计性能精度。令 $P_{base}$ 表示 $K$ 基分类器的 N 折交叉验证预测准确率，则一个 $K$ 基分类器的类准确率 $K$ 元组可以表示为
$$
P_{base} = { [ P_{1m}, P_{1b} ], [P_{2m}, P_{2b} ], \ldots, [P_{Km}, P_{Kb} ], }
$$

其中，$m$ 表示恶意（malicious）类，$b$ 表示良性（benign）类。 $P_{base}$ 中的元素之后会被应用到基于排序的算法中，文章提出了 AAB、CDB、RAPC 与 RACD 4种方案（scheme）。令 $X$ 为实例总数，其中恶意实例数为 $M$，良性实例数为 $B$ 。标签 $L$ 表示每个实例的类别：$L = 1$ 表示恶意实例，$L = 0$ 表示良性实例。每个实例同样由具有 $f$ 个二元表征的特征向量表示，$f$ 是从给定APP中提取的特征数量。向量中的特征取值为 0 或 1，代表给定特征的缺失或存在。此外，经过N折交叉验证过程后（如上图所示），对每一个实例 $x$ 的 $K$ 元组类预测，都会得到一组 $K$ 元组类预测值， 表示为
$$
V(x) = { v_1, v_2, \ldots, v_k }, \forall k \in {1, \ldots, K }
$$

注意 $v_1, v_2, \ldots, v_k$ 可能是0、1这样准确的预测结果，也可能是概率。再将（已知的）标签 $l$ 加入其中，可得：
$$
\dot{V}(x) = { v_1, v_2, \ldots, v_k, l }, \forall k \in {1, \ldots, K }, k \in { 0, 1 }
$$

在DroidFusion的构建过程中，$P_{base}$ 与 $\dot{V}(x), \forall x \in X$ 会在第 2 层计算中用到。令 $S = { S1, S2, S3, S4 }$ 表示4个基于排序的方案，它们两两组合成对，有6种可能性：
$$
\phi = { S1S2, S1S3, S1S4, S2S3, S2S4, S3S4 }
$$

目标是从 $S$ 中选出最优的排序方案对，如果它的性能超过了原始基础分类器的非加权组合，那么它将被选取来构建最终的 DroidFusion 模型。如果非加权方案性能较高，DroidFusion 将被配置为在最终的结构化模型中应用基础分类器的多数值（或概率的平均值）。为估算 $S$ 中每个方案对的准确率，DroidFusion 使用每个方案对，对 $X$ 做重分类（reclassification）。

令 $\omega_i, i \in { 1, \ldots, Z }, Z \leq K$ 表示 $S$ 中某个方案的权重。那么，根据方案的标准，对实例 $x$ 进行重分类，其类预测值将由下式得出：
$$
C_{Sj}(x) =
\begin{cases}
\begin{array}{ll}
1: & if \dfrac{\sum_{i=1}^Z \omega_i v_i}{\sum_{i=1}^Z \omega_i} \geq 0.5 \
0: & otherwise \quad \forall j \in { 1, 2, 3, 4 }
\end{array}
\end{cases}
$$
如前所述，标签 $L = 1$ 表示恶意实例，$L = 0$ 表示良性实例，因此 $C_{Sj}$ 接近 1，则分类结果偏向恶意，否则偏向良性。作者这里选择了中间值 0.5 作为区分标准。

因此，对于给定方案的良性类分类准确率可由下式计算：
$$
P_{Sj}^{ben} = \frac{ \sum_{x = 1}^X (C_{Sj}(x) + 1) | C_{Sj}(x) = 0, l(x) = 0 }{B}
$$
分式的分子与 TP (True Positive) 的表示非常相似。$C_{Sj}(x) + 1$ 是因为 $x$ 为良性类元素时，$C_{Sj}(x) = 0$。

同理，对于给定方案的恶意类分类准确率可由下式计算：
$$
P_{Sj}^{mal} = \frac{ \sum_{x = 1}^X C_{Sj}(x) | C_{Sj}(x) = 1, l(x) = 1 }{X - B}
$$

由此，平均准确率可简单表示为
$$
\dot{P}{Sj} = \frac{ B \cdot P{Sj}^{ben} + (X - B) \cdot P_{Sj}^{mal} }{X}
$$

以上讨论的是某个方案的准确率计算。同样地，对于 $\phi$ 中的每个方案对，令 $\omega_i, i \in { 1, \ldots, Z }, Z \leq K$ 表示方案对的第一个方案的权重， $\mu_i, i \in { 1, \ldots, Z }, Z \leq K$ 表示方案对的第二个方案的权重，那么，根据方案对的标准，对实例 $x$ 进行重分类，其类预测值将由下式得出：
$$
C_{SjSn}(x) =
\begin{cases}
\begin{array}{ll}
1: & if \dfrac{ \sum_{i=1}^Z \omega_i v_i + \sum_{i=1}^Z \mu_i v_i }{\sum_{i=1}^Z \omega_i + \sum_{i=1}^Z \mu_i} \geq 0.5 \
0: & otherwise \quad \forall j \in { 1, 2, 3, 4 }, \forall n \in { 1, 2, 3, 4 } \
& j \neq n, SjSn \equiv SnSj
\end{array}
\end{cases}
$$

因此，对于给定方案对的良性类分类准确率可由下式计算：
$$
P_{SjSn}^{ben} = \frac{ \sum_{x = 1}^X (C_{SjSn}(x) + 1) | C_{SjSn}(x) = 0, l(x) = 0 }{B}
$$
同理，
$$
P_{SjSn}^{mal} = \frac{ \sum_{x = 1}^X C_{SjSn}(x) | C_{SjSn}(x) = 1, l(x) = 1 }{X - B}
$$
平均准确率可表示为：
$$
\dot{P}{SjSn} = \frac{ B \cdot P{SjSn}^{ben} + (X - B) \cdot P_{SjSn}^{mal} }{X}
$$
其中，$\forall j \in { 1, 2, 3, 4 }, \forall n \in { 1, 2, 3, 4 }, j \neq n, SjSn \equiv SnSj$ 。

与上同理，可得非加权方案的良性类分类准确率：
$$
P_{mv}^{ben} = \frac{ \sum_{x = 1}^X (C_{mv}(x) + 1) | C_{mv}(x) = 0, l(x) = 0 }{B}
$$
同理，
$$
P_{mv}^{mal} = \frac{ \sum_{x = 1}^X C_{mv}(x) | C_{mv}(x) = 1, l(x) = 1 }{X - B}
$$
平均准确率可表示为：
$$
\dot{P}{mv} = \frac{ B \cdot P{mv}^{ben} + (X - B) \cdot P_{mv}^{mal} }{X}
$$

在所有重分类完成、结果计算后，取得分最大的方案作为 DroidFusion 的模型构建方案：
$$
\begin{cases}
\begin{array}{l}
arg_{\phi}max(\dot{P}_{/phi}), \
\phi = { S1S2, S1S3, S1S4, S2S3, S2S4, S3S4, mv }
\end{array}
\end{cases}
$$

基于排序的算法

文章提出的算法设计受到了“大多数典型的分类器对两个类的表现出不同的观察效果”这一事实的影响。也就是说，良性分类器和恶意软件的分类精度性能很少有相同的情况。算法有以下4个：

• AAB (Average Accuracy-Based Ranking Scheme) 排序方案
• CDB (Class Differential-Based Ranking Scheme) 排序方案
• RAPC-based (Ranked Aggregate of Per Class Accuracies-Based) 排序方案
• RACD (Ranked Aggregate of Average Accuracy and Class Differential) 排序方案

AAB 排序方案

在 AAB 方案中，排序直接与各类的平均预测精度成正比。在这种情况下，总体准确率较高的基础分类器的排序会更靠前。AAB 不考虑基础分类器对某一个特定类的分类效果。令 AAB 为集合 $S$ 中的 $S1$ 方案，其算法总结如下。

令 $P_{base}$ 代表准确率的集合，$P_{k, c} \in P_{base}$， 其中 $k$ 为基础分类器，$c$ 为类别，$m$ 代表恶意类，$b$ 代表良性类。则第 $k$ 个基础分类器的平均准确率为：
$$
a_k = 0.5 \times \sum_{c=m,b} P_{k, c} | k \in { 1, \ldots, K }, 0 < P_{k, c} \leq 1
$$
令 $A \gets a_k, \forall k \in { 1, \ldots, K }$ 为平均准确率的集合，对其应用一个排序函数 $Rank_{desc}(.)$ ：
$$
\overline{A} \gets Rank_{desc}(A)
$$
因此，$\overline{A}$ 包含1层基础分类器的平均准确率，按降序排列。之后，对排序的前 $Z$ 个，进行了如下的权重分配：
$$
\omega_1=Z, \omega_2=Z-1, \ldots, \omega_Z=1, Z \leq K
$$

之后可计算实例 $x$ 应用 AAB 的 $C(x)$。

CDB 排序方案

在 CDB 方法中，排序与平均准确率成正比，与类之间性能差异的绝对值成反比。假设有一个二元分类问题，这种方法将较少倾向于在一个类中表现出比另一个类的准确度高得多的基础分类器，而会给在两个类中表现相对较好的分类器分配较大的权重。其算法总结如下。

令 CDB 为方案 $S2$，每个基础分类器的平均准确率为 $a_k$。定义 $\overline{D}$ 为一组降序排列。计算 $d_k$，使其与平均准确率成正比，与类之间性能差异的绝对值成反比：
$$
d_k = \frac{a_k}{|P_{k,m} - P_{k,b}|}, k \in { 1, \ldots, K }
$$
令 $D \gets d_k, \forall k \in { 1, \ldots, K }$ 为 $d_k$ 取值的集合。对其应用一个排序函数 $Rank_{desc}(.)$ ：
$$
\overline{D} \gets Rank_{desc}(D)
$$
权重分配方法与 AAB 排序方案相同。CDB 排序方案可设为 $S2$。

RAPC-based 排序方案

在 RAPC 方法中，排序是直接根据基础分类器的准确度在每个类中的排序之和来进行的。这种方法更倾向于将较大的权重分配给在两类中都有很好表现的基础分类器。其算法总结如下。

定义 $\overline{F}$ 为一组排列。给出 $K$ 个基础分类器的初始性能精度：
$$
\begin{cases}
\begin{array}{ll}
P_m \gets P_{k,c} & where \quad c \neq b \
P_b \gets P_{k,c} & where \quad c \neq m
\end{array}
\end{cases}
, \forall k \in { 1, \ldots, K }
$$
之后对它们应用排序函数 $Rank_{desc}(.)$ ：
$$
\begin{cases}
\begin{array}{l}
\overline{P}m \gets Rank{desc}(P_m) \
\overline{P}b \gets Rank{desc}(P_b)
\end{array}
\end{cases}
$$
对每个基础分类器的每个类的排序进行汇总，然后再次进行排序：
$$
\begin{cases}
\begin{array}{l}
f_k \gets \overline{P}{k,m} + \overline{P}{k,b} \
P_b \gets f_k
\end{array}
\end{cases}
, \forall k \in { 1, \ldots, K }
$$
$$
\overline{F} \gets Rank_{desc}(F)
$$

权重分配方法与 AAB 排序方案相同。RAPC-based 排序方案可设为 $S3$。

RACD 排序方案

在 RACD 中，分类器的排序直接设为平均性能精度的初始排序和类间性能差异的初始排序之和。这种方法的目的是将较大的权重分配给初始总精度较好的基础分类器，而且这些分类器在类之间的性能差异也相对较小。算法总结如下。

设 RACD 排序方案为 $S4$。定义 $\overline{H}$ 为一组基数为 $K$ 的排列。给定 $A$，计算出每个基础分类器的平均准确度（在 AAB 方案中给出），再计算出每个分类器的类间性能差异：
$$
g_k \gets | P_{k,cm} - P_{k,b} |, k \in { 1, \ldots, K }
$$
定义 $G \gets g_k, \forall k \in { 1, \ldots, K }$ 为 $g_k$ 的排列，对其应用一个升序排序函数 $Rank_{ascen}(.)$ ：
$$
\overline{G} \gets Rank_{ascen}(G)
$$

之后，对于每个基本分类器，汇总结果，并应用排序函数 $Rank_{ascen}(.)$ ：
$$
\begin{cases}
\begin{array}{l}
h_k \gets A_k + G_k \
H \gets h_k
\end{array}
\end{cases}
A_k \in \overline{A}, G_k \in \overline{G}, \forall k \in { 1, \ldots, K }
$$
$$
\overline{H} \gets Rank_{desc}(H)
$$
权重分配方法与 AAB 排序方案相同。

研究方法

用于特征提取的静态自动分析器

DroidFusion 系统的实验评估中使用的特征是通过使用 Python 开发的自动静态分析工具获得的。该工具可以在使用AXMLprinter2（一个用于反编译Android manifest文件的库）反编译后，从 APP 的 manifest 文件中提取权限和意图。此外，通过 Baksmali 反编译器对 .dex 文件进行逆向工程，提取API调用。静态分析器还可以从 APP 文件中搜索危险的 Linux 命令，并检查 APP 中是否存在内嵌的.dex、.jar、.so和.exe文件。之前有研究表明，这些静态应用属性集为基于机器学习的 Android 恶意软件检测提供了辨别特征，因此，文章将其用于 DroidFusion 的研究。此外，在提取API调用的同时，使用从其它文献获得的流行广告库列表排除了第三方库。下图显示了使用静态应用分析器的特征提取过程的概述。在所有的数据集中，特征提取过程以二进制形式表示，并以类值标注。

特征选择

特征排序和选择通常被应用于特征的降维，这反过来又降低了模型的计算成本。本文的研究使用了四个数据集来评估 DroidFusion 。其中一个数据集是通过应用信息增益（IG）特征排序方法对 350 个特征进行排序，然后选择最上面的 $n$ 个特征，将初始的350个特征缩减到100个。IG 通过计算每个特征所获得的 IG 来评估特征。对给定的特征 $X$，IG 定义如下：
$$
IG = E(X) - E(X/Y)
$$
其中，$E(X)$ 与 $E(X/Y)$ 表示特征 $X$ 在特征 $Y$ 纳入观察之前及之后的熵，可以由下式计算：
$$
E(X) = - \sum_{x \in X} p(x) \log_2 (p(x))
$$
$$
E(X/Y) = - \sum_{x \in X} p(x) \sum_{x \in X} p(x|y) \log_2 (p(x|y))
$$
其中，$p(x)$ 是随机变量 $X$ 的边际概率密度函数。$p(x|y)$ 是给定 $y$ 的 $x$ 的条件概率。特征 $X$的熵越大，其意义越大。

此外，在评估模型时，还参考了以下几个性能指标：

• TPR: $TPR = \frac{TP}{TP+FN}$
• FPR: $FPR = \frac{FP}{TN+FP}$
• Precision: $Precision = \frac{TP}{TP+FP}$
• F-Measure: $FM = \frac{2\cdot precision \cdot recall}{precision + recall}$
• 时间消耗