基于SimHash算法的Android惡意程序檢測(cè)

李紅靈，詹 翊

(1.云南大學(xué) 信息學(xué)院 計(jì)算機(jī)科學(xué)與工程系，云南 昆明 650091; 2.云南省信息安全測(cè)評(píng)中心，云南 昆明 650000)

基于SimHash算法的Android惡意程序檢測(cè)

李紅靈1，詹 翊2

(1.云南大學(xué) 信息學(xué)院 計(jì)算機(jī)科學(xué)與工程系，云南 昆明 650091; 2.云南省信息安全測(cè)評(píng)中心，云南 昆明 650000)

針對(duì)當(dāng)前Android應(yīng)用程序良莠不齊，存在大量的惡意程序?qū)€(gè)人隱私和信息安全構(gòu)成嚴(yán)重威脅的現(xiàn)狀，在分析基于MD5的傳統(tǒng)特征代碼檢測(cè)技術(shù)的基礎(chǔ)上，提出了利用SimHash算法，經(jīng)過(guò)APK文件特征文本提取，特征文本數(shù)字指紋生成，數(shù)字指紋比對(duì)及比對(duì)結(jié)果分析三個(gè)步驟，進(jìn)行Android惡意程序檢測(cè)的新方法。為實(shí)現(xiàn)APK文件特征文本化，引入惡意軟件分析程序androlyze.py，同時(shí)，考慮到Android特征的有效性，經(jīng)研究需要選取Android程序的權(quán)限及調(diào)用映射、廣播接收器、服務(wù)等核心信息組合成對(duì)應(yīng)APK文件的復(fù)合特征文本，將復(fù)合特征文本轉(zhuǎn)換為字符串后利用程序進(jìn)行海明距離計(jì)算，由海明距離判斷待測(cè)試APK文件的安全性。通過(guò)實(shí)驗(yàn)進(jìn)行實(shí)例分析，并將得到的檢測(cè)效果與360殺毒軟件做比較，發(fā)現(xiàn)基于SimHash算法的惡意程序檢測(cè)方法，檢測(cè)率高于360，可以作為Android惡意軟件檢測(cè)的一種有效方法。

SimHash算法；Android惡意程序檢測(cè)；復(fù)合特征文本；相似性比較

0 引 言

如今Android應(yīng)用市場(chǎng)由于缺乏統(tǒng)一的APK程序安全檢測(cè)與審查制度，Android應(yīng)用程序良莠不齊，其中大量的惡意程序?qū)€(gè)人隱私和信息安全構(gòu)成了嚴(yán)重威脅。因此，加強(qiáng)對(duì)Android惡意程序的檢測(cè)與分析研究十分必要。

國(guó)外對(duì)Android惡意程序檢測(cè)等方面的研究成果顯著，David Barrera等[1]對(duì)Google應(yīng)用市場(chǎng)中1 100個(gè)應(yīng)用類(lèi)型的應(yīng)用程序的AndroidManifest.xml文件進(jìn)行分析，并利用Self-Organizing Maps (SOM)算法將這些數(shù)據(jù)組織成二維授權(quán)圖，可以直觀(guān)清晰地看出這些應(yīng)用程序申請(qǐng)的權(quán)限名稱(chēng)、類(lèi)型。Gianluca Dini等[2]提出了針對(duì)Android惡意軟件的多級(jí)異常檢測(cè)方法(Multi-level Anomaly Detector for Android Malware，MADAM)，該方法同時(shí)監(jiān)視Android的內(nèi)核級(jí)和用戶(hù)級(jí)，使用機(jī)器學(xué)習(xí)技術(shù)來(lái)區(qū)分正常行為和惡意行為。W.Enck等[3]提出了一種基于應(yīng)用程序權(quán)限請(qǐng)求的輕量級(jí)的不安全應(yīng)用程序識(shí)別方法，并開(kāi)發(fā)了一個(gè)輕量級(jí)的Android應(yīng)用安全認(rèn)證系統(tǒng)Kirin。Justin Sahs等[4]提出了一種用機(jī)器學(xué)習(xí)來(lái)檢測(cè)Android惡意軟件的方法，通過(guò)開(kāi)源項(xiàng)目Androguard從Android應(yīng)用程序包APK中提取特征，采用支持LIBSVM接口的Scikit-learn框架提供的二分類(lèi)支持向量機(jī)訓(xùn)練這些特征并生成一個(gè)分類(lèi)器，用來(lái)分類(lèi)Android軟件。而在國(guó)內(nèi)，魏松杰等[5]通過(guò)靜態(tài)分析提取了APK文件中API在應(yīng)用包、對(duì)象類(lèi)、類(lèi)函數(shù)層面的調(diào)用信息，并以樹(shù)形方式進(jìn)行描述，歸納了應(yīng)用程序描述樹(shù)的特征。

