任維武, 張波辰, 底曉強(qiáng), 盧奕南

(1. 長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 長(zhǎng)春 130022； 2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012)

隨著移動(dòng)智能終端設(shè)備的大規(guī)模普及, 移動(dòng)芯片已逐漸接近甚至達(dá)到了桌面級(jí)計(jì)算機(jī)的計(jì)算和處理能力, 而且搭載在移動(dòng)終端上的各類應(yīng)用進(jìn)一步擴(kuò)大了終端的使用范圍. 移動(dòng)智能設(shè)備的“電腦化”, 不但給自身帶來(lái)了傳統(tǒng)計(jì)算機(jī)系統(tǒng)的各類安全威脅, 而且還增加了自身獨(dú)有的更復(fù)雜、 更具挑戰(zhàn)性的安全風(fēng)險(xiǎn). 入侵檢測(cè)系統(tǒng)是一種經(jīng)典有效的防御技術(shù), 對(duì)保護(hù)全球信息基礎(chǔ)設(shè)施發(fā)揮了巨大作用. 入侵檢測(cè)通過(guò)計(jì)算機(jī)系統(tǒng)或網(wǎng)絡(luò)中若干節(jié)點(diǎn)的收集和分析審計(jì)記錄、 安全日志、 用戶行為及網(wǎng)絡(luò)數(shù)據(jù)等信息, 檢查網(wǎng)絡(luò)或系統(tǒng)中是否存在違反安全策略的入侵行為及被攻擊的跡象[1]. 根據(jù)檢測(cè)機(jī)制不同, 可以將入侵檢測(cè)系統(tǒng)分為誤用檢測(cè)和異常檢測(cè). 誤用檢測(cè)精度高, 誤報(bào)率低, 但不能檢測(cè)未知入侵行為; 異常檢測(cè)通過(guò)建立正常的用戶和系統(tǒng)行為輪廓, 能檢測(cè)未知入侵行為, 但誤報(bào)率一般較高. 根據(jù)訓(xùn)練數(shù)據(jù)源的不同, 可以將入侵檢測(cè)系統(tǒng)分為有監(jiān)督和無(wú)監(jiān)督. 有監(jiān)督方法能夠從標(biāo)記數(shù)據(jù)集中發(fā)現(xiàn)與標(biāo)記示例近似的入侵或正常行為, 如決策樹(shù)、 神經(jīng)網(wǎng)絡(luò)、 支持向量機(jī)(SVM)等; 無(wú)監(jiān)督方法能夠從無(wú)標(biāo)記數(shù)據(jù)集中發(fā)現(xiàn)隱藏的結(jié)構(gòu)性知識(shí), 即不同于正常行為的異常行為, 如聚類方法[2]等.

目前針對(duì)安卓平臺(tái)的安全性研究成果較多, 如Shabtai等[3]通過(guò)提出一個(gè)基于主機(jī)惡意行為的檢測(cè)框架, 建立機(jī)器學(xué)習(xí)異常檢測(cè)器來(lái)識(shí)別正常行為和異常行為； Reina等[4]提出了自動(dòng)動(dòng)態(tài)分析安卓異常行為的方法, 該方法通過(guò)分析底層的QS特征行為(如讀寫文件、 執(zhí)行程序等)及高層的安卓特征行為(如存取個(gè)人信息、 發(fā)送信息等), 利用一系列的系統(tǒng)調(diào)用判定行為屬性； Enck等[5]提出了實(shí)時(shí)監(jiān)控用戶隱私的信息流跟蹤系統(tǒng), 針對(duì)敏感信息如信息數(shù)據(jù)、 郵件數(shù)據(jù)、 電話數(shù)據(jù)等進(jìn)行實(shí)時(shí)監(jiān)控; Burguera等[6]提出了一種安卓異常行為檢測(cè)系統(tǒng), 由兩部分組成： 需要安裝的源APP和一個(gè)遠(yuǎn)程的惡意檢測(cè)服務(wù)器, 源APP發(fā)送特征數(shù)據(jù)到遠(yuǎn)程服務(wù)器, 由遠(yuǎn)程服務(wù)器進(jìn)行鑒別.

