用基于规划的方法生成和分析最小攻击图_ftp_rhost

用基于规划的方法生成和分析最小攻击图

A planner-based approach to generate and analyze minimal attack graph

申明
版权归原文作者及出版单位所有，如有侵权请联系删除。

摘要

在当前情景下，即使是经过良好管理的网络也容易受到复杂的网络攻击。这类攻击结合了存在于不同系统/服务上的漏洞，可能比单点攻击更具破坏性。分析企业网络中此类安全漏洞的方法之一是使用攻击图。攻击图是一个完全图，它以攻击路径的方式提供了不同攻击场景的简洁表示。攻击路径是一系列漏洞的逻辑连续，其中系列中的每个漏洞满足后续漏洞的前提条件，并在它们之间建立因果关系。因此，分析攻击图有助于从黑客的角度评估网络安全。生成和分析完整攻击图的固有问题之一是可扩展性。在这项工作中，提出了一种基于Planner的方法，Planner是人工智能领域的一种特殊用途搜索算法，用于高效、可扩展地表示攻击图。此外，还开发了定制的算法，用于自动生成攻击路径（使用Planner作为低级模块）。分析表明，使用定制算法生成攻击图可以在多项式时间内完成。还提供了一个案例研究，以展示所提出方法的有效性。
关键词：网络安全 · 攻击图 · 攻击路径 · 漏洞 · Planner

1.介绍

如今，企业网络越来越容易受到入侵和复杂的网络攻击的威胁。因此，网络管理员必须以一种方式分析网络的安全需求，使其在安全性和操作性方面都足够安全。当今的安全威胁涉及多阶段、多主机攻击。在这种相关攻击中，不同主机中存在的漏洞被结合起来以便入侵目标。网络安全技术包括一些高效的网络扫描工具，如Nessus、Retina、Nmap、CyberCop等。这些扫描工具在检测系统本地的漏洞方面非常有用，但无法识别完整攻击的所有条件，或者不知道不同系统中存在的不同漏洞是如何相关联以产生多阶段、多主机攻击的。一个描述网络中相关攻击的工具是攻击图。攻击图中的每个节点表示攻击者在攻击的各个阶段中使用的漏洞利用。边构成了成功执行漏洞利用所需的安全条件，或者是在执行漏洞利用后获得的结果。传统上，攻击图是完全图，描述了所有可能的攻击情景。这既包括成功的攻击，也包括那些未能达到目标状态的攻击。这种完整的攻击图包含了冗余的节点和边，并且难以直观地理解和分析。通过生成最小攻击图可以解决这些问题。最小攻击图包含那些终止于目标（或目标）节点的边，即只包含成功的攻击情景。本文关注使用Planner，一种人工智能技术，生成和分析最小攻击图，从而有助于管理员保护企业网络。

在生成和可扩展地表示攻击图方面，已经有相当数量的研究工作。研究人员使用自定义(custom)算法或形式化(formal)的方法构建攻击图。在一些文献中，攻击图也被称为漏洞依赖图[1]。一些尝试构建完整攻击图的自定义算法[2-5]在网络中的主机数量呈指数级增长。在[3、6-8]中使用的形式化(formal)方法用于生成攻击图，虽然探索了允许的攻击路径空间，但不具有高效的可扩展性。此外，用于图生成的模型检查器(model checkers)存在状态空间膨胀问题，即使对于中等规模的网络，也无法处理现实的一组漏洞。为了改进图生成的复杂性，一些方法[1、9、10]引入了单调性的显式假设。这意味着一旦攻击者在特定主机上获得了一定级别的权限，他在不久的将来就不必再次获得这些权限。这从攻击图中消除了回溯的概念，将复杂性从指数级提高到多项式级。然而，基于单调性假设生成的攻击图仍然不具有可扩展性，并且还包含许多冗余路径。在[11-13]中解决了这个可扩展性问题，不再生成完整的攻击图，而是引入了最小攻击图的概念。最小攻击图是一个攻击图，所有的攻击路径都终止在一个特定的目标节点上。但是，生成最小攻击图仍然需要多项式时间（在一些文献中[9]详述为$O(n^6)$，其中$n$是主机的数量）。在[14]中，提出了一个多先决条件图，它与网络的规模几乎线性相关。

