基于kNN算法和K—means算法的Android惡意軟件檢測

潘夏福

摘要：目前針對(duì)Android惡意應(yīng)用可以采用靜態(tài)或者動(dòng)態(tài)分析的方法獲取軟件的特征，并根據(jù)這些特征采用特定的算法進(jìn)行檢測，但單一的分析方法無法充分體現(xiàn)Android應(yīng)用的多樣性。該文首次提出一種分析Android應(yīng)用權(quán)限、調(diào)用和動(dòng)作等特征，使用kNN分類算法識(shí)別正常應(yīng)用和惡意應(yīng)用。同時(shí)為了提高分類的正確性，該文還采用了K-means算法對(duì)訓(xùn)練類進(jìn)行初始化。實(shí)驗(yàn)表明本文算法能夠充分利用Android多樣的特征有效檢測惡意應(yīng)用，并且與相關(guān)工作對(duì)比，算法在檢測效率和執(zhí)行效率上表現(xiàn)更好。

關(guān)鍵詞：kNN；K-means；Android；惡意軟件檢測

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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系統(tǒng)是Google公司開發(fā)的一款開放發(fā)式系統(tǒng)，任何手機(jī)廠商都可以對(duì)其進(jìn)行定制，開放的特性使得Android系統(tǒng)占智能手機(jī)平臺(tái)的主導(dǎo)地位，擁有整個(gè)市場的大部分份額。但由于Android系統(tǒng)的開放性，它也成為眾多黑客、惡意開發(fā)者攻擊的對(duì)象。特別是現(xiàn)階段我國Android的第三方市場很多，這些市場允許用戶自己上傳自己的應(yīng)用代碼，但是市場的審核功能極其不完善，許多惡意軟件流行其中。

手機(jī)惡意軟件的危害主要有惡意扣費(fèi)、竊取賬號(hào)密碼等用戶隱私、破壞系統(tǒng)等，其中竊取隱私行為占大多數(shù)，一旦有惡意的人獲取這些隱私信息，他可以對(duì)用戶進(jìn)行詐騙，危害非常大，甚至對(duì)國家安全都會(huì)造成影響[1]。

另外由于惡意代碼使用的技術(shù)不斷更新，Android系統(tǒng)的惡意軟件監(jiān)測變得越來越困難，Android上的應(yīng)用在被監(jiān)測出來之前，已經(jīng)被用戶大量下載了。對(duì)Android惡意軟件檢測十分有必要。但是由于手機(jī)內(nèi)存、運(yùn)行速度、電池耗電量的限制，Android惡意軟件檢測在手機(jī)上的分析效果不是很理想。因此對(duì)Android系統(tǒng)的惡意軟件進(jìn)行高效的檢測十分必要。

1 相關(guān)工作

Android惡意軟件檢測目前主要采用靜態(tài)分析和動(dòng)態(tài)分析兩種技術(shù)。靜態(tài)分析技術(shù)主要采用分析Android軟件的源代碼或者二進(jìn)制代碼，找出可疑行為，通過分析Android權(quán)限和調(diào)用函數(shù)等內(nèi)容，根據(jù)特定模型，判定是否為惡意軟件。權(quán)限分析主要針對(duì)AndroidManifest.xml文件進(jìn)行自動(dòng)化分析，提取permission、activity、service、receive和provider組件進(jìn)行特征提取，然后根據(jù)特定的類別進(jìn)行設(shè)置[2]。而調(diào)用函數(shù)分析則通過Android平臺(tái)的虛擬機(jī)Dalvik指令特點(diǎn)，定義形式化描述語言，描述惡意軟件[3， 8]，或者通過native代碼使用lib庫文件進(jìn)行分析，提取函數(shù)調(diào)用序列，完成軟件判定[4， 9]。靜態(tài)惡意代碼檢測優(yōu)點(diǎn)是覆蓋率高，缺點(diǎn)是無法檢測代碼混淆、加密，而且無法分辨發(fā)短信等在動(dòng)態(tài)執(zhí)行中才可以判定的惡意行為。

動(dòng)態(tài)分析技術(shù)主要采用沙盒技術(shù)，通過模擬應(yīng)用軟件的操作過程，自動(dòng)完成軟件的安裝，用戶操作，用戶卸載等操作實(shí)現(xiàn)惡意軟件判定。動(dòng)態(tài)分析可以分享Android系統(tǒng)的系統(tǒng)調(diào)用頻率數(shù)，根據(jù)一些特殊調(diào)用在系統(tǒng)惡意代碼執(zhí)行時(shí)出現(xiàn)波動(dòng)的現(xiàn)象進(jìn)行惡意軟件判定，另外還可以使用mokeyrunner等工具模擬用戶行為，點(diǎn)擊應(yīng)用程序，模擬運(yùn)行，根據(jù)模擬數(shù)據(jù)建立用戶活動(dòng)模型，實(shí)現(xiàn)惡意行為判定[5， 7]。但是這種檢測方法工作量大，分析時(shí)間長，在手機(jī)上運(yùn)行實(shí)時(shí)性不高，資源消耗過大。