在對(duì)上述各種方法進(jìn)行學(xué)習(xí)研究以及對(duì)傳統(tǒng)的特征碼比對(duì)方法進(jìn)行分析的基礎(chǔ)上，提出將相似性哈希算法SimHash靈活運(yùn)用到Android惡意程序檢測(cè)，設(shè)計(jì)并開(kāi)發(fā)了基于SimHash算法的Android惡意應(yīng)用檢測(cè)程序，并對(duì)其進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1 惡意程序特征碼檢測(cè)方法

惡意程序特征碼檢測(cè)主要采用的方法是基于已有的特征信息，對(duì)程序進(jìn)行特征碼提取和特征模式匹配，以此判定是否為惡意程序[6]。

1.1傳統(tǒng)的特征碼比對(duì)方法

基于特征碼的檢測(cè)方法可歸納為模式的提取和匹配，特征碼就是提取出的惡意代碼的特征模式，而惡意代碼的掃描過(guò)程就是特征模式匹配的過(guò)程，即特征碼比對(duì)。

傳統(tǒng)的特征代碼檢測(cè)主要基于MD5計(jì)算，即先計(jì)算程序的MD5值，如果此值與已有的某個(gè)惡意程序的MD5值相同，則認(rèn)為該程序具備惡意程序的特征[7-8]。優(yōu)點(diǎn)是能在惡意程序首次運(yùn)行前比對(duì)，對(duì)單一程序而言，檢測(cè)速度快，準(zhǔn)確度高，對(duì)已知惡意代碼十分有效。但是也存在一些難以解決的問(wèn)題。比如，其對(duì)惡意代碼的分析完全依賴(lài)于特征庫(kù)，使其無(wú)法處理未知和變形的惡意代碼。當(dāng)前，很多惡意程序的變種，行為非常相似，但簽名卻不同，這導(dǎo)致此類(lèi)檢測(cè)方法不能抵抗壓縮、混淆、加殼等攻擊。另外，要分析未知或變種惡意代碼的特征碼，必須逐一提取其特征碼并加入特征庫(kù)，否則無(wú)法進(jìn)行匹配。若惡意程序變種數(shù)量巨大，需要?jiǎng)?chuàng)建大量的簽名添加到簽名庫(kù)，這會(huì)大大增加惡意軟件特征比對(duì)時(shí)間，占用過(guò)多系統(tǒng)資源，最終導(dǎo)致特征庫(kù)爆炸。

針對(duì)上述問(wèn)題，提出基于SimHash算法的特征碼比對(duì)方法。

1.2基于SimHash算法的特征碼比對(duì)方法

SimHash算法設(shè)計(jì)的初衷是為了解決海量數(shù)據(jù)的重復(fù)檢測(cè)問(wèn)題，主要思想是降維，將高維的特征向量映射成一個(gè)f-bit的指紋(fingerprint)，通過(guò)比較兩篇文章的f-bit指紋的Hamming Distance來(lái)確定文章是否重復(fù)或者高度近似[9]。由于SimHash算法是局部敏感哈希算法，局部的變化對(duì)整體影響不大，所以可將需檢測(cè)的文本通過(guò)SimHash算法，降維成固定長(zhǎng)度的二進(jìn)制序列，并將這些二進(jìn)制序列作為文本信息的數(shù)字指紋，通過(guò)比較文本信息的數(shù)字指紋來(lái)判斷文本信息是否重復(fù)或者高度近似。

針對(duì)Android惡意程序的檢測(cè)，運(yùn)用SimHash算法進(jìn)行特征碼比對(duì)，需要經(jīng)過(guò)三個(gè)步驟。首先，將APK文件轉(zhuǎn)化為文本文件；其次，對(duì)文本文件生成其對(duì)應(yīng)的數(shù)字指紋；最后，對(duì)其數(shù)字指紋進(jìn)行信息比對(duì)分析。經(jīng)過(guò)上述三個(gè)步驟的分析和處理，最終判別Android程序的安全性。

2 基于SimHash算法的Android惡意程序檢測(cè)

2.1SimHash算法思想

SimHash是局部敏感哈希的一種，最早由Moses Charikar[10]提出，但是并沒(méi)有給出具體的SimHash算法和證明。SimHash算法廣泛用于信息檢索領(lǐng)域，如Google就基于此算法實(shí)現(xiàn)了網(wǎng)頁(yè)文件重復(fù)檢測(cè)。

