沈士根,黄龙军,周海平,范 恩,李宏杰,曹奇英

(1.绍兴文理学院计算机科学与工程系,浙江 绍兴 312000;2.嘉兴学院数理与信息工程学院,浙江 嘉兴 314001;3.东华大学计算机科学与技术学院,上海 201620)



面向恶意程序传播的异质WSNs稳态可用度评估*

沈士根1*,黄龙军1,周海平1,范 恩1,李宏杰2,曹奇英3

(1.绍兴文理学院计算机科学与工程系,浙江 绍兴 312000;2.嘉兴学院数理与信息工程学院,浙江 嘉兴 314001;3.东华大学计算机科学与技术学院,上海 201620)

为预测异质传感网(HWSNs)的可用性能,提出一种面向恶意程序传播的HWSNs稳态可用度评估方法。在考虑异质传感节点实际状态基础上,增加状态D(死亡)扩展经典SIR传染病模型得到SIRD模型以描述节点因能量耗尽、物理损坏或恶意程序攻击导致功能丧失的情况。使用Markov链描述节点各状态之间的动态转换过程,分析得到状态转换矩阵和各状态变化的动力学方程。推理得到一个异质传感节点的稳态可用度计算公式,再依次推理得到星形和簇形HWSNs稳态可用度计算公式。实验分析了IDS检测率和误报率对异质传感节点稳态可用度的影响,验证了所提出方法的有效性。

异质传感网;稳态可用度评估;恶意程序;传染病模型;Markov链

物联网在智慧城市、智慧交通、智慧健康、智慧安防等应用领域用途广泛,已成为我国五大新兴战略性产业之一。在具体构建时,其底层网络通常使用传感网实现[1]。由于物联网普遍具有多元与异构的特性,所以包含异质传感节点的异质传感网HWSNs(Heterogeneous Wireless Sensor Networks)已成为必然需求,它比同质传感网更有实际应用价值。

HWSNs可用度表示HWSNs在感知数据、数据通信、数据汇聚时该网络处于可用或可操作状态的概率,是反映HWSNs性能的重要指标之一。在实际计算时,常用稳态可用度表示,代表了网络在长期或较长期运行的情况下网络处于可用或可操作状态的概率。但是,要评估HWSNs的稳态可用度并非易事。从传感节点的角度来看,HWSNs的异质性体现在能量、计算、通信、存储、安全和基础协议等方面;从外部环境看,这种异质性体现在链路、空间地理位置和恶意程序攻击等方面。甚至有时需要人为引入异质,如通过引入少量高性能节点,可以显著提高整个传感网的数据处理和传输速率,减少其他传感节点的能耗及节点对节点的传输延迟。面对HWSNs具有的节点异质性、链路异质性、拓扑结构异质性等特点,如何评估HWSNs的可用度已成为HWSNs能否成功应用的关键问题。

恶意程序已成为威胁HWSNs安全的主要因素。它们一旦利用节点的软硬件漏洞在HWSNs中大范围传播后,就能窃听、破坏节点感知的数据,甚至阻塞通信信道、耗尽节点能量,使整个HWSNs处于瘫痪状态,从而严重影响整个HWSNs数据的机密性和整个网络的可用度。因此,迫切需要研究恶意程序在HWSNs中的传播行为,评估在恶意程序传播环境下HWSNs的可用度,以便采取措施增强HWSNs的可用度和抑制恶意程序的传播。

