💻 computer science

The Needle is a Thread: Finding Planted Paths in Noisy Process Trees

受网络安全应用的启发，本文引入了“植入路径”问题，并提出了一种寻找树之间模糊匹配的算法，展示了其在噪声过程数据中识别有意义事件序列方面的有效性。

原作者： Maya Le, Paweł Prałat, Aaron Smith, François Théberge

发布于 2026-02-05

📖 1 分钟阅读☕ 轻松阅读

原作者： Maya Le, Paweł Prałat, Aaron Smith, François Théberge

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名试图破案的侦探，但交给你的不是几件线索，而是一个包含数百万本书的图书馆。其中大多数书都充满了随机的胡言乱语、广告和无关的故事。然而，在其中的一些书中，隐藏着完全相同的“犯罪秘密配方”，只是每次书写的笔迹略有不同，或者有些单词缺失或拼写错误。

这篇论文介绍了一个旨在从海量噪声的图书馆中找到那个隐藏的“秘密配方”（植入路径/Planted Path）的工具。

以下是使用简单类比对该论文思想的拆解：

1. 问题所在：大海捞针

在网络安全领域，计算机生成大量的“进程树”（Process Trees）。可以将这些理解为计算机程序的“家谱”。每当一个程序启动另一个程序时，它就会为这棵树增加一个分支。

噪声： 大多数这些树只是正常的计算机活动（比如用户打开浏览器）。
信号： 有时，黑客会使用特定的程序序列进行入侵。这个序列就是“植入路径”。
挑战： 黑客的路径通常埋藏在巨大的树结构深处，混杂在正常的活动之中，而且程序的名称可能略有不同或缺失。这就像是在一本书中寻找特定的句子，而那里的墨迹正在褪色，有些词被随机的词替换了。

2. 解决方案：“模糊匹配”算法

作者创建了一个工具（算法 1），它就像一个智能荧光笔。

它并不寻找精确、完美的匹配（这在现实生活中很少发生），而是寻找一种“模糊”的匹配。
它对比两棵树，并询问：“即使不完美，这棵树中的有多少步看起来像那棵树中的步骤？”
它会给出一个匹配的“得分”。如果得分很高，意味着这两棵树很可能共享同一个隐藏的故事，即使细节很混乱。

类比： 想象你正在尝试匹配两首歌。一首是清晰的录音，另一首是由于吉他走音且漏掉了一些音符而演奏的翻唱版本。一个追求完美匹配的算法会说：“它们是不同的。”而这个“模糊”算法会说：“嘿，旋律基本上是一样的！把这些匹配的部分高亮显示出来吧。”

3. 他们是如何测试的（“玩具”模型）

在测试真实数据之前，作者创建了一个“沙盒”来观察他们的工具是否真的有效。

实验： 他们构建了数千个虚假的计算机树。在其中一些树中，他们秘密植入了一个特定的事件序列（例如一组特定的指令）。而在另一些树中，他们什么也没植入。
结果： 他们证明了该工具能够成功地将带有“秘密配方”的树与仅包含随机噪声的树区分开来。
难点： 他们证明了简单的技巧（比如仅仅统计一个词出现的次数）是行不通的。你必须观察事件的顺序和结构，而这正是他们的工具所做的。

4. 现实世界应用：ACME4 数据集

作者将他们的工具应用于名为 ACME4 的真实网络安全数据集，该数据集模拟了一个遭受攻击的企业网络。

数据： 他们查看了超过一百万个计算机进程树。
发现： 他们发现大多数树都很小（仅有 2 个节点），但真正重要的树规模较大。
成功之处： 他们使用该工具找到了由“坏人”（黑客）使用的特定事件链。
- 他们发现了一个类似于：登录 (Logon) -> 用户初始化 (User Init) -> 资源管理器 (Explorer) -> 命令提示符 (Command Prompt) -> 控制台主机 (Console Host) 的序列。
- 即使用户名是空白的或略有不同，该工具仍能识别出这种模式。
工作流： 他们展示了两种使用方式：
1. 聚类 (Clustering)： 将相似的树分组在一起，以便在不知道具体是什么的情况下发现常见的“坏”模式。
2. 分类 (Classification)： 使用“匹配得分”作为特征来训练计算机自动标记可疑树（就像是计算机日志的垃圾邮件过滤器）。

