基于随机博弈网的Ad Hoc网络攻击行为分析

摘 要：Ad Hoc网络攻击行为分析可以为Ad Hoc网络安全机制的设计提供借鉴，为此提出一种基于随机博弈网的ad hoc网络安全分析方法。该方法通过建立Ad Hoc网络的攻防随机博弈网模型并计算得到纳什均衡策略，然后将模型转化为一个同构的连续时间马尔科夫链（CTMC），通过计算CTMC的稳态概率就可以对Ad Hoc网络的攻击行为进行定量分析。仿真结果表明攻击行为的成功概率只与攻击能力与预期收益有关，而与攻击速率无关。

关键词：Ad Hoc网络；随机博弈网；连续时间马尔科夫链；攻击行为分析

中图分类号：TN929.5

Ad Hoc网络是一种最初被开发出来用于军事领域的特殊的无线移动网络。随着移动设备和无线网络的普及，Ad Hoc网络将拥有越来越广阔的应用前景。但由于其自身无中心、自组织、多跳、节点能源及计算能力有限等特点，使得Ad Hoc网络更容易受到安全威胁。

建立一套行之有效的Ad Hoc网络安全评价与分析方法可以为Ad Hoc网络安全机制的建立提供方向。因此国内外有不少学者对此进行了研究。刘建军等[1]提出了一种基于不确定性理论的Ad Hoc网络可信性评价模型，该模型采用不确定变量来描述网络的评价因子的权重系数，最后用实验结果表明了模型方法的可行性和有效性。何明等[2]提出了一种可以有效评估自然失效和能量束缚条件下的无线传感器网络的网络可靠性。针对同一时刻有多种拓扑结构且每种拓扑结构以一定概率出现的Ad Hoc网络，肖坤等[3]提出了一种基于韧性度的Ad Hoc网络可生存性度量方法。马涛等[4]提出了一种针对Ad Hoc网络攻击的改进攻击树建模方法，该方法可以有效地对节点的属性参数进行量化分析。

以上针对Ad Hoc网络的安全性评价方法都在一定程度上对Ad Hoc网络的某一项安全属性进行了分析，但在模型的动态描述能力上存在着不足。针对这一问题，提出了一种基于随机博弈网（Stochastic Game Nets，SGN）[5]的Ad Hoc网络安全分析方法。该方法将随机博弈思想与随机Petri网相结合，用随机博弈中的行为强度和选择概率给随机Petri网中的变迁赋值，然后通过求解随机Petri中位置的稳态概率和变迁的吞吐量等数值对网络安全进行定量分析的一种方法。最后，在该模型基础上用仿真实验对Ad Hoc网络的攻击行为成功概率进行了分析。

1 基于SGN的Ad Hoc网络模型

1.1 Ad Hoc网络SGN的模型定义

对于Ad Hoc网络，考虑博弈双方为网络攻击者与网络系统自身。由于网络攻击者的收益会成为网络系统的损失，因此博弈类型为双人随机零和博弈。

定义1 Ad Hoc网络的SGN模型为一个9元组，SGN（Ad Hoc）=（N，P，T，F，π，λ，R，U，M），其中：

（1）N={N1，N2}，N1表示Ad Hoc网络攻击者，N2表示Ad Hoc网络自身；

（2）P=P1∪P2∪…∪Pn为位置集合，表示系统可能处于的状态；

（3）T=A∪D为行为集合，A（a1，a2，…，an）表示Ad Hoc攻击者的攻击行为集合，D（d1，d2，…，dn）表示Ad Hoc网络的防御行为集合；

（4）F为弧的选择概率；

（5）π：T[0，1]，表示某条弧（攻击或防御行为）的选择概率；

（6）λ=（λ1，λ2，…，λn），表示Ad Hoc网络攻防行为强度；

（7）R：T（r1，r2，…rn）表示Ad Hoc网络攻击和防御行为被选择后带来的收益或损失；

（8）Uk（pi）（k=1，2）表示Ad Hoc网络攻击者与Ad Hoc网络自身在位置pi处的收益函数；

（9）M为标识集合。

1.2 Ad Hoc网络攻击行为与防御策略描述

选用Ad Hoc网络典型的攻防策略构建Ad Hoc网络攻防行为集合。其中Ad Hoc网络攻击者的攻击行为描述为：

（1）虫洞攻击[6]（wormhole）：一种由两个恶意结点合谋针对Ad Hoc路由协议的严重攻击；

（2）Sybil攻击[7]：攻击者假冒多个节点，造成虚假的节点冗余信息，使得依赖于节点冗余特性的路由算法以及其它算法无法正常工作；

（3）自私性攻击[8]（selfish attack）：攻击者节点只接受数据包和路由包，而不转发数据包和路由包，从而对网络的通信流量和延迟造成较大的影响；

（4）RREQ flooding攻击：攻击者大量、连续地发送RREQ报文，使整个网络充满RREQ报文，占用大量无线通信带宽，导致网络拥塞，正常通信无法进行，网络性能严重下降；

