NETPLIER : 一款基于概率的网络协议逆向工具（一）理论

本文系原创，转载请说明出处：信安科研人
关注微信公众号 信安科研人 获取更多网络安全学术技术资讯

今日介绍一篇发表在2021 NDSS会议上的一项有关协议逆向的工作：

@

目录

• 1 网络协议逆向工程简介
  • 1.1 协议逆向工程的主流技术
  • 案例
  • 1.2 基于对齐的聚类
  • 1.3 基于标识的聚类
  • 1.4 NETPLIER的构思
• 2 NETPLIER——系统设计
  • 2.1 预处理
  • 2.2 关键字段候选列表生成
    • 2.2.1 序列对齐
    • 2.2.2 生成字段
  • 2.3 基于概率的关键字段识别
  • 2.4 迭代对齐和聚类
  • 2.5 格式和状态机推理
• 3 核心——基于概率的关键字段识别
  • 3.1 随机变量和概率约束
    • • 断言
      • 约束
  • 3.2 确定先验观察概率
    • 3.2.1 消息相似性约束（M（f,c））
    • 3.2.2 远程耦合约束（R(f,c)）
    • 3.2.3 结构一致性约束（S(f，c)）
    • 3.2.4 维度约束（D（f））
    • 3.2.5 规则化
  • 3.3 概率推理
    • 3.3.1 因子图
• 4 总结

1 网络协议逆向工程简介

网络协议逆向工程可以用来解决很多网络空间安全中的问题，比如恶意代码的流量识别、FUZZ中的用例生成，静态/符号漏洞扫描、攻击检测和恶意软件行为分析，这需要对网络协议进行准确建模。

1.1 协议逆向工程的主流技术

现有的协议逆向工程技术分为几类。
第一类利用程序分析。通过分析应用程序实现的语义信息（例如，怎样访问输入缓冲区），这些技术可以在逆向工程中实现高精度。然而，这些技术中的大多数都需要访问程序二进制文件，这在实践中通常是不可行的。例如，某些物联网固件由于其保护机制而无法访问；如果二进制文件被打包或混淆，则很难进行动态分析。即使客户端应用程序的二进制文件可用，它在服务器端的对应物也很难获得。
因此，另一类侧重于使用网络流，这些痕迹可以通过网络窃听获得。基于网络跟踪的逆向工程有两种主要技术：基于对齐的：例如，PIP、ScritGen 和 Netzob ，和基于token：例如，Veritas 和 Discoverer。前者利用各种序列对齐算法来对齐消息对并计算相似度分数，基于这些分数对消息进行聚类，然后通过分析集群内消息的共性来导出格式。 然而，消息内容的多样性大大降低了对齐的质量，给下游的分析带来了困难。基于token的方法建议在对齐之前首先标记消息（例如，到文本字段和二进制字段）以减少变化。 然而，这些技术通常需要分隔符来识别token（对于二进制协议可能不存在）或生成过多的集群，因为token化是基于启发式的。 也就是说，制定临时规则用于执行标记，并且这些规则在许多情况下可能不成立。 现有技术不能对这种不确定性进行建模，因此通常会产生错误的结果。

案例

以DNP3协议为例：

深色的是服务器发送的数据报文，浅色的是客户端。每个数据包都由几个部分组成，如上图的第一行列表所示，ID、Time等等，这些被称作为关键词keywords。

发送与接收数据包整个协议状态的演变过程，可以用协议状态机表示。协议程序处理发送来的数据包的过程是依据其程序所定义的协议结构，对数据包按其所定义的关键词一层层的进行拆解。

上图中，mc0 、mc1 、mc2 、mc4是客户端主动发起的请求，服务端发送的对应的确认数据报文为ms0、ms2、ms3以及ms4。

建立连接后，服务端就可以发送如ms1、ms5、ms6的写功能数据包，也可以发送如ms7的读功能数据包，而客户端对应的响应包为mc1、mc5、mc6、mc7。

协议逆向工程的主要目标是推断协议的语法和语义。 协议逆向工程的第一步是将相同类型的消息分组到一个集群中。 聚类是一个关键步骤，因为它的结果决定了进一步的格式和状态机推断的准确性。 现阶段的研究通常分别考虑来自不同方向的消息，以来自客户端的消息为例（mc0 -mc7）并讨论现有技术和我们的技术如何进行聚类。理想的聚类结果是将消息 mc0 、 mc2 、 mc3 、 mc4 放入一个集群，并将消息 mc1 、 mc5 、 mc6 和 mc7 放入另一个集群。

