计 算 机 学 报
CHINESEJOURNALOFCOMPUTERSVol.32No.4
Apr.2009
基于攻防博弈模型的网络安全测评和
最优主动防御
姜 伟
1)(
1)
方滨兴
1),2)
田志宏
1),2)
张宏莉
1)
哈尔滨工业大学计算机网络信息安全研究中心 哈尔滨 150001)
2)
(中国科学院计算技术研究所 北京 100190)
摘 要 为了进行网络信息系统安全测评和主动防御,提出了网络防御图模型、攻防策略分类及其成本量化方法、网络攻防博弈模型和基于上述模型的最优主动防御选取算法.最后通过一个典型的网络实例分析了上述模型和算法在网络安全测评和最优主动防御中的应用.分析结果表明,提出的模型和方法是可行的、有效的.关键词 网络安全;防御图;成本量化;攻防博弈;最优主动防御中图法分类号TP309 DOI号:10.3724/SP.J.1016.2009.00817
EvaluatingNetworkSecurityandOptimalActiveDefenseBasedon
Attack-DefenseGameModel
JIANGWei FANGBin-Xing
1)
2)
1)1),2)
TIANZh-iHong
1),2)
ZHANGHong-Li
1)
(ComputerNetworkandInformationSecurityResearchCenter,HarbinInstituteofTechnology,Harbin 150001)
(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing 100190)
Abstract Toevaluatethesecurityofnetworkinformationsystemsandperformactivedefense,thispaperpresentssomemodelsincludingdefensegraphmodel,attack-defensetaxonomyandcostquantitativemethod,andAttack-DefenseGame(ADG)model.Algorithmsforselectingop-timizingactivedefensestrategybasedonthosemodelsareproposedandanalyzedinarepresenta-tivenetworkexample.Resultsindicatethatthemodelsandmethodsareeffectiveandefficient.Keywords
internetsecurity;defensegraph;quantitativecostanalysis;attack-defensegame
model;optimalactivedefense
此时已为时过晚,可能已经造成严重的损失,缺乏主
1 引 言
现有的网络安全技术依赖于防火墙、入侵检测和反病毒软件等,属于静态的、片面的被动安全防御,强调以攻击为中心,检测到攻击后才有所响应,
动性和对攻击的预测能力.为了保证网络系统的安
全性和健壮性,世界各国政府、学术界和企业界都正在寻求新的防御技术.在报告¹中作者提出:/主动实时防护模型与技术的战略目标是通过态势感知,风险评估、安全检测等手段对当前网络安全态势进
收稿日期:2008-12-08;最终修改稿收到日期:2009-02-12.本课题得到国家/九七三0重点基础研究发展规划项目基金(2007CB311100)、国家/八六三0高技术研究发展计划项目基金(2007AA01Z442,2007AA01Z406,2009AA012437)资助.姜 伟,男,1979年生,博士研究生,主要研究方向为网络与信息安全、网络攻防等.E-mail:jiangwei@pact518.hit.edu.cn.方滨兴,男,1960年生,教授,博士生导师,中国工程院院士,主要研究领域为计算机体系结构、信息安全和计算机网络等.田志宏,男,1978年生,博士,讲师,主要研究方向为计算机网络与信息安全等.张宏莉,女,1973年生,教授,博士生导师,主要研究领域为网络信息安全、网络测量.
¹
方滨兴.解读信息安全创新突破点.http://www.cert.org.cn/articles/news/common/2007051823317.shtml,2008
818
计 算 机 学 报2009年
行判断,并依据判断结果实施网络主动防御的主动安全防护体系.0
信息安全测评工作是保障网络和信息系统安全的基础.目前,基于网络安全测评的主动安全防御技术渐渐成为主流,这是因为与传统的被动防御技术相比,基于安全测评的主动防御技术能够帮助用户预先识别网络系统脆弱性以及所面临的潜在的安全威胁,根据安全需求来选取符合最优成本效应的主动安全防御措施和策略,从而提前避免危险事件的发生.
理想的防御系统应该对所有的弱点或攻击行为都做出防护,但是从组织资源限制等实际情况考虑,/不惜一切代价0的防御显然是不合理的,必须考虑/适度安全0的概念,即考虑信息安全的风险和投入之间寻求一种均衡,应当利用有限的资源做出最合理的决策.防御成本有效性是安全管理员考虑的重要因素.信息安全中攻防对抗的本质可以抽象为攻防双方的策略依存性,防御者所采取的防御策略是否有效,不应该只取决于其自身的行为,还应取决于攻击者和防御系统的策略.所以可以利用博弈论[3]来研究攻防矛盾及其最优防御决策等信息安全攻防对抗难题.Hamilton[4]指出,博弈论将在网络攻防对抗领域发挥重要作用,是未来信息安全很有前途的研究方向.
本文的主要贡献如下:(1)本文考虑了针对攻击的防御策略的成本有效性,对传统攻击图进行了改进和丰富,提出了用于网络系统安全评估的防御图模型,完整地给出了攻防策略分类及其成本/收益分析;(2)本文把网络攻防双方建模为二人非合作博弈模型,并详细地给出了攻防博弈模型的形式化描述.用此模型来研究网络攻防双方的矛盾冲突和最优决策;(3)本文提出基于上述模型的最优主动防御策略选取算法,帮助防御者采取最优防御策略进行主动防御.
本文首先介绍相关研究工作,然后给出用于网络系统安全评估的防御图模型和攻防策略分类及其代价量化模型.从而引出网络攻防博弈模型的形式化定义,接着描述基于上述模型的最优主动防御策略选取算法.以上几个部分是相互关联的整体,防御图模型用于帮助用户预先识别网络系统脆弱性以及所面临的安全威胁,从而可以确定攻防策略.攻防策略分类及其代价量化用于分析攻防双方的策略收益.攻防策略和攻防策略收益是攻防博弈模型的重要元素,是基于攻防博弈模型的最优防御策略选取算法的数据源.利用攻防博弈模型预先选取和实施
[1-2]
最优的主动安全防御策略和措施,以避免危险和损失的发生,将被动防御变为主动防御.最后通过一个
实例对模型和方法的有效性进行分析验证.
2 相关研究工作
目前,有关网络安全测评、防御代价定量分析和主动防御的研究工作还处于起步阶段,尚未形成系统化的理论方法.主要的研究工作可概括为以下几个方面.
(1)网络脆弱性测评分析方面
冯登国等人[5]分析了信息安全风险评估国内外现状、评估体系模型、评估标准、评估方法、评估过程等,探讨了国内外测评体系,指出了目前信息安全风险评估需要解决的问题,展望了信息安全风险评估的发展前景.林闯等人介绍了网络安全性的随机模型与评价技术等方面的研究现状与进展,总结了网络安全性随机模型的若干研究方法和评价技术.在攻击树方面,Schneier提出了利用攻击树形式化、系统化地描述系统安全的方法,用来对单个弱点威胁建模.Moore详细地论述了以递归或渐进的方式来表达攻击变化的攻击树,能比较直观地反映攻击者实施攻击的步骤.在特权图方面,Dacier等人提出了特权图的概念,用来表达系统漏洞带来的攻击者对系统控制权限的变化,对系统的安全性进行评估.并且为弱点定义了一个度量来表达对此弱点进行攻击的成功可能性.Ortalo等人基于特权图思想提出了一种网络安全评估试验模型框架.在攻击图方面,Phillips和Swiler提出基于图的网
[11]
络弱点分析方法,这种方法可以检验一个成功攻击之后可能存在的所有结果,指出攻击者可以采取的那些具有较大成功概率的攻击路径,从而获得网络信息资产面临的不同风险.在模型检验方面,Ramakrishnan等人[12]首先提出将模型检测的方法应用在主机弱点综合分析方面,并实现了一个UNIX系统下的弱点分析工具.Ritchey和Ammann[13]把模型检测这种评估方法的应用扩展到了网络系统的评估中.张永铮等人提出了一个由风险网络和风险传播算法构成的风险传播模型,风险网络描述了网络系统的访问关系结构和风险态势,风险传播算法则给出了风险的运动规则.
(2)防御代价定量分析方面信息安全经济学近年来逐渐成为研究热点,并取得了一些研究成果.Lee在2002年首次提出了成本敏感模型作为响应决策的基础[14],根据响应成本
[1]
[10]
[9]
[8]
[7][6]
4期姜 伟等:基于攻防博弈模型的网络安全测评和最优主动防御
819
和攻击损失成本来决定是否响应.该响应决策思想比较简单.但其代价量化、代价分类和攻击分类的思想和方法对本文的研究内容有一定的借鉴意义.文献[15]中,给出了比较完整的攻防分类及其成本敏感模型,有效地应用于最优主动防御中.冯萍慧等人提出了脆弱性利用成本估算模型[16].通过对网络系统进行全面的脆弱性分析,并引入可靠性原理,从利用成本的角度对攻击代价进行估算,从而对网络系统的脆弱性进行量化评估,为管理员在权衡修复成本和效果时提供参考.
(3)博弈论在安全领域方面的应用
博弈论是一种基于事前的决策分析理论,由于在理解和建模冲突方面的价值,博弈论应用于安全相关问题的历史很久.开始于军事应用,1954年Haywood通过分析二战中的军事运作证明了博弈论的应用与军事领域的有效性.后来应用于政治科学[18].近来应用于信息战和计算机网络安全,1997年,Syverson提出应用随机博弈来对网络中的正常节点和恶意节点进行理性分析的思想.1997年Burke[20]提出利用不完全信息的重复博弈对信息战中的攻击者和防御者行为建模.2002年,Lye和Wing利用随机博弈形式分析了防护者和攻击者双方纳什均衡和各自的最优策略.2003年,Xu[22]基于完全信息的静态博弈设计和分析了DDoS防御系统,并使得该系统性能得到了优化.2003年,Liu提出了基于博弈理论的入侵意图、目标和策略推理模型,为这个领域的进一步发展做出了贡献.
本文借鉴了上述相关研究成果,但是也不同于上述研究工作.具体如下:首先,本文提出一种用于网络安全评估的防御图模型;其次,提出一种面向主动防御的攻防策略分类及其代价量化模型;最后,形式化定义攻防博弈模型并给出了基于上述模型的最优主动防御策略选取算法.
[23]
[21]
[19]
[17]
御(护)图(networkdefensegraph)模型[24].3.1 防御图定义
定义1. 防御图(也称防护图,DefenseGraph,简称DG)是一个6元组,DG=(S,S,S0,Ss,Sa,Sd),其中S是图的节点集,每一个节点表示一种网络安全状态,SAS@S,S是一种网络安全状态转换关系,S0AS,S0是初始网络安全状态集合,SsAS是攻击者目标状态集合,Sa是攻击者策略集合,Sd是防御者策略集合.
防御图是一个有向图,节点表示某种网络安全状态,表达了网络的资源属性和用户或攻击者对整个网络的访问能力.有向边表示攻击者利用各种原子攻击从一个网络安全状态到一个新的网络安全状态的转换关系和实现该转换的攻击成本/收益.这种状态变化可以表现为文件修改、系统配置改变、可执行程序运行、攻击者的特权提升等.Sa是攻击者从初始节点到目标节点所有的攻击路径的集合,即攻击策略集合.每一个攻击路径是一个或多个原子攻击的序列.对于每一个原子攻击或攻击策略都对应一系列防御策略,所有的防御策略组成Sd.如图1是某网络系统生成的防御图DG=(S,S,S0,Ss,Sa,Sd),S={A,B,C,D,E,F},用标有字母的圆圈表示.S0={A},Ss={F},用标有原子攻击名称和攻击收益的有向边表示状态转换关系,如a1:30表示原子攻击a1使得网络从状态A到状态B,攻击收益是30(单位是货币单位,可以用美元表示,下同),
dd
Sa={1,2,3}.Sd={sd1,s2,s3}用标有防御策略名称
和收益的方框表示每条攻击路径的防御策略.
3用于网络安全测评的防御图模型
网络攻击图(networkattackgraph)是由攻
击者在对目标网络进行攻击时可能采取的攻击路径组成的集合.攻击路径是攻击者进行攻击时所采取的攻击动作的序列.网络攻击图仅反映了攻击动作和系统状态变化情况,没有考虑各个攻击动作相应的防御策略及其攻防策略成本估计.为了评估网络信息系统安全和全面反映网络攻防策略及其代价情况,我们对攻击图模型进行了改进,并提出了网络防
[11]
图1 防御图实例
3.2 防御图的生成
防御图的建模和生成需要防火墙和路由器的配置文件、网络弱点扫描器、弱点数据库和攻防策略及其成本/收益量化模型等信息,具体模块图如图2所示.由于防御图的建模和生成不是本文讨论的重点,后续工作将重点讨论,这里不作详细介绍.
820
计 算 机 学 报2009年
图2 防御图生成模块图
3.3 攻防策略分类及其成本量化
网络攻防策略及其成本收益分析是防御图建模和最优网络安全防御的基础.本节重点介绍网络攻防策略分类及其成本/收益模型.由于目标资源的重要程度是随着网络环境的不同而变化,而且各类攻击的固有危害也是不尽相同.所以攻击造成的损失不仅与攻击的类型有关,而且与攻击的目标有关.为了能尽量精确地评估攻击损失代价,需要建立攻击分类模型和攻击对目标资源的损害模型,损失代价的量化可以结合攻击及其攻击目标进行计算.
攻防策略分类须考虑:(1)攻防策略分类空间大小直接影响后续攻防博弈模型分析复杂度;(2)攻防策略分类方法符合现有的防御系统.参考MIT林肯实验室攻击分类[27],给出一种面向主动防御的攻击/防御分类方法.攻击战略目的和攻击影
响对主动防御系统评估决策具有重要意义.所以攻击分类方法结合攻击战略目的和攻击影响作为分类依据,如表1所示.我们在总结各种防御方法分类基础之上,结合上述攻击分类和主动防御的时空特点,根据攻防博弈模型要求,将防御策略分为基于主机和基于网络的两大类,其中每一种防御分类包括若干个子类,具体如表2所示.
表1 攻击分类
分类RootUserDataDOSProbeOther
描述
获取管理员权限获取普通用户权限非授权访问或读写数据拒绝服务攻击扫描攻击其它
AL10532015*
[24,26]
表2 防御策略分类
分类
子类
关闭进程
删除文件
删除用户账号关闭服务
限制用户活动关闭主机重启主机
基于主机防御
安装软件升级补丁系统病毒扫描文件完整性检验安装系统升级补丁重新安装系统修改账号密码格式化硬盘备份系统其它
描述
关闭可疑进程或者所有进程删除被修改或者感染的文件删除可疑用户账号关闭易受攻击的软件
限制可疑用户的权限和活动关闭被攻击主机
重新启动被攻击主机
升级存在漏洞的软件到最新版本利用杀毒软件扫描系统
利用软件工具检验系统文件完整性升级系统到最新版本
安装被感染或者文件被修改的系统修改系统的所有账号密码
格式化硬盘去除所有恶意代码备份系统数据 *
OcostOL1OL1OL1OL2OL2OL2OL2OL2OL3OL3OL3OL3OL2OL3OL3*
4期姜 伟等:基于攻防博弈模型的网络安全测评和最优主动防御
821
(续 表)
分类
基于网络的防御
子类
隔离主机
丢弃可疑数据包断开网络TCP重置阻断端口阻断IP地址设置黑洞路由其它
描述
通过关闭NIC隔离受害主机
利用IDS或Firewall丢弃可疑数据包断开信息系统与外部网络连接发送重置包重置会话
利用软件阻断端口利用软件阻断IP地址
利用Firewall修改路由表到不可达IP *
OcostOL2OL2OL2OL2OL2OL2OL2*
下面我们来分析攻防成本/收益,首先给出一些定义.
定义2. 攻击回报AR(AttackReward)表示攻击者发动一次成功攻击所得到的好处,一般用该攻击对网络系统的损失来表示(用正值表示).事实上,攻击者收益一般少于网络系统损失.有时为了简便分析,可以把防御者的损失作为攻击者的所得.
定义3. 攻击成本AC(AttackCost)表示攻击者发动一次攻击所需要的软硬件资源、专业知识和攻击被发现时相应的法律制裁(用负值表示).
定义4. 攻击致命度AL(AttackLethality)表示某类攻击所具有的固有危害程度.表1中给出了各类攻击的致命度,用0~10之间的数值表示.定义5. 系统损失代价Dcost(Damagecost)表示某类攻击对目标资源的损害程度.
攻击的目标资源损失可以用危险度(criticality)、安全属性损害来描述.Northcut提出用危险度和致命度来描述被攻击目标的重要性程度和攻击的固有危害,本文参考了他的量化思想.在报告¹中,作者提出了信息安全属性的可计算性的思想和模型.在这里我们受该思想启发,将安全属性的损害可以分为完整性代价Icost(Integritycost)、机密性代价Ccost(Confidentialitycost)和可用性代价Acost(A-vailabilitycost).安全属性的损害对每一种安全属性代价具有一定偏重,用(Pi,Pc,Pv)来表示对完整性代价、机密性代价和可用性代价的偏重,且满足Pi+Pc+Pv=1.安全属性代价的值可以根据攻击将对目标资源产生的危害评估,可以用高、中、低来进行分类表示.安全属性代价的偏重可以根据具体的网络环境来确定.攻击a对网络系统的损失代价可以由式(1)来计算: Dcost(a)=
[28]
[27]
定义6. 防御回报DR(DefenseReward)表示针对某一攻击采取防御策略后,网络系统免受的损失.一般用攻击对网络系统的损失来表示(用正值表示).
定义7. 操作代价Ocost(Operationcost)表示防御者的防御操作消耗的时间和计算资源的数量.根据防御操作的复杂程度分为以下3个级别[14]:
OL1:操作代价非常小,几乎可以忽略不计,如终止用户进程等.
OL2:防御操作在生效时间内持续占用系统资源,但占用资源较少,如配置防火墙规则.
OL3:防御操作在生效时间内持续占用较多的系统资源,如系统备份.
在表2中给出了各种防御策略的操作代价.可以根据不同的网络情景用具体的代价值来表示各层次相对的操作代价,如OL1的操作代价可以设为1~10,OL2的操作代价可以设为10~50,OL3的操作代价可以设为50~100.
定义8. 负面代价Ncost(Negativecost)表示防御策略导致系统无法正常工作或服务质量下降等带来的损失.例如,关闭服务或系统可能无法正常用户提供相关服务.可以用前面定义的系统可用性乘以一个负面系数r(a,d)来表示:Ncost=Acost@r(a,d).其中r(a,d)表示用防御策略d来防御攻击a对系统可用性所具有的负面影响程度.
定义9. 残余损失Rcost(Remaindercost)表示防御系统执行防御策略后,攻击对系统带来的残余的未被消除的损失.可以用以损失代价乘以残余系数来表示:Rcost(a,d)=Dcost(a)@E(a,d).其中E(a,d)表示用防御策略d来防御攻击a所具有的残余损失程度.
定义10. 防御成本Decost(Defensecost)是防
EAL@criticality@
1
m
(Icost@Pi+Ccost@Pc+Acost@Pa)
(1)
其中m是受攻击主机个数.
¹
方滨兴.关于信息安全属性的可计算性初探.中国信息安
全大会主题报告.http://www.51cto.com/art/200604/25703.htm
822
计 算 机 学 报2009年
御策略的操作代价、负面代价和残余代价之和(用负值表示).即
Decost(d)=Ocost+Ncost+Rcost
=Ocost(d)+Acost@r(a,d)+
Dcost(a)@E(a,d)
(2)
数,表示局中人Pi的效用函数,其中R是效用值.效用函数表达了攻防双方从博弈中能够得到的收益水平,它是所有局中人策略的函数.不同的策略可能得到不同收益,它是每个局中人真正关心的参数.在上
一节中我们已经对攻防双方的成本和收益进行了量化,这里攻防效用函数分别表示为攻防成本和回报之和.
图3给出了网络攻防博弈模型的图表示,该模型是网络攻防博弈模型的通用模型.为了简化分析,我们只考虑n=2的情况,ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud)),其中Pa表示攻击者,Pd表示防御者(系统).Sa=(s1,s2,,,sm)表示攻击者的攻击策略集合,Sd=(s1,s2,,,sn)是防御系统的防御策略集合.PsiISa,sjISd,Ua(si,sj),Ud(si,sj)分别表示防御系统对攻击者的攻击策略si采取防御策略sj后攻击者和防御者的收益.效用函数集合可以表示为一个矩阵U,攻击者可能选取的攻击策略用矩阵中每一行来表示,防御者选取矩阵中每一列作为其防御策略.攻防双方的目标是最大化其收益,用矩阵中的数字表示攻防双方的收益.图4给出了图1防御图实例对应的攻防博弈矩阵.
a
d
a
d
a
d
a
d
d
d
d
a
a
a
4 网络攻防博弈模型
理性的攻击者是考虑攻击成本的,在攻击所得利益相同而攻击成本不同的情况下,他会选择具有低成本的攻击方式的.但是对于非理性的攻击者来说,他只考虑如何最大化攻击所得回报,不考虑攻击成本.防御非理性攻击者只需要从攻击者角度来研究何种攻击策略能够使得攻击者具有最多的回报.但是防御理性的攻击者具有一定的难度,本文只考虑理性的攻击者的防御研究.
假设1. 攻击者是智能而理性的决策主体.攻击者不会发动无利可图的攻击.
假设2. 攻击者总是追求攻击收益最大化.例如,攻击者偏向于对目标资源具有最大损害的攻击方式.
在攻防博弈过程中,攻击者和防御者都希望通过最优的策略来最大化他的收益,所以我们假定他们是理性的、合理的.在以上两条合理假设的基础上,可以将攻击者与防御者(系统)的矛盾冲突关系描述为策略型攻防博弈模型,从而通过计算该博弈的纳什均衡获得攻击意图和最优的防御策略.4.1 模型相关定义
定义11. 攻防博弈模型ADG(Attack-De-fenseGame)是一个三元组ADG=(N,S,U),其中
¹N=(P1,P2,,,Pn)是参加攻防博弈的局中人集合,局中人是博弈的决策主体和策略制定者.在不同的博弈中局中人的含义是不同的,既可以是个人也可以是具有共同的目标和利益的团体或者集团,这里局中人是攻击者或防御系统.若攻击者的数量E2,则表示分布式协同攻击;若防御系统的数量E2,则表示多个防御系统协同防御.
ºS=(S1,S2,,,Sn)是局中人的策略集合(strategyset),PiIn,SiXÁ,Si=(s,s,,,s)表示局中人Pi的策略集合,是局中人Pi进行博弈的工具和手段,每个策略集合至少应该有两个不同的策略,即mE2.
»U=(U1,U2,,,Un)是局中人的效用函数集合(utilityfunction).PiIn,Ui是@
iIni1
i2
im
图3 攻防博弈模型
在任何网络攻防环境中,攻击者和防御者之间的关系都是非合作的、对抗性的.在攻防博弈的过程中,攻防双方不会事先将策略决策信息告知对方,攻击者总是希望通过破坏目标资源的功能或服务质量来获得最大化收益.防御系统总是希望把系统的损伤降为最少.所以我们的攻防博弈模型是一个非合作攻防博弈(Non-CooperativeADG,NCADG).
Sd1
Ua11sa1
a
s2Ua21sa3Ua31
Ud11Ud21
Ud31
Ua12Ua22Ua32
Sd2
Ud12Ud22
Ud32
Ua13Ua23Ua33
Sd3
Ud13Ud23Ud33
图4 攻防博弈收益矩阵
通常,在攻防博弈中,网络信息系统的损失即为攻击者的收益.但是考虑到在一些特殊情况下,攻防双方的收益和损失并非总是相等.所以攻防双方的
SiyR的函
4期姜 伟等:基于攻防博弈模型的网络安全测评和最优主动防御
823
收益关系可分为零和(zero-sum)与非零和(nonzero-sum).如果攻防双方的收益Ua和Ud满足Ua+Ud=0,就称此为零和攻防博弈.Ua+UdX0,称为非零和攻防博弈.根据不同的网络环境和攻防情景进行选择是否零和或非零和博弈模型.
下面给出几个重要定义,它们是后面主动防御策略选取算法的理论依据和求解方法.
定义12. 纳什均衡(NashEquilibrium,NE).在ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud))中,攻防策
d略对(sa*,s*)是一个纳什均衡,当且仅当对每一个
[3]
合策略是攻防双方的最优混合策略,即满足:对于
***
Ppa,Va(p*a,pd)EVa(pa,pd);对于Ppd,Vd(pa,*p*d)EVa(pa,pd).
利用定义14,我们可以计算攻防双方采用混合策略时的纳什均衡.
4.2 基于攻防博弈模型的主动防御策略选取算法防御策略的选取十分复杂,因为针对单个攻击策略,防御决策只需要选择综合防御代价最小的策略.而在多步攻击和多个攻击策略的情况下,有的防御策略可能对某类攻击有效,对其它攻击无效,同时要考虑到防御操作代价、负面代价和残余损失.另外每个攻击策略的发生概率是未知的,如何保证该防御策略是最优的,即期望综合防御代价是最低的,是一个十分复杂的问题.基于攻防博弈模型的主动防御策略选取可以很好地解决此类问题.下面给出基于攻防博弈模型的主动防御策略选取算法,具体描述如下.
算法1. 基于攻防博弈模型的主动防御策略选取算法.
输入:网络防御图DG=(S,S,S0,Ss,Sa,Sd)输出:攻击意图和最优防御策略Soa
1.初始化ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud));
aa
2.构建攻击策略集合Sa={sa1,s2,,,sm};dd3.构建防御策略集合Sd={sd1,s2,,,sn};
局中人i,策略s*是对付另一个局中人的最优对策:对于PsISa,Ua(s*,s*)EUa(s,s*);对于PsI
dad
Sd,Ud(sa*,s*)EUd(s*,s).
a
a
d
a
d
d
i
在攻防双方都对对方具有完全信息的假设下,纳什均衡表示了攻防双方的最优对策.利用定义12我们可以计算攻防博弈模型所有可能的纳什均衡.但是考虑到攻防双方行为的不确定性,所以有时不可能存在一个纳什均衡,此时攻防各方必须考虑攻防混合策略.
定义13. 混合策略(MixedStrategy[29],MS).给定一个攻防博弈ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud),攻防双方的混合策略分别是Sa=(s1,
dd
sa2,,,sam)和Sd=(s1,s2,,,sdn)的概率分布pa=
a
(pa1,pa2,,,pam)和pd=(pd1,pd2,,,pdn),且满足0FpaiF1,0FpdiF1,
i=1
Ep
m
ai
=1,
j=1
Ep
n
4.IfADG是零和攻防博弈模型(Ua=-Ud)then
//仅需计算Ua或Ud,这里计算Ud5. forallsaiISa,do
6. 用式(1)计算sai的所有原子攻击的攻击收益之和
dj
=1.
在网络攻防环境下,特别是防御者在处理单个
攻击者的未知攻击策略时,利用先验知识(以前攻击者所采用的攻击策略的频率)来评估该攻击者可能使用的策略概率分布,从而可以采用混合防御策略.
定义14. 混合策略纳什均衡(MSNE)
[29]
EDcost(a);
i
i
d
7. 对每一个防御策略sdjISd,用式(2)计算sj的
Decost,Udij=
EDcost(a)-i
i
Decost;
.给
定一个攻防博弈ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud),攻防双方的混合策略分别是概率分布pa=(pa1,pa2,,,pam)和pd=(pd1,pd2,,,pdn),那么攻防双方的期望收益分别用下式来计算
Va(pa,pd)=
=
Vd(pa,pd)=
=
*
a
8. 生成效用矩阵U;
9.elseifADG是非零和攻防博弈模型(UaX-Ud)then
a
10. 对每一个攻击策略saiISa,用式(1)计算si的所有
原子攻击的攻击收益之和
EDcost(a),
i
i
Uaij=
Ep
iminj
m
ainj
Ep
jaimi
n
dj
Ua(s,s)
(3)
a
idj
EDcost(a)+
i
i
AC;
d
11. 对每一个防御策略sdjISd,用式(2)计算sj
EEpEp
nj*
ddjmi
d
#pdjUa(sai,sj)
的Decost,Udij=
EDcost(a)+
i
i
Decost;
Ep
ai
ai
Ud(si,sj)
(4)
ad
12. 生成效用矩阵U;
13.if矩阵U存在鞍点 then
14. 调用纯策略求解子算法Slove1(ADG);//求解ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud))
15.elseif矩阵U不存在鞍点 then
16. 调用混合策略求解子算法Slove2(ADG);
EEp
d
#pdjUd(sai,sj)
混合策略(p,p)是纳什均衡,当且仅当该混
824
的攻击意图和最优主动防御策略Soa;18.returnSoa;
计 算 机 学 报2009年
17.对得到攻击意图和防御策略进行分析,确定最终
博弈模型ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud))的最优混合策略集合的时间复杂度是多项式时间的.
分析可见,整个算法的复杂度可以满足防御系统的需求.
纯策略求解子算法具体如下.
算法2. 纯策略求解子算法Slove1(ADG).
输入:攻防博弈模型ADG输出:NashEquilibrium1.M=Á;
2.foralls1ISi,
3.{S=Solve1(Sub(ADG,s1))4.Sc=argmaxUi(s1,s);
sIS
5 应用实例与分析
为了验证前面所提出的攻防代价量化可计算模型和网络攻防博弈模型,本文采用如图5所示的网络拓扑结构来模拟攻防情景.攻击主机位于外部网络,目标网络为交换网络,其中共有3台计算机,分别为公共Web服务器、文件服务器和内部数据库服务器.防火墙将目标网络与外部网络分开,防火墙规则如表3所示.利用弱点扫描软件对目标系统进行弱点分析,主机信息和得到的弱点信息如表4所示.
5.//argmaxUi(s1,s)表示使Ui(s1,s)取最大值的s集合
sIS
6.ifM=ÁorUi(s1,Sc)=Ui(M)7.M=MGAdd(s1,Sc);
8.//Add(s1,Sc)表示添加策略s1到Sc9.ifUi(s1,Sc)>Ui(M);10.M=Add(s1,Sc); }returnM.
混合策略求解子算法具体如下.
算法3. 线性规划求解混合策略子算法Slove2(ADG).
输入:攻防博弈模型ADG输出:NashEquilibrium1.maximizev2.subjectto3.forallsjISj;4.5.
i=1mm
图5 网络拓扑实例表3 防火墙规则信息
源主机AllAllAll
WebserverFileserver
目的主机WebserverWebserverFileserver
DatabaseserverDatabaseserver
服务httpftpftpOracleftp
访问策略AllowAllowAllowAllowAllow
EpU(s,s)Ev;
i
i
j
i=1
Ep=
i
1,piE0.
4.3 算法复杂性分析
基于攻防博弈模型的主动防御策略选取算法的关键是攻防博弈模型ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud))的建立和求解,包括特定攻击策略的可行防御策略集合的建立,攻防策略成本量化和计算,最后就是攻防博弈模型的求解.为了提高效率,攻防成本量化模型中许多参量可以预先配置在数据库中.在防御策略选取模块初始化时,这些数据库信息加载入内存中.例如攻击损失代价、资源描述、防御操作和负面代价系数表、残余损失系数表等防御代价模型参数.整个算法的时间复杂度主要取决于两个子算法计算所有的纳什均衡.给出以下两个关于子算法复杂度的定理.由于篇幅限制,这里不给出定理的证明.
定理1. 子算法1求解攻防博弈模型ADG=((Pa,Pd),(Sa,Sd),(Ua,Ud))的最优纯策略集合的时间复杂度是线性时间的.
定理2. 子算法2利用非线性规划求解攻防
表4 服务器弱点信息
主机WebserverFileserverDatabaseserver
操作系统LinuxLinuxLinux
弱点
ApacheChunkedEnc.,Wu-FtpdSockPrintf()Ftp.rhostoverwriteOracleTNSListenerLocalbufferoverflow
Bugtraq编号
5033866832840333886
假设攻击者在攻击主机上具有Root权限,并在此发起攻击,将获取数据库服务器的Root权限作为目标.根据防火墙规则,攻击者在Web服务器、文件服务器上,仅仅具有最低的用户权限Access,而无法访问数据库服务器.但是服务器弱点的存在及其依赖关系,攻击者可以进行如表5所示的原子攻击,同时给出了攻击类别和致命度信息.对服务器弱点、原子攻击及其关联关系进行评估分析,从防御策略库(参见表2)选出可用的防御策略信息如表6
4期姜 伟等:基于攻防博弈模型的网络安全测评和最优主动防御
825
所示,并考虑无防御措施的情况.
表5 原子攻击描述
1.2.3.4.5.
编号及名称
ApachechunkoverflowWu-FtpdbufferoverflowFtp.rhosts
RemotebufferoverflowLocalbufferoverflow
类别RootRootUserRootRoot
AL101051010
金融货币为单位的.查询防御策略库得到各个防御策略的Ocost,具体数值见表4.因为攻击都是针对某个服务器,可能造成该服务器的拒绝服务.所以该攻击仅对目标资源的可用性产生危害,即Pi=Pc=0,Pv=1.若Ncost很小时,我们可忽略不计,在表4中设为0.否则Ncost的计算转换为对服务器DOS攻击的损失代价,因为防御策略的负面影响可以看作是对服务器的一次DOS攻击.Web服务器和文件服务器的criticality均为4,Database服务器的criticality为5.安全属性代价的高、中、低分别用30,20,10来表示,Web服务器和文件服务器的安全属性代价为20,Database服务器的安全属性代价为30.防御代价模型参数取值如表6所示,Ei表示防御策略防御编号为i的攻击所具有的残余损失程度.然后,通过用式(1)和(2)来计算每一个攻击策略的防御代价,如图7攻防策略收益矩阵所示.
A1
A2A3
Sd18108102310
Sd2151024702310
Sd3167016702470
Sd4247024701670
Sd526502470970
Sd6230023002300
表6 防御策略描述
名称 OcostNcostRcost中E的取值
D1:安装Oracle补丁10 0E1=E2=E3=E5=1,E4=0D2:安装Apache补丁10 0E1=0,E2=E3=E4=E5=1D3:取消/MAIL_ADMIN010160E2=0,E1=E3=E4=E5=1D4:关闭FTP服务10160E1=E2=E4=E5=1,E3==0D5:取消suidroot10240E1=E2=E3=E4=1,E5=0D6:不采取防御措施00E1=E2=E3=E4=E5=1
根据我们提出的网络防御图模型,对输入防火墙和路由器的配置文件、弱点数据库和防御策略等信息对该网络系统进行建模得到一个抽象的网络防御图,如图6所示.通过对图6分析发现,虽然网络防火墙设置了静态的规则来保护网络中的数据库服务器,但由于弱点的依赖关系,还是存在3条可能的攻击路径到达攻击目标.攻击者可能攻击策略为
A1:AA2:AA3:A
其中A
1
4
123
443
图7 攻防博弈收益矩阵
BCDE;E;F5
Nash根据Brouwer不动点定理给出了每一个有限博弈都有一个均衡点的证明[30].我们这里得到的攻防博弈是一个有限博弈,所以肯定存在均衡点.
E.最后,用定义14来求解上述建立的攻防双方采用混合策略时的纳什均衡.利用基于攻防博弈模型的主动防御策略选取算法,得到一个纳什均衡:pa=6792,0,,pd=159159
2825,0,0,0,0,.即攻击者最535392选择攻击策略A3和以概159
BE表示攻击者从初始状态A利用
原子攻击1到达B,然后利用攻击4到达目标状态E,即为一个攻击策略.
优的攻击策略是以概率
率67选择攻击策略A1;防御者最优的防御策略是159以概率
2825选择防御策略D1和以概率选择防御策5353
略D5.所以对于防御者来说,最优的防御策略是D1安装Oracle补丁,从而攻击者的目标将无法实现.
图6 网络系统防御图
在实际应用中,可以根据网络环境和安全需求可以同时采取防御策略D1和防御策略D5,这样网络信
息系统安全性将大大加强.
下面我们介绍利用上述算法来求解最优的防御策略的过程.攻防策略集合确定完之后,需要计算攻防策略代价,为了简化分析,采用零和非合作攻防博弈模型来进行最优防御策略选取,从而仅需计算防御代价即可.考虑到攻防代价的实际意义,防御者的防御代价取负值.本文给出的具体代价数值都是以
6 结束语
为了进行网络信息系统安全测评和最优主动防御,提出了一个新的基于网络系统安全测评的主动
826
计 算 机 学 报2009年
防御模型)))网络攻防博弈模型,该模型包括网络防御图模型、攻防策略代价分类及其量化模型和基于上述模型的最优主动防御决策算法.防御者以最优的防御代价进行网络安全加固和主动防御.从而构建一套自动地风险评估、最优防御成本的主动防御模型,为及时有效地主动防御提供了有力保证.
最后通过一个典型的网络实例模拟和分析该模型和算法在网络安全测评和最优主动防御方面的应用.
参
[1]
[13][12]
NewSecurityParadigms.Charlottesville,Virginia,UnitedStates,1998:71-79
RamakrishnanC,SekarR.Mode-lbasedvulnerabilityanaly-sisofcomputersystems//Proceedingsofthe2ndInternation-alWorkshoponVerification,ModelCheckingandAbstractInterpretation.Pisa,Italy,1998:1-8
RitcheyRW,AmmannP.Usingmodelcheckingtoanalyzenetworkvulnerabilities//ProceedingsoftheIEEESympos-iumonSecurityandPrivacy.Berkeley,CA,USA,2000:156-165
[14]
LeeWenke.Towardcost-sensitivemodelingforintrusionde-tectionandresponse.JournalofComputerSecurity,2002,10(1-2):5-22
[15]
JiangWeietal.Agametheoreticmethodfordecisionandanalysisoftheoptimalactivedefensestrategy//ProceedingsoftheInternationalConferenceonComputationalIntelligenceandSecurity.Harbin,China,2007:819-823
[16]
FengPing-Hui,LianY-iFeng,DaiYing-Xiaetal.Anevalu-ationmodelofvulnerabilityexploitationcostfornetworksys-tem.ChineseJournalofComputers,2006,29(8):1375-1382(inChinese)
(冯萍慧,连一峰,戴英侠等.面向网络系统的脆弱性利用成本估算模型.计算机学报,2006,29(8):1375-1382)
[17]
HaywoodOG.Militarydecisionandgametheory.JournaloftheOperationsResearchSocietyofAmerica,1954,2(4):365-385
[18][19]
BramsSJ.GameTheoryandPolitics.NewYork:FreePress,1975
SyversonPF.Adifferentlookatsecuredistributedcompu-tation//Proceedingsofthe1997IEEEComputerSecurityFoundationsWorkshop.MA,USA,1997:109-115
[20]
BurkeD.Towardsagametheorymodelofinformationwar-fare[M.S.dissertation].TechnicalReport:AFIT/GSS/LAL/99D-1.AirforceInstituteofTechnology,1999
[21]
LyeK-W,WingJ.Gamestrategiesinnetworksecurity.SchoolofComputerScience,CarnegieMellonUniversity,Pittsburgh:TechnicalReportCMU-CS-02-136,2002
[22]
XuJ,LeeW.SustainingavailabilityofWebservicesunderdistributeddenialofserviceattacks.IEEETransactionsonComputers,2003,52(4):195-208
[23]
LiuP,ZangW.Incentive-basedmodelingandinferenceofattackerintent,objectives,andstrategies//Proceedingsofthe10thACMComputerandCommunicationsSecurityCon-ference(CCS.03).Washington,DC,2003:179-189
[24]
JiangWei,FangBin-Xingetal.Optimalnetworksecuritystrengtheningusingattack-defensegamemodel//Proceedingsofthe6thInternationalConferenceonInformationTechnolo-gy:NewGenerationsITNG2009.LasVegas,Nevada,USA,2009
[25]
LippmannRP,FriedDJ,GrafIetal.Evaluatingintrusiondetectionsystems:The1998DARPAoff-lineintrusionde-tectionevaluation//ProceedingsoftheInformationSurviv-
考文献
ZhangYong-Zheng,FangBin-Xing,ChiYueetal.Riskpropagationmodelforassessingnetworkinformationsys-tems.JournalofSoftware,2007,18(1):137-145(inCh-inese)
(张永铮,方滨兴,迟悦等.用于评估网络信息系统的风险传播模型.软件学报,2007,18(1):137-145)
[2]NicolDM,LiljenstamM.Modelsandanalysisofactivewormdefense//LectureNotesinComputerScience,2005,3685:38-53
[3][4]
NashJohn.Equilibriumpointsinn-persongames.Proceed-ingsoftheNationalAcademyofSciences,1950,(36):48-49HamiltonSN,MillerWL,OttA,SaydjariOS.Theroleofgametheoryininformationwarfare//Proceedingsofthe4thInformationSurvivabilityWorkshop.Vancouver,Canada,2002:45-46
[5]FengDeng-Guo,ZhangYang,ZhangYu-Qing.Surveyofin-formationsecurityriskassessment.JournalofChinaInstituteofCommunications,2004,25(7):10-18(inChinese)(冯登国,张阳,张玉清.信息安全风险评估综述.通信学报,2004,25(7):10-18)
[6]LinChuang,WangYang,LinQuan-Lin.Stochasticmodel-ingandevaluationfornetworksecurity.ChineseJournalofComputers,2005,28(12):1944-1956(inChinese)
(林闯,汪洋,李泉林.网络安全的随机模型方法与评价技术.计算机学报,2005,28(12):1944-1956)
[7][8]
SchneierB.Attacktrees.Dr.Dobb.sJournal,1999,24(12):21-29
MooreAndrewP,EllisonRobertJ,LingerRichardC.At-tackmodelingforinformationsecurityandsurvivability.TechnicalNote:CMU/SEI-2001-TN-001,2001
[9][10]
DacierM.Towardsquantitativeevaluationofcomputersecu-rity.InstitutNationalPolytechniquedeToulouse,1994OrtaloR,DeswartesY,KaanicheM.Experimentingwithquantitativeevaluationtoolsformonitoringoperationalsecur-ity.IEEETransactionsonSoftwareEngineering,1999,25(5):633-650
[11]PhillipsCA,SwilerLP.Agraph-basedsystemfornetworkvulnerabilityanalysis//Proceedingsofthe1998Workshopon
4期姜 伟等:基于攻防博弈模型的网络安全测评和最优主动防御
2006:1-29
[28]
827
abilityConferenceandExposition(DISCEX)2000.LosAlamitos,CA:IEEEComputerSocietyPress,2000,2:12-26
[26]
NataliaStakhanova,SamikBasu,JohnnyWong.ATaxono-myofIntrusionResponseSystems.InternationalJournalofInformationandComputerSecurity,2007,1(1/2):169-184
[27]
GordonL,LoebM,LucyshynW,RichardsonR.2006CSI/FBIcomputercrimeandsecuritysurvey//ProceedingsoftheComputerSecurityInstitute.
SanFrancisco,
California,
[30][29]
NorthcuttS.NetworkingIntrusionDetection:AnAnalyst.sHandbook.Indianapolis,Indiana,UnitedStates:NewRid-ersPublishing,1999
GibbonsRobert.APrimerinGameTheory.NewYork:PearsonHigherEducation,1992
NashJohn.Non-cooperativegames.TheAnnalsofMathe-matics,2ndSer.,1951,54(2):286-295
JIANGWei,bornin1979,Ph.D.candidate.
Hisresearchinterestsare
networkandinformationsecurity,net-workattackanddefense.
pervisor,memberofChineseAcademyofEngineering.Hiscurrentresearchinterestsincludecomputerarchitecture,in-formationsecurityandcomputernetwork.
TIANZh-iHong,bornin1978,Ph.D.,lecturer.Hisre-searchinterestsfocusonnetworkandinformationsecurity.
ZHANGHong-Li,bornin1973,professor,Ph.D.su-pervisor.Herresearchinterestsincludenetworkandinfor-
FANGBin-Xing,bornin1960,professor,Ph.D.su-mationsecurity,networkmeasure.
Background
ThisresearchispartlysupportedbytheNationalBasicResearchProgram(973Program)ofChinaundergrantNo12007CB311100,theNationalHighTechnologyResearchandDevelopmentProgram(863Program)ofChinaundergrant(Nos12007AA01Z442,2007AA01Z406,2009AA012437).
Traditionalstaticprotectivemeasuresarenotsufficienttosecureacomplexnetworkedsystem.Existingcybersecur-itytechnologiescanonlypassivelyprevent,detect,andreacttocyberattacks.Intrusiondetection(ID)architectureisapassiveinformationprocessingparadigm.Inmanycasesin-trusionresponseis/toolate0afterveryseriousdamageiscaused.Attackpredictionisverycriticalforcyberhomelandsecurity.Itisabigchallengethatmakingcorrectoptimalproactivedefensedecisionsduringanearlierstageoftheat-tack.Insuchawaywecantransformpassivetoproactivecy-berdefense,andmuchlessharmwillbecausedwithoutcon-sumingalotofresources.
Thispaperviewstheinteractionsbetweenanattackerandthedefenderasatwo-playernon-cooperativegameandformulateanattack-defensegame(ADG)modelforthegame.Thedefensegraphmodel,attack-defensetaxonomyandcostquantitativemodelareproposed.Analgorithmforoptimalactivedefensestrategyselectionbasedonthosemod-elsisproposed.Optimaldefensestrategieswithminimizingcostsareusedtodefendtheattackandhardenthenetworkinadvance.Thispaperisanextensionanddevelopmentoftheirpreviouswork[14,24].
因篇幅问题不能全部显示，请点此查看更多更全内容