（5）无攻击行为。

针对网络攻击者的攻击行为Ad Hoc网络自身的防御措施描述如下：

（1）“数据包限制”[11]（packet leashes）：采用一种有效的认证协议TIK检测并防御虫洞攻击，即匹配每个数据包的时间戳和位置戳，以检测系统中是否有虫洞入侵；

（2）身份认证技术：使用惟一对称密钥，即通过此密钥每个节点能够证明其邻节点的身份，防止身份的假扮以此来防御Sybil攻击；

（3）强制合作：采用基于令牌的强制合作机制来尽可能地降低自私性攻击带来的影响；

（4）设定RREQ的发送优先级：如果节点发送过多的RREQ包，则降低对它的处理优先级，以此来防御RREQ flooding攻击；

（5）无防御行为。

1.3 SGN分角色模型

根据前一节给出的Ad Hoc网络攻击行为，可以构建基于攻击者视角的SGN模型，如图1所示。其中，圆形表示位置，代表系统所处于的状态；矩形表示变迁，代表攻击者或防御者所采取的行为；圆形中带有黑点的位置表示模型的初始状态。同理，可以构建网络防御者视角的SGN模型，如图2所示。

1.4 Ad Hoc网络的SGN攻防组合模型

根据图1，图2构建的分角色SGN模型，通过将相同含义的位置进行合并可以得到Ad Hoc网络的SGN攻防组合模型，如图3所示。其中，黑色的变迁表示攻击者的攻击行为，白色的变迁表示Ad Hoc网络的防御策略。由于空行为对模型的计算没有任何影响，因此省略该位置。表1给出了各个位置的具体含义。

2 Ad Hoc网络SGN模型的稳态概率

2.1 SGN组合模型参数设置及攻击行为均衡策略计算

Ad Hoc网络攻击者的目标是破坏Ad Hoc网络，使其无法正常健康地运行。其中Ad Hoc网络攻击者的收益即为Ad Hoc网络系统自身的损失。由于Ad Hoc网络攻击者并不知道Ad Hoc网络自身会采取怎样的防御措施，因此Ad Hoc网络攻击者不能按纯策略来选取攻击行为，而应是一种混合策略。

定义2 对于Ad Hoc网络SGN模型中的位置P0，给出以下收益描述矩阵：

其中，收益矩阵中的元素rij表示Ad Hoc网络攻击者和防御者在位置P0处采用行为对（ai，dj）时网络攻击者可以获得的收益。

由于攻击行为只会被相对应的防御行为影响，因此收益矩阵的参数可以设置为r11=2，r12=r13=r14=8，r22=3，r21=r23=r24=5，r33=1，r31=r32=r34=4，r44=1，r41=r42=r4=6。根据随机博弈均衡策略的标准计算方法[12]，可以计算得到Ad Hoc网络攻击行为的均衡策略。其中攻防行为强度λ及计算得到的均衡策略概率π如表2所示。

2.2 同构的连续时间马尔科夫链

已经证明，一个随机Petri网同构于一个连续时间马尔科夫链（CTMC）。由于SGN是一种特殊的随机Petri网，同理可得一个SGN同构于一个CTMC，根据标准技术，求出可达标识集如表3所示，同构马尔科夫链如图4所示。

图4中，可达标识集Mi（i=1，2，3，4，5）表示位置集（P1，P2，P3，P4，P5）拥有的标识情况。弧上的标记表示同构CTMC的变迁实施速率，其值为πi1λi1，πi2λi2（i=1，2，3，4）。其中πi1，λi1表示Ad Hoc网络攻击者某一攻击行为的选择概率与行为强度，πi2，λi2表示Ad Hoc网络自身防御行为的选择概率与行为强度，具体数值表2已经给出。

根据变迁实施速率和CTMC的标准计算方法，可以得到同构CTMC的状态转移矩阵Q，如表4所示。

3 Ad Hoc网络攻击成功概率分析

3.1 Ad Hoc网络攻击成功概率计算方法

基于已经求得的同构CTMC的可达标识的稳态概率，系统的很多安全性评价指标就可以被量化分析，如：首次安全事件的平均时间，安全事件的平均间隔时间，网络系统的机密性、完整性，攻击的成功概率与响应时间等。

以下给出系统单位时间内攻击成功概率的计算公式：

pattack（ai）=P[M（pr）≠0]=1-P[M（pr）=0] （3）

式（3）中，pattack（ai）表示系统单位时间内的Ad Hoc网络攻击者的攻击成功概率，P[M（pr）=0]表示攻击行为的结果位置标识为空的概率。

随着系统时间的发展，攻击成功概率可以理解为攻击者在系统时间t内至少有一次攻击成功的概率，根据公式（4）可以给出攻击成功概率随着系统时间发展的计算公式：

ptattack（ai）=1-Pt[M（pr）=0] （4）

