一种检测无线网络 MAC 层退避访问攻击行为的.doc

精品论文一种检测无线网络 MAC 层退避访问攻击行为的新型算法1李勇 ，冷甦鹏电子科技大学通信抗干扰国家级重点实验室，成都 (610054)E-mail：liyong647472yahoo.com.cn摘要：网络安全是无线网络正常高效工作的先决条件。IEEE802.11 的 DCF 功能采用二进 制随机退避（BEB）机制竞争信道。恶意节点很容易利用 MAC 协议中随机退避算法的特性 发动退避攻击，达到阻塞信道或扩大自身的利益的目的。文章将提出一种新的检测算法 CLT（Central limit theorem）算法，检测自私节点的违背协议的退避算法行为，该算法具有 较低的误判率，较快的检测速度。仿真试验表明，CLT 算法其正确判断概率和平均收敛速度 都要高于传统 DOMINO 算法。关键词：网络安全；随机退避；CLT 算法；MAC 攻击；检测 中图分类号：TP3931引言在无线自组织网络、无线局域网和无线Mesh 网络中，基于竞争共享型信道的IEEE802.11分布式协调(DCF)机制广泛用于无线信道的访问控制，其核心机制是载波侦听介质访 问/冲突避免（CSMA/CA）,当信道上发生报文冲突时，发送节点随机选择回退时间来避免冲 突。对信道资源的共享访问建立在节点间协同，信任的基础之上，然而网络中可能存在不遵 守退避准则的自私节点。这些节点通过选取较小的退避窗口不公平地抢占信道，或者为了达 到节能目的选取较大的竞争窗口而少转发数据，这样的行为被统称之为退避攻击行为。从大 量的仿真和试验123可以发现，退避攻击行为会破坏网络的公平机制，影响网络整体传输 性能，甚至会引起网络瘫痪。如何高效地检测和避免退避攻击行为，是无线网络领域急需解 决的重要课题之一。目前，已有部分文献研究了攻击行为的检测方法。例如，PRB算法3让发送节点通过上-7-次的退避值来动态地设置本次退避窗口的下限 Blb 。当本次退避时间 Bact< Blb 时便可直接判断出发送节点为恶意节点。该算法可以提高节点信道访问的公平性，检测出违背算法的恶意节点，但如果发送者选择略大于 Blb 的窗口值，将不会被检测出来。Kyasanur-Vaidya协议1则 是通过接受节点为发送节点设置退避时间，从而阻止节点的恶意行为，但是接收节点不能预 知下个时段网络中潜在的数据量，无法恰当地设置发送节点退避时间，网络的整体传输性能 难以优化。退避攻击行为的检测方法还可以通过建立数学模型4对数据分析，并得出检测结 果，但复杂的数学模型会造成节点大量的计算开销。DOMINO算法56是一种典型的简单数 学模型检测方法，该算法通过检测发送节点数据分组的平均时延，判断发送节点是否恶意。 但DOMINO算法很难确定判断门限，难以在检测准确度和检测速度之间取得折衷。此外， 恶意节点攻击呈智能化发展趋势，恶意节点能根据检测系统的检测方法采取相应的躲避措 施，使得退避攻击检测更加困难。本文提出了一种新的检测算法，CLT（Central Limit Theorem）检测算法，该算法将收 集到的发送节点的退避时间参数进行统计分析，能够用较少的计算开销，快速准确地检测出 恶意节点，并且不必对原有网络的MAC协议作修改，适用于各种竞争共享无线信道的退避 攻击检测。2CLT检测算法本节首先阐述 CLT 检测算法的单步检测方式，对检测性能进行理论分析，然后引入Markov 链形成 CLT 多步检测算法，并讨论其到达稳态时的理论转移步数。2.1 CLT 单步检测算法1本课题得到国家自然科学基金：车用无线自组织网络安全告警信息传输策略研究（No.60802024）的资助。IEEE 802.11 DCF采用随机退避机制，当节点有数据要发送且检测到信道忙时，启动随 机退避推迟发送，退避时间为t = Random(0,CW k ) × SlotTime ，其中，k为窗口阶数，取值为 5 至 10 的整数，每失败发送一次发送节点将k值增加 1；CW k 为第k阶的最大竞争窗口，通常为 2k 1 ； Random(0,CW k ) 表示取 0 至CW k 间均匀分布的随机整数；SlotTime 为时隙宽度。然而，如图 1所示，恶意节点（M节点）可能采用较小的窗口获取对信道的访问机 会，不公平地占用信道资源，使得正常节点（N节点）失去发送机会。DI F SN 节点 RTS DI F S正 常 退 避 窗 口M 节点 RT S恶 意 退 避 窗 口图 1 正常(N)和恶意(M)节点分别的退避行为我们提出了分布式的CLT单步检测算法侦测恶意节点的退避攻击行为，网络中各节点根 据测量到的信道参数独立执行该算法。为了判断一个被测节点是否为恶意节点，需要在不同 的窗口阶数下分别统计节点采用的退避窗口值5。如果每个窗口下都搜集n个分组才完成检 测，将造成检测周期过长。为了用较少的分组测量值计算出检测结果，提高检测速度，我们将第k阶窗口的竞争窗口范围Wa k ,Wbk 映射为标准窗口Wa ,Wb ，其中Wa k 和Wbk 分别表示第ik阶窗口下产生退避值区间的下限和上限，且 0 Wak< Wbk 。假设某个被测节点在发送第 i（ 0 i < n ）个分组时，经过若干次退避尝试后，最终在窗口阶数为 k 时采用退避窗口值Uik 成功发送。 Uik 是独立的随机变量，并且满足Uik= Random(Wa k ,Wbk ) 。如果将竞争窗口范围Wa k ,Wbk 映射为标准窗口，则U k 可换算成标准窗口下的对应值，即U = W+ W W U W )(1)(bak ki ak k i aWb Wa由U i 构造如下随机变量：nY = B (Ui E(Ui )i = 0(2)其中 B 是预设常量，E(Ui ) 为Ui 的均值。根据独立同分布的中心极限定理7，n 趋于无穷大 时Y 服从正态随机分布，且均值 E(Ui ) = = (Wa + Wb ) 2 ，方差为D(Ui ) = 2 = (Wb Wa)2 12。Y由式(2)可得，Y的均值为 E(Y ) = = 0 ，方差 D(Y ) = 2= nB 22 。如果取常量 B = 1n ，则可得nY = 1n (Uii = 0 ) (3)通过对比分析（详见 2.1 节），我们发现 Y 近似服从 N (0, 1) 正态分布。由正态分布的性质可知 Y 应该以大概率落在 0 值附近。为了检测出节点故意减少竞争窗口和增大窗口这两 种退避攻击行为，假定节点正常发送报文采用的竞争窗口应满足| Y |< z ，z 为是否正常使 用竞争窗口的判定门限，则正常节点（N 节点）被正确判定的概率为P(| Y |< z) = 2(z) 1其中 (z ) 为标准正态分布函数。ni i(4)假设网络中有恶意节点在窗口Wa ' ,Wb ' 下取随机退避值U ' ，则有Y ' =恶意节点被检测出的概率为 P '(Y ' < z Y ' > z ) 。又因为有i = 0(U ' ) /n ，n n i ' nz + n( ')(U')(Ui ')P'(i=0 <z)，即P'( i=0 < nz +n(') = ()n n'n'n '我们以 N 表示正常节点，M 表示恶意节点，恶意节点被检测出的概率为nz +n( ') nz +n( ')P(M | M) = 1( ) +()n'其中 ' = (W 'a + W 'b ) 2 , ' =n' '2 = | W 'b W 'a | 2 3 。(5)然而，在对节点行为判决中总存在着误判，主要包括以下两种情况：1）将N节点判为M节点，其误判概率为P(N| M ) = 2(1 (z )(6)2）将M节点判为N节点，其误判概率为 + )( |) (nz +n( ')( nz n( ' )PM N = n') n'(7)以上两个误判概率可作为CLT检测算法参数设置的依据。2.2 Markov 链 CLT 检测算法CLT单步检测算法能以很高的概率检测出恶意节点，但仍然存在将M节点误判为N节点 的可能。若要求不能出现将恶意节点误判的情况，且当单个节点发送数据分组的数量足够多 时，则可CLT算法的基础上采用Markov链56改进策略。图 2示出了基于Markov链的CLT改进策略的状态转移情况，图中被检测节点的状态变量s表示该节点的被怀疑为恶意节点的程度，状态变化范围从 0 至K+1。节点初始状态为s=0，当状态为K+1 时将节点判为恶意节点。p 表示节点从状态s转移到状态s+1 的转移概率，1 p则是状态s+1 转移到状态s的转移概率。状态转移概率 p = P(| Ytest |> z ) ，Ytest 为每n个退避窗口值采用CLT单步检测算法得到的判定结果，可由式(4)给出。当判定结果为可疑发送行 为（即| Ytest |> z ）时，执行s=s+1；反之，当判定结果为正常行为，且s不等于 0，则执行s=s-1。p1-p0 1 21-pK p K+1图 2 Markov 状态转移图容易发现，以上的状态转移过程构成了一个齐次吸收马氏链5，则该马氏链的K+2维状 态转移矩阵为1 pp0"0 1 p0p 0 " 0 P = 01 p0p " 0 1#%# 000" 1 0 从而可得 P 的等价矩阵为 P C = ，其中，R 为(K+1)×1 矩阵，S 是非吸收态到吸收态的状态转移矩阵,即 R S 1 p p 0"0 1 p0p0 "0 S =#%#%0 0" 1 p0p 00"1 p0 另外，采用 Markov 链状态转移过程判断一个恶意节点的平均转移步数直接影响到算法精品论文的收敛速度。由于以上吸收链的基矩阵 F = (ES S )1吸收态 i 出发到吸收态 K+1 的平均转移步数为（ ES 为 K+1 维单位矩阵），则从非K (8)i(K +1) = Fij + 1j = 03仿真结果与分析本节首先比较了 CLT 算法中变量 Y 的累积分布函数（cdf）与标准正态分布的 cdf，从 而验证 CLT 算法的理论依据，然后通过仿真对比分析验证 CLT 单步检测算法和 Markov 链 改进算法的检测性能。仿真场景中布置 10 个网络节点，每个节点平均每秒钟发送 10 个分组。3.1 CLT 算法的理论依据CLT 算法利用了随机变量 Y 对发送节点进行检测判决，若 Y 服从正态分布，则上节中的 理论推导是可行的。Y 的分布密度假设可通过仿真比较 Y 与标准正态分布的 cdf 加以证明。 我们采用 Matlab 建立仿真模型，CLT 算法检测节点的判断门限 z 取值 0 至 4，检测一个节点所需报文数量为 n=120，标准窗口设为Wst10000 次仿真。= 0, 63 。另外，仿真步长为 0.1，每个取值点作图 3示出了变量Y的累积分布函数（cdf）和标准正态分布N(0,1)的累积分布函数。由图 3可 知CLT算法的cdf与标准正态分布几乎完全重合，因此，CLT算法采用服从正态分布的假设， 能够达到较好的检测效果。由图可知，在3.0 以后落入判断门限区间的概率几乎为， 所以在后续的CLT单步检测算法仿真中取z=3.5。图 3 CLT 的 cdf 与 N(0,1)的 cdf 的比较32 CLT 单步算法检测性能检测算法的性能可用正常节点（N 节点）正确检测概率 P（N|N）和恶意节点（M 节点） 正确检测概率 P（M|M）进行评判。n 的取值直接决定检测时间，n 过大时，检测时间将过 长，且难以达到发送数据分组数量要求；但 n 值过小将使变量 Y 的分布函数偏离标准正态 分布，从而大大降低检测可信度，因此需要测试 CLT 算法在各个 n 值下的性能。CLT算法和DOMINO算法56具有相近的算法复杂度，在相同网络环境下，我们通过仿 真对比两种检测算法的性能。设置 10 个节点中 5 个为N节点，5 个为M节点，N节点一直严格遵守二进制指数退避退算法，采用CWst 回退窗口竞争信道，而M节点始终采用 3/4CWst 退避窗口竞争信道。两种检测算法分别对N节点和M节点检测 10000 次。DOMINO算法5的因子 =0.9，常量B设为该退避窗口的退避均值。图 4示出了分别采用CLT算法和DOMINO算法的正确检测概率P（N|N）和P（M|M）。容易 发现，CLT算法的N节点正确检测概率能够始终保持为 1，在n值较小时（n<50），正常节点 检测正确性明显优于DOMINO算法。另一方面，CLT算法的M节点正确检测概率随n值增加 而快速提高。在n值较小时，CLT算法的P（M|M）低于DOMINO算法，但此时两者的正确检精品论文查概率都很低，没有实用价值。而当n>110 时，CLT算法的P（M|M）明显高于DOMINO算 法，特别当n接近 160 时，CLT算法能使P（M|M）近似等于 1。由此可见，CLT单步检测算 法比DOMINO算法有更好的检测性能。图 4 CLT 与 DOMINO 检测性能的单步比较33 Markov 链改进算法性能为了减小单步检测带来的误判概率，消除将 M 节点误判为 N 节点的情况，我们可采用 Markov 链模型对 CLT 算法进行改进。Markov 改进算法需经过多步判断，允许在单次判断中 存在误判。为了减小检测时间，必须减小 n 值，否则总的检测所需数据分组太多而失去了使用 Markov 链的意义。为此，我们设置判定每个节点所需的累计报文数都为nT= 180 ,并选取n = nT(K + 1) 作为单次状态转移所用分组个数。为保证性能对比的公正性，我们选取带Markov链的DONIMO算法5与CLT算法Markov链改进策略进行仿真比较。当DOMINO算法取K=3,n = 45 时，达到最佳检测性能5。在CLT算法中，考虑到其单步检测的性能优于DOMINO算法，选取K=2，则n = 60 。经仿真检测发 现，当 = 0.88 ，z=1.7 时，DONIMO算法和CLT检测算法的误判概率能控制在 0.1% 以内（可通过图 5 得出）。在此基础上，我们仿真了Markov链改进算法对N节点和M节点分别发送的1600000 个数据分组进行的检测情况（如图 6 所示）。图 5 显示了正常节点被误判次数随网络中数据分组数量增加的变化情况。不难发现，CLT 算法将正常节点误判的概率低于 DOMINO 算法 25% 左右。图 6 示出了平均检测每个 M节点使用报文数，CLT 算法完成一次判断所使用分组的平均数明显小于 DOMINO 算法。由 图 5 和图 6 可知，采用 CLT 算法不仅误判次数少于 DOMINO 算法，而且具有更快的检测 速度。尤其在仅有少量恶意节点或数据分组较少的轻负载网络中，CLT 算法比 DOMINO 算 法更具有性能优势。图 5 Markov 链改进算法将 N 节点误判的次数图 6 Markov 链改进算法检测 M 节点平均 使用报文数4总结本文提出了一种基于中心极限定理（CLT）的新型信道攻击行为检测算法，该算法对违 背竞争信道随机退避算法的恶意节点非法抢占信道和中继偷懒行为都有较好检测效果。仿真 结果表明，与经典 DOMINO 算法相比，CLT 单步算法和 Markov 链改进算法能够以更高的 准确度、更快的收敛速度检测节点的退避攻击行为。CLT 算法适用于各种采用竞争共享信道 的无线网络，具有较广泛的应用前景。参考文献1P. Kyasanur and N. Vaidya. Selfish MAC layer misbehavior in wireless networks J. IEEE Transactions on Mobile Computing. Vol. 4, No. 5, pp.6-14, April 2004.2J. Bellardo, S. Savage. 802.11 denial-of-service attacks: Real vulnerabilities and practical solutions C, in Proc. USENIX Security Symposium, pp.17-35, 20033Lei Guang and Chadi Assi. Mitigating smart selfish MAC layer misbehavior in ad hocnetworks C. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications 2006, WiMob 2006, pp.116-123, 20064Jerzy Konorski. A station strategy to deter backoff attacks in IEEE 802.11 LANs J. Journal of Discrete Algorithms, Vol 5, pp.436454, 20075Alvaro A. C´ardenas2, Svetlana Radosavac and John S. Baras. Performance Comparison of Detection Schemes for MAC Layer Misbehavior C. in Proc. INFOCOM 2007, pp.1496-1504, 2007.6M. Raya, J. P. Hubaux, and I. Aad. DOMINO: A system to detect greedy misbehavior inIEEE 802.11 hotspots C. In Proc. of ACM MobiSys, pp.84-97, 2004.7 王立宁等编著.MATLAB与通信仿真北京 M，人民邮电出版社，2000A New Algorithm for Detecting MAC Backoff Access AttackMisbehavior in Wireless NetworkLi Yong ，Leng Supeng1 National Communication Laboratory, University of Electronic Science and Technology of ChinaChengdu, Sichuan, (610054) chinaAbstractNetwork Security is a fundamental prerequisite for network survivability and reliability in wireless network. IEEE802.11 Distributed Coordinating Function（DCF）is based on binaryrandom backoff for the channel competing. However, malicious node can launch backoff access attack, which disobey the rules of random access backoff algorithms, for the purpose of the unfair occupation of channel resource or selfish benefit enhancement. This paper proposes a novel Central Limit Theorem (CLT) algorithm to detect MAC misbehaviors of malicious nodes. The CLT algorithm has the characteristics of lower misdiagnose probability and more efficiency compared with the traditional detection methods. Simulation experiments show that the CLT algorithm is superior to the DOMINO algorithm, in terms of detection correctness and convergence speed.Keywords: network security; random backoff; MAC attack; CLT algorithm; detection;作者简介：李勇（1983-），男，四川乐山人，硕士研究生，主要研究方向：无线网络安全。 冷甦鹏（1973-）， 男，四川攀枝花人，博士，副教授，主要研究方向为无线自组织/传感器网络、无线多跳网络、下一代无线 网络等。