基于SimHash算法的Android恶意程序检测

李红灵，詹 翊

(1.云南大学 信息学院 计算机科学与工程系，云南 昆明 650091; 2.云南省信息安全测评中心，云南 昆明 650000)

基于SimHash算法的Android恶意程序检测

李红灵1，詹 翊2

(1.云南大学 信息学院 计算机科学与工程系，云南 昆明 650091; 2.云南省信息安全测评中心，云南 昆明 650000)

针对当前Android应用程序良莠不齐，存在大量的恶意程序对个人隐私和信息安全构成严重威胁的现状，在分析基于MD5的传统特征代码检测技术的基础上，提出了利用SimHash算法，经过APK文件特征文本提取，特征文本数字指纹生成，数字指纹比对及比对结果分析三个步骤，进行Android恶意程序检测的新方法。为实现APK文件特征文本化，引入恶意软件分析程序androlyze.py，同时，考虑到Android特征的有效性，经研究需要选取Android程序的权限及调用映射、广播接收器、服务等核心信息组合成对应APK文件的复合特征文本，将复合特征文本转换为字符串后利用程序进行海明距离计算，由海明距离判断待测试APK文件的安全性。通过实验进行实例分析，并将得到的检测效果与360杀毒软件做比较，发现基于SimHash算法的恶意程序检测方法，检测率高于360，可以作为Android恶意软件检测的一种有效方法。

SimHash算法；Android恶意程序检测；复合特征文本；相似性比较

0 引 言

如今Android应用市场由于缺乏统一的APK程序安全检测与审查制度，Android应用程序良莠不齐，其中大量的恶意程序对个人隐私和信息安全构成了严重威胁。因此，加强对Android恶意程序的检测与分析研究十分必要。

国外对Android恶意程序检测等方面的研究成果显著，David Barrera等[1]对Google应用市场中1 100个应用类型的应用程序的AndroidManifest.xml文件进行分析，并利用Self-Organizing Maps (SOM)算法将这些数据组织成二维授权图，可以直观清晰地看出这些应用程序申请的权限名称、类型。Gianluca Dini等[2]提出了针对Android恶意软件的多级异常检测方法(Multi-level Anomaly Detector for Android Malware，MADAM)，该方法同时监视Android的内核级和用户级，使用机器学习技术来区分正常行为和恶意行为。W.Enck等[3]提出了一种基于应用程序权限请求的轻量级的不安全应用程序识别方法，并开发了一个轻量级的Android应用安全认证系统Kirin。Justin Sahs等[4]提出了一种用机器学习来检测Android恶意软件的方法，通过开源项目Androguard从Android应用程序包APK中提取特征，采用支持LIBSVM接口的Scikit-learn框架提供的二分类支持向量机训练这些特征并生成一个分类器，用来分类Android软件。而在国内，魏松杰等[5]通过静态分析提取了APK文件中API在应用包、对象类、类函数层面的调用信息，并以树形方式进行描述，归纳了应用程序描述树的特征。

在对上述各种方法进行学习研究以及对传统的特征码比对方法进行分析的基础上，提出将相似性哈希算法SimHash灵活运用到Android恶意程序检测，设计并开发了基于SimHash算法的Android恶意应用检测程序，并对其进行了实验验证。

1 恶意程序特征码检测方法

恶意程序特征码检测主要采用的方法是基于已有的特征信息，对程序进行特征码提取和特征模式匹配，以此判定是否为恶意程序[6]。

1.1传统的特征码比对方法

基于特征码的检测方法可归纳为模式的提取和匹配，特征码就是提取出的恶意代码的特征模式，而恶意代码的扫描过程就是特征模式匹配的过程，即特征码比对。

