无线网络中基于贝叶斯博弈模型的入侵检测算法研究

陈行，陶军

(1.东南大学 计算机网络和信息集成教育部重点实验室，江苏 南京 210096；2.东南大学 计算机科学与工程学院，江苏 南京 210096)

1 引言

近年来无线通信技术在全世界范围内得到了飞速的发展，由于能够方便地支持用户的移动性，无线网络成为 Internet的重要发展方向之一。无线网络节点的计算、存储、能量资源往往非常有限，无线信道带宽往往十分有限而且很不稳定。无线节点的移动性、无线信道的开放性更使得无线网络的安全性变得非常脆弱[1]，网络使用者本能的自私行为很难受到遏制，无线节点之间的行为往往相互影响并难于集中管理，而博弈理论正是研究无线网络安全问题的有力工具[2]。

入侵检测技术可以发现网络中的异常现象，目前已有数种无线网络的入侵检测部署方案[3～5]。基于网络的入侵检测系统通过检测网络中的报文，观察网络中发生的异常行为。网络攻击存在一定的模式，通过分析异常行为发生的频率、种类和顺序等要素，提取特征值，创建攻击知识库，可以判断网络是否遭到攻击和遭到何种攻击。然而网络攻击往往会发生一定的变化，采用固定不变的入侵检测参数无法把发生变化的攻击检测出来，必须根据网络受攻击的状况不断对入侵检测参数进行调整[6]。本文将贝叶斯博弈理论运用到无线网络中的入侵检测研究中，对入侵检测参数调整问题展开讨论。

2 入侵检测参数调整问题描述

由于无线节点资源的有限性，应当采用算法复杂度较低的检测算法。本文采用误用检测的思路[6]：每种网络攻击都由一系列相互关联的异常行为组成，当这一系列异常行为连续以高于正常频率出现的时候，才判断系统遭到攻击并发出警报。无线网络的特点决定网络中可能存在着诸如网络信道带宽的无故变化，网络连接无故中断然后又突然恢复，网络节点无规律的离开网络然后又无规律的重新加入网络等情况[7]。所以即使网络没有遭到攻击，异常行为也会以一定的概率发生。因此这里提出“阈值”[8]的概念，只有当阈值被超过的时候，才认为发生了攻击行为。针对不同种类的攻击，对阈值的定义是不相同的。它可能与异常行为的数量相关，可能与异常行为的频率相关，可能与异常行为的种类相关，也可能与异常行为的发生顺序相关，还可以是多种因素组成的复合向量。构成攻击行为的一系列恶意异常行为应当分布在一定的时间间隔内，否则会失去攻击效果，所以入侵检测系统对于攻击行为的检测也应当被约束在一定的时间间隔之内。只要攻击行为以一定的频率反复发生，便一定会有机会完整地分布在入侵检测的时间间隔之内。

定义 1 在正常情况下异常行为发生的频率被称为正常频率PN，将入侵检测的时间间隔称为TI，将入侵检测算法调整的时间间隔称为T。由攻击行为引发的异常行为被称为恶意异常行为。

每一种攻击都有一组相关的异常行为以及与之对应的阈值和时间间隔TI。当攻击行为发生变化，恶意异常行为在时间间隔TI内可能没有越过阈值，攻击没有被检测出来，但是攻击行为确确实实发生了。为了能更精确地检测出攻击行为，需要对检测参数进行调整，增大检测攻击的时间间隔TI，即每隔时间T逐步增大时间间隔TI，T＞TI。这使得入侵检测系统有机会检测出那些在阈值之下的攻击活动。当入侵检测系统检测到攻击的时候，系统可以对入侵行为进行分析，提取其中异常行为的信息，对阈值和时间间隔进行修正。这使得入侵检测系统能够跟踪攻击的变化情况，调整阈值。

3 基于贝叶斯博弈的入侵检测博弈模型及其完美均衡

根据无线节点的能源、无线连接数量、所转发的报文数量等要素可以判断这个无线节点在网络中的重要性。将无线节点的价值设置为ω，恶意节点的攻击获得成功的收益也为 ω，无线节点进行入侵检测的代价为Cd，攻击者发动攻击的代价为Ca。当恶意节点进行攻击时，入侵检测系统能够以 α的概率发出正确的警报，当网络没有受到攻击时入侵检测系统以β的概率发出误警，误警会给系统带来的损失为r。博弈双方的收益函数可以用表1来描述。

