基于Spark框架的分布式入侵檢測方法

左曉軍，董立勉，曲 武

（1.河北電力科學研究院，河北 石家莊050021；2.北京啟明星辰信息安全技術有限公司核心研究院，北京100193；3.清華大學 計算機科學與技術系，北京100084）

0 引 言

入侵檢測系統對計算主機或網絡傳輸進行即時監視，分析入侵特征，入侵一般可以定義為試圖威脅計算機系統或網絡的可信性、完整性、可用性，以及繞過安全機制的行為。具體表現為，攻擊者通過網絡以非授權的方式訪問系統，系統授權用戶誤用授權或是試圖獲得額外權限。入侵檢測系統 （intrusion detection systems，IDS）是一類能夠自動檢測并分析入侵的軟件或硬件產品，與使用靜態檢測技術的防火墻不同，IDS使用了一種被動的積極防護技術，能夠高效地提供網絡攻擊檢測，很大程度上幫助網絡管理員提高網絡安全管理能力，完善網絡安全架構的整體布局。

近幾年，利用機器學習技術［1－5］解決入侵檢測問題已吸引了越來越多的關注。作為機器學習的一個重要應用領域，其目標是減輕海量審計數據的分析壓力、實現數據流實時分析，以及優化檢測規則性能。在該領域，不同的研究者根據應用分類提出了相應的算法，例如分類、聚類、序列分析、時序分析、預測、關聯規則等，這些算法的應用使得入侵檢測效率得到很大提高，但是這些算法卻無法解決海量數據的實時處理。為了滿足入侵檢測數據的規模性，分析的實時性和分析算法可擴展性的要求，基于Spark框架［6］和位置敏感哈希算法，本文提出一種新穎的分布式數據流聚類方法，DSCLS （distributed stream clustering method based on the local sensitive Hash and the Spark framework）。理論分析和實驗結果表明，與主流的數據流聚類算法D－Stream 相比，DSCLS方法能夠有效提高入侵檢測率并降低誤報率，在時間性能和擴展性方面更有優勢。

1 相關工作

1.1 入侵檢測系統

在網絡安全領域，防火墻通常用來保護內部網免受非法用戶的侵入，而IDS通過監視網絡流量，檢測網絡是否受到攻擊，如對系統的DDoS攻擊。因此，IDS是完整網絡安全系統的一個重要組成部分，它并不能完全保證安全，但可以通過使用安全策略，漏洞評估，數據加密，用戶認證，訪問控制等技術，大大增強網絡的安全性。IDS 也可以用于監視網絡流量，從而檢測網絡攻擊，如對系統的DDoS攻擊。IDS的檢測和響應仍然是應對企業內外網絡威脅的唯一積極的手段。

對于網絡入侵檢測，主流的檢測技術主要分為4 類，分別為異常檢測、誤用檢測、目標監控和隱式探測，如圖1所示，定義如下。

圖1 IDS分類

（1）異常檢測［7］：其目的是發現異常模式或行為。IDS首先根據用戶的正常使用行為建立基線模式，對于任何偏離基線模式的行為標注為可疑的入侵行為。對于不同的情況，異常的認定通常是變化的。一般情況下，事件的發生頻率低于或高于正常統計值2個標準偏差，則被標注為異常事件。根據偏離正常行為自動識別異常，這種技術能夠識別新出現的入侵行為，其缺點是高誤報率。因此，異常檢測的關鍵在于如果根據用戶的行為建立基線，并且以較低的誤報率檢測 “入侵”；