在本研究中，我们使用$SGPlan$，$Planner$的一个变种，来生成最小攻击路径，然后使用自定义算法在多项式时间内将其合并成最小攻击图。本文主要关注使用模型检查器高效生成最小攻击图，从而解决可视化问题并避免状态空间膨胀。

接下来的部分组织如下。第2节简要介绍攻击图和Planner。第3节描述了所提出的方法以及一个案例研究。第5节分析了所提方法的时间复杂性，并在第6节中得出结论。

2.背景

在本节中，通过一个示例网络，简要介绍了攻击图模型。此外，还概述了Planner，以说明它如何用于生成攻击图。

2.1 攻击图模型

攻击图建模了不同主机上存在的不同漏洞，并将它们结合起来生成不同的攻击场景。实际上，攻击图由多个攻击路径组成，这些路径是漏洞利用的逻辑连续。序列中的每个漏洞满足后续漏洞的前提条件，并在彼此之间建立因果关系。攻击图中的一个节点子集被称为目标节点。目标节点通常由一个存在于目标主机上的漏洞来描述，执行该漏洞利用会导致该主机中关键资源的受损。先前描述的工作中使用了两种类型的攻击图，如下所示：

• 完整/全攻击图：在这种类型的攻击图中，绘制了所有可能的攻击场景（成功和不成功的）。
• 最小攻击图：最小攻击图仅包含终止于特定目标节点的攻击场景。

在本研究中，使用了最小攻击图的概念。攻击图的示例及网络配置如图1所示[15]。

图1：示例网络

网络（参见图1）包含两个内部主机，即Host1和Host2，它们与外部主机（即Host0）由防火墙隔开。攻击者已经入侵了Host0，并旨在入侵Host2中的数据库。
网络的主机描述在表1中给出。

表1：主机描述

给定网络的连接限制防火墙策略在表2中描述。

表2：连接限制防火墙 策略

防火墙允许入站的ftp和ssh数据包与Host1和Host2通信，同时阻止其他数据包。在网络内部，防火墙允许内部主机在任何端口上连接到远程服务器。

通过结合不同主机上的漏洞（参见表1）使用连接限制防火墙策略（参见表2），生成相应的最小攻击图（如图2所示）。

图2：示例网络攻击图

可以将其视为一个有向图，其中漏洞显示为椭圆形，安全条件显示为纯文本。例如，ftp_rhosts(0, 1)是属性(generic)漏洞ftp_rhosts的一个实例，表示Host0上的攻击者在ftp主目录上创建“.rhost”文件，以建立与Host1的远程信任关系。类似地，trust(0, 1)表示建立了Host0和Host1之间的信任关系的安全条件。通常，攻击图中的一个节点表示一个漏洞，而边则表示条件、可用漏洞或利用漏洞后获得的权限。从图2可以看出，攻击图包含三条攻击路径，这些路径都终止于所需的目标节点，即local_bof(2, 2)。成功执行local_bof(2, 2)漏洞的结果使攻击者能够在Host2上获得root权限。

2.1.1 形式化定义

在这个子节中，给出了攻击图（参见图2）的形式化定义，以及相关的术语。正式地，攻击图可以根据[16]的方法定义为：
定义 1 给定漏洞集合 $E$，安全条件集合 $C$，关系 $require{R}_r\subseteq C\times E$，以及关系 $imply{R}_i\subseteq E\times C$，攻击图 $AG$ 是一个无环有向图 $AG(E\cup C,R_r\cup R_i,C_0,C_{goal})$，其中 $E\cup C$ 是顶点集合，$R_r\cup R_i$ 是边集合，$C_0$ 是初始条件集合，$C_{goal}$ 是目标条件集合：$C_0\subseteq C$ 且 $C_{goal}\subseteq C$。

攻击图的一个重要观察是，$require$ 关系始终是安全条件的合取(conjunction)，而$imply$关系始终是同一条件的析取(disconjunction)。因此，可以正式地定义安全条件如下：

定义 2 攻击图 $AG$ 中源主机 $h_S$ 和目标主机 $h_T$ 之间的安全条件 $c\in C$ 是一个三元组 $(c,h_S,h_T)$，其中 $c$ 要么是启动实例化的漏洞利用 $e\in E$ 所需的前提条件，要么是启动后的后置条件。