传统的特征代码检测主要基于MD5计算，即先计算程序的MD5值，如果此值与已有的某个恶意程序的MD5值相同，则认为该程序具备恶意程序的特征[7-8]。优点是能在恶意程序首次运行前比对，对单一程序而言，检测速度快，准确度高，对已知恶意代码十分有效。但是也存在一些难以解决的问题。比如，其对恶意代码的分析完全依赖于特征库，使其无法处理未知和变形的恶意代码。当前，很多恶意程序的变种，行为非常相似，但签名却不同，这导致此类检测方法不能抵抗压缩、混淆、加壳等攻击。另外，要分析未知或变种恶意代码的特征码，必须逐一提取其特征码并加入特征库，否则无法进行匹配。若恶意程序变种数量巨大，需要创建大量的签名添加到签名库，这会大大增加恶意软件特征比对时间，占用过多系统资源，最终导致特征库爆炸。

针对上述问题，提出基于SimHash算法的特征码比对方法。

1.2基于SimHash算法的特征码比对方法

SimHash算法设计的初衷是为了解决海量数据的重复检测问题，主要思想是降维，将高维的特征向量映射成一个f-bit的指纹(fingerprint)，通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似[9]。由于SimHash算法是局部敏感哈希算法，局部的变化对整体影响不大，所以可将需检测的文本通过SimHash算法，降维成固定长度的二进制序列，并将这些二进制序列作为文本信息的数字指纹，通过比较文本信息的数字指纹来判断文本信息是否重复或者高度近似。

针对Android恶意程序的检测，运用SimHash算法进行特征码比对，需要经过三个步骤。首先，将APK文件转化为文本文件；其次，对文本文件生成其对应的数字指纹；最后，对其数字指纹进行信息比对分析。经过上述三个步骤的分析和处理，最终判别Android程序的安全性。

2 基于SimHash算法的Android恶意程序检测

2.1SimHash算法思想

SimHash是局部敏感哈希的一种，最早由Moses Charikar[10]提出，但是并没有给出具体的SimHash算法和证明。SimHash算法广泛用于信息检索领域，如Google就基于此算法实现了网页文件重复检测。

通过降维，将高维的特征向量映射成一个低维的特征向量，通过两个向量的海明距离来确定两个文件的相似度[11]。在信息编码中，两个合法代码对应位上编码不同的位数称为码距，又称海明距离。Simhash算法的实现过程分为5步：分词、hash、加权、合并、降维。详细过程如图1所示。

图1 SimHash算法示意

2.2SimHash算法描述

SimHash算法的输入为一个N维向量V，每个特征具有一定权重。输出是一个C位的二进制签名S。具体步骤如下[12]：

(1)初始化一个C维向量Q(为0)，C位的二进制签名S为0。

(2)对V中的每一个特征，使用传统的Hash算法计算出一个C位0、1组成的散列值H。对1≤i≤C，如果H的第i位为1，则Q的第i个元素加上该特征的权重；否则，Q的第i个元素减去该特征的权重。

(3)如果Q的第i个元素大于0，则S的第i位为1，否则为0。

(4)返回二进制签名S。

2.3字符串测试

假设S1,S2为2个字符串，其中：

S1=“computers-work androi-malware permission function(x)”

S2=“computers-home androi-malware permission function(y)”

采用MD5进行计算，结果如下：

S1的MD5值为：

63bf17b026ff5081db6422fcb3 fbb51c

S2的MD5值为：

f74d55b317c1a023349e6e5fb 33fe33c

由此可见，尽管S1与S2内容相差不大，但采用MD5计算后其结果差异很大。

另外，采用SimHash进行计算，程序输出如图2所示。

图2 字符串S1与S2的Binary Hash值

最后进行字符串相似度计算：

S1的SimHash值为：

1000000000100101100001100 0000101

S2的SimHash值为：

1000000000000110100001001 0000100

S1、S2经过异或运算XOR后，共有六位不同，即：第1、8、10、17、18、22位，不同位数所占比例为6/32，等于0.187 5，那么其相同位数所占比例为26/32，等于0.812 5，即81.25%。

