基于kNN算法和K—means算法的Android恶意软件检测
2016-06-30潘夏福
潘夏福
摘要：目前针对Android恶意应用可以采用静态或者动态分析的方法获取软件的特征，并根据这些特征采用特定的算法进行检测，但单一的分析方法无法充分体现Android应用的多样性。该文首次提出一种分析Android应用权限、调用和动作等特征，使用kNN分类算法识别正常应用和恶意应用。同时为了提高分类的正确性，该文还采用了K-means算法对训练类进行初始化。实验表明本文算法能够充分利用Android多样的特征有效检测恶意应用，并且与相关工作对比，算法在检测效率和执行效率上表现更好。
关键词：kNN；K-means；Android；恶意软件检测
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）14-0216-03
Detection of Android Malware Base on kNN Algorithm and K-means Algorithm
PAN Xia-fu
（Public Safety Technology Department of Hainan Vocational College of Political Science and Law， Haikou 571100， China）
Abstract： Currently， static analysis and dynamic analysis method is aways used to get Android applications features， according to these features， particular algorithm can detect unknow malicious applications of Android. But single analysis algorithm could not play the role of multi-class Android features. So this paper presents a new algorithm which analysis Android features， suach as permission， function calls and system behavior. The algorithm can distinguish malwares from normal ones by using kNN classificaiton. For improving the correct rate of classification， the algortithm also uses K-means method to initialize the training classifictaion. The experimental results show that the algorithm plays the role of malware dectection by using multi-class Android features， and it performs better than other realted algorithm on the efficiency and accuracy.
Key words： kNN； K-means； Android； malware detection
Android系统是Google公司开发的一款开放发式系统，任何手机厂商都可以对其进行定制，开放的特性使得Android系统占智能手机平台的主导地位，拥有整个市场的大部分份额。但由于Android系统的开放性，它也成为众多黑客、恶意开发者攻击的对象。特别是现阶段我国Android的第三方市场很多，这些市场允许用户自己上传自己的应用代码，但是市场的审核功能极其不完善，许多恶意软件流行其中。
手机恶意软件的危害主要有恶意扣费、窃取账号密码等用户隐私、破坏系统等，其中窃取隐私行为占大多数，一旦有恶意的人获取这些隐私信息，他可以对用户进行诈骗，危害非常大，甚至对国家安全都会造成影响[1]。
另外由于恶意代码使用的技术不断更新，Android系统的恶意软件监测变得越来越困难，Android上的应用在被监测出来之前，已经被用户大量下载了。对Android恶意软件检测十分有必要。但是由于手机内存、运行速度、电池耗电量的限制，Android恶意软件检测在手机上的分析效果不是很理想。因此对Android系统的恶意软件进行高效的检测十分必要。
1 相关工作
Android恶意软件检测目前主要采用静态分析和动态分析两种技术。静态分析技术主要采用分析Android软件的源代码或者二进制代码，找出可疑行为，通过分析Android权限和调用函数等内容，根据特定模型，判定是否为恶意软件。权限分析主要针对AndroidManifest.xml文件进行自动化分析，提取permission、activity、service、receive和provider组件进行特征提取，然后根据特定的类别进行设置[2]。而调用函数分析则通过Android平台的虚拟机Dalvik指令特点，定义形式化描述语言，描述恶意软件[3， 8]，或者通过native代码使用lib库文件进行分析，提取函数调用序列，完成软件判定[4， 9]。静态恶意代码检测优点是覆盖率高，缺点是无法检测代码混淆、加密，而且无法分辨发短信等在动态执行中才可以判定的恶意行为。
动态分析技术主要采用沙盒技术，通过模拟应用软件的操作过程，自动完成软件的安装，用户操作，用户卸载等操作实现恶意软件判定。动态分析可以分享Android系统的系统调用频率数，根据一些特殊调用在系统恶意代码执行时出现波动的现象进行恶意软件判定，另外还可以使用mokeyrunner等工具模拟用户行为，点击应用程序，模拟运行，根据模拟数据建立用户活动模型，实现恶意行为判定[5， 7]。但是这种检测方法工作量大，分析时间长，在手机上运行实时性不高，资源消耗过大。
另外为了提高分析的准确性，还有作者提出来基于静态分析和动态分析相结合的多类特征恶意行为检测系统THEA[7]，或者基于权限类别的恶意检测程序[2]。但这些程序对恶意程序检测存在着各种问题，因此本文提出基于kNN算法的Android恶意软件监测算法。
2 特征代码提取
特征代码采用静态与动态分析相结合的方式，选取权限、系统函数调用作为特征代码。使用Android SDK自带的AAPT打包工具，对APK进行解压，提取AndroidManifest.xml文件和lib库文件（.so文件）。根据AndroidManifest.xml的内容生成特征代码向量P，其中P={permission， activity， service， receiver， provider}。对.so文件进行合并后，提取动态符号表中的函数信息，对数据应用程序进行统计，提取最能描述系统功能的函数生成向量L，其中L={open， icocl， read， write， sendmsg， recvfrom， recvmsg， access， chmod， chown}。
动态分析通过模拟器调用APK文件，模拟打电话、发短信等操作，然后使用trace和wireshark工具动态检测系统调用日志、系统API和网络数据，并使用mokeyrunner工具模拟用户行为，获取用户行为数据，生成向量U，其中U={trace， wireshark， mokeyrunner}。
特征码向量采用这几个数据构成，M={P， L， U}T。向量相异度采用欧几里得距离，向量X与Y之间的相异度：
3 相关算法实现
3.1 kNN算法简介
kNN算法又被称为k近邻分类（k-nearest neighbor classification）算法，就是在测试组中找和训练元组向量空间上最接近的k个点中，类别最多的那个分类。由于向量组中部分值由于取值范围大，对距离的影响高，不利于反映真实的相异度，需对属性值进行规格化，将各个属性按比例均映射到[0， 1]区间，以平衡各个属性对距离的影响，映射公式为：
这里Xi为向量X的第i个分量。
Android程序被分为2种，正常应用和恶意应用，根据分组，计算Android程序类别，分类结果离待测向量最近的为其所属类别。
在试验过程中，发现恶意程序应用判定中权限向量P和用户行为向量U在恶意程序中异常情况比较突出，而系统功能函数往往只是调用一两次，对异常情况判定影响较小，可以对这种情况设置不同的权值，增加判定的准确率。向量X的属性可以设置为：
3.2 基于k-means算法的改进
基于kNN算法的Android恶意软件监测实现比较简单，是数据挖掘分类技术中的最简单方法，比较适合对稀有事物进行分类。但是算法如果样本不平衡时，比如现阶段恶意软件数目较少，正常软件类数目较大，导致正常软件样本占大多数，有可能k个邻居中占有概率大，造成无论怎样，目标软件都判定为正常软件。
因此可以对恶意软件类和正常软件类进行初始化数据处理，通过K-means算法分别计算出分类的N个质心。K-means算法是一种非监督实时算法，可以在最新误差函数的基础上将数据划分为预定的类数。通过指定聚类数目N和迭代次数或收敛条件，根据一定的相似性原则，分配相似的质心，形成类，然后以每一类的平均矢量作为新的质心，反复迭代直至收敛或者达到最大迭代数目。
K-means的质心可以采用下面的公式计算：
（4）
其中Kj为软件训练类的质心，Vi为训练软件特征向量，
K-means算法的收敛条件可以设置一个阈值
其中D为误差方差，公式如下：
K-means算法描述如下：
步骤1：选择误差门限
步骤2：初始化质心
步骤3：
步骤4：使用公式（4）（5）计算
步骤5：根据公式（6）（7）计算
步骤6：结束。
3.3 kNN算法描述
在对Android恶意软件判定之前，首先对恶意软件和正常软件的训练集进行K-means初始化，获得这两个集合的质心向量组，作为检测程序的样本向量，根据这些样本向量，运行Android恶意检测算法，算法描述如下：
步骤1：获取Android程序的特征代码P，L，U；
步骤2：根据公式（2）（3）计算特征向量M；
步骤3：根据公式（1）计算特征向量M与正常应用和恶意应用组的相异度；
步骤4：按照相异度进行递增排序；
步骤5：选取最近的k个特征向量；
步骤6：统计这k个特征向量在正常应用和恶意应用的数目，返回最多的一个；
步骤7：根据返回值判定结果。
4 实验分析
为了评估算法的有效性，本文将算法与近年来的相关工作进行对比，使用相同的测试样本进行判断分析。样例主要是从Google Play或者国内的第三方Android市场上下载，一共1798个恶意软件，3021个正常软件，对比结果如下：
从对比表中可以看出，本文算法比单纯的静态或动态检测的方法判定率都高，但是在恶意软件判定率方面比Androdect算法差，有待提高。本文算法实现简单，对系统资源耗费更少，更适合在有限资源的移动系统中实现。实验表明本文算法比Androdect算法更容易在Android系统中实现。
5 总结
本文采用了静态和动态结合的技术获取Android应用程序的特征向量，并在此基础上设计了kNN分类算法和K-means聚类算法相结合恶意软件检测模型，并实现了恶意检测算法。该算法弥补了单纯静态或单纯动态监测的不足，在对大量程序的测试中，算法表现良好。实验结果表明算法的准确率和执行效率上表现良好，优于大部分恶意代码检测工具。下一步将kNN分类算法和K-means聚类算法结合到云计算上面，进一步完善算法，并对恶意软件库进行云存储，提高系统的运行速度和判定准确率。
参考文献：
[1] 边悦，戴航，慕德俊. Android恶意软件特征研究[J]. 计算机技术与发展， 2014， 24（11）：178-181.
[2] 杨欢， 张玉清， 胡予濮，等. 基于权限频繁模式挖掘算法的Android恶意应用检测方法[J]. 通信学报， 2013， 34（Z1）：106-115.
[3] 李挺， 董航， 袁春阳，等. 基于Dalvik指令的Android恶意代码特征描述及验证[J]. 计算机研究与发展， 2014， 51（7）：1458-1466.
[4] 雷灵光， 荆继武， 王跃武，等. 一种基于行为的Android系统资源访问控制方案[J]. 计算机研究与发展， 2014， 51（5）：1028-1038.
[5] 蔡志标，彭新光. 基于系统调用的Android恶意软件监测[J]. 计算机工程与设计， 2013， 34（11）：3757-3761.
[6] 杨欢， 张玉清， 胡予濮，等. 基于多类特征Android应用恶意行为检测系统[J]. 计算机学报， 2014， 37（1）：15-25.
[7] S. Asaf， K. Uri， E. Yuval， et al. Andromaly： A behavioral malware detection framework for Android devices[J]. Journal of Intelligent Information Systems. 2012， 38（1）：161-190.
[8] Wu Dong-Jie， Mao Ching-hao， Wei Te-En， et al. DroidMat： Android malware detection through manifest and API calls tracing// Proceedings of the Seventh Asia Joint Conference on Information Security（ AsiaJCIS 2012）. Tokyo Japan， 2012： 62-69.
[9]Schmidt Aubrey-Derrick， Bye Rainer， Schmidt Hans-Gunther， et al. Static analysis of executables for collaborative malware detection on Android//Proceeding of the 2009 IEEE international conference on Communications（ ICC 09 ）. Dresden， Germany， 2009： 631-635.