攻击图中的任何节点本质上都是一个已实例化的漏洞利用，如果一组安全条件被合取满足，则可以在一对主机之间启动该漏洞利用。漏洞利用的成功执行会生成一个析取的结果集或效果。因此，给定实例化的漏洞利用集合 $E$，主机集合 $H$ 和条件集合 $C$，攻击图中节点的形式化定义如下：

定义 3 给定安全条件 $c_1,c_2,...,c_n$，对于所有 $c_i\in C$，攻击图 $AG$中的节点$v\in V$ 是一个三元组 $(e,h_S,h_T)$，其中 $e\in E$ 是已实例化的漏洞利用，$h_S$ 是源主机，$h_T$ 是目标主机，当且仅当关系 $c_1\wedge c_2\wedge \cdot \cdot \cdot \wedge c_n$ 得到满足时，可以启动漏洞利用$e$。

攻击图中的边可以是在一对已实例化的漏洞利用之间的转换，也可以是在已实例化的漏洞利用与安全条件之间的转换，或者反之，还可以是应用漏洞利用后获得的权限。攻击图中边的形式化定义如下：

定义 4 攻击图 $AG$ 中的边 $e\in E$ 是一个有向弧，可以是在一对节点之间的转换，也可以是在节点与安全条件之间的转换，或者反之。

2.1.2 高效生成攻击图的动机

随着主机网络规模不断增长和复杂化，它们越来越容易受到复杂攻击的威胁。这些攻击将存在于不同机器上的漏洞结合起来，以便入侵网络中的关键资源。因此，保护网络资源免受这些相关的、多阶段、多主机攻击已成为一个活跃的研究领域。攻击图可以被看作是为特定网络提供不同攻击场景的简洁表示的工具。传统上，它是一个具有内在可扩展性问题的完全图，需要指数时间来生成。此外，完整攻击图具有冗余的节点和边，并且存在与可理解性和可视化呈现相关的问题。随着最小攻击图的引入，可扩展性和可视化问题已得以解决，最小攻击图只考虑终止于特定目标的攻击场景。

为了在多项式时间内生成最小攻击图，已经使用了各种模型检查器和自定义算法。但是这些模型检查器存在状态空间爆炸的问题，而且在表示现实网络中的漏洞方面并不高效。因此，本文的动机是提出一种基于人工智能领域的模型检查器自动生成最小攻击图的方法，避免了状态空间爆炸或组合爆炸问题。使用所提出的方法生成最小攻击图的复杂性已与先前报道的方法进行比较，并在某些特殊情况下被证明是高效的。

在本研究中，提出了一种基于人工智能技术Planner的方法，用于生成最小攻击图。还详细分析了使用所提出方法生成最小攻击图的时间复杂性。

2.2 Planner

人工智能在定义和开发大多数现代环境决策支持系统（EDSS）方面产生了重大影响。当前关于生成最小攻击图的工作在构建之前需要做出许多决策。因此，自然而然地尝试使用人工智能来整合和增强这些决策结果。

Planner [17, 18] 是人工智能领域中的一种特殊用途搜索算法，用于在大型状态空间中找到解决方案。在这项工作中，使用了Planner的一个变体，称为SGPlan，用于找到攻击路径。初始状态、目标状态和状态转换运算符被提供为Planner的输入。输入规范以PDDL [19]（计划领域定义语言）编写在两个文件中，即 domain.pddl 和 fact.pddl。domain.pddl 包含未实例化的谓词和状态转换运算符。这些未实例化的谓词通过使用多个对象和STRIPS运算符 [19] 由现实世界实体进行初始化，以在 fact.pddl 中表示初始状态和目标状态。通过在 fact.pddl 中进行适当的更改，Planner可以放弃先前的计划并寻找新的计划。

Planner从初始状态开始执行，使用被称为plangraph的基于图的表示。plangraph是从初始状态开始生成的，并通过连续应用状态转换运算符生成。它在领域中的所有实例上运行，并将状态和目标映射到操作 [20]。生成plangraph在整个攻击路径识别过程中消耗了大部分时间。对于n个对象、m个STRIPS运算符，每个运算符最多具有k个常量形式参数，$t$级别的plangraph的生成时间将是多项式的，因为任何操作级别中最多生成的节点数为$O(m{n}^k)$ [17]。选择Planner作为生成攻击路径的技术的动机，是因为它提供了以下优势：

• 从系统中剪除不必要的动作，并找到最短路径。

