基于最优反应均衡的传感网恶意程序传播抑制方法*

沈士根,周海平,黄龙军,范 恩,胡珂立,曹奇英

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

项目来源:国家自然科学基金项目(61772018,61603258,61272034)

2017-04-08修改日期2017-06-09

基于最优反应均衡的传感网恶意程序传播抑制方法*

沈士根1,周海平1,黄龙军1,范 恩1,胡珂立1,曹奇英2

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

为抑制传感网恶意程序传播,在考虑传感网恶意程序传播参与者“有限理性”的基础上,提出一种基于最优反应均衡的方法。根据传感网恶意程序传播过程中的博弈分析,建立传感网恶意程序传播阶段博弈模型以反应传感网恶意程序和传感网入侵检测系统之间的博弈交互过程。由参与者之间博弈交互持续进行的事实,建立传感网恶意程序传播重复博弈模型。使用最优反应均衡预测传感网恶意程序的行为以解决重复博弈纳什均衡解求解困难的问题,给出抑制传感网恶意程序传播的算法。实验分析了参与者基于最优反应均衡的策略,对所提出方法的有效性进行了验证。

传感网;恶意程序;有限理性;最优反应均衡

近年来,保障包括物联网安全在内的网络空间安全已上升到前所未有的高度[1-2]。由于传感网是物联网构成的基础,所以物联网安全的保障实际上需要通过保障传感网安全来实现。其中,传感网恶意程序已成为破坏传感网安全的主要威胁[3-4]。因此,迫切需要分析传感网恶意程序的传播行为,给出防御传感网恶意程序传播的方法,以便较好地抑制传感网恶意程序的传播。

针对传感网恶意程序传播如何抑制的问题,王小明团队提出了面向移动传感网恶意程序空间分布的定向免疫和恢复控制策略[5],又在借鉴传染病防御思想上提出了脉冲免疫和恢复控制策略[6],还使用Pontryagin极大值原理得到了易感节点免疫比例与感染节点恢复比例的最优控制变量对,为抑制恶意程序在移动传感网中传播提供了安全策略[7]。杨雄等人[8]在扩展传统SIR传播模型基础上,提出了一种适用于传感网的攻防策略优化模型。傅蓉蓉等人[9]提出了一种传感网环境自适应的节点免疫算法。王田等人[10]在建立移动恶意程序传播模型基础上,通过挂起感染边界附近的高风险节点来阻断恶意程序的进一步传播。Zhu和Zhao[11]针对传感网中的恶意程序,给出了基于Pontryagin最大化原理的最优防御策略。同样使用Pontryagin最大化原理,Eshghi等人[12]针对聚簇网络环境给出了一种优化的补丁安装策略,从而抑制恶意程序的传播。另外,Yang等人[13]利用软件多样性方法抑制恶意程序的传播。

要实现传感网恶意程序传播的抑制,寻找抑制策略是关键,而抑制策略的选择在本质上需要探究传感网恶意程序和传感网入侵检测系统之间的交互和相互依存性问题。博弈论与这种交互行为有着天然的密切关系,能够充分地考虑传感网恶意程序和传感网入侵检测系统策略的依存性及成本与收益之间的平衡性[14],因此,博弈论自然而然已成为一种寻找抑制策略的理论工具。刘玉岭等人[15]建立了一种基于静态贝叶斯博弈的绩效评估模型以及攻防双方对抗情形下的恶意程序攻防策略绩效评估方法。陈永强等人[16]提出了一种基于模糊贝叶斯博弈模型的网络最优抑制策略选取方法。王晋东等人[14]提出了一种基于静态贝叶斯博弈的最优抑制策略选取方法。Garnaev等人[17]利用贝叶斯博弈针对恶意攻击的不确定性给出了一种防御策略。Chen等人[18]基于演化博弈提出了一种主动防御传感网恶意程序攻击的方法。Spyridopoulos等人[19]利用完全信息静态博弈给出了能最小化恶意程序传播影响的优化策略。Liu等人[20]基于随机演化联盟博弈提出了一种针对传感云(Sensor-Cloud)服务系统中动态变化攻击的动态防御方法。Shen等人[21]提出了基于微分博弈的传感网恶意程序传播抑制策略。然而,上述文献均假设博弈参与者具有“完全理性”,而在实际博弈过程中,参与者常具有学习能力,即具有“有限理性”(Bounded Rationality)的特性。