1.2 基于对齐的聚类

序列比对算法最初用于生物学中，用于排列 DNA、RNA 和蛋白质序列以识别相似区域。 这个想法被大量现有的基于网络跟踪的协议逆向工程方法所借鉴，例如工具 PIP、ScriptGen 和 Netzob，他们使用成对序列比对算法来比对每对消息，并通过比对结果计算相似度分数，在构建相似度矩阵后，具有最高相似度的消息或者集群通过聚类算法递归合并，例如 UPGMA，然后从聚类结果中导出协议格式和状态机。

基于对齐的聚类方法假设消息具有相同的类型，如果它们具有相似的值序列。 然而，这个假设并不总是正确的。 对于相同类型的消息，它们可能具有相同字段的不同值。 对于不同类型的消息，它们可能共享一些公共字段并具有相同的值。

图 2a 中可以看到，消息对(mc0 , mc2)和(mc0 , mc1)的对齐结果。 红色字节是对齐在一起的相同值。 我们可以看到，虽然 mc0 和 mc2 属于同一类型，但它们的相似度低于不同类型的 mc0 和 mc1 （用阴影表示）。基于这个弱假设，聚类结果是有问题的。

图 2b 显示了 Netzob 的聚类结果。 它生成两个集群，并且都包含不同类型的消息。 基于错误的聚类结果，进一步的格式和状态机推断也会不准确。

基于对齐的聚类方法的另一个限制是，当使用 UPGMA 等算法时，它需要一个相似度阈值来决定哪些聚类应该在递归聚类步骤中合并在一起。 聚类结果对这个阈值很敏感，不同的协议应该使用不同的阈值。 然而，当对未知协议进行反向工程时，如果没有基本事实，很难计算出最佳阈值。 通常，我们只能使用从其他经过充分研究的协议训练的通用阈值。 因此，聚类准确性可能会很垃圾。

1.3 基于标识的聚类

基于标识的聚类方法将消息按标识拆分，然后按特定标识值或标识类型对消息进行分组。大多数方法如工具 ASAP 、Veri-tas 、Prisma 和 ProDecoder ，都依赖于预定义的分隔符或 n-gram 将消息拆分为标记，然后搜索具有最频繁值的值，可进一步用于对消息进行聚类。

另一种基于标识的聚类策略是使用标识类型模式。Discoverer 是最先进的基于标识的方法，使用标识类型模式进行初始聚类，然后结合代表性标记值和序列比对算法来改进聚类结果。

图 3a 显示了 Discoverer 的标记化结果。它将具备可打印 ASCII 值的连续字节视为文本标记，利用相同类型的网络消息具有相同的二进制序列和文本字符串混合的观察结果。因此 mc2 、 mc3 和 mc7 中的第二到第四个字节被标记为文本标记 T，而其他单个字节被标记为二进制标记 B。

标记化后，它观察到两种不同的标记模式，序列“BBBB ... B” 表示 mc0 、 mc1 、 mc4 等，序列“BTBB ... B” 表示 mc2 、 mc3 和 mc7 。两种模式的差异以红色突出显示。

因此，Discoverer 会生成两个初始集群，如图 3b 所示。然后它通过潜在代表（PR）的值将每个集群划分为子集群。

最后，它利用消息对齐将一些子集群合并到一个更大的集群中，以避免过度分区。例如，在第一个集群（mc0、mc4、mc1、mc5、mc6）中，红色标记（'B'）仅包含两个不同的值（81 和 82），可以将其视为代表标记，用于获得新的子集群（图 3c 中的集群 1 和集群 2）。

最后它产生了四个集群，如图 3c 所示。尽管每个集群中只有一种类型，但每个真实类型（用阴影或无阴影表示）都被次优地划分为两个较小的类型（集群）。造成这个问题的原因有很多：
1、首先，二进制协议中没有明确的分隔符。因此，大多数字节被视为单独的标记，由于很少暴露结构信息，因此降低了标记化的价值。
2、此外，二进制标记的值有时位于文本标记的范围内，因此这些二进制标记可能会被误认为是文本标记（例如，图 3a 中的文本标记）。
3、短于最小长度的文本字符串（作为文本标记）也被错误地标记为二进制标记。
4、另一个问题是在递归聚类和合并步骤中可能会发现多个代表性标记。所有这些原因导致令牌类型过多。