（2）誤用檢測［8，9］：也稱為特征檢測，是一種基于特征的監督學習方法，該方法將數據集標注為 “正常”或 “入侵”，使用標注數據模式訓練分類器，進而分類未標注的數據。只要數據被正確標注，這類技術能夠根據包含新類型攻擊的不同輸入數據自動重新生成入侵檢測模型。與異常檢測不同，誤用模型能夠被自動建立，比人工建立的模型更為復雜，相應的檢測精度也更為準確。因此，誤用檢測在檢測已知攻擊和變種方面具有較高的精度。其缺點是該技術不能檢測未知入侵，過于依賴于專家提取的特征。這類方法使用明確的、已知的入侵行為模式去預測和檢測隨后的相似行為，這些特定的模式也被稱為特征。因此，誤用檢測的主要特點是使用標注的數據集構建分類模型，樣本僅僅被標注為正常和攻擊兩類，與特征檢測相似，時空代價較高，而且不能夠檢測到新出現的威脅；

（3）目標監控：這類技術并不主動檢查異常和誤用，僅僅檢查對特定文件的修改操作。這是一種糾正的控制方法，識別未經授權的行為，并進行修正。檢查特定文件的編輯操作，通常是將當前文檔預先計算的加密哈希與新哈希進行比較，而且這種比較可以按照預定周期進行，實現簡單，監控范圍可以定義，且無需系統管理員頻繁管理。

（4）隱式探測：這類技術通常選擇在一段時間內執行攻擊者的任務，通過系統收集各種不同的數據，檢查任何一個有計劃的有策略的攻擊。本質上，這類技術聯合使用了異常檢測和誤用檢測去識別異常行為。

根據應用檢測技術的場景不同，IDS分為基于網絡的IDS和基于主機的IDS，如圖1所示：

（1）基于網絡IDS引擎：該引擎通常要求把網卡設置成混雜模式，以此來檢測網絡上的數據包，分析攻擊模式，據此判斷非法或異常行為，并可以自動執行告警和阻斷。該引擎的優點具有檢測速度快、檢測范圍廣、占用資源少，缺點是不能審計主機信息。在該技術中，通常使用異常檢測、誤用檢測和混合檢測技術，相關技術能力比較見表1。

表1 基于網絡入侵檢測方法比較

（2）基于主機的IDS引擎：任何入侵企圖 （或者成功的入侵）都會在監測日志、文件日志、登陸日志或其它主機上的文件中留下痕跡，基于主機的IDS引擎通過分析系統的審計日志文件發現異常行為。該引擎的優點是配置靈活、檢測粒度精細、性價比高。由于該引擎僅對抵達主機的數據進行檢測，缺乏對網絡異常行為的檢測。

顯然，這兩種檢測引擎具有明顯的互補特性，基于網絡的IDS能夠客觀地反映當前網絡狀態，而基于主機的IDS能夠監測主機中的各種異常行為。

1.2 機器學習

在入侵檢測領域，利用機器學習相關技術解決檢測問題已經被廣泛研究。其中，用戶行為特征提取部分主要使用分類、關聯分析和序列模式挖掘等方法，學習過程主要采用監督學習和無監督學習方法：

（1）監督學習方法：該方法主要目標是建立一個預測模型，分類或標注新到來的數據樣本。該分類器使用已經標注好的數據進行訓練，然后分類未標注的數據。訓練樣本使用輸入向量和預期輸出所組成。函數的輸出可以是一個連續的值，或是預測一個分類標簽。目前最廣泛被使用的分類器有人工神經網絡、支持向量機、最近鄰居法、遺傳算法、Fuzzy分類、Gaussian算法、貝葉斯模型、決策樹和RBF classifier等。通常，IDS技術中誤用檢測技術大量使用監督學習方法。

（2）無監督學習方法：數據聚類作為最重要的無監督學習方法，以相似性為基礎，使用不同的算法將未標注的數據分成若干簇，同一個聚類簇中的數據具有更多的相似性。對于先驗信息較少的情況下，數據聚類是非常有效的。因此，聚類技術常被用于異常檢測中。

