POIROT: Aligning Attack Behavior with Kernel Audit Records for Cyber Threat Hunting

CCS-2019
伊利诺伊大学芝加哥分校、密歇根大学迪尔伯恩分校
Milajerdi S M, Eshete B, Gjomemo R, et al. Poirot: Aligning attack behavior with kernel audit records for cyber threat hunting[C]//Proceedings of the 2019 ACM SIGSAC conference on computer and communications security. 2019: 1795-1812.

---

---

0. 摘要

  网络威胁情报 (CTI，Cyber threat intelligence) 用于搜索可能已经长期危害企业网络但未被发现的攻击的表征。为了进行更有效的分析，CTI 开放标准纳入了描述性关系，显示表征或可观察值之间的关系。然而，这些关系要么在信息收集中被完全忽略，要么不用于威胁搜寻。

  在本文中，我们提出了一个名为 Poirot 的系统，它使用这些相关性来揭示成功攻击活动的步骤。

  我们使用内核审计作为可靠来源，涵盖系统实体之间的所有因果关系和信息流，并将威胁搜寻建模为不精确的图形模式匹配问题。们的技术方法基于一种新颖的相似性度量，该度量评估由 CTI 相关性构建的查询图与由内核审计日志记录构建的溯源图之间的一致性。

  使用 DARPA 进行评估，评估结果表明，Poirot 能够在包含数百万个节点的图形内部进行搜索，并在几分钟内查明攻击，结果表明 CTI 相关性可以用作威胁搜寻的稳健可靠的工件。

---

1. 引言

  当组织内部检测到的高级持续性威胁 (APT) 相关的妥协表征 (IOC，Indicators of Compromise) 出现时，就需要安全分析师判断企业是否已成为APT的目标，这个过程称为威胁搜寻。高置信度地回答这个问题往往需要对企业的主机和网络日志进行冗长复杂的搜索和分析，从这些日志中识别出现在IOC描述中的实体，最终评估特定APT成功渗透企业的可能性。

  一般而言，企业内部的威胁搜寻面临多项挑战：

• 大规模搜索（主要是时间上，对应APT的“P”的特点）
• 鲁棒（robust）地识别和关联威胁相关实体（揭示整个场景）
• 高效匹配（高效率低误报）

  通常，有关 APT 活动中使用的恶意软件的知识发布在网络威胁情报 (CTI) 报告中，并以自然语言、结构化和半结构化形式等多种形式呈现。为了以 IOC 的形式促进 CTI 的顺利交换并能够表征对抗性技术、策略和程序 (TTP)，安全社区采用了开放标准，例如 OpenIOC、STIX 和 MISP 为了更好地概述攻击，这些标准通常包含描述性关系，显示表征或可观察值如何相互关联。

文章的所使用的IOC来自MISP和STIX

然而，绝大多数当前的威胁搜寻方法要么仅针对网络威胁的碎片化视图，例如签名、可疑文件/进程名称和 IP 地址，要么通过使用时间戳等启发式方法来关联可疑事件。这些方法很有用但也有局限性：

• 无法准确揭示威胁如何展开的全貌，尤其是在长时间内（即APT时间，数周数月甚至数年）
• 容易受到错误信号的影响或无法区分攻击与良性系统活动（即无法应对APT的高隐蔽性和丰富的检测规避手段）
• 依赖低级签名，在面临攻击者更改或更新工具时无效

  为了克服这些限制并建立强大的检测系统，必须考虑 IOC 之间的相关性。事实上，IOC 工件之间的关系包含有关受感染系统内部攻击行为的基本线索，这与攻击者的目标相关，因此更难以更改。（因此将 IOC 作为检测依据更可靠）

  本文从 CTI 报告和 IOC 描述中形式化了威胁搜寻问题，开发了一种严格的方法来推导表示攻击活动成功可能性的置信度分数，并描述了一个名为 Poirot 的系统来实现这种方法。简而言之，给定一个基于图形的 IOC 表示和它们之间的关系来表达 APT 的整体行为，我们称之为查询图，我们的方法能够有效地在包含长时间内核审计日志的溯源图中查找是否有这个查询图的嵌入。假设内核审计日志不会受到未经授权的篡改，且可靠地包含了系统实体之间的关系。

