基于混沌粒子群的IDS告警聚類算法

胥小波，蔣琴琴，鄭康鋒，武斌，楊義先

（1. 中國電子科技集團公司 第三十研究所，四川 成都 610041；2. 北京郵電大學(xué) 信息安全中心，北京 100876)

1 引言

隨著信息時代的發(fā)展，網(wǎng)絡(luò)和通信技術(shù)不斷進步，計算機網(wǎng)絡(luò)和操作系統(tǒng)的漏洞與安全隱患日益暴露在人們面前，網(wǎng)絡(luò)信息安全狀況日益惡化。入侵檢測是對攻擊行為進行檢測的主要工具，是維護網(wǎng)絡(luò)安全的重要技術(shù)手段之一。

入侵檢測系統(tǒng)收集和分析網(wǎng)絡(luò)數(shù)據(jù)分組，識別可能存在的攻擊事件，并對攻擊事件產(chǎn)生報警。然而，IDS每天可能會產(chǎn)生數(shù)以萬計的告警[1～3]。如果沒有適當(dāng)?shù)母婢芾?，安全分析人員將被淹沒于大量的網(wǎng)絡(luò)入侵告警中。

大量的網(wǎng)絡(luò)告警數(shù)據(jù)不僅無法真實地反映網(wǎng)絡(luò)所遭受的攻擊情況，反而增加了安全人員的工作負(fù)擔(dān)，過多的無用告警將有用信息淹沒，使得安全分析人員無法找到系統(tǒng)的漏洞和防范的重點，從而導(dǎo)致入侵檢測的可用性大大降低。因此，需要一種有效的方法，將大量冗余告警去除，分析出系統(tǒng)受到的真實攻擊行為，有利于安全人員對系統(tǒng)進行安全管理和防護。

2 相關(guān)工作

數(shù)據(jù)挖掘技術(shù)在入侵檢測中的應(yīng)用日益廣泛，特別是在管理IDS告警顯示方面。相關(guān)研究者把模式識別、數(shù)據(jù)挖掘等知識運用到告警的分析上來，對告警信息進行聚合和關(guān)聯(lián)分析，得出了較好的研究成果。聚類是一種廣泛使用的數(shù)據(jù)挖掘技術(shù)，在處理海量的告警方面有著大量的研究及應(yīng)用。

Viinikka[4]等提出基于時間序列模型融合大規(guī)模告警的方法，將特定時間序列的告警進行融合；Vaarandi[5]等提出基于頻率集數(shù)據(jù)挖掘的告警分類算法，從大量告警中提取頻繁項集；Njogu[6]等提出告警聚類方法減少告警數(shù)量，根據(jù)告警的相關(guān)性、重要性、頻率等方面的相似程度進行聚類。Fei[7]等提出了一種利用變長染色體的遺傳算法對IDS告警進行層次化聚類的方法，聚類數(shù)量與染色體長度相等，能夠?qū)Ω婢M行較好的分類。李永忠[8]等提出了基于粒子群優(yōu)化的聚類入侵檢測算法，克服傳統(tǒng)的K均值算法易陷入局部極小值的缺點，使算法具有較好的全局收斂性，將粒子群優(yōu)化算法應(yīng)用于入侵檢測，給出了基于粒子群優(yōu)化的K均值聚類算法。

粒子群算法(PSO)由于算法概念簡單、實現(xiàn)容易，獲得了很大發(fā)展。相對遺傳算法而言，PSO不需要進行交叉和變異，操作較為簡單，而且在迭代過程中，粒子運動的思路與人類決策相似，易于理解[9]。但是，傳統(tǒng)粒子群算法初期收斂較快，而在后期容易陷入早熟、局部最優(yōu)。針對這一特點，本文提出了一種新的混沌粒子群優(yōu)化算法，不同于己有的混沌粒子群算法的簡單粒子序列替換，該算法將混沌融入到粒子運動過程中，使粒子群在混沌與穩(wěn)定之間交替運動，逐步向最優(yōu)點靠近。

