安全態(tài)勢感知系統(tǒng)中K-Means算法的并行化研究

江佳希，謝穎華

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海201620)

0 引言

隨著大數(shù)據(jù)時代的來臨，SQL注入攻擊、XSS攻擊等網(wǎng)絡(luò)安全事件層見疊出，給網(wǎng)絡(luò)安全帶來了巨大的挑戰(zhàn)。日志記錄著設(shè)備運行狀態(tài)，各種安全事件都會在系統(tǒng)中留下日志記錄，通過對日志進行分析，可以挖掘重要信息，實時掌握網(wǎng)絡(luò)安全狀況，既可做到事前防護，又可做到事后追本溯源及責(zé)任追查。

本文設(shè)計的安全態(tài)勢感知系統(tǒng)將采集到的日志文件送至分布式文件系統(tǒng)HDFS進行存儲，在Hadoop架構(gòu)上將改進的K-Means算法和MapReduce高效的并行計算能力相結(jié)合，對存儲的日志進行聚類和分析。安全態(tài)勢感知系統(tǒng)可以實時監(jiān)控網(wǎng)絡(luò)安全態(tài)勢，實現(xiàn)日志分析追責(zé)，有效地減少網(wǎng)絡(luò)安全事故的發(fā)生。系統(tǒng)采用高可用部署模式，具有可靠、易拓展、易維護以及可視化的特點[1]。

1 系統(tǒng)總體架構(gòu)及工作原理

1.1 總體架構(gòu)

基于Hadoop大數(shù)據(jù)架構(gòu)的安全態(tài)勢感知系統(tǒng)通過對安全日志的實時分析,可以對網(wǎng)絡(luò)安全環(huán)境實現(xiàn)實時監(jiān)測。針對現(xiàn)存威脅，系統(tǒng)以實時和統(tǒng)計的方式對安全告警進行展現(xiàn)，針對未知威脅，系統(tǒng)從外部威脅和脆弱性兩個方面進行預(yù)警。

安全態(tài)勢平臺的總體軟件架構(gòu)由數(shù)據(jù)層、分析層、展示層三部分組成。數(shù)據(jù)層處于整個系統(tǒng)框架的底層，主要完成的是數(shù)據(jù)源的采集與存儲，將不同來源的日志切成大小相同的數(shù)據(jù)片后送到各個節(jié)點。分析層調(diào)用Map和Reduce函數(shù)庫將任務(wù)進行拆分作并行計算，結(jié)合K-Means聚類算法進行聚類結(jié)果分析。在展示層，用戶可以用Hive語句查詢結(jié)構(gòu)化的數(shù)據(jù)，對于非結(jié)構(gòu)化的數(shù)據(jù)，可以用MapReduce進行分析[2]。系統(tǒng)架構(gòu)圖如圖1所示。

1.2 系統(tǒng)工作原理

安全態(tài)勢感知系統(tǒng)包含四個模塊，分別是數(shù)據(jù)采集、數(shù)據(jù)處理、安全分析以及態(tài)勢呈現(xiàn)模塊。系統(tǒng)的功能模塊圖如圖2所示。

數(shù)據(jù)采集模塊用Flume采集器收集系統(tǒng)日志，利用web+ssh獲取采集程序的狀態(tài)，將不同數(shù)據(jù)來源的日志數(shù)據(jù)進行高效收集、聚合、移動，最后存儲到一個中心化數(shù)據(jù)存儲系統(tǒng)HDFS中，實現(xiàn)各種網(wǎng)絡(luò)設(shè)備、安全設(shè)備、服務(wù)器、應(yīng)用服務(wù)等設(shè)備的日志采集，在HDFS底層，對日志進行切片，一般默認切片大小為64 MB，存放至不同的數(shù)據(jù)節(jié)點。數(shù)據(jù)處理模塊采用kafka集群，對采集到的數(shù)據(jù)進行預(yù)處理，預(yù)處理過程中首先對數(shù)據(jù)進行清洗過濾，通過指定過濾規(guī)則，將重復(fù)數(shù)據(jù)、噪聲點以及不合理的數(shù)據(jù)從數(shù)據(jù)集中去除，然后對異構(gòu)原始數(shù)據(jù)作格式統(tǒng)一處理，最后補齊字段、做數(shù)據(jù)標準化等處理，并將標準數(shù)據(jù)加載到HDFS系統(tǒng)中。安全分析模塊是安全態(tài)勢感知系統(tǒng)的核心，通過制定風(fēng)險模型，對預(yù)處理后的數(shù)據(jù)集進行聚類和分析，將并行化編程模型MapReduce與改進的K-Means聚類算法相結(jié)合，完成對日志的聚類分析并形成追責(zé)證據(jù)鏈，可以識別惡意掃描、SQL注入攻擊、XSS攻擊等威脅事件在內(nèi)的多類安全事件。態(tài)勢呈現(xiàn)模塊呈現(xiàn)將安全數(shù)據(jù)按各種場景分析之后得出的結(jié)果，利用各類圖表直觀地展現(xiàn)數(shù)據(jù)分析結(jié)果[3]。

