基于博弈理论的入侵检测与响应模型综述

一、整体介绍

1.1 研究背景

当前网络规模急剧增加，各类入侵过程也逐渐向复杂化，多样化和分布式的趋势发展，利用传统的入侵检测与响应技术对各类安全事件进行检测发现、查处、响应变得日益困难。因此，需要用新的视角去理解入侵检测与响应模型。博弈论提供了一个自然的框架捕获攻击者和防御者的交互，提供了一种定量的方法评估系统的安全性。从博弈论的角度理解入侵检测与响应模型，不仅需要识别出复杂的攻击模式和攻击场景，还需要在攻击检测之后进行自动化响应，形成检测，发现，预警，响应的闭环防御体系。

1.2 相关研究现状

2009年，国内第一篇将博弈论应用于网络安全领域的论文发表在计算机学报上，提出了基于博弈论的防御图模型，针对不同类型的攻击产生对应的响应[1]。厦门大学肖亮教授在相关的学术会议上也发表了论文[2]，描述了云存储中的动态安全资源分配。王震等将博弈论与攻击图相结合[3]，研究了基于Stackelberg攻防博弈的网络系统安全控制优化。

国外的研究者对相关领域开始的比较早，不仅仅是将博弈论应用在入侵检测中，也同样将博弈论应用在安全领域。主要分成两个派系：Milind Tambe和Vicki Bier。以南加州大学Milind Tambe教授为代表的计算博弈论方向，开山作是文献[4]。该流派目前代表人物有安波教授(南洋理工)及其课题组等。以威斯康辛-麦迪逊大学Vicki Bier教授为代表的是基于博弈与决策的风险分析方向，代表作之一为她的学生的一篇论文[5]。该流派目前代表人物有该教授本人，Jun Zhuang教授(纽约大学buffalo校区)及其课题组，David Banks(杜克大学)等等。

纽约大学的华人研究者ZhuQuanYan，开创了该领域的学术会议GameSec，并发表了博弈论应用在网络安全领域的综述性文章[6]。南巴黎电信的Christophe Kiennert[7]研究员提出将博弈论应用在入侵检测与入侵响应优化中。

1.3 研究框架

我们按照网络攻击的先后顺序将博弈论应用在入侵检测和响应分成三个阶段和一个整体的架构设计。

第一阶段：攻击前的网络安全加固。

这个阶段的研究成果主要是基于Stackelberg博弈模型的网络安全加固。

第二阶段：攻击中，IDS配置与效率优化。

这个阶段主要有三个方面：优化基于网络的入侵检测的资源配置;优化NIDS的规则库和参数;基于生成对抗模型优化异常检测效率。

第三个阶段：攻击后的自动化响应。

整体架构设计主要是基于合作博弈的分布式入侵检测架构优化。

1.4 研究意义

(1)博弈论应用在网络安全领域之前，入侵检测都是通过提高检测效率来优化的，而博弈论提供了一个自然的框架去捕获攻击者和防御者的交互，提供一个定量的方法去评估系统的安全性，使研究者从策略和决策的视角理解网络攻击与防御。

(2)与标准的安全性定义有所不同，博弈理论采用不同的视角看待安全：安全不是没有威胁，而是攻击系统比不攻击系统更加昂贵，因此，可以建立激励机制来鼓励良好的行为而防止恶意的行为发生。

(3)传统的安全检测假定系统是静态的，但是复杂的网络环境是动态变化，借助动态博弈可以确保系统在动态环境中也是安全的。

(4)一般来说，保证动态系统稳定运行，需要反馈机制，而借助博弈论的入侵检测与响应模型，可以构成检测，发现，预警，响应闭环防御体系，可以让入侵防御的在不同环节循环，保证系统动态稳定。

二、相关基础知识

2.1 入侵检测

入侵检测是[8]对企图入侵，正在进行的入侵或者已经发生的入侵进行识别的过程。它

在不影响网络性能的情况下能对网络进行监控，收集计算机网络或系统中的关键信息，并对其进行分析，从中发现是否有违反安全策略的行为和被攻击的迹象。

按照不同的分类标准，入侵检测可以分成不同的类别：

(1)按照检测源的不同，可以分为基于网络的入侵检测(NIDS)，基于主机的入侵检测(HIDS)，混合入侵检测(Hybrid IDS)。

(2)按照检测方法进行分类，可以分为误用检测，异常检测和基于规范的检测。

(3)按照是否能响应，分为入侵检测(IDS)和入侵防御(IPS)/入侵响应(IRS)。

2.1.1 误用检测