本文將混沌粒子群算法與K均值算法結(jié)合，對IDS告警進行聚類，并對 KDDCUP99數(shù)據(jù)集進行測試，實驗結(jié)果表明，該算法在入侵檢測中能獲得理想的檢測率和誤檢率，能夠減少告警數(shù)量，改善告警質(zhì)量，最終生成攻擊場景。

3 混沌粒子群算法

在文獻[10]中，針對混沌蟻群（CAS）算法[11]進行改進，并結(jié)合粒子群算法，提出了混沌粒子群優(yōu)化(CPSO)系統(tǒng)動力學(xué)模型。現(xiàn)將其應(yīng)用于告警聚類算法中，以改善聚類效果。CPSO模型如式(1)～式(3)所示?；煦缌Ｗ尤壕唧w的數(shù)學(xué)模型定義如下

其中，式(1)為粒子速度更新算法。式(2)為混沌變量，影響粒子的混沌程度。rid是一個小于1的正常數(shù)，定義為第i個粒子的第d維混沌因子。式(3)在粒子群的位置更新中引入混沌。t表示迭代次數(shù)，Ψd表示搜索測度，Mi表示粒子i的搜索空間向負(fù)方向移動的比例，如：Ψd=100，Mi=0.5，則表示搜索空間為[-50,50]。

一直處于混沌或穩(wěn)定狀態(tài)對于尋找最優(yōu)值沒有任何意義，只有在混沌與穩(wěn)定的交替中才能不斷向最優(yōu)結(jié)果靠近。也就是說，要在粒子穩(wěn)定時，引入混沌，跳出局部最優(yōu)；在粒子不穩(wěn)定時，加速向最優(yōu)值靠近，加快收斂過程?；煦缢惴ú捎昧宋墨I[11]中的混沌算法，即Sole等給出的混沌系統(tǒng)[12]，混沌迭代式如式(4)所示。

該算法將混沌融入到粒子運動過程中，不同于己有的混沌粒子群算法的簡單粒子序列替換，使粒子群在混沌與穩(wěn)定之間交替向最優(yōu)點靠近，將混沌運動與粒子群運動結(jié)合到一起，并通過混沌因子來調(diào)節(jié)混沌程度，具有較好的全局搜索能力。數(shù)值結(jié)果表明該方法用于解決函數(shù)最優(yōu)化問題的有效性，并且能有效避免粒子群優(yōu)化算法的早熟收斂問題，能跳出局部最優(yōu)，極大提高了計算精度和全局尋優(yōu)能力[10]。

4 告警聚類算法

4.1 問題描述

告警聚類需要解決的問題：將大量的IDS告警進行分類整合，每個集群產(chǎn)生一個告警作為代表，闡述網(wǎng)絡(luò)正在發(fā)生的攻擊行為。將IDS告警聚類定義為：給定一個告警數(shù)據(jù)集X＝{x1, x2, …, xn}，將其分為K個聚類C1, C2, …, Ck，滿足式(5)所給出的條件。

本文采用最小均方誤差法（MSE）作為聚類評判標(biāo)準(zhǔn)，如式(6)所示。

其中，zi為聚類中心。聚類的目標(biāo)就是使均方誤差達到最小。

4.2 告警空間定義

為了實現(xiàn)IDS告警的聚類，首先需要將告警映射為N維向空間上的點集。針對研究中廣泛采用的開源軟件Snort，將其每條告警映射為(AID，Atime，Aproto，AsrcIP，AsrcPort，AdestIP，AdestPort，Amsg，Acontent，Aclasstype)。

定義告警之間的距離為

其中，X、Y為告警，XAi為告警X的Ai屬性值，當(dāng)屬性值取實數(shù)值時，其距離定義如式(8)所示。其中，a、b為告警的屬性值。

當(dāng)屬性值為字符串時，距離定義如式(9)所示。

4.3 聚類算法流程

該算法將每組聚類中心對應(yīng)到一個粒子，然后利用粒子群方法進行搜索，找到最優(yōu)告警分類結(jié)果。具體步驟如下。

