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

任維武, 張波辰, 底曉強, 盧奕南

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

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

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

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

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

1 預備知識

初始化蜜源： 在使用ABC算法求解優化時, 每個蜜源都代表問題的一個優化組合解. 設ABC算法隨機初始化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個待優化參數. 當xij為離散二值時, 參數xij表示為

(2)

領域搜索： 引領蜂和跟隨蜂對蜜源領域進行搜索, 蜜源的每個參數均被搜索, 其搜索過程可表示為

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

(3)

(4)

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

(5)

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

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

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

(6)

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

(7)

其中: TAs表示正確報警的入侵數; Is表示總的入侵樣本數. 誤報率：

(8)

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

隨機搜索： 如果經過最大限制次搜索后, 解未得到改善, 則引領蜂變為偵察蜂, 并隨機產生一個新解, 可表示為

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

(9)

當xij為離散二值時, 新解可表示為

(10)

MSN表示算法經過一定次數的迭代后, 適應值沒有改善, 則該蜜源被放棄.

2 主要算法

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

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

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

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

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

WhileI

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

Calculatefit(xi) 根據式(6)計算每個蜜源的適應值

While Iter

Whilei

Whilej

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

Calculatefit(xi) 根據式(6)計算新蜜源的適應值

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

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

Whilej

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

Calculatefit(xi) 根據式(6)計算新蜜源的適應值

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

If>MSN

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

If iter>C

Current optimal solution 大于迭代次數, 輸出當前最優解

3 實驗結果與討論

3.1 數據來源

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

表1 部分特征列舉

3.2 結果分析

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

圖2 適應度與迭代次數的關系Fig.2 Relationship between fitness and number of iterations

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

圖3為Minipts與迭代次數關系曲線. 由圖3可見: 經過260次迭代后, ABC-DBSCAN算法的Minipts收斂, 而經過360次迭代后, GA-DBSCAN算法的Minipts收斂; 比較兩種算法的收斂速度, ABC-DBSCAN算法的收斂速度更快. 圖4為Eps與迭代次數關系曲線. 由圖4可見: 經過260次迭代后, ABC-DBSCAN算法的Eps收斂, 而經過350次迭代后, GA-DBSCAN算法的Eps收斂; 比較兩種算法的收斂速度, ABC-DBSCAN算法的收斂速度更快. 表2為3種算法的性能比較.

圖3 Minipts與迭代次數的關系Fig.3 Relationship between Minipts and number of iterations

圖4 Eps與迭代次數的關系Fig.4 Relationship between Eps and number of iterations

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

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

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

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