国内外学者目前在传感网可用度评估相关领域已经提出了一些方法。Trivedi等人[2]从非状态空间模型、状态空间模型和层次模型三方面综述了随机模型在系统可用度评估中的应用。而Costa等人[3]综述了可视传感网中可用度评估问题。王文彬等人[4]提出了一种针对移动Ad hoc网络能感知环境的服务可用性评估模型,并结合层次分析法和多属性综合评估法实现量化评估。王海涛等人[5]和朱世才等人[6]分别采用网络分析法和半马尔可夫过程建立了适用于应急通信传感网的可生存性评估模型,实现了对协议SRPC和RLEACH的可生存性评估。刘文芬等人[7]基于Markov博弈提出了一种网络风险评估方法。沈士根等人[8]结合使用完全信息静态博弈、Markov链和可靠性理论,给出了一种在恶意程序传播环境下簇形传感网的可生存性评估方法。李阿妮等人[9]将虚拟机启动时间对应云计算系统的平均故障修复时间,提出了一种云计算系统可用度评估方法。张晓花和董荣胜[10]结合使用Markov链和有序二叉决策图提出了一种用于评估传感网可用度的离散概率模型,并给出了相应的算法。Silva等人[11]针对网络节点出现的永久性故障,提出了一种基于自动生成的故障树来评估传感网可用度的方法。Faghih-Roohi等人[12]面对不同状态组件失效概率变化的情况,提出了一种针对多状态加权K-out-of-N系统的动态可用度评估方法。Yue等人[13]利用Monte Carlo方法给出了针对工业传感网的可靠度评估模型。另外,其他适用于评估可用度的典型模型还包括层次模型[14]、Semi-Markov链[15]和模糊Markov链[16]等。但上述方法都未考虑受恶意程序传播的HWSNs环境,不能用于具有异质性特点的HWSNs可用度评估。

因为网络恶意程序传播与传染病传播相似,所以传染病模型常用于建立恶意程序传播的模型[8,17]。一般来说,传染病模型在使用时会给出节点在不同时刻所有可能的状态,如状态S(Susceptible,易感)、I(Infectious,传染)、R(Removed,恢复)等。然后结合不同状态得到不同的传染病模型,如经典的SI[18]、SIS[19]、SIR[20]等模型。

本文扩展经典传染病模型,基于Markov链提出一种面向恶意程序传播的HWSNs可用度评估方法。首先,考虑在恶意程序传播环境下一个异质传感节点可能存在的状态,通过增加状态D(Dead,死亡)来描述由于能量耗尽、物理损坏或恶意程序攻击使得节点功能丧失的情况,从而扩展经典SIR传染病模型得到SIRD模型;其次,通过Markov链描述各状态之间的动态转换过程,给出一个异质传感节点各状态之间的状态转换概率,得到各状态变化的动力学方程;最后,给出一个异质传感节点的稳态可用度计算公式,然后针对典型的星形和簇形HWSNs拓扑结构,分别给出计算整个星形和簇形HWSNs稳态可用度计算公式。

1 异质传感节点SIRD状态转换模型

借鉴传染病理论中经典SIR模型的思想,在恶意程序传播环境下的一个异质传感节点在其整个生命周期内可划分为不同的状态。当一个节点被恶意程序发现具有安全漏洞但尚未被传染恶意程序时,其归属于状态S;当一个节点被传染恶意程序且节点自身受恶意程序控制而传播恶意程序时,其归属于状态I;当一个节点受基站控制通过安装安全补丁以弥补安全漏洞或移除节点上的恶意程序并能抵抗现有恶意程序的传染时,其归属于状态R;当一个节点因能量耗尽、物理损坏或由于恶意程序攻击使得节点功能丧失时,其归属于状态D。基于上述实际情况中异质传感节点各状态的分析,本文引入状态D来扩展经典的传染病模型SIR,从而得到一个更能确切反映异质传感节点面对恶意程序传播时状态动态转换的新模型SIRD,如图1所示。

图1 异质传感节点SIRD状态转换模型

显然,图1中各状态之间的转换只跟当前状态有关,因此可将异质传感节点状态之间的动态转换过程看作是一个Markov过程。假设HWSNs中各个异质传感节点被均匀地洒播在感知区域,其分布密度为λ。对于任意的一个异质传感节点i,记ri为其通信半径,Ni为其邻居节点数,则

(1)

(2)

(3)

(4)

综上分析可得

(5)

(6)

(7)

至此,用于描述异质传感节点i在时刻t各状态之间动态转换的Markov过程的状态转换矩阵Mi(t)可表示为

(8)

各状态变化的动力学方程可表示为

(9)