• 允许在计划中随时随地添加所需的动作。

• 使用更丰富的输入语言PDDL，相对于自定义构建的分析引擎更容易地表达复杂的状态空间领域。

• 允许以更加真实的方式对网络、主机、漏洞、利用和连接关系进行建模。

3.使用Planner生成最小攻击图的方法

在本节中，提出了一种使用Planner生成最小攻击图的方法。相比于完整攻击图，倾向于生成最小攻击图的原因如下：

• 最小攻击图不包含冗余的节点和边，这使得网络管理员可以更好地可视化和理解网络中不同的攻击场景。
• 它基于明确的单调性假设，消除了攻击图中的回溯，并将生成时间从指数级降低为多项式级别。
• Planner生成无环路径，将其组合在一起即可生成最小攻击图。

在本研究中，Planner的功能机制已在图3中描述。

图3：Planner行为的流程图

它假设初始网络配置和漏洞分析已预先完成，并以PDDL [19]编写的域和事实文件的形式输入给Planner。根据初始网络配置、连接关系和漏洞描述，生成最短的攻击路径。为了生成其他最短的攻击路径，必须适当修改fact.pddl文件。最后，当所有攻击路径生成完毕，它们会被合并以形成最小攻击图。总之，整体机制如下：

1. 将初始网络配置和漏洞描述（以域和事实文件的形式）输入Planner，以生成最短攻击路径。
2. 自定义攻击路径枚举算法会自动修改fact.pddl，以生成下一个最短攻击路径或没有路径。
3. 自定义攻击图构建算法会将生成的最短攻击路径合并，以生成最小攻击图。

大型网络的攻击图扩展在许多文献调查中都被提及为一个问题[11-13]。大多数作者声称，一旦网络中的主机数量增加到数千台，现有的攻击图生成技术将会遇到严重的可扩展性问题。但是，从实际企业或学术网络的角度来看，我们会发现网络通常被划分为不同的区域、子区域等，每个区域都有不同的防火墙和访问策略，形成单独的管理域。理论上，我们可能有一个包含数千台主机的网络区域，但在现实中，我们几乎不太可能找到这样的情况。这些网络区域包含有限数量的主机，在它们上存在的漏洞数量也受到常数的上界限制。因此，为特定区域编码域文件所需的时间将与现有通用漏洞数量成比例。如果检测到新的漏洞，可以以线性递增的方式将其正式编码到域文件中。即使为事实文件进行编码，也不必输入 $N^2$ 个连接关系（其中 $N$ 是区域中主机的数量），因为存在限制性的防火墙策略。因此，为网络区域或子区域生成攻击图不会生成太多的状态变量，从而导致组合爆炸问题。因此，如果为每个区域生成单独的攻击图，然后通过一些启发式方法将它们合并，并适当修改状态变量，可以获得一个大的累积攻击图。因此，目前的方法可以被视为一种有效地为主机数量受到某个常数限制的网络区域生成攻击图的方法。

在接下来的部分中，将通过一个案例研究来解释所提出的方法。

3.1 案例研究

类似于[21]的网络被考虑为测试网络（TEST-NET），如图4所示.

图4：测试网络

该网络包括四台主机：Host0（H0）、Host1（H1）、Host2（H2）和Host3（H3）。H3被选作目标机器或目标，该机器上运行的MySQL6数据库是关键资源。TEST-NET中主机的系统特性在表3中列出。

表3：系统特性

这些数据可在Nessus、NVD [7] 和Bugtraq [8]中获得。表3中的每个通用漏洞都有一组前提条件和影响 [21,22]。其中一个通用漏洞（即IIS缓冲区溢出）的前提条件和影响如下所示：

• 前提条件：
  1. 目标上运行IIS Web服务。
  2. 存在IIS缓冲区溢出漏洞。
  3. 攻击者在目标上的权限 >= 用户。
  4. 攻击者能够访问目标上运行的某些服务（在传输层）。
• 影响：
  1. 目标上的IIS Web服务被禁用。
  2. 攻击者在目标上获得根级别权限。

TEST-NET中的防火墙（参见图4）允许外部主机连接到H0上运行的端口80上的IIS Web服务。连接到其他所有端口都被阻止。内部主机允许在网络内的任何端口上进行连接。连接限制防火墙策略见表4。

表4：连接限制防火墙策略