Step1 初始化粒子群，在搜索空間范圍內(nèi)隨機產(chǎn)生N個粒子，每個粒子對應(yīng)一組聚類中心。初始粒子的速度和方向隨機產(chǎn)生。

Step2 根據(jù)聚類中心位置，將告警以最近原則分配到各個聚類中。然后利用式(6)～式(9)計算SSE值。更新Pid(個體歷史最優(yōu))和Pgd(全局歷史最優(yōu))。

Step3 根據(jù)式(1)、式(3)更新粒子速度、位置，進行混沌搜索，并根據(jù)式(2)更新粒子群混沌變量。

Step4 判斷終止條件是否滿足，如果滿足，則記錄Pid和Pgd值并退出程序；否則轉(zhuǎn)至Step 2。

算法代碼如圖 1所示。算法初始化粒子群為1)～6)行，其中，N 為粒子個數(shù)，K 為聚類個數(shù)。7)～25)行為粒子群混沌搜索過程，15)～18)行為保存?zhèn)€體最優(yōu)值 Pid，19)～23)行為保存全局最優(yōu)值 Pgd。26)～33)行為存儲分類結(jié)果。fitness(x，D)實現(xiàn)了具有 D維的粒子群中心按式(6)對適值進行計算。

圖1 混沌粒子群告警聚類算法

4.4 攻擊場景構(gòu)建

攻擊場景構(gòu)建在上述告警聚類基礎(chǔ)上，采用“行為+位置+目的”的三段式攻擊行為表述方法，構(gòu)建攻擊場景，還原攻擊入侵過程。

4.4.1 攻擊行為提取

行為是指攻擊者采用何種方法進行攻擊，主要從告警消息的MSG字段進行提取。該算法將攻擊行為分為以下幾類：probe(探測)、scan(掃描)、flood(洪泛)、overflow(溢出)、authenticate(鑒別)、bypass(迂回)、spoof(欺騙)、read(讀取)、copy(拷貝)、steal(盜取)、modify(修改)、delete(刪除)。

通過以上關(guān)鍵字對規(guī)則的MSG字段進行分類，得出可以采用的行為關(guān)鍵字為：Probe、Scan、Flood、Overflow、Bypass、Spoof。而 Read、Copy、Steal、Modify、Delete等信息可以從主機端獲得。

4.4.2 攻擊位置提取

位置是指攻擊者攻擊的作用點，主要分為2類：網(wǎng)絡(luò)（IP地址、端口、協(xié)議、應(yīng)用）、主機（注冊表、進程、文件）。

IP地址和端口均可以從告警信息MSG的地址字段中獲取。icmp、pop2、ftp、smtp、imap、netbios、P2P等協(xié)議類型，均可以從告警中MSG信息的開始的大寫字符串獲得。因為規(guī)則文件是通過協(xié)議來命名的，如P2P.rules里面都是針對P2P協(xié)議的攻擊，而每一條規(guī)則的MSG都以已所在文件名字符串的大寫形式開始。如$HOME_NET any -＞ $EXTERNAL_NET any (msg："P2P GNUTella client request";flow： to_server,established; content： "GNUTELLA";depth：8; metadata：policy security-ips drop; classtype：policy-violation; sid：1432; rev：7)。

告警中的MSG信息還包括如下應(yīng)用程序位置：聊天工具（chat）、游戲(game)、mail、oracle數(shù)據(jù)庫、策略(policy)、http服務(wù)器(sql-injection、web-attacks)、mysql數(shù)據(jù)庫、多媒體(windows media)等，均可從規(guī)則開始的大寫字符串獲得。

4.4.3 攻擊目的提取

目的是指攻擊者的攻擊意圖，即攻擊者希望得到的攻擊效果，這個要素的信息主要從classtype字段來獲得。將目的分為以下14類。

嘗試獲取權(quán)限（用戶、管理員）：attempted-userattempted-admin。

成功獲得權(quán)限（用戶、管理員）：successful-usersuccessful-user unsuccessful-user。