Discoverer 总是存在冗余的集群，这表明其结果并不简洁。

1.4 NETPLIER的构思

上面的讨论中可以观察到基于对齐的聚类和基于标记的聚类都依赖于假设消息是相同类型的，如果它们具有相似的值或模式。 然而，在许多情况下，这种假设并不成立，并且会导致不准确的聚类。 实际上，当客户端或服务器接收到消息时，只是通过关键字来确定消息类型。 因此，如果能够推断出表示关键字的字段，就可以获得理想的聚类结果。需要注意的是，尽管一些基于toke的聚类方法使用代表性token进行聚类，但它们仅通过频率等统计信息搜索此类token，这通常会生成多个代表性token，然后导致冗余聚类。

同时，很多工具只考虑仅仅一端的网络流信息，而并没有考虑客户端和服务端两端之间的交互，这种交互可以用来验证和改善聚类结果。

NETPLIER对来自客户端和服务器端的消息使用多序列对齐 (MSA) 算法，并将消息划分为字段列表，MSA 只生成一个全面的字段列表。

1. 对于每个字段，引入一个随机变量来表示成为关键字的概率。
2. 假设一个字段是关键字，消息可以通过字段的值被分组到不同的簇中，这些簇会满足一些约束，例如消息相似性约束、远程耦合约束、结构一致性约束和维度约束。
3. 对于每个约束，计算概率以作为观察到的符合规则程度。
4. 使用这些概率，然后执行概率推断以得出表示预先假设的随机变量的后验概率，即当前字段是关键字。
5. 在检查所有字段后，可以选择概率最高的一个作为关键字，并用它来聚类消息。

2 NETPLIER——系统设计

2.1 预处理

输入到NETFLIER的网络数据流可以由 tcpdump 工具抓取，NETFLIER主要针对应用层进行协议逆向工程。基于其他的已知的协议，NETFLIER提取一些有用的信息如网络层的端口号，并丢弃不相关的协议的数据。预处理后的网络消息包含以下信息：时间戳、IP地址、端口号和目标协议的数据。

通过时间戳、IP 地址和端口号，可以将消息分组到通讯会话中。 例如，在上文的图 1 所示的示例中有三个会话，其中 mc0 、 ms0 、 ms1 、 mc1 属于第一个会话， mc2 、 ms2 、 mc3 、 ms3 属于第二个会话，其他消息 属于第三届。 会话信息将用于概率推理和状态机推理阶段。

2.2 关键字段候选列表生成

消息报文数据由多个字段组成，对于图 1 中的示例，所有报文数据都具有相似的字段结构，并且这些字段具有相同的长度（最后一个字段DATA除外）。

但是，对于复杂的协议，报文可能具有不同的结构，并且某些字段可能具有可变长度，这使得一个字段在不同的报文中出现在不同的位置。

例如，图 6a 中的消息有一个用户名字段，该字段具有可变长度。直观地说，识别这些字段的方法可以是通过消息对齐来识别固定长度字段。

2.2.1 序列对齐

可以看到报文倾向于拥有一些相同的值，特别是对于固定长度的字段，例如图 6a 中的“用户”和“年龄”。因此，可以对齐报文并公开此类公共序列范围，然后识别它们之间的可变长度字段。如果多个连续的可变长度字段存在于两个边界固定长度字段之间，NETPLIER 将这些可变长度字段识别为一个整体可变长度字段。

然而，成对对齐的按双比对报文序列在样本数量很大的时候开销很大且影响伸缩性。因此，NETFLIER提出多序列比对, 这是生物信息学中成对比对的扩展，可以一次比对所有序列。 有多种策略可用于降低计算复杂性并提高多序列比对的准确性。 在NETFLIER里使用的是渐进式方法和迭代细化。 渐进式方法首先比对最相似的序列，然后逐步将其他序列添加到比对结果中。 迭代细化方法则是迭代地重新比对初始全局比对结果的序列子集以提高准确性。

2.2.2 生成字段