另外為了提高分析的準(zhǔn)確性，還有作者提出來基于靜態(tài)分析和動(dòng)態(tài)分析相結(jié)合的多類特征惡意行為檢測系統(tǒng)THEA[7]，或者基于權(quán)限類別的惡意檢測程序[2]。但這些程序?qū)阂獬绦驒z測存在著各種問題，因此本文提出基于kNN算法的Android惡意軟件監(jiān)測算法。

2 特征代碼提取

特征代碼采用靜態(tài)與動(dòng)態(tài)分析相結(jié)合的方式，選取權(quán)限、系統(tǒng)函數(shù)調(diào)用作為特征代碼。使用Android SDK自帶的AAPT打包工具，對(duì)APK進(jìn)行解壓，提取AndroidManifest.xml文件和lib庫文件（.so文件）。根據(jù)AndroidManifest.xml的內(nèi)容生成特征代碼向量P，其中P={permission， activity， service， receiver， provider}。對(duì).so文件進(jìn)行合并后，提取動(dòng)態(tài)符號(hào)表中的函數(shù)信息，對(duì)數(shù)據(jù)應(yīng)用程序進(jìn)行統(tǒng)計(jì)，提取最能描述系統(tǒng)功能的函數(shù)生成向量L，其中L={open， icocl， read， write， sendmsg， recvfrom， recvmsg， access， chmod， chown}。

動(dòng)態(tài)分析通過模擬器調(diào)用APK文件，模擬打電話、發(fā)短信等操作，然后使用trace和wireshark工具動(dòng)態(tài)檢測系統(tǒng)調(diào)用日志、系統(tǒng)API和網(wǎng)絡(luò)數(shù)據(jù)，并使用mokeyrunner工具模擬用戶行為，獲取用戶行為數(shù)據(jù)，生成向量U，其中U={trace， wireshark， mokeyrunner}。

特征碼向量采用這幾個(gè)數(shù)據(jù)構(gòu)成，M={P， L， U}T。向量相異度采用歐幾里得距離，向量X與Y之間的相異度：

3 相關(guān)算法實(shí)現(xiàn)

3.1 kNN算法簡介

kNN算法又被稱為k近鄰分類（k-nearest neighbor classification）算法，就是在測試組中找和訓(xùn)練元組向量空間上最接近的k個(gè)點(diǎn)中，類別最多的那個(gè)分類。由于向量組中部分值由于取值范圍大，對(duì)距離的影響高，不利于反映真實(shí)的相異度，需對(duì)屬性值進(jìn)行規(guī)格化，將各個(gè)屬性按比例均映射到[0， 1]區(qū)間，以平衡各個(gè)屬性對(duì)距離的影響，映射公式為：

這里Xi為向量X的第i個(gè)分量。

Android程序被分為2種，正常應(yīng)用和惡意應(yīng)用，根據(jù)分組，計(jì)算Android程序類別，分類結(jié)果離待測向量最近的為其所屬類別。

在試驗(yàn)過程中，發(fā)現(xiàn)惡意程序應(yīng)用判定中權(quán)限向量P和用戶行為向量U在惡意程序中異常情況比較突出，而系統(tǒng)功能函數(shù)往往只是調(diào)用一兩次，對(duì)異常情況判定影響較小，可以對(duì)這種情況設(shè)置不同的權(quán)值，增加判定的準(zhǔn)確率。向量X的屬性可以設(shè)置為：

3.2 基于k-means算法的改進(jìn)

基于kNN算法的Android惡意軟件監(jiān)測實(shí)現(xiàn)比較簡單，是數(shù)據(jù)挖掘分類技術(shù)中的最簡單方法，比較適合對(duì)稀有事物進(jìn)行分類。但是算法如果樣本不平衡時(shí)，比如現(xiàn)階段惡意軟件數(shù)目較少，正常軟件類數(shù)目較大，導(dǎo)致正常軟件樣本占大多數(shù)，有可能k個(gè)鄰居中占有概率大，造成無論怎樣，目標(biāo)軟件都判定為正常軟件。

因此可以對(duì)惡意軟件類和正常軟件類進(jìn)行初始化數(shù)據(jù)處理，通過K-means算法分別計(jì)算出分類的N個(gè)質(zhì)心。K-means算法是一種非監(jiān)督實(shí)時(shí)算法，可以在最新誤差函數(shù)的基礎(chǔ)上將數(shù)據(jù)劃分為預(yù)定的類數(shù)。通過指定聚類數(shù)目N和迭代次數(shù)或收斂條件，根據(jù)一定的相似性原則，分配相似的質(zhì)心，形成類，然后以每一類的平均矢量作為新的質(zhì)心，反復(fù)迭代直至收斂或者達(dá)到最大迭代數(shù)目。

K-means的質(zhì)心可以采用下面的公式計(jì)算：

（4）

其中Kj為軟件訓(xùn)練類的質(zhì)心，Vi為訓(xùn)練軟件特征向量，為訓(xùn)練矢量與質(zhì)心的關(guān)聯(lián)程度。其取值只能是0和1，其中0代表空隸屬度，1代表著全隸屬度，計(jì)算公式如下：