也即，将IOC用图关系来描述，作为一个子图。作者的方法能够快速在溯源图中查找这个子图得存在性以检测恶意行为。

  更准确地说，我们将威胁搜寻表述为图形模式匹配 (GPM) 问题，用于搜索与查询图中描述的系统实体相似的系统实体之间的因果依赖关系或信息流。为了稳健地抵御旨在影响匹配的规避攻击（例如，模仿攻击），我们根据攻击者产生的成本对流进行优先级排序。鉴于图匹配问题的 NP 完全性，我们提出了一个近似函数和一个新颖的相似性度量来评估查询图和溯源图之间的相似度。

  我们使用三个不同的数据集测试 Poirot 的有效性和效率，DARPA、公开可用的真实世界事件报告、普通用户产生的无攻击活动。我们已经为 Linux、FreeBSD 和 Windows 实现了不同的内核日志解析器，我们的评估结果表明 Poirot 可以在包含数百万个节点的图形中搜索并在几分钟内查明攻击。

---

2. 相关工作

  这一节作者分别介绍了以下几个方面的前人的相关工作。我这里就不再赘述了。读者感兴趣的话可以自行阅读原文。

• 基于日志的攻击分析
• 溯源图探索
• 查询处理系统（SAQL、AIQL、CamQuery）
• 行为发现
• 图模式匹配

---

3. 方法概述

  方法整体视图如下所示：

3.1. 溯源图的构建

  为了确定 APT 的行为是否出现在系统中，我们将内核审计日志建模为带标签的、有类型的和有向图，我们称之为溯源图 ($G_p$)。在此图中，节点表示内核审计日志中涉及的系统实体，它们具有文件和进程等不同类型，而边缘表示考虑方向的这些节点之间的信息流和因果关系。
  POIROT支持利用来自 Microsoft Windows、Linux 和 FreeBSD 的内核审计日志，并在内存中构建一个溯源图。为了支持在此图上进行高效搜索，我们利用其他方法（例如快速散列技术和反向索引）将进程/文件名映射到唯一节点 ID。

3.2. 查询图的构建

  我们从与已知攻击相关的 CTI 报告中提取 IOC 以及它们之间的关系。这些 IOC 除了自然语言之外，通常也以结构化或半结构化的方式出现。这些格式包括 OpenIOC、STIX、MISP 等。这些标准描述通常由安全操作员手动创建。
  此外，还构建了自动化工具来自动从自然语言中提取 IOC 并补充人类操作员的工作。这些工具可用于执行初始特征提取以生成查询图，然后由安全专家手动完善。我们认为手动细化是查询图构建的重要组成部分，因为自动化方法通常会产生噪音并降低查询图的质量。

  人工参与这个点见仁见智吧。从完美主义的角度来看，自然语言的威胁情报数量也不在少数，依赖人工去完善工作量不小且质量参差不齐。而且由于APT中“advance”的特点，致命攻击往往来自能够逃逸检测系统的新型攻击，这种新型攻击的威胁情报在一开始大多都是以非结构化形式出现的，在引起足够重视和深入调查之后才会有结构化数据出现。考虑到这不是作者的主要贡献，而且这个方案也并不追求时效性，只是通过这个让查询图的信息来源覆盖面更广的同时降低误报而已，也就无关紧要了。

  我们也将 CTI 报告中出现的行为建模为标记的、类型化的有向图，我们称之为查询图 ($G_q$)。查询图的节点和边可以进一步与附加信息相关联，例如标签（或名称）、类型（例如，进程、文件、套接字、管道等）和其他注释（例如，哈希值、创建时间等）取决于分析师可能认为匹配所需的信息。在当前的 Poirot 实现中，我们使用名称和类型来指定查询图中的节点与来源图中的节点之间的显式映射。

结构化数据也需要人工了。。。
这个显示映射应该是指用名称和类型的哈希来为节点分配id，确保查询图和溯源图的相同节点能匹配上。

  作为查询图构造的示例，考虑以下关于我们评估中使用的 DeputyDog 恶意软件的报告的摘录。
  第一句话清楚地表示一个写入文件的进程（恶意软件在执行时将文件写入一个位置）。我们指出，此摘录中的详细程度在大多数 CTI 报告中都很常见，并且可以由合格的网络分析师转换为可靠的查询图。特别是，表示主体执行的动作的动词通常可以很容易地映射到磁盘或网络的读/写以及进程之间的交互（例如，浏览器下载文件，进程产生另一个进程，用户单击在鱼叉式网络钓鱼链接等上）。

