基于擴展傳染病模型和馬爾可夫鏈的物聯網可用度評估方法

葉曉彤，孫文飛, ，沈士根

（1. 紹興文理學院計算機科學與工程系，浙江 紹興 312000；2. 浙江理工大學信息學院，浙江 杭州 310018）

1 引言

物聯網與人們的生活息息相關，其安全問題是影響物聯網應用的關鍵因素，而惡意程序傳播[1-6]是影響物聯網性能的諸多原因之一。當惡意程序感染物聯網節點后，將通過物聯網節點之間的通信傳播到其他物聯網節點，導致物聯網節點數據丟失、通信阻斷以及能量損耗等問題，甚至直接使整個物聯網系統發生癱瘓。物聯網可用度評估反映的是物聯網在感知數據、數據通信、數據匯聚時該網絡處于可用或可操作狀態的概率，是反映物聯網性能的重要指標之一。在惡意程序傳播環境下，如何評估物聯網可用度已成為物聯網能否成功應用的關鍵問題。因此，面向惡意程序傳播的物聯網可用度評估得到了學術界和工業界的廣泛重視。

當前，與網絡可用度（availability）評估相關的有可靠度（reliability）、可信賴度（2epen2ability）、可生存性（survivability）評估。鄒青丙等[7]綜述了無線多跳網絡中的可靠度評估方法，并結合物聯網展望可靠度評估發展趨勢。何明等[8]較早研究了物聯網可靠度評估問題，通過綜合考慮感知層網絡節點移動性和網絡故障因素，給出了一種物聯網中感知層網絡可靠度評估方法。沈士根等[9]基于靜態博弈預測惡意程序的傳播行為，再將惡意程序傳播的概率關聯到馬爾可夫鏈的隨機性，實現了無線傳感器網絡的可生存性評估。沈士根等還使用“非合作非零和博弈”[10]和隨機博弈[11]給出了無線傳感器網絡的可信賴度和可靠度評估方法，利用SIRD 傳染病模型和馬爾可夫鏈[12]給出了面向惡意程序傳播的異質無線傳感器網絡可用度評估方法。進一步地，金娟等[13]基于節點分布和脆弱性差異給出異質無線傳感器網絡節點異質模型，再進行節點可用度的分析。石瓊等[14]利用連續時間馬爾可夫鏈，考慮節點獨立失效與相關失效，針對無線傳感器網絡可靠度、可用度及可生存性分別給出了評估方法。另外，基于連續時間馬爾可夫鏈研究網絡可生存性評估問題的文獻還包括多種攻擊并發下的無線傳感器網絡可生存性評估模型[15]、考慮節點移動的無線傳感器網絡可生存性評估模型[16]。Liu 等[17]提供了一種區域失效概率模型，以捕捉區域失效的關鍵特征，并將其應用于無線Mesh 網絡的可靠度評估。Huang 等[18]利用隨機游走模型描述物聯網節點間關系，提出了一種基于隨機模型的物聯網節點可信賴度評估方法。Yue 等[19]針對工業無線傳感器網絡，給出了一種時間演化的Monte Carlo（蒙特卡洛）可靠度評估方法。Ferraz 等[20]針對IPv6 物聯網，使用多元統計方法識別異常感知信息，給出了一種物聯網可靠度評估模型。Huang 等[21]針對基于邊緣計算的物聯網環境，建立了表述物聯網設備、邊緣服務器和云服務器之間流量關系的網絡模型，并給出了評估網絡可靠度的算法。An2ra2e 等[22]提出了一種基于Petri 網的物聯網基礎設施災難恢復建模與分析方法，實現了物聯網基礎設施的可用度評估。Xiang 等[23]考慮無線傳感器網絡的隨機失效、能量消耗、環境隨機性和干擾等方面，基于代數圖論和Monte Carlo 仿真提出了廣義節點可靠度和平均廣義節點可靠度評估指標，用于實現無線傳感器網絡的可靠度評估。

然而，在物聯網惡意程序傳播環境中，除參考文獻[12-13]描述的易感狀態（S）、感染狀態（I）、免疫狀態（R）、死亡狀態（D）4 種狀態外，還普遍存在潛伏狀態（E）。該狀態表示物聯網節點被惡意程序感染后，隱藏自己并且不表現出傳播惡意程序的行為。因此，本文為更好地反映物聯網惡意程序傳播環境下物聯網節點的實際狀態，建立SEIRD 物聯網節點狀態轉換模型。然后，構建物聯網節點處于5 種狀態的概率動力學方程，得到各狀態轉換矩陣，進一步得到物聯網節點可用度計算方法。最后，以典型的星形和簇形物聯網拓撲結構為例，給出整個物聯網可用度評估的方法。

