基于數(shù)字微分的函數(shù)化樹突狀細(xì)胞算法模型

張 藝,周 雯,梁意文,譚成予

(武漢大學(xué) 計算機(jī)學(xué)院,武漢 430072)

0 概述

人工免疫系統(tǒng)(Artificial Immune System,AIS)是受到人體免疫系統(tǒng)啟發(fā),模擬其行為、機(jī)制和功能的計算機(jī)系統(tǒng)[1],可用于解決信息安全領(lǐng)域的多個問題,包括惡意代碼檢測、入侵檢測、垃圾郵件檢測、shellcode檢測等[2]。AIS算法根據(jù)應(yīng)用類別主要分為優(yōu)化算法、學(xué)習(xí)算法和異常檢測算法。異常檢測算法能夠解決計算機(jī)安全的相關(guān)問題[3],其中代表算法為樹突狀細(xì)胞算法(Dendritic Cell Algorithm, DCA)。

目前樹突狀細(xì)胞算法已經(jīng)成功應(yīng)用于諸多安全相關(guān)領(lǐng)域,解決了具體的入侵檢測問題,其中包括端口掃描檢測[4]、僵尸網(wǎng)絡(luò)檢測[5]、機(jī)器人安全分類器[6]、ping掃描檢測[7]、服務(wù)器攻擊檢測[8]以及電網(wǎng)攻擊檢測[9]等,近年來也被應(yīng)用于地震預(yù)測[10]和網(wǎng)絡(luò)水軍檢測[11]等方面。

GREENSMITH等人于2005年提出最初的樹突狀細(xì)胞算法(prototype DCA,pDCA)模型,并證明這種基于種群的算法能夠?qū)τ行驍?shù)據(jù)進(jìn)行兩類判別[12],此后其又完善了算法使用的步驟和流程,提出了更完整的模型(libtissue DCA,ltDCA)[13]。盡管ltDCA已被證明在諸多應(yīng)用中有效,但其存在算法可控性差(相互作用參數(shù)和隨機(jī)元素多)、信號預(yù)處理方法不明確、算法缺乏形式化規(guī)范、可分析性差等不足[14]。針對可控性差的問題,GREENSMITH等人通過去除大部分隨機(jī)性參數(shù),提出了輕量級的算法模型——確定性樹突狀細(xì)胞算法(deterministic DCA,dDCA)模型[15]。近年來也有學(xué)者對原算法的信號提取進(jìn)行優(yōu)化,如結(jié)合XGBoost的改進(jìn)算法[16]和集成PCA的改進(jìn)算法[17],但都沒有給出明確的形式化描述。在理論分析方面,GU等人對DCA和dDCA進(jìn)行了形式化描述[18],但描述與實現(xiàn)細(xì)節(jié)混雜在一起,缺少數(shù)據(jù)流和函數(shù)定義;GREENSMITH等人引入事件流的概念,在dDCA的基礎(chǔ)上,對算法進(jìn)行了函數(shù)化描述,形成了較為明確的規(guī)范(deterministic DCA in Haskell,hDCA)[19]。在信號預(yù)處理階段,通過特征選擇機(jī)制提取信號的方式會損壞數(shù)據(jù)特征的隱含意義,因此,CHELLY等人結(jié)合模糊粗糙集的方法[20]避免了信息損失,但該方法仍存在信號提取受人工影響、普適性差的不足。

通過數(shù)字微分可以依據(jù)數(shù)據(jù)的變化和變化趨勢來感知危險[21],在信號提取階段使用能夠自適應(yīng)提取危險信號(DS)和安全信號(SS),解決上述算法普適性差的問題。為此,本文在hDCA模型的基礎(chǔ)上,結(jié)合數(shù)字微分改進(jìn)原算法中的信號提取過程,建立基于數(shù)字微分的函數(shù)化樹突狀細(xì)胞算法(numerical differentiation based hDCA,ndhDCA)模型,并將其應(yīng)用于UCI機(jī)器學(xué)習(xí)庫,與傳統(tǒng)DCA和dDCA模型進(jìn)行性能比較。

1 相關(guān)知識

1.1 數(shù)字微分

