張艷 羅文華 中國刑事警察學(xué)院

引言

網(wǎng)絡(luò)技術(shù)的迅速發(fā)展催生了大量新興的網(wǎng)絡(luò)犯罪，而服務(wù)器入侵屬于網(wǎng)絡(luò)犯罪中偵破難度較高的犯罪形式之一。在非法入侵計算機(jī)信息系統(tǒng)類案件的偵破中，通過聚類算法分析服務(wù)器登陸日志是電子數(shù)據(jù)取證領(lǐng)域必不可少的技術(shù)方法之一。

聚類是根據(jù)樣本數(shù)據(jù)之間的相似性進(jìn)行分類并聚合的過程。在大數(shù)據(jù)時代數(shù)據(jù)挖掘已經(jīng)成為大數(shù)據(jù)分析中最為核心的模塊，而數(shù)據(jù)挖掘依賴各種聚類算法。聚類算法會概括出海量數(shù)據(jù)中每一類的特點，以便針對某一個特定的類做進(jìn)一步的分析。聚類還作為數(shù)據(jù)挖掘算法中的預(yù)處理步驟服務(wù)于其他分析算法。在數(shù)據(jù)挖掘算法中使用聚類算法可以準(zhǔn)確地在海量數(shù)據(jù)中挖掘具有極高價值的信息，比如在網(wǎng)絡(luò)攻擊案件中可以幫助取證調(diào)查人員從海量日志數(shù)據(jù)集[1]中區(qū)分正常行為與入侵行為，進(jìn)而挖掘破案線索或定案證據(jù)。入侵檢測中最重要的調(diào)查對象之一即是網(wǎng)絡(luò)服務(wù)器中的用戶登錄日志，為此本文以該類日志為數(shù)據(jù)基礎(chǔ)，針對K-means、DBSCAN以及改進(jìn)的MajorClust三種常用的聚類算法進(jìn)行分析，通過實驗結(jié)果比較三種算法的特點及不足，希望能夠為打擊日益猖獗的網(wǎng)絡(luò)攻擊犯罪提供可行高效的建議。

一、K-means算法

（一）算法簡介

K-means聚類[2]是最著名的分區(qū)聚類算法，是使用最廣泛的算法之一。其主要思想是給定一個對象集合和需要的聚類數(shù)目K，根據(jù)距離函數(shù)反復(fù)把對象分入K個聚類中。

（二）算法的原理及特點

K-means方法用于將雙向雙模對象（即對每個P變量進(jìn)行N個對象的測量）劃分為K類（C1， C2， …，CK），其中Ck是聚類簇K中的所有對象集合，并且K是給定的。如果XN*P= {xij}N*P表示N*P的對象矩陣，則K-means方法構(gòu)造這些聚類簇使得任何對象的行向量與其各自聚類簇的聚類中心向量之間的歐幾里德距離為至少與剩余聚類簇的聚類中心距離一樣小。

K-means原理簡單且實現(xiàn)容易，但K值通常依賴先驗知識、假設(shè)和實踐經(jīng)驗的臨時決策。當(dāng)數(shù)據(jù)具有多個維度時即使群集分離良好，選擇K也會變得更加困難。如果使用多個中心對象來描述從一種模式中提取的對象，則這些中心對象是對整體對象不必要的復(fù)雜描述，并且實際上多個中心對象捕獲關(guān)于子集的真實性不如一個中心對象。

二、DBSCAN算法

（一）算法簡介

DBSCAN算法[3]是基于密度的聚類算法。同一類別的對象之間是緊密相連的，通過將緊密相連的對象劃為一類就會得到一個聚類簇。該算法適用于處理大型數(shù)據(jù)集，并且能夠識別具有不同大小和形狀的群集。

（二）算法的原理及特點

DBSCAN算法以密度為度量將對象聚類。對于樣本集D=(x1， x2， ...，xm)，鄰域參數(shù)（領(lǐng)域半徑，領(lǐng)域半徑內(nèi)對象的最小數(shù)量），實現(xiàn)xn∈ D且N(xj)≥MinPts，其中領(lǐng)域半徑、領(lǐng)域半徑內(nèi)對象的最小數(shù)量需指定，xj為隨機(jī)對象，xn的 集合為N(xj) ，N(xj) 是隨機(jī)對象xj領(lǐng)域內(nèi)對象的聚類簇。