人工蜂群(artificial bee colony, ABC)算法[7]通過(guò)模擬蜜源搜索、 采蜜分工、 信息分享等蜜蜂采蜜過(guò)程, 實(shí)現(xiàn)目標(biāo)問(wèn)題的隨機(jī)優(yōu)化. 相比其他隨機(jī)優(yōu)化算法, 如遺傳算法、 蟻群算法和模擬退火算法等, 其優(yōu)點(diǎn)是兼顧了全局搜索和局部搜索, 使得解搜索和解選擇達(dá)到了較好的平衡. 目前人工蜂群算法研究主要集中于算法在不同領(lǐng)域的應(yīng)用和對(duì)算法本身的改進(jìn)兩方面. 在聚類分析應(yīng)用中, Karaboga等[8]利用數(shù)據(jù)不同屬性尋找它們的相似性, 對(duì)多變量數(shù)據(jù)聚類有較好的效果.

聚類是一種無(wú)監(jiān)督異常算法, 能在沒(méi)有任何先驗(yàn)知識(shí)的前提下發(fā)現(xiàn)未知攻擊, 典型的聚類算法包括DBSCAN算法[9]、 OPTICS算法[10]和DENCLUE算法[11]等, 其中DBSCAN算法的聚類速度快, 參數(shù)較少, 只有兩個(gè)全局變量的參數(shù)Eps和Minipts, 且能在含有噪聲空間的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇, 生成的正常行為輪廓精度較高, 因此, 改進(jìn)后的DBSCAN算法是一種較優(yōu)良的異常入侵檢測(cè)算法. 雖然DBSCAN算法只有兩個(gè)參數(shù), 但在實(shí)際應(yīng)用中, 確定參數(shù)Eps和Minipts十分困難, 如果選取不當(dāng), 就會(huì)生成精度較差的正常行為輪廓, DBSCAN算法提供了一種可視化輔助確定Eps的方法, 但這種方法確定的Eps通常不是最優(yōu)參數(shù), 聚類效果并不穩(wěn)定. 此外, DBSCAN算法具有一定的抗噪聲能力, 但異常檢測(cè)數(shù)據(jù)通常涉及多個(gè)特征屬性, 有些特征屬性不能有效地代表業(yè)務(wù)邏輯和業(yè)務(wù)場(chǎng)景, 甚至有些特征屬性本身即為噪聲, 訓(xùn)練生成的行為輪廓可能將噪聲特征作為正常行為特征, 影響了真實(shí)輸入與輸出間的關(guān)系, 導(dǎo)致過(guò)擬合現(xiàn)象, 影響最終的檢測(cè)效果. 基于這兩個(gè)問(wèn)題, 本文提出一種基于人工蜂群優(yōu)化的密度聚類異常入侵檢測(cè)(ABC-DBSCAN)算法, 利用人工蜂群對(duì)密度聚類的參數(shù)和特征屬性進(jìn)行組合優(yōu)化, 以實(shí)現(xiàn)檢測(cè)性能的最終提升.

1 預(yù)備知識(shí)

初始化蜜源： 在使用ABC算法求解優(yōu)化時(shí), 每個(gè)蜜源都代表問(wèn)題的一個(gè)優(yōu)化組合解. 設(shè)ABC算法隨機(jī)初始化N個(gè)蜜源(解), 則蜜源xi可表示為

xi=lb+(ub-lb)×rand(0,1),

(1)

其中:xi(i=1,2,…,N)表示第i個(gè)蜜源；lb和ub分別表示x取值范圍的上限和下限.xi可以用一個(gè)D維向量表示, 其中xij(j=1,2,…,D)為蜜源i的第j個(gè)待優(yōu)化參數(shù). 當(dāng)xij為離散二值時(shí), 參數(shù)xij表示為

(2)

領(lǐng)域搜索： 引領(lǐng)蜂和跟隨蜂對(duì)蜜源領(lǐng)域進(jìn)行搜索, 蜜源的每個(gè)參數(shù)均被搜索, 其搜索過(guò)程可表示為