目前，存在較多的聚類方法可以用于異常檢測，為了能夠實時檢測不斷到來的數據，通常使用數據流聚類方法。而一個有效的數據流聚類算法必須解決以下兩個挑戰：①在一路算法中，對于每個數據點，算法都可以在無需遍歷整個數據集的情況下形成聚類簇；②隨著新數據點的到來，算法必須能夠管理聚類簇的增量更新。大部分存在的聚類算法都局限k－means的變種［10］，這類算法并不能夠處理任意形狀數據簇。D－Stream 算法［11］，是一種利用密度和網格產生高質量聚類結果的數據流聚類算法，性能優于主流的數據流聚類算法。對于高維數據流，特別是對于入侵檢測中的高維數據流，D－Stream 算法所需要的網格數量會變得異常大，導致這種情況下算法的總體性能較低。為了克服這種限制，本文提出一種新穎的數據流聚類算法，DSCLS（distributed stream clustering method based on the local sensitive hash and the spark framework）算法。在Spark框架基礎上，DSCLS算法通過使用位置敏感哈希機制 （locality sensitive hashing，LSH）［12－14］，可以對海量高維實時數據流進行快速聚類。

2 DSCLS方法

2.1 位置敏感哈希方法

LSH 算法首先由Indyk等［12－14］提出，用來解決主存儲器中的近鄰相似性檢索問題，能夠證明其對數據規模n具有線性時間復雜度。它的關鍵思想是使用一組哈希函數，確保距離近的點比距離遠的點沖突的概率大，因此原始數據空間中距離相近的點將被映射到同一個桶中，聚成一類，從而減少了距離計算，加快聚類時間。其形式化定義如下：

定義位置敏感哈希 （LSH），對于任意數據點p，q∈Rd，函數族H ＝｛h：S →U｝被稱為（r1，r2，p1，p2）對距離函數D（∥p－q∥）敏感，滿足條件

為了使一個位置敏感哈希函數族可用，必須滿足條件p1＞p2和r1＜r2，D 為距離函數，可以是歐式距離、曼哈頓距離等，S為點集域。

本文構造LSH 使用的哈希函數族H 是基于P－Stable分布，針對p范式度量空間 （p＝2時為歐式距離）：

2.2 DSCLS算法

DSCLS算法流程如圖2所示，包含一個實時處理的在線組件和一個基于Spark框架的近實時組件。當一個新數據點到來時，在線組件被執行。首先調用概要獲取函數Fsyn（x）［15］以獲取d維數據流特征向量pi，利用LSH 算法將pi投影到位置敏感哈希表相應的桶b中，最后返回Xt個聚類簇。從Xt中選出包含數據點最多的前Xmax個聚類簇作為候選聚類簇。而近實時組件以一定的時間間隔周期并發執行。調用Xmax－median 方法獲得聚類簇質心Ccen，分別計算新到的數據流特征向量pi到Xmax個質心之間的距離范數，獲取最小距離范數dmin的聚類簇，若dmin≤dth，則將pi歸為dmin對應聚類簇，否則建立新的聚類簇。近實時組件通過使用Spark框架實現分布式計算。聚類過程的并發執行很大程度上減少計算時間，特別是對于海量高維數據具有較好的可擴展性。

2.2.1 在線組件

在線組件主要包括4 個階段，算法流程如圖2 所示，具體流程如下：

（1）為獲取對數據流的概要描述，本文使用文獻 ［15］中提出的滑動窗口模型對數據流進行分析。其基本思想是，僅僅基于最近的數據做出聚類決策。即，在每個時刻t，一個新的數據點到來時間為ta，tc為當前時間，λ為衰減因子，使用距離范數相關系數dco＝λ（tc－ta）控制數據點聚類過程；

圖2 DSCLS算法流程

（2）計算特征向量到各聚類簇中心距離，根據實際需求，判斷距離是否低于設定的閾值 （或是最小），若滿足條件，則將該特征向量 （關聯數據流）與相應的聚類簇關聯；