在表4中，“All” 表示源主机可以连接目标主机的任何端口，“None” 表示源主机被阻止访问目标主机的任何端口。根据连接限制防火墙策略，每个通用漏洞都有一些实例，这些实例被称为实例化漏洞[9]。以下是一些实例化漏洞的示例：

• IIS_bof(0,0)——从Host0对Host0进行IIS缓冲区溢出利用。
• ftp_rhosts (0,1)——从Host0到Host1的rsh信任。
• squid_port_scan (1,3)——从Host1对Host3进行的squid端口扫描。
• LICQ_remote_to_user (1,3)——Host1使用LICQ-remote-to-user漏洞在Host3上获得用户级别权限。
• local_setuid_bof (3,3)——通过利用本地缓冲区溢出漏洞，在Host3上获得根级别权限。
• netbios_ssn_nullsession (1,2)——通过执行netbios-ssn-nullsession漏洞，从Host1获得Host2上的用户级别权限。

3.2 使用GraphPlan识别攻击路径

GraphPlan是一种在巨大状态空间中寻找解决方案的搜索算法。初始网络配置、攻击者的目标和利用漏洞被视为GraphPlan的输入。在这项工作中，使用SGPlan 5.2.2 [9] 作为攻击路径识别组件。相较于其他GraphPlan的变体，如LPG-td [10] 和Metric-FF [11]，选择SGPlan，是因为它支持数值谓词或流数谓词、派生谓词和持续谓词 [23]。

3.2.1 域和事实文件

如第2.2节所述，Planner需要两个文件，即domain.pddl和fact.pddl，用于其操作。测试网络（参见图4）的domain.pddl的一个实例如表5所示。

表5：测试网络的Domain.pddl文件

domain.pddl对以下内容进行了编码：

• 网络配置——描述主机上运行的服务，例如ftp ?H等。

• 漏洞实例——指示存在的漏洞类型，例如ftp_rhost_overwrite ?H等。

• 函数——例如has_priv，用于分配权限级别。

• 利用描述——以动作规则规范的形式进行编码，其中包含四个组件：入侵者前提条件、入侵者效果、网络前提条件和网络效果。

fact.pddl编码了各种网络对象，包括主机、攻击者、防火墙等。fact.pddl的一个实例如表6所示。

表6：测试网络的Fact.pddl文件

fact.pddl编码了以下属性：

• 对象——包括不同的网络对象，如主机、防火墙等。
• 数值谓词——与domain.pddl中定义的函数相对应，例如（=（root_priv）3），表示已将根权限分配为3。
• 初始网络配置——包括在主机上运行的服务（（IIS_web_service Host0））、传输层连接性（（ssh_port_connectivity Host2 Host1））和应用层连接性（（netbios_apps_connectivity Host1 Host2））。
• 目标条件——表示为（：goal（and（=（has_priv Attacker Host3）3）））。

SGPlan使用domain.pddl和fact.pddl生成单个最短攻击路径。通过系统性修改fact.pddl，SGPlan可以识别替代的最短攻击路径。管理员可以自行决定(discretion)要更改哪些网络配置以生成新的攻击路径。通过禁用在一台主机上运行的服务，或在一对主机之间的连接性之间放置双分号（;;），可以修改fact.pddl。根据给定的domain.pddl和fact.pddl，SGPlan生成的最短攻击路径如下所示。

; 时间 0.00； 解析时间 0.00； 动作数 4
; 构建时间；度量值；规划技术
Modified-FF（强制爬坡搜索）作为子规划器
0.001：（IIS-BUFFOVFLW ATTACKER ATTACKER HOST0）[1]
1.002：（SQUID-PORT-SCAN ATTACKER HOST0 HOST3）[1]
2.003：（LICQ-REMOTE-TO-USER ATTACKER HOST0 HOST3）[1]
3.004：（LOCAL-SETUID-BUFFOVRFLW ATTACKER HOST3）[1]
1
2
3
4
5
6
7

SGPlan生成的攻击路径可以表示如下：

Attacker → IIS_bof(Att, H0)
→ squid_port_scan(H0, H3)
→ LICQ_remote_to_user(H0, H3)
→ local_setuid_bof(H3, H3)。
1
2
3
4

