基于元胞自動機的無線網絡安全態勢模擬

陳劍鋒，龍 愷，李明桂

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

0 引言

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

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

1 元胞自動機

1.1 定義

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

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

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

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

狀態:狀態是一個有限集，可以是整數集，也可以是包含特殊意義的枚舉集合;

元胞空間:元胞所分布的空間網格，一般都是有限的;

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

規則:根據中心元胞及鄰居的當前狀態確定下一時刻中心元胞狀態的動力學函數;

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

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

1)平穩型:自任何初始狀態開始，經過一定時間運行后，元胞空間趨于一個平穩的構形。

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

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

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

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

1.2 演化規則

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

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

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

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

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

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

2 無線網絡安全態勢模型

2.1 構建目標

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

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

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

In(Infected):節點已被感染，但系統尚能執行操作，處于該狀態的節點會傳染鄰居節點;

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

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

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

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

圖2 CA狀態間的轉換關系Fig.2 Transition relation between CA states

2.2 演化規則

令感染率ri表示狀態為Su的元胞受附近一個In態元胞影響，下一時刻被感染的概率;治愈率rh表示狀態為In的元胞受附近一個Sr態元胞影響，下一時刻被治愈的概率;致死率rd表示狀態為In的元胞下一時刻進入當機狀態的概率;轉變率rs為狀態為Im的節點轉變為具有清除能力節點態Sr的概率;重啟率re為一個當機節點進行重新啟動并進入In節點的概率。為表述方便，計算中心元胞鄰居中In態元胞數量為a，Sr態元胞數量為b，則CA元胞狀態演化規則矩陣如表1所示，表中首行為前一時刻的狀態，首列為后一時刻的狀態，狀態交叉處的取值為狀態間轉移的概率。

表1 元胞狀態演化規則Table 1 Evolution rules between CA states

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

2.3 屬性斷言

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

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

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

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

3 基于CA的態勢模擬

3.1 起始條件

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

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

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

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

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

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

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

3.2 算法實現

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

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

3.3 實驗結果分析

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

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

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

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

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

4 結語

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

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

［2］ 張傳武.基于細胞自動機的Hash函數方法［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.