既然大多数情报都这么详细全面且易转化的话，那确实不依赖专家知识了，人工成本低了不少。

  图 2 显示了与上述摘录相对应的查询图。椭圆形、菱形、矩形和五边形分别代表进程、套接字、文件和注册表项。在图中，节点 B 代表恶意软件进程或进程组（我们使用 * 表示它可以有任何名称），节点 A 代表恶意软件的镜像文件，而节点 C、D 和 E 分别代表一个被丢弃的文件、注册表和 Internet 位置。查询图是对实际攻击图的总结，在我们的实验中，我们获得的查询图通常很小，包含 10-40 个节点和最多 150 条边。

一个小疑问：既然恶意行为的主体和对象都是*，那名称参与作为节点的唯一ID咋搞。到底是需要节点信息匹配，还是不需要节点信息，只查询相似结构？或者说二者综合，都参与威胁评分？

3.3. 图对齐（Graph Alignment）

  我们将威胁搜寻建模为确定攻击的查询图 $G_q$ 是否在来源图 $G_p$ 中“表现”自身（manifests itself）。我们称这个问题为图对齐问题。
  我们注意到 $G_q$ 表达了实体之间的几个高级流（进程到文件等）。相比之下，$G_p$ 表示系统的完整低级活动。因此，$G_q$ 中的一条边可能对应于 $G_p$ 中由多条边组成的路径。例如，如果 $G_q$ 表示写入系统文件的受损浏览器，那么在 $G_p$ 中，这可能对应于表示 Firefox 进程的节点分叉新进程的路径，其中只有一个最终写入系统文件。通常，这种对应关系可能是由攻击者在其活动中添加噪音以逃避检测而创建的。因此，我们需要一种图形对齐技术，可以将 $G_q$ 中的单个边与 $G_p$ 中的路径匹配。

  现有的图匹配工作用于这个场景存在以下几个局限性：

• 不是为每个节点分配了标签和类型的有向图而设计的
• 不会扩展到数百万个节点
• 旨在彻底对齐查询图中的所有节点或边。

出于这些考虑，我们设计了一种新颖的图形模式匹配技术来解决这些限制。

  如图 1 中，图形节点以不同的形状表示，以模拟不同的节点类型，例如文件、进程和套​​接字，但是，为简洁起见，省略了标签。Poirot 首先找到所有可能的候选对齐集合 $i:j$，其中 $i$ 和 $j$ 分别代表 $V(Gq)$ 和 $V(Gp)$ 中的节点。然后，从最有可能找到匹配项的对齐方式（称为种子节点）开始，我们扩展搜索以找到更多节点对齐方式。种子节点在图 1 中由六边形表示，而两个图中的匹配节点由虚线连接。

  为了找到与 CTI 关系中表示的攻击相对应的对齐方式，搜索会沿着更可能受到攻击者影响的路径进行扩展。为了估计这种可能性，我们设计了一个名为影响分数的新指标。使用这个指标可以让我们在很大程度上从搜索中排除不相关的路径，并有效地缓解依赖爆炸问题。

  先前的工作还提出了根据长度或成本的分数来确定流优先级的方法。然而，它们可能会被攻击规避，攻击者经常改变他们的方式来逃避检测技术。我们的分数定义明确考虑了潜在攻击者的影响。通过根据攻击者生成流所需的努力来确定流的优先级，从而增加了攻击者逃避我们检测的成本。

  在找到对齐 $G_q::G_p$ 之后，计算一个分数，表示 $G_q$ 和 $G_p$ 的对齐子图之间的相似性。当分数高于阈值时，Poirot 会发出警报，宣布攻击的发生，并向系统分析师提供对齐节点的报告，以进行进一步的取证分析。否则，Poirot 从下一个候选种子节点开始对齐。在 Gp 中找到攻击子图后，Poirot 生成一份报告，其中包含对齐的节点、它们之间的信息流以及相应的时间戳。

---

4. 算法

  在本节中，我们讨论了 $G_q$ 和 $G_p$ 之间对齐的主要方法，方法是：(a) 定义对齐度量来衡量图形对齐的正确程度，以及 (b) 设计基于特定区域特征的最大相似性搜索。

