海量恶意样本下高性能 Yara 检测方案

工作来源

Usenix Security 2021

工作背景

Yara 已经是行业和社区中公认的检测标准了，可以表现恶意软件的特征模式。而近几年恶意软件的数量猛增，恶意样本库随之扩充到数十亿。与此同时，Yara 的运行时间会随着检测文件数量而线性增长，在超大型恶意软件库上的检索性能会急剧下降。

以名为 foo 的 Yara 规则为例，其中包含普通字符串、正则表达式和十六进制字符串匹配，逻辑条件包含布尔表达式。分别展开：

• 普通字符串：直接分解成 n-gram，例子中为 "calc.exe" 与 "IsDebuggerPesent"。

• 正则表达式：将正则表达式中的纯字符串转换为多个普通字符串，再直接分解成 n-gram。例子中为 ".png" 与 "xC7x45xC3A"。

• 十六进制字符串：将十六进制字符串中的连续纯字符串转换为多个普通字符串。例子中为“x01x01x01x01”、“xF3xABx88x12” 和 “xABx88x12x83”。

赛门铁克也此前提出过恶意软件索引树（SMIT），利用函数调用图进行索引。前人实现的 BIGGREP 利用无偏移的倒排 n-gram 索引和类似增量编码方案进行检索，但仅限于纯字符串检索。

工作设计

YARIX 是第一个兼具可扩展性和空间效率的通用 Yara 检索引擎。通过将 YARA 规则转换为索引查找来优化 Yara 规则的检索，后端使用倒排 n-gram 索引，将固定长度的字节序列和文件建立映射关系。与此同时，YARIX 使用可变字节增量编码抽象文件偏移, 并利用一种基于分组的压缩方法压缩磁盘占用空间。使用该方案向恶意样本库中添加新的恶意样本时需要更新索引，而更新 Yara 规则则无需更新索引。

整体流程如下所示：

优化能优化的，不能优化的保留，最后按照逻辑取交集和并集得到候选文件进行 Yara 扫描。

为匹配逻辑构建抽象语法树，对表达式进行简化：

如果表达式中包含太多不可优化字符串，YARIX 基本等效于顺序 Yara 扫描。

文件索引

YARIX 的底层数据结构是一个倒排的 n-gram 索引。倒排索引将 n-gram 映射到包含这些标记的文件 ID 集合，所谓的倒排列表。

要将倒排 n-gram 索引应用于恶意软件样本上，必须解决一些值得注意的挑战：

• 首先，自然语言中存在语法和分隔符将单词分隔开，而恶意软件的样本没有明显的边界，必须使用固定长度的字节序列。

• 其次，恶意软件样本可能会存在产生的字节序列数量爆炸的问题，在 n=4 的情况下发现有不放呢样本可以覆盖所有可能的 4-gram 字节序列。

一种优化策略是将 n 设置为一个较小的值。虽然较小的 n 明显减少了倒排列表的数量，但较短的 n-gram 特征较少，并且很有可能会出现在大部分索引文件中。另一种优化策略是忽略不作为任何搜索标准的判别部分的 n-gram。但这样会使检索受限，也不可行。

第一条路走不通故而只能选择优化倒排列表的大小，YARIX (i) 在不存储偏移量的情况下运行，(ii) 部署最佳增量编码来表示倒排列表，(iii) 对文件进行分组以缩短必须存储的标识符空间。

无偏移索引

索引中只包含文件 ID 而不包含位置信息，这样可以大幅度减小倒排列表的大小。

索引会由 2 的 8n 次方个倒排列表组成，为了减少索引的磁盘占用空间，我们采用 (i) 可变长度编码，(ii) 使用增量编码压缩倒排列表，以及 (iii) 提出一种基于过度近似分组（overapproximating grouping-based）的压缩方法。

可变增量编码

为最多 232 个恶意软件文件创建一个索引，当使用排好序的倒排列表时，文件 ID 可以不存储原始绝对值转而存储 ID 的差值。为了利用增量编码的空间增益，使用可变长度 s 位编码而不是固定大小的增量来存储增量。

分组

为了节省空间在索引中删除了偏移量，这样纯索引检索就不可靠了，只能在索引之后接续顺序搜索。

将倒排列表中的每个文件 ID 随机分配到一个组中，存储一个组 ID 而非文件 ID，这样可以占用更小的空间。通过确保 gn ≤ 216，可以保证一个组 ID 永远不会占用超过 2 个字节。然而，为了最小化不同倒排列表之间的重叠，又希望 gn 能够是素数。即在 n = 4 的情况下，需要 232 个素数。与此同时，建议不要对每个倒排列表应用分组。

增量索引更新

新样本添加到索引中，通过计算其 n-gram 并更新必要的倒排列表完成增量更新。