本文考虑传感网恶意程序和传感网入侵检测系统的“有限理性”,基于最优反应均衡(Quantal Response Equilibrium)提出一种抑制传感网恶意程序传播的方法。首先,分析传感网恶意程序和传感网入侵检测系统博弈过程中的动作及各“动作对”的偏好值,给出传感网恶意程序传播阶段博弈模型;其次,根据实际传感网环境中传感网恶意程序和传感网入侵检测系统之间博弈交互持续进行的现状,将传感网恶意程序传播阶段博弈模型扩展为传感网恶意程序传播重复博弈模型;最后,针对传感网恶意程序传播重复博弈纳什均衡解求解困难的问题和参与者双方具有“有限理性”的事实,使用最优反应均衡预测传感网恶意程序的行为,提出抑制传感网恶意程序传播的新方法。

1 传感网恶意程序传播阶段博弈模型

定义1传感网恶意程序传播阶段博弈模型定义为一个三元组Θ=(Φ,Γ,Δ),其中:

①Φ={传感网恶意程序,传感网入侵检测系统}为参与者集合;

②Γ=ΓMal×ΓIDS为参与者动作集合的笛卡儿积,其中,ΓMal={aMal|合作(Cooperate,C),故障(Fault,F),预传播(Pre-infect,P),传播(Infect,I)}为传感网恶意程序的动作集合,ΓIDS={aIDS|休眠(Sleep,S),授权(Grant,G),防御(Defend,D)}为传感网入侵检测系统的动作集合;

③Δ=ΔMal×ΔIDS为参与者支付集合的笛卡儿积,其中,ΔMal={uMal(aMal):ΓMal|→}为传感网恶意程序的支付集合,ΔIDS={uIDS(aIDS):ΓIDS|→}为传感网入侵检测系统的支付集合。

在定义1中,对于传感网恶意程序而言,它有4种可能的动作。为了迷惑传感网入侵检测系统,被恶意程序感染的传感节点在与其他节点通信时会采取“合作”动作C使传感网入侵检测系统认为它是一个正常节点。由于传感网属于多跳网络,其网络通信可靠度较有线网络低,存在一定的数据丢包现象,对于这些不是因为恶意程序采取恶意行为造成的网络故障问题本文将其归结为“故障”动作F。然而,恶意程序的最终目的是窃取传感节点感知的信息,干扰传感网节点通信,甚至会通过耗尽传感节点电源等方式使传感节点完全失去功能,为了达到这些目的,传感网恶意程序会采取探测目标传感节点的漏洞和网络的拓扑结构等方面的“预传播”动作P,最后再采取“传播”动作I。

另一方面,传感网入侵检测系统可采取的动作跟传感网特性是密切相关的。由于入侵检测系统的运行需要耗费较多的能量,而传感节点能量有限,所以,传感网中的入侵检测系统一直处于运行状态不是一种优化策略,需要采取“休眠”动作S降低传感节点的能量消耗。传感网入侵检测系统启动后,当未检测到恶意行为时,需要采取“授权”动作G以便保证传感节点的正常工作;当检测到恶意行为时,需要采取“防御”动作D防御恶意程序的传播。值得说明的是,未检测到恶意行为包含两种情况:一种情况是被检测的数据确实不包含恶意行为,而另一种情况是由于任何入侵检测系统都存在漏报率,造成恶意行为的漏报。