为了生成备用的攻击路径，将Host0和Host3之间Squid_proxy服务上的传输层连接性禁用（参见表7）。这通过在谓词squid_port_connectivity (Host0, Host3)之前放置双分号（;;）来实现。

SGPlan会放弃先前的解决方案，生成以下最短攻击路径：

; 时间 0.00 ; 解析时间 0.00; 动作数 5 ;
制造跨度(MakeSpan)；度量值；规划技术
Modified-FF（通过强制爬坡搜索作为子计划程序）
0.001：（IIS-BUFFOVFLW ATTACKER	ATTACKER	HOST0）[1]
1.002：（SSH-BUFFOVFLW ATTACKER	HOST0 HOST1）[1]
2.003：（SQUID-PORT-SCAN ATTACKER HOST1 HOST3）[1]
3.004：（LICQ-REMOTE-TO-USER ATTACKER HOST1 HOST3）[1]
4.005：（LOCAL-SETUID-BUFFOVRFLW ATTACKER HOST3）[1]
1
2
3
4
5
6
7
8

SGPlan生成的攻击路径可以表示为：

Attacker → IIS_bof(Att,H0)
→ ssh_bof(H0,H1)
→ squid_port_scan(H1,H3)
→ LICQ_remote_to_user(H1,H3)
→ local_setuid_bof(H3,H3)。
1
2
3
4
5

在下一部分中，将介绍一个定制算法，通过自动修改fact.pddl文件来枚举所有可能的非循环攻击路径。

3.3 攻击路径枚举算法

Planner需要一个域文件和一个事实文件来生成最短路径。domain.pddl文件（参见表5）编码了网络配置、漏洞实例、函数和攻击描述。fact.pddl编码了网络对象、数值谓词、初始网络配置和目标条件。如果正确修改了fact.pddl，Planner在每次运行时会生成单个最短路径。然而，为了生成所有可能的解决方案（最短路径），需要一个定制的算法，该算法将Planner作为底层模块使用。由于每个解决方案都是一个攻击路径，可以得到一组所有非循环路径。本文使用[26]中给出的定制的攻击路径枚举算法（参见算法1）。它通过自动修改fact.pddl在低层执行Planner。在[26]中，作者定义了这些算法中使用的各种数据结构。本文详细描述了算法的工作原理和复杂性分析。

3.3.1 算法描述

攻击路径枚举算法在每次迭代中自动运行Planner，以生成新路径、重复生成先前路径或不生成路径。其主要功能包括自动修改fact.pddl文件。在此过程中，它会阻塞一个或多个服务，以便生成新的解决方案（攻击路径）。

该攻击路径枚举算法的输入是domain.pddl和fact.pddl。已声明一个二维数组Path，用于以邻接矩阵形式存储新生成的攻击路径。在domain.pddl中定义的每个操作都被声明为一个结构（称为节点）。在节点结构中，有一个字段是Critical（布尔类型）。根据节点是否为关键节点，分别分配1或0。关键节点和非关键节点的定义如下：

• 关键节点：攻击路径中必须无条件阻塞的节点。
• 非关键节点：依赖于一个或多个关键节点效果的节点，如果它们不被执行，则对应的前提条件不会生成。

根据[21, 22]中给出的攻击描述，可以观察到LICQ_remote_to_user攻击仅在攻击者具有此应用程序运行的端口号时适用。这将在成功执行squid_port_scan攻击以获取不同应用程序的端口号后实现。因此，LICQ_remote_to_user 漏洞的执行必须在 squid_port_scan 之后，因为前者依赖于后者提供的端口号信息。这意味着前者是非关键节点。

类似地，local_setuid_bof攻击的描述仅需要用户级别权限作为其前提条件，并在成功执行后授予根权限。现在，有许多攻击生成用户级别权限作为其效果，如netbios_ssn_nullsession、LICQ_remote_to_user、rsh_login等。因此，local_setuid_bof攻击必须在所有这些攻击之后执行，这意味着local_setuid_bof攻击不是关键节点，即除非其前面的攻击成功执行，否则无法到达该节点。根据本文中使用的攻击集，关键和非关键节点可以如表8所示。

表8：关键和非关键漏洞利用

节点结构的其余字段如下：

• name（字符数组）：包含节点的名称（即攻击或服务）；
• source（整数）：主机ID，例如Host0为0，Host1为1；
• target（整数）：主机ID；
• flag（布尔）：用于跟踪节点（或服务）是否已被阻止。如果已阻止，则值为1，否则为0。