于是可以得出结论：字符串S1与S2的相似度为81.25%。

3 Android程序复合特征码提取

3.1恶意代码特征定义

恶意代码的特征，简称特征码，即是指其所特有的、非恶意代码所没有的特征。也就是从恶意代码体内不同的位置提取的一系列字节，这些字节和恶意代码有唯一的关联性。特征码一般包括行为特征和状态特征。行为特征包括API调用函数、访问网络资源(创建SOCKETS，发起连接TCP、UDP、DNS)、修改系统服务等行为。状态特征包括程序的文件信息(程序大小、MD5值)、程序代码段、程序操作的连贯顺序等。

3.2Android程序复合特征

由特征码定义可知，程序的代码段、网络访问等都可以作为特征，就Android程序而言，权限、广播接收器、服务都可以作为特征，考虑到单一特征存在的局限性，不能全面地概括应用程序特性。因此，可以把Android程序的权限、广播接收器、服务等信息组合起来构成复合特征，这样才可以全面精准地反映Android程序的特性。另外，可以通过开源恶意软件分析包Androguard中的androlyze.py工具分别导出APK文件的权限及调用映射、广播接收器、服务等信息，将其组合成该APK文件对应的复合特征文本。

3.3Android程序权限及调用映射提取

使用Androlyze.py-s命令进入Androlyze的Shell交互环境，通过a，d，dx=AnalyzeAPK(“./Android4-4.apk”，decompiler=“dad”)命令分别实现了建立的apk、dex文件对象的提取，DalvikVMFormat()调用的功能。

使用命令：show_Permissions(dx)可以提取Android程序权限及其调用映射，详见图3。

3.4Android程序广播接收器提取

通过命令a.get_receivers()实现APK文件的广播接收器提取(详细信息略)。

3.5Android程序服务提取

通过命令a.get_services()实现APK文件的服务提取(详细信息略)。

4 基于SimHash算法的Android程序检测实例

4.1待测APK文件描述

待测试应用程序为Android4-4.apk、Android4-5.apk、cutepuppies.apk。其中，Android4-4.apk是远程控制木马程序，Android4-5.apk是Android4-4.apk的升级版，而cutepuppies.apk为C&C类型恶意程序。

4.2APK文件特征文本

Android4-4.apk特征文本如图4所示。由于篇幅有限，在此就不再给出其升级版Android4-5.apk和cutepuppies.apk的特征文本。

图3 Android程序权限及调用映射

图4 Android4-4.apk特征文本

4.3计算结果分析

将特征文本转换为字符串后进行SimHash计算，其结果如图5所示。

图5 SimHash算法的输出结果

计算结果分析：

cutepuppies.apk和Android4-4.apk的海明距离为14。

cutepuppies.apk和Android4-5.apk的海明距离为14。

Android4-4.apk和Android4-5.apk的海明距离为2。

因为是64 bit hash值，故其相似度为：

cutepuppies.apk和Android4-4.apk：50/64，等于78.125%。

cutepuppies.apk和Android4-5.apk：50/64，等于78.125%。

Android4-4.apk和Android4-5.apk：62/64，等于96.875%。

4.4检测效果比较

Gurmeet Singh Manku等[13]对SimHash算法效果进行了测试，发现对于64位的SimHash值，当海明距离为3时，召回率和准确率都比较高，约为75%。因此，海明距离小于3都可以认为是相似的。

实验测试发现SimHash比较适用于大文本，500字以上效果都不错，经初步统计Android恶意程序复合特征文本字数在600～3 000字区间范围，可适用于SimHash算法进行检测。通过对CutePuppiesWallpaper.apk、Android4-4.apk等5款恶意程序进行检测，并与360杀毒软件做比较，发现基于SimHash算法的恶意程序检测方法效果显著，检测率高于360杀毒软件。

5 结束语