通過(guò)降維，將高維的特征向量映射成一個(gè)低維的特征向量，通過(guò)兩個(gè)向量的海明距離來(lái)確定兩個(gè)文件的相似度[11]。在信息編碼中，兩個(gè)合法代碼對(duì)應(yīng)位上編碼不同的位數(shù)稱(chēng)為碼距，又稱(chēng)海明距離。Simhash算法的實(shí)現(xiàn)過(guò)程分為5步：分詞、hash、加權(quán)、合并、降維。詳細(xì)過(guò)程如圖1所示。

圖1 SimHash算法示意

2.2SimHash算法描述

SimHash算法的輸入為一個(gè)N維向量V，每個(gè)特征具有一定權(quán)重。輸出是一個(gè)C位的二進(jìn)制簽名S。具體步驟如下[12]：

(1)初始化一個(gè)C維向量Q(為0)，C位的二進(jìn)制簽名S為0。

(2)對(duì)V中的每一個(gè)特征，使用傳統(tǒng)的Hash算法計(jì)算出一個(gè)C位0、1組成的散列值H。對(duì)1≤i≤C，如果H的第i位為1，則Q的第i個(gè)元素加上該特征的權(quán)重；否則，Q的第i個(gè)元素減去該特征的權(quán)重。

(3)如果Q的第i個(gè)元素大于0，則S的第i位為1，否則為0。

(4)返回二進(jìn)制簽名S。

2.3字符串測(cè)試

假設(shè)S1,S2為2個(gè)字符串，其中：

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

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

采用MD5進(jìn)行計(jì)算，結(jié)果如下：

S1的MD5值為：

63bf17b026ff5081db6422fcb3 fbb51c

S2的MD5值為：

f74d55b317c1a023349e6e5fb 33fe33c

由此可見(jiàn)，盡管S1與S2內(nèi)容相差不大，但采用MD5計(jì)算后其結(jié)果差異很大。

另外，采用SimHash進(jìn)行計(jì)算，程序輸出如圖2所示。

圖2 字符串S1與S2的Binary Hash值

最后進(jìn)行字符串相似度計(jì)算：

S1的SimHash值為：

1000000000100101100001100 0000101

S2的SimHash值為：

1000000000000110100001001 0000100

S1、S2經(jīng)過(guò)異或運(yùn)算XOR后，共有六位不同，即：第1、8、10、17、18、22位，不同位數(shù)所占比例為6/32，等于0.187 5，那么其相同位數(shù)所占比例為26/32，等于0.812 5，即81.25%。

于是可以得出結(jié)論：字符串S1與S2的相似度為81.25%。

3 Android程序復(fù)合特征碼提取

3.1惡意代碼特征定義

惡意代碼的特征，簡(jiǎn)稱(chēng)特征碼，即是指其所特有的、非惡意代碼所沒(méi)有的特征。也就是從惡意代碼體內(nèi)不同的位置提取的一系列字節(jié)，這些字節(jié)和惡意代碼有唯一的關(guān)聯(lián)性。特征碼一般包括行為特征和狀態(tài)特征。行為特征包括API調(diào)用函數(shù)、訪(fǎng)問(wèn)網(wǎng)絡(luò)資源(創(chuàng)建SOCKETS，發(fā)起連接TCP、UDP、DNS)、修改系統(tǒng)服務(wù)等行為。狀態(tài)特征包括程序的文件信息(程序大小、MD5值)、程序代碼段、程序操作的連貫順序等。

3.2Android程序復(fù)合特征

由特征碼定義可知，程序的代碼段、網(wǎng)絡(luò)訪(fǎng)問(wèn)等都可以作為特征，就Android程序而言，權(quán)限、廣播接收器、服務(wù)都可以作為特征，考慮到單一特征存在的局限性，不能全面地概括應(yīng)用程序特性。因此，可以把Android程序的權(quán)限、廣播接收器、服務(wù)等信息組合起來(lái)構(gòu)成復(fù)合特征，這樣才可以全面精準(zhǔn)地反映Android程序的特性。另外，可以通過(guò)開(kāi)源惡意軟件分析包Androguard中的androlyze.py工具分別導(dǎo)出APK文件的權(quán)限及調(diào)用映射、廣播接收器、服務(wù)等信息，將其組合成該APK文件對(duì)應(yīng)的復(fù)合特征文本。

3.3Android程序權(quán)限及調(diào)用映射提取

使用Androlyze.py-s命令進(jìn)入Androlyze的Shell交互環(huán)境，通過(guò)a，d，dx=AnalyzeAPK(“./Android4-4.apk”，decompiler=“dad”)命令分別實(shí)現(xiàn)了建立的apk、dex文件對(duì)象的提取，DalvikVMFormat()調(diào)用的功能。