2 K-Means算法及其改進

2.1 K-Means算法

K均值聚類算法(K-Means Clustering Algorithm)由James MacQueen在1967年提出，基于相似度和距離這兩個方面的技術(shù)已經(jīng)非常成熟，而且由于實現(xiàn)簡單、收斂速度快，K-Means算法常用于日志挖掘。K-Means算法的主要思想是將用戶與服務(wù)器交互的各維數(shù)據(jù)作為特征進行聚類，對一部分非數(shù)值類型的特征需要進行轉(zhuǎn)化和標記，使其適用于與質(zhì)心之間的距離的計算[4]。傳統(tǒng)的K-Means算法將用戶的數(shù)據(jù)集O和K值作為輸入，隨機自動選取K個聚類中心，通過距離計算將數(shù)據(jù)點劃分到離它最近的聚類中心所在的簇，直至收斂，輸出K個簇。算法描述如下：

(1)輸入 K值和數(shù)據(jù)集 O。

(2)從數(shù)據(jù)集O中選取K個值作為初始聚類中心，記為 X1，X1，…，XK，選取方式為隨機選取。

(3)將已經(jīng)被選為聚類中心的點從數(shù)據(jù)集中去除，新的數(shù)據(jù)集記為 O1。

(4)對于 O1中的數(shù)據(jù)點，計算其到K個初始聚類中心的歐式距離，按照就近原則將數(shù)據(jù)點劃分到距離最近的簇中。

(5)K個簇初步劃分完成后，計算簇內(nèi)均值，記為新的聚類中心，重新計算數(shù)據(jù)點到中心點的距離，進行新一輪的劃分，直至通過準則函數(shù)判斷聚類中心點收斂，聚類停止，否則迭代更新中心點。

(6)輸出 K個類簇。

2.2 改進K-Means算法

安全態(tài)勢感知系統(tǒng)要實現(xiàn)實時告警和威脅預(yù)測功能，要求算法具有可伸縮性，不管是處理小數(shù)據(jù)集還是大數(shù)據(jù)集，都要具有高效的特點。同時，安全態(tài)勢感知系統(tǒng)要求算法準確率高，對于干擾點能準確識別并去除[5]。

傳統(tǒng)的K-Means算法采用單機部署，執(zhí)行效率低下，且K-Means的性能與聚類中心的位置關(guān)系很密切，初始聚類中心的選擇極大程度地影響聚類效果。由于傳統(tǒng)K-Means算法在選取初始聚類中心的隨意性，假如將孤立點選為聚類中心，聚類準確性會大打折扣，同時算法循環(huán)迭代次數(shù)也會增多，且少量的孤立點會使得類內(nèi)均值計算出現(xiàn)大的偏差。

圖1 系統(tǒng)架構(gòu)圖

圖2 功能模塊圖

針對K-Means在數(shù)據(jù)處理方面的缺陷，本文提出一種改進K-Means算法。新算法在去除孤立點干擾、尋找合適的聚類中心、判斷中心點收斂的方式等方面做出了改進，改善了傳統(tǒng)K-Means算法耗時長、執(zhí)行效率低等問題[6]。改進后的算法流程圖如圖3所示。

圖3 改進K-Means算法流程圖

改進K-Means算法描述如下：

(1)設(shè)數(shù)據(jù)集中數(shù)據(jù)量為 m，定義 Ai為數(shù)據(jù)點到數(shù)據(jù)集中其他點的距離之和，計算公式如下：