2 惡意程序傳播環境下的物聯網節點狀態轉換模型

在物聯網中，惡意程序通過被感染節點獲取節點數據，并進行相鄰節點的傳播，這跟傳染病的傳播模式類似。因此，可以考慮基于傳染病原理和馬爾可夫鏈來描述物聯網節點在惡意程序傳播環境下的節點狀態轉換模型。

在物聯網惡意程序傳播過程中，易感狀態（S）、潛伏狀態（E）、感染狀態（I）、免疫狀態（R）、死亡狀態（D）為物聯網節點常見的5 種狀態，而這5 種狀態的節點存在相互轉換關系，如圖1 所示。圖1 中，易感狀態的節點指的是物聯網系統內存在漏洞并有可能被感染的節點；潛伏狀態的節點指的是該物聯網節點已經被惡意程序感染但此時惡意程序未處于活動期，即此時該節點雖被感染但不會向外傳播惡意程序；感染狀態的節點指的是一個本來處于潛伏狀態的物聯網節點試圖向其他節點傳播惡意程序，此時處于潛伏狀態的節點中的惡意程序被激活，從而由潛伏狀態轉換成感染狀態；免疫狀態的節點指的是處于易感狀態、潛伏狀態或感染狀態的物聯網節點通過安裝系統安全補丁，從而達到類似于人體免疫力的效果，此時對已知的惡意程序可以起到抵抗的作用，從而保護節點不會被感染；死亡狀態的節點指的是處于易感狀態、潛伏狀態、感染狀態或免疫狀態的物聯網節點在惡意程序的代碼攻擊之下消耗殆盡節點內部的能量，從而導致該節點死亡的節點，也有可能是因為自身能量耗盡而死亡的節點。

3 惡意程序傳播環境下的物聯網節點狀態轉換動力學

對于任意一個物聯網節點i而言，記其度為k，即其周圍有k個與之相鄰且可以互相通信的節點。這k個與物聯網節點i相鄰的節點都有一定的可能性對節點i進行攻擊，從而使節點i由易感狀態S轉換到潛伏狀態E再進一步由潛伏狀態E轉換到感染狀態I，所以，在t時刻節點i的狀態與t? 1時刻該節點與其相鄰節點的狀態有密切關系。分別為節點i在t時刻處于易感狀態、潛伏狀態、感染狀態、免疫狀態和死亡狀態的概率，表示在t時刻節點由狀態x轉換到狀態y的概率，其中，x,y∈{S,E,I,R,D}。顯然，在一個剛建立的物聯網中，各節點會被默認安裝安全補丁對已知的惡意程序產生抵抗力，同時應對未來可能入侵的惡意程序，所以物聯網內各節點的初始狀態都處于免疫狀態，即

圖1 物聯網節點SEIRD 狀態轉換圖

部署于物聯網中的入侵檢測系統可以對節點進行安全檢測和安裝安全補丁，從而使節點獲得抵抗惡意程序的免疫力。當入侵檢測系統檢測到節點存在安全漏洞時，可以為節點安裝安全補丁，使該物聯網節點從易感狀態、潛伏狀態或感染狀態轉換成免疫狀態。記惡意程序感染節點的概率為α，物聯網入侵檢測系統的檢測率和誤報率分別為β和γ，一個節點由潛伏狀態轉換到感染狀態的概率為μ，被惡意程序殺死即進入死亡狀態的概率為ω，節點非惡意程序攻擊下死亡的概率為φ，單位時間內物聯網管理員向物聯網內部投放新的健康節點和清除死亡節點的概率均為η，由于物聯網節點存在漏洞導致其從免疫狀態轉換到易感狀態的概率為ζ，物聯網節點i的相鄰節點為j。

當物聯網節點i處于潛伏狀態時，無法轉換成易感狀態，但是該節點內的惡意程序處于活動狀態后將使該節點從潛伏狀態轉換為感染狀態。當該節點經物聯網入侵檢測系統檢測并安裝安全補丁后，該節點將從潛伏狀態變為免疫狀態。當該節點因為物理原因死亡時，就會從潛伏狀態轉換為死亡狀態。因此，在t時刻，處于潛伏狀態的節點i的狀態轉換概率如式（2）所示。