（3）LSH 映射階段，選擇l 個函數，gj（pi）＝（h1，j（pi），…，hk，j（pi）），從函數族H 中以獨立、一致隨機的方式來選擇k個ht，j（1≤t≤k，1≤j≤l），然后使用這些函數對數據點進行哈希。將特征向量集合中每一個數據點pi映射到桶gj（pi）中，1≤j≤l，進行構建位置敏感哈希數據結構。由于桶的總數過大，不可能精確存儲所有可能的桶，僅存儲非空桶。通過該階段的映射 （總計l×k個位置敏感哈希函數），可以得到l個k 維哈希映射值；

（4）二次哈希階段，對k維的映射向量計算二次哈希，結果為一維哈希索引值。其中，二次哈希算法選擇MD5算法。基于兩方面考慮，其一，可以把一個任意維度的向量映射為單個值，降低存儲代價；其二，MD5算法的碰撞概率較低，能夠保證第一階段產生的不同k維哈希值仍然被映射到不同索引值上。最后，每個索引值構成一個哈希桶，將特征向量pi的HDFS 物理地址鏈接到桶上，形成一個倒排表；

通過階段 （3）和 （4），LSH 方法為特征向量集合提供了一個索引結構來確定近似最近鄰。對于特征向量pi，LSH 方法利用哈希表返回相對小的候選聚類簇，這些聚類簇表示與目標特征向量 （例如，聚類簇質心）以較高概率相似的特征向量集合。LSH 返回的可變的聚類簇數Xt，這個參數主要依賴于LSH 表中簇的總數、相似性和構建LSH 的參數。為確保有限的處理時間，從Xt中選出包含特征向量最多的前Xmax個聚類簇作為候選聚類簇Ccan，Ccan的選擇使用Top－k算法，最后返回候選聚類簇Ccan；

2.2.2 基于Spark的聚類算法

隨著網絡帶寬的不斷提高，數據流速越來越大，集中式的數據流聚類過程由于內存限制變得不可行。基于Spark計算框架，本文提出將近實時組件的聚類過程并行化，以適應海量高維、高速數據的聚類需求。針對一個較長時間段數據流的聚類，由于數據量變得很大，聚類特征向量需要迭代獲取聚類質心和距離計算，時間復雜度較高，利用Spark機制啟動Spark－Map任務并行化獲取聚類簇質心，在Spark－Reduce階段將特征向量分配到相應的候選聚類簇中，利用新到的特征向量到聚類簇質心的精確距離進行篩選。SCluster算法流程如算法1所示。

3 性能評估

本文通過實驗評估驗證了DSCLS算法的性能。實驗中選用的數據集來自KDD Cup 1999［16］入侵檢測數據集。該數據集來自MIT 林肯實驗室所管理的局域網流量中TCP連接記錄，每個記錄都被分為正常連接和異常連接，異常連接又被進一步分為22 類。這個數據集包含494020個連接記錄，每個連接記錄具有42 個特征，如文獻 ［17，18］所示，其中34個連續特征能夠被用來做聚類分析。在本文的實驗中，使用該數據集的子集，15000個數據點，每個數據點表示一個時間段數據流的特征向量，即表示一個鏈接，特征值將會被泛化，最大值為1。接下來，主要介紹DSCLS算法的實驗評估細節，然后基于實驗結果，評估DSCLS算法的性能和局限性。

?

3.1 實驗環境

實驗環境使用一臺Master管理節點服務器，4臺普通PC計算節點，具體軟硬件配置如下：

（1）Master管理節點服務器：英特爾至強處理器四核E3－1220 3.1Ghz，內存8G，硬盤1T；

（2）普通PC 計算節點：英特爾處理器四核I3－2120，3.3Ghz，內存4G，硬盤1T；

（3）軟件系統：操作系統，Cent OS 6.4，64位；開發環境，Eclipse 3.6.1 和 Spark Eclipse 插件；Apache Spark 0.9.1。

3.2 DSCLS算法參數、性能權衡及評價標準

