基于元胞自動機的無線網(wǎng)絡安全態(tài)勢模擬

陳劍鋒，龍 愷，李明桂

(1.保密通信重點實驗室，四川成都610041;2.中國電子科技集團公司第三十研究所，四川 成都610041)

0 引言

無線通信不受地理位置和空間限制，部署靈活，效率較高，近30年來一直是業(yè)界的研究和發(fā)展重點。無線網(wǎng)絡通過無線通信技術將各類網(wǎng)元連接在一起，使信息傳輸擺脫了實體介質的束縛，用戶可以通過移動通信網(wǎng)、廣播網(wǎng)、Wifi、Wimax等多種手段接入網(wǎng)絡，充分享受無線連接為生產(chǎn)、生活帶來的便利。但是，無線網(wǎng)絡天然的開放性特點也使得由病毒、木馬等帶來的安全問題較有線網(wǎng)絡更為嚴重:各類惡意程序可能通過無線網(wǎng)絡迅速傳播，對無線節(jié)點、計算設備構成巨大的安全威脅，關鍵節(jié)點的失效可能會使整個無線網(wǎng)絡癱瘓。

針對這類安全威脅，對惡意程序流行規(guī)律進行研究，建立風險的網(wǎng)絡傳播模型，形成無線安全態(tài)勢的整體認知，是提升無線網(wǎng)絡安全防御能力的關鍵因素。安全人員基于對態(tài)勢的全面判斷能夠選擇有效的響應措施，在最短時間內抑制威脅的擴散。元胞自動機［1］作為描述復雜動力系統(tǒng)的數(shù)學工具，已經(jīng)在生物、工業(yè)、經(jīng)濟等多個研究領域得到了廣泛應用，如利用元胞自動機作為Hash迭代函數(shù)［2］。由于無線網(wǎng)絡中病毒傳播過程的自相似性強、擴散較有規(guī)律，因而元胞自動機的特性使其能夠對此類安全態(tài)勢演化進行有效模擬。目前對病毒傳播模型的研究均對客體狀態(tài)及轉移關系進行了定義，主要文獻有ER復雜網(wǎng)絡上的SIR模型［3］，SF復雜網(wǎng)絡上的SIS模型［4］等。在元胞自動機與無線網(wǎng)絡的結合方面，目前僅用于對拓撲結構等特征進行仿真［5］，而未涉及到對安全性質、安全態(tài)勢進行驗證的層面。

1 元胞自動機

1.1 定義

元胞自動機(CA，Cellular Automaton)也稱為細胞自動機，起源于20世紀40年代，由“現(xiàn)代計算機之父”馮·諾依曼設計，是一類時間和空間都離散的動力系統(tǒng)。元胞自動機由規(guī)則網(wǎng)絡(Lattice Grid)及附于其上的元胞(Cell)構成。每一元胞的狀態(tài)均從同一集合中取值，遵循同樣的轉移規(guī)則，并在時刻變化時作同步更新。大量元胞在離散的時間片中，通過簡單的相互作用而構成動態(tài)系統(tǒng)的演化［6］。

元胞自動機在設計時參照了生物現(xiàn)象的自繁殖原理，因此其概念和特征與一般的動力學模型不同。它不是由嚴格定義的物理方程或函數(shù)確定，而是一類模型的統(tǒng)稱，這些模型由給定的規(guī)則構造，凡是滿足這些規(guī)則的模型都可以視為是元胞自動機模型。

元胞自動機具有時間、空間、狀態(tài)均離散的特征，即元胞只能取有限多個狀態(tài)，只能在給定的空間中分布，且狀態(tài)的變化需要等待時間點到來才可進行。這些性質導致其演化的規(guī)則在時間和空間上都具有局部性特征，元胞自動機的要素描述如下:

元胞:元胞是CA最基本的組成部分。元胞是不可拆分的變量，分布在離散的一維(線)、二維(面)或多維空間上;

狀態(tài):狀態(tài)是一個有限集，可以是整數(shù)集，也可以是包含特殊意義的枚舉集合;

元胞空間:元胞所分布的空間網(wǎng)格，一般都是有限的;

鄰居:鄰居是一個元胞的集合，由CA指定。由于CA演化規(guī)則的局部性特征，每一元胞狀態(tài)更新時只需要知道其鄰居元胞的狀態(tài)即可;

規(guī)則:根據(jù)中心元胞及鄰居的當前狀態(tài)確定下一時刻中心元胞狀態(tài)的動力學函數(shù);