對處于感染狀態的物聯網節點i，當物聯網入侵檢測系統檢測到惡意程序所攻擊的安全漏洞時，通過安裝安全補丁來彌補這個安全漏洞，從而使節點i由感染狀態轉換為免疫狀態。也有可能在惡意程序的攻擊下或者受物理原因影響，節點i由感染狀態轉換為死亡狀態。另外，處于感染狀態的節點不能轉換為易感狀態和潛伏狀態。因此，在t時刻，處于感染狀態的節點i的狀態轉換概率如式（3）所示。

對處于免疫狀態的物聯網節點i，如果惡意程序發現了新的安全漏洞，則會使該節點又存在被攻擊的可能性，使其從免疫狀態轉換成易感狀態。而當物聯網入侵檢測系統誤報時，會將物聯網節點判斷為潛伏狀態。同時，節點i也存在非惡意程序攻擊下死亡的可能。因此，在t時刻，處于免疫狀態的節點i的狀態轉換概率如式（4）所示。

針對惡意程序傳播和節點正常死亡導致物聯網內部正常節點數量減少的問題，為了保障物聯網的性能狀態，一般采取向物聯網內加入健康節點的辦法。這種方法可以維持整個物聯網中正常節點數量穩定。在實際操作中，加入健康節點的概率跟死亡節點的概率相同，并且，新加入節點的初始狀態為免疫狀態。因此，在t時刻，處于死亡狀態的節點i的狀態轉換概率如式（5）所示。

結合圖1 可知，在t?1 時刻處于易感狀態的物聯網節點可以轉換為潛伏狀態、免疫狀態或死亡狀態；處于潛伏狀態的節點可以轉換為感染狀態、免疫狀態或死亡狀態；處于感染狀態的節點可以轉換為免疫狀態或死亡狀態；處于免疫狀態的節點可以轉換為易感狀態、潛伏狀態或死亡狀態；處于死亡狀態的節點可以轉換為免疫狀態（實質是新加入的健康節點）。因此，物聯網節點i在t時刻處于各個狀態的概率如式（6）所示。

將式（1）～式（5）代入式（6），化簡可得物聯網節點i在t時刻各個狀態轉換的動力學方程，如式（7）～式（11）所示。

4 惡意程序傳播環境下的物聯網可用度

根據可靠性理論，一個物聯網節點i在t時刻的可用度稱為瞬時可用度，而當t趨于無窮時的可用度稱為穩態可用度，該值能最終體現節點i和物聯網的性能狀況。記節點i在時刻t的瞬時可用度為τi(t)，穩態可用度為則該節點穩態可用度為：

在實際計算物聯網節點可用度時，通常經過計算表達物聯網節點狀態轉換的馬爾可夫矩陣的穩定點來得到具體值。記：

5 典型物聯網拓撲結構下的物聯網可用度評估

5.1 星形物聯網拓撲結構

星形物聯網拓撲結構以物聯網網關節點為中心，所有物聯網節點都與網關節點相連。當連接網關節點的物聯網節點需要發送數據時都要通過網關節點，再由網關節點統一向上一級基站發送數據。因此，星形物聯網拓撲結構中網關節點是網絡成功運行的關鍵，容錯率較低，所有物聯網節點單獨與網關節點進行通信。

在星形物聯網拓撲結構下，要使物聯網可以正常工作，除網關節點必須正常運行外，還需要正常工作的物聯網節點。記整個星形物聯網中節點數為Y，能正常工作的節點數為g，保證星形物聯網正常工作的最小節點數為X，則當g∈[X,Y]時，該星形物聯網可以正常運行。因此，整個星形物聯網的可用度τstar為：

5.2 簇形物聯網拓撲結構

簇形物聯網拓撲結構較星形物聯網增加了簇頭節點，每個簇頭節點與同一個簇中的物聯網節點相連并且直接跟網關節點相連。當簇頭節點出現故障時，通過簇頭選舉算法將選擇同一個簇內其他物聯網節點作為新的簇頭。因此，每一個簇內的物聯網節點與對應的簇頭進行通信，屬于并行系統，簇頭節點跟網關節點的通信路由屬于串行系統，所有的通信路由進一步組成了并行系統。

記一個簇中的物聯網節點數為YB，整個簇的可用度可以表示為：

記W為整個簇形物聯網中所有路由的條數，則整個簇形物聯網可用度

6 實驗仿真與結果分析

6.1 物聯網入侵檢測系統檢測率和誤報率對物聯網節點可用度的影響