令數據集規模為n，維度為d，近似因子為c ＝（1＋ε），計算節點的個數為R，投影個數為k、哈希函數個數為L、投影區域寬度為w。除非特別指出，本文使用的數據流速v設定為每秒200個數據點，衰減因子λ ＝0.992，L ＝20，k＝10，ε＝0.6，w ＝6，R ＝4，n＝1.5×104和d＝34。在數據流聚類中，SSQ 和聚類純度是常用的聚類性能評估指標［17，18］。此外，本文還選用聚類簇的個數與基準數據的差異、檢測率和誤報率來評估算法的檢測性能。

3.3 實驗結果

在本節中，使用3 個性能指標 （距離平方和 （sum of squared distance，SSQ），聚類純度和簇個數）評估和比較DSCLS和D－Stream 算法的性能。時間軸表示評估過程中的數據流流逝時間。數據流速為200，數據集的規模為15000個數據點，數據流持續時間為75s，隨機選取評估時間點為15，30，45，60，75，時間間隔為15s。如圖3 （a）所示，對于DSCLS 和D－Stream 算法的平均SSQ 性能評估，這兩個算法有接近相似的SSQ 均值。由于SSQ 均值坐標使用對數評估，因此一個數量級的差異性可以忽略。如圖3（b）所示，對于DSCLS和D－Stream 算法的聚類純度評估，這兩個算法都獲得了相對較高的聚類純度 （幾乎都大于85%），總體上，DSCLS算法的聚類純度高于D－Stream 算法，但二者的最大差異不到5%。值得注意的是，在每個時間單元生成聚類簇的個數很大程度上影響著聚類純度和平均SSQ 的值。顯然，接近真實聚類簇的個數，將會導致較小的平均SSQ 和較高的聚類純度。因此，本文設計了實驗探索DSCLS和D－Stream 算法生成的聚類簇個數，并且與基準聚類簇個數進行了比較，如圖4所示。基準聚類簇個數是有人工標注的數據集真實聚類簇的數目，DSCLS算法生成聚類簇的數據更接近基準值，這也可以解釋DSCLS算法在聚類純度指標上高于D－Stream 算法。基于假設，一個真實的網絡環境，數據流中包含正常連接數目要遠大于攻擊數，因此，小的聚類簇被認為包含攻擊，大的聚類簇被認為包含正常連接。但也會經常出現小聚類簇中包含正常連接，大簇中包含攻擊連接。本文設計了實驗，評估DSCLS算法在此情況下的性能，即準確率和誤報率。圖5展示了在15，30，45時間點DSCLS算法的檢測準確率和誤報率，縱坐標表示數據集包含攻擊的聚類簇數，圖中可知，隨著含有攻擊的聚類簇個數增大，檢測準確率會提高，而誤報率也會隨之增大。而且，隨著聚類簇的總數增大，準確率提高，誤報率降低，但聚類簇的個數不能無休止的降低，因此選擇適合的聚類簇的個數是非常重要的。

圖3 DSCLS和D－Stream算法的平均SSQ和聚類純度對比

圖4 DSCLS、D－Stream 算法生成的聚類簇個數對比

圖5 DSCLS算法檢測正確率和誤報率

4 結束語

聚類分析作為一種無監督學習方法，已廣泛應用于數據分析、入侵檢測系統中。而實際入侵檢測數據往往具有高維、高速、大數據的特征，如何聚類這類數據對于提高檢測效率起到了很大的作用，目前在這方面的研究還相對較少。本文面向云計算環境，基于Spark框架，設計了一個基于LSH 的分布式數據流聚類算法，DSCLS，實現了數據流聚類的在線算法和離線算法。通過實驗分析了DSCLS算法的性能，進一步驗證DSCLS聚類方法有效性，與傳統的數據流聚類框架D－Stream 算法相比，在高效并行處理、可擴展性方面和聚類結果質量方面，DSCLS算法具有一定優勢。本文所提出的基于Spark數據流聚類算法，并將該算法用于網絡入侵檢測領域是一個初步嘗試，未來還需要進一步完善，例如通過自適應的參數配置進一步提高數據流聚類算法的性能，同時融合多種特征，并調整適合的LSH 參數來達到更好的聚類效果。