嘗試非法登錄（口令猜測，暴力破解）：suspicious-login default-login-attempt。

嘗試竊取信息：attempted-recon。

竊取信息成功失?。簊uccessful-recon-limitedsuccessful-recon-largescale。

掃描：network-scanprotocol-command-decode。

嘗試植入惡意內(nèi)容（代碼、命令、木馬）：shell code-detectsystem-call-detectstring-detect rojanactivity。

實施拒絕服務(wù)攻擊：attempted-dosdenial-ofservicesuccessful-dos。

木馬通信：trojan-activity。

正在實施拒絕服務(wù)攻擊：attempted-dos denial-of-servicesuccessful-dos。

針對Web應(yīng)用的攻擊：web-application-attackweb-application-activity on-standard-protocol。

違反內(nèi)部策略：policy-violation。

RPC服務(wù)攻擊：rpc-portmap-decode。

潛在可能攻擊、存在安全隱患或者無法識別的流量：unknownad-unknown。

4.4.4 攻擊場景還原

攻擊場景還原存在不能從告警信息中獲得完全的3個要素的情況。以端口掃描為例，一般情況下，端口掃描是為以后的攻擊打基礎(chǔ)，往往伴隨著后續(xù)的攻擊，如掃描一些特定的漏洞或者端口。但是如果只是單純的掃描IP地址則看不出攻擊的目的。

攻擊描述字符串不需要三要素都兼?zhèn)?。若三要素齊全，攻擊描述字符串為：行為+位置+“以”+目的；若沒有行為要素，攻擊描述字符串為：“針對”+位置+“以”+目的；若沒有目的要素，攻擊描述字符串為：行為+位置。具體攻擊場景還原實例見5.2節(jié)。

5 實驗測試

5.1 告警聚類算法測試

為了驗證算法的應(yīng)用效果，入侵檢測測試數(shù)據(jù)采用 KDDCUP99網(wǎng)絡(luò)數(shù)據(jù)集進行實驗?；煦缌Ｗ尤簠?shù)設(shè)置為：w =0.729 8，c1=c2=1.496 2，T=1 000，r(i,d)=0.5+0.005rand，N=20，Cid(t)=0.999，Ψd為各自搜索空間長度，Mi=0.5，粒子初始值為Ψd×Mi×(2*rand()-1)。

其中，粒子群算法結(jié)果來自文獻[9]。對比表1的結(jié)果可以看出：本文所提出的混沌粒子群告警聚類算法結(jié)果明顯好于粒子群告警聚類算法。本文平均告警檢測率為80.35%，高于POS-KM聚類算法的74.43%。而平均誤警率為1.35%，低于POS-KM聚類算法的 1.86%?？梢?，CPOS-KM 聚類算法更有效地檢測入侵攻擊行為。

表1 告警聚類算法比較結(jié)果

5.2 攻擊場景構(gòu)建測試

在真實網(wǎng)絡(luò)環(huán)境中，對攻擊場景構(gòu)建進行測試，在主機192.168.1.108上利用MS08-067漏洞，對主機192.168.1.114進行攻擊。聚合后告警有如下3條。

ALEART 1： 04/09-14：51：43.051508 [**] [1：648：10] SHELLCODE x86 NOOP [**] [Classification：Executable code was detected] [Priority： 1] {TCP}192.168.1.108：3169 -＞ 192.168.1.114：135。

場景構(gòu)建步驟1：針對SHELLCODE x86漏洞，以嘗試植入可執(zhí)行代碼。

ALEART 2： 04/09-14：51：43.051508 [**] [1：3397：8] NETBIOS DCERPC NCACN-IP-TCP ISystemActivatorRemoteCreateInstance attempt [**][Classification： Generic Protocol Command Decode][Priority： 3] {TCP} 192.168.1.108：3169 -＞ 192.168.1.114：135。

場景構(gòu)建步驟2：探測NETBIOS漏洞。