DBSCAN算法可以對任意形狀的對象集進(jìn)行聚類，執(zhí)行效率高，且僅需輸入領(lǐng)域半徑和領(lǐng)域半徑最小數(shù)量即可實現(xiàn)快速聚類。但是該算法的領(lǐng)域半徑較難指定，領(lǐng)域半徑代表著對象間的緊密程度，決定著聚類效果的優(yōu)劣。領(lǐng)域半徑內(nèi)的點數(shù)量代表聚類結(jié)果中對象的最小數(shù)量，需經(jīng)過多次嘗試。

三、改進(jìn)的MajorClust算法

（一）算法簡介

MajorClust算法是基于密度的聚類算法，能夠自動進(jìn)行對象聚類，通過計算對象相似度來改變聚類的形狀以提升聚類效率。

（二）算法的原理及特點

MajorClust算法將相似度作為聚類的依據(jù)，其處理結(jié)果顯得較為粗糙。實驗中，在原有基礎(chǔ)上改進(jìn)MajorClust算法，根據(jù)“最大吸引制勝”原則[4]，以相似度為量度將對象迭代傳到聚類結(jié)果中。擁有“其鄰居的相似度之和的最大值”的對象與其最大相似度的對象實現(xiàn)聚類，其遵循的公式如下：

其中c是當(dāng)前聚類簇，h是具有最大相似度的鄰居對象，并且c(h)是h的聚類簇標(biāo)簽，ci是第i個聚類簇，c*是具有最大相似度的聚類。通過這樣的部署使得對象將僅跟隨最相似的對象。實際實驗過程中，將選取相似度之和最大的對象，以逐步挑選最相似對象，同時改進(jìn)的MajorClust算法即選取了最長子串優(yōu)化聚類效果。

MajorClust算法無需輸入?yún)?shù)，即可自動實現(xiàn)對象集的聚類，使得前期工作更為簡潔。在聚類推導(dǎo)過程中，由于只考慮對象的鄰居對象，從而擁有了良好的運行效率，同時使得對象最大程度的貼近從而精確了聚類簇的中心內(nèi)容。該算法雖迭代次數(shù)有限，但在逐步選取相似度之和最大的對象時會因?qū)ο蠹瘮?shù)量的龐大而影響到運行時間。

四、實驗結(jié)果及比較

本實驗使用的樣本數(shù)據(jù)來自安裝Linux系統(tǒng)的服務(wù)器保存的登錄日志文件“auth.log”。該日志中的每條數(shù)據(jù)記錄由日期（date）、時間（time）、進(jìn)程名稱（process name）、ID（PID）、主機(jī)名稱（hostname）以及具體的事件（event）組成。

采用聚類算法K-means、DBSCAN以及改進(jìn)的MajorClust實現(xiàn)日志中數(shù)據(jù)的聚類，為分析事件類型、挖掘深層信息奠定基礎(chǔ)[5]。由于日志數(shù)據(jù)集過大，為了使聚類圖顯示更加直觀，選取日期為Nov 30的數(shù)據(jù)進(jìn)行聚類實驗。

（一）數(shù)據(jù)處理

針對樣本數(shù)據(jù)聚類之前需要進(jìn)行數(shù)據(jù)的預(yù)處理，即相似度計算。不同的相似度計算算法適應(yīng)的數(shù)據(jù)類型也不盡相同。本實驗的樣本數(shù)據(jù)為以條為單位的文本數(shù)據(jù)記錄，故選用TF-IDF和余弦距離來計算相似度。

在相似度計算過程中，由于語句中的停用詞會導(dǎo)致其相似度偏高，因此實際聚類過程中設(shè)定停用詞并在數(shù)據(jù)記錄中去除，將“for”、“by”、“form”、“[preauth]”、“port”、“sshd”、“ssh”設(shè)定為停用詞并在計算相似度之前去除。

（二）三種算法實驗比對

算法結(jié)束后將對聚類效果進(jìn)行準(zhǔn)確性計算，其計算步驟如下：

（1）聚類中心：計算聚類中心不唯一的簇占實驗數(shù)據(jù)集的平均比例。

