第 24 卷 第 10 期 2007 年 10 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 24 No. 10 Oct. 2007 基 于 静 态 贝 叶 斯 博 弈 的 攻 击 预 测 模 型 * ( 1. 兰州 大学 信息 科学 与工 程学 院, 兰 州 730000; 2. 清 华大 学 计算 机科 学与 技术 系, 北 京 100084) 曹 晖 1 , 王青青 1, 马义忠 1 , 罗 平2 摘 要: 提 出了 基于 静态 贝叶 斯博 弈的攻 击预 测模 型。 该模 型通 过模拟 攻击 者和 防御 者的 攻 防行 为 选 择, 能 预 测出 理性 的攻 击者和 防御 者为 最大 化各 自的 收益 会选 择 攻击 和 防 御的 概 率 。预 测 结 果 为 网 络 安全 管 理 员 进 行 安全 配置 提供 了有价 值的 参考 依据 , 从 而使 被动 的检 测变 为主 动的 有针 对性的 防御 成为 可能 。最 后 介 绍了 相 应 的实 验过 程和 结果分 析, 验 证了 模型的 有效 性。 关键 词: 静 态贝 叶斯 博弈 ; 博 弈论 ; 攻击 预测 ; 入 侵检测 中图 分类 号: TP393. 08 文章 编号 : 1001- 3695( 2007) 10- 0122- 03 文献 标志 码: A Attack prediction model based on static Bayesian game CAO Hui1 , WANG Qing-qing1, MA Yi-zhong1, LUO Ping2 ( 1. School of Information Science & Engineering, Lanzhou University, Lanzhou 730000, China; 2. Dept. of Computer Science & Technology, Tsinghua University, Beijing 100084, China) Abstract: This paper described an attack prediction model based on static Bayesian game. The model could predict the probabi- lity of attacks or defenses that reasonable attacker or defender would take, in order to maximize their payoff. Thus the result could be used to assist security administrators to configure the network system. It might improve the passive detection to the active protection for the defender. This paper also presented the process of experimental and analysis result for validity of the model. Key words: static Bayesian game; game theory; attack prediction; intrusion detection 1990 年, 第一个网络 入侵 检测系 统 NSM[ 1] 问 世。至今 为 止, 提出的方法有概率统计分析方法、数据挖掘方法、神经网络 方法、模糊数学理论、人工免疫方法、支持向量机方法等。然而 这些入侵检测的方法都滞后于攻击, 即使是能动态适应网络环 境的入侵防御系 统( IPS) 也 是在 攻 击发 生一 段 时间 后才 会 采 取防御措施。因此, 无论是入侵检测还是入侵防御系统均属于 被动防御的方法, 不能有效地进行攻击预测以提前阻止攻击的 发生。近年来, 经济学中的博弈论为主动防御领域的研究提供 了宝贵的思路。 早在 1997 年, Syverson[ 2] 就提出使用随机博弈来对网 络中 的正常节点和恶意节点进行理性分析的 想法。2002 年, Lye 和 Wing[ 3] 使用随机博 弈 形式 化 定 义和 实 现 了 Syverson 的 想法, 并给出一个应用在企业网络中的例子, 分析了企业和攻击者双 方进行博弈时的纳什均衡和 各自的 最优行 动。2003 年, Xu 和 Lee[ 4] 采用基于完全信息的静态博弈来设计和分析他们提出的 DDoS 防御系统, 并说明 正是由 于 引入 了 博弈 论使 得 DDoS 防 御系统性能得到了优 化。后来 Alpcan 等人 [ 5, 6] 使 用博 弈论 分 析无线网络中的入侵检测。他 们的研 究在不 同程度 上是针 对 完全信息下的博弈进行分析, 还没有明确给出不完全信息下的 博弈分析模型。 此外, 在 2005 年 Liu Peng 等 人 [ 7] 使用 重复博 弈和 随机 博 弈建立了一个基于入侵意 图的 攻击 预测 模型 AIOS, 并 详细 分 析了 AIOS 在 DDOS 防御 中 的应 用。本 文的 研 究 参考 了 其 思 想, 从一个新的角度提出了基于静态贝叶斯博弈的攻击预测模 型。主要工作包括: a) 系 统 地给 出 了攻 击预 测 模型 的形 式 化 定义。b) 详细分析 了该 攻击 预测 模 型下 的贝 叶 斯均 衡, 给 出 攻击预测的结果。c) 对 攻击 预测 模 型进 行实 验, 结 果表 明 该 模型能有效地预测当前网络存在攻击的可能性。 1 攻击预测模型( APM) 的描述 使用静态贝叶斯博弈能很好地对攻击进行理性的预测, 这 是因为: a) 静态贝叶斯博弈 是非合 作的不 完全信 息博弈, 能 模 拟现实中攻击者和防御者的攻防特征。b) 博 弈论是 研究决 策 主体行为依赖的理论, 而行为依赖正是计算机网络安全中最基 本的特征。防御者会根据当前 网络受 攻击的 威胁程 度来进 行 相对应的安全管理和配置; 而攻击者也会对目标主机的防御能 力 进 行探 测 和 估计, 从 而选 择 某 种攻 击 方 式或 不 进 行攻 击。 c) 博弈论在拍卖、股票等领域 应用非 常成功。拍 卖者、股票 的 投资者会根据当前获知的信息进行理性的预测, 作出选择来最 大化自己的收益。d) 贝叶斯纳什均衡 [ 9] 保 证了攻击 预测的 有 效性和理性。下面给出 APM 的形式化定义和分析过程。 1. 1 APM的形式化定义 本文将网络中的主机节点 抽象为 defender 和 attacker。其 中 defender 是指一个配有入侵防御系统( IPS) 的主机节 点。由 收 稿日期 : 2006- 08- 17; 修 返日期 : 2006- 10- 11 作 者简介 : 曹晖( 1982- ) , 男 , 江苏姜 堰人, 硕 士研究 生, 主要 研究方 向 为网 络 安全 、数 据库 安 全( wikicc @ gmail. com) ; 王 青 青 ( 1984- ) , 女, 宁 夏 基 金项 目: 国 家科 技部“973”资助项 目( 2003CB314805) 吴忠人 , 硕 士研 究生, 主要 研究 方向为 网络 安全、下一 代互 联网技 术; 马义 忠( 1952- ) , 甘 肃通 渭人, 副教 授, 主要 研究方 向为 网络安 全、分布 式计算 ; 罗平( 1959- ) , 男 , 湖 南溆 浦人, 副 教授, 主要 研究 方向为 网络安 全、信息 安全 、密 码算法 、有 限元 方法. 