使用命令：show_Permissions(dx)可以提取Android程序權(quán)限及其調(diào)用映射，詳見(jiàn)圖3。

3.4Android程序廣播接收器提取

通過(guò)命令a.get_receivers()實(shí)現(xiàn)APK文件的廣播接收器提取(詳細(xì)信息略)。

3.5Android程序服務(wù)提取

通過(guò)命令a.get_services()實(shí)現(xiàn)APK文件的服務(wù)提取(詳細(xì)信息略)。

4 基于SimHash算法的Android程序檢測(cè)實(shí)例

4.1待測(cè)APK文件描述

待測(cè)試應(yīng)用程序?yàn)锳ndroid4-4.apk、Android4-5.apk、cutepuppies.apk。其中，Android4-4.apk是遠(yuǎn)程控制木馬程序，Android4-5.apk是Android4-4.apk的升級(jí)版，而cutepuppies.apk為C&C類(lèi)型惡意程序。

4.2APK文件特征文本

Android4-4.apk特征文本如圖4所示。由于篇幅有限，在此就不再給出其升級(jí)版Android4-5.apk和cutepuppies.apk的特征文本。

圖3 Android程序權(quán)限及調(diào)用映射

圖4 Android4-4.apk特征文本

4.3計(jì)算結(jié)果分析

將特征文本轉(zhuǎn)換為字符串后進(jìn)行SimHash計(jì)算，其結(jié)果如圖5所示。

圖5 SimHash算法的輸出結(jié)果

計(jì)算結(jié)果分析：

cutepuppies.apk和Android4-4.apk的海明距離為14。

cutepuppies.apk和Android4-5.apk的海明距離為14。

Android4-4.apk和Android4-5.apk的海明距離為2。

因?yàn)槭?4 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檢測(cè)效果比較

Gurmeet Singh Manku等[13]對(duì)SimHash算法效果進(jìn)行了測(cè)試，發(fā)現(xiàn)對(duì)于64位的SimHash值，當(dāng)海明距離為3時(shí)，召回率和準(zhǔn)確率都比較高，約為75%。因此，海明距離小于3都可以認(rèn)為是相似的。

實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)SimHash比較適用于大文本，500字以上效果都不錯(cuò)，經(jīng)初步統(tǒng)計(jì)Android惡意程序復(fù)合特征文本字?jǐn)?shù)在600～3 000字區(qū)間范圍，可適用于SimHash算法進(jìn)行檢測(cè)。通過(guò)對(duì)CutePuppiesWallpaper.apk、Android4-4.apk等5款?lèi)阂獬绦蜻M(jìn)行檢測(cè)，并與360殺毒軟件做比較，發(fā)現(xiàn)基于SimHash算法的惡意程序檢測(cè)方法效果顯著，檢測(cè)率高于360殺毒軟件。

5 結(jié)束語(yǔ)

針對(duì)當(dāng)前Android應(yīng)用程序良莠不齊，大量的惡意程序?qū)€(gè)人隱私和信息安全構(gòu)成嚴(yán)重威脅的現(xiàn)狀，提出利用SimHash算法進(jìn)行Android惡意程序檢測(cè)。通過(guò)實(shí)驗(yàn)進(jìn)行實(shí)例分析，并將所得到的檢測(cè)效果與360殺毒軟件做比較，發(fā)現(xiàn)該方法比較適合復(fù)合特征文本字?jǐn)?shù)在600～3 000字區(qū)間的特征檢測(cè)，檢測(cè)率高于360殺毒軟件，可以作為Android惡意軟件檢測(cè)的一種有效方法。

[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調(diào)用的Android惡意代碼靜態(tài)描述方法[J].計(jì)算機(jī)科學(xué),2015,42(1):155-158.

[6] 陳 震,許建林,余奕凡,等.移動(dòng)網(wǎng)絡(luò)軟件架構(gòu)中的安全技術(shù)研究[J].信息網(wǎng)絡(luò)安全,2013(12):6-9.

[7] 王文君,董歡歡.Android應(yīng)用程序安全[M].北京：電子工業(yè)出版社,2013.

[8] 陳 文,郭依正.深入理解Android網(wǎng)絡(luò)編程[M].北京：機(jī)械工業(yè)出版社,2013.

[9] Simhash與Google的網(wǎng)頁(yè)去重[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算法原理和代碼實(shí)現(xiàn)[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">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-19

國(guó)家自然科學(xué)基金資助項(xiàng)目(61562090)；云南大學(xué)教育教學(xué)改革研究項(xiàng)目

李紅靈(1966-)，女，副教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、信息安全。

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

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