基于人工蜂群優(yōu)化的密度聚類異常入侵檢測算法

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

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

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

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

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

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

1 預(yù)備知識

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

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

(1)

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

(2)

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

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

(3)

(4)

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

(5)

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

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

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

(6)

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

(7)

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

(8)

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

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

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

(9)

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

(10)

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

2 主要算法

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

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

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

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

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

WhileI

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

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

While Iter

Whilei

Whilej

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

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

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

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

Whilej

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

Calculatefit(xi) 根據(jù)式(6)計算新蜜源的適應(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 實驗結(jié)果與討論

3.1 數(shù)據(jù)來源

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

表1 部分特征列舉

3.2 結(jié)果分析

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

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

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

圖3為Minipts與迭代次數(shù)關(guān)系曲線. 由圖3可見: 經(jīng)過260次迭代后, ABC-DBSCAN算法的Minipts收斂, 而經(jīng)過360次迭代后, GA-DBSCAN算法的Minipts收斂; 比較兩種算法的收斂速度, ABC-DBSCAN算法的收斂速度更快. 圖4為Eps與迭代次數(shù)關(guān)系曲線. 由圖4可見: 經(jīng)過260次迭代后, ABC-DBSCAN算法的Eps收斂, 而經(jīng)過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檢測效果(檢測率/誤報率)/%72．5/8．183．2/5．474．2/7．8特征數(shù)量1062342

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

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

[1] 楊宏宇, 朱丹, 謝豐, 等. 入侵異常檢測研究綜述 [J]. 電子科技大學(xué)學(xué)報, 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)密度聚類的異常檢測算法 [J]. 吉林大學(xué)學(xué)報(理學(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.