基于扩展传染病模型和马尔可夫链的物联网可用度评估方法

叶晓彤，孙文飞, ，沈士根

（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 物联网节点状态转换模型，能确切地反映恶意程序传播环境下的物联网节点状态。分析得到的物联网节点处于各个状态的概率动力学方程反映了物联网节点各个状态之间的动态变化过程，进一步得到的马尔可夫矩阵为计算物联网节点可用度奠定了基础。最终得到的星形和簇形物联网可用度评估方法能为管理员合理部署正常工作节点数、路由数提供建议，从而提高星形和簇形物联网的可用度，对促进物联网的成功应用具有理论指导意义。