基于數(shù)據(jù)挖掘K—means算法的異常檢測(cè)模型的研究與實(shí)現(xiàn)

張鄰

【摘 要】本文結(jié)合數(shù)據(jù)倉(cāng)庫(kù)的優(yōu)勢(shì)采用數(shù)據(jù)挖掘中的K-means算法，對(duì)經(jīng)過(guò)標(biāo)準(zhǔn)化預(yù)處理的數(shù)據(jù)進(jìn)行訓(xùn)練、分類，獲得可用的入侵檢測(cè)規(guī)則。實(shí)驗(yàn)結(jié)果表明，K-means算法設(shè)計(jì)的異常檢測(cè)模型可以作為預(yù)測(cè)和判斷用戶行為合法性的依據(jù)，并有較高的正確率，能降低系統(tǒng)的漏報(bào)率和誤報(bào)率。

【關(guān)鍵詞】K-means算法；入侵檢測(cè)規(guī)則；用戶行為；正確率

引言

入侵檢測(cè)是當(dāng)前流行的安全防御技術(shù)，一般可分為異常檢測(cè)和誤用檢測(cè)兩種類型[1]，異常檢測(cè)主要用來(lái)發(fā)現(xiàn)未知的、可疑的攻擊行為。提高異常檢測(cè)的性能可以降低入侵檢測(cè)系統(tǒng)的漏報(bào)率和誤報(bào)率。數(shù)據(jù)挖掘K-means算法能高度自動(dòng)化地分析原有數(shù)據(jù)，從中挖掘出潛在的模式，預(yù)測(cè)用戶行為，對(duì)入侵行為重新劃分，獲得入侵行為規(guī)則。從本文實(shí)驗(yàn)結(jié)果表明，其可以降低入侵檢測(cè)系統(tǒng)的漏報(bào)率和誤報(bào)率。

1.數(shù)據(jù)挖掘（Data Mining）

數(shù)據(jù)挖掘就是要從大量的數(shù)據(jù)中整理出或挖掘出有用的知識(shí)，這些知識(shí)是隱含的、事先未知的具有潛在有用信息，它們可表示為概念、規(guī)則、規(guī)律、模式等形式[2]。數(shù)據(jù)挖掘技術(shù)是一種決策支持過(guò)程，它主要基于人工智能（AI）、機(jī)器學(xué)習(xí)統(tǒng)計(jì)等技術(shù)，能從大量數(shù)據(jù)中提取或挖掘知識(shí)。

2.數(shù)據(jù)挖掘的K-means算法

入侵檢測(cè)模型需要高效、準(zhǔn)確地處理海量的用戶行為數(shù)據(jù)，并盡可能降低誤判率、漏判率是判斷一個(gè)入侵檢測(cè)系統(tǒng)成功與否的標(biāo)志。聚類分析方法具有可伸縮性、高維性、能處理不同類型屬性、可按各種約束聚類等優(yōu)點(diǎn)，尤其適用大型數(shù)據(jù)庫(kù)的模式分類[3]。

2.1聚類分析

聚類按照“最大化類內(nèi)相似性，最小化類間相似性”的原則，將數(shù)據(jù)對(duì)象分組為多個(gè)類或簇（cluster），同一個(gè)簇中的對(duì)象具有較高相似度，而不同簇間的對(duì)象差別較大，對(duì)象間的相異度根據(jù)對(duì)象的屬性值計(jì)算。

給定一個(gè)有N個(gè)對(duì)象或元組的數(shù)據(jù)庫(kù)，用聚類劃分法構(gòu)建數(shù)據(jù)的K個(gè)劃分，每個(gè)劃分表示一個(gè)聚簇，并且 K≤N。在聚類劃分中，基于距離的分類采用度量方式，例如K-means、K-medoids等。當(dāng)前比較流行的啟發(fā)式方法首推K-means算法，我們?cè)诖擞么怂惴▽?duì)已知用戶行為數(shù)據(jù)庫(kù)進(jìn)行聚類劃分，檢測(cè)入侵行為[4]。

2.2 K-means算法

K-means算法以K為參數(shù)，把N個(gè)對(duì)象分為K個(gè)簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度較低。相似度的計(jì)算根據(jù)一個(gè)簇中的平均值（視為簇重心）進(jìn)行。K-means算法的處理過(guò)程為：

1）隨機(jī)選擇K個(gè)對(duì)象，每個(gè)對(duì)象初始代表一個(gè)簇的平均值或中心。對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。

2）重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)，直至準(zhǔn)則函數(shù)收斂到期望值。由于實(shí)際應(yīng)用中對(duì)象數(shù)據(jù)選用的度量單位將直接影響聚類分析結(jié)果，不同度量單位可能產(chǎn)生迥異的聚類結(jié)構(gòu)，因此為避免對(duì)度量單位選擇的依賴，實(shí)際中應(yīng)先對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。

每個(gè)對(duì)象與簇中心的距離采用歐幾里德距離，其定義如式（2-1）所示，其中i =（Xi1，Xi2，...，Xip）和 j =（Xj1，Xj2 ， ...， Xjp）是2個(gè)p維的數(shù)據(jù)對(duì)象。

（2-1）

該算法試圖找出使均方誤差函數(shù)值最小的 K個(gè)劃分，令生成的結(jié)果盡量緊湊、獨(dú)立。下面是K-means算法的流程，從中可以得到，算法的復(fù)雜度為O（nkt），遠(yuǎn)小于O（n2），其中，n是所有對(duì)象的數(shù)目，K是簇的數(shù)目，t是迭代次數(shù)（一般k和t均小于n）。鑒于待劃分的數(shù)據(jù)庫(kù)通常比較大，這種性能還是比較優(yōu)良的。