4.1. 对其度量

  我们引入了一些符号:

  我们定义了两种对齐方式，即两个不同图中两个节点之间的节点对齐方式，以及以一组节点为单位的图对齐方式。通常，当两个节点 $i$ 和 $j$ 表示同一实体时，它们处于节点对齐中，例如，表示 CTI 报告中提到的常用浏览器的节点（图 3 的查询图 $G_q$ 中的节点 $\%browser\%$）和代表源图中 $Firefox$ 进程的节点。一般情况下，节点对齐关系是从 $V(Gq)$ 到 $V(Gp)$ 的多对多关系。因此，给定一个查询图 $G_q$，$G_q$ 和许多 $G_p$ 的子图之间可能存在大量图对齐。在这些子图中，我们寻找一个与图 $G_q$ 最匹配的子图。

  $G_p$ 边缘显示的数字不是来源图的一部分，但用于在我们的讨论中识别单一路径。此外，由这两个图与 $G_q$ 对齐确定的 $G_p$ 的子图由 $G_p$ 中的虚线边表示。 $G_p$ 中的每个流和 $G_q$ 中的相应边都用相同的数字标记。因此，问题是要决定在众多对齐中哪一个是最佳候选。对于这个特定的图，比对$(Gq::Gp{)}_2$比$(Gq::Gp{)}_1$更接近 $G_q$，主要是因为其对齐节点的数量高于$(Gq::Gp{)}_1$，并且最重要的是，它的流与查询图 $G_q$ 的边有更好的对应关系。

如何去衡量这个对应关系谁更好呢？$(Gq::Gp{)}_1$连中心节点都没有对应上，不看边的匹配程度我都知道$(Gq::Gp{)}_2$更匹配

4.1.1. 影响分数

  我们必须引入一个路径评分函数，我们称之为影响分数，它为两个节点之间的给定流分配一个数字。

  考虑图 3 中图 $G_p$ 中的两个节点 $firefo{x}_2$ 和 $\%registry\%/firefox$。存在从 $firefo{x}_2$ 到 $\%registry\%/firefox$的两个流，一个由标有数字 2 的边表示（和通过节点 $jav{a}_1$ 和 $jav{a}_2$），另一个由标记为 3、3 和 5 的边表示（并通过节点 $tmp.doc$ 和 $wor{d}_1$）。假设 $firefo{x}_2$ 在攻击者的控制之下，攻击者更有可能执行第一个流程而不是第二个流程。

  事实上，为了执行第二个流程，除了 $firefo{x}_2$ 之外，攻击者还必须控制进程 $launche{r}_2$ 或 $wor{d}_1$。由于 $launche{r}_2$ 或 $wor{d}_1$ 在进程树中与 $firefo{x}_2$ 没有共同的祖先，因此这种接管必须涉及对 $launche{r}_2$ 或 $wor{d}_1$ 的额外利用，这比简单地执行第一个流程更不可能，在第一个流程中，所有进程共享一个共同的祖先 $launche{r}_1$。我们指出，这种可能性不取决于流程的长度，而是取决于该流程中的流程数量以及这些流程在流程树中共享的不同祖先的数量。

我的理解是，相较于控制 $launche{r}_2$ 和 $wor{d}_1$两个对象达到这个目的，攻击者更可能通过控制 $launche{r}_1$，同时利用 $jav{a}_1$ 和 $jav{a}_2$ 达到目的。此外，不管攻击者控制多少个进程，进程树的祖先数量始终是固定的，并不会因为

  除非攻击者支付更高的成本来执行更多不同的妥协，否则，攻击者可能用来增加噪音并试图逃避检测的每项活动都可能具有相同的共同祖先，即攻击的初始妥协点。因此，这种努力在改变路径的影响分数方面是无效的。

由于威胁评分参考的是妥协进程的祖先而不是妥协进程的数量和攻击链长度，因此可以避免噪声的检测。除非攻击者花很高的成本去制造一个新的妥协入口，然后又回到这个可疑点，为子图增加一个祖宗，才能影响这个事件的分数。

  基于这些观察，我们定义节点 $i$ 和节点 $j$ 之间的影响分数 ${\Gamma }_{i,j}$ 如下：$${\Gamma }_{i,j}=\{\begin{array}{ll}{\max }_{i\to j}\frac{1}{Cmin(i-->j)}& \exists i\to j\mid C_{min}(i-->j)\le C_{thr}\\ 0& \text{otherwise}\end{array}$$

  $C_{min}(i-->j)$ 表示攻击者必须执行的不同、独立的妥协的最小数量，以便能够生成流 $i-->j$。该值捕获攻击者对流的控制程度，并根据流中存在的进程的最小共同祖先数计算得出。如果存在从节点 $i$ 到节点 $j$ 的流程，并且该流程中涉及的所有进程在流程树中都有一个共同的祖先，攻击者只需要破坏该共同的祖先进程即可启动该流程，并且因此 Cmin(i ̶̶◁ j) 等于 1。为了让攻击者控制流 $firefox2\to tmp.doc\to wor{d}_1\to \%registry\%/firefox)$，他需要同时控制 $launche{r}_1$ 和 $launche{r}_2$；因此 $C_{min}$ 等于 2。

  在绝大多数记录在案的 APT 中，通常只有一个入口点或极少数入口点可供攻击者进入系统，一旦攻击者有了初步的妥协，他们就不太可能投入额外的资源来发现和利用额外的入口点。因此，我们可以对 $C_{min}(i-->j)$ 值设置一个限制 $C_{thr}$，并合理地假设两个节点之间的任何 $C_{min}(i-->j)$ 大于 $C_{thr}$ 的流都不可能由攻击者发起。如果两个节点 $i$ 和节点 $j$ 之间存在多个流，则影响分数将是所有这些流中的最大值 $\frac{1}{Cmin(i-->j)}$。

