文献标识码:A
DOI:10.16157/j.issn.0258-7998.2015.12.033
中文引用格式:钱震,蔚承建,王开,等. 基于贝叶斯Stackelberg博弈的Web安全问题研究[J].电子技术应用,2015,41(12):124-128.
英文引用格式:Qian Zhen,Wei Chengjian,Wang Kai,et al. Web security research base on Bayesian Stackelberg Game[J].Application of Electronic Technique,2015,41(12):124-128.
0 引言
近年来,许多研究都集中于博弈论在资源分配和调度方面的问题[1],但博弈论不仅适合应用在这些问题上,也可以应用在Web安全攻防问题上。Stackelberg博弈应用在Web安全问题中时,领导者是信息安全人员,而追随者是黑客。随着安全技术的提升,有多种先进的策略和技术可以提供给攻击者和防御者。本文中要解决问题是寻找稳定的Stackelberg博弈用于Web应用安全中领导者的最优策略。本文提供了Stackelberg安全博弈和贝叶斯Stackelberg安全博弈的详细描述,对其在Web安全领域的适用性进行了讨论,并给出了实验的结果。
不同的研究者探索用博弈论的方法来建立安全问题的适用性[1],在过去的几年有了显著的结果和实际运用。在文献[2]中,提出了ARMOR框架,能够有效地在洛杉矶国际机场内设置检查点和警犬巡逻维护安全。在文献[3-4]中,博弈论被用于联邦空警在商业航班中的安全护航,以及在纽约地铁中的逃票检查。博弈论也已经被用在建立信息安全领域的模型中,文献[5]用完全信息的静态博弈来建立信息安全的攻防模型。在文献[6]中,利用零和随机博弈对攻击者和系统管理员的行为进行建模,其中网络被表示为一组独立的节点来对应安全资产和漏洞。在文献[7-8]中,描述了在信息安全问题中运用博弈论的方法找到最佳的策略,提出了相关决策的惩罚参数。在文献[9]中,提出了基于马尔科夫决策过程的博弈模型对漏洞威胁进行风险评估。
本文将会探讨在Stackelberg博弈中防守者和攻击者形成最优稳定局面可能性以及在Web安全领域的应用。本文的目标是找到在Web安全问题中面对攻击时最有效的防守策略。
1 Stackelberg博弈
Stackelberg博弈是非合作、有先后次序的决策博弈。是由两个局中人领导者和追随者参与的一种博弈论类型。被称为领导者(leader)的参与者首先发布一个混合策略,另一个被称为追随者(follow)的参与者在领导者的策略下优化自己的性能或收益,回应一个纯策略。两个参与者都想其收益最大化。每个参与者有一个可能的行动集合,每个参与者可以从集合中选择形成策略,这个策略是参与者可能采取行动的概率分布,可以表示参与者选择这个行动的可能性。参与者只能选择一个行动的策略就叫做“纯策略”。而在混合策略中每个行动可以被选择的概率是0≤p<1。由于本文侧重于Stackelberg博弈在安全领域中的应用,相关术语“领导者”对应的“防守者”及“追随者”对应的“攻击者”会被交替使用。
1.1 贝叶斯Stackelberg博弈
贝叶斯Stackelberg博弈将Stackelberg博弈扩展成允许有多个类型的追随者,每种类型都有其自己的收益矩阵,方便建立有多个类型攻击者的模型。在贝叶斯Stackelberg博弈中,追随者的类型集合表示为{1,2,…,I},其中每种类型1≤λ≤I都有一个先验概率Pλ来表示其出现的可能性。领导者在知道每种类型追随者先验概率分布的情况下承诺一个混合策略,但是领导者不知道面对的追着者的具体类型。而追随者会根据领导者的策略回应一个最佳的策略。对于每个追随者类型,领导者和追随者对应的收益矩阵分别为Uλ和Vλ。
1.2 稳定Stackelberg均衡条件
为了计算领导者的最优策略,则需要先定义稳定Stackelberg均衡[10]。首先需要定义一组向量函数g=(g1,g2,…,gI),其中每个gλ表示领导者的混合策略到λ类型追随者的纯策略的映射关系,那么g(x)就是追随者回应x策略的一组向量,可以表示为g(x)=(g1(x),…,gI(x))。
定义1:对于给定一个收益矩阵为(U1,V1),…,(UI,VI)类型的概率分布为p的贝叶斯Stackelberg博弈,一组策略集(x,g)当且仅当满以下条件时能构成一个稳定Stackelberg均衡。
其中的所有j都是(2)中追随者的最优反应策略.
2 DOBSS算法
在以前的研究中,有很多方法可以用来解决Stackelberg安全博弈问题[11],DOBSS算法是其中一个能够有效计算出在贝叶斯Stackelberg博弈中领导者的最优混合策略。采用这个方法有3个优势,首先这个方法不需要通过海萨尼转换转化为正则形式的博弈来表示贝叶斯博弈;第二,该方法仅需计算一个混合整数线性规划问题,而不是计算一组线性规划问题的集合;第三,它直接搜索了领导者的最优策略,而不是Nash均衡,从而使其能够找到高回报的Stackelberg均衡策略(利用了领导者的优势)。
首先需要定义一个基本形式来解决贝叶斯Stackelberg博弈问题,这是一个混合整数二次规划问题(MIQP),其次会将其转化为一个混合整数线性规划的问题(MILP)。我们用x表示领导者的策略,其由一组领导者的纯策略向量组成。xi的值表示纯策略i在混合策略中的比例。同样,用q表示追随者策略的向量。我们用X和Q表示领导者和追随者各自纯策略的集合。M则是表示一个无穷大的正数。收益矩阵R和C的定义是:当领导者选择纯策略i,追随者选纯策略j,Rij是领导者的收益,Cij是追随者的收益。
领导者的MIQP问题定义为:
为了扩展这个Stackelberg模型来处理多个追随者类型,我们遵循贝叶斯方法先假设存在一个先验概率pl来表示追随者类型l出现概率,用L表示追随者类型的集合。在这个例子中,ql表示追随者类型l∈L的策略向量。同样的,领导者和追随者类型为l的收益矩阵用矩阵Rl和Cl表示。那么领导者需要解决问题变为:
这是我们可以在IBM的cplex框架下实施的最终形式,将会在第4章讨论。
3 Stackelberg博弈在Web安全上的应用
3.1 Stackelberg博弈在Web安全上的适用性探讨
Stackelberg博弈在Web安全应用问题中非常有用。在这种情况下,领导者可以是信息安全人员或者组织,追随者可以是黑客或者有组织的犯罪集团。领导者首先通过部署不同的信息安全策略来保护其资源,然后追随者可以通过探测网络确定其状态,用纯策略回应领导者的策略。不同类型的追随者可以被解释为不同类型的攻击,根据以前的研究和统计[12],安全部门可以构建攻击技术分布比例,而攻击者可以扫描网络的当前状态,查找漏洞,实施最佳策略。
安全部门可以被当做一个领导者,原因如下:
(1)在大多数情况下,Web应用的安全策略是对外公开的。
(2)Web应用的安全手段和措施都是标准的和众所周知的。黑客可以通过探测网络来推断安全部署。而且这种信息经常也可以从安全供应商得到。
(3)每个安全措施都有自己的弱点和不足,这给了攻击者有机会选择最好的方式来攻击。
这些情况都可以说明Stackelberg策略可用在Web安全领域。
3.2 Web应用中的攻击策略和修补策略
为了具体说明将Stackelberg博弈策略运用在Web安全应用中,本文建立了在Web安全应用中的攻防模型。在Web应用安全问题中,攻击者(跟随者)试图利用一些漏洞来执行未经授权的操作,而安全人员(领导者)试图解决这些错误。根据研究[13],Web应用中最广泛的追随者的攻击策略和领导者的修补策略见表1,这些攻击手段和防御手段分别对应了追随者的行动集合和领导者的行动集合。
3.3 Web安全中领导者和追随者的收益计算
将Stackelberg博弈应用于Web应用的安全问题上,其核心问题是需要以一种有意义的方式填充领导者和追随者的收益矩阵。在研究[13]中,OWASP团队的文档数据由7家专业的应用安全公司提供。数据涵盖了来自上百家组织上千个应用,超过500 000个漏洞。根据这些数据,同时考虑攻击向量的可利用性、安全漏洞的普遍性和可检测性以及技术影响的严重性程度等多方面因素,给出了Web漏洞每个风险因素的风险值。在研究[13]的基础上,本文给出了Web安全应用中领导者修补策略的收益(表2)和追随者攻击策略的收益(表3)。
根据收益表格,当追随者发起攻击时给出定义:
(1)如果修补手段对攻击手段是有效的,那么领导者的收益为领导者行动的影响减去领导者修补手段的成本,追随者的收益是其攻击手段的成本。
(2)如果修补手段对攻击手段是无效的,那么领导者的收益是负的,其值为领导者修补手段的成本减去追随者攻击手段的影响,追随者的收益为追随者行动的影响减去追随者攻击手段的成本。
(3)追随者同样可以选择不进行攻击,那么领导者的收益为其修补手段的成本,追随者的收益为0,由此可以得到收益表格来定义收益矩阵(表4)。
4 实验结果
在本文实验中使用了IBM ILOG CPLEX软件来处理寻找Stackelberg博弈领导者的最优策略时面临的线性规划问题,IBM ILOG CPLEX是一种非常强大的线性规划处理工具,支持各种编程语言,在这个例子中,我们使用JAVA语言编程实现。
在这个例子中,定义了两种类型的追随者,它们的攻击手段相同时具有相同的收益值,但是有不同的行动集合。其中A类型的追随者可以用第3章表1里攻击策略集合中的任何纯策略,但是不可以不进攻(选择NA策略)。而B类型的追随者不可以使用SQLi和ITIP策略。A类型的追随者先验概率为0.7,B类型的追随者先验概率为0.3.
得到程序的结果如下:
优化状态 : Optimal
领导者最大预期效用 : -0.702 052 238 805 969 8
A类型追随者最大预期效益: 1.357 142 857 142 857 2
B类型追随者最大预期效益: 1.283 582 089 552 239
追随者的追策略:
A的纯策略: SQLi
B的纯策略: XSS
领导者的混合策略:
采取转义程序行动的概率: 0.390 485 074 626 865 66
采取会话安全的概率: 0.221 641 791 044 776 13
采取访问控制行动的概率: 0.0
采取跨站点请求伪造防卫行动的概率:0.166 231 343 283 582 05
采取环境安全行动的概率: 0.221 641 791 044 776 05
采取安全算法行动的概率: 0.0
上述结果与研究[13]中的Web应用安全的研究情况相符,SQLi和XSS是威胁性最大的攻击手段,因此基于所得到的结果,领导者可以使用如上的混合策略达到最优防守状态。
5 结论
博弈论在安全领域有着越来越重要的作用,近年来理论研究和生产实践使安全博弈分析有了长足的发展[14]。本文综述了贝叶斯Stackelberg博弈,在此基础上提出了一种贝叶斯Stackelberg博弈策略在Web安全中的应用的模型,综合考虑领导者和追随者的成本参数和收益参数,构建了更加全面的局中人收益函数。并利用文献[10]提出的DOBSS算法,计算贝叶斯Stackelberg博弈均衡的混合整数二次规划问题转化为混合整数线性规划问题,并且借助了高性能的线性规划问题处理工具CPLEX,给出实例计算了Web应用安全中防守者的最优混合策略。
下一阶段的工作将主要集中在两个方面。一方面,双方策略收益计算的精确性是一个亟待解决的问题,可以继续研究提高收益函数计算的精确性。另一方面,在某些情况下防御者的策略是随着威胁而变化的,可能加入信息收集工具,将领导者和追随者收益的数值进行实时更新,采用动态博弈的理论进行研究。
参考文献
[1] YOU X,SHI Y Z.A kind of network security behavior model based on game theory[C].Proceedings of the Fourth International Conference on Parallel and Distributed Computing,Applications and Technologies,2003.
[2] TAMBE M,JAIN M,PITA J A,et al.Game theory for security:key algorithmic principles,deployed systems,lessons learned[C].In 50th Annual Allerton Conference on Communication,Control,and Computing,2012.
[3] Yin Zhengyu,ALBERT X J,MATTHEW P J,et al.Sullivan:TRUSTS:Scheduling Randomized Patrols for Fare Inspection in Transit Systems[C].In Proceedings of Twenty-Fourth Conference on Innovative Applications of Artificial Intelligence(IAAI),Toronto,Canada,July 2012.
[4] KORZHYK D,YIN Z,KIEKINTVELD C,et al.Stackelberg vs nash in security games-an extended investigation of interchangeability,equivalence and Artificial Intelligence Research,2011(4).
[5] JORMAKKA J,MOLSA J V E.Modeling information warfare as a game[J].Journal of Information Warfare,2005,4(2).
[6] NGUYEN K C,ALPCAN T,BASAR T.Stochastic games for security in networks with independent nodes[J].Proceedings of International Conference on Game Theory for Networks(GameNets),2009.
[7] SUN W,KONG X,HE D,et al.Information security investment game with penalty parameter[C].The 3rd International Conference on Innovative Computing Information and Control,2008.
[8] SUN W,KONG X,HE D,et al.Information security problem research based on game theory[C].International Symposium on Publication Electronic Commerce and Security,2008.
[9] C.Xiaolin,T.Xiaobin,YONG Z,et al.A Markov game theory-based risk assessment model for network information systems[C].International conference on computer science and software engineering,2008.
[10] PARUCHURI P,PEARCE J P,MARECKI J,et al.Playing games with security:an efficient exact algorithm for bayesian stackelberg games[C].In Proc.of The 7th InternationalConference on Autonomous Agents and Multiagent Systems(AAMAS),2008.
[11] Manish Jain,Christopher Kiekintveld,Milind Tambe.Quality-bounded solutions for finite bayesian stackelberg games: scaling up[C].In The 10th Inter- national Conference on Autonomous Agents and Multiagent Systems-Volume 3,AAMAS’11,pages 997-1004,Richland,SC,2011.International Foundation for Autonomous Agents and Multiagent Systems.
[12] Kaspersky Lab website[DB/OL].http://www.kaspersky.com/.
[13] Jeff Williams,Dave Wichers.OWASP Top 10 2013[DB/OL].https://www.owasp.org/index.php/Top_10_2013,2013.
[14] CONITZER V,SANDHOLM T.Computing the optimal strategy to commit to.In EC,2006.