根据上述分析,传感网恶意程序和传感网入侵检测系统之间博弈交互时共有12种“动作对”。例如,“动作对”(C,S)表示传感网恶意程序表现正常时,传感网入侵检测系统采取动作S;“动作对”(C,D)和(F,D)分别表示传感网恶意程序表现正常(动作C)和网络故障(动作F)时,传感网入侵检测系统因误报都采取动作D;“动作对”(P,G)和(I,G)分别表示传感网恶意程序表现出恶意行为而采取动作P和I时,传感网入侵检测系统因漏报都采取动作G;“动作对”(I,D)表示传感网恶意程序采取动作I时,传感网入侵检测系统成功检测到恶意程序的传播行为而采取动作D。

接下来分析传感网恶意程序和传感网入侵检测系统采取各“动作对”时的偏好值,并以此确定传感网恶意程序传播博弈模型的支付矩阵。对∀x,y∈Γ,记x≻y和x～y分别表示“动作对”x的偏好值优于“动作对”y和“动作对”x的偏好值等价于“动作对”y。对传感网恶意程序而言,采取动作I传播恶意程序后传感网入侵检测系统未能检测到恶意程序时,它获得的收益最大。而传感网入侵检测系统采取动作S和G都未能检测到恶意程序,因此,(I,S)与(I,G)具有相同的收益。接下来传感网恶意程序获得收益从大到小依次为(P,S)、(F,S)、(C,S)。另一方面,传感网恶意程序获得收益最小的是其采取“预传播”动作P时就被传感网入侵检测系统采取动作D实现防御,随后依次为(F,D)、(C,D)、(I,D)。综合上述分析,可得到传感网恶意程序对各“动作对”的偏好次序为:

(I,S)～(I,G)≻(P,S)～(P,G)≻(F,S)～(F,G)≻
(C,S)～(C,G)≻(I,D)≻(C,D)≻(F,D)≻(P,D)

(1)

对传感网入侵检测系统而言,获得收益最大的是传感网恶意程序采取动作C而传感网入侵检测系统采取动作S的情况。由于传感网入侵检测系统采取动作G比S要消耗更多的能量用于检查监控数据,所以“动作对”(C,G)获得的收益其次。当传感网入侵检测系统采取动作D时,它获得的收益从大到小依次为“动作对”(I,D)、(P,D)、(F,D)、(C,D)。当传感网恶意程序采取动作I而传感网入侵检测系统采取动作G时传感网入侵检测系统获得的收益最小,接下来依次为“动作对”(I,S)、(F,G)、(F,S)、(P,G)、(P,S)。综合上述分析,可得到传感网入侵检测系统对各“动作对”的偏好次序为:

(C,S)≻(C,G)≻(I,D)≻(P,D)≻(F,D)≻(C,D)≻

(P,S)≻(P,G)≻(F,S)≻(F,G)≻(I,S)≻(I,G)

由Binmore[22]提供的根据偏好次序定义各参与者支付值的方法,可以得到传感网恶意程序和传感网入侵检测系统采取各动作的支付矩阵,如表1所示。

表1 传感网恶意程序传播阶段博弈模型的支付矩阵

2 传感网恶意程序传播重复博弈模型

在实际的传感网环境中,传感网恶意程序和传感网入侵检测系统之间的博弈交互是持续进行的。例如,当传感网恶意程序采取动作C而传感网入侵检测系统采取动作S完成第1阶段博弈后,传感网恶意程序可以采取动作C、F、P或I进行第2阶段博弈,此时,传感网入侵检测系统针对传感网恶意程序的不同动作可以采取S、G或D完成第2阶段博弈,……,这些过程重复进行,直到传感网入侵检测系统采取动作D结束整个博弈。由此可知,传感网恶意程序和传感网入侵检测系统这两个参与者谁都不知道博弈何时结束,所以,该博弈属于典型的无限次重复博弈类型。图1给出了传感网恶意程序和传感网入侵检测系统之间的重复博弈过程。