物聯網入侵檢測系統的檢測率β和誤報率γ的變化會影響物聯網節點可用度，為了分析其影響程度，根據物聯網入侵檢測系統的實際檢測率和誤報率變化情況，實驗設置檢測率β變化的范圍為80%～ 98%，誤報率γ變化的范圍為2%～ 20%。實驗結果如圖2 所示。

圖2 物聯網入侵檢測系統檢測率和誤報率變化下的物聯網節點可用度

從圖2 可以看出，在誤報率相同的情況下，物聯網節點可用度隨著檢測率的增大而增大。例如，當誤報率γ=10%時，隨著檢測率從80%提高到98%，物聯網節點可用度從約34.56%提升到約41.18%。而在檢測率相同的情況下，物聯網節點可用度隨著誤報率的減小而增大。例如，當檢測率β=90%時，隨著誤報率從20%降低到2%，物聯網節點可用度從約34.44% 提升到約41.28%。實驗結果反映了在實際物聯網應用中，為了提高物聯網節點可用度，應盡量提高物聯網入侵檢測系統的檢測率并且降低其誤報率。

6.2 星形物聯網可用度實驗分析

由式（26）可知，星形物聯網可用度主要與總的節點數和正常工作的節點數密切相關，因此，實驗在設定物聯網入侵檢測系統檢測率和誤報率不變的情況下，分析物聯網總節點數和正常工作節點數變化對整個星形物聯網可用度的影響。實驗結果如圖3 所示。

圖3 物聯網總節點數和正常工作節點數變化下的星形物聯網可用度

從圖3 可以看出，在物聯網總節點數不變的情況下，增加正常工作節點數能顯著提升星形物聯網可用度。例如，當物聯網總節點數Y=25 時，若正常工作節點數小于10，星形物聯網可用度低于10%，基本處于不可用狀態；若正常工作節點數從10 逐步增加到20，星形物聯網可用度從約10%快速增加到約100%。而在物聯網正常工作節點數不變的情況下，增加物聯網總節點數將降低整個星形物聯網的可用度。例如，當物聯網正常工作節點數g=15 時，若物聯網總節點數Y分別為20、25、30，則整個星形物聯網的可用度分別約為97.40%、71.39%、30.19%。實驗結果反映了在星形物聯網中，保證合理的正常工作節點數是提高星形物聯網可用度的關鍵，同時反映了提出的星形物聯網可用度評估方法能給出合理的正常工作節點數建議，從而為提高星形物聯網可用度提供理論指導。

6.3 簇形物聯網可用度實驗分析

由式（29）可知，簇形物聯網可用度主要與路由數和簇中物聯網節點數密切相關，因此，實驗在設定物聯網入侵檢測系統檢測率和誤報率不變的情況下，分析路由數和簇中物聯網節點數變化對整個簇形物聯網可用度的影響。實驗結果如圖4 所示。

圖4 路由數和簇中物聯網節點數變化下的簇形物聯網可用度

從圖4 可以看出，在簇形物聯網中，改變簇中物聯網節點個數對整個簇形物聯網可用度影響有限，而改變物聯網中路由數對整個簇形物聯網可用度影響巨大。例如，當簇中物聯網節點個數YB= 10時，若物聯網中路由數從1 增加到5，則簇形物聯網可用度從約40.02% 增加到約92.23%；若物聯網中路由數繼續從5 增加到10，則簇形物聯網可用度從約92.23%增加到100%。實驗結果反映了在簇形物聯網中，保證合理的路由數是提高簇形物聯網可用度的關鍵，同時反映了提出的簇形物聯網可用度評估方法能給出合理的路由數建議，從而為提高簇形物聯網可用度提供理論指導。

7 結束語

本文通過擴展傳統的傳染病模型，基于能表達物聯網節點狀態轉換的馬爾可夫鏈，提出了一種惡意程序傳播環境下的物聯網可用度評估方法。經過擴展后得到的SEIRD 物聯網節點狀態轉換模型，能確切地反映惡意程序傳播環境下的物聯網節點狀態。分析得到的物聯網節點處于各個狀態的概率動力學方程反映了物聯網節點各個狀態之間的動態變化過程，進一步得到的馬爾可夫矩陣為計算物聯網節點可用度奠定了基礎。最終得到的星形和簇形物聯網可用度評估方法能為管理員合理部署正常工作節點數、路由數提供建議，從而提高星形和簇形物聯網的可用度，對促進物聯網的成功應用具有理論指導意義。