時間:CA在時間維的變化是離散的，時間t是一個非負整數(shù)值，而且連續(xù)等間距。時間具有順序性，t與t+1時刻的CA狀態(tài)具有因果關系。

元胞自動機在定義了基本元素后可自動運行，元胞狀態(tài)隨著時間的推移將不斷變化，整體上呈現(xiàn)出有規(guī)律、或者雜亂的特征。元胞自動機分類的研究是元胞自動機的一個重要的研究課題和核心理論，Wolfram將所有元胞自動機的動力學行為歸納為四大類［7］:

1)平穩(wěn)型:自任何初始狀態(tài)開始，經(jīng)過一定時間運行后，元胞空間趨于一個平穩(wěn)的構形。

2)周期型:經(jīng)過一定時間運行后，元胞空間趨于一系列簡單的周期結構。

3)混沌型:自任何初始狀態(tài)開始，經(jīng)過一定時間運行后，元胞自動機整體表現(xiàn)出混沌的非周期行為，通常表現(xiàn)為分形分維特征。

4)復雜型:出現(xiàn)復雜的局部結構，或者混沌狀態(tài)，有時會傳播至其它區(qū)域中。

使用形式語言描述，CA可以定義為四元組CA=(Ld，S，N，f)，其中 CA 代表元胞自動機系統(tǒng)，Ld代表一個規(guī)則劃分的d維網(wǎng)絡空間(d為正整數(shù)，一般取1或2，代表一維或二維空間)，S為元胞狀態(tài)取值的離散有限集合，N代表單個元胞的鄰域內元胞狀態(tài)的組合(鄰域包括中心元胞及鄰居元胞):假設中心元胞的鄰居個數(shù)為 j，則 N=(S0，S1，…，Sj)。令St+1i這種表示方式代表元胞i在t+1時刻的狀態(tài)，則f是將St+1i映射為S上的一個轉換函數(shù)，又稱為局部規(guī)則或狀態(tài)轉換函數(shù)。元胞i在t+1時刻的狀態(tài)取值將取決于t時刻元胞i自身及所有鄰居的狀態(tài)組合，即

1.2 演化規(guī)則

元胞自動機算法是一種簡單、但描述能力強大的數(shù)學算法，在元胞自動機中各個相鄰元胞一般存在著交互作用關系，在系統(tǒng)運行開始以后每個元胞的狀態(tài)都是整個系統(tǒng)在一些規(guī)則作用下不斷進化的結果。只要不斷地重復應用這些規(guī)則，就可以用元胞自動機的演化進程來預測系統(tǒng)將來的發(fā)展情況，在系統(tǒng)停機后將演化結果重新代入現(xiàn)實語義中，即可得到研究者們所關注的程序結果。

CA的核心是狀態(tài)定義及規(guī)則描述，在狀態(tài)基本固定的前提下，對規(guī)則的微小修改都可能導致最終結果的顯著變化，因此規(guī)則制訂必須嚴謹、能夠切實反映現(xiàn)實系統(tǒng)的運行狀態(tài)。CA中的每一個元胞在下一時刻的狀態(tài)完全由自身及鄰居當前的狀態(tài)決定，因而鄰居的范圍決定了規(guī)則的定義域。根據(jù)元胞自動機網(wǎng)絡的維數(shù)不同、半徑選取不同，鄰域的范圍也有所不同。圖1所示分別為一維、二維元胞自動機中以中心元胞為基準的鄰域元胞示意圖，圖中r表示鄰域半徑。

圖1 中心元胞鄰居定義Fig.1 Definition of central cell neighbor

在CA的一次演化過程中，所有元胞都會逐一被作為中心元胞參與運算，根據(jù)運算的結果執(zhí)行下一步的狀態(tài)轉移。這種狀態(tài)轉移是全局同步進行的，即各個元胞的狀態(tài)變化沒有先后順序，在時間推進到t+1的瞬間，所有的元胞都將轉移至新的狀態(tài)，這也是經(jīng)典CA的狀態(tài)轉移方式。中心元胞這種轉移的確定性使對于相同的起始狀態(tài)而言，該CA的每次運行結果都是一樣的，不能將隨機性這類反映現(xiàn)實系統(tǒng)運行的因素在模型中體現(xiàn)。