=xij+(xij-xkj)×rand(-1,1),

(3)

(4)

蜜源選擇： 跟隨蜂根據(jù)蜜源概率采蜜, 概率大的蜜源被采的可能性也大, 反之亦然. 蜜源選擇公式表示為

(5)

其中： Prob(i)表示第i個(gè)蜜源被選擇的概率; fit(i)表示第i個(gè)蜜源的適應(yīng)值; fitmax表示最大適應(yīng)值. 適應(yīng)值越高, 概率越大.

適應(yīng)值： 入侵檢測(cè)系統(tǒng)的檢測(cè)性能評(píng)價(jià)參數(shù)主要有兩個(gè), 即檢測(cè)率DR(detection rate)和誤報(bào)率FPR(false positive rate), 檢測(cè)率越高越好, 誤報(bào)率越低越好, 所以可以將適應(yīng)值定義為

fit(i)=DR+(1-FPR)×γ-d/D,

(6)

其中:γ為誤報(bào)率影響因子, 可以根據(jù)實(shí)際需要, 提高誤報(bào)率的權(quán)值;d為蜜源特征數(shù). 檢測(cè)率：

(7)

其中: TAs表示正確報(bào)警的入侵?jǐn)?shù); Is表示總的入侵樣本數(shù). 誤報(bào)率：

(8)

其中: FAs為錯(cuò)誤報(bào)警數(shù)； Ts為總樣本數(shù).

隨機(jī)搜索： 如果經(jīng)過(guò)最大限制次搜索后, 解未得到改善, 則引領(lǐng)蜂變?yōu)閭刹旆? 并隨機(jī)產(chǎn)生一個(gè)新解, 可表示為

xij=lbj+(upj-lbj)×rand(0,1),

(9)

當(dāng)xij為離散二值時(shí), 新解可表示為

(10)

MSN表示算法經(jīng)過(guò)一定次數(shù)的迭代后, 適應(yīng)值沒(méi)有改善, 則該蜜源被放棄.

2 主要算法

人工蜂群算法包括蜜源初始化過(guò)程、 引領(lǐng)蜂搜索過(guò)程、 跟隨蜂選擇過(guò)程和偵察蜂搜索過(guò)程. 將其與異常檢測(cè)的過(guò)程整合優(yōu)化后如圖1所示. 由于本文提出的改進(jìn)算法涉及到異常檢測(cè)算法參數(shù)優(yōu)化和特征選擇兩方面, 因此其中既有連續(xù)值的優(yōu)化, 也有離散值的選取. 此外, 選擇適應(yīng)值一定要遵循提高算法檢測(cè)性能的原則, 所以本文主要從初始化蜜源、 鄰域搜索和適應(yīng)值計(jì)算等三方面介紹改進(jìn)算法的特有優(yōu)化過(guò)程.

圖1 算法流程Fig.1 Flow chart of algorithm

1) 初始化蜜源. 在使用ABC算法求解最優(yōu)化問(wèn)題時(shí), 每個(gè)蜜源都代表問(wèn)題的一個(gè)優(yōu)化組合解, 本文方法中, 蜜源由兩部分組成： 參數(shù)部分和特征部分. 參數(shù)部分采用連續(xù)值編碼, 特征部分采用離散二值編碼. 密度異常檢測(cè)算法有兩個(gè)主要參數(shù)Eps和Minipts, 這兩個(gè)參數(shù)是連續(xù)值, 取值范圍受聚類規(guī)模影響, 生成蜜源時(shí)可參考式(1). 算法的訓(xùn)練和測(cè)試數(shù)據(jù)樣本有106個(gè)特征, 對(duì)這些特征可采用遺傳算法的編碼機(jī)制, 利用一個(gè)長(zhǎng)度為106位的二進(jìn)制串表示, 若當(dāng)前位取值為1, 則表示選擇該特征, 若當(dāng)前位取值為0, 則表示刪除該特征. 采用這種編碼機(jī)制的解每一位都是離散二值的, 生成蜜源時(shí)可參考式(2).