（2）聚類簇中內(nèi)容：當(dāng)聚類簇中出現(xiàn)少于一半的數(shù)據(jù)內(nèi)容與簇中其他數(shù)據(jù)內(nèi)容不相同時，計算其在該簇中所占的比例；若多于一半數(shù)據(jù)內(nèi)容不相同，計算其占實驗數(shù)據(jù)集的比例。

（3）計算精確值：初始聚類效果準(zhǔn)確性為100%，減去步驟1、2中的不準(zhǔn)確性得到最終聚類效果準(zhǔn)確性的精確值。

1. 使用K-means算法進(jìn)行聚類

（1）確定K值，并隨機(jī)選擇K個聚類中心數(shù)據(jù)：K值代表聚類的簇數(shù)，K個聚類中心數(shù)據(jù)即K個簇的中心內(nèi)容。日志文件為登錄類型的文件，決定選取4和5作為K值分別進(jìn)行實驗。K值確定之后，將從所有樣本數(shù)據(jù)中隨機(jī)選擇K個數(shù)據(jù)作為聚類中心。

（2）數(shù)據(jù)劃分：遍歷樣本數(shù)據(jù)，以數(shù)據(jù)預(yù)處理獲得的相似度為衡量標(biāo)準(zhǔn)，將每條數(shù)據(jù)分給其對應(yīng)相似度最高的聚類中心。若出現(xiàn)某條數(shù)據(jù)與所有聚類中心的相似度都為零的情況，則將此數(shù)據(jù)記錄分配給第一個聚類簇。

（3）更新聚類中心：在數(shù)據(jù)劃分后，將每一個簇中出現(xiàn)頻率最高的數(shù)據(jù)記錄更新為聚類中心。

（4）重復(fù)進(jìn)行數(shù)據(jù)劃分：重復(fù)執(zhí)行步驟2到4。為避免出現(xiàn)死循環(huán)，本實驗中將設(shè)定閾值為10以限制算法運行時間。算法結(jié)束條件設(shè)定為以下三個條件之一：

·聚類結(jié)果不再發(fā)生改變；

·K個中心點收斂（無變化）；

·執(zhí)行了10次迭代。

（5）繪制聚類圖：對樣本數(shù)據(jù)經(jīng)過聚類計算后，其聚類結(jié)果通過Python自帶的軟件庫繪制出聚類結(jié)果圖，圖1是K值為4時執(zhí)行的兩次結(jié)果。

從聚類圖中可以看出，相同的K值，聚類結(jié)果有差異；經(jīng)多次實驗，不同K值，其聚類效果不唯一。K值的選取是該算法的難點，K值設(shè)置太小則會導(dǎo)致相似度較小的數(shù)據(jù)發(fā)生聚類，使得結(jié)果過度模糊，中心內(nèi)容不唯一，同時較小的K值會導(dǎo)致過多的更新聚類中心，進(jìn)而致使運行時間也隨之增長；而當(dāng)K值設(shè)置過大時則會導(dǎo)致聚類結(jié)果過度擬合，使得聚類簇數(shù)多而每個聚類簇內(nèi)的數(shù)據(jù)量過少，從而導(dǎo)致多個聚類簇的中心內(nèi)容相同，影響運行時間、效果。因此K個聚類中心不能明顯代表簇中心，導(dǎo)致運行時間加長，聚類效果變差，違背了聚類的本意。

（6）計算聚類效果準(zhǔn)確性：本實驗中，實驗數(shù)據(jù)為688條，當(dāng)K值為5時，第一次實驗結(jié)果準(zhǔn)確性為64.4%，第二次實驗結(jié)果準(zhǔn)確性為48.7%；當(dāng)K值為4時，第一次實驗結(jié)果準(zhǔn)確性為78%，第二次實驗結(jié)果準(zhǔn)確性為66%。

2. 使用DBSCAN算法進(jìn)行聚類

（1）計算相似度：使用TF-IDF以及余弦相似性來計算兩兩數(shù)據(jù)之間的相似度。此計算為前期準(zhǔn)備過程，不參與DBSCSN的直接計算。