（5）

K-means算法的收斂條件可以設(shè)置一個(gè)閾值，當(dāng)誤差率低于，可以終止算法，的定義如下：

（6）

其中D為誤差方差，公式如下：

（7）

K-means算法描述如下：

步驟1：選擇誤差門限；

步驟2：初始化質(zhì)心，根據(jù)公式（6）（7）計(jì)算，k=0；

步驟3：；

步驟4：使用公式（4）（5）計(jì)算；

步驟5：根據(jù)公式（6）（7）計(jì)算，，如果，跳轉(zhuǎn)至步驟3；

步驟6：結(jié)束。

3.3 kNN算法描述

在對(duì)Android惡意軟件判定之前，首先對(duì)惡意軟件和正常軟件的訓(xùn)練集進(jìn)行K-means初始化，獲得這兩個(gè)集合的質(zhì)心向量組，作為檢測程序的樣本向量，根據(jù)這些樣本向量，運(yùn)行Android惡意檢測算法，算法描述如下：

步驟1：獲取Android程序的特征代碼P，L，U；

步驟2：根據(jù)公式（2）（3）計(jì)算特征向量M；

步驟3：根據(jù)公式（1）計(jì)算特征向量M與正常應(yīng)用和惡意應(yīng)用組的相異度；

步驟4：按照相異度進(jìn)行遞增排序；

步驟5：選取最近的k個(gè)特征向量；

步驟6：統(tǒng)計(jì)這k個(gè)特征向量在正常應(yīng)用和惡意應(yīng)用的數(shù)目，返回最多的一個(gè)；

步驟7：根據(jù)返回值判定結(jié)果。

4 實(shí)驗(yàn)分析

為了評(píng)估算法的有效性，本文將算法與近年來的相關(guān)工作進(jìn)行對(duì)比，使用相同的測試樣本進(jìn)行判斷分析。樣例主要是從Google Play或者國內(nèi)的第三方Android市場上下載，一共1798個(gè)惡意軟件，3021個(gè)正常軟件，對(duì)比結(jié)果如下：

從對(duì)比表中可以看出，本文算法比單純的靜態(tài)或動(dòng)態(tài)檢測的方法判定率都高，但是在惡意軟件判定率方面比Androdect算法差，有待提高。本文算法實(shí)現(xiàn)簡單，對(duì)系統(tǒng)資源耗費(fèi)更少，更適合在有限資源的移動(dòng)系統(tǒng)中實(shí)現(xiàn)。實(shí)驗(yàn)表明本文算法比Androdect算法更容易在Android系統(tǒng)中實(shí)現(xiàn)。

5 總結(jié)

本文采用了靜態(tài)和動(dòng)態(tài)結(jié)合的技術(shù)獲取Android應(yīng)用程序的特征向量，并在此基礎(chǔ)上設(shè)計(jì)了kNN分類算法和K-means聚類算法相結(jié)合惡意軟件檢測模型，并實(shí)現(xiàn)了惡意檢測算法。該算法彌補(bǔ)了單純靜態(tài)或單純動(dòng)態(tài)監(jiān)測的不足，在對(duì)大量程序的測試中，算法表現(xiàn)良好。實(shí)驗(yàn)結(jié)果表明算法的準(zhǔn)確率和執(zhí)行效率上表現(xiàn)良好，優(yōu)于大部分惡意代碼檢測工具。下一步將kNN分類算法和K-means聚類算法結(jié)合到云計(jì)算上面，進(jìn)一步完善算法，并對(duì)惡意軟件庫進(jìn)行云存儲(chǔ)，提高系統(tǒng)的運(yùn)行速度和判定準(zhǔn)確率。

參考文獻(xiàn)：

[1] 邊悅，戴航，慕德俊. Android惡意軟件特征研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2014， 24（11）：178-181.

[2] 楊歡， 張玉清， 胡予濮，等. 基于權(quán)限頻繁模式挖掘算法的Android惡意應(yīng)用檢測方法[J]. 通信學(xué)報(bào)， 2013， 34（Z1）：106-115.

[3] 李挺， 董航， 袁春陽，等. 基于Dalvik指令的Android惡意代碼特征描述及驗(yàn)證[J]. 計(jì)算機(jī)研究與發(fā)展， 2014， 51（7）：1458-1466.

[4] 雷靈光， 荊繼武， 王躍武，等. 一種基于行為的Android系統(tǒng)資源訪問控制方案[J]. 計(jì)算機(jī)研究與發(fā)展， 2014， 51（5）：1028-1038.

[5] 蔡志標(biāo)，彭新光. 基于系統(tǒng)調(diào)用的Android惡意軟件監(jiān)測[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2013， 34（11）：3757-3761.

[6] 楊歡， 張玉清， 胡予濮，等. 基于多類特征Android應(yīng)用惡意行為檢測系統(tǒng)[J]. 計(jì)算機(jī)學(xué)報(bào)， 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.