數(shù)據(jù)的變化及數(shù)據(jù)的變化趨勢被認(rèn)為是異常檢測的基礎(chǔ)?！拔ｋU”通常表現(xiàn)為數(shù)據(jù)的異常,可用于評估數(shù)據(jù)集中各項要素的重要性。數(shù)字微分[21]是一種通過研究離散數(shù)據(jù)集,分析數(shù)值變化和變化趨勢來感知“危險”的方法,能夠從全部特征集中提取應(yīng)用環(huán)境的所需特征。數(shù)字微分包括數(shù)值微分、數(shù)組微分和向量微分,在實際使用中可根據(jù)數(shù)據(jù)的特點選用合適的算子并加以調(diào)整。

文獻(xiàn)[22]利用數(shù)字微分從應(yīng)用環(huán)境的信號中自適應(yīng)地提取危險信號,建立基于變化的自適應(yīng)危險信號提取模型。文獻(xiàn)[23]將數(shù)字微分用于入侵檢測的數(shù)據(jù)預(yù)處理過程,提高了入侵檢測的準(zhǔn)確率。文獻(xiàn)[24]將數(shù)字微分結(jié)合樹突狀細(xì)胞算法用于故障檢測,在提高檢測率的同時實現(xiàn)較早檢測到漸變性故障的目標(biāo)。

1.2 DCA發(fā)展及hDCA介紹

DCA是一種免疫啟發(fā)算法,最初基于天然樹突細(xì)胞的功能,因為其具有非常低的CPU處理要求并且不需要大量的訓(xùn)練期,所以在應(yīng)用于實時計算機(jī)安全問題時具有明顯的優(yōu)勢。DCA應(yīng)用于端口掃描檢測、僵尸網(wǎng)絡(luò)檢測、無線傳感器不良行為檢測、機(jī)器人安全等方面都取得了較好的效果。但由于算法中相互作用的參數(shù)數(shù)量過多,相關(guān)研究中參數(shù)設(shè)置和可變閾值設(shè)置較為隨意。GREENSMITH等人對DCA進(jìn)行分解并測試其內(nèi)在關(guān)系,對算法進(jìn)行了參數(shù)簡化,并提出新的異常度量,建立了可控性更強(qiáng)的確定性樹突狀細(xì)胞算法模型dDCA[15]。2010年,CHELLY等人新增了兩個信號模型,采用模糊集切換輸入流數(shù)據(jù),利用模糊子集修改信號變換方程,由此建立模糊樹突狀細(xì)胞模型FDCM,提高了算法性能[25]。2011年,GU等人提出xDCA[26],通過引入自動化信號預(yù)處理過程,使用主成分分析法并利用特征選擇機(jī)制自適應(yīng)選擇信號流的數(shù)據(jù)源。

在理論研究方面,OATES等人于2007年發(fā)現(xiàn)了DCA算法的濾波和降噪屬性,并指出算法具有線性分類器屬性[27]。2009年,STIBOR等人使用點積構(gòu)建信號處理階段的模型,并且演示了其線性分類器屬性,結(jié)果表明DCA可能遇到與線性分類器相同的問題:分類邊界復(fù)雜造成錯誤和處理動態(tài)超平面問題的性能受損[28]。2011年,GU等人以支持向量機(jī)代替線性分類階段,發(fā)現(xiàn)DCA的濾波屬性在應(yīng)用于噪聲流數(shù)據(jù)時會提高性能,但在傳統(tǒng)機(jī)器學(xué)習(xí)數(shù)據(jù)集上表現(xiàn)較差[29]。MUSSELLE研究了事件流對DCA的影響,發(fā)現(xiàn)DCA對流數(shù)據(jù)的延遲具有魯棒性[30]。

結(jié)合以上研究結(jié)果,GREENSMITH將流作為輸入,基于dDCA對算法進(jìn)行函數(shù)化的聲明和表達(dá),并使用Haskell進(jìn)行實現(xiàn)[19]。Haskell是一種純函數(shù)式編程語言,其中程序的規(guī)范被解釋為其實現(xiàn)。hDCA規(guī)范由集合上的純數(shù)學(xué)函數(shù)組成,與之前算法使用一系列抽象步驟來呈現(xiàn)的方式不同。該規(guī)范適用于多數(shù)編程語言,也可用于正式推理算法[19]。

