基于數字微分的函數化樹突狀細胞算法模型

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

(武漢大學 計算機學院,武漢 430072)

0 概述

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

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

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

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

1 相關知識

1.1 數字微分

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

文獻[22]利用數字微分從應用環境的信號中自適應地提取危險信號,建立基于變化的自適應危險信號提取模型。文獻[23]將數字微分用于入侵檢測的數據預處理過程,提高了入侵檢測的準確率。文獻[24]將數字微分結合樹突狀細胞算法用于故障檢測,在提高檢測率的同時實現較早檢測到漸變性故障的目標。

1.2 DCA發展及hDCA介紹

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

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

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

1.3 問題描述

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

2 ndhDCA模型

2.1 模型框架

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

圖1 ndhDCA模型架構

數據采集模塊通過從實際應用環境(或已有的數據集)中獲得的所有特征建立原始抗原庫,再從其中構建候選抗原庫和候選信號庫,以便后續處理和評估抗原。

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

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

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

函數式描述模塊對上述過程分別進行函數化描述,這也是模型最重要的部分。

2.2 基礎理論

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

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

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

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

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

2.3 數字微分信號提取

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

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

(1)

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

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

(2)

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

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

假設指標與時間之間的映射關系為fmi(ti),指標mi左右側可描述為:

(3)

(4)

指標mi的變化趨勢可描述為:

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

(5)

上述過程可通過數字微分實現,將其稱為numeric,表示為:

numeric:mi×T→Δmi

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

(6)

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

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

(7)

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

adds0:mi→si

(8)

2.4 信號融合

2.4.1 輸入

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

A=Stream(E×T)

(9)

S=Stream(T×s0×s1)

(10)

2.4.2 樹突狀細胞

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

(11)

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

(12)

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

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

(13)

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

dead:Cell→B

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

(14)

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

reset:Cell→Cell

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

(15)

當細胞達到遷移閾值時,計算細胞的臨時異常分數,然后將其分配給細胞事件緩沖區的每個事件。有以下2種度量方法:

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

(16)

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

(17)

2.4.3 信號融合

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

1)用信號流中當前元素獲得的信號值,迭代更新細胞總群中所有細胞的決策信號,此過程稱為updateS,其中,N表示細胞總群,p表示當前的一個細胞:

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

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

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

(18)

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

表1 信號融合權重Table 1 Fused weights of signals

由表1中的權重得出決策信號計算公式:

ωA=s0+(-2.0)×s1

ωI=s1

ωM=s0+s1

(19)

由此,transduction的函數表達式可定義為:

transduction(s0,s1)=

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

(20)

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

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

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

(21)

2)更新決策信號導致每個細胞的遷移值增加,即ωM增加。因此,需要檢查細胞是否已超過相應遷移閾值。當壽命超過其遷移閾值的細胞,需要使用results函數為其事件緩沖區中的每個事件生成中間異常分數。

results(p)=

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

(22)

3)達到遷移閾值的細胞內異常分數值計算完成后,使用migrate重置這些細胞以生成新的一代:

migrate(cs)=

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

(23)

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

2.5 抗原背景環境評估與分類

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

(24)

3 實驗與分析

3.1 實驗設計

3.1.1 數據集選擇

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

實驗在兩個數據集上進行:

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

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

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

3.1.2 參數說明

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

3.2 實驗結果與分析

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

3.2.1 評價指標說明

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

表2 評價指標說明

3.2.2 在有序數據集WBC上的實驗

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

表3 WBC數據集上的實驗結果Table 3 Experimental results on the WBC dataset %

圖2 WBC數據集上的ROC圖Fig.2 ROC graph on the WBC dataset

3.2.3 在無序數據集KDD99上的實驗

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

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

表4 KDD99數據集上的實驗結果Table 4 Experimental results on the KDD99 dataset %

圖3 KDD99數據集上的ROC圖Fig.3 ROC graphs on the KDD99 dataset

4 結束語

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