為了進一步增強CA的適用性從而能描述更復雜的動力系統(tǒng)，研究者們引入了概率CA，在這類CA中元胞下一時刻的狀態(tài)不僅依賴鄰域元胞，還取決于一個概率p，演化規(guī)則將根據(jù)p的取值進行分支，從而使元胞在下一時間進入一個服從概率分布、不可預知的狀態(tài)。即:

其中，0≤p≤1，P1，P2，…，Pn均為［0，1］上的區(qū)間，∪Pi=［0，1］且對于不同的 i，j都有 Pi∩Pj= ?。即p必定會落入轉換函數(shù)f的一個子項中，中心元胞的下一狀態(tài)將由此子項計算并唯一確定。另外，CA所在網(wǎng)絡空間通常是有限的，因此狀態(tài)轉移函數(shù)在處理邊界元胞時會出現(xiàn)輸入取值不足的情形，一般CA在建立時就指定了邊界問題的處理方式，這里將缺失的元胞狀態(tài)都視為缺省狀態(tài)。

2 無線網(wǎng)絡安全態(tài)勢模型

2.1 構建目標

這里研究的對象無線網(wǎng)絡是由大量分布在不同位置上的主機(或智能設備、傳感器)通過無線方式彼此連接構成的自組織網(wǎng)絡，節(jié)點間通過訪問點間接連接，或直接以點對點方式相連。相對于固定網(wǎng)絡，這類無線網(wǎng)絡(包括無線傳感器網(wǎng)絡WSN，或自治無線網(wǎng)絡)具有地理位置分散、信息交互需要經(jīng)過多跳、以自動管理為主、人工干預較少的特點。為方便研究，這里略去各計算單元在結構與功能上的差異，將它們作為彼此相同的元胞，將目標無線網(wǎng)絡映射至平坦的二維網(wǎng)格中，網(wǎng)格中每一小格代表元胞。構建的CA使用Von Neumann型鄰居定義，取r=1，即只有直接相鄰的兩個節(jié)點才被認為具有連接關系。

元胞的狀態(tài)集{Su，Id，In，De，Sr}為各節(jié)點相對于某一網(wǎng)絡威脅(病毒、木馬等)的安全狀態(tài)，元胞在某一時刻只能處于這五種狀態(tài)中的一種，狀態(tài)空間定義如下:

Su(Susceptive):節(jié)點尚未被威脅感染，但易受感染;

In(Infected):節(jié)點已被感染，但系統(tǒng)尚能執(zhí)行操作，處于該狀態(tài)的節(jié)點會傳染鄰居節(jié)點;

Im(Immune):節(jié)點對威脅處于免疫狀態(tài)，不會被感染。此類節(jié)點有一定幾率升級為Sr節(jié)點;

Id(Idle):節(jié)點被感染，且系統(tǒng)無法執(zhí)行任何操作，可視為當機。當機的節(jié)點會以很小機率由管理者重啟而恢復為In狀態(tài);

Sr(Serve):安全服務類節(jié)點，對威脅免疫，且能為已感染的鄰居節(jié)點清除威脅。

狀態(tài)間的轉換關系如圖2所示。稱某時刻網(wǎng)絡中元胞狀態(tài)的分布為一個格局，代表無線網(wǎng)絡在某時刻的安全態(tài)勢。隨著時間的推移，格局也在不斷演變，直至滿足預先設置的停機條件使自動機終止運行。威脅出現(xiàn)前大部分元胞的默認狀態(tài)為Su態(tài)，威脅的出現(xiàn)會使少數(shù)節(jié)點進入In態(tài)，而后安全專家設計、部署了防御工具將一些節(jié)點轉入Sr態(tài)。在格局變化的過程中In節(jié)點會感染附近的正常節(jié)點，而Sr節(jié)點會治愈附近的感染節(jié)點，格局的變化直接反映了無線網(wǎng)絡當前的安全態(tài)勢。

圖2 CA狀態(tài)間的轉換關系Fig.2 Transition relation between CA states

2.2 演化規(guī)則

令感染率ri表示狀態(tài)為Su的元胞受附近一個In態(tài)元胞影響，下一時刻被感染的概率;治愈率rh表示狀態(tài)為In的元胞受附近一個Sr態(tài)元胞影響，下一時刻被治愈的概率;致死率rd表示狀態(tài)為In的元胞下一時刻進入當機狀態(tài)的概率;轉變率rs為狀態(tài)為Im的節(jié)點轉變?yōu)榫哂星宄芰?jié)點態(tài)Sr的概率;重啟率re為一個當機節(jié)點進行重新啟動并進入In節(jié)點的概率。為表述方便，計算中心元胞鄰居中In態(tài)元胞數(shù)量為a，Sr態(tài)元胞數(shù)量為b，則CA元胞狀態(tài)演化規(guī)則矩陣如表1所示，表中首行為前一時刻的狀態(tài)，首列為后一時刻的狀態(tài)，狀態(tài)交叉處的取值為狀態(tài)間轉移的概率。