(10)

(11)

(12)

2 异质传感节点稳态可用度计算

即

(13)

在实际计算一个异质传感节点的稳态可用度时,常通过计算描述异质传感节点状态之间动态转换的Markov过程的稳定点来得到具体值。

(14)

得到的等式中的任意3个等式联合

(15)

(16)

(17)

(18)

和式(15)构成方程组,解得

(19)

(20)

(21)

(22)

(23)

3 HWSNs稳态可用度计算

3.1 星形HWSNs

(24)

图2 星形HWSNs拓扑结构

3.2 簇形HWSNs

如图3所示,一个簇形HWSNs通常包含若干簇头节点,每个簇头节点管理若干普通异质传感节点。这种结构适合中大规模HWSNs的部署,并采用如LEACH协议等的多跳路由协议。当一个普通异质传感节点感知到数据后,先发送到对应的簇头节点,然后该簇头节点对接收到的数据进行处理后发送到Sink节点,最后由Sink节点发送到基站。

图3 簇形HWSNs拓扑结构

(25)

(26)

(27)

式中:Z表示整个簇形HWSNs的路由数。

4 实验仿真与结果分析

由式(20)～式(23)可知,计算一个异质传感节点的稳态可用度涉及多个参数,其中β和γ作为IDS的检测率和误报率,属于可变参数,而其他参数值一旦确定选用的传感节点和要部署的拓扑结构后将是固定的。因此,使用MATLAB R2010b,实验首先说明β和γ对一个异质传感节点稳态可用度的影响,然后分别从星形和簇形拓扑结构评估整个HWSNs的稳态可用度。根据传感网IDS的实际情况,实验设定β和γ参数的变化范围分别为80%～98%和2%～19%。

4.1 IDS检测率和误报率对异质传感节点稳态可用度的影响

如图4所示,提高IDS检测率或降低误报率都能提高异质传感节点的稳态可用度,这与实际事实相符。因为IDS检测率越高,异质传感节点上的恶意程序越容易被成功检测,从而使节点的状态转换到R。而IDS误报率越低,异质传感节点的状态从R转换到I的概率越低,也就是说,整个HWSNs中节点状态为R的比例越高。所以,IDS的检测率越高或误报率越低,都将使异质传感节点的稳态可用度越高。

图4 IDS检测率和误报率对异质传感节点稳态可用度的影响

图5 星形HWSNs的稳态可用度

4.2 评估星形HWSNs的稳态可用度

由式(24)可知,星形HWSNs的稳态可用度与HWSNs中异质传感节点总数和要求能正常工作的普通异质传感节点数密切相关,因此,通过实验来进一步说明它们之间的关系。图5给出了星形HWSNs的稳态可用度评估结果,其中,异质传感节点总数分别为20、25和30。从图5可以看出,星形HWSNs的稳态可用度随HWSNs中要求正常工作的普通异质传感节点数的增加而降低,但随HWSNs中异质传感节点总数的增加而升高。例如,当要求正常工作的普通异质传感节点数从10增加到15时,对于N=20、N=25和N=30等3种情况,星形HWSNs的稳态可用度分别从约0.588 1降低到约0.020 7、从约0.885 2降低到约0.212 2和从约0.978 6降低到约0.572 2。实验结果反映出构建星形HWSNs过程中若要求增加正常工作的普通异质传感节点数时,应适当增加冗余的异质传感节点数,以达到用户可接受的HWSNs稳态可用度。

4.3 评估簇形HWSNs的稳态可用度