（2）確定領(lǐng)域范圍及領(lǐng)域范圍內(nèi)數(shù)據(jù)的最小數(shù)量：依據(jù)數(shù)據(jù)之間的相似度來確定領(lǐng)域半徑，通過對相似度的觀察，可以看出其相似度主要集中在0、0.4、0.8附近，實驗中選取0.5作為領(lǐng)域半徑。領(lǐng)域半徑內(nèi)數(shù)據(jù)的最小數(shù)量一般定的相對較小，本實驗中設(shè)定為5。

（3）實現(xiàn)領(lǐng)域半徑內(nèi)數(shù)據(jù)聚類：隨機(jī)選取一個數(shù)據(jù)作為聚類中心，遍歷剩余數(shù)據(jù)，將與聚類中心的相似度大于領(lǐng)域半徑的數(shù)據(jù)分配給此聚類中心，同時將分配的數(shù)據(jù)標(biāo)為已分配。

（4）遍歷所有數(shù)據(jù)：在未被標(biāo)記的數(shù)據(jù)中重復(fù)執(zhí)行步驟3，其結(jié)束條件為下列之一即可：·所有數(shù)據(jù)均被分配；

·未分配數(shù)據(jù)沒有在任一數(shù)據(jù)的領(lǐng)域范圍內(nèi)；

·未分配數(shù)據(jù)少于領(lǐng)域范圍內(nèi)最小數(shù)據(jù)量。

（5）繪制聚類圖：對樣本數(shù)據(jù)經(jīng)過聚類計算后，其聚類結(jié)果通過Python自帶軟件庫繪制出聚類的結(jié)果圖，圖2是領(lǐng)域半徑為0.5、領(lǐng)域半徑數(shù)據(jù)最小數(shù)量為5時的實驗結(jié)果。

經(jīng)過多次實驗，選取了具有明顯特征的聚類結(jié)果展示，在輸入?yún)?shù)相同的情況下，其聚類效果相同。該算法未直接保留數(shù)據(jù)之間的相似度，而是將其直接歸為簇中，使得數(shù)據(jù)間的聯(lián)系不能直觀顯示。該算法由于未直接確定聚類簇數(shù)，其聚類簇數(shù)不可直接預(yù)知且由領(lǐng)域半徑?jīng)Q定。從聚類結(jié)果中可以看出，領(lǐng)域半徑影響聚類結(jié)果，但對運行時間的影響微乎其微。領(lǐng)域半徑的取值依據(jù)先前的相似度來選取，提高了聚類效果的準(zhǔn)確性，然而過大的領(lǐng)域半徑值仍然會使得聚類簇數(shù)增多，簇中的數(shù)據(jù)減少，甚至可能引起過度擬合，過小的領(lǐng)域半徑則相反。

（6）計算聚類效果準(zhǔn)確性：本實驗中，實驗數(shù)據(jù)為688條，當(dāng)領(lǐng)域半徑值為0.4、領(lǐng)域半徑內(nèi)最小數(shù)據(jù)量為5時，實驗結(jié)果準(zhǔn)確性為66%；當(dāng)領(lǐng)域半徑值為0.5、領(lǐng)域半徑內(nèi)最小數(shù)據(jù)量為5時，實驗結(jié)果準(zhǔn)確性為86%。

3. 使用MajorClust算法進(jìn)行聚類

（1）選取聚類中心：遍歷樣本數(shù)據(jù)，以數(shù)據(jù)預(yù)處理獲得的相似度為衡量標(biāo)準(zhǔn)，計算數(shù)據(jù)到其他所有數(shù)據(jù)的相似度并求其總和，將總和最大的數(shù)據(jù)設(shè)定為聚類中心，并將對聚類中心的相似度總和有絕對影響的數(shù)據(jù)與聚類中心進(jìn)行聚類。未聚類的節(jié)點重復(fù)上述步驟，直至所有數(shù)據(jù)全部聚類完畢為止。此時的聚類結(jié)果是過度擬合的，由于每兩條或三條數(shù)據(jù)就形成一個聚類簇，因此選擇更新聚類中心來實現(xiàn)再一次聚類。

（2）更新聚類中心：在步驟1完成后會存在多個聚類簇，即每兩三個數(shù)據(jù)就會形成一個聚類簇，其聚類結(jié)果過度擬合，選取聚類簇中數(shù)據(jù)的最長子串作為新的聚類中心，原始數(shù)據(jù)依舊保存以便后期調(diào)取分析。

