宋 勇,蔡志平
(1.湖南民族職業(yè)學(xué)院工程技術(shù)系 湖南 岳陽 414000;2.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073)
隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展,計(jì)算機(jī)網(wǎng)絡(luò)在各個(gè)領(lǐng)域得到廣泛應(yīng)用,網(wǎng)絡(luò)安全也變得日益重要。入侵檢測(cè)是一種通過采集和分析被保護(hù)系統(tǒng)的信息從而發(fā)現(xiàn)入侵行為的技術(shù)。入侵檢測(cè)的數(shù)據(jù)源通常來自網(wǎng)絡(luò)中的數(shù)據(jù)包和系統(tǒng)的審計(jì)日志等,這些原始數(shù)據(jù)通常包含多達(dá)幾十個(gè)特征,如果直接將它們應(yīng)用到檢測(cè)算法中,將導(dǎo)致檢測(cè)速度緩慢,響應(yīng)不及時(shí)。因此,從大量特征中提取可替代的特征子集是入侵檢測(cè)數(shù)據(jù)預(yù)處理需要解決的重要問題。
如何選擇一個(gè)度量對(duì)量化特征進(jìn)行測(cè)度是在進(jìn)行特征選取前的一項(xiàng)重要工作。信息論中的熵是對(duì)隨機(jī)信息中不確定性的度量。熵作為一種良好全局測(cè)度,在特征選取時(shí),它能夠幫助我們尋找到更有作用的特征。本文在深入分析網(wǎng)絡(luò)流量數(shù)據(jù)集的基礎(chǔ)上,提出了一種改進(jìn)的面向入侵檢測(cè)的基于信息論模型的特征提取方法。
特征提取作為數(shù)據(jù)挖掘技術(shù)中的一項(xiàng)重要的預(yù)處理步驟,在機(jī)器學(xué)習(xí)領(lǐng)域具有重要的研究?jī)r(jià)值。根據(jù)樣本集是否有標(biāo)記,特征提取方法可以分為3種:無監(jiān)督學(xué)習(xí)算法[1-2]、半監(jiān)督學(xué)習(xí)算法[3-4]和有監(jiān)督學(xué)習(xí)算法[5-6]。有監(jiān)督模式特征提取算法是在計(jì)算類別與特征之間的相關(guān)度時(shí),依據(jù)標(biāo)記的類別信息,選擇類別區(qū)分力最大的特征子集。該算法的優(yōu)點(diǎn)是分類性能比較高,但缺點(diǎn)是必須在樣本集中標(biāo)記類別,故通用性不強(qiáng)。無監(jiān)督模式特征提取算法是在沒有前面的經(jīng)驗(yàn)指導(dǎo)下,通過特征間的內(nèi)在聯(lián)系,利用樣本數(shù)據(jù)的方差或分離性從特征集中提取重要的特征。該算法的優(yōu)點(diǎn)是無需具有標(biāo)記的數(shù)據(jù)樣本,具有一定的通用性,但性能不如有監(jiān)督模式特征提取算法,并且算法的時(shí)間和空間復(fù)雜度也高于前者。結(jié)合無監(jiān)督學(xué)習(xí)算法和有監(jiān)督學(xué)習(xí)算法,出現(xiàn)了半監(jiān)督模式特征提取算法,該算法為了提高大量未標(biāo)記類別樣本數(shù)據(jù)的特征提取,先對(duì)少數(shù)樣本數(shù)據(jù)標(biāo)記類別,并以之為指導(dǎo)。
根據(jù)與學(xué)習(xí)算法結(jié)合的方式不同,一般將特征提取算法大致分為4類:Embedded、Filter、Wrapper和Hybrid模型[7]。Embedded模型將特征提取與學(xué)習(xí)過程同時(shí)進(jìn)行,在學(xué)習(xí)訓(xùn)練的過程中選擇合適的特征,學(xué)習(xí)過程完成后,算法所涉及到的特征即為提取的特征結(jié)果。該模型的典型算法是決策樹算法,如文獻(xiàn)[8]提出的ID3和C4.5算法。Filter特征提取算法的評(píng)估標(biāo)準(zhǔn)直接由數(shù)據(jù)集求得,獨(dú)立于學(xué)習(xí)算法。該算法以特征之間相互獨(dú)立為條件,依據(jù)每一個(gè)特征對(duì)于分類的區(qū)分能力,選擇其中區(qū)分能力最強(qiáng)的n個(gè)特征進(jìn)行組合。與Filter模型特征提取算法不同,基于Wrapper模型的特征提取算法使用分類器的分類評(píng)價(jià)來確定特征子集,即首先利用分類器對(duì)不同的特征子集組合進(jìn)行評(píng)價(jià),然后對(duì)不同的特征子集評(píng)價(jià)對(duì)比得出最優(yōu)的特征子集。但是該算法一個(gè)明顯的缺點(diǎn)是算法的時(shí)間和空間復(fù)雜度比較高。Hybrid模型特征提取算法結(jié)合Filter模型和Wrapper模型確定最后的特征子集。它一般先采用前者除掉與類別無關(guān)的特征,然后將剩下的特征和類別作為后者的輸入,進(jìn)一步獲取最優(yōu)的特征子集。
特征選擇是一種典型的搜索尋優(yōu)問題。大小為n的特征集合,根據(jù)選擇或不選擇兩種情況,可以形成2n種集合空間,然后從這個(gè)空間中搜索出最優(yōu)的結(jié)果。但是在特征數(shù)目多的情況下,如果采用窮盡式的選擇算法,那么將會(huì)導(dǎo)致特征選擇過程占用大量的計(jì)算資源、花費(fèi)大量的時(shí)間,因此許多研究人員致力于用一種智能化的搜索算法來尋找最優(yōu)解。一般特征選擇算法必須確定以下4個(gè)方面[9]:1)搜索起點(diǎn);2)搜索策略;3)特征評(píng)估函數(shù);4)終止條件。本文從這4個(gè)方面出發(fā),根據(jù)入侵檢測(cè)中數(shù)據(jù)集的特點(diǎn),提出了一種結(jié)合信息熵中的信息增益和條件互信息概念的特征提取方法。
設(shè)入侵檢測(cè)訓(xùn)練數(shù)據(jù)集為D,|D|表示其樣本的容量,即樣本個(gè)數(shù)。設(shè)數(shù)據(jù)集中的類別標(biāo)記為C={C1,C2,…,Ck},在本文中將入侵檢測(cè)數(shù)據(jù)集類別標(biāo)記劃分為normal和abnormal兩類,即將所有正常數(shù)據(jù)標(biāo)記為normal,所有攻擊數(shù)據(jù)均標(biāo)記為abnormal,因此|Ci|=2。數(shù)據(jù)集中類別標(biāo)記集合F是類別C的一種組合。設(shè)數(shù)據(jù)集的特征集合為T={t1,t2,…,tn},|T|表示其特征的個(gè)數(shù),T′為特征集合T的一個(gè)子集,即T′?T。特征選取方法的基本思想是從原特征集合T中選擇出它的—個(gè)子集構(gòu)成新的特征空間。
對(duì)于某一個(gè)特征tx,其可能取值集合記為Stx。對(duì)于x∈Stx,其概率為P(x),根據(jù)Shannon信息理論,tx的信息熵定義為:
在信息論里面,式(1)是信息不確定性的一個(gè)度量,值越大則表示信息的不確定程度越高。對(duì)于訓(xùn)練數(shù)據(jù)集,可以得到數(shù)據(jù)集類別標(biāo)記集合的信息熵為H(F),也是數(shù)據(jù)集的經(jīng)驗(yàn)熵。
當(dāng)訓(xùn)練數(shù)據(jù)集中特征ty已知時(shí),特征tx中剩余的不確定性用條件熵來定義:
對(duì)于訓(xùn)練數(shù)據(jù)集中兩個(gè)隨機(jī)特征tx和ty的統(tǒng)計(jì)依存關(guān)系用互信息來定義:
互信息越大,這兩個(gè)隨機(jī)特征之間的聯(lián)系越緊密;當(dāng)互信息趨近于零時(shí),這兩者之間相互獨(dú)立。
在機(jī)器學(xué)習(xí)領(lǐng)域,信息增益作為信息論統(tǒng)計(jì)中的一個(gè)重要概念被廣泛應(yīng)用。對(duì)分類系統(tǒng)來說,信息增益是某—特征項(xiàng)t在系統(tǒng)中出現(xiàn)與否的信息量之差,它定義為:
式中,p(ci)表示ci類在樣本標(biāo)記集合F中出現(xiàn)的概率;p(t)和p(t′)表示數(shù)據(jù)集中特征t所有取值的概率;p(ci|t)和p(ci|t′)表示數(shù)據(jù)集中特征t取某一值時(shí)屬于ci類的概率。在特征選擇中,某個(gè)特征的信息增益越大,說明它的作用越大,對(duì)F也越重要。因此,在進(jìn)行特征選擇時(shí),信息增益值大的特征將會(huì)是候選特征。但通過式(4)可以看出:給定一個(gè)數(shù)據(jù)集后,它的H(F)是固定的,因此IG(t)的大小取決于H(F|t)。當(dāng)特征t的取值都不相同時(shí),H(F|t)將會(huì)等于0,這時(shí)IG(t)將最大,顯然這種情況的特征意義不大。因此根據(jù)C4.5[8]算法,為了解決這個(gè)問題,一般采用信息增益率,定義如下:
式中,H(t)表示特征t的信息熵。
在入侵檢測(cè)數(shù)據(jù)集中,類別標(biāo)記是由離散型數(shù)據(jù){normal,abnormal}表示,但有些樣本特征的值是連續(xù)型的數(shù)據(jù),如duration、src_bytes等特征的值。在評(píng)判這些連續(xù)特征與類別標(biāo)記的相關(guān)性時(shí),需要對(duì)連續(xù)特征進(jìn)行離散化。由于入侵檢測(cè)數(shù)據(jù)集的類別標(biāo)記只有normal和abnormal兩類,所以對(duì)于連續(xù)型特征的值域只需要將它們劃分為兩個(gè)區(qū)域,分別對(duì)應(yīng)前面的兩種標(biāo)記類型。具體劃分點(diǎn)的計(jì)算方法如下。
對(duì)于連續(xù)特征T,對(duì)它的樣本數(shù)據(jù)集中不重復(fù)的值經(jīng)排序后為v1<v2<…<vn,并按下面的步驟進(jìn)行計(jì)算:
1) 設(shè)i=1;
2)令v=(vi+vi+1)/2;設(shè)樣本數(shù)據(jù)集中特征T的值≤v時(shí)為0,>v時(shí)為1;
3) 令I(lǐng)i=I(T;C),設(shè)i=i+1,重復(fù)步驟2),直到i≤n;
4) 輸出{I1,I2,…}值最大對(duì)應(yīng)的v值。
v值就是特征T值域的劃分點(diǎn),利用該值將特征T的值域分成兩個(gè)區(qū)域,按照約定分別將在這兩個(gè)區(qū)域的值指定為0或者1。
被選取特征子集的初始狀態(tài)稱為算法的搜索起點(diǎn),它對(duì)搜索結(jié)果有十分重要的影響。當(dāng)被選取特征子集為空時(shí),可以按照一定方法逐個(gè)地向被選取特征子集加入特征;當(dāng)被選取特征子集為全集時(shí),可以按照一定方法不斷地刪減特征;當(dāng)被選取特征子集從特征集的某個(gè)子集開始時(shí),那么搜索策略一般采用隨機(jī)或者啟發(fā)式。
本文根據(jù)最優(yōu)被選取特征集中一定包含了對(duì)數(shù)據(jù)集類別信息增益最高的特征這一原則,搜索起點(diǎn)為:max{IGR(t1), IGR(t2),…, IGR(tn)}。IGR函數(shù)為某一特征的信息增益率,具體如式(5)所示。
被選取特征集搜索算法一般采用順序搜索和隨機(jī)搜索。順序搜索算法采用順序的方式,從特征集中選取特征到被選取特征集,從而逐步擴(kuò)展搜索,如順序前向搜索和順序后向搜索等。隨機(jī)搜索算法包括模擬退火、遺傳算法和集束式搜索等。本算法采用順序搜索的方式,基本步驟如下:
1) 初始化:提取特征子集T′=max{IGR(t1), IGR(t2),…, IGR (tn)},T={除T′外所有的屬性};
2) ?t∈T,按特征評(píng)估函數(shù)計(jì)算特征t的值;
3)計(jì)算T集合中所有特征的值,獲得具有最大值的特征tmax,設(shè)置T=T?{tmax},T′=T′∪{tmax};
4)重復(fù)步驟2)和步驟3)直至滿足終止條件;
5)輸出特征集T′。
特征評(píng)估函數(shù)是特征選擇的評(píng)價(jià)標(biāo)準(zhǔn),即可以利用單獨(dú)的特征獨(dú)立進(jìn)行評(píng)價(jià),也可以利用某個(gè)特征子集整體進(jìn)行評(píng)價(jià)。
在文獻(xiàn)[10]中,針對(duì)利用信息增益思想提取特征時(shí)存在的一些問題,分別提出了增加了頻度、集中度和分散度3項(xiàng)測(cè)試指標(biāo)的方法。在MaxMI[11]特征選擇算法中,提出了最大化互信息的基本思想,即提取的特征子集應(yīng)當(dāng)盡可能多地提供關(guān)于類別的信息,也就是最大化I(C;T′)。這兩個(gè)算法最大的問題就是只考慮到了各特征與類別之間的關(guān)系,而沒有考慮到提取的特征之間的相互影響。在PG-HMI[12]算法中,雖然評(píng)估函數(shù)即考慮到了特征選取準(zhǔn)則既與屬性能夠提供的新信息量I(C;f |S)相關(guān),也與屬性和類別標(biāo)記的相關(guān)度I(C;f)相關(guān),但是沒有考慮到新選擇的特征f可能會(huì)對(duì)已提取的特征子集產(chǎn)生冗余。
結(jié)合前面的研究成果和信息論模型,提出一種基于信息論模型的特征選擇算法,該算法即考慮到在已選取特征子集確定的條件下,候選特征與類別之間的關(guān)系,又將候選特征與已選取特征子集之間的相關(guān)度作為該特征是否選取的重要依據(jù)。
設(shè)原始特征集為T={T1,T2,…,Tn},選取的特征子集為T′={T′1,T′2,…},候選特征為t。在已選取特征子集確定的條件下,候選特征與類別之間的相關(guān)性根據(jù)式(2)和式(3)得到:
候選特征與已選取特征子集之間的相關(guān)度定義為:
式中,H(t)表示候選特征數(shù)據(jù)集的信息熵;表示候選特征數(shù)據(jù)集與當(dāng)前已選取特征子集數(shù)據(jù)集的聯(lián)合熵;表示當(dāng)前已選取特征子集數(shù)據(jù)集的聯(lián)合熵。式(7)的值等于零時(shí),表示候選特征與已選取特征子集不相關(guān)。但是根據(jù)入侵檢測(cè)數(shù)據(jù)集的分析,MI(t;T′)為零的可能性幾乎很小,所以必須設(shè)置一個(gè)閥值控制候選特征與已選特征子集之間的相關(guān)度。
綜合上述得到本算法的搜索評(píng)估函數(shù)為:
該函數(shù)表示在已選取特征子集確定的條件下,從所有候選特征中選取與已選取特征子集的互信息小于閥值ε∈[0,1]、并且與樣本標(biāo)記的互信息值最大且大于零的特征。
算法的終止條件可以選擇固定的迭代次數(shù)和特征數(shù)目來進(jìn)行,也可以自己定義終止條件函數(shù)。本算法的終止條件為:
上述終止條件表示當(dāng)所有候選特征在已選取特征子集確定的條件下,與樣本標(biāo)記的互信息都小于閥值β∈[0,1]時(shí)終止,或者在前面表達(dá)式不成立的條件下,所有候選特征與已選取特征子集的互信息大于閥值ε∈[0,1]。
為了檢驗(yàn)本文提出的特征提取算法的有效性,選用了KDD99數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集。KDD CUP 1999數(shù)據(jù)集是由麻省理工學(xué)院的林肯實(shí)驗(yàn)室采用1998年美國(guó)國(guó)防部高級(jí)規(guī)劃署的入侵檢測(cè)數(shù)據(jù)集建立起來的。數(shù)據(jù)提取了41個(gè)特征,包括34個(gè)連續(xù)型特征和7個(gè)離散型特征。
由于原始數(shù)據(jù)集過于龐大,因此只選取KDD99中的kddcupdata10percent數(shù)據(jù)集。該數(shù)據(jù)集包含494 021條連接記錄,其中攻擊連接記錄396 743條,正常連接記錄97 278條,攻擊類型22個(gè)。為了驗(yàn)證本算法提取的特征集對(duì)未知攻擊類型的有效性,在訓(xùn)練數(shù)據(jù)集中只包含12種攻擊類型,記錄條數(shù)4 000條,其中攻擊記錄2 000條。測(cè)試數(shù)據(jù)集中包含22種攻擊類型,記錄條件10 000條,其中攻擊記錄3 000條。
在實(shí)驗(yàn)過程中,本方法的主要參數(shù)是搜索函數(shù)和終止條件函數(shù)的兩個(gè)閥值。其中通過閥值β可以控制選取特征子集與樣本標(biāo)記的相關(guān)性程度。如果β太大,它們的相關(guān)程度變高,入選特征數(shù)少,可能一些較重要的特征無法選取,從而導(dǎo)致分類算法精確度不高;若β值太小,入選特征數(shù)變多,不利于分類算法的性能。通過多次實(shí)驗(yàn),確定β為0.35。閥值ε主要控制被提取特征之間的相關(guān)性程度,較大時(shí)導(dǎo)致被提取特征之間的冗余度較高,因此ε值設(shè)為0.05。
實(shí)驗(yàn)環(huán)境為CPU Inter Core i7 2.50 GHz,內(nèi)存8.00 GB,操作系統(tǒng)Windows8 64位,開發(fā)工具M(jìn)atlab2010。
根據(jù)上面的實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)設(shè)置,利用本文提出的特征提取算法,得到特征子集的屬性ID為1、3、5、6、12、23、24、32、33、36、37、40。為了驗(yàn)證特征選取的有效性,本文使用支持向量機(jī)分類算法(support vector machines, SVM)對(duì)測(cè)試數(shù)據(jù)集進(jìn)行兩組實(shí)驗(yàn),分別是原始特征全集和本文提出的方法所選出的特征子集,并進(jìn)行入侵檢測(cè)性能評(píng)估。本文采用檢測(cè)時(shí)間、檢測(cè)率和誤報(bào)率3個(gè)評(píng)價(jià)指標(biāo)進(jìn)行性能評(píng)估,其中:
式中,DR表示檢測(cè)率;DC表示檢測(cè)的異常記錄個(gè)數(shù);AC表示真實(shí)入侵記錄個(gè)數(shù);FPR表示誤碼報(bào)率;MIC表示正常記錄誤報(bào)為異常的個(gè)數(shù);NIC表示正常記錄個(gè)數(shù)。實(shí)驗(yàn)結(jié)果如表1所示。
表1 特征提出前后的效果比較
從表中可以看出,使用本文的特征提取算法,特征維度降低了70.7%,但是檢測(cè)率和誤警率影響不大,算法的處理速度提高了50.8%。
本文面向入侵檢測(cè)提出了一種基于信息論模型的特征提取方法,本方法依據(jù)最優(yōu)被選取特征集中一定包含對(duì)數(shù)據(jù)集類別信息熵增益最高的特征這一原則,首先從所有特征中選取信息增益最大的特征作為搜索起點(diǎn),然后充分考慮樣本數(shù)據(jù)集分類標(biāo)記、已選取特征子集和候選特征三者之間的信息相關(guān)性基礎(chǔ)上順序搜索最合適的特征,最后在搜索終止條件下完成所有特征的選取。通過在KDD99數(shù)據(jù)集上的實(shí)驗(yàn)表明,本文提出的特征選擇方法在保證檢測(cè)準(zhǔn)確率的前提下,大大降低了入侵檢測(cè)數(shù)據(jù)的特征維度,從而減輕了檢測(cè)系統(tǒng)的存儲(chǔ)負(fù)擔(dān),提高了入侵檢測(cè)分類器的性能。后續(xù)將在真實(shí)系統(tǒng)架構(gòu)[13]中驗(yàn)證本文方法在大數(shù)據(jù)流量情況的性能,并考慮在Spark等大數(shù)據(jù)處理平臺(tái)[14]上的實(shí)現(xiàn)方法。
[1]CHIMIENTI M,CORNULIER T,OWEN E.The use of an unsupervised learning approach for characterizing latent behaviors in accelerometer data[J].Ecology & Evolution,2016, 6(3): 1948-1952.
[2]楊國(guó)亮, 謝乃俊, 王艷芳, 等.基于低秩稀疏評(píng)分的非監(jiān)督特征選擇[J].計(jì)算機(jī)工程與科學(xué), 2015, 37(4): 649-656.YANG Guo-liang, XIE Nai-jun, WANG Yan-fang, et al.Unsupervised feature selection based on low rank and sparse score[J].Computer Engineering and Science, 2015,37(4): 649-656.
[3]]ZHENG Zhao, LIU Huan.Semi-supervised featrue selection via spectral analysis[C]//Proceedings of the 7th SIAM International Conference on Data Mining.[S.l.]:DBLP, 2007: 1193-1201.
[4]史彩娟.網(wǎng)絡(luò)空間圖像標(biāo)注中半監(jiān)督稀疏特征選擇算法研究[D].北京: 北京交通大學(xué), 2015.SHI Cai-juan.Research on semi-supervised sparse feature selection for image annotation in web space[D].Beijing:Beijing Jiaotong University, 2015.
[5]YU Lei, LU Ling.Featrue selection based on loss-margin of nearest neighborclassification[J].Pattern Recongnition,2009, 42(9): 1914-1921.
[6]鄭瑩斌.有監(jiān)督的視覺特征提取算法研究[D].上海: 復(fù)旦大學(xué), 2013.ZHENG Ying-bin.Research on supervised visual feature extraction algorithms[D].Shanghai: Fudan University, 2013.
[7]MANSOORI E G, SHAFIEE K S.On fuzzy feature selection in designing fuzzy classifiers for high-dimensional data[J].Evolving Systems, 2015, 7(4): 1-11.
[8]QUINLAN J R.Programs for machine learning[M].San Mateo, CA: Morgan Kaufmann, 1993.
[9]張麗新, 王家欽, 趙雁南, 等.機(jī)器學(xué)習(xí)中的特征選擇[J].計(jì)算機(jī)科學(xué), 2004, 31(11): 180-184.ZHANG Li-xin, WANG Jia-qin, ZHAO Yan-nan, et al.Feature selection in machine learining[J].Computer Science,2004, 31(11): 180-184.
[10]李玲, 劉華文, 徐曉丹, 等.基于信息增益的多標(biāo)簽特征選擇算法[J].計(jì)算機(jī)科學(xué), 2015, 42(7): 52-56.LI Ling, LIU Hua-wen, XU Xiao-dan, et al.Multi-label feature selection algorithm based on information gain[J].Computer Science, 2015, 42(7): 52-56.
[11]唐亮, 段建國(guó), 許洪波, 等.基于互信息最大化的特征選擇算法及應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用, 2008, 44(13):130-133.TANG Liang, DUAN Jian-guo, XU Hong-bo, et al.Mutual information maximization based feature selection algorithm in text classification[J].Computer Engineering and Applications, 2008, 44(13): 130-133.
[12]WANG H, SUN H B, ZHANG B M.PG-HMI: Mutual information based feature selection method[J].Pattern Recognition & Artificial Intelligence, 2007, 20(1): 55-63.
[13]CAI Zhi-ping, WANG Zhi-jun, ZHENG Kai, et al.A distributed TCAM coprocessor architecture for integrated longest prefix matching, policy filtering, and content filtering[J].IEEE Trans Computers, 2013, 62(3): 417-427.
[14]方峰, 蔡志平, 肇啟佳, 等.使用Spark Streaming的自適應(yīng)實(shí)時(shí)DDoS檢測(cè)和防御技術(shù)[J].計(jì)算機(jī)科學(xué)與探索,2016, 10(5): 601-611.FANG Feng, CAI Zhi-ping, ZHAO Qi-jia, et al.Adaptive technique for real-time DDoS detection and defense using spark streaming[J].Journal of Frontiers of Computer Science and Technology, 2016, 10(5): 601-611.