1.3 問題描述

xDCA、dDCA和hDCA在信號提取和信號分類時均采用了主成分分析法,這使得進(jìn)行危險信號和安全信號選取時依賴于人工經(jīng)驗,一旦確定之后就不可更改,不具備自適應(yīng)性。而數(shù)字微分方法可以自適應(yīng)地提取信號并隨機(jī)動態(tài)采樣抗原,去除信號提取和敏感的數(shù)據(jù)序列。因此,本文提出ndhDCA模型,在輸入數(shù)據(jù)的預(yù)處理階段引入數(shù)字微分方法描述數(shù)據(jù)變化將導(dǎo)致“危險”這一特性,并利用數(shù)據(jù)的變化自適應(yīng)提取需要的輸入信號。

2 ndhDCA模型

2.1 模型框架

ndhDCA模型架構(gòu)包括數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、信號融合、抗原背景評估與分類以及函數(shù)式描述模塊,如圖1所示。

圖1 ndhDCA模型架構(gòu)

數(shù)據(jù)采集模塊通過從實際應(yīng)用環(huán)境(或已有的數(shù)據(jù)集)中獲得的所有特征建立原始抗原庫,再從其中構(gòu)建候選抗原庫和候選信號庫,以便后續(xù)處理和評估抗原。

數(shù)據(jù)預(yù)處理模塊將數(shù)字微分用于選取候選信號庫中的信號,通過深入的數(shù)據(jù)分析檢測每個時間窗下數(shù)據(jù)的變化,在考慮特征變化和特征之間相互作用的前提下,自適應(yīng)地提取危險信號和安全信號,將其作為信號融合階段的輸入。

信號融合模塊利用人工樹突狀細(xì)胞群(DCs)對抗原進(jìn)行取樣,從信號集中獲取危險信號和安全信號。當(dāng)樹突狀細(xì)胞成熟時,通過累積輸出信號濃度來確定抗原環(huán)境。

抗原環(huán)境評估與分類模塊通過每次累積的數(shù)據(jù)計算環(huán)境評估的度量值MCAV和K值,以確定抗原環(huán)境處于異常還是正常。

函數(shù)式描述模塊對上述過程分別進(jìn)行函數(shù)化描述,這也是模型最重要的部分。

2.2 基礎(chǔ)理論

通常,數(shù)據(jù)流是一組有時間序列的數(shù)據(jù)。流是一個有限的列表。任意集合X上的列表集用ListX表示,有以下兩種情況:

1)空列表ε是ListX的一個元素。

2)如果x∈X且xs∈Listx,則x:xs∈Listx,x:xs讀作“xconsxs”。

由此可知,空表ε是任意集合X上列表集合的元素,只要X具有至少一個元素,那么就可以利用上述第2種情況將X的每個元素添加到Listx中任何列表的開頭,因此,Listx就具有無限數(shù)量的元素。例如,X={1},由1∶ε∈Listx可以推出1∶(1∶ε)∈Listx。

因為流總是有限的,所以可用列表相同的方式對其進(jìn)行歸納描述,但需要去掉空列表的情況,以Streamx表示任意集合X上的流集合,其可以被描述為“若x∈X,xs∈Streamx,則x?xs∈Streamx”。

2.3 數(shù)字微分信號提取

在數(shù)據(jù)預(yù)處理階段,輸入由各指標(biāo)數(shù)據(jù)構(gòu)成,數(shù)字微分用于從指標(biāo)集{m1,m2,…,mn}中選取特定指標(biāo)作為危險信號或安全信號。將此階段的輸入信號稱為原始數(shù)據(jù)流,它由各指標(biāo)和時間戳T組成,表示為:

M=Stream(T×m1×m2×…×mn)

(1)

用s0表示危險信號,安全信號s1表示s0和s1都由原始數(shù)據(jù)流經(jīng)過數(shù)字微分選取指標(biāo)并融合各指標(biāo)后得到,將此過程稱為Mix,則s0和s1可以被表示為:

s0,s1=Mix[Stream(T×m1×m2×…×mn)]

(2)

上述過程主要包括以下3個步驟:

1)將各指標(biāo)歸一化,用數(shù)字微分計算每個指標(biāo)mi的變化率。

假設(shè)指標(biāo)與時間之間的映射關(guān)系為fmi(ti),指標(biāo)mi左右側(cè)可描述為:

(3)

(4)

指標(biāo)mi的變化趨勢可描述為:

fmi(ti)=fmi(ti)right-fmi(ti)left

(5)

上述過程可通過數(shù)字微分實現(xiàn),將其稱為numeric,表示為:

numeric:mi×T→Δmi

numeric(mi,T)=fmi(ti)right-fmi(ti)left

(6)

2)對指標(biāo)mi進(jìn)行分類,判定是作為危險信號s0還是安全信號s1,將此過程稱為divide,設(shè)判定的閾值為k,則有:

divide:mi→si{m1,m2,…,mn}

(7)

3)累計多個指標(biāo)融入信號中,作為下一步過程的輸入。將累計到信號si的過程命名為addsi,危險信號s0的累積過程如下:

adds0:mi→si

(8)

2.4 信號融合

2.4.1 輸入

ndhDCA模型兩個輸入均為數(shù)據(jù)流,一個稱為事件流(抗原流),另一個稱為信號流。事件(抗原)是E×T的元素,其中,E是抗原(事件)的類型集合,T是時間戳集合。因而事件流可以被定義為:

A=Stream(E×T)

(9)

S=Stream(T×s0×s1)

(10)

2.4.2 樹突狀細(xì)胞

人工樹突狀細(xì)胞接收輸入信號并用他們計算3個決策信號,即激活信號、抑制信號和遷移信號。用實數(shù)三元組表示這三個信號:

(11)

每個樹突狀細(xì)胞由事件集、3個信號值和遷移閾值組成。事件緩沖區(qū)es用于記錄細(xì)胞在其生命周期中遇到的事件,遷移閾值決定了細(xì)胞的生命周期。因此,細(xì)胞可被定義為:

(12)

給定遷移閾值d,則初始化新細(xì)胞的方法可以表示為:

new(d)=(?,(0.0,0.0,0.0),d)

(13)

定義以下方法判定細(xì)胞是否達(dá)到生命周期,如果達(dá)到遷移閾值,則評估為true,否則為false:

dead:Cell→B

dead(es,(ωA,ωI,ωM),d)=ωM≥d

(14)

如果某個細(xì)胞的dead值為true,則對該細(xì)胞使用reset方法重置事件緩沖區(qū)和決策信號,并保持原始的遷移閾值:

reset:Cell→Cell

reset(es,os,d)=new(d)

(15)

當(dāng)細(xì)胞達(dá)到遷移閾值時,計算細(xì)胞的臨時異常分?jǐn)?shù),然后將其分配給細(xì)胞事件緩沖區(qū)的每個事件。有以下2種度量方法:

1)利用成熟背景抗原值MCAV,返回特定事件被分類為異常的概率,定義如下:

(16)

2)如果激活信號ωA大于抑制信號ωI,則細(xì)胞將其緩沖區(qū)的事件判定為異常,要計算細(xì)胞的實際度量,需要獲取ωA減去ωI的值,這是一種真實度量(在dDCA中稱為Kα):

(17)

2.4.3 信號融合

信號融合由以下3個步驟組成:

1)用信號流中當(dāng)前元素獲得的信號值,迭代更新細(xì)胞總?cè)褐兴屑?xì)胞的決策信號,此過程稱為updateS,其中,N表示細(xì)胞總?cè)?p表示當(dāng)前的一個細(xì)胞:

updateS:(T×R1×R2)×N→N

updateS((_,s0,s1),p)=

{(es,accumulate(d,transduction(s0,s1),t))|(es,d,t∈p)}

(18)

更新細(xì)胞決策信號階段分為兩個部分,其中,transduction把當(dāng)前輸入的信號值映射到細(xì)胞各個決策信號,將輸入的危險信號s0、安全信號s1轉(zhuǎn)化為決策信號。accumulate將當(dāng)前的決策信號累加到先前決策信號,計算出細(xì)胞新的決策信號。為計算決策信號,本文應(yīng)用線性函數(shù),用ω=ωj×si+…+ωj×si形式的公式來表示,其中,ω是正在計算的判定信號,si是輸入信號,ωj是權(quán)重。權(quán)重可從生物免疫學(xué)對樹突狀細(xì)胞的實驗中獲得,如表1所示。