掃描數(shù)據(jù)集，尋找符合 Ai＞min Ai+的數(shù)據(jù)點，由于數(shù)據(jù)點距離和遠遠大于均值，將其認為是孤立點，從數(shù)據(jù)集中去除。min Ai為距離和的最小值，數(shù)據(jù)點到數(shù)據(jù)集中其他點的距離和越小，證明該點周圍聚集的數(shù)據(jù)點越多，即密度越大。記去除孤立點后得到的新的數(shù)據(jù)集為P，新數(shù)據(jù)集中的數(shù)據(jù)量記為q。

(3)將符合Ai＜-min Ai且距 X1最遠的數(shù)據(jù)點 X2作為第二個聚類中心，確保X2和 X1來自于兩個不同的簇，同時將X2從集合P中去除。此處將符合Ai＜-min Ai的數(shù)據(jù)點定義為高密度點。

(4)在高密度區(qū)域，即符合 Ai＜min Ai條件的數(shù)據(jù)集中尋找與前兩個數(shù)據(jù)點距離之和最遠的數(shù)據(jù)點X3作為第三個聚類中心，并將X3從P集合中刪除。

(5)依次類推，在高密度區(qū)域?qū)ふ遗c已確定的簇中心距離之和最大的數(shù)據(jù)點，同時將這些點從集合P中去除，直到K個聚類中心搜尋完畢。

(6)對于P中剩余的數(shù)據(jù)點，分別計算其到K個中心的歐式距離，根據(jù)就近劃分原則將數(shù)據(jù)點都劃分到離它最近的簇中。

(8)各個飽和類簇分別計算簇內(nèi)各個維度的算術(shù)平均值，形成新的聚類中心。

(9)計算新一輪迭代和上一輪迭代的DBI指標值，分別用 DBIn和 DBIo表示，若 DBIn＜DBIo，則開始新一輪的迭代，直到 DBIn＞DBIo為止。DBI計算方式如下：

其中，Si代表第i個聚類中數(shù)據(jù)點與聚類中心的標準誤差，Si越小代表類內(nèi)相似度越高。d(i，j)代表聚類中心之間的歐式距離，d(i，j)越大代表類間距離越大，類間相似度越低。DBI可以描述聚類效果，DBI的值越小，代表類內(nèi)相似度高，且類間相似度低，聚類效果越好[7]。

2.3 改進算法的并行化實現(xiàn)

MapReduce編程模型由谷歌提出，可以對大規(guī)模的數(shù)據(jù)集作并行運算。改進后的K-Means算法的迭代過程主要有兩個步驟：(1)將數(shù)據(jù)集中的數(shù)據(jù)點進行分類；(2)計算中心點。由于數(shù)據(jù)點運算時完全獨立，互不干擾，且計算中所用的公共變量不多，可采用MapReduce并行計算編程模型實現(xiàn)，一次迭代為一個任務(wù)，由 Map函數(shù)、Combine函數(shù)、Reduce函數(shù)實現(xiàn)，Map函數(shù)主要用于計算距離，對數(shù)據(jù)集中的數(shù)據(jù)點進行分類，Combine函數(shù)對Map函數(shù)輸出的鍵對值進行合并預(yù)處理，Reduce函數(shù)以Combine函數(shù)的輸出作為輸入，負責(zé)重新計算中心點，判斷是否符合閾值條件，不符合則開始新一輪的迭代[8]。實現(xiàn)過程如下：

(1)數(shù)據(jù)初始化，將日志文件進行 n維切片，將大小相同的數(shù)據(jù)塊存入HDFS。

(2)將切片和副本送至對應(yīng)的數(shù)據(jù)節(jié)點。

(3)節(jié)點調(diào)用Map函數(shù)提取出數(shù)據(jù)塊，計算距離和，選擇初始聚類中心，計算點到聚類中心的距離，得到K個聚類中心。

(4)前一階段函數(shù)Map的結(jié)果進入combine階段進行歸并處理，為Reduce函數(shù)提供標準化輸入。

(5)Reduce函數(shù)對輸入的候選聚類中心計算新一輪迭代和上一輪迭代的DBI指標值，若DBIn＜DBIo則開始新一輪的迭代，直到 DBIn＞DBIo為止，判定中心點收斂，任務(wù)結(jié)束，否則，更新中心點并且開始新一輪的迭代。