2) 適應(yīng)值計(jì)算. 每個(gè)蜜源都有自己的適應(yīng)值, 用于評(píng)價(jià)蜜源的優(yōu)劣. 在密度聚類異常算法中, 蜜源的適應(yīng)值表示當(dāng)前參數(shù)和特征組合的檢測(cè)性能. 評(píng)價(jià)入侵檢測(cè)算法檢測(cè)性能的指標(biāo)很多, 常見(jiàn)的有檢測(cè)率、 誤報(bào)率和實(shí)時(shí)性等, 檢測(cè)率越高、 誤報(bào)率越低、 實(shí)時(shí)性越好的檢測(cè)算法越能成為優(yōu)秀入侵檢測(cè)系統(tǒng)的核心算法. 本文只考慮最主要的兩個(gè)指標(biāo)： 檢測(cè)率和誤報(bào)率, 其中檢測(cè)率的定義如式(7), 誤報(bào)率的定義如式(8). 由于檢測(cè)原理等方面的原因, 高誤報(bào)率是制約異常檢測(cè)算法發(fā)展的主要瓶頸, 高誤報(bào)率會(huì)導(dǎo)致入侵檢測(cè)系統(tǒng)頻繁地報(bào)警, 而多數(shù)警報(bào)是虛警, 會(huì)給系統(tǒng)管理員產(chǎn)生大量不必要的麻煩. 因此, 異常檢測(cè)算法檢測(cè)性能的評(píng)價(jià)原則是在保證檢測(cè)率的前提下, 盡量降低誤報(bào)率. 基于此, 適應(yīng)值定義為式(6), 并且本文設(shè)計(jì)了一個(gè)誤報(bào)率影響因子γ, 可以根據(jù)不同入侵檢測(cè)系統(tǒng)對(duì)誤報(bào)率的需求, 提高或降低誤報(bào)率影響因子γ, 以達(dá)到放大或縮小誤報(bào)率在整體適應(yīng)值上的影響.

3) 鄰域搜索. 引領(lǐng)蜂和跟隨蜂對(duì)蜜源的鄰域進(jìn)行搜索, 根據(jù)蜜源組成不同, 搜索也分為參數(shù)部分和特征部分. 參數(shù)部分是連續(xù)值, 搜索方法可按式(3)對(duì)Eps和Minipts兩個(gè)參數(shù)的鄰域進(jìn)行隨機(jī)搜索； 特征部分是離散值, 搜索方法可按式(4)對(duì)106維特征空間的鄰域進(jìn)行隨機(jī)搜索. 算法偽代碼如下.

WhileI

Initialize (xi) 根據(jù)式(1),(2)隨機(jī)初始化N個(gè)蜜源

Calculatefit(xi) 根據(jù)式(6)計(jì)算每個(gè)蜜源的適應(yīng)值

While Iter

Whilei

Whilej

Initialize(xij) 根據(jù)式(3),(4)鄰域搜索(引領(lǐng)蜂), 生成新蜜源

Calculatefit(xi) 根據(jù)式(6)計(jì)算新蜜源的適應(yīng)值

Maxfit(xi) 貪婪法選擇最優(yōu)解

Prob(xi) 根據(jù)概率選擇蜜源

Whilej

Initialize(xij) 根據(jù)式(3),(4)鄰域搜索(跟蹤蜂), 生成新蜜源

Calculatefit(xi) 根據(jù)式(6)計(jì)算新蜜源的適應(yīng)值

Maxfit(xi) 貪婪法選擇最優(yōu)解

If>MSN

Initialize(xi) 根據(jù)式(9),(10)隨機(jī)搜索(偵察蜂), 生成新蜜源

If iter>C

Current optimal solution 大于迭代次數(shù), 輸出當(dāng)前最優(yōu)解

3 實(shí)驗(yàn)結(jié)果與討論

3.1 數(shù)據(jù)來(lái)源