工作评估

最终构建一个包含 3200 万个恶意样本和 1404 个 Yara 规则的数据集进行测试，为千万级恶意样本生成 4-gram 的索引用于预过滤。索引仅需要存储恶意软件样本所需空间的 74%，而使用 YARIX 比标准 Yara 扫描要快五个数量级。

恶意样本

恶意样本数据集包括适用于所有流行操作系统的知名恶意软件家族。针对其中 90 万个恶意样本检索了杀软结果，匹配了超过 1.9 万个微软的结果标签和超过 2.1 万个卡巴斯基的结果标签，表明恶意样本是高度多样的。

Yara 规则

使用了 Malpedia 中的所有 1404 条 YARA 规则。所有样本中约有 28.6 万样本至少匹配一个 Yara 规则。

索引构建

利用 C++ 和 Python 3 开发了一个原型系统 YARIX。在 3200 万恶意软件样本上构建了一个 4-gram 倒排索引，未压缩总大小为 13.79 TB。

在 2 颗 Intel 至强 E5-2667 v4 处理器上运行，使用 NVME 驱动作为中间快速存储，在 15 个小时内索引 10 的 6 次方个样本，即 YARIX 单机处理能力超过一百万样本。如果直接在硬盘上写索引，需要耗时 39 小时。

正确性

YARIX 的扫描结果与 Yara 扫描都是完整的，YARIX 无法优化的规则只有 37 条，占到 1404 条规则中的 2.64%。

检索性能

为了最大限度减少缓存和调度的影响，在单线程中进行测试：

在 3200 万样本的场景下，YARIX 平均比 Yara 扫描快五个数量级。随着索引文件的数量增加，加速的倍率也在逐渐增加。

分组影响

分组对检索的影响如下所示，选择 2 的 15 次方、阈值 τ 为 10000 的分组策略会将相对磁盘占用空间从 149.5% 减少到 65.48%，同时只会使搜索速度平均降低 11.56 倍。

n 的选择

n=3 的时候候选文件膨胀太多，n=5 时不可优化的规则数量几乎翻倍且倒排列表更加稀疏。故而权衡之下，最后选择 n=4。

磁盘占用空间

测试使用 ext4 文件系统和文件夹结构 a/b/c 来组织倒排列表。在不使用分组阈值的情况下，在使用增量编码和分组阈值的情况下进行分别测试。

在未压缩的情况下，索引需要所有样本所需空间的 281.46%。应用增量编码可以将相对大小显著降低至 149.5%。而分组则进一步缩小了所需的磁盘空间，且组数越少，磁盘占用空间越小。但这些分组方式的搜索性能都很差，无法实用。

小阈值 τ = 1500 对磁盘占用空间几乎没有影响，因为太多的倒排列表不受分组的影响。磁盘占用空间在开始时对 τ 的变化很敏感，随着 τ 变大而变得不敏感。

案例分析

• 表现很好的规则是 Retefe 银行木马的 Yara 规则，该规则应该匹配 16 个样本。逻辑为 all of them，足够简单，且七个纯字符串都较长。

• 一个表现不好的规则是 PlugX 的 Yara 规则，该规则应该匹配 84 个样本，但 YARIX 匹配了超过 1200 万个样本。匹配规则依赖偏移，逆向工程后发现是用于捕获自定义 API 导入特征，优化后可以匹配 84 个样本。

• 另一个表现不好的规则是 Smokeloader 的 Yara 规则，该规则应该匹配 2 个样本，但 YARIX 匹配了超过 1000 万个样本。匹配规则中的十六进制字符串被拆成了特别常见的一段，导致匹配率非常高。逆向工程后对匹配规则进行硬编码优化可将匹配样本降到 2 个。

• 还有一个表现不好的规则是 SnatchLoader 的 Yara 规则，该规则应该匹配 3 个样本，但 YARIX 匹配了超过 700 万个样本。

工作思考

UTF 16 编码字符串是个问题，删除空字节会对十六进制字符串影响很大。

从这篇文章的工作来看，为超大规模的恶意软件数据集的 Yara 匹配检索提供了一个很好的思路。但从方案的实现来看，个人仍然倾向走并行化的技术路线会带来更好的适用性。这条路上也许有很多可以尝试的点，比如能否利用 HyperScan 进一步提升 Yara 的正则匹配性能？目前 Yara 有类似 PCRE 实现的正则匹配引擎，而 HyperScan 相比 PCRE 的性能提升可能存在数量级的差别，特别是流式应用场景下。

再比如能否像 BlackHat USA 2013 时，Endgame 为处理 TB 级别的恶意软件并打通机器学习路径而提出的 BinaryPig，该项目已经废弃可能是 Endgame 内部已打造更好的系统，这可能也是适用性更强的一种方案。