数据结构 以下数据结构被攻击路径枚举算法使用：

• Marker（类型：队列）：$Marker$数据结构用于存储特定攻击图的节点。当生成新的攻击路径时，根据关键$critical$和$flag$字段的值，将节点插入此队列。插入节点后，通过$flag$字段标记这些节点，以便不再插入相同的节点。为了生成下一个攻击路径，从队列中的第一个元素对应的服务将被出列并阻塞。在这里，阻塞意味着在$fact.pddl$文件中的相应谓词之前放置双分号（$;;$）来禁用服务。需要阻止以生成新攻击路径的是顶层服务。此服务被推入栈stack中。
• Stopped（类型：栈）：此数据结构维护在顶级服务下已被阻止的服务的信息。顶级服务指的是在攻击路径中某个节点在分层上位于一组节点的上方。当找到重复路径或未找到路径时，它会跟踪停止的服务。在这种情况下，算法通过从Stopped中弹出元素来回溯到先前的状态。
• Critical（类型：二维数组）：它映射与生成路径对应的关键服务。算法会检查构成新攻击路径的节点的关键字段，然后将它们插入数组中。当未生成路径时，关键服务的路径号用作索引以访问关键服务。通过将关键服务推入Stopped中，逐个阻止这些关键服务。
• false_run（类型：整数）：用作标志，用于识别即使完成了所有必要的网络修改的完整迭代后，仍未生成路径的情况。当从Stopped中弹出了顶级服务且仍未获取路径时，会发生这种情况。在此情况下，false_run的值增加为(increase to)1。弹出顶级服务是为了允许算法搜索是否存在包括顶级服务的替代路径。如果找不到这样的路径，则会增加false_run的值，算法通过得出无法获得更多唯一路径来终止。
• Path（类型：二维数组）：此二维数组用于以邻接矩阵格式存储生成的攻击路径。矩阵的列包含路径号，而行则表示包含在特定攻击路径中的节点。如果存在空间限制，也可以使用不同的数据结构，例如邻接列表。但是，基本原理将保持不变。

使用的逻辑 定制的攻击路径枚举算法 基于这样的逻辑：可能存在一些攻击，它们与另一个路径中的另一个攻击具有相同的直接前驱漏洞利用(攻击)(immediate predecessor exploit)。这种情况在图5中有所说明，可以从中得出以下观察：

• 攻击A依赖于某个其他攻击（直接前驱攻击），后者又依赖于其他依赖攻击（攻击B）。
• 如果阻止了攻击A的基本网络条件，Planner将尝试输出不包括A的路径。这对应于将攻击A推入Stopped中。
• 这将生成一条新的路径，因为仍然活动的前导攻击（直接前驱攻击）上仍可能存在其他依赖攻击（对应于攻击B）。
• 每个这样的攻击都应以迭代的方式被阻止，以打开查找新路径的可能性。这将导致所有网络的攻击路径都已被枚举出来。

然而，假设阻止一个攻击将总是导致生成新的攻击路径并不正确。这是因为Planner总是基于其算法输出最短路径。这可能导致生成一个重复路径，而不是新路径。如果找到了重复路径，则需要阻止构成重复路径的其他攻击，以便算法可以继续进行。这实际上是一种受控的蛮力方法。还可能出现未找到路径的情况。如果以某些错误的顺序阻止了攻击，就有可能出现这种情况。这需要按照被停止的服务（与攻击漏洞相关）的相反顺序重新启动它们。从本质上讲，这是一种回溯算法，它有助于逃脱在算法执行过程中可能出现的不可行解决方案。

在下一小节中，已提供了攻击路径枚举算法的执行实例，展示了不同数据结构的值如何在每次运行中变化。

算法1：攻击路径枚举算法

3.4 攻击路径枚举算法的执行过程

正如在第3.2.1节中所述，当未修改fact.pddl文件时，Planner输出的第一个最小攻击路径是Path0。

Path0:
Attacker→ IIS_bof(Att, H0)
→ squid_port_scan(H0, H3)
→ LICQ_remote_to_user(H0, H3)
→ local_setuid_bof(H3, H3)

由于生成的最小攻击路径是新的，因此必须将其以邻接矩阵的形式插入到2-D数组Path中。这在表9中显示。