第 10 期 曹 晖, 等: 基于 静态 贝叶 斯博 弈的 攻击 预测 模型 ·321· 参与人 j 表示 defender。Attacker 是指 网 络 中除 defender 之 外 的所有其他主机节点, 由参与人 i 表示 attacker。 ( θm i , θr i } 定义 1 攻击预测模型 包括以下六个元组。 1) 参与人 ( players) 包 括参 与人 i 和 参与 人 j。其 中: 参 与人 i 的类型空间为 θi { θm i 表 示参与 人 i 的类 型是 恶 意的主机节点, 能对网络造成 一定的 威胁和 破坏; θr i 表示参 与 人 i 的类型是正常访问网络的主机节 点, 不能 对网络造成 任何 破坏) ; 参与人 j 的类型空间为 θj = { θd j 表示参 与人 j 的类 型是配有 IPS 的主机节点, 能检测和阻止其他主机节点攻击) 。 2) 先验信念( prior belief) 是 指每 个参 与 人在 进行 博 弈 i ) 、 时认为 其 他 参 与 人 是 某 种 类 型 的 先 验 概 率, 包 括 p( θm p( θr j ) = 1。 i ) 、p( θd 3) 行动空间( action space) 指每 个参与 人在进 行博弈 时 i ) 、Ai ( θr i ) 、 i) = { not at- 依据其 所 属 类 型 可 以 选 择 的 行 动。包 括 Ai ( θm Aj( θd i ) = { attack, not attack} ; Ai ( θr tack} ; Aj( θd j ) = { defend, not defend} 。 i ) = 1 - ψ; p( θd j ) 。其中: p( θm j ) 。其中: Ai( θm i ) = ψ; p( θr j } ( θd 4) 收益函数( payoff) 指每 个 参与 人在 参 与博 弈时 依 据 i ) 、μi 其所属类 型 和 选 择 的 行 动 可获 得 的 收 益。 包 括 μi ( θm ( θr i ) 、μj( θd j ) 。 5) 私有信息( private information) 指只有参与人 i 知 道自 己的类型 θi, 参与人 j 不知 道参与 人 i 的类型 是恶意 的主机 节 点还是正常访问网络的 主机 节点。因 此参 与人 i 的类 型信 息 是参与人 i 的私有信息。 6) 共同知 识( common knowledge) 指每个 参与 人都 知 道 其他参与人的类型先验信念、类型依存行动空间及类型依存收 益函数。因此, 尽管参与人 j 并不知道参与人 i 的类型 θi, 但他 知道参与人 i 的行动空间和收益函数是如何依赖于他的类型。 i ) , j ) } 来 表 攻击预 测 模 型 可 用 APM = { θm j ) ; μi ( θm j ) ; Ai( θm p( θd 示。攻击预测的结果为 APM 的贝叶斯纳什均衡( BNE) 。 i , θd i , θr i ) , μi ( θr j ; p( θm i ) , μi ( θd i ) , p( θr i ) , Ai ( θr i ) , Aj ( θd 1. 2 APM 的贝叶斯纳什均衡(BNE) 由于参与人 j 不知道参与 人 i 的类 型, 无 法使用 完全信 息 [ 8] 的方法 来求解 APM 的 贝叶 博弈模型中求解纳什均衡( NE) 斯纳什均衡( BNE) 。但使 用 Harsanyi 转换 [ 8] 可以解 决这个 问 题, 通过引入一 个虚 拟的 参 与人 自 然( N) , 由 自然 首 先 行动, 决定参与人 i 的类型。这样 对于 参与 人 j 来 说, 参与 人 i 的 类 型就由不完全信息变成完全但不完美的信息, 从而可以构造如 图 1 所示的 博弈 树 [ 8] 来 分 析 不 完 全 信 息下 的 贝 叶 斯 纳 什 均 衡。表 1 列出了在图 1 中使用的符号及其含义。 鬃 兹m 参与人 i attack not defend defend 参与人 j defend 篆 员-鬃 not attack (0,0) 兹r not attack not defend defend 兹d (0,-滋PF-Cips) not defend (0,0) ((1鄄PD)棕-PD 茁-Catt,(PD-1)棕+滋PD-Cips (0,-滋PF-Cips) (棕鄄Catt-棕) 图1 Attacker 和 defender 的博弈树 表 1 博 弈树 中使用 的符 号列表 含 义 符 号 含 义 IPS 的 检 测 率 IPS 的 误 报 率 β 检 测 出 攻 击 时 , attacke r 受 到 的 惩 罚 μ 检 测 出 攻 击 时 , defender 得 到 的 收 益 Attacker 实 施 攻 击 的 代 价 Defender 阻 止 攻 击 的 代 价 ω 没 有 检 测 出 攻 击 时 , attacke r 的 收 益 没 有 检 测 出 攻 击 时 , defender 的 损 失 符 号 PD PF C att Cips 利用静态贝叶斯博弈对攻 击进行 预测的 基本思 路是参 与 人 i 和参与人 j 在进行博弈 时都是 理性的, 他 们都会 为最大 化 自己的收益而选择最优的行动。因此可作如下分析: a) 当 参 与 人 i 选 择 的 纯 策 略 的 行 动 是 ( ai ( θm i ) = { at- i ) = { not attack} ) 时: 若参与人 j 选择的纯策略的行 j ) = { defend} , 此时 defender 的收益为 tack} , ai ( θr 动为 aj( θd Ej( defend) = ψ( ( PD - 1) ω+ μP D - Cips) - ( 1 - ψ) ( μP F + Cips) 若 参与人 j 选择的纯策略的行动为 aj( θd j ) = { not defend} , 此时 defender 的 收 益 为 Ej ( not defend) = - ψω。 因 此 只 有 满 足 Ej( defend) ≥Ej( not defend) 时, 即 ψ≥ ( μP F + Cips ) / ( ωPD + μPD + μPF) 时, 对于 defender 来 说, 最 优 的 行 动 为 aj ( θd j ) = { defend} 。但如果 defender 选择了 aj( θd j ) = { defend} , 此时 对 attacker 来说, ai ( θm i ) = { not attack} 是 他 的 最 优 行 动。因 此 ( ( ai( θm j ) = { de- fend} , ψ) 不 是 一 个 纯 策 略 的 BNE。然 而 当 ψ< ( μPF + Cips ) / ( ωPD + μP D + μP F) 时, 对于 defender 来说, 最优行动为 aj( θd j ) = { not defend} 。因 此 ( ( ai ( θm i ) = { not at- tack} ) , aj( θd j ) = { not defend} , ψ) 是一个纯策略的 BNE。 i ) = { not attack} ) , aj ( θd i ) = { attack} , ai ( θr i ) = { attack} , ai ( θr b) 当参与人 i 选择的行动 为 ai( θm ψ的值是多少, 对于参与人 j 来说, aj( θd 他的最优行动; 然而当参与人 j 选择 aj( θd 参与人 i 最优行动为 ai ( θm 一样。因此( ( ai( θm aj( θd i ) = { not attack} 。无 论 j ) = { not defend} 都 是 j ) = { not defend} 时, i ) = { attack} 。这与 a) 讨论 的情 况 i ) = { not attack} ) , j ) = { not defend} , ψ) 不是一个纯策略的 BNE。 c) 当 ψ≥( μPF + Cips) / ( ωPD + μPD + μPF) 时, 由 a) 分析可 i ) = { not attack} , ai( θr 知不存在一个纯策略的 BNE。 - ψ( 1 - σ) ( μPF + Cips ) 若参与人 i 以 σ的概率选择 ai ( θm i ) = { attack} , 则参与人 j 选择 aj( θd j ) = { defend} 时的 收益为 Ej( defend) = ψσ( ( PD - - ( 1 - ψ) ( μP F + 1) ω+ μPD - Cips ) Cips ) ; 若参与人 j 选择 aj( θd j ) = { not defend} , 则 defender 的收 益为 Ej( not defend) = - ψσω。因此当 Ej( defend) = Ej( not de- fend) , 即当 参 与 人 i 以 σ* = ( μPF + Cips) / [ ψ( ωP D + μPD + μPF) ] 的概率选择 ai( θm i ) = { attack} 时, 对于参与人 j 来说, 选 择防御或不防御是没有区别的。 同理, 通过计算 Ei( attack) = Ei( not attack) , 可以求得当参 与人 j 以 ρ* = ( ω- Catt) /[ ( ω+ β) PD ] 的 概率 选 择 aj ( θd j ) = { defend} 时, 对于参 与人 i 来 说, 选 择攻 击和 不 攻击 是没 有 区 ( σ* 别的。因 此, i ) = { not attack} ) , ρ* ( aj( θd j ) = { defend} ) , ψ) 是一个混合策略的 BNE。 由上面分析可知, 在攻击预测模型 APM 下, attacker 和 de- fender 会按照表 2 所示的 BNE 结果进行博弈, 并由此来决定各 自的最优行动。 ) = { attack} ) , ai ( θm i ( θr ( ai ( ψ ψ < ( μP F + C ips) / ( ωP D + μPD + μPF) ψ > ( μP F + C ips) / ( ωP D + μPD + μPF) 表 2 BNE 表 BNE 存 在 纯 策 略 的 BNE ( ( ai( θm i ) = { attack} , a i( θr i) = { not attac k} ) , aj( θd j ) = { not defend} , ψ) 存 在 混 合 策 略 的 BNE ( σ* ( ai( θm i ) = { attack} ) , a i( θr ρ* ( aj( θd j ) = { defend} ) , ψ) i) = { no t attack} , 

·421· 计 算 机 应 用 研 究 第 24 卷 2 实验过程及结果分析 使用 GAMBIT[ 9] 博弈分析 工 具对 APM 进行 实验, 并 分 析 了实验结果。共做了以下两组实验: a) 测试入侵检测率 PD 和误报率 PF 对 APM 攻击预测结果 的影响。给定与收益函数相关的初始参数值: ω= 100, β= 120, μ= 80, Catt = 5, Cips = 10, ψ= 0. 5。实验结果如图 2、3 所示。 PF=0.01 PF=0.1 PF=0.5 0.8 0.7 0.6 0.5 0.4 0.3 PD=0.5 PD=0.7 0.2 PD=0.9 0.10 0.4 0.5 (b) PF 对 attacker 选择攻击的影响 0.3 0.1 0.2 * PF 0.550.650.750.850.95 PD (a) PD 对 attacker 选择攻击的影响 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.90.850.80.750.70.650.60.550.50.450.4 图2 选择攻击的影响 PF=0.01 PF=0.1 PF=0.5 * 0.90.850.80.750.70.650.60.550.50.450.40 * PD=0.5 PD=0.7 PD=0.9 0.5 0.6 0.8 0.7 PD 1 (a) PD 对 defender 选择防御的影响 0.9 0.1 0.3 0.2 0.5 (b) PF 对 defender 选择防御的影响 0.4 PF 图3 选择防御的影响 图 2( a) 说明了随着 PD 增大, attacker 选 择攻击 的概率 会 变小; ( b) 说明 了 随着 PF 增 大, attacker 选择 攻 击的 概率 会 变 大。 图 3( a) 说明了随着 PD 增大, defender 选 择防御 的概率 会 变小; ( b) 说明了 defend 选择防御策略的概率与 PF 无关。 b) 测试 Catt / ω, Cips / ω对 APM 攻击预测 结果的影响。Catt / ω表 示 attacker 攻 击 代 价 和 攻 击 获 益 的 比 值。 Cips / ω表 示 defender防御代价和不防御时损失的比值。给 定与收益函 数相 关的初始参 数 值: ω= 100, β= 120, μ= 80, PD = 0. 7, PF = 0. 1。其中: Catt = Cips = { 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140} 。实验结果如图 4 所示。 defender 选择防御的概率 attacker 选择攻击的概率 0.7 0.6 0.5 0.4 0.3 0.2 0.1 000.20.40.60.8 11.21.4 Catt /棕 (a) Catt/棕 对 attacker尧defender 选择的影响 10.90.80.70.60.50.40.30.20.10 defender 选择防御的概率 attacker 选择攻击的 概率 00.20.40.60.8 11.21.4 Cips /棕 (b) Cips /棕 对 attacker尧defender 选择的影响 图4 Catt /棕 和 Cips /棕对选择的影响 图 4( a) 说明了当 Catt/ ω≤1 时, 随着 Catt / ω增大, defender 选择防御的概 率会 变小, 而 attacker 选 择攻 击的 概 率与 Catt/ ω 无关; 当 Catt / ω≥1 时, attacker 不再选 择攻击, 且 defender 不 再 选择防御。( b) 说明 了 当 Cips / ω≤1 时, 随 着 Cips / ω增 大, at- tacker 选择攻击的概率会 变大, 而 defender 选 择防 御的 概率 与 Cips / ω无关; 当 Cips / ω≥1 时, defender 不再选择防御, 而attacker 会一直选择攻 击。本 实验 中 在 Cips / ω≥0. 56 以 后, attacker会 一直选择攻击。因此, 由 图 2 ～4 可知: a) 利 用 APM 不 仅能 预 测 attacker 选择攻击的概率还能预测 defender 应选择防御的 概 率。b) 作为 defender, 应通过提高 IPS 的检测率 P D 和减 少 IPS 的误报率 P F, 以减少攻 击事件 的发 生和 减少 防御 攻击 所花 费 的代价。c) 无论是 defender, 还 是 attacker, 都 能根 据对 方的 情 况作出最理 性的 选 择。这也 解 释了 为什 么 当 attacker 攻 击 代 价增大时, 攻击的概率会不变而防御的概率会变小的现象。这 是由于在 APM 攻击预测模型 中, 选择攻 击或者 选择防 御是 依 赖于对方而不是自身的情况。另外, 当 Catt / ω和 Cips / ω的值 超 过 1 时, 从图 4 中可以看出, APM 能理 性地预测出 defender 和 attacker 各自的最优选择。 3 结束语 本文 提 出 了 基 于 静 态 贝 叶 斯 博 弈 的 攻 击 预 测 模 型 ( APM) , 并在实验中验证了该模型 的有效 性。实验表 明, 该 模 型具有以下优点: a) APM 能理性预测出 attacker 选择攻击的 概 率和 defender 选择防御的概率; b) 通 过 APM 分析 入侵 检测 率 P D、误报率 PF、Catt/ ω、Cips /ω对攻 击 预测 结果 的 影响, 使 得 安 全管理员能根据自身 IPS 的性能 和网络 情况 更好 地进 行有 针 对性的安全配置, 从而达到主动防御的目的。 另外, 本文提出的攻击预测模型还需要在某些方面作进一 步 的研 究, 包 括: a) 将 现 有两 人 博弈 模型 扩 展到 N 人博 弈 模 型; b) ψ的取值应能动态反映真实网络中恶意主机节点的概 率 的变化; c) 考虑正 常访 问网 络的 主 机节 点由 于 自私 而争 用 网 络资源, 造成对网络的被动攻击的因素。 参考文献: [ 1] EBERLEIN L. A network security monitor[ EB/ OL] . [ 1990 ] . ht- [ 2] tp: / / seclab. cs. ucdavis. edu/ papers / pdfs / th-gd-90 . pdf. SYVERSON P F. A different look at secure distributed computation [ C] / / Proc of the IEEE Computer Security Foundations Workshop. [ S. l. ] : IEEE Computer Society, 1997: 109-115. [ 3] LYE K, WING J M. Game strategies in network security[ C] / / Proc of the IEEE Computer Security Foundation Workshop. [ S. l. ] : IEEE, 2002: 159-163. [ 4] XU J, LEE W. Sustaining availability of Web services under distribu- ted denial of service attacks[ J] . IEEE Trans Comput , 2003 , 4( 2) : 195- 208 . [ 5] ALPCAN T, BASAR T. A game theoretic approach to decision and analysis in network intrusion detection[ C] / / Proc of the 42nd IEEE Conference. [ S. l. ] : IEEE, 2003 : 2595 -2600. [ 6] ALPCAN T, BASAR T. A game theoretic analysis of intrusion detec- tion in access control systems [ C] / / Proc of the 43rd IEEE Confe- rence. [ S. l. ] : IEEE, 2004: 1568-1573. [ 7] LIU Peng, WAN Yu-zang, YU Meng. Incentive-based modeling and inference of attacker Intent, objectives, and strategies[ C] / / Proc of the 10th ACM Computer and Communications Security Conference ( CCS ’03 ) . New York: ACM Press, 2003: 179-189. [ 8] 张 维 迎. 博 弈 论 与 信 息 经 济 学 [ M] . 上 海: 上 海 人 民 出 版 社 , 2002: 300- 355. [ 9] McKELVEY R D, McLENNAN A M, TUROCY T L. Gambit: software [ 2004 ] . http: / / econweb. tamu. tools for game theory [ EB/ OL] . edu/ gambit/ .