［1］Wang Gang，Hao Jinxing，Ma Jian，et al.A new approach to intrusion detection using artificial neural networks and fuzzy clustering ［J］.Expert Syst Appl，2010，37 （9），6225－6232.

［2］Rouhi R，Keynia F，Amiri M.Improving the intrusion detection systems’performance by correlation as a sample selection method ［J］.Journal of Computer Sciences and Applications，2013，1 （3）：33－38.

［3］Song J，Zhu Z，Scully P，et al.Selecting features for anomaly intrusion detection：A novel method using fuzzy C means and decision tree classification ［M］／／Cyberspace Safety and Security.Springer International Publishing，2013：299－307.

［4］Idrees F，Rajarajan M，Memon AY.Framework for distributed and self－healing hybrid intrusion detection and prevention system ［C］／／International Conference on ICT Convergence.IEEE，2013：277－282.

［5］Kim G，Lee S，Kim S.A novel hybrid intrusion detection method integrating anomaly detection with misuse detection［J］.Expert Systems with Applications，2014，41 （4）：1690－1700.

［6］Zaharia M，Chowdhury M，Franklin MJ，et al.Spark：Cluster computing with working sets［C］／／Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing，2010.

［7］Chauhan A，Mishra G，Kumar G.Survey on data mining techniques in intrusion detection ［M］.Lap Lambert Academic Publ，2012.

［8］Sabahi F，Movaghar A.Intrusion detection：A survey ［C］／／3rd International Conference on Systems and Networks Communications.IEEE，2008：23－26.

［9］Visumathi J，Shanmuganathan KL，Junaid KAM.Misuse and anomaly－based network intrusion detection system using fuzzy and genetic classification algorithms ［J］.Fuzzy Systems，2012，4 （4）：137－141.

［10］Shahnewaz SM，Asikur Rahman Md，Hasan Mahmud.A self acting initial seed selection algorithm for k－means clustering based on convex－hull［J］.Informatics Engineering and Information Science，2011，252 （5）：641－650.

［11］Chen Y，Tu L.Density－based clustering for real－time stream data［C］／／In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：133－142.

［12］Indyk P，Motwani R.Approximate nearest neighbors：Towards removing the curse of dimensionality ［C］／／Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing.New York：ACM，1998：604－613.

［13］Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing ［C］／／Proceedings of the 25th International Conference on Very Large Data Bases.San Francisco：Morgan Kaufmann Publishers Inc，1999：518－529.

［14］Datar M，Immorlica N，Indyk P，et al.Locality－sensitive hashing scheme based on p－stable distributions ［C］／／Proceedings of the Twentieth Annual Symposium on Computatio－nal Geometry.New York：ACM，2004：253－262.

［15］Li Z，Gao Y，Chen Y.HiFIND：A high－speed flow－level intrusion detection approach with DoS resiliency ［J］.Computer Networks，2010，54 （8）：1282－1299.

［16］KDD Cup 1999Data ［DB／OL］.http：／／kdd.ics.uci.edu／databases／kddcup99／kddcup99.html，1999.

［17］Aggarwal C，Han J，Wang J，et al.A framework for clustering evolving data streams［C］／／Proceedings of the 29th International Conference on Very Large Databases，2003：81－92.

［18］Aggarwal C，Han J，Wang J，et al.A framework for projected clustering of high dimensional data streams ［C］／／Proceedings of the International Conference on Very Large Databases，2004：852－863.

［19］Xin Sun，Yu Jiao.PGrid：Parallel grid－based data stream clustering with spark ［R］.Reports，OAK Ridge National Laboratory Oak Ridge，Applied Software Engineering Research Group，2009.