基于集成学习投票算法的Android恶意应用检测
2020-11-18赵宇鑫努尔布力
赵宇鑫，努尔布力，艾 壮
1.新疆大学 软件学院，乌鲁木齐830046
2.新疆大学 网络中心，乌鲁木齐830046
3.新疆大学 信息科学与工程学院，乌鲁木齐830046
1 引言
根据Gartner 公司的统计，截至2017 年，Android 智能手机操作系统的市场占有率已经达到85.9%。Android系统受到了市场的青睐，这与其开源的特性密不可分。随着基于Android系统二次开发的操作系统和手机数量的增长，Android平台逐渐成为攻击者的主要目标，系统自身和应用程序的安全问题变得越来越严重。爆炸式增长的应用市场的管理因此成为一种新兴的涉及恶意应用程序检测的关键问题。随着Android恶意应用检测技术的发展，越来越复杂的恶意应用逃避系统检测。因此，Android 应用程序市场的管理需要有效的方法来检测恶意程序。应用程序市场通常会根据应用程序开发人员指定的类别或通过分析应用程序开发人员提供的描述对应用程序进行分类。恶意应用的开发人员很容易操纵这个过程来逃避检测。并且随着应用数量的激增，快速准确地自动分类应用程序从而提高管理效率，变得至关重要。
在这种背景下，本文提出了一个新的模型，以便在检测恶意应用程序方面有效地管理应用商店中的大量应用程序。应用商店从每个APK（Android Application Package）文件中提取大量功能，并使用这些功能来表示应用程序的行为。一般来说，恶意应用的行为与良性应用程序的行为不同。例如，恶意应用程序可能会请求其功能上不需要的权限。某个类别中的良性应用程序的行为也与其他类别的行为区别开来。从所有的应用程序中，总共提取了2 374 348 个功能[1]，分为11 种类型。为了提高检测和分类的效率，使用SVM-RFE（Support Vector Machine Recursive Feature Elimination）根据功能对检测的重要性对其进行排名。然后，使用包括SVM（Support Vector Machine）、K-NN（K-Nearest Neighbor）、NB（Naïve Bayes）、CART（Classification and Regression Tree）和RF（Random Forest）在内的五个分类器的集合来检测恶意应用程序。在该模型框架的最终实验中，使用MASV检测方法实现了99.27%的检测精度。
2 基本概念及相关工作
2.1 定义
2.1.1 指示函数
Π(·)为指示函数，当·为真时输出1，为假时输出0。定义如下：
2.1.2 特征排序和排名标准
特征选择是通过穷举出所有的特征子集，选择满足给定“模型选择”标准的最佳特征子集。但由于子集的组合数量庞大，穷举出所有的特征子集不切实际，可以回归到一种实际可用的方法，首先将特征数量减少到可管理的大小，其中特征排序算法比较有竞争力，可实现。
特征排序算法顾名思义就是通过对每个特征依照某种标准进行评估，对每个特征进行打分或赋权值，选择出固定数量排名最高的特征进行下一步的分析或设计分类器。本文用到的SVM递归特征消除算法是依照敏感性分析对特征进行排名，具体原理如下。
OBD（Optimal Brain Damage）算法作者LeCun[2]提出使用成本函数DJ(x)代替权重作为修剪特征的标准：
对于线性判别函数J 与ωi的二次函数是等价的，最小值时可以表示为：
该公式进一步证明[3]可以使用(ωi)2作为排序标准。
2.1.3 梯度上升算法的目标函数和代价函数
梯度上升算法的目标函数为：
其中，θi(i=0,1,2,3,4,5)为梯度上升模型参数，也是该算法的输出；xi(i=1,2,3,4,5)为每个样本的基分类器输出的正确率值，增加一个特征x0=1。
代价函数J ：
其中，yj设为1，m 代表迭代次数，使得代价函数J 最大化，对应的θ 就是最优参数。
2.2 背景
计算机系统和网络的安全性是一个广泛讨论的主题，因为目前对系统或网络基础设施的攻击是主要威胁。现已提出了许多方法来确保系统安全[4-6]和网络安全[7-12]。
2.2.1 基于权限检测Android恶意应用程序
本文工作的动机是确保Android 应用程序的安全性。目前，检测Android 恶意应用程序的工作主要集中在静态特征的分析[13-19]或动态特征[20-22]的分析。由于Android权限限制API（Application Programming Interface）的调用，所请求的权限可以表现应用程序的部分行为。Pandita 团队[17]提出WHYPER，采用自然语言处理技术来解释为什么应用程序需要某些权限。在之前的调研工作中，Wang团队[23]根据风险对权限进行了排名，并系统地研究了Android权限在检测恶意应用程序方面的表现。Barrera 等人[24]调查了1 100 个最受欢迎的应用程序，发现这些应用程序只需要小部分权限，还发现应用类别和权限之间的关系不是非常密切。Chia 团队[25]和Felt 团队[26]研究列出了Android 应用中最常用的权限。Enck 等人[27]开发了一个工具，该工具通过将Android 应用程序请求的权限与预定义的权限列表进行匹配来检查应用程序是否是恶意的。Zhou 团队[28]提出了一种基于行为足迹的权限方案，用于检测已知Android 恶意软件家族的新样本，并应用基于启发式的过滤方案来识别未知恶意家族的某些固有行为。
2.2.2 基于API调用和功能检测Android恶意应用程序
Shabtai等人[29]研究静态分析技术来解析Android源代码，他们还应用机器学习技术，通过从Android应用程序中提取的静态功能对游戏和工具进行分类。La Polla等人[30]概述了移动设备安全方面的相关工作。Nath等人[31]比较了用于分析Android 恶意软件的各种机器学习技术。Lindorfer等人[32]介绍了MARVIN，这是一种利用机器学习技术以风险评分的形式评估未知Android应用程序的系统。Peiravian团队[33]通过权限和API调用来检测出恶意应用程序。Pirscoveanu 等人[34]开发了一个分布式Android 恶意软件测试环境。Amin 团队[35]调查了恶意应用的性质和身份，并提出了基于网络和系统调用的检测方法。Apvrille 等人[36]用Alligator 结合了几种分类算法，提取了代码级的功能，并对未知应用进行了分类。
目前的检测方法在某些方面存在不足。首先，所使用方法是基于应用程序的权限与应用的类型比较来判断该应用程序是否是恶意应用程序，不能应对新类型的Android应用程序，适应性较差且误报率较高。其次，仅使用基于机器学习单分类器的Android恶意应用检测虽然在检测速度上略有优势，但检测的正确率并不是很高。
2.3 基于应用程序功能的特征提取
本文根据Arp 等人[13]提出的Android 功能特征提取方法，对Android 应用程序进行静态分析。通过线性扫描应用程序的XML（eXtensible Markup Language）文件以及反编译的dex 代码提取有效特征。为了进行通用和可扩展的分析，将所有提取的功能表示为字符串集，例如权限、广播和API调用。提取以下11组字符串[1]。
2.3.1 程序清单中的功能集
为Android开发的每个应用程序都必须包含一个名为AndroidManifest.xml的清单文件，该清单文件提供支持该应用程序安装和执行的数据。使用Android Asset Packaging Tool可以在设备上有效地检索此文件中存储的信息，该工具能够提取以下数据集：
FS1 组件名称：大多数Android 恶意应用程序都是经过重新打包的合法应用程序[37]，攻击者将相同的恶意有效负载（通常在组件方面）插入到许多不同的合法应用程序中。将组件名称作为功能集包含在内，以捕获良性和恶意应用程序中出现的组件重用行为。
FS2 请求的权限以及FS3 硬件和软件要求：应用程序尝试访问哪些资源对于检测恶意软件非常重要。在Android系统中，请求的权限（FS2）以及硬件和软件要求（FS3）指示应用对系统资源的需求。权限请求模式可以表现应用程序的资源访问意图。在数据集中，使用了Android平台和第三方应用程序定义的所有权限。硬件和软件要求（FS3）是指Android应用程序使用
FS4 过滤后的广播：Android 平台将广播用作应用程序的消息传递对象，并且平台可以将其发送到另一个应用程序的组件以请求操作。恶意应用程序通常使用广播过滤器进行声明，以接收特定的系统事件（例如BOOT_COMPLETED）来激活恶意活动。在这项工作中，将样本清单文件中的所有广播过滤器提取为功能集。
2.3.2 反编译代码中的功能集
Android 应用程序是用Java 开发的，并被编译为Dalvik 虚拟机的优化字节码。该字节码可以有效地反汇编，并提供有关API调用和应用程序中使用的数据信息。使用基于Android 平台的dex 库的反编译程序，可以输出应用程序中包含的所有API调用和字符串。
FS5 受限的API 调用和FS6 使用的权限：请求权限并不意味着该应用程序实际上访问了相应的资源。扫描应用程序样本的反编译代码，并记录它们是否调用某些受保护的API。另外，使用PScout[39]提供的API 权限映射来获取使用的权限。使用的权限和受限制的API调用反映了应用程序实际在不同程度级别上访问的资源。
FS7证书信息：应用开发人员必须使用证书对自己的APK 文件签名，该证书的私钥由他们自己持有。该证书有助于将开发人员与其他开发人员区分开。可以从证书中提取开发人员信息，例如国家/地区、电子邮件地址、组织、州或省以及SHA-1指纹。
FS8源代码中的URL、IP地址、文件路径和数字：通过正则表达式模式匹配，收集了反编译代码中的所有URL、IP 地址、文件路径字符串和数字（三位数以上）作为功能集。这些字符串可能涉及许多恶意行为。
FS9 有效负载信息：有效负载指APK 存档中的文件。将有效负载信息作为功能集包含在内，是因为某些恶意应用程序在主机应用程序中包含额外的.apk文件，诱骗用户安装这些恶意.apk文件，并且恶意应用程序为了避免引起怀疑，可以将文件扩展名从.apk或.dex更改为.png。
FS10代码模式：在此功能集中，检查应用程序是否动态加载.dex 文件或Linux 本地代码，应用程序是否执行shell 命令，应用程序是否使用Java 反射机制以及应用程序是否调用密码功能等。
FS11 可疑的API 调用：受Drebin[13]的启发，提取了某些API 调用，这些API 调用允许访问敏感资源，例如访问设备ID，发送和接收恶意应用程序经常使用的SMS消息。
本文以Android 应用程序的功能为依据进行分类，借鉴机器学习中集成学习的方法，提出了MASV检测方法。由于Android 应用程序功能特征庞大，本文先使用SVM-RFE 算法对特征的重要性进行排序，去掉一些对训练模型不重要的特征。同时，针对集成学习加权投票的权重选择耗时较长的问题，使用梯度上升算法训练并得出每个基分类器的权重。MASV 检测方法集合了每个基分类算法的优点，提升了检测方法的适应性和准确率，同时减少了集成学习模型的训练时间，提高了效率。
3 MASV集成方法
3.1 综述
本文提出了一个模型框架MASV来过滤大量Android应用程序，从而检测恶意应用程序。如图1 所示，在将应用程序输入模型后，从APK 文件中提取大量功能特征。如果通过MASV将其识别为恶意应用，则会触发警报。具体步骤如下：
步骤1 将待检测的Android 应用程序功能特征使用SVM-RFE 算法进行重要性排名，淘汰不重要的样本特征。
步骤2 将选择后的特征矩阵输入五个基分类器。
步骤3 根据五个基分类器的预测结果输入到训练好的集成学习加权投票分类器中，得出分类结果。
步骤4 根据分类结果判定该Android 应用程序的性质，结束。
3.2 基于SVM-RFE的特征选择
在检测恶意应用程序时，提取和选择功能始终很重要。在这项工作中，通过静态分析技术从应用程序中提取静态特征。静态分析技术是指分析代码特征，例如语法、词典、数据流和控制流。与在应用程序运行时从系统中提取功能的动态分析相比，应用静态分析会消耗更少的资源和时间，并且不需要执行应用程序。由于有大量的应用程序集，因此更专注于静态分析以确保检测效率。
通过静态分析，从所有应用程序中提取2 374 340个功能，具体数量如表1所示。由于功能的数量太大而无法有效处理，本文使用SVM-RFE 算法根据其对检测的重要性对每个特征的权重进行排序。SVM-RFE算法[3]的过程如下：
表1 功能集（特征选择前）
（1）训练分类器（优化权重ωi以使得J 最优）；
（2）计算所有特征的排序标准(DJ(i)或(ωi)2)；
（3）删除具有最小排序评分的功能。
该迭代循环是消除排名最差的一个过程。出于计算效率的原因，一次删除多个功能特征可能更为有效，但会降低分类器的评分结果。在这种情况下，该方法产生与特征排名相反的特征子集。
如果一次删除一项功能特征，会有一个相应的功能排名。但排名最高（最后淘汰）的功能不一定是最重要的特征，因为一些功能特征可以和其他互补功能特征很好地区分数据。
通常，SVM-RFE采用的是线性核函数，推广到多维特征向量的应用场景，需要采用非线性核函数。本实验采用的是RBF核函数。
SVM-RFE（RBF核）算法描述如下所示：
进而将线性SVM应用于恶意应用程序检测并实现SVM 模型，其中每个特征的标签由其在区分良性应用和恶意应用方面的有效性决定。权重为正的特征被视为“恶意特征”，而权重为负特征被视为“良性特征”。一些权重等于0，表明它们对分类没有贡献，因此可以在分析中删除。如图2 所示，实验测试了1 000～46 000 个特征每隔3 000特征的ACC值，发现当特征数量为34 000个时，ACC值最高。最后使用34 630个功能，用于执行恶意应用和良性应用程序的分类。经过特征选择后的特征指标如表2所示。
图1 MASV集成框架
图2 各特征数的ACC值
表2 功能集（特征选择后）
3.3 基于分类器的检测
MASV检测方法使用了五种基分类器，五种分类器的原理及优缺点如表3所示。
3.4 基于集成学习的加权投票算法
为了发挥每种算法的优势并进一步提高检测和分类的准确性，通过五种分类算法的对比，在获得上述五种算法的分类结果后，采用多分类器的集合进行多数表决。软投票，即一种加权投票法，其做法就是以每个基分类器测试结果的正确率为权重，对每个类进行加权平均，取得分最高的类别作为分类结果。
加权投票算法如下所示。
对于训练样本D，其中x 为训练样本值，在本文中就是Android应用程序功能特征值，y 为样本x 所对应的标记。基学习器L1,L2,…,L5在本文中实际有五种，也就是五种基分类器（SVM，RF，NB，K-NN，CART）。ht表示基学习器Lt在样本x 上的输出。输出结果为标记空间C 中的一个值，本文为二分类问题，只有两个值，正例标记为-1，反例标记为+1。其中Π(·)为指示函数，详见第2.1.1小节。加权投票法的输出为：
3.5 基于梯度上升的权重选择
梯度上升是一个用来求目标函数最大值的算法，最优的路线是沿着该函数的梯度方向探寻。传统集成学习加权投票法首先对每个基分类器测试结果的正确率进行计算，然后以正确率作为权重，对每个类概率进行加权平均，得分最高的类作为分类结果。本文对此权重选择方法进行了改进，使用各基分类器10 次交叉验证的正确率（ACC）结果组成训练集，将其作为梯度上升算法的输入，将步长α 设置为0.001，可以快速得到各基分类器加权投票的权重。
表3 五种分类算法对比
本文使用梯度上升算法来求出集成学习加权投票的权重，目标函数hθ和代价函数J ，详见第2.1.3 小节。使代价函数J 最大化，对应的θ 就是最优参数。
θi的更新公式如下：
其中，α 为步长。
梯度上升的伪代码如下所示：
输入：多分类器输出结果集D={(x1,y1),(x2,y2),…,(xm,ym)}
1. 初始化所有θ=1,α=0.001,y=1
2. for 1,2,…,m do
6. end for
输出：θi
4 实验评估
4.1 实验环境和应用程序集
在实验过程中，实验环境使用Windows 系统，具有四核的Xeon CPU和64 GB内存的服务器。使用Python编写的scikit-learn 软件包作为实验中的机器学习工具包，因为它可以在各种环境中访问和重用，且配置简便。
本文使用由良性应用程序和恶意应用程序组成的大型应用程序集来验证本文提出的MASV 方法。应用程序数据来自北京交通大学Wang团队[1]所整理收集的2014 年和2015 年的Android 应用功能集。该数据集总共231 619个应用程序，包括213 256个良性应用程序和18 363个恶意应用程序。使用VirusTotal标记良性应用程序，如果VirusTotal 中的防病毒引擎不足以将该应用视为恶意应用，会将其视为良性应用。数据预处理中将App 样本转换为LIBSVM 格式，每行描述一个App 样本，第一列表示分类标签，其余列表示功能特征。本实验使用欠采样，去掉部分良性样本，使得恶意样本和良性样本数量平衡，最终使用的数据集良性样本和恶意样本数量如表4 所示。分层选择80%的样本作为训练数据，其余20%的样品作为测试数据。根据应用市场的分类，目前获取的APK数量如表5所示。
表4 实验数据集切分
表5 应用程序数据集分类描述
4.2 实验设计
首先，本文实验将数据集的80%作为训练集，20%作为测试集，再将训练集分为训练集和验证集，采用十折交叉验证的方法对分类器进行训练，这样做是为了对模型参数调优。其次，为了提高SVM分类器的效率，本文使用SVM-RFE算法对数据特征的重要性进行了全局排名。然后，使用梯度上升算法，将五个基分类器的输出结果的准确率作为梯度上升算法的输入，对集成学习加权投票的参数ω 进行预估。最后，通过加权投票算法训练模型，使用测试集得出预测值。
本文的实验方法较Wang团队[40]提出的检测方法有所不同。首先，本文使用的集成学习投票方法是加权投票方式，较多数投票方式在准确率上有所提高。其次，本文率先使用了梯度上升算法确定每个分类器的权重，原理是基于训练时的准确率求最优解问题。为了检验MASV的检测效果，本文使用五种基分类器作为对比实验进行分析，并和同样使用应用程序功能特征作为研究对象的几种方法进行了比较。
4.3 评价指标
在本文的实验中，分类器结果的评估通过表6混淆矩阵中的各项数值，分别计算出准确率（ACC）、正确率（PRE）、召回率（REC）以及F1值（F1-score），计算公式如下：
表6 分类结果混淆矩阵
4.4 模型训练参数
对于SVM 分类器的评估实验，在所有实验中选择线性核函数。参数ωi，即每个类别的权重，被指定为与每个类别中的样本数成反比。另一个参数c，错误惩罚参数，设置为0.25。
特征的数量是CART的重要参数，将此参数设置为默认值，因为使用默认值时精度最佳。在设置决策树深度这一参数时，对决策树深度取100～1 200 分别进行了对比实验，如图3所示，结果在TreeDepth=1 000 时正确率最高，ACC=96.89%。
图3 CART的树深度参数比较
将K=3 设为K-近邻的参数。如图4 所示，ACC、PRE、F1-score 的数值都随K 值的增加而递减，只有REC 值随K 值的增加而增加，但K 为3～15 时的REC值变化不大，取K=3 使得K-NN的正确率、准确率、F1值都获得一个较为不错的结果。
图4 K-NN的K 值参数比较
决策树的数量是RF 的一个重要参数，因为在寻找最佳分割时需要考虑这些参数。通过几次实验来平衡效率和准确性，并将决策树的数量设置为100，如图5、图6 所示。对于朴素贝叶斯分类算法，在实验中选择MultinomialNB模型。
图5 RandomForest的决策树数量参数比较
图6 RandomForest的决策树数量参数比较
集成学习投票算法SVM、RF、NB、K-NN 和CART分类器的权重为ω1,ω2,ω3,ω4,ω5,使用本文提到的梯度上升算法得到的结果分别为0.772，0.157，0.001，0.044，0.027。
4.5 实验结果与分析
五种分类器和集成学习方法的恶意应用程序检测结果如表7所示。可以看出，SVM分类器的准确率ACC在五个基分类器中是最高的，达到98.93%。评估结果表明，除NB算法外，各算法的检测准确率非常相似。从表7 还可以看出，SVM 算法和RF 算法的检测结果非常接近。一般来说，RF 算法的实验检测结果优于CART算法，因为RF 算法也是一种基于决策树的集成学习方法，实验结果也证明了这一结论。NB 分类算法准确率最低，只有61.63%，正确率PRE 仅有61.99%，这也说明贝叶斯模型不适合分类Android应用程序功能特征。
表7 各分类器实验结果 %
采用具有软投票机制的五种分类器集合后，本文的MASV 方法在检测恶意应用程序方面达到了99.27%的准确率。通常，本文的集成方法优于基本分类器SVM、RF、NB、K-NN和CART。
4.6 与其他方法比较
表8所示是Drebin、LR（Logistic Regression）、Droid-Ensemble 和本文方法的对比结果。通过和同样使用应用程序功能数据集的其他方法比较，可以看出MASV方法在TPR（True Positive Rate）上有较大优势，但本实验结果的FPR（False Positive Rate）略低于其他方法，如图7、图8所示。可以得出，本实验检测良性样本的正确率较为有效，因为本文恶意样本数量多于其他方法，所以FPR 略有偏高，但不明显。综上所述，本文这种集成学习加权投票算法的检测效果优于Drebin[13]使用的SVM方法、Wang 团队[1]使用的LR 方法和使用多数投票的DroidEnsemble[40]方法。
表8 MASV与其他方法比较
图7 检测方法的TPR比较
图8 检测方法的FPR比较
5 结束语
本文提出了一个检测恶意应用程序的模型框架，将恶意应用程序用于五个分类器的集合模型分类，旨在简化Android 应用程序市场的管理。给定一个应用程序，本文的模型框架从应用程序中提取大量功能，然后使用这些功能来检测它是否是恶意的。如果被识别为恶意应用程序，则会触发警报。否则，它将被归类为良性应用程序类别。本文采用五个分类器的集合，即SVM、K-NN、NB、CART和RF，集成学习软投票算法用于检测恶意应用程序和良性应用程序的分类。实验结果表明，MASV 在检测和分类方面比五个基本分类器更稳健。在恶意应用程序检测实验中，本文的集成方法实现了99.27%的检测精度。
在未来的工作中，计划探索更多信息功能，以更好地体现应用程序的行为，提高恶意应用程序和良性应用程序的分类效果。目前，还在研究设计更有效的方法以针对恶意应用进行分类，以及使用分布式计算减少模型训练时间。