表1 博弈收益表

假设入侵检测系统以 p的概率对网络进行检测，恶意节点以q的概率对网络进行攻击，网络中存在恶意节点的概率为 μ。得到入侵检测系统的收益期望为公式 Ed=p[ q(μ a ω+μβr )-βr-Cd]+ω-qμω，恶意节点的收益期望为公式Ea=q(-paω+ω-Ca)。用取导数的方法可以得到，当入侵检测系统以的概率进行网络检测，恶意节点以的概率进行网络攻击时，网络安全博弈取得平衡[9]。

将时间间隔TI理解成一个博弈周期，在每一个博弈周期中，根据上一周期的检测结果运用贝叶斯法则对恶意节点存在概率μ进行修正。如果入侵检测系统发出警报，用式来对信念进行修正。如果入侵检测系统没有发出警报，那就用式进行修正。然后重新计算每一个博弈周期中合理的p*和 q*。

命题 1 在基于贝叶斯博弈的入侵检测博弈模型中存在完美均衡。

证明 这里根据文献[9]中的条件5来依次证明完美均衡的存在性。

这里的入侵检测博弈是一个双人博弈，只有 2个局中人，网络用户和网络安全系统。局中人只有一个博弈对手，所以局中人对博弈对手类型的信念必然是相互独立的，而且其他局中人对他的信念也是一致的，所以条件1和条件4必然符合。通过观察信念概率迭代式(1)和式(2)，可以发现对恶意节点存在概率的信念µ的修正结果仅仅取决上一周期的信念本身和网络用户在本周期的行动，因此条件3也成立。在每个回合对博弈对手的信念进行修正时引入误报概率α、β，所以条件2必然符合。考虑到网络安全系统只有一个类型，所以博弈策略集中不需要对网络安全系统的类型进行判断，因此条件5也满足。从上面的证明可以知道，基于贝叶斯博弈的入侵检测博弈模型的阶段均衡策略同时满足文献[9]中的条件5，所以它就是此博弈的完美博弈均衡点。

4 基于贝叶斯博弈的入侵检测调整

4.1 入侵检测时间间隔调整算法

入侵检测系统并不确切知道网络中是否真的存在恶意节点，它不断搜集无线网络中的报文信息，检测网络中存在的异常行为。为了检测出可能发生一定变化的攻击，需要对入侵检测算法进行一定的调整，不完全信息动态博弈理论为这种调整提供了理论基础。

在博弈周期内恶意节点的攻击概率为q*，其攻击行为引起的恶意异常行为在时间间隔 TI内超越阈值的概率也为q*。如果在博弈周期中没有检测出攻击行为，可能是因为没有恶意节点发起攻击，也可能是因为攻击引起的恶意异常行为没有越过阈值。为了检测出可能存在的攻击，这里假设网络中必然存在进行攻击的恶意节点，因为攻击行为发生了一定的变化，使得恶意异常行为的时间分布跨度超过了TI，所以入侵检测系统不能正确地检测出攻击行为。于是入侵检测系统将受到攻击时正确发出警报的概率α取为0。将α=0代入式(2)，得到

然而网络攻击者并不清楚入侵检测系统的调整情况，所以它将正确报警概率α设置为初始值，运用式来计算周期t中发动攻击的概率qt。

这里设计基于贝叶斯博弈的入侵检测时间间隔调整算法（TSMA-BG,time span modify algorithm based on Bayes game）。

在时间间隔T内存在n个TI时间的博弈周期，n=T/TI，周期编号为k,k+1,…,k+n-1。运用迭代式(3)和式(4)，计算各博弈周期中恶意节点的攻击概率qt，然后求和，得到时间间隔T内攻击行为发生次数的期望值，即攻击的次数期望约为将时间间隔T除以攻击次数期望，就得到了时间间隔TI的修正值

观察式(3)，易证得μt+1＞μt，所以得到经过这种方法修正的 TI必然比前一个时间间隔T内的TI值要大。

4.2 对入侵检测参数的修正算法

针对无线网络的攻击多种多样，可以抽象成多种多样的特征。为简单起见，这里将网络攻击抽象成异常行为种类 VoM、异常行为频率 FoM、时间分布跨度SoA这3个要素。只有当检测到的异常行为包括了足够的种类，每种异常行为的频率足够高，并且在这2个条件能在一定的时间内同时被满足，才认为网络遭到攻击，并发出警报。一旦网络攻击被发现，网络安全系统行动起来对网络进行全面的分析。分析攻击源头，判断其行为模式，将恶意异常行为的VoM、FoM和SoA整理出来，用得到的新数据对攻击阈值和入侵检测时间间隔进行修正。