针对当前Android应用程序良莠不齐，大量的恶意程序对个人隐私和信息安全构成严重威胁的现状，提出利用SimHash算法进行Android恶意程序检测。通过实验进行实例分析，并将所得到的检测效果与360杀毒软件做比较，发现该方法比较适合复合特征文本字数在600～3 000字区间的特征检测，检测率高于360杀毒软件，可以作为Android恶意软件检测的一种有效方法。

[1] Barrera D,Kayacik H G,van Oorschot P C,et al.A methodology for empirical analysis of permission-based security models and its application to Android[C]//Proceedings of the 17th ACM conference on computer and communications security.New York,NY,USA:ACM,2010:73-84.

[2] Dini G,Martinelli F,Saracino A,et al.Madam:amulti-level anomaly detector for Android malware[M].Berlin:Springer,2012:240-253.

[3] Enck W,Ongtang M,McDaniel P.On lightweight mobile ph-one application certification[C]//Proceedings of the 16th ACM conference on computer and communications security.New York,NY,USA:ACM,2009:235-245.

[4] Sahs J,Khan L.A machine learning approach to Android malware detection[C]//Proceedings of EISIC.[s.l.]:IEEE,2012:141-147.

[5] 魏松杰,杨 铃.基于分层API调用的Android恶意代码静态描述方法[J].计算机科学,2015,42(1):155-158.

[6] 陈 震,许建林,余奕凡,等.移动网络软件架构中的安全技术研究[J].信息网络安全,2013(12):6-9.

[7] 王文君,董欢欢.Android应用程序安全[M].北京：电子工业出版社,2013.

[8] 陈 文,郭依正.深入理解Android网络编程[M].北京：机械工业出版社,2013.

[9] Simhash与Google的网页去重[EB/OL].2011-04-12.http://leoncom.org/?p=650607,2011-4-12.

[10] Charikar M.Similarity estimation techniques from rounding algorithms[EB/OL].2002.http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf.

[11] Simhash算法原理和代码实现[EB/OL].2012-11-29.http://blog.sina.com.cn/s/blog_81e6c30b0101cpvu.html.

[12] SimHash算法[EB/OL].2015-03-26.http://blog.csdn.net/acdreamers/article/details/44656481.

[13] Manku G S，Jain A，Sarma A D.Detecting near-duplicates for web crewling[C]//16th international world wide web conference.[s.l.]:[s.n.],2007.

AndroidMalwareDetectingBasedonSimHashAlgorithm

LI Hong-ling1，ZHAN Yi2

(1.Department of Computer Science and Engineering,School of Information Science and Engineering,Yunnan University,Kunming 650091,China; 2.Information Security Evaluation Center of Yunnan Province,Kunming 650000,China)

Current Android applications vary in quality,while there exist many potential malwares threatening privacy and information safety.In order to cope with this particular predicament,a new solution using SimHash algorithm for Android malware detection is proposed on the basis of analysis of signature detection technology based on MD5,which consists of three steps including APK signature-text extraction,signature-text digital fingerprint generation and results contrast.In order to textualize APK files,malware analyzing program androlyze.py is introduced.Meanwhile,considering the efficiency of Android signatures,Android program permission,call function,receiver and services have been converted into composite signatures APK text.Then,the composite signatures text has been converted into string,of which the Hamming Distance is counted as measurement for the security level.In addition,after practically analyzing and compared with 360 Anti-virus Software the overall detecting efficiency is proved to be better,thus considered as an effective method of Android malware detection.

SimHash algorithm;Android malware detecting;composite signatures text;similarity comparison

TP309;TP393

A

1673-629X(2017)10-0121-05

2016-10-19

2017-01-20 < class="emphasis_bold">网络出版时间

时间：2017-07-19

国家自然科学基金资助项目(61562090)；云南大学教育教学改革研究项目

李红灵(1966-)，女，副教授，研究方向为计算机网络、信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1109.024.html

10.3969/j.issn.1673-629X.2017.10.026