（3）重新聚類：對步驟2中重新選取的每個聚類簇的聚類中心兩兩計算相似度，形成最終聚類結(jié)果。

（4）繪制聚類圖：對樣本數(shù)據(jù)經(jīng)過聚類計算后，兩兩相似度可直觀反映，因此通過軟件Gephi繪制出聚類的結(jié)果圖，如圖3所示。

由于該算法保留了數(shù)據(jù)間的相似程度，因此在聚類圖中可以直觀地看到數(shù)據(jù)內(nèi)容、數(shù)據(jù)間相似度（數(shù)據(jù)間的相似度會顯示在數(shù)據(jù)間的連線上，由于聚類數(shù)據(jù)較多暫沒有顯示其相似度）。此聚類算法無需輸入聚類參數(shù)即可實現(xiàn)自動聚類，其結(jié)果客觀且準(zhǔn)確度較高。在聚類過程中，相似度之和最大的數(shù)據(jù)的挑選會因數(shù)據(jù)量的增多而增加時間。在聚類結(jié)果中因其保留了數(shù)據(jù)記錄之間的相似度，使得后續(xù)分析更為直觀。

（5）計算聚類效果準(zhǔn)確性：本實驗中，實驗數(shù)據(jù)為688條，實驗結(jié)果準(zhǔn)確性為86%。

五、結(jié)果比較

通過對auth.log日志文件的聚類，總結(jié)三種算法對此類型文件的適用情況，如表1所示。其中時間為實際實驗中聚類算法運行的平均時間，聚類準(zhǔn)確性為實際聚類效果準(zhǔn)確性的平均值。

?

在對auth.log日志文件的聚類中，使用了K-means、DBSCAN、MajorClust三種算法，由于算法本身存在自身特點，致使使用方式和效果不盡相同。在整個實驗中，使用的日志文件數(shù)據(jù)屬于文本類數(shù)據(jù)，且密度較稠密，DBSCAN算法和改進(jìn)的MajorClust算法顯示出了良好的運行效果，而K-means算法則稍有遜色。三種算法首要區(qū)別是在參數(shù)的設(shè)置上，MajorClust算法不需要輸入任何參數(shù)即可自己實現(xiàn)聚類，而DBSCAN算法需輸入兩個參數(shù)、Kmeans需輸入一個參數(shù)，實驗中，參數(shù)的選擇相對較難，需要先驗經(jīng)驗和不斷嘗試，這要求取證人員具備較高的技術(shù)水平和豐富的實踐經(jīng)驗，因為參數(shù)的選擇直接影響聚類效果的優(yōu)劣，若能基于先驗經(jīng)驗給出精確的參數(shù)，那么其參數(shù)問題便可忽略。算法的運行時間在一定程度上反映著算法的運行效率，這在電子數(shù)據(jù)取證過程中至關(guān)重要，因為通常服務(wù)器日志較實驗日志極大，分析極為耗時。本實驗中相似度的計算是每個算法必有的運行時間，K-means算法運行時間主要依賴于K個聚類中心的不斷更新，而聚類中心的更新則取決于數(shù)據(jù)的稠密程度；DBSCAN算法只要設(shè)定好領(lǐng)域半徑即可快速運行；改進(jìn)的MajorClust算法依賴相似度的總和，因此其運行時間取決于數(shù)據(jù)集的數(shù)量。實驗運行結(jié)果顯示出三種算法各自的特征，就文本數(shù)據(jù)集而言，在偵破服務(wù)器入侵類犯罪時，K-means算法更適合于數(shù)據(jù)內(nèi)容有明顯差異的數(shù)據(jù)集，DBSCAN算法對稠密的數(shù)據(jù)有良好的運行能力，適合短時間內(nèi)分析海量日志內(nèi)容，節(jié)省案件偵破周期，而Majorclust算法適應(yīng)范圍較廣，效果突出，但耗時略長，在時間充裕的情況下能準(zhǔn)確鎖定關(guān)鍵信息，協(xié)助偵查人員縮小偵查范圍，指明偵查方向。綜上所述，在服務(wù)器入侵類案件針對日志進(jìn)行電子數(shù)據(jù)取證的過程中，根據(jù)具體情況結(jié)合不同的聚類算法分析日志方能在最短時間內(nèi)準(zhǔn)確定位關(guān)鍵信息。