由式(27)可知,簇形HWSNs的稳态可用度与簇中普通异质传感节点数和整个簇形HWSNs的路由数密切相关,因此,通过实验来进一步说明它们之间的关系。图6给出了簇形HWSNs的稳态可用度评估结果,其中,簇中普通异质传感节点数和整个簇形HWSNs的路由数都从2变化到6。从图6可以看出,簇形HWSNs的稳态可用度随簇中普通异质传感节点数和整个簇形HWSNs的路由数的增加而升高,但具有不同的变化趋势。例如,当簇中普通异质传感节点数为4、整个簇形HWSNs的路由数从2变化到6时,簇形HWSNs的稳态可用度从0.831 1变化到0.995 2,增加了约19.74%;而当整个簇形HWSNs的路由数为4、簇中普通异质传感节点数从2变化到6时,簇形HWSNs的稳态可用度从0.713 1变化到0.998 0,增加了约39.95%。实验结果反映出当构建簇形HWSNs时,在簇中增加冗余的异质传感节点数比在整个簇形HWSNs中增加路由数更能有效提高整个簇形HWSNs的稳态可用度。

图6 簇形HWSNs的稳态可用度

5 结论

HWSNs稳态可用度评估能反映网络在长期或较长期运行的情况下HWSNs数据感知、通信、汇聚等功能处于可用或可操作状态的概率,是评估HWSNs性能的重要指标,为此,本文提出了一种面向恶意程序传播的HWSNs稳态可用度评估方法。本文扩展得到的SIRD模型比SIR模型更确切地反映了异质传感节点的状态,能描述节点因能量耗尽、物理损坏或恶意程序攻击导致功能丧失的情况。通过Markov链描述了节点各状态之间的动态转换,得到的状态动力学方程能反映各状态的动态变化过程。得到了能反映异质传感节点稳态可用度的计算公式,并进一步推理得到了能反映星形和簇形HWSNs稳态可用度的计算公式。实验结果说明了IDS检测率和误报率对提高异质传感节点稳态可用度的影响,分别给出了提高星形和簇形HWSNs稳态可用度的建议,为高可用的HWSNs设计、部署和维护提供了理论依据。

本文提出的方法适用于评估面向恶意程序传播的HWSNs稳态可用度,实现了星形和簇形这两种典型拓扑结构下HWSNs稳态可用度的评估。然而,面对复杂的HWSNs稳态可用度评估,仍有大量工作要做。例如,Mesh拓扑结构也是HWSNs的典型拓扑结构,如何针对该结构进行稳态可用度评估是非常值得进一步研究的课题。

[1] 钱志鸿,王义君. 面向物联网的无线传感器网络综述[J]. 电子与信息学报,2013,35(1):215-227.

[2] Trivedi K S,Kim D S,Ghosh R. System Availability Assessment Using Stochastic Models[J]. Applied Stochastic Models in Business and Industry,2013,29(2):94-109.

[3] Costa D G,Silva I,Guedes L A,et al. Availability Issues in Wireless Visual Sensor Networks[J]. Sensors,2014,14(2):2795-2821.

[4] 王文彬,孙其博,杨放春. MANET下环境感知的服务可用性量化评估模型[J]. 计算机研究与发展,2012,49(3):558-564.

[5] 王海涛,朱世才,陈晖,等. 应急通信中基于ANP的WSN可生存性评价指标体系研究[J]. 传感技术学报,2014,27(4):557-563.

[6] 朱世才,王海涛,吴连才,等. 基于SMP的分簇WSN生存性评估模型[J]. 传感技术学报,2014,27(3):383-387.

[7] 刘文芬,张树伟,龚心. 一种优化的基于Markov博弈理论的网络风险评估方法[J]. 电信科学,2014,30(7):13-18.

[8] 沈士根,黄龙军,范恩,等. 受恶意程序传染的WSNs可生存性评估[J]. 传感技术学报,2016,29(7):1083-1089.

[9] 李阿妮,张晓,赵晓南,等. 面向IaaS的云计算系统可用性评估[J]. 计算机科学,2016,43(10):33-39.

[10] 张晓花,董荣胜. 基于OBDD的无线传感器网络可用度算法[J]. 桂林电子科技大学学报,2016,36(3):210-214.

[11] Silva I,Guedes L A,Portugal P,et al. Reliability and Availability Evaluation of Wireless Sensor Networks for Industrial Applications[J]. Sensors,2012,12(1):806-838.

