攻击文法与攻击图模型的对比研究1张殷乾，王轶骏，薛质上海交通大学信息安全工程学院，200240【摘要】攻击文法【1】是我们提出的一种保障大型计算机网络安全的分析模型和工具。
与传统的攻击图模型相比，攻击文法有其独特的优势。
本文以近年来国内外的攻击图研究成果为背景，对比分析攻击文法在网络攻击建模、模型描述能力和算法复杂度等方面的优点和不足。
同时，通过回顾理清该领域当前世界最先进的研究思路和发展方向，明确攻击文法的定位，为未来研究奠定基础。
【关键词】网络安全攻击文法攻击图网络攻击建模A Comparative Review of Researches on Attack Grammar and Attack GraphYinqian Zhang Yijun Wang Zhi Xue(School of Information Security Engineering, SJTU, Minhang District, Shanghai, 200240, China)Abstract: Our attack grammar is a new approach to large scale network attack modeling and analysis. Compared with traditional models such as attack graphs, attack grammars have their unique advantages. In this paper we summarize recent researches on attack graphs and compare them with our attack grammar approach in the ability of network attack modeling, attack scenario expressing and scaling. In the mean while, a review of the most advanced techniques in attack graphs is proposed in order to summarize their methodology and to provide a clearer research direction for future studies.Key words: Network security, attack grammar, attack graph, network attack modeling.1.引言计算机网络由于软件和配置漏洞而存在着安全威胁。
在大规模的计算机网络中，黑客的入侵不再是针对一台主机，而是以跳板的方式，一步一步渗透至网络内部。
负责安全防护的网络管理员必须在错综复杂的网络环境中找到所有可能的攻击路径，并在技术和资金允许的情况下优先选择修补最为关键的安全漏洞，或者监控最薄弱的安全环节。
为此目的，学者们设计出了多种安全威胁模型。
这些模型中最重要的就是攻击图。
攻击图是一种用图来表示大型网络中攻击路径的方法【2】。
它利用大型网络的配置和漏洞信息，从全局的角度分析它们的依存关系，找出所有可能的攻击路径，并且为网络管理员提供安全建议。
近年来，攻击图的研究重点主要围绕以下几个问题：一、网络结构和主机配置的自动获取；二、漏洞细节的自动生成；三、攻击图生成算法的扩展性（scalability）；四、基于攻击图自动提出网络安全增强建议。
这些研究使攻击图逐步从理论走向了实践。
但是，我们认为攻击图方法本身存在着一定的不足。
首先，对于复杂网络，攻击图的规模往往大到无法控制，使管理员很难理解图的内容。
第二，攻击图中普遍存在冗余信息，加大了分析的1作者简介：张殷乾（1983.7-），男，硕士研究生，主要研究领域为网络与信息安全（email: stanielzhang@）。
王轶骏（1980.9-），讲师，主要研究网络与信息安全。
薛质（1971.2-），教授，博士生导师，主要研究网络与信息安全。
难度。
第三，攻击图不能有效表达漏洞间的依赖关系，不适合用于入侵检测系统(IDS)报警关联。
为此，我们提出了一种基于上下文无关文法的网络攻击模型和安全分析系统——攻击文法【1】。
攻击文法能够从一个新的角度去解决攻击图模型固有的问题，为该领域带来了新的思路。
2.攻击图研究回顾根据攻击图的基本研究方法分类，可以把攻击图研究分为两类：基于图的方法和基于逻辑的方法。
2.1 基于图的方法早期的基于图的方法研究攻击图的代表是Swiler和Phillips等人在1998年提出的方法【4】【5】，他们用网络的状态变量的集合来建模攻击图的结点，用黑客的动作来建模攻击图的边。
该方法的运行时间对网络的规模具有指数特征。
Ammann提出的基于图搜索的方法，假设网络攻击具有单调性，即黑客在攻击过程中不会放弃已经获得的权限。
这种假设在大多数的网络攻击场景中都适用，同时大大降低了算法的复杂度。
Jajodia等人提出的TV A系统【6】就结合了这种假设并且设计出O(N6)的算法。
2006年，麻省理工学院提出使用预测图（predictive graph）的NetSPA v1【7】和使用了多重先决条件图(Multiple-prerequisite graph，简称MP图) 的NetSPA v2【2】。
NetSPA v2是一个端到端的攻击图生成和分析工具。
它解决了以往攻击图研究中的网络数据自动采集问题和攻击图生成算法扩展性的问题。
它定义了更为简单的网络模型，方便系统自动采集网络数据；它采用MP图来代替NetSPA v1的预测图，使攻击图的生成算法几乎达到O(N)。
NetSPA的网络模型中包括了主机，端口和漏洞。
这些信息可以由Nessus扫描结果得到。
模型还定义了漏洞利用的两种先决条件——可达性和信用凭证。
可达性可以由防火墙配置得到；信用凭证用来建模用于访问控制的密码或者私钥。
NetSPA简化了漏洞的前提和影响结果，并采用自动化工具来提取NVD和Bugtraq漏洞库中的文本信息中的关键内容。
MP图包含了三种不同的结点：状态结点、先决条件结点和漏洞实例结点。
状态结点代表黑客在主机上的权限。
与状态结点通过有向边连接的先决条件结点表示黑客在该状态上可获得的先决条件，它可以是一个可达性条件，也可以是一个信用凭证。
与先决条件结点连接的漏洞实例结点表示该先决条件可以利用的漏洞。
漏洞实例结点通过有向边与新的状态结点相连。
NetSPA提供了把网络模型转化为MP图的算法。
算法的复杂度最坏情况下是O(max(V,T )NC)，其中V代表漏洞实例的个数，T代表端口数，C代表信任凭证的数目，N代表主机群的个数。
实验数据表明NetSPA的性能非常好，可以在数秒内完成对数百台主机的安全检测和分析。
2.2 基于逻辑的方法早期的基于逻辑的方法大都源于模型检查。
Ritchey和Ammann等人提出使用模型检查器来为已知的漏洞生成攻击路径【8】。
Sheyner的工作【3】扩展了模型检查，但是模型检查没有假设网络攻击具有单调性，所以这些方法扩展性都不好，一个3台主机和4个漏洞的实例需要运行2个小时才能得到攻击图。
2005年Ou等人提出了MulV AL【9】。
MulV AL是一种基于逻辑的网络安全分析器。
它是一个端到端的多主机、多层次的网络安全分析架构和推理系统。
它使用Datalog作为建模语言，能够结合网络扫描器自动收集网络数据，并转化为Datalog语言描述的网络模型。
MulV AL 把网络模型输入给推理引擎，其推理规则假设了网络攻击的单调性。
引擎输出结果是该网络的一条攻击路径。
MulVUL具有强大的网络数据采集能力。
它能够整合开放漏洞评估语言(OV AL)兼容的网络扫描工具，把OV AL描述的漏洞信息和主机配置信息整合为Datalog描述的语句。
它还能够自动提取ICAT漏洞数据库的漏洞描述，为扫描得到的漏洞提供前提条件和影响结果的细节。
性能优势是MulV AL系统的一个特点。
实验数据显示，MulV AL的算法复杂度在O(N2)到O(N3)之间。
对于2000台主机的模拟网络运行时间大约在15秒左右。
MulV AL的缺陷在于它仅仅给出了一条攻击路径，而不是产生一个完整的攻击图。
另外，它在最坏情况下的复杂度也可能是指数的。
X. Ou进一步扩展了MulV AL【10】，把其生成的攻击路径拓展成为攻击图。
论文证明，生成攻击图的算法的复杂度为O(N2logN)。
3.攻击文法我们提出一种基于下推自动机（PDA）的网络攻击模型和利用上下文无关文法进行安全分析的工具——攻击文法。
攻击文法的工具如图所示。
Nessus图1 攻击文法工具组成3.1 网络模型和攻击文法攻击文法的网络模型中，主机是网络中可能受到攻击的网络实体，主机具有网络接口、端口和漏洞等属性。
主机群是具有相同可达性和相同漏洞的主机的集合。
模型中的漏洞使用前提条件和影响结果来描述，这两者都通过多维向量对象来建模，它们都表示黑客在某台主机上的某种权限或者知识，也称为黑客状态。
模型允许同时存在多个攻击目标。
攻击文法工具能够自动的把网络信息建模到PDA中。
一个攻击模型PDA定义为一个7元组：(S, Σ, Γ, δ, q0, Z0, F), 其中S是状态集合，代表网络攻击场景中的主机群。
Σ是输入符号的集合，代表漏洞或者对应的漏洞利用。
Γ是栈顶符号的集合，代表黑客状态。
δ是转移函数(Σ×S×Γ)→ (S×Γ)的集合，描述了一个漏洞利用的过程。
q0是初始状态，代表黑客的初始攻击点，Z0是栈中的初始符号，用于定义“空栈”接受的语言。
F是S的子集，表示终结状态。
攻击文法定义为一个四元组：(V, T, R, S)，其中V是文法中变量的集合，T是终结变量的集合，R是产生式的集合，S是初始符号。
攻击文法与PDA模型具有相同的描述能力。
攻击模型PDA描述了一个网络的攻击场景，如果一系列攻击动作对应的输入符号串能够被PDA所接受，那么这个攻击序列就能够使黑客从他的初始状态成功入侵目标主机；相应的，这个攻击序列应该是该网络的攻击文法所能够生成的一个句子。
我们的工具能够自动的把描述网络攻击模型的PDA转化为攻击文法。
自动生成的攻击文法往往非常庞大，我们设计了一系列的攻击文法简化算法，包括去除可空变量、去除无逻辑意义变量、去除非产生变量、去除非可达变量，目的是使攻击文法更简约明了，其变量更具有实际意义。
简化后的攻击文法中，一个终结变量代表了黑客入侵中可能利用的一种漏洞，一个非终结变量代表了黑客在攻击过程中的一种状态，这个状态能够与网络中的某台主机上的某种权限对应。