这里设计入侵检测参数修正算法(DPMA,detection parameter modify algorithm)，算法如下。

恶意异常行为的种类：VoM={p,q,r,s},保持不变。攻击时间分布跨度：

恶意异常行为的频率：

在式(5)、式(6)中，VoM表示攻击与异常行为p、q、r、s相关联，这不会随着入侵检测参数的调整而改变。表示在博弈周期t内，攻击相关的异常行为分布的时间跨度，α、β表示修正参数。表示在博弈周期t中异常行为r的频率阈值，PNr表示正常情况下异常行为 r的发生频率。表示在刚检测到的攻击行为中时间跨度和异常行为 r的频率。这里应该特别指出，每一种攻击行为都有与之相关的 VoM和 SoA，与攻击行为相关的每一个异常行为都有各自的FoM。

4.3 针对多个异常行为进行的检测时间间隔调整

经过实验发现，当一种攻击行为包含有多种恶意异常行为的时候，对阈值的调整需要变得非常谨慎。入侵检测系统可以精确地检测出恶意异常行为的发生概率并进行入侵检测参数修正。当攻击只有一种恶意异常行为的时候，阈值和检测时间间隔TI可以很快调整至稳定状态，此时入侵检测系统能以很高的概率检测出攻击行为。而当攻击包含多种异常行为的时候，则必须要求每种异常行为都达到相应的阈值。如果一种异常行为到达阈值的概率为a，a＜1，那么n种异常行为同时到达阈值的概率则为an，an会随着n值的增大而迅速变小。实验证明，当n≥3的时候，根据攻击行为信息进行参数调整，阈值和入侵检测时间间隔TI无法稳定下来，在出现TI值大幅上升后缓缓下降，再大幅上升，反复震荡的现象。这是因为对入侵检测参数的修正使TI下降到一定程度时，入侵检测系统无法检测到发生的攻击，于是在时间间隔T后，又进行入侵检测时间间隔调整。当检测到攻击行为后，又根据检测到的信息进行入侵检测参数修正，反复进行。

在这样的情况下，原有的办法无法完全解决问题，此时应当对参数修正的目标进行调整，即入侵检测系统首先根据检测到的攻击行为信息进行参数修正，随着参数修正的不断进行，入侵检测系统开始无法有效地检测到攻击行为。此时应当将最近一次检测到攻击行为的入侵检测参数作为修正目标，而不是直接将检测到的攻击行为参数作为修正目标。即在DPMA算法中，用最后一次检测成功的参数来取代这种机制被称为基于回退机制的入侵检测参数修正算法(DPMA-DB,detection parameter modify algorithm based on drawback mechanism)。

5 入侵检测算法的数据结构和实现

本节为入侵检测参数调整设计数据结构和基本算法。首先是攻击知识库，它由一个二维数组和2个一维数组组成。二维数组 FoM[voa][vom]表示攻击行为相关的异常行为频率阈值，横坐标vom表示异常行为的种类，纵坐标voa表示网络攻击的种类，节点FoM[i][j]表示在网络攻击 i中异常行为 j的频率阈值。一维数组SoA[voa]表示每种网络攻击的时间分布跨度，一维数组TSA[voa]表示每种网络攻击的算法调整时间间隔T。

设置2个时钟数组clockI[voa]、clockT[voa]，针对每种网络攻击分别在2个数组中各保存一个时钟，分别为入侵检测时间间隔和算法调整时间间隔计时。当时钟值到达时间间隔时将时钟清零，重新开始计时。clockI[voa]对应时间间隔 SoA[voa]，clockT[voa]则对应入侵检测算法调整时间间隔T。