實(shí)驗(yàn)數(shù)據(jù)源于一臺(tái)紅米NOTE1手機(jī), 其配置為四核1.6 GHz, 內(nèi)存為2.0 GB, 操作系統(tǒng)為MIUI8.0.1.0(已root), 正常行為數(shù)據(jù)源于用戶日常使用行為收集, 異常行為主要來(lái)自于特定時(shí)間段內(nèi)對(duì)Android Malware Genome Project項(xiàng)目(http://www.malgenomeproject.org/)和卡飯論壇(http://bbs.kafan.cn/forum-31-1.html)APK病毒樣本數(shù)據(jù)收集. 特征選取參考文獻(xiàn)[3-4,6], 對(duì)于文獻(xiàn)的特征[6], 都已加入本文的數(shù)據(jù)中, 而由于安卓平臺(tái)版本更迭, 一些新特征也被加入, 數(shù)據(jù)包含106個(gè)特征, 主要分為8個(gè)類別： CPU、 內(nèi)存、 網(wǎng)絡(luò)、 SIM、 電話、 短信、 電池、 APP, 部分特征列于表1. 一條數(shù)據(jù)為一段時(shí)間內(nèi)特征的累計(jì)值或平均值, 時(shí)間片T=500 ms.

表1 部分特征列舉

3.2 結(jié)果分析

算法的重要參數(shù)有兩個(gè)： MSN和γ. MSN表示經(jīng)過(guò)一定次數(shù)(MSN次)的迭代后, 解并未發(fā)生明顯改善, 則重新進(jìn)行隨機(jī)搜索. 如果MSN取值過(guò)小, 則收斂速度慢, 隨機(jī)性變強(qiáng), 但搜索空間變大, 容易找到最優(yōu)解； 如果MSN取值過(guò)大, 則收斂速度快, 隨機(jī)性變?nèi)? 但容易陷入局部最優(yōu). 本文選取參數(shù)MSN=10, 這樣選取會(huì)導(dǎo)致收斂速度較慢, 但放出的偵查峰變多, 搜索空間變大. 為了提高檢測(cè)效果, 本文更注重最優(yōu)解, 收斂速度慢可容忍.γ為誤報(bào)率影響因子, 一般認(rèn)為異常檢測(cè)算法更注重誤報(bào)率, 在保證一定檢測(cè)率的基礎(chǔ)上, 更低的誤報(bào)率通常會(huì)有更好的用戶體驗(yàn), 因此本文選取γ=2.

圖2 適應(yīng)度與迭代次數(shù)的關(guān)系Fig.2 Relationship between fitness and number of iterations

圖2為適應(yīng)度與迭代次數(shù)關(guān)系曲線. 由圖2可見(jiàn): 每10次迭代輸出最后一次的適應(yīng)度值, 經(jīng)過(guò)240次迭代后, ABC-DBSCAN算法的適應(yīng)值收斂, 而經(jīng)過(guò)350次迭代后, GA-DBSCAN算法的適應(yīng)值收斂; 比較兩種算法的收斂值, ABC-DBSCAN算法的收斂值更好, 檢測(cè)效果更好; 比較兩種算法的收斂速度, ABC-DBSCAN算法的收斂速度更快, 能在更短的時(shí)間內(nèi)找到最優(yōu)解.

圖3為Minipts與迭代次數(shù)關(guān)系曲線. 由圖3可見(jiàn): 經(jīng)過(guò)260次迭代后, ABC-DBSCAN算法的Minipts收斂, 而經(jīng)過(guò)360次迭代后, GA-DBSCAN算法的Minipts收斂; 比較兩種算法的收斂速度, ABC-DBSCAN算法的收斂速度更快. 圖4為Eps與迭代次數(shù)關(guān)系曲線. 由圖4可見(jiàn): 經(jīng)過(guò)260次迭代后, ABC-DBSCAN算法的Eps收斂, 而經(jīng)過(guò)350次迭代后, GA-DBSCAN算法的Eps收斂; 比較兩種算法的收斂速度, ABC-DBSCAN算法的收斂速度更快. 表2為3種算法的性能比較.

圖3 Minipts與迭代次數(shù)的關(guān)系Fig.3 Relationship between Minipts and number of iterations