[12] Faghih-Roohi S,Xie M,Ng K M,et al. Dynamic Availability Assessment and Optimal Component Design of Multi-State Weightedk-out-of-nSystems[J]. Reliability Engineering and System Safety,2014,123:57-62.

[13] Yue Y,Li J,Fan H,et al. An Efficient Reliability Evaluation Method for industrial Wireless Sensor Networks[J]. Journal of Southeast University(English Edition),2016,32(2):195-200.

[14] Costa I,Araujo J,Dantas J,et al. Availability Evaluation and Sensitivity Analysis of a Mobile Backend-as-a-Service Platform[J]. Quality and Reliability Engineering International,2016,32(7):2191-2205.

[15] Loganathan M K,Kumar G,Gandhi O P. Availability Evaluation of Manufacturing Systems Using Semi-Markov Model[J]. International Journal of Computer Integrated Manufacturing,2016,29(7):720-735.

[16] Hu L,Su P. Fuzzy Availability Assessment for a Discrete Time Repairable Multi-State Series-Parallel System[J]. Journal of Intelligent and Fuzzy Systems,2016,30(5):2663-2675.

[17] 沈士根,刘建华,曹奇英. 博弈论与无线传感器网络安全[M]. 北京:清华大学出版社,2016.

[18] Wang Y,Yang X. Virus Spreading in Wireless Sensor Networks with a Medium Access Control Mechanism[J]. Chinese Physics B,2013,22(4):040206,5.

[19] Tang S,Myers D,Yuan J. Modified SIS Epidemic Model for Analysis of Virus Spread in Wireless Sensor Networks[J]. International Journal of Wireless and Mobile Computing,2013,6(2):99-108.

[20] Wang X,He Z,Zhang L. A Pulse Immunization Model for Inhibiting Malware Propagation in Mobile Wireless Sensor Networks[J]. Chinese Journal of Electronics,2014,23(4):810-815.

沈士根(1974-),男,汉族,绍兴文理学院计算机科学与工程系教授,博士,主要研究方向为无线传感器网络、移动互联网、博弈论,shigens@126.com;

黄龙军(1976-),男,汉族,绍兴文理学院计算机科学与工程系讲师,博士,主要研究方向为电磁纳米网络、无线传感器网络、博弈论,hlj_jlh@163.com;

曹奇英(1960-),男,汉族,东华大学计算机科学与技术学院教授,博士生导师,博士,主要研究方向为普适计算、智能信息处理,caoqiying@dhu.edu.cn。

Steady-State Availability Evaluation for Heterogeneous WSNs under Malware Infection*

SHEN Shigen1*,HUANG Longjun1,ZHOU Haiping1,FAN En1,LI Hongjie2,CAO Qiying3

(1.Department of Computer Science and Engineering,Shaoxing University,Shaoxing Zhejiang 312000,China;2.College of Mathematics,Physics and Information Engineering,Jiaxing University,Jiaxing Zhejiang 314001,China;3.College of Computer Science and Technology,Donghua University,Shanghai 201620,China)

To predict available performance of Heterogeneous Wireless Sensor Networks(HWSNs),we propose a method to evaluate steady-state availability of HWSNs under malware infection. Based on actual states of an heterogeneous sensor node,we extend the traditional epidemic-model SIR to SIRD by adding stateD(Dead)to describe the case that a node is dysfunctional due to energy consumption,physical damage,or malware attacks. We next illustrate state transitions among different states with a Markov chain,analyze and attain the state transition matrix and dynamical equations of all states. Moreover,we compute a node’s steady-state availability,and deduce steady-state availability equations for star and cluster HWSNs,respectively. Experiments analyze influences produced by IDS’ detection rate and false alarm rate on a node’s steady-state availability,and verify the proposed method’s efficiency.

heterogeneous wireless sensor networks;steady-state availability evaluation;malware;epidemic model;Markov chain

项目来源:国家自然科学基金项目(61272034);嘉兴市科技局项目(2016AY13011)

2017-01-01 修改日期:2017-02-09

TP393

A

1004-1699(2017)07-1100-06

C:7230

10.3969/j.issn.1004-1699.2017.07.022