设置二维数组 counter[voa][vom]来保存异常行为计数器，节点counter[i][j]保存了网络攻击i中异常行为j的发生数量。每当异常行为k被发现一次，数组的第k列节点值都增加1。当时钟clockI[l]清零时，要将数组的第l行节点清零，重新开始计算异常行为的数量。当第l行的每一个节点counter[l][j]的值都满足 counter[l][j]≥SoA[l]×FoM[l][j]，认为网络遭到了攻击，发出警报。此时也要将数组的第 l行节点清零，重新开始计数，同时将时钟 clockI[l]和clockT[l]清零，重新开始计时。网络诊断模块也同时启动，对网络攻击进行全面分析，收集网络攻击的详细信息，阻止网络攻击的继续，并运用式(5)、式(6)对入侵检测参数进行调整，将调整结果分别保存到数组 FoM[voa][vom]、SoA[voa]中去。当时钟clockT[l]清零的时候，运用 4.1节中的 TSMA-BG算法对入侵检测时间间隔进行调整。

6 模拟实验及实验结果

这里用网络模拟软件 NS2[10]来对算法进行仿真，模拟恶意节点对多跳无线网络进行攻击的情景及网络安全系统的反应。

实验1 对灰洞攻击的检测和分析

恶意节点以一定的概率丢弃应当转发的报文，阻碍多跳无线网络中的报文传输，这被称为灰洞攻击。由于无线通信的特征，正常的无线信道本身也存在着一定的报文传输失败概率。入侵检测系统通过统计无线链路中报文传输失败的概率来发现灰洞攻击行为，当传输失败概率超过阈值的时候，入侵检测系统发出警报。入侵检测节点观察邻居节点收到报文和转发报文的数量[5]，可以精确地找到恶意节点及其行为特征。这为恶意节点行为特征的修正提供了必要的信息。

将网络系统的价值ω设置为500，网络安全系统进行入侵检测的代价Cd设置为100（在移动的无线节点中进行入侵检测通常要付出很高的代价），恶意节点发动攻击的代价Ca为50，误警损失r设置为100，正确发出警报的概率α为0.9，误警的概率为 0.2。报文传输失败的攻击阈值取为 0.95，分别将恶意异常行为的发生概率取为0.6和0.3。入侵检测算法调整的时间间隔T被设置为50个博弈周期，检测攻击的时间间隔TI的初始值被设置为5个时间单位。时间间隔TI和攻击阈值的修正参数α和β都被设置为 0.5。观察入侵检测时间间隔 TI的调整过程和攻击阈值的调整过程。

在图1中，横坐标表示博弈周期，纵坐标表示入侵检测时间间隔TI。这里不进行阈值的修正而只进行时间间隔TI的调整。图中的实线表示恶意异常行为概率为0.3时入侵检测时间间隔的变化情况，观察图1可以知道，在第50个博弈周期，也就是第一个时入侵检测算法调整的时间间隔T结束的时候，进行了第一次入侵检测时间间隔调整，TI由 5上升为12。在第100个博弈周期即第2个时间间隔T时进行了第二次入侵检测时间间隔调整，TI被调整为22。在第112个博弈周期时，入侵检测系统检测到了攻击行为，随即根据检测到的信息对TI进行修正。每检测出一次攻击就进行一次修正，使得TI不断下降，逐步稳定在 17个时间单位。图中的虚线表明恶意异常行为概率为0.6时，在第一个时间间隔T中就检测出了攻击行为，根据检测出的攻击信息进行的调整结果反而使得时间间隔 TI逐步上升，最终稳定在7个周期的时间内。

图1 单独进行入侵检测时间间隔调整

这里研究同时进行参数修正和入侵检测时间间隔调整的情况下，阈值和时间间隔 TI的变化情况。图2和图3中的2条曲线表示恶意异常行为的发生概率分别为0.6和0.3时，TI和阈值的变化情况。当第一个时间间隔T结束的时候，TI开始第一次调整，从第二个时间间隔T开始检测到攻击行为，开始根据检测到的信息进行参数修正。阈值经修正不断减小，分别稳定为0.6和0.3，这和恶意异常行为的发生概率相符合。当发生概率为0.3时，TI首先上升，然后逐步下降为至 5。而发生概率为 0.6时，TI直接下降直到5。这是因为TI在调整的同时，阈值也在不断下降。随着阈值的稳定，时间间隔回归到了初始的时间间隔 5，此时入侵检测系统可以正常的检测出变化过的攻击行为。

图2 时间间隔的变化情况

图3 攻击阈值的变化情况

实验2 针对隧道攻击的检测和分析

这里模拟恶意节点进行隧道攻击的情景，选取3种异常行为进行判断：修改路由控制报文序列号使之失效、发送错误的路由控制报文使报文向恶意节点汇聚、将收集的报文向特定节点转发。将其阈值设置为{0.95,0.95,0.95}，恶意异常行为的发生概率为{0.6,0.65,0.7}。其他参数设置与实验1中设置的相同。