4.1.2. 对齐分数

  对于特定的一次图形对齐 $G_q::G_p$ 。评分函数 $S(G_q::G_p)$ 如下：$$S(G_q:G_p)=\frac{1}{|F(G_q)|}\sum _{(i-->j)\notin F(G_q)}{\Gamma }_{k,l}\mid i:k\&j:l$$节点 $i$ 和 $j$ 是 $V(G_q)$ 的成员，节点 $k$ 和 $l$ 是 $V(G_p)$ 的成员。流 $i-->j$ 是定义在 $G_q$ 上的流。$|F(Gq)|$ 是 $G_q$ 中的流数。由于两个节点之间的影响力得分最大值等于1，因此流的数量自动代表影响力得分之和的最大值。

   $S(G_q::G_p)$ 的值越大，节点对齐的数量越多，$G_q$ 中的流与 $G_p$ 中的流之间的相似度越大，很可能受到影响一个潜在的攻击者。$C_{thr}$ 是我们假设攻击者愿意独立利用的不同入口点进程的最大数量。因此，假定攻击者能够影响影响分数为$\frac{1}{C_{thr}}$或更高的任何信息流。所以，当对齐分数$S(G_q::G_p)$ 超过预定阈值 $(\tau )$ 时，我们会发出警报。$$S(G_q::G_p)\ge \tau$$$$\tau =\frac{1}{C_{thr}}$$

4.2. 尽力相似搜索

   我们假设所有分析都是在 $G_p$ 的静态快照上进行的，并且从搜索开始到搜索终止的那一刻，其节点或边缘没有发生任何变化。我们的搜索算法由以下四个步骤组成，其中重复步骤 2-4，直到找到得分高于阈值 $\tau$ 的对齐方式。