误用检测又称为特征检测，它将已知的入侵活动用一种模式来表示，形成网络攻击特征库(或称为网络攻击规则库)。

目前商用的IDS基本上是采用误用检测方法。基于误用检测方法的入侵检测技术，其误报率低，漏报率高。它能够准确地识别已知的攻击，并可以详细地报告出网络攻击类型。但是，该方法对新的入侵方法无能为力，需要将新的入侵模式不断加入特征库，才能提高其识别新网络攻击的能力。

2.1.2异常检测

异常检测可以称为无监督或者弱监督下的非平衡数据下的多分类的问题。且往往异常点(不平衡数据中较少的部分)对我们更为重要。相对于误用检测，该方法检测的结果的漏报率低，误报率高，能检测出一些未知攻击。其实现的难点在于如何避免将正常活动识别为入侵活动和遗漏正在发生的入侵活动。

2.1.3 基于规范的检测

基于规范的检测描述了程序的期望行为，如果用户的行为与安全规范的描述不同，那么可以断定产生了攻击。因为它描述的是程序的期望行为，所以当一个合法的用户做了与常规不一样的事(是合法的)，它不会产生虚警，它还能识别已知攻击与未知攻击[9-10]。

2.2 入侵检测的整合

入侵检测技术的主要挑战是分析IDS发出的警报，发生入侵时，选择对策所需要的时间应该尽可能短。所以现在大型网络下入侵检测系统常常被集成到SIEM[11]系统中，系统架构图如图1所示。该架构一般分成5层，从下至上包括数据采集层，数据归一化层，数据存储层，数据分析层和数据可视化层，其中数据分析层的核心是关联引擎;数据可视化层用于可视化展示，供安全分析人员使用。

图1 SIEM系统架构

2.3 博弈论

按照不同的分类条件，博弈论可以分成不同的类别[12]。

(1)按照博弈论之间是否存在约束协议，可分为合作博弈和非合作博弈，两者主要区别在于相互作用的当事人之间是否存在具有约束力的协议。

(2)按照博弈双方互相了解的程度，可分为完全信息博弈和不完全信息博弈。完全信息博弈是指在博弈过程中，每一位参与人对其他参与人的特征、策略空间及收益函数有准确的信息。而在不完全信息博弈中，每个参与者并不清楚有关博弈的一些信息。

(3)按照行为的时间序列，分为静态博弈和动态博弈。静态博弈是指在博弈中，参与人同时选择或虽非同时选择但后行动者并不知道先行动者采取了什么具体行动;动态博弈是指在博弈中，参与人的行动有先后顺序，且后行动者能够观察到先行动者所选择的行动。

(4)按照博弈的表现形式分为战略型博弈和展开型博弈。

三、研究方法

3.1 攻击前的网络安全加固

网络安全加固的核心模型是Stackelberg博弈模型[14]。Stackelberg安全博弈最开始应用于现实生活的安全领域，用于安全资源调度，后来被运用在网络安全资源调度之上。例如，美国的洛杉矶国际机场应用在警力资源调度，空中警察调度，城市轨道交通系统安全调度等实际应用中。我们的模型是建立在攻击图上的Stackelberg博弈模型：将网络攻击场景建模为攻击图上的Stackelberg博弈，防御者是先行者，攻击者是跟随者，攻击者的目标是从攻击图中找到一条最短代价的路径，防御者的目的是用有限的资源在路径上设置障碍阻止攻击者。博弈模型建好之后，最重要的就是求解纳什均衡。

目前，针对Stackelberg纳什均衡主要列举如下基本求解算法，文献[13]对三种算法进行了总结。

(1)MultiLPs算法[15]

该算法是研究者于2006年提出，是针对标准型的Stackelberg博弈求解的最基本多项式时间的算法，也可以用来求解贝叶斯Stackelberg博弈。

(2)DOBSS 算法[16]

因为不同类型的追随者之间是相互独立的，所以追随者的纯策略产生组合爆炸。而DOBSS算法可以解决这个问题，DOBSS算法是第一个成功的应用在实际系统上的算法，它利用跟随者的类型相互独立的特点将这一问题进行降解，从而将其转化成求解一个混合整数规划的问题(MILP)。

(3)ERASER 算法[17]

该算法直接对紧凑型的安全博弈进行求解，可以避免枚举指数级的防御者的纯策略。

3.2 IDS优化

3.2.1优化基于网络的IDS的资源分配

(1)NIDS如果对每个数据包都检查，需要很高的处理资源。文献[20]中研究者开发了一种网络分组采样策略，在总资源预算一定的情况下，通过合适的采样率采样不同路径的数据包，作者定义了一个简单的双人静态零和博弈，求解出预算一定的情况下每一条链路的最优采样率。