图1 传感网恶意程序传播重复博弈过程

由图1可知,传感网恶意程序传播重复博弈实质是传感网恶意程序传播阶段博弈的重复,而对应的策略为一系列阶段博弈所定义的动作计划,参与者传感网恶意程序和传感网入侵检测系统能根据历史动作观察到上一个阶段博弈的结果,并由此选择未来的动作。另外,重复博弈中的支付值通常是每个阶段支付值折扣后的累加值。下面给出传感网恶意程序传播重复博弈的定义。

①参与者集合Φ与定义1相同;

④β∈[0,1]为折扣因子。

对于重复博弈而言,最大的问题是随着阶段博弈的不断重复,“策略对”总量将呈爆炸性增长趋势。在传感网恶意程序传播重复博弈的第1阶段,由图1可知共有12种“策略对”。由于传感网入侵检测系统采取动作D将结束整个博弈,因此在第2阶段博弈时共有9×12=108种“策略对”。依此类推,可得到传感网恶意程序传播重复博弈在阶段t时的“策略对”总量φt为:

φt=9×φt-1,t∈{2,3,4,…}

式中:φ1=12。

通常,对于一个非合作博弈,纳什均衡是最优解,达到纳什均衡意味着参与者双方都认为自己现有的策略是最好的策略,因此,在对方不改变策略的前提下,任何一方都不会调整自己的策略,否则,率先改变策略的一方将减少对应的期望效益。然而,面对传感网恶意程序传播重复博弈,求解纳什均衡将随“策略对”总量的爆炸性增长变得异常复杂。另外,在多阶段的传感网恶意程序传播重复博弈中,参与者双方“完全理性”的假设变得不现实。例如,传感网恶意程序在博弈的初始阶段为了隐藏自己,常采取动作C,此时的纳什均衡解为“策略对”(C,S),而传感网恶意程序最终将通过传播自己来达到获得传感节点上感知的信息,甚至破坏传感网通信的目的,此时的纳什均衡解变为“策略对”(I,D)。因此,针对传感网恶意程序传播重复博弈纳什均衡解求解困难的问题和参与者双方具有“有限理性”的事实,本文引入最优反应均衡来预测传感网恶意程序的行为,从而为抑制传感网恶意程序传播提供新方法。

3 基于最优反应均衡抑制传感网恶意程序传播的策略

最优反应均衡在行为博弈论中是一个普遍使用的均衡概念,最早由McKelvey和Palfrey[23]提出,其最大的特点是考虑了实际情况中参与者具有的“有限理性”,也就是说,在计算参与者选择动作后的期望收益时,各个参与者会因为认识偏差而造成错误。因此,在实际情况中参与者经常不能选择最优的纳什均衡,而只能选择参与者认为的最优策略。对于传感网恶意程序传播重复博弈,传感网恶意程序和传感网入侵检测系统会根据每个阶段博弈的结果进行学习,并修正自己的动作。随着博弈的进行,各个阶段博弈的均衡点不断变动,最终收敛于纳什均衡。

算法1基于最优反应均衡抑制传感网恶意程序传播的算法

步骤1 系统管理员配置传感网入侵检测系统的初使动作;

步骤2 系统管理员初使化传感网恶意程序传播重复博弈的博弈参数;

步骤3 传感网入侵检测系统被包含传感网恶意程序行为的监控数据唤醒;

步骤4t=1;

步骤5 DO WHILE T.

步骤7 IFaIDS="D" THEN

步骤8 BREAK;

步骤9 ELSE

步骤14 ENDIF

步骤15t=t+1;

步骤16 ENDDO

4 实验结果分析

使用Gambit实验工具,首先通过仿真得到传感网恶意程序传播重复博弈中传感网恶意程序和传感网入侵检测系统基于最优反应均衡的策略(如表2所示),再说明基于最优反应均衡抑制传感网恶意程序传播的有效性。实验参数设置时,传感网恶意程序和传感网入侵检测系统初始以等概率选择各自的策略,即传感网恶意程序以25%的概率选择动作C、F、P或I,而传感网入侵检测系统以约33.33%的概率选择动作S、G或D;参与者理性度参数初始设置为γ=0。