图 6b 显示了多序列比对后的结果。 将间隙（即“-”）插入可变长度字段以显示对齐结果。

基于初始对齐结果，将消息报文数据划分为字段。对于文本数据，可以使用预定义的分隔符（例如空格字符）将消息数据划分为字段。但是，二进制数据没有特定的分隔符，其字段通常只有几个字节长，需要以非常保守的方式使用对齐结果，以便它考虑一个领域的每个可能的候选者。

首先，将每个（对齐的）字节视为一个单元字段。如果所有消息数据具有相同的字段值，则该单元字段被标记为静态，否则为动态。然后将连续的静态单位字段合并为一个更大的单位字段。这些单位字段入选字段的候选列表，也就是说字段是指一个单位字段或多个单位字段的串联。

候选阶段结束时，生成一个列表，其中包含所有单元字段以及单元字段短于阈值（即本文中的 10 个字节）的组合。该列表表示关键字字段的候选，并受下面的概率分析的影响，并限制大小以减少要分析的候选字段的数量。NETFLIER分别为客户端和服务器端生成字段（同时考虑它们在概率分析中的对应关系）并依靠后面的概率分析来高精度地识别关键字字段，从而可以识别其他字段并修剪虚假字段。

2.3 基于概率的关键字段识别

给定客户端与服务端双方的关键字候选字段列表，NETFLIER使用概率方法来推断哪些字段最有可能是关键字。通过识别关键字字段，可以识别相同类型（即具有相同关键字值）的消息，并且可以对这些消息执行进一步的对齐和分析。

设字段 fc 和 fs 分别是来自客户端和服务器端的潜在关键字。客户端发出的报文由 fc 推测性地分组到集群 (tc0 , tc1 , ...) 中，服务器端发出的报文由 fs 分组到 (ts0 , ts1 , ...) 中。

在图 1 所示DNP3协议的示例中，客户端消息的候选字段列表如图 4a 所示。

图 7a 显示了考虑 f1 作为客户端和服务器端消息关键字的聚类结果，图 7b 显示了考虑 f7 作为关键字的结果。即，使用 f1 关键字时，mc0 、 mc1 、 mc4 、 mc5 和 mc6 属于一个簇，因为它们的 f1 字段的值都为 A0，而 ms0 、 ms2 、 ms3 和 ms4 属于一个簇，因为它们的 f1 值为 08 （可以见上一张图）。

如果关键字推测为真，即集群中的消息（按关键字值分组）确实属于同一类型，我们应该可以从生成的集群中得到以下观察结果：

1. 同一集群中的消息应该比不同集群中之间的报文更相似。
2. 客户端和服务器端的集群应该有对应关系。 换句话说，属于集群一侧的消息（例如，来自客户端的请求）很可能在集群的另一侧也有其对应的消息（例如，来自服务器端的相应响应）。
3. 同一集群中的消息遵循相同的字段结构。
4. 不应该有太多的集群。 在每个集群中，应该有足够数量的消息。

观察结果可能具有不确定性，也就是真正的集群可能无法证明这样的观察结果，它们的存在也不一定意味着这是真正的集群。 因此，该研究引入了一个随机变量来指示候选者是否是真正的关键字。 变量和观察形成联合概率分布，将关键字识别表述为一个概率推理问题，计算给定观察结果的关键字随机变量的边际后验概率。

正如我们将在第四节中解释的那样，推理规则可以是定向的（即贝叶斯推理）或非定向的（马尔可夫随机场），而一种称为因子图的通用图模型支持这两种类型。

经过推理，具有最大后验概率的随机变量表示最可能的关键字对。

2.4 迭代对齐和聚类

MSA（多序列比对） 可能不会在第一轮迭代中产生预期的对齐，因为它本身也不确定。所以，NETFLIER使用迭代对齐和聚类来解决这个问题。也就是说，假设 MSA 没有正确对齐，就无法正确识别关键字。

尽管如此，概率推断和聚类可能会减少集群内消息的结构差异。因此，对于每个集群，NETPLIER执行 MSA 和概率关键字识别。然后，将结果关键字与原始关键字进行比较。如果新关键字可以更好地对所有消息进行全局划分，就用新关键字替换原来的关键字。重复该过程，直到无法识别出更好的关键字。该策略对于具有大量消息长度变化的协议（例如 DHCP）特别有效。