(2)基于规则的NIDS如Snort，一般会存储对于已知的网络攻击的特征库，并需要配置大量的攻击检测库和一些系统参数。比如Snort有51个攻击类别以及将近10000个特征规则，所以获得最佳的IDS配置以有效检测攻击绝非易事，配置规则库是在系统性能和安全性能之间找到平衡，文献[21]建立一个动态的随机博弈对于不同的系统状态去设计最优的IDS配置，使用动态和迭代的方式配置IDS，是平衡安全开销和系统性能的方法。

(3)从博弈论的角度来看，生成对抗网络是一个二人零和博弈，生成器和判别器是博弈的两个参与者，生成器的策略是如何生成样本，判别器的策略则是如何判定样本的真实度。因此，策略组(“生成好样本”，“真假难辨”)是一个纳什均衡，在这种情况下，生成器和判别都无法单方面改变策略而得到额外的好处。

利用生成对抗网络进行异常检测主要存在以下两方面问题：

(1)由于对异常数据进行正向检测的效果不理想，研究者往往逆向研究，基于生成对抗网络的无监督多元异常检测，利用重构误差进行异常检测。

(2)因借助训练标签样本较少，从而影响有监督分类模型的检测效果的问题。文献[22]借助生成对抗网络对抗交互训练的思想，在训练的阶段引入了生成模型，由生成模型不断生成样本，扩充原有标签样本集，可辅助入侵检测模型分类，提高了模型检测准确率，提升了执行多分类任务时对入侵行为的识别能力。

3.3 攻击自动化响应

攻击之后的自动化选择，主要涉及IPS和IRS，研究工作[23]主要是一旦发现攻击就会触发最佳的防御策略，无需依靠管理员的手动干预，该项工作主要是优化系统响应，而不是IDS性能，因此假定总能够成功检测到攻击。

3.4 基于合作博弈的分布式入侵检测

单个入侵检测系统难以检测所有的攻击,与传统的同类产品相比，入侵检测设备之间的协作可以获得更高的检测精度和成本效率。文献[24-26]提出协作式入侵检测网络的系统架构，其中值得信赖的高效反馈聚合是关键组成部分,当IDS协作者的数量很大的时候，提出了一种固有的信任评价机制，并减少了IDS所需的通信开销以及实现令人满意的反馈聚合所需的计算资源和内存。

四、挑 战

(1)建立的博弈模型一般都是基于完全理性假设，假设攻击过程中攻击者和防御者都是完全理性的，有人尝试前景理论和量化反应模型，大多数的这些模型具有不同于理性人假设的表现，也使得优化问题增加了求解的难度。

(2)建立的模型一般假设博弈双方具有完全信息，网络中的信息对于攻防双方都是一致的，但是在实际中不可能。

(3)网络攻击数据集很难构建，小规模的数据集可以使用真实的场景，但是大规模的网络数据集无法实现。

(4)博弈模型的抽象程度较高，很难应用在实际生产中。

五、研究展望

基于博弈论的入侵检测与响应模型仍处于高速发展的过程中，目前，我觉得比较有前景的研究方向是以下两点。

(1)基于历史数据的学习

攻击者和防御者因重复且频繁的交流，不断积累数据，这成为了沟通博弈与机器学习领域的一个研究契机。研究人员能够在既往收集的数据中学习得到博弈模型，现有的安全领域收益都是专家指定的，但是很多地方无法确定收益函数，而且数值会随着时间发生变化，进而影响博弈结果。如何在尽可能少的博弈回合之下学习攻击者的攻击偏好，进而进行有效的保护，将会是一个很好的研究方向。值得注意，基于逆向强化学习得出收益函数可能是一个解决办法。

(2)基于合作博弈的分布式入侵检测

不同的传感器收集数据之后，还需要进行聚合关联，共同决策，达到合作博弈的帕累托最优。因此各个入侵检测之间需要有良好的通讯机制和良好的协商机制。一个良好的入侵检测系统应该是一个高级的多智能系统，每个采集的传感器都是一个智能体，如基于误用检测和异常检测的IDS，日志分析等传感器都是智能体，全部的传感器智能体共同优化一个目标，产生高效的告警信息，并自动化响应一部分告警，通过人机联动，反馈到传感器中，动态迭代优化系统，让整体的入侵检测系统处于学习进化中。

参考文献

[1] 姜伟，方滨兴，田志宏.基于攻防博弈模型的网络安全测 评和最优主动防御[J]. 计算机学报，2013，32 ( 4) : 818 - 827.