表1 信號融合權(quán)重Table 1 Fused weights of signals

由表1中的權(quán)重得出決策信號計算公式:

ωA=s0+(-2.0)×s1

ωI=s1

ωM=s0+s1

(19)

由此,transduction的函數(shù)表達(dá)式可定義為:

transduction(s0,s1)=

(s0+(-2.0)×s1,s1,s0+s1)

(20)

一旦計算了來自兩個輸入信號的決策信號的值,則需要將它們添加到細(xì)胞的決策信號的當(dāng)前值,由此accumulate可被描述為:

accumulate((ωA,ωI,ωM),(ω′A,ω′I,ω′M))=

(ωA+ω′A,ωI+ω′I,ωM+ω′M)

(21)

2)更新決策信號導(dǎo)致每個細(xì)胞的遷移值增加,即ωM增加。因此,需要檢查細(xì)胞是否已超過相應(yīng)遷移閾值。當(dāng)壽命超過其遷移閾值的細(xì)胞,需要使用results函數(shù)為其事件緩沖區(qū)中的每個事件生成中間異常分?jǐn)?shù)。

results(p)=

{(e,score(c)|c∈p,dead(c),e∈events(c))}

(22)

3)達(dá)到遷移閾值的細(xì)胞內(nèi)異常分?jǐn)?shù)值計算完成后,使用migrate重置這些細(xì)胞以生成新的一代:

migrate(cs)=

{if dead(c) then reset(c) elsec|c∈cs}

(23)

migrate遍歷群體中所有細(xì)胞,并用dead測試是否超過其遷移閾值。 如果dead為true,則通過reset重置細(xì)胞,清除細(xì)胞的事件緩沖區(qū)并將其決策信號設(shè)置為0,遷移閾值保持不變。

2.5 抗原背景環(huán)境評估與分類

在經(jīng)過n次迭代之后,停止處理輸入并返回映射到異常分?jǐn)?shù)的一組事件的元素。該集合被傳遞給analyze函數(shù)。此時,對于同一事件類型,可能會有多個臨時異常分?jǐn)?shù),在analyze中計算每種事件類型的平均異常分?jǐn)?shù):

(24)

3 實驗與分析

3.1 實驗設(shè)計

3.1.1 數(shù)據(jù)集選擇

本文提出ndhDCA的目的是在信號提取階段能夠脫離人工經(jīng)驗,自適應(yīng)地提取DS和SS信號,同時保證分類的準(zhǔn)確性。為展示ndhDCA的有效性及其性能,測試本文模型的性能,將使用ndhDCA、DCA、dDCA/hDCA分別在兩個數(shù)據(jù)集進(jìn)行對比實驗。

實驗在兩個數(shù)據(jù)集上進(jìn)行:

1)the UCI Wisconsin Breast Cancer dataset(WBC),其由700個數(shù)據(jù)實例組成,每個數(shù)據(jù)項有10個特征。

2)KDD99數(shù)據(jù)集,其源自DAPRA 98 Lincoln Lab數(shù)據(jù)集,用于將數(shù)據(jù)挖掘技術(shù)應(yīng)用于入侵檢測領(lǐng)域,由約500萬個數(shù)據(jù)實例組成,每個數(shù)據(jù)實例具有42個特征。本文使用是其10%的子集,數(shù)據(jù)項從整個數(shù)據(jù)集中隨機(jī)按比例選擇。

在兩個數(shù)據(jù)集的數(shù)據(jù)項中,WBC數(shù)據(jù)集按種類排序,為有序數(shù)據(jù);KDD99數(shù)據(jù)集經(jīng)由多次隨機(jī)打亂,為無序數(shù)據(jù)。

3.1.2 參數(shù)說明