2.5 格式和状态机推理

如前所述，在多序列比对后，每条消息被分成几个比对字段（如图 4a）。

经过迭代对齐和聚类后，可以通过对同一簇中所有消息的字段进行汇总，直接恢复每种类型的格式。 该格式包括用长度 (L)、值 (V) 和字段类型定义的字段（S：具有特定值的静态字段；“D”：具有潜在值列表的动态字段）。

例如，在图 4a 中，字段 f0 可以表示为 S(V =‘0564’)【原论文这里错了】； f7 可以是 D(L = 1, V = [‘82’,‘81’])，这是一个有两个潜在值的动态字段； 并且字段 f12 可以是 D(L = (0, 11))，这是一个可变长度字段或可选字段，因为它对于某些消息是空的。 可以基于这样的格式生成新报文。

此外，对于推断状态机，当正确定义消息类型时，基本思想是为每个会话增加消息类型序列并将这些序列聚合以形成状态机。

3 核心——基于概率的关键字段识别

NETFLIER中的一个关键步骤是将关键字段识别中的不确定性建模为观察值和一组随机变量的联合分布，每个变量都表示候选字段是否是消息的关键字。 本节将讨论如何使用概率对不确定性进行建模以及使用图形模型进行概率推断的细节。

3.1 随机变量和概率约束

断言

表 I 的前三列分别定义了断言、断言的符号和描述。谓词具由布尔值，并与系统中的随机变量相关联。

1. 关键字断言 K(f) 断言字段 f 是关键字字段。
2. M(f, c) 通过关键字段 f 断言集群 c 中的消息报文之间的相似度高于其他集群中的消息报文；
3. R(f, c) 断言对于c中的消息，它们在另一侧（例如这边是客户端，另一侧就是服务器端）的对应消息应该属于同一个集群；
4. S(f, c) 断言集群c中的消息应该具有相似的字段结构；
5. D(f) 是一个全局断言（即，不是特定于一个集群），断言关键字 f 不会导致太多的集群，并且每个集群应该有足够的消息。

约束

表 I 中的最后一列显示了与断言相关的一组约束，它们表示随机变量的相关性，可以认为是这些变量的联合分布。

每个断言都有两种约束。 第一种称为将断言与先验概率相关联的观察约束。 它们下标有一个符号，表示相关断言。 例如，约束 Cm 是消息相似性断言 M(f, c) 的观察约束。 它的主体 M(f, c) = 1(pm) 表示“谓词 M(f, c) 具有 pm 为真的先验概率”， 其他观察约束的定义类似。本节后面解释如何系统地推导先验概率。

第二种约束称为推理约束，它们以隐含关系为下标。
例如，Ck→m ：

表示如果 f 是关键字段，则报文有 pm→ 的机率，在集群c 中（使用 f 作为关键字段形成的集群）的集群内相似度高于集群间相似度。下面一行的的约束 Ck←m 表示推理的相反方向。这两个约束描述了 K 和 M 之间关系的不确定性。例如，即使 f 确认了是真正的关键字段，相同类型的报文仍有可能不具有高相似度。（这类似于充分与必要条件的判断）

现有研究表明，由于推理算法的迭代性，推理结果通常对这些值不敏感。NETFLIER遵循相同的观察值定义的做法，例如使用 0.95 表示可能，使用 0.1 表示不太可能，并根据个人观察的不确定性水平根据这两个值调整蕴涵概率。

例如，远程耦合约束（表一的第三行的R(f，c)的第四列） Ck→r（从关键字到耦合断言）的隐含概率 pr→ 为 0.9，这么定义是因为几乎是没有不确定性。即同一种请求消息的响应消息很可能属于同一种。然而，沿着相反的方向，pr← = 0.8 表示如果两侧的相应消息属于两个不同的集群，则不能如此确信 f 是正确的关键字段，因为这种完美耦合可能是偶然的。

消息相似性（S(f,c)）的隐含概率低于远程耦合(R(f,c))的隐含概率，因为它们更不确定。在 NETPLIER 中，概率 p→ 对于消息相似性约束设置为 0.8，对于其他约束设置为 0.9。概率 p← 位于 [0.6, 0.8] 取决于集群大小。