随着攻击路径枚举算法继续生成下一个最小攻击路径，不同数据结构的值会以以下方式发生变化：

1. Stopped← φ [参考算法1中的第32行]
2. Marker←{IIS_bof(0, 0), squid_port_scan(0, 3)} [参考算法1中的第35行]
3. Critical [idx1][idx2] [参考算法1中的第36行]
4. 出队列(Marker)⇒出队列←{IIS_bof(0, 0)} [参考算法1中的第41行]
5. Block←{IIS_bof(0, 0)} [对应于fact.pddl中的“阻止IIS_port_connectivity攻击者Host0”（参考表6）]。
6. Marker←{squid_port_scan(0, 3)}
7. Stopped←{IIS_bof(0, 0)} [参考算法1中的第43行]

具有当前值集的情况下，攻击路径枚举算法会对fact.pddl文件进行必要的修改并运行Planner。结果没有生成路径。

要生成路径（可以是新路径或重复路径），算法执行以下操作：

1. Service← 弹出(Stopped) ⇒ 弹出(IIS_bof(0, 0)) [参考算法1中的第5行]
2. 重新启动(IIS_bof(0, 0)) [对应于fact.pddl中的“解除阻止IIS_port_connectivity攻击者Host0”（参考表6）]
3. idx1 ← 0，因为弹出的服务(IIS_bof(0, 0))属于Path0 [参考算法1中的第7行]
4. idx2 ← 0，因为弹出的服务(IIS_bof(0, 0))是Path0中的第0个关键节点 [参考算法1中的第8行]
5. idx2 ← idx2 + 1 ⇒ idx2 ← 1 [参考算法1中的第10行]
6. Service← Critical[0][1]←{squid_port_scan(0, 3)} [参考算法1中的第11行]
7. Block← {squid_port_scan(0, 3)} [对应于fact.pddl中的“阻止squid_port_connectivity Host0 Host3”（参考表7）]
8. Stopped← {squid_port_scan(0, 3)} [参考算法1中的第13行]

以上一组值由算法用于运行Planner。结果生成了新的路径，称为Path1：

Path1:
Attacker → IIS_bof(Att, H0)
→ ssh_bof(H0, H1)
→ squid_port_scan(H1, H3)
→ LICQ_remote_to_user(H1, H3)
→ local_setuid_bof(H3, H3)

这个新生成的路径（Path1）以表10所示的方式插入到2-D数组Path中。

由定制的攻击路径枚举算法生成的其余最小攻击路径如下：

Path2:
Attacker → IIS_bof(Att, H0)
→ netbios_ssn_nullsession(H0, H2)
→ squid_port_scan(H2, H3)
→ LICQ_remote_to_user(H2, H3)
→ local_setuid_bof(H3, H3)

Path3:
Attacker → IIS_bof(Att, H0)
→ ftp_rhost_overwrite(H0, H1)
→ rsh_login(H0, H1)
→ squid_port_scan(H1, H3)
→ LICQ_remote_to_user(H1, H3)
→ local_setuid_bof(H3, H3)

Path4:
Attacker → IIS_bof(Att, H0)
→ ssh_bof(H0, H1)
→ netbios_ssn_nullsession(H1, H2)
→ squid_port_scan(H2, H3)
→ LICQ_remote_to_user(H2, H3)
→ local_setuid_bof(H3, H3)

Path5:
Attacker → IIS_bof(Att, H0)
→ ftp_rhost_overwrite(H0, H1)
→ rsh_login(H0, H1)
→ netbios_ssn_nullsession(H1, H2)
→ squid_port_scan(H2, H3)
→ LICQ_remote_to_user(H2, H3)
→ local_setuid_bof(H3, H3)

Path6:
Attacker → IIS_bof(Att, H0)
→ netbios_ssn_nullsession(H0, H2)
→ ssh_bof(H2, H1)
→ squid_port_scan(H1, H3)
→ LICQ_remote_to_user(H1, H3)
→ local_setuid_bof(H3, H3)

Path7:
Attacker → IIS_bof(Att, H0)
→ netbios_ssn_nullsession(H0, H2)
→ ftp_rhost_overwrite(H2, H1)
→ rsh_login(H2, H1)
→ squid_port_scan(H1, H3)
→ LICQ_remote_to_user(H1, H3)
→ local_setuid_bof(H3, H3)