數(shù)據(jù)集中每個數(shù)據(jù)項被映射為抗原。在所有實驗中,DC總數(shù)均設(shè)置為100,每個循環(huán)中對10個DC采樣,以確保ndhDCA的自適應(yīng)性。在數(shù)字微分計算結(jié)果中,選取變化最大的4個信號形成DS,最小的一個信號為SS,其余所有特征參數(shù)設(shè)置按照文獻(xiàn)[1]設(shè)置,這些參數(shù)來自經(jīng)驗免疫學(xué)數(shù)據(jù)(同hDCA/dDCA)。對于DCA,在WBC和KDD99中設(shè)置的異常值分別為0.65和0.446。

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

為與原始DCA進(jìn)行對比,本文使用的編碼環(huán)境為 Python 3.6。實際上,本文給出的函數(shù)化表達(dá)方式更適合在Haskell的環(huán)境下進(jìn)行實驗。

3.2.1 評價指標(biāo)說明

本文實驗使用分類器模型常用指標(biāo)作為評價指標(biāo),使用的每個指標(biāo)的具體說明如表2所示。

表2 評價指標(biāo)說明

3.2.2 在有序數(shù)據(jù)集WBC上的實驗

有序數(shù)據(jù)集WBC上3種算法的對比實驗結(jié)果如表3和圖2所示。從實驗結(jié)果看,ndhDCA在陽性預(yù)測率、陰性預(yù)測率、特異度上都有更高的評價,召回率與dDCA相同,馬修斯相關(guān)系數(shù)、AUC高于其他兩種算法。漏報率也低于dDCA和DCA。從ROC曲線圖可以更明確地看出,本文提出的ndhDCA不僅能自適應(yīng)地提取危險信號和安全信號,其在有序數(shù)據(jù)集上,與 DCA、hDCA/dDCA相比,還具有更高的準(zhǔn)確率和更低的誤報率。

表3 WBC數(shù)據(jù)集上的實驗結(jié)果Table 3 Experimental results on the WBC dataset %

圖2 WBC數(shù)據(jù)集上的ROC圖Fig.2 ROC graph on the WBC dataset

3.2.3 在無序數(shù)據(jù)集KDD99上的實驗

無序數(shù)據(jù)集KDD99上3種算法的對比實驗結(jié)果如表4和圖3所示。在之前的DCA研究中,錯誤的分類常發(fā)生在過渡邊界。因此,當(dāng)環(huán)境連續(xù)多次變化時DCA會產(chǎn)生更多錯誤。ndhDCA每次運行對每個數(shù)據(jù)項進(jìn)行10次采樣,可以緩解數(shù)據(jù)項混亂帶來的影響。

實驗結(jié)果顯示,由于數(shù)據(jù)隨機(jī)亂序了多次,DCA的性能基本上等同于隨機(jī)分類器,對于dDCA和ndDCA,在陽性預(yù)測率、陰性預(yù)測率、特異度、馬修斯相關(guān)系數(shù)、準(zhǔn)確率上ndhDCA有更高的評價,但誤報率比dDCA高。圖3所示的ROC圖更清晰地反映了在無序數(shù)據(jù)集KDD99上,3種算法分類效果均不理想,但在數(shù)據(jù)項亂序的情況下,nhDCA相比較于其他兩種算法取得了更準(zhǔn)確的分類結(jié)果。

表4 KDD99數(shù)據(jù)集上的實驗結(jié)果Table 4 Experimental results on the KDD99 dataset %

圖3 KDD99數(shù)據(jù)集上的ROC圖Fig.3 ROC graphs on the KDD99 dataset

4 結(jié)束語

本文構(gòu)建了基于數(shù)字微分理論的函數(shù)化樹突狀細(xì)胞模型ndhDCA。在hDCA模型基礎(chǔ)上,利用數(shù)字微分可根據(jù)離散數(shù)值變化和變化趨勢感知危險的特性,以DC信號隨機(jī)動態(tài)地對抗原進(jìn)行采樣,通過分析數(shù)據(jù)變化及變化趨勢確定并自適應(yīng)提取DS和SS信號。實驗結(jié)果表明,相比通過人工經(jīng)驗設(shè)置,該模型的算法普適性更強(qiáng),并能減小輸入數(shù)據(jù)順序的敏感性。后續(xù)將評估本文模型在無序數(shù)據(jù)集上的分類效果,并進(jìn)一步提高其檢測性能。