MapReduce并行化流程圖如圖4所示。

3 實驗結(jié)果與分析

為了體現(xiàn)改進K-Means算法的有效性和準確性，本文采用了傳統(tǒng)的K-Means算法和改進后的并行K-Means算法對同一組數(shù)據(jù)集進行聚類。實驗數(shù)據(jù)來自于某安全態(tài)勢感知網(wǎng)站90天的日志文件，總計4.5 GB大小。日志在處理之前，需先經(jīng)過標準化處理。例如，原始日志格式為：time:2019-12-15_13:42:30;danger_degree:1;breaking_sighn:0;event:[50193]某某入侵攻擊;src_addr:192.168.10.244;src_port:138;dst_addr:192.168.10.255;dst_port:138;proto:UDP.NETBIOSDGM；user:xiaoming。

經(jīng)過標準化、過濾、補齊、關(guān)聯(lián)標簽等流程后，日志數(shù)據(jù)如表 1所示[9]。

3.1 算法有效性驗證

衡量改進后K-Means算法有效性的重要指標是觀察算法的迭代次數(shù)和準確率相較于優(yōu)化前有無改進。準確率=×100%，代表放入聚類簇中的數(shù)據(jù)點個數(shù)占數(shù)據(jù) 總數(shù)的比例。分別使用傳統(tǒng)的K-Means算法和優(yōu)化后的K-Means算法進行實驗，結(jié)果如圖 5、圖 6所示。

從圖5可以看出，由于采用MapReduce并行化架構(gòu)，對于同一數(shù)據(jù)集，改進后的算法迭代次數(shù)少于傳統(tǒng)K-Means算法，隨著數(shù)據(jù)量的增大，優(yōu)勢更明顯。

圖4 MapReduce并行化處理流程

表1 預(yù)處理后的日志數(shù)據(jù)

圖5 傳統(tǒng)K-Means算法與改進的K-Means算法迭代次數(shù)對比

圖6 傳統(tǒng)K-Means算法與改進的K-Means算法準確率對比

從圖6可以看出，改進后的K-Means算法準確率有所提升，有更多數(shù)據(jù)點被正確劃分到類簇中，聚類效果更佳。

3.2 算法時間驗證

算法聚類時間是另一個衡量算法性能的重要指標，針對同一數(shù)據(jù)集，算法耗時越短代表執(zhí)行效率越高。本文將并行K-Means優(yōu)化算法和串行傳統(tǒng)K-Means算法在聚類時間上進行了對比，改變數(shù)據(jù)集的大小進行實驗。實驗結(jié)果如圖7所示。

圖7 傳統(tǒng)K-Means算法與改進的K-Means算法聚類時間對比

由圖7可以看出，當數(shù)據(jù)量較小時，傳統(tǒng)K-Means算法稍快于改進并行K-Means算法，隨著數(shù)據(jù)量增大到1.5 GB時，改進算法運行時間開始比傳統(tǒng)算法短，且隨著數(shù)據(jù)集的增大，優(yōu)勢越來越明顯。產(chǎn)生這種現(xiàn)象的原因是當數(shù)據(jù)量較小時，改進K-Means算法采用了MapReduce并行架構(gòu)，較傳統(tǒng)串行算法更耗時，隨著數(shù)據(jù)量的增大，改進算法對數(shù)據(jù)片進行并行處理的優(yōu)勢顯現(xiàn)出來，算法運行時間大大縮短，證明了改進K-Means并行算法更適用于大數(shù)據(jù)處理[10]。

4 結(jié)論

本文提出的改進K-Means算法克服了傳統(tǒng)K-Means算法在尋找初始聚類中心的隨機性，克服了孤立點對聚類效果的影響，降低了算法時間開銷，提升了執(zhí)行效率，并基于MapReduce實現(xiàn)了并行化，使其適應(yīng)于大數(shù)據(jù)處理要求。通過實驗，證明了新算法在有效性和時間復(fù)雜度方面都優(yōu)于傳統(tǒng)K-Means算法。基于該算法實現(xiàn)的日志追責(zé)系統(tǒng)具有可靠性高、可拓展性強、執(zhí)行效率高等優(yōu)點，有一定的實用價值。