表1 元胞狀態(tài)演化規(guī)則Table 1 Evolution rules between CA states

在CA定義時，需要仔細選擇ri、rh等參數(shù)的取值，確保表中概率不會落在合規(guī)區(qū)間之外。

2.3 屬性斷言

給定了起始格局和演化規(guī)則，元胞自動機就可以一直運行下去。然而，受概率事件的影響，每一次格局的變化都不會完全相同，而僅僅是遵循一定的內在規(guī)律。為了捕捉這類規(guī)律，可以用屬性斷言來建立對格局特點的描述，在CA運行中通過斷言的證實或證偽來確定與規(guī)律的符合度。

屬性斷言按對象的范圍分為全局屬性斷言、局部屬性斷言等。一項屬性斷言代表一條待驗證的性質，按性質是否在給定格局里成立，屬性斷言的取值為true或false。例如，在時刻t對應的某一格局c中，全局屬性斷言“當機節(jié)點的個數(shù)占總節(jié)點的20%以上”可以描述為P1=Eval(Countt=tcc({Id})＞20%)，其中Eval算子檢驗屬性表達式的值，其返回值為真或假;Count算子統(tǒng)計格局中某一狀態(tài)元胞的數(shù)量。這條屬性斷言反映了系統(tǒng)的整體安全狀態(tài)。

局部屬性斷言僅關心少部分元胞的狀態(tài)，如“指定節(jié)點x在30個時間周期后處于免疫狀態(tài)”可以描述為 P2=Eval(Nextt=30x∈{Im，Sr})，Next算子表示返回元胞在給定時間間隔后的狀態(tài)。該屬性斷言可以用來表達對于關鍵節(jié)點狀態(tài)的驗證目標。

在同一初始格局的多次試驗中，屬性斷言的總體滿足情況無法用單一true或false表示，而是呈現(xiàn)出一種傾向性。約定如果總計進行m次試驗，滿足屬性的格局出現(xiàn)了n次，則屬性斷言的滿足率為100%×n/m，隨著試驗進行的次數(shù)增多，該值通常都會收斂至一定范圍內。

3 基于CA的態(tài)勢模擬

3.1 起始條件

為模擬現(xiàn)實中無線網(wǎng)絡安全態(tài)勢的演變情況，這里設計三類格局場景，即威脅入侵場景，威脅抑制場景和安全對峙場景。

如圖3所示，威脅入侵場景主要用于模擬威脅的蔓延，起初惡意代碼只在網(wǎng)絡的幾個分散節(jié)點出現(xiàn)，隨后逐漸隨時間而擴散;威脅抑制場景模擬大量免疫節(jié)點對少部分感染節(jié)點的威脅清除過程;安全對峙場景模擬在威脅爆發(fā)一段時間后，安全節(jié)點與受感染節(jié)點之間的對峙情況，期望得到最終元胞狀態(tài)的分布。

如圖3所示，在一個32×32元胞的網(wǎng)格上對上述場景進行模擬試驗，在時間流逝到指定條件時終止，各場景期望驗證的屬性如下:

威脅入侵場景:初始分布如圖3(a)所示，經(jīng)過30個時間單位以后，計算網(wǎng)絡內感染節(jié)點是否超過40%;

威脅抑制場景:初始分布如圖3(b)所示，經(jīng)過40個時間單位以后，計算網(wǎng)絡內受感染節(jié)點數(shù)量是否少于20;

安全對峙場景:初始分布如圖3(c)所示，經(jīng)過30個時間單位以后，計算當機或受感染節(jié)點數(shù)量少于已免疫節(jié)點;

同時，對各變化率進行量化賦值，取ri=rh=0.

3.2 算法實現(xiàn)

在CA 中進行屬性驗證一般使用重復迭代的方法，每一次迭代意味著時間推移了一個單位。算法持續(xù)運行，在終止條件達到后計算屬性的滿足情況，并給出最終結果。基于這種思想，算法實現(xiàn)的偽代碼如下:

圖3 不同態(tài)勢模擬場景的初始分布Fig.3 Initial distribution for different types of simulation scenario

3.3 實驗結果分析

取試驗次數(shù)n=20，在一臺配置為i3 CPU，內存為4096MB的計算機上運行自制的VS 2010 C#元胞自動機模擬程序，將試驗結果疊加至同一坐標系，得到試驗結果如圖4、圖5和圖6所示，模擬試驗結果的橫軸為迭代次數(shù)，縱軸為處于不同狀態(tài)的節(jié)點數(shù)量，“○”指代當機或受感染節(jié)點數(shù)量，“×”指代已免疫節(jié)點數(shù)量。

圖4 威脅入侵場景模擬試驗結果Fig.4 Result of threat intrusion situation simulation

將試驗結果對照屬性斷言可以認定:在威脅入侵場景圖4中，經(jīng)過30個時間單位以后網(wǎng)絡內感染節(jié)點超過40%的幾率為0.48;在威脅抵制場景圖5中，網(wǎng)絡內受感染節(jié)點數(shù)量在上升至極大值后隨之降低，經(jīng)過40個時間單位以后網(wǎng)絡內受感染節(jié)點數(shù)量少于20的幾率為0.45;在安全對峙場景圖6中，免疫節(jié)點與受感染節(jié)點數(shù)量均呈上升趨勢，但免疫節(jié)點增加速度更快。經(jīng)過30個時間單位以后當機或受感染節(jié)點數(shù)量少于已免疫節(jié)點的幾率為0.68。

圖5 威脅抑制場景模擬試驗結果Fig.5 Result of threat suppression situation simulation

圖6 安全對峙場景模擬試驗結果Fig.6 Result of security confrontation situation simulation

4 結語

無線網(wǎng)絡在提供部署靈活、使用方便等優(yōu)點的同時也延續(xù)了有線網(wǎng)絡固有的安全問題，病毒等惡意程序將會為無線網(wǎng)元帶來較嚴重的安全威脅。元胞自動機作為一類具有嚴格理論基礎的數(shù)學模型，能夠對無線網(wǎng)絡信息傳播過程進行模擬，進而應用于無線網(wǎng)絡安全態(tài)勢展現(xiàn)和評估環(huán)節(jié)中。文中建立了無線網(wǎng)絡的概率元胞自動機模型，給出了系統(tǒng)內威脅蔓延、治愈恢復等行為的形式化描述。基于預定義的屬性斷言，通過模型運行得到的驗證結果可為無線網(wǎng)絡安全態(tài)勢分析及事件響應提供有效的決策支撐。

［1］ HALPERN P.A Guide to Structurally Dynamic Cellular Automata［J］.Am.J.Phys，2003，57(05):28 －39.

［2］ 張傳武.基于細胞自動機的Hash函數(shù)方法［J］.通信技術，2010，43(12):123 －125.ZHANG Chuan － wu.Hash Function based on Cellular Automata.Communications Technology［J］.2010，43(12):123－125.

［3］ 于鑫，段曉東，劉向東，等.基于元胞自動機的流行病傳播模型及模擬［J］.計算機工程與應用，2005(02):205－209.YU Xin，DUAN Xiao － dong，LIU Xiang － dong，et al.Cellular Automata Model to Simulate the Infectof the Epidemic Diseases［J］.Computer Engineering and Applications.2005(02):205 － 209.

［4］ BARABáSIA L，ALBERTR.Emergence of Scaling in Random Networks［J］.Science，1999，286(5439):509 －512.

［5］ Stavros Athanassopoulos，Christos Kaklamanis，Gerasimos Kalfountzos，et al.Cellular Automata for Topology Control in Wireless Sensor Networks［C］//Electrotechnical Conference(MELECON)，2012 16th IEEE Mediterranean.Berlin，Germany:IEEE，2012:212 －215.

［6］ CULIK K，HURD LP.Formal Languagesand Global Cellular Automaton Behavior［J］.Physical D，1990(45):396 －403.

［7］ WOLFRAM S.Cellular Automata as Models of Complexity［J］.Nature，1984，311(06):419 －424.

［8］ SONG Yu － rong，JIANG Guo－ Ping.Modeling Malware Propagation in Wireless Networks using Cellular Automata［C］//Neural Networks and Signal Processing，2008 International Conference.Piscataway，NJ:IEEE，2008:623 －627.