Short-Circuiting Boolean Operators in YARA">Short-Circuiting Boolean Operators in YARA

Short-Circuiting Boolean Operators in YARA

在 InQuest，YARA 是我们用于执行深度文件检查的众多工具之一，具有相当广泛的规则集。InQuest 在流量非常大的网络中以线速运行，因此这些规则需要快速。
这篇博文是讨论 YARA 性能说明、技巧和技巧的系列文章中的第二篇。
YARA旨在将文件和内存块与任意模式进行匹配。这些模式通过常规表达式和文字字符串以及模块提供的各种功能来表达。
对于给定的输入，这些测试（正则表达式、字符串匹配、函数调用等）中的每一个都可能成功或失败。规则是否触发由单个条件确定，该条件是正在测试的所有单个术语的组合。
这篇文章讨论了在规则条件下更改术语的顺序如何对性能产生重大影响。

示例规则

举一个简单的例子，让我们编写一个规则来检查相关文件是否是列入黑名单的可执行文件。我们的黑名单表示为SHA-256哈希列表，当我们在此示例中说“可执行”时，我们指的是 ELF二进制文件。

第一次尝试

这是在 Yara 中写这个的“明显”方式，考虑到我们超级庞大的两个成员黑名单和 YARA 的hash模块：

import "hash"
rule BlacklistedExecutable
{
  condition:
    hash.sha256(0, filesize) ==
        "0d06f9724af41b13cdacea133530b9129a48450230feef9632d53d5bbb837c8c"
    or
    hash.sha256(0, filesize) ==
        "aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23"
}

这将计算文件的 SHA256 哈希值，并在哈希值与列入黑名单的哈希值之一匹配时触发规则。
让我们在 InQuest“好”语料库上运行它：

$ time yara -r blacklist.yara /data/corpus/good
BlacklistedExecutable /data/corpus/good/aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23
real   0m12.192s
user   0m33.474s
sys    0m4.081s

好的，大约十二秒。不坏，不坏。

计算哈希是耗时的

计算文件的哈希值花了多少时间？我们可以通过创建一个空规则来查看：

rule Empty
{
    condition:
        false
}

并针对同一组文件运行：

$ time yara -r empty.yara /data/corpus/good
real    0m6.118s
user    0m15.209s
sys     0m3.568s

所以我们可以看到，我们大约一半的时间花在了计算哈希上，而另一半则花在了不可避免的工作上，比如打开和读取文件内容；我们永远不会超过六秒。

不要不必要地计算哈希

如果我们知道它不可能是有问题的文件，那么如果我们不必计算文件的哈希值，那就太好了。
那个“好”的语料库有很多不可能匹配的文件，因为它们不是可执行文件：它们是文档、图像、文本文件等等。如果我们可以尽可能避免计算这些文件的哈希值，那就太好了。

逻辑连接和短路

YARA 支持三种逻辑连接词：and、or和not。这些与它们在逻辑中的含义相同：

a和b只有在a和b都为真时才为真
a和b为真时a或b为真，或两者都为真
如果a为false， not a*为真
```
*a and b* is true only if both *a* and *b* are true
*a or b* is true if either *a* and *b* or true, or both of them are
*not a* is true if *a* is false
```
YARA 版本的这些运算符使用一种称为“短路”的技术来实现它们。这种技术在许多执行一种“条件评估”的编程语言（包括普遍流行的 Python、C 和 Java 等）中很常见。and和or的参数从左到右进行评估，如果在评估左侧之后结果是确定的，则跳过右侧。
例如，如果写：
```
false and check_database(1)
```
在评估了错误之后，我知道该陈述不可能是真的。相反，如果写
```
true or check_database(1)
```
在评估了真实之后，我知道该陈述不可能是错误的。
许多编程语言，包括 YARA，都利用了这一点逻辑真理，如果左侧足以确定真假，则根本不评估连接词的右侧。
著名的、才华横溢的……可以说是精确的……计算机科学家 Edsger Dijkstra 在奥斯汀任教多年，他反对短路评估是出了名的。“因为条件连接词因此使关于程序，最好避免使用，”他在他著名的笔迹中写道。
由于这种对程序形式推理的障碍，一些语言完全省略了短路运算符，而其他语言，如 Erlang 和 Eiffel，提供它们但使用不同的名称，以便你知道你正在进入什么。
仅计算二进制文件的哈希值
有了在 YARA 中短路逻辑连接词的知识，我们现在可以编写一个规则，只计算我们已确认为 ELF 二进制文件的文件的哈希值。如果二进制检查比哈希计算快，并且我们知道我们要检查的大多数文件不是 ELF 二进制文件，那么这应该会导致相当显着的加速。
首先，让我们确认短路是否按预期工作。如果 YARA 不进行短路，让我们编写一个规则来计算哈希： ```yaml import “hash”

rule BlacklistedExecutable { condition: false and (hash.sha256(0, filesize) == “0d06f9724af41b13cdacea133530b9129a48450230feef9632d53d5bbb837c8c” or hash.sha256(0, filesize) == “aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23”) }

并运行它：
```shell
$ time yara -r short-circuit.yara /data/corpus/good
real    0m6.118s
user    0m15.209s
sys     0m3.568s