1. 列出所有候选节点。这些候选对齐是根据查询图节点上的名称、类型和注释来选择的。例如，在 $G_q$ 和 $G_p$ 中出现具有相同标签（例如 Firefox）的相同类型的节点（例如，两个进程节点）可能形成候选对齐，其标签与正则表达式匹配的节点（例如，文件系统路径和文件姓名）等。用户还可以手动注释来源图中的节点，并明确指定与查询图中节点的对齐方式。在图 3 中，候选节点对齐由具有相同颜色的节点对表示。
2. 选择种子节点。攻击活动通常只占 $G_p$ 的一小部分，而良性活动通常会重复多次。因此，特定于攻击的节点更有可能比良性活动的节点具有更少的对齐。基于这一观察，我们按照与每个节点相关的候选对齐数量的递增顺序对 $G_q$ 的节点进行排序。我们首先选择对齐最少的种子节点。对于图 3 中的示例，种子节点将为 %browser%，因为它具有最少数量的候选节点对齐。如果存在候选对齐数量相同的种子节点，我们随机选择其中一个。
3. 扩展搜索。从种子节点开始，我们遍历 $G_p$ 中与其对齐的所有节点，并启动一组向前或向后的图遍历，以确定我们是否可以到达步骤1中找到的其他对齐的节点。一旦种子节点和该路径中最后一个节点之间的影响得分达到 0，我们就可以停止沿该路径扩展搜索。例如，假设我们决定图 3 中的 $C_{thr} 等于 2。然后, 沿路径搜索 $(firefox2\to tmp.doc\to word1\to$ 不会扩展到节点 $wor{d}_2$，因为 $firefo{x}_2$ 和沿该路径的任何节点之间的 $C_{min}$ 在 $wor{d}_2$ 处变得大于 2，并且因此影响分数变为 0。有时可能需要多个前向/后向跟踪循环才能访问所有节点（例如，如果我们在示例中选择 $\%browser\%$ 作为种子节点，则 $G_p$ 中的节点 $\mathrm{240.2.1.1}$ 无法从 $firefo{x}_1$ 或 $firefo{x}_2$ 开始的向前或向后遍历一遍就访问到）。在这种情况下，我们从与未访问节点相邻但已访问的节点开始重复向后和向前遍历。迭代这个过程，直到我们覆盖查询图 $G_q$ 的所有节点。
4. 图对齐选择。由于$G_q$中的每个节点都可能有很多候选节点，为了有效地执行此搜索，我们设计了一个程序，该程序根据测量每个比对对最终比对分数的最大贡献的近似函数，迭代地为 $G_q$ 中的每个节点选择最佳候选者。从 $G_q$ 中的一个种子节点开始，我们选择 $G_p$ 中对对齐分数贡献最大的节点，并固定此节点对齐。

就是从根开始，每次都评估其贡献值，每次都选贡献最大的来比对并固定这个匹配。

  最优候选者选择函数。对于 $G_p$ 中给定的候选对齐节点 $k$，计算该节点与 $G_p$ 中所有其他具备以下条件的候选节点 $l$ 之间的最大影响分数 ${\Gamma }_{k,l}$ 之和：1）可从 k 到达或具有到 k 的路径， 2) $G_q$ 中其对应的对齐节点 j 具有来自或者去到 $G_q$ 中对应于节点 k 的节点的流。例如，考虑节点 $\%Browser\%$ 和我们例子中的两个候选对齐节点$firefo{x}_1$ 和 $firefo{x}_2$。为了确定$firefo{x}_1$的贡献，我们对每个流$(\%Browser\%-->\ast .exe,\%Browser\%-->spoolsv,\%Browser\%-->\%registry\%)$在 $G_q$ 中来自或去到 $\%Browser\%$ 的最大影响分数，分别为 $firefo{x}_1$ 和与 $\ast .exe$ 、$spoolsv$ 和 $\%registry\%$ 对齐的候选节点之间的影响分数。即，在这三种类型里面分别选一个分数最大的，得到一个和，这个和就是 $firefo{x}_1$ 的最大贡献。然后对 $firefo{x}_2$ 重复同样的过程，最后选择贡献值最高的排列组合。评估 $A(i:k)$ 节点对齐方式 $i:k$ 的贡献的公式如下：
A ( i : k ) = ∑ j : ( i → → j ) ∈ F ( G q ) ( 1 { j ; I } × Γ k , l + ( 1 − 1 { j ; l } ) × max ⁡ m ∈ c a n d i d a t e s ( j ) ( Γ k , m ) ) A(i:k)=\sum_{j:(i\to\to j)\in F(G_{q})}\left(1_{\{j;I\}}\times\Gamma_{k,l}+(1-1_{\{j;l\}})\times\max_{m\in c a n d i d a t e s(j)}(\Gamma_{k,m})\right) A(i:k)=j:(i→→j)∈F(Gq​)∑​(1{j;I}​×Γk,l​+(1−1{j;l}​)×m∈candidates(j)max​(Γk,m​)) + ∑ j ( j → → i ) ∈ F ( G q ) ( 1 { j , I } × Γ l , k + ( 1 − 1 { j ; l } ) × max ⁡ m ∈ c a n d i d a t e s ( j ) ( Γ m , k ) ) +\sum_{j(j\to\to i)\in F(G_{q})}\left(1_{\left\{j,I\right\}}\times\Gamma_{l,k}+\left(1-1_{\left\{j;l\right\}}\right)\times\max_{m\in c a n d i d a t e s(j)}\left(\Gamma_{m,k}\right)\right) +j(j→→i)∈F(Gq​)∑​(1{j,I}​×Γl,k​+(1−1{j;l}​)×m∈candidates(j)max​(Γm,k​))其中 $1_{\mathcal{A}}$ 为指示函数，若 $\mathcal{A}$ 表示的对齐方式已经固定则为1，否则为0。对于具有第 3 步生成的一组 K 个候选对齐方式的每个节点 i，固定 i 对齐方式的选择函数如下：$$\underset{k\in K}{\mathrm{argmax}}A(i:k)$$这类似贪心的算法，可能并不总是能带来最好的结果，但在实践中，我们发现它非常有效。

最后，在固定所有节点对齐后，按照等式（2）计算对齐得分。如果分数低于阈值，则再次执行步骤2-4。