K-means算法流程如下：

（1）算法K-means基于簇中對(duì)象平均值。

（2）輸入簇的數(shù)目K和N個(gè)對(duì)象的數(shù)據(jù)庫(kù)。

（3）輸出K個(gè)簇，滿足均方誤差函數(shù)值最小。

3.異常檢測(cè)模型

通過(guò)數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)采集、預(yù)處理及分析后，形成一個(gè)以異常檢測(cè)為主題的數(shù)據(jù)集市，該數(shù)據(jù)集市的模型包含IP地址ID、連接次數(shù)、訪問(wèn)協(xié)議ID、訪問(wèn)協(xié)議次數(shù)、訪問(wèn)目標(biāo)端口次數(shù)、出現(xiàn)連接錯(cuò)誤次數(shù)、訪問(wèn)資源級(jí)別ID、訪問(wèn)資源次數(shù)。

對(duì)生成的異常檢測(cè)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，成為可供K-means使用的特征數(shù)據(jù)。采用C++語(yǔ)言按照上述原理與流程進(jìn)行編程，對(duì)數(shù)據(jù)進(jìn)行分析，經(jīng)過(guò)有限次的迭代即可識(shí)別出異常、攻擊、安全3種類型的記錄，當(dāng)然也可以按照自己的要求設(shè)置分類數(shù)。

圖1是使用K-means算法設(shè)計(jì)異常檢測(cè)模型的設(shè)計(jì)流程圖，用它來(lái)生成異常檢測(cè)規(guī)則。

圖1異常檢測(cè)模型的設(shè)計(jì)流程圖

對(duì)K-means聚類結(jié)果進(jìn)行分析后，總結(jié)出不同類規(guī)則及其含義，把這些規(guī)則中的正常與攻擊行為模式作為入侵檢測(cè)模式存入在數(shù)據(jù)倉(cāng)庫(kù)中，用以預(yù)測(cè)和判斷用戶行為合法性的依據(jù)。

4.實(shí)驗(yàn)

4.1實(shí)驗(yàn)用例

本測(cè)試使用MIT林肯實(shí)驗(yàn)室開(kāi)發(fā)的DARPA 1999年IDS評(píng)測(cè)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)測(cè)試。異常檢測(cè)實(shí)驗(yàn)時(shí)把星期一的部分?jǐn)?shù)據(jù)用來(lái)經(jīng)過(guò)入侵檢測(cè)模型來(lái)生成異常檢測(cè)規(guī)則，把星期二、星期四、星期五的數(shù)據(jù)用來(lái)進(jìn)行異常檢測(cè)實(shí)驗(yàn)。

4.2測(cè)試過(guò)程

處理星期一的部分?jǐn)?shù)據(jù)，使數(shù)據(jù)的形式滿足異常檢測(cè)模型的需要，表4-1是處理數(shù)據(jù)的最終形式，太多的數(shù)據(jù)會(huì)使程序運(yùn)行緩慢，而且沒(méi)有太大的必要。把此數(shù)據(jù)以文件的形式提交給異常檢測(cè)模型，我們根據(jù)異常檢測(cè)模型的運(yùn)行結(jié)果（運(yùn)行時(shí)間與主機(jī)配置有關(guān)）得到異常檢測(cè)規(guī)則。接下來(lái)把星期二、星期四、星期五的數(shù)據(jù)進(jìn)行異常檢測(cè)。

表1中各參數(shù)含義：

Ip 源IP地址。

count 在一個(gè)時(shí)間窗口內(nèi)目標(biāo)主機(jī)的連接次數(shù)。

error 出現(xiàn)syn錯(cuò)誤的連接百分比。

same_srv 目標(biāo)端口相同的連接所占的百分比。

diff_srv 目標(biāo)端口不同的連接所占的百分比。

srv_count 目標(biāo)端口與當(dāng)前連接相同的連接次數(shù)。

srv_diff_host 目標(biāo)主機(jī)不同的連接所占的百分比。

通過(guò)異常檢測(cè)模型分析，發(fā)現(xiàn)SYN錯(cuò)誤為0.9、0.75、0.8屬于同一類，所以SYN大于0.75的應(yīng)屬于是攻擊行為，SYN錯(cuò)誤為0.2-0.7屬于同一類作為異常行為，而SYN錯(cuò)誤小于0.2的屬于正常行為。

5.結(jié)束語(yǔ)

本文采用數(shù)據(jù)挖掘K-means算法來(lái)建立異常檢測(cè)模型。通過(guò)以上模擬實(shí)驗(yàn)可知，使用K-means算法可以形成可用的異常檢測(cè)規(guī)則，用于異常檢測(cè)時(shí)也有較高的正確率。影響異常檢測(cè)因素很多，比如異常檢測(cè)模型規(guī)則的數(shù)據(jù)的正確性、數(shù)據(jù)的角度等。以后的研究中可以提供不同角度不同主題的數(shù)據(jù)給異常檢測(cè)模型，以生成其他角度的異常檢測(cè)的規(guī)則，提高入侵檢測(cè)的精確度。

參考文獻(xiàn)：

[1] 楊永銘.異常點(diǎn)檢測(cè)算法在入侵檢測(cè)中的應(yīng)用研究.現(xiàn)代計(jì)算機(jī).2008.1：35-38.

[2] Chen W M.Data Mining：an Overview from An Database Perspective.IEEE Trans on Knowledge and Data Eng，l996（8）：866.

[3] 李洋.K-means聚類算法在入侵檢測(cè)中的應(yīng)用.計(jì)算機(jī)工程.2007年7月：155-156.