3.2 确定先验观察概率 3.2.1 消息相似性约束（M（f,c））

基于 MSA 结果，可以用以下公式计算一对对齐消息的相似度得分：
也就是 s = 相同字节的数量 / 所对比的两个消息报文的字节总数

在得到所有消息对的相似度数值后，构造一个相似度得分矩阵。对于每个关键字候选字段 f，可以根据其聚类结果将所有相似度得分分为两类：

• 两条消息来自同一集群的相似度值
• 两条消息来自不同集群的相似度值

按道理来说，消息相似性约束（M(f,c)）所有的集群内部之间两个报文进行对比的分数应该大于不同集群两个消息的类间分数。如果是这样，那么可以将 pm 设置为 1。但是，两种分数的分布通常是重叠的，就是说两种分数，比如内部分数达到了80，类间分数也有可能达到80，这就是所谓的重叠。

这就是一个错误匹配和错误不匹配的问题。也就是说，前者表示不同类型的消息不希望被分组到一个集群中（错误匹配），而后者表示同一类型的消息不希望被放置在不同的集群中（错误不匹配），通过计算两个误差来量化重叠的程度，较小的误差导致消息相似性约束（M(f,c)）的先验概率更高。

具体来说，对于从 0 到 1 的阈值 t，计算错误匹配率 (FMR) 和错误不匹配率 (FNMR)，如下所示：

也就是
FMR = 类间分数大于t的数量 / 类间分数的数量
FNMR = 内部分数小于t的数量 / 内部分数的数量

依据[0, 1]范围中的所有阈值t，绘制出FMR和FNMR的曲线，如图8所示。观察到当t增加时，FMR减小，FNMR增加。 也就是说为了描述相似性约束，需要同时考虑 FMR 和 FNMR。可以直观的看到选择两条曲线的交点可以平衡FMR和FNMR。 交叉点的错误率值也称为等错误率（EER），它描述了聚类结果的整体准确性。同时，也可以得出pm的计算公式：

这意味着 EER 越低，对消息相似性约束 M 的置信度就越高。

可以说，NETFLIER使用的是动态阈值。

3.2.2 远程耦合约束（R(f,c)）

在预处理步骤中，原始数据流被拆分为多个会话。在会话中，可以根据时间戳、IP 和端口号将来自客户端和服务器端的消息分组。 例如在图 1 中的DNP3，可以生成如表 II 所示的消息对。

通过对服务端和客户端两端的候选关键字段进行聚类后，将消息报文替换为其所属的集群，并将消息报文对转换为集群对。右两列分别显示了通过字段 f1 和 f7 生成的集群对。 对于大小为 N 的一侧的集群，计算另一侧属于同一集群的对应消息的最大数量，用 M 表示，并有以下公式：

举个例子，对于 f1 的消息类型对，有四个集群（红色）与 ts1 配对，其中两个是 tc1 。因此，集群 ts1 的 pr 为 0.50（即2/4）。 同理，ts2的pr为1。可以看出，这个pr就相当于一个配对率，同时，这篇文章上文的 t 表示阈值，这里的ts和tc明确说明是集群，例如ts是server端的一种集群，要分辨清楚。

在 f7 的表 II 中，只有两个唯一的集群对，即 <tc1 , ts1 > 和 <ts2 , tc2 >。 因此，所有聚类的 pr = 1，表明聚类质量比使用 f1 更好。

总的来说，这个约束就是计算聚类后不同端的相同集群匹配率。

3.2.3 结构一致性约束（S(f，c)）

结构一致性约束表明相同类型的消息报文拥有相似的字段结构。 对于不同类型的消息，它们可能共享一些公共字段，由它们的唯特定字段分隔。 在对齐这些消息时，由于这些特定于类型的字段，会形成对齐间隙。

例如在图 9 中，两条消息属于不同类型，具有不同的字段结构。 如果它们被错误地放入一个集群中，将插入很多间隙（'-'）以使它们的公共字段对齐。 尽管相同类型的消息的对齐中也存在间隙（由于数据变化），但前一种情况通常会导致更多的间隙。 因此，在与候选字段进行聚类后，再次对齐同一聚类中的消息并计算对齐间隙的平均数量。 间隙的比例用将作为一致性约束的先验概率：