ALEART 3： 04/09-14：51：30.112161 [**] [1： 7209：10] NETBIOS DCERPC NCACN-IP- CP srvsvcNetr-PathCanonicalize overflow attempt [**] [Classification： Attempted Administrator Privilege Gain] [Priority：1] {TCP} 192.168.1.108：3161 -＞ 192.168.1.114：445。

場景構(gòu)建步驟 3：溢出 NETBIOS漏洞以嘗試獲得管理員權(quán)限。

結(jié)合主機入侵告警信息：最后一步為開啟目標(biāo)端口，攻擊成功。終上所述，入侵過程與告警場景構(gòu)建結(jié)果步驟相符合。

6 結(jié)束語

本文利用混沌的遍歷性和粒子群收斂快的特點，提出了一種新的混沌粒子群算法。該算法將混沌融入到粒子運動過程中，不同于己有的混沌粒子群算法的簡單粒子序列替換，使粒子群在混沌與穩(wěn)定之間交替向最優(yōu)點靠近。利用混沌粒子群算法指導(dǎo)K均值算法的初始聚類中心的選擇，從而使得聚類容易收斂到全局最優(yōu)，擺脫了初始聚類中心點選擇對最終聚類結(jié)果的影響。相對于目前的混沌粒子群算法，本文提出的混沌粒子群算法具有更好的跳出局部最優(yōu)，尋找全局最優(yōu)解的能力。通過對KDDCUP99數(shù)據(jù)集進行測試，實驗證明本文提出的混沌粒子群優(yōu)化告警算法具有較高的檢測率和較低的誤警率。在此基礎(chǔ)上，本文還引入了由聚類后的告警還原出攻擊場景的方法，經(jīng)實驗證明，該方法可以有效地還原攻擊步驟。

[1] VAARANDI R. Real-time classification of IDS alerts with data mining techniques[A]. MILCOM 2009[C]. Boston, Massachusetts： IEEE Press, 2009. 1-7.

[2] AI-MANIRY S O, ZHANG H L, ABBAS A R. IDS alarms reduction using data mining[A]. WCCI 2008[C]. Hong Kong, China： IEEE Press,2008. 3564-3570.

[3] PIETRASZEK T. Using adaptive alert classification to reduce false positives in intrusion detection[A]. RAID 2004[C]. Sophia Antipolis,France： Springer-Verlag. 2004. 102- 124.

[4] VIINIKKA J, DEBAR H, ANSSI L, et al. Processing intrusion detection alert aggregates with time series modeling[J]. Information Fusion Journal, 2009, 10(4)： 312-324.

[5] VAARANDI R, PODINS K. Network IDS alert classification with frequent item-set mining and data clustering[A]. CNSM 2010[C].Niagara Falls, Canada, IEEE Press, 2010. 451-456.

[6] NJOGU H W, LUO J W. Using alert cluster to reduce IDS alerts[A].ICCSIT 2010[C]. Chengdu, China, IEEE Press, 2010. 467-471.

[7] FEI A, DONG X L. Hierarchically clustering IDS alarms using a GA with vary-lengthed chromosomes[A]. ISIP 2010[C]. China： IEEE Press, 2010.172-177.

[8] LI Y Z, YANG G, XU J, et al. Anomaly detection for clustering algo-rithm based on particle swarm optimization[J]. Journal of Jiangsu University of Science and Technology(Natural Science Edition), 2009,23(1)： 51-55.

[9] WEN Z W, LI R J. Fuzzy C-means clustering algorithm based on improved PSO[J]. Application Research of Computers, 2010, 27(7)：2520-2522.

[10] XU X B, ZHENG K F, LI D, et al. A new chaos-particle swarm optimization algorithm[J]. Journal on Communications, 2012,33(1)：24-30.[11] LI L X, YANG Y X, PENG H P, et al. An optimization method inspired by chaotic ant behavior[J]. International Journal of Bifurcation and Chaos, 2006, 16： 2351-2364.

[12] SOLE R V, MIRAMONTES O, GOODWIN B C. Oscillations and chaos in ant societies[J]. Journal of Theoretical Biology, 1993, 161(3)：343-357.