记录黑客技术中优秀的内容,传播黑客文化,分享黑客技术精华

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

2021-08-25 16:31

工作来源

Usenix Security 2021

工作背景

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

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

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

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

  • 十六进制字符串:将十六进制字符串中的连续纯字符串转换为多个普通字符串。例子中为“\x01\x01\x01\x01”、“\xF3\xAB\x88\x12” 和 “\xAB\x88\x12\x83”。

在数千万个恶意样本上运行标准 Yara 扫描需要数天时间,而且会随着样本的数量线性增加。尽管类似卡巴斯基的 Klara 方案将 Yara 扫描并行化可以在一定程度上缓解这个问题,但不解决根本问题。

赛门铁克也此前提出过恶意软件索引树(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 字节序列。

倒排索引的大小主要由两个因素决定:(a) 索引中的 n-gram 的数量 (b) 每个 n-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 内部已打造更好的系统,这可能也是适用性更强的一种方案。



知识来源: id=f567d89e69f0e12ef04f43eaf7702384&source_url=https%3A%2F%2Fmp.weixin.qq.com%2Fs%2FvtmrhjXzL3gj8m_1uwgtmw

阅读:164553 | 评论:0 | 标签:无

想收藏或者和大家分享这篇好文章→复制链接地址

“海量恶意样本下高性能 Yara 检测方案”共有0条留言

发表评论

姓名:

邮箱:

网址:

验证码:

黑帝公告 📢

永久免费持续更新精选优质黑客技术文章Hackdig,帮你成为掌握黑客技术的英雄

↓赞助商 🙇🧎

标签云 ☁

本页关键词 💎