即ps = 1 - （消息报文中的平均间隔数/一个对齐消息的总长度）

例如，图 7b 中字段 f7 的集群 tc1 中有 4 条消息 mc0、mc2、mc3 和 mc4。

根据图 4a 所示的 MSA 结果，消息 mc0 和 mc4 在对齐后有 11 个间隙，由对齐后插入尾部的符号“-”表示。 相比之下，mc2 和 mc3 没有差距。 在对齐（和间隙插入）之后，所有四个消息的长度均为 28。因此，对于集群 tc1，平均间隙数为 (11 + 0 + 0 + 11)/4 = 5.5，集群的 ps 计算为 1 - 5.5/28。

3.2.4 维度约束（D（f））

维度约束中考虑两个指标：集群的总数和只有一个消息的集群的数量。
第一个与特殊值有关的参数定义如下：

将其与阈值 t 值进行比较，本文中阈值保守地设置为 0.5。 如果指标大于阈值，则意味着候选字段生成的簇太多，不太可能是真正的关键字。 请注意，真正的关键字通常只有少量不同的值。因此 0.5 是一个非常保守的值，以确保不会忽略真正的关键字并且不会影响生成的集群的数量。

它还与阈值 tsingle 进行了比较，在本文中也是 0.5。 如果两个值都小于它们的阈值，则维度约束的概率很高，例如 0.95。 否则，将其设置为低概率，例如 0.1。

例如，根据图 7 所示的聚类结果，可以确定rsingle_cluster的值（以字段 f1为聚类） 的单个聚类为 5/8，因此其 pd 为 0.1，而 f7 满足这两个条件，其 pd 为 0.95。

3.2.5 规则化

如上所述，四个观察约束由不同的值表示，这并不意味着是可以用的概率，且可能具有不同的分布。 例如，EER 通常在 [0.3, 0.6] 范围内，而远程耦合约束的计算 pr 可能高达 1。如果一种类型的观测约束的概率被限制在一个小范围内，则这种类型的观测约束可能与其它的相比，扮演的角色不那么重要。 为了避免这个问题，在进一步的概率推断之前，将所有候选字段的相同类型约束的概率归一化到相同的范围，例如 [0.1, 0.95]。

3.3 概率推理

在这个阶段，上一步所有的约束被考虑在一起形成一个联合分布。 让布尔变量 k 表示关键字段的断言，xi 表示 表I 中的断言。那么所有约束都可以表示为带有布尔变量的概率函数。 具体而言，观察约束 xi = 1(p) 被转换如下：

xi为真意味着
以及推理约束

被转化如下：

p⬅道理是一样的。

那么所有约束的结合可以表示为所有相应概率函数的乘积：

链接的概率的函数定义为：

该研究的一个重点是假设 k 的边际概率，它是所有观察变量的总和。 该值表示候选字段是关键字的概率，计算如下：

3.3.1 因子图

由于约束的数量太多，边际概率的计算量很大。NETFLIER使用图形模型因子图来表示所有概率函数并进行高效计算。

因子图是具有两种节点的二分图，即因子节点和变量节点。因子节点代表概率函数，变量节点表示概率函数中使用的变量，其边连接到相应的因子节点。

然后使用和积置信传播算法通过以有效方式迭代消息传递来计算节点的边际概率。

可以将其视为谣言传播过程。观察结果是最初的谣言。在每次迭代中，每个变量（把它想象成一个人）从它的邻居那里收集所有关于自己的谣言，聚合它们，并将聚合的谣言传递给连接的因素。每个因子（涉及多个变量）收集其变量的谣言，并根据该因子表示的条件概率计算边际概率，然后将计算的概率传播到其变量。该过程重复直到收敛。NETFLIER使用的是现成的因子图引擎，因此这里省略了细节。

4 总结

简要的做个总结：
首先，NETLIER通过网络流量预处理蒸馏提取有用的信息。

接着以多序列对比的方法快速的对多消息进行字节对齐，接着，按照对齐的几个结果，划分字段，生成字段候选列表。

然后，迭代的进行以概率为标准进行关键字段识别以及聚类。

最后，使用现有的研究对格式与状态机进行推理。

项目地址：https://github.com/netplier-tool/NetPlier
后期我会出文章对源代码进行分析。
关注微信公众号，获取更多安全学术、技术资讯。