总结

该论文认为，如果在寻找特定事件序列时，不再寻找完美的匹配，而是开始寻找有意义的相似性，那么在混乱、嘈杂的计算机日志中找到它是有可能的。他们的“模糊匹配”算法是那个“找针器”，它可以忽略干草堆，并高亮显示黑客所走的路径，即使这条路径是肮脏的、破碎的或部分隐藏的。

该论文并未声称：

它并不声称能实时阻止黑客。
它并不声称是针对每种类型网络攻击的完美解决方案。
它并不声称能应用于医疗数据或生物树（尽管它提到了这些是数学可以应用的其他领域，但本论文仅测试了网络安全数据）。

核心信息是：我们有一种新的、简单的方法，可以在杂乱的数据中找到隐藏的模式，并且它在真实的计算机日志中行之有效。

技术摘要：针尖中的线索：在噪声过程树中寻找植入路径

1. 问题定义

本文探讨了**“植入路径”（planted path）问题**，这是一个数学挑战，即从一个大型、含噪声的有标签有向无环图（DAG）中恢复出一个微小且具有意义的序列（路径）。虽然该问题在“植入团”（planted clique）和“植入结构”（planted structure）文献中具有理论上的类比，但本研究侧重于在网络安全领域的实际应用，特别是过程树（process trees）。

在这种背景下，目标是识别出执行攻击者操作的进程序列（即“植入路径”），该序列隐藏在被入侵计算机产生的海量、高噪声日志之中。挑战在于：

日志数据的总量极其庞大。
朴素的启发式算法会产生过多的“可疑”行，导致人工检查负担过重。
真实的恶意序列通常仅占总树结构的极小部分，并被噪声（缺失事件、误报以及无关的背景进程）所掩盖。
完整的事件在观测到的数据中可能并不严格表现为单一的连续路径。

作者认为，虽然植入路径的抽象模型对于现实世界的数据而言并不完美，但提取局部路径是一个关键的“信号聚合”步骤，能够增强不良序列的信号并过滤噪声。

2. 方法论

2.1 模糊匹配算法 (算法 1)

核心贡献是一种动态规划算法，旨在计算两个树 $G$ 和 $H$ 之间的基于特征的相似度得分。

输入： 两个有向树，节点由来自集合 $S$ 的特征进行标记，以及一个量化任意两个特征之间相似性的权重函数 $w$ 。
机制： 该算法使用自底向上的制表法（避免递归）来寻找最优的节点匹配 $(u_1, v_1), \dots, (u_k, v_k)$ ，使得该序列同时遵循两棵树中的父子顺序关系（即 $u_i <_G u_{i+1}$ 且 $v_i <_H v_{i+1}$ ）。
评分： 匹配的得分是权重 $w(\phi_G(u_i), \phi_H(v_i))$ 的总和。算法通过最大化此得分来寻找最佳的“模糊”对齐。
复杂度： 时间复杂度为多项式级别 $O(nm) $，其中$ n $和$ m$ 分别是两棵树的节点数。
输出： 算法返回匹配的节点序列及最大得分。它可以配置为返回单条最佳路径，或适配为返回“Top-K”路径。

2.2 工作流

作者建议将算法 1 作为构建更大规模机器学习工作流的基础组件：

无监督聚类 (算法 2)：
- 目标： 在一组大型图中识别未知的模板。
- 流程：
  1. 使用算法 1 计算数据集中所有树之间的两两相似度得分。
  2. 使用特定的归一化方法（公式 5）将相似度矩阵转换为距离矩阵。
  3. 将树嵌入到低维空间中（使用 UMAP）。
  4. 对嵌入结果进行聚类（使用 HDBSCAN）。
  5. 对聚类内匹配度最高的序列应用多序列比对（MSA）方法，以提取代表性的“模范样本”（exemplars）。