图4中实线表示对包含3种异常行为的隧道攻击进行入侵检测时TI的变化情况，虚线表示对只有一种异常行为的灰洞攻击进行入侵检测时TI的变化情况。这里直接使用了DPMA算法。如图中所示，当只有一种异常行为时，对检测时间间隔TI的调整取得了很好的效果，当TI稳定的时候，入侵检测系统可以以很高的概率检测出潜在的攻击行为。而当有 3种异常行为时，TI值出现大幅度的波动，此时入侵检测系统对攻击行为的检测概率也很低，往往低于50%。具体原因参见4.3节的分析。

图4 调整比较

这里针对隧道攻击进行入侵检测时采用的不同入侵检测参数修正算法进行研究。图5中的虚线表示采用DPMA算法进行参数修正，而实线则表示采用DPMA-DB算法进行参数修正。观察发现，当采用DPMA算法的时候，TI出现了较大的波动，而且这种波动没有趋向稳定的趋势，会一直持续下去。采用DPMA-DB算法时，TI值最低为5，然后逐渐回升，并最终稳定在8。这表明DPMA-DB算法可以使TI达到合适的稳定值，实验结果同时还表明，此算法可以使入侵检测系统能以大约85%的概率检测出攻击行为。

图5 入侵检测方式比较

图6展示了采用DPMA-DP调整算法后，攻击阈值的变化情况，3条曲线分别表示3种异常行为的攻击阈值。实验结果表明，算法可以对攻击阈值进行有效的调整，最终得到稳定的结果。

图6 攻击阈值的调整情况

7 结束语

本文将贝叶斯博弈理论引入到无线网络中的入侵检测研究中，运用不完全信息动态博弈中的完美均衡计算多个博弈周期中网络攻击者发动攻击的期望，设计入侵检测时间间隔调整算法TSMA-BG，使得入侵检测系统能够有效地检测出发生变化的攻击行为。根据检测出的攻击行为特征，对入侵检测参数进行修正，并设计入侵检测参数修正算法DPMA。实验发现，当攻击行为有多个异常行为的时候，单纯使用DPMA算法无法使入侵检测系统达到稳定的状态。这里设计基于回退机制的入侵检测参数修正算法DPMA-DB，实验证明，在入侵检测系统中使用 TSMA-BG算法和DPMA-DB算法可以对发生变化的攻击行为进行有效的检测。

[1] ZHANG Y,LEE W.Intrusion detection in wireless ad hoc networks[A].Proc MobiCom 2000[C].2000.275-283.

[2] JOHARI R,TSITSIKLIS J N.Routing and peering in a competitive Internet[A].Conference on Decision and Control[C].2004.

[3] HIJAZI A,NASSER N.Using mobile agents for intrusion detection in wireless ad-hoc networks[A].Proc of Second IFIP International Conference on Wireless and Optical Communications Networks(WOCN 2005)[C].2005.362-366.

[4] HASSWA A,ZULKERNINE M,HASSANEIN H.Routeguard: an intrusion detection and response system for mobile ad-hoc networks[A].Proc of IEEE International Conference on Wireless and Mobile Computing,Networking and Communications(WiMob’2005)vol 3[C].2005.336-343.

[5] JIANHUA S,FAN H,YAJUN G.A distributed monitoring mechanism for mobile ad-hoc networks[A].Proc of the 8th International Symposium on Parallel Architectures,Algorithms and Networks(ISPAN'05)[C].2005.236-240.

[6] KETAN N,AMITABH M.A novel intrusion detection approach for wireless ad hoc networks[A].Wireless Communications and Networking Conference[C].2004.831-836.

[7] HUBAUX P,GROSS T,LE Y,et al.Towards self-organizing mobile ad-hoc networks: the Terminodes project[J].IEEE Communication Magazine,2001,39(1): 118-124.

[8] MISHRA A,NADKARNI K,PATCHA A.Intrusion detection in wireless ad hoc networks[A].Proc of IEEE Wireless Communications[C].2004.48-60.

[9] 施锡铨.博弈论[M].上海:上海财经大学出版社,2000.SHI Y Q.Game Theory[M].Shanghai: Shanghai University of Finance and Economics Press,2000.

[10] The network simulator ns-2[EB/OL].http://www.isi.edu/nsnam/ns/.2009.