式（4）中，t（t=1，2，3，……）表示系统时间，ptattack（ai）表示系统时间t内Ad Hoc网络攻击者的攻击成功概率，Pt[M（pr）=0]表示单位时间内攻击行为的结果位置标识为空的概率的t次方。

3.2 Ad Hoc网络攻击成功概率Matlab仿真分析

根据公式（4），使用Matlab对Ad Hoc网络攻击概率进行仿真分析，得到的结果如图5和图6所示。

图5和图6中，曲线表示虫洞攻击的成功概率随系统时间发展的变化情况，曲线表示Sybil攻击的成功概率随系统时间发展的变化情况，曲线表示自私性攻击的成功概率随系统时间发展的变化情况，+曲线表示RREQ flooding攻击的成功概率随系统时间发展的变化情况。

从图5，图6可以看出各种攻击行为的成功概率都随着系统时间的发展而增加。其中，Sybil攻击的成功概率最大，虫洞攻击的成功概率第二，RREQ flooding攻击的成功概率次之，自私性攻击的成功概率最低。

通过比较图5，图6可以看出攻击成功概率与攻击的速率无关，而只与Ad Hoc网络攻击者的攻击行为强度以及其预期收益有关。这是一个很重要的结论，这意味着Ad Hoc网络防御机制的设计者将不需要关心攻击行为的频率，而只需要关心攻击行为的强度和预期收益即可。

Ad Hoc防御机制的设计者可以根据不同的实际情况对模型的初始行为强度和预期收益进行设定，从而得到满足自己需求的安全数据。

4 结语

行之有效的Ad Hoc网络安全分析方法将会为Ad Hoc网络安全机制的设计提供方向和借鉴。针对这一问题，本文提出了一种基于随机博弈思想和随机Petri网相结合的随机博弈网模型方法，通过建立Ad Hoc网络攻防随机博弈网模型，求解与模型同构的马尔科夫链可达标识的稳态概率，可以为Ad Hoc网络安全性指标进行定量分析。通过仿真分析可知：攻击行为的成功概率与攻击频率无关。

下一步的工作将会把Ad Hoc网络攻击行为的相互影响考虑进去，构建更加完善的Ad Hoc网络攻防随机博弈网模型。

参考文献：

[1]刘建军.不确定环境下的Ad Hoc网络可信性评价模型研究[J].计算机科学，2011，38（8）：101-105.

[2]何明，董强，袁黎苗.无线传感器网络的可靠性评估模型[J].理工大学学报（自然科学版），2010（4）：392-396.

[3]肖坤，古天龙，常亮.一种Ad Hoc网络可生存性度量方法[J].桂林电子科技大学学报，2011（3）：213-216.

[4]马涛，单洪.移动Ad Hoc网络的改进攻击树建模方法研究[J].计算机应用与软件，2009，26（4）：271-273.

[5]王元卓，林闯，程学旗.基于随机博弈模型的网络攻防量化分析方法[J].计算机学报，2010（9）：1748-1762.

[6]黄成兵.基于Ad Hoc的虫洞攻击与防御研究综述[J].网络安全技术与应用，2012（6）：17-19.

[7]王峰，李平，朱海.一种基于社交网络的Sybil攻击防御[J].计算机应用与软件，2013，30（6）：38-39，59.

[8]李庆城，任开，宫晓利，丛跃进.结合结点信任度的Ad Hoc地址配置协议研究[J].计算机应用与软件，2013，30（2）：270-276.

[9]Yih-chun Hu，Adrian Perrig， David B Johnson.Packer leashes： A Defense against Wormhole Attacks in Wireless Ad Hoc Networks. Proceedings of the Twenty-Second Annual Joint Conference of the IEEE Computer and Communiciton Societies （IN-FOCOM 2003），IEEE[C].San Francisco，CA，April 2003（3）：1976-1986.

[10]Sallhammar K，Helvik B E，Knapskog S J.On stochastic modeling for integrated security and dependability evaluation[J].The Journal of Networks，2006，1（5）：31-42.

[11]Zuberek W M. Performance evaluation using unbound timed Petri nets.In：Proceedings of the Third International Workshop on Petri Nets and Performance Models[C].Kyoto Japan，1989，180-186.

[12]Molloy M K.Structurally bounded stochastic Petri nets. In： Proceedings International Workshop on Petri Nets and Performance Models[C].Wisconsin，USA 1987.

作者简介：孙杰，硕士研究生，主要研究领域：Ad Hoc网络安全；沈士根，副教授，主要研究领域：无线网络安全、博弈论；马绚，博士生，主要研究领域：无线网络安全；曹奇英，教授，博士生导师，主要研究领域：普适计算、优化决策等。

作者单位：东华大学计算机科学与技术学院，上海 201620；嘉兴学院数理与信息工程学院，浙江嘉兴 314001；东华大学信息科学与技术学院，上海 201620

基金项目：国家自然科学基金资助项目（61272034）。