用于分类器的特征增强 (第 3.2 节)：
- 目标： 提高树的分类能力（例如，区分良性与恶意）。
- 流程： 利用一组已知模板（例如已知的攻击序列）为每个观测到的树生成辅助特征。特征 $X_{i,j}$ 代表树 $G_i$ 与模板 $T_j$ 之间的最长公共路径长度（或得分）。随后将这些特征输入到标准分类器（如随机森林）中。

2.3 合成数据生成

为了验证该方法，作者引入了一个类似于随机块模型（SBM）但专门针对树定制的数据生成过程（算法 3 和 4）：

树生成： 使用 Galton-Watson 过程生成“茂密”的树。
植入路径： 在树中的一条随机路径内植入特定的标签序列。
噪声模型： 植入路径中的标签受观测概率 $p$ （欠采样）和错误概率（重采样）的影响。其他节点则从一个字母表中均匀取样。
设计目标： 该模型确保了简单的算法（如统计标签频率）会失效，因为标签的分布与植入路径的类别无关，从而迫使算法必须依赖结构化的路径信息。

3. 关键结果

3.1 合成实验

可区分性： 由算法 1 导出的相似度得分成功区分了包含植入路径与不包含植入路径的树，即使当路径仅为大型树的一小部分且观测率较低（ $p=0.75$ ）时也是如此。
聚类： 在具有 4 个类别的无监督设置下，嵌入工作流（算法 2）成功分离了地面真值（ground-truth）簇。
权重影响： 实验表明，使用概率加权得分函数（降低稀有符号的权重）相比于未加权的二元得分，能显著改善聚类分离效果，尤其是在字母表中包含稀有符号的情况下。

3.2 实际应用 (ACME4 数据集)

作者将方法应用于 ACME4 数据集，该数据集模拟了一个包含各种攻击行为的 Windows 商务网络。

数据规模： 该数据集包含超过 110 万个过程树（大部分规模为 2）和近 300 万个节点。其中只有 8 棵树包含“坏”（恶意）用户。
子树构建： 为了克服小规模树过多的问题，作者从较大的过程树中构建了 2,693 个子树（规模在 3 到 9,558 之间）。
匹配结果：
- 使用包含“坏”用户的参考树，算法成功识别出了其他树中匹配的路径。
- 评分灵活性： 作者展示了不同的评分函数（基于进程名称的精确匹配 vs 基于进程名和用户名的软匹配）会产生不同但具有实际意义的结果。例如，“软”匹配可以识别出进程序列相同但用户名略有不同的路径（例如，“user88”对比“bad3”）。
工作流性能：
- 过滤： 当作为过滤器来筛选与已知模板共享路径的树时，该方法成功隔离出了得分较高的树子集，这些树的得分与较大的树规模以及特定的进程序列（如 winlogon.exe $\to$ cmd.exe）相关联。
- 分类： 使用基于路径匹配特征（针对 38 个模板的最长公共路径长度）训练的随机森林分类器，在根据根进程名称对树进行分类时达到了极高的准确率，仅在 bash.exe 和 cmd.exe 之间存在轻微混淆。

4. 重要性与主张

本文将自身定位为一项探索性工作，旨在证明路径提取对于真实的网络安全数据是可行且有用的。

实用价值： 作者声称，虽然“植入路径”是一个抽象概念，但所提出的算法能有效聚合相关事件的信号，从而过滤掉足以淹没人类专家的绝大部分噪声。
范围适度： 作者明确指出这是一项初步研究。他们承认当前工作并未针对特定洁净版本的具体问题提供统计学上的最优解，而是侧重于开发适用于“杂乱”数据的现实模型。
未来工作： 文中提到，未来的版本将提供更多关于现实机器学习工作流的细节、在真实数据集上与其他算法的对比，以及基础的理论分析。
局限性： 作者承认在真实数据中，完整的事件可能并不严格包含在单一路径中，且观测的噪声可能会阻碍完整植入路径的观测。然而，他们认为即使是不完美的过滤也能增强恶意序列的信号。

总之，本文介绍了一种模糊匹配算法，将其作为从噪声过程树中恢复有意义序列的基础工具，通过合成模型验证了其有效性，并展示了其作为特征生成器和过滤器在真实网络安全排查中的潜力。