是的。这条规则基本上以与我们上面的空规则相同的速度运行。所以，现在我们只需要用仅适用于 ELF 二进制文件的东西来替换那个错误。

Magic and More Magic

让我们尝试使用仅计算 ELF 二进制文件哈希的magic模块编写规则：

import "magic"
import "hash"
rule BlacklistedExecutable
{
  condition:
   magic.mime_type() == "application/x-sharedlib"
   and
   (hash.sha256(0, filesize) ==
        "0d06f9724af41b13cdacea133530b9129a48450230feef9632d53d5bbb837c8c"
   or
   hash.sha256(0, filesize) ==
        "aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23")
}

ELF 二进制文件在我的系统上被标识为“application/x-sharedlib”，这并不奇怪，因为 ELF 也是共享库格式：

$ time yara -r blacklist.yara /data/corpus/good
BlacklistedExecutable /data/corpus/good/aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23
real    1m9.621s
user    4m0.515s
sys     0m8.023s

不好了！我们现在需要一分钟多，而我们的第一条规则只用了 12 秒。
注意，本节的标题来自于一个古老的黑客传奇Magic and More Magic的故事。请注意，魔术模块的名字当然不是来自这个故事，而是来自“magic numbers（幻数）”的概念识别它们是什么的文件的开头。

整数技巧

可是等等！我们可以使用我上一篇博文中的技巧为 ELF 二进制文件编写一个快速测试。
ELF 二进制文件的魔法字符串是“\x7fELF”；也就是说，一个 ASCII DEL 字符后跟字母“E”、“L”和“F”。我们可以将其转换为单个 32 位整数，并使用 YARA 的 uint32be函数使用上一篇博文中描述的技巧非常快速地检查文件的前四个字节。
让我们这样写一个规则：

import "hash"
rule BlacklistedExecutable
{
  condition:
   uint32be(0) == 0x7f454c46
   and
   (hash.sha256(0, filesize) ==
        "0d06f9724af41b13cdacea133530b9129a48450230feef9632d53d5bbb837c8c"
   or
   hash.sha256(0, filesize) ==
        "aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23")
}

再次注意短路评估。让我们看看它是如何执行的：

$ time yara -r blacklist.yara /data/corpus/good
BlacklistedExecutable /data/corpus/good/aec283b16bc0916fb028d5cac5b409c24f879c5940ca04fc01ba5f7acb81bc23
real    0m8.575s
user    0m23.309s
sys     0m3.650s

成功！它比我们的第一个测试快 50% 左右，只比空测试慢 33%！

结论

通过利用我们对 YARA 如何实现逻辑连接词的了解，我们将 YARA 规则的速度提高了 50%。在具有许多不同连接项的任何规则中，将廉价测试移动到连接项的左侧是有意义的。

快来了

下次请关注我们用于自动生成 YARA 规则的一些工具的讨论（并发布！），包括使上述“整数检查”易于编写的工具。

👮‍♀️网络安全👮‍♀️

18.12.18-InQuest-Rob King - YARA 中的短路布尔运算符