圖4 Eps與迭代次數(shù)的關(guān)系Fig.4 Relationship between Eps and number of iterations

算法DBSCANABC?DBSCANGA?DBSCAN檢測(cè)效果(檢測(cè)率/誤報(bào)率)/%72．5/8．183．2/5．474．2/7．8特征數(shù)量1062342

由表2可見(jiàn)： 與無(wú)優(yōu)化的原始算法相比, ABC-DBSCAN算法收斂后特征數(shù)降至23維, 檢測(cè)率更高, 誤報(bào)率更低； 與GA-DBSCAN算法相比, ABC-DBSCAN算法不僅特征數(shù)量更少, 而且檢測(cè)效果也有一定優(yōu)勢(shì).

綜上所述, 本文提出的基于人工蜂群優(yōu)化的密度聚類異常入侵檢測(cè)算法, 解決了基于密度聚類異常檢測(cè)算法的參數(shù)優(yōu)化和特征選擇問(wèn)題. 該算法能在較短的時(shí)間內(nèi)在106維的特征空間中找到最優(yōu)的特征子集, 并找到合適的Minipt和Eps, 使得算法的檢測(cè)性能達(dá)到最優(yōu). 此外, 誤報(bào)率影響因子的加入, 使算法在保證一定檢測(cè)率的基礎(chǔ)上誤報(bào)率更低.

[1] 楊宏宇, 朱丹, 謝豐, 等. 入侵異常檢測(cè)研究綜述 [J]. 電子科技大學(xué)學(xué)報(bào), 2009, 38(5): 587-592. (YANG Hongyu, ZHU Dan, XIE Feng, et al. The Research Summary of Intrusion Detection [J]. Journal of University of Electronic Science and Technology of China, 2009, 38(5): 587-592.)

[2] 胡亮, 任維武, 任斐, 等. 基于改進(jìn)密度聚類的異常檢測(cè)算法 [J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版), 2009, 47(5): 954-960. (HU Liang, REN Weiwu, REN Fei, et al. Anomaly Detection Algorithm Based on Improved Density Cluster [J]. Journal of Jilin University (Science Edition), 2009, 47(5): 954-960.)

[3] Shabtai A, Kanonov U, Elovici Y, et al. “Andromaly”: A Behavioral Malware Detection Framework for Android Devices [J]. Journal of Intelligent Information Systems, 2012, 38(1): 161-190.

[4] Reina A, Fattori A, Cavallaro L. A System Call-Centric Analysis and Stimulation Technique to Automatically Reconstruct Android Malware Behaviors [C]//EuroSec. New York: ACM, 2013: 1-6.

[5] Enck W, Gilbert P, Han S, et al. TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones [C]//10th Usenix Conference on Operating Systems Design & Implementation. New York: ACM, 2010: 393-407.

[6] Burguera I, Zurutuza U, Nadjm-Tehrani S. Crowdroid: Behavior-Based Malware Detection System for Android [C]//ACM Workshop on Security & Privacy in Smartphones & Mobile Devices. New York: ACM, 2011: 15-26.

[7] Karaboga D. An Idea Based on Honey Bee Swarm for Numerical Optimization [EB/OL]. [2016-11-01]. http://www.dmi.unict.it/mpavone/nc-cs/materiale/tr06_2005.pdf.

[8] Karaboga D, Ozturk C. A Novol Clustering Approach: Artificial Bee Colony (ABC) Algorithm [J]. Applied Soft Computing, 2011, 11(1): 652-657.

[9] Birant D, Kut A. ST-DBSCAN: An Algorithm for Clustering Spatial-Temporal Data [J]. Data & Knowledge Engineering, 2007, 60(1): 208-221.

[10] Ankerst M, Breuniq M M, Krieqel H P, et al. OPTICS: Ordering Points to Identify the Clustering Structure [J]. ACM Sigmod Record, 1999, 28(2): 49-60.

[11] Hinneburg A, Gabriel H H. DENCLUE 2.0: Fast Clustering Based on Kernel Density Estimation [C]//International Symposium on Advances in Intelligent Sata Analysis. New York: ACM, 2007: 70-80.