[2] Minghui Min, Liang Xiao, Caixia Xie, Mohammad Hajimirsadeghi, and Narayan B Mandayam. Defense against advanced persistent threats: A colonel blotto game approach. In 2017 IEEE international conference on

communications (ICC), pages 1{6. IEEE, 2017.

[3] 王震，段晨健，吴 铤. 基于 Stackelberg 攻防博弈的网络系统 安全控制机制优化研究. 信息安全学报，2019

[4] Praveen Paruchuri, Jonathan P Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, and Sarit Kraus. Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games. In Proceedings

of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, pages 895{902. International Foundation for Autonomous Agents and Multiagent Systems, 2008.

[5] Jun Zhuang and Vicki M Bier. Balancing terrorism and natural disasters|defensive strategy with endogenous attacker effort. Operations Research, 55(5):976{991, 2007.

[6]Quanyan Zhu and Stefan Rass. Game theory meets network security: A tutorial. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 2163{2165, 2018.

[7]Kiennert C, Ismail Z, Debar H, et al. A survey on game-theoretic approaches for intrusion detection and response optimization[J]. ACM Computing Surveys (CSUR), 2018, 51(5): 1-31.

[8] Denning D E. An intrusion-delection model. IEEE Transactions on Software Engineering, 1987, SE-13(2):

222-232.

[9] Sandeep Kumar. Classification and detection of computer intrusions. PhD thesis, PhD thesis, Purdue

University, 1995

[10] Phillip A Porras and Richard A Kemmerer. Penetration state transition analysis: A rule-based intrusion

detection approach. In Computer Security Applications Conference, 1992. Proceedings., Eighth Annual,

pages 220–229. IEEE, 1992

[11] IBM QRadar SIEM. https://www.ibm.com/us-en/marketplace/ibm-qradar-siem.

[12] Osborne M J, Rubinstein A. A course in game theory[M]. MIT press, 1994.

[13] 王震，袁勇，安波。安全博弈论研究综述 ，指挥自动化学报，2015

[14] Milind Tambe. Security and game theory: algorithms, deployed systems,

lessons learned. Cambridge university press, 2011.

[15] Conitzer V, Sandholm T. Computing the optimal strategy to commit to[C]// Proceedings of the 7th

ACM Conference on Electronic Commerce (EC’06). Ann Arbor, Michigan, USA, 2006: 82?90.

[16] Paruchuri P, Pearce J P. Playing games for security: an e–cient exact algorithm for solving bayesian

stackelberg games[C]// Proceedings of the 7th International Joint Conference on Autonomous Agents and

Multiagent Systems (AAMAS’08). Estoril, Portugal, 2008: 895902.

[17] Pita J, Jain M. Using game theory for los angeles airport security[J]. AI Magazine, 2009, 30(1): 43?57

[18] 杜威, 丁世飞. 多智能体强化学习综述[J]. 计算机科学, 2019, 46(8): 1-8.

[19] Lowe R, Wu Y, Tamar A, et al. Multi-agent actor-critic for mixed cooperative-competitive environments[C]//Advances in neural information processing systems. 2017: 6379-6390.

[20] Murali Kodialam and TV Lakshman. Detecting network intrusions via sampling: a game theoretic approach. In IEEE INFOCOM 2003. Twentysecond Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No. 03CH37428), volume 3, pages 1880{1889.IEEE, 2003

[21] Quanyan Zhu and Tamer Ba?sar. Dynamic policy-based ids configuration. In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 8600{8605. IEEE, 2009.

[22] An Enhancing Framework for Botnet Detection using Generative Adversarial Networks, 2018 International Conference on Artificial Intelligence and Big Data. 2018.

[23] Yi Luo, Ferenc Szidarovszky, Youssif Al-Nashif, and Salim Hariri. A game theory based risk and impact analysis method for intrusion defense systems. In 2009 IEEE/ACS International Conference on Computer Systems and Applications, pages 975{982. IEEE, 2009.

[24] Carol J Fung and Quanyan Zhu. Facid: A trust-based collaborative decision framework for intrusion detection networks. Ad Hoc Networks, 53:17{31, 2016.

[25] Quanyan Zhu, Carol Fung, Raouf Boutaba, and Tamer Basar. A gametheoretical approach to incentive design in collaborative intrusion detection networks. In 2009 International Conference on Game Theory for Networks, pages 384{392. IEEE, 2009.

[26] Quanyan Zhu, Carol Fung, Raouf Boutaba, and Tamer Basar. Guidex:A game-theoretic incentive-based mechanism for intrusion detection networks. IEEE Journal on Selected Areas in Communications, 30(11):2220{

2230, 2012.