表2 传感网恶意程序和传感网入侵检测系统基于最优反应均衡的策略

图2给出了传感网恶意程序在给定理性度参数前提下基于最优反应均衡选择相应动作的变化趋势,其中,y轴表示选择某个动作的概率。从图2和表2的数据中可以看出,随着理性度γ值的增加,传感网恶意程序选择动作C的概率经历先降后升最后再下降的过程(两次拐点分别出现在理性度γ≈0.287 518和γ≈0.868 198),选择动作F的概率呈现越来越小的趋势,选择动作P的概率经历先缓慢上升再逐步下降的过程(拐点出现在理性度γ≈0.32 61),而选择动作I的概率呈现越来越大的趋势。最终,当理性度γ约达到15.576 65时,传感网恶意程序选择动作I的概率达到1,也就是说,此时动作C、F、P已被传感网恶意程序摒弃,传感网恶意程序始终选择动作I以获取最大的效益。

图2 传感网恶意程序基于最优反应均衡的策略

图3给出了传感网入侵检测系统面对传感网恶意程序采取的动作选择基于最优反应均衡的相应动作的变化趋势。从图3和表2的数据中可以看出,随着理性度γ值的增加,传感网入侵检测系统选择动作S和G的概率越来越小,而选择动作D的概率越来越大。最终,当理性度γ约达到2.293 818时,传感网入侵检测系统选择动作D的概率达到1,也就是说,此时动作S和G已被传感网入侵检测系统摒弃,传感网入侵检测系统始终选择动作D以获取最大的效益。

图3 传感网入侵检测系统基于最优反应均衡的策略

5 结论

如何抑制传感网恶意程序传播已成为当前保障传感网安全的研究热点,本文提出了一种基于最优反应均衡并考虑传感网恶意程序传播参与者“有限理性”的抑制方法。建立的传感网恶意程序传播阶段博弈模型分析了传感网恶意程序传播过程中各参与者的动作及偏好值,能体现参与者的交互过程,进一步建立的传感网恶意程序传播重复博弈模型能体现实际传感网中各参与者之间的重复博弈过程。通过最优反应均衡预测传感网恶意程序的行为,解决了重复博弈纳什均衡解求解困难的问题,给出的算法为实际应用提供了思路。实验结果说明本文方法能有效抑制传感网恶意程序的传播,为保障传感网安全提供了一种新方法。

[1] 罗军舟,杨明,凌振,等. 网络空间安全体系与关键技术[J]. 中国科学:信息科学,2016,46(8):939-968.

[2] 张焕国,韩文报,来学嘉,等. 网络空间安全综述[J]. 中国科学:信息科学,2016,46(2):125-164.

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

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

[5] Wang X,He Z,Zhao X,et al. Reaction-Diffusion Modeling of Malware Propagation in Mobile Wireless Sensor Networks[J]. Science China Information Sciences,2013,56(9):1-18.

[6] 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.

[7] 曹玉林,王小明,何早波. 移动无线传感网中恶意软件传播的最优安全策略[J]. 电子学报,2016,44(8):1851-1857.

[8] 杨雄,查志琴,朱宇光,等. 基于能量有限型无线传感网的恶意软件攻防优化策略[J]. 计算机工程与科学,2011,33(5):22-26.

[9] 傅蓉蓉,郑康锋,张冬梅,等. 无线传感器网络蠕虫的传播与控制[J]. 北京交通大学学报,2013,37(2):17-21.

[10] 王田,吴群,文晟,等. 无线传感网中移动式蠕虫的抑制与清理[J]. 电子与信息学报,2016,38(9):2202-2207.

[11] Zhu L,Zhao H. Dynamical Analysis and Optimal Control for a Malware Propagation Model in an Information Network[J]. Neurocomputing,2015,149:1370-1386.

[12] Eshghi S,Khouzani M H R,Sarkar S,et al. Optimal Patching in Clustered Malware Epidemics[J]. IEEE/ACM Transactions on Networking,2016,24(1):283-298.

[13] Yang Y,Zhu S,Cao G. Improving Sensor Network Immunity under Worm Attacks:A Software Diversity Approach[J]. Ad Hoc Networks,2016,47:26-40.

[14] 王晋东,余定坤,张恒巍,等. 静态贝叶斯博弈主动防御策略选取方法[J]. 西安电子科技大学学报,2016,43(1):144-150.

[15] 刘玉岭,冯登国,吴丽辉,等. 基于静态贝叶斯博弈的蠕虫攻防策略绩效评估[J]. 软件学报,2012,23(3):712-723.

[16] 陈永强,吴晓平,付钰,等. 基于模糊静态贝叶斯博弈的网络主动防御策略选取[J]. 计算机应用研究,2015,32(3):887-889.

[17] Garnaev A,Baykal-Gursoy M,Poor H V. Incorporating Attack-Type Uncertainty into Network Protection[J]. IEEE Transactions on Information Forensics and Security,2014,9(8):1278-1287.

[18] Chen Z,Qiao C,Qiu Y,et al. Dynamics Stability in Wireless Sensor Networks Active Defense Model[J]. Journal of Computer and System Sciences,2014,80(8):1534-1548.

[19] Spyridopoulos T,Maraslis K,Mylonas A,et al. A Game Theoretical Method for Cost-Benefit Analysis of Malware Dissemination Prevention[J]. Information Security Journal,2015,24(4-6):164-176.

[20] Liu J,Shen S,Yue G,et al. A Stochastic Evolutionary Coalition Game Model of Secure and Dependable Virtual Service in Sensor-Cloud[J]. Applied Soft Computing,2015,30:123-135.

[21] Shen S,Li H,Han R,et al. Differential Game-Based Strategies for Preventing Malware Propagation in Wireless Sensor Networks[J]. IEEE Transactions on Information Forensics and Security,2014,9(11):1962-1973.

[22] Binmore K. Playing for Real:A Text on Game Theory[M]. New York:Oxford University Press,2007.

[23] Mckelvey R D,Palfrey T R. Quantal Response Equilibria for Extensive Form Games[J]. Experimental Economics,1998,1:9-41.

QuantalResponseEquilibrium-BasedMethodforPreventingWSNsMalwareInfection*

SHENShigen1,ZHOUHaiping1,HUANGLongjun1,FANEn1,HUKeli1,CAOQiying2

(1.Department of Computer Science and Engineering,Shaoxing University,Shaoxing Zhejiang 312000,China; 2.College of Computer Science and Technology,Donghua University,Shanghai 201620,China)

We consider bounded rationality of players during the process of WSNs(Wireless Sensor Networks)malware infection,and propose a method based on QRE(Quantal Response Equilibrium)to prevent the infection behavior of malware. According to game analyses,we construct a stage game model to reflect interactions between two players-WSNs malware and WSNs IDS(Intrusion Detection System). Furthermore,we construct a repeated game model describing continual interactions between the two players. We then solve the problem of computing Nash Equilibrium in the repeated game by employing QRE to predict behaviors of WSNs malware,and attain an algorithm preventing WSNs malware infection. Experiments analyze QRE-based strategies for the two players,and confirm the efficiency of our method.

wireless sensor networks;malware;bounded rationality;quantal response equilibrium

TP393

A

1004-1699(2017)10-1589-07

10.3969/j.issn.1004-1699.2017.10.023

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

周海平(1977-),男,汉族,绍兴文理学院计算机科学与工程系教授,博士,主要研究方向为复杂网络、推荐算法、博弈论,hpzhou2885@163.com;

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