strawberry/tests/test_rule_partition.cpp
trvon db4c49155f
yara: rule partitions — scan each file only with the rules that can match it
Why YARA-X scanned ~1.6x faster than libyara (perf + source audit, 2026-11-14):
not the language — both spend ~5 s in the atom search loop — but verification
(libyara 2.0 s vs 0.3 s). YARA-X derives filesize bounds and header constraints
per rule at compile time and disables those patterns before the search, so their
atom hits are dropped with one bit test. In the yara-forge core pack 1787 rules
require an MZ header and 2498 bound filesize, so for big Linux ELFs most of
libyara's verification is wasted.

Rule partitioning gets the same win with libyara, and drops the rules' atoms from
the automaton entirely:
- src/rule_partition.cpp (pure): lexer-aware splitter (comments, text, regex
  after = or matches, hex), facts from TOP-LEVEL `and` terms only (MZ /
  pe.is_pe, ELF, Mach-O magic; filesize < / <=), exclusion per (MZ / non-MZ) x
  size bucket (<1, 1-4, 4-16, >=16 MiB). Global rules and rules referenced by
  kept rules always stay.
- YaraScanner builds subsets in a background thread after each load, in
  priority order (big non-PE first) under rule_partition_budget_pct (default
  100 ~ one extra full set: 3 subsets, +59 MiB; all 16 class x size subsets
  would cost +428 MiB). Cached under rules_cache_dir/partitions/. File, buffer
  and fd scans pick their subset; process-memory scans use the full set.
- Fails closed to the full rules: include directives, a split count that
  differs from libyara's, or a subset compile / count error.
- Status rules.partitions (state, reason, subsets, kept_rules/scans per
  partition, full_scans); config rule_partitions (default true) and
  rule_partition_budget_pct.

Measured on the 5132-rule pack: big ASan ELFs 1.64x, 1200 system binaries
1.59x, 0 match-set differences, including 348 positive files across
MZ/ELF/raw x small/5 MiB. Tests: splitter traps, facts, exclusion soundness
property, real pack = 5132 rules; differential test (24 file shapes x memory /
ranges / fd scans, every subset built) and fail-closed; bench --partitions.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-15 06:58:39 -07:00

177 lines
8.9 KiB
C++

// Rule partitioning: splitter, condition facts, exclusion soundness, and the real rule pack.
#include "strawberry/rule_partition.hpp"
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
using namespace strawberry::rules;
namespace {
#define CHECK(cond) \
do { \
if (!(cond)) { \
std::cerr << "CHECK FAILED: " #cond " (" << __FILE__ << ":" << __LINE__ << ")" << std::endl; \
std::abort(); \
} \
} while (0)
void test_split_tricky() {
std::cout << "Test split_rules on tricky sources:" << std::endl;
const std::string src = R"YARA(
import "pe"
// a comment that says rule Fake { condition: true }
/* block comment: private rule Nope { } */
rule A : tag1 tag2 {
meta:
description = "braces } { and \" quote and // not a comment"
strings:
$t = "rule X { }" ascii wide
$h = { 4D 5A [2-4] ( 90 | 91 ) ?? /* hex comment } */ 00 }
$r = /a\/b\{2\}[}]c/is
condition:
uint16(0) == 0x5a4d and filesize < 2MB and any of them
}
private rule B { condition: A and (filesize / 2) > 10 }
global rule G { strings: $g = "x" condition: $g }
rule C { strings: $s = "y" condition: $s and pe.number_of_sections > 1 and "abc" matches /a}b/ }
)YARA";
const auto r = split_rules(src);
CHECK(r.ok);
CHECK(r.rules.size() == 4);
CHECK(r.rules[0].name == "A" && r.rules[1].name == "B" && r.rules[2].name == "G" && r.rules[3].name == "C");
CHECK(r.rules[2].is_global && !r.rules[0].is_global);
CHECK(r.preamble.find("import \"pe\"") != std::string::npos);
// Each rule's text is exactly its span and ends at its own closing brace.
for (const auto& rule : r.rules) {
CHECK(src[rule.end - 1] == '}');
CHECK(src.compare(rule.begin, 4, "rule") == 0 || src.compare(rule.begin, 7, "private") == 0 ||
src.compare(rule.begin, 6, "global") == 0);
}
CHECK(r.rules[0].facts.required_class == FileClass::pe);
CHECK(r.rules[0].facts.filesize_lt == 2u * 1024 * 1024);
CHECK(!r.rules[1].facts.required_class && !r.rules[1].facts.filesize_lt);
const auto ids = condition_identifiers(r.rules[1].condition);
CHECK(std::find(ids.begin(), ids.end(), "A") != ids.end());
// include directives disable partitioning.
CHECK(!split_rules("include \"other.yar\"\nrule X { condition: true }").ok);
// Unbalanced / unterminated input fails closed.
CHECK(!split_rules("rule X { strings: $a = \"oops condition: $a }").ok);
CHECK(!split_rules("rule X { condition: true ").ok);
std::cout << " PASSED" << std::endl;
}
void test_facts() {
std::cout << "Test condition_facts (top-level and only):" << std::endl;
CHECK(condition_facts("uint16(0) == 0x5a4d and $a").required_class == FileClass::pe);
CHECK(condition_facts("0x5a4d == uint16(0) and $a").required_class == FileClass::pe);
CHECK(condition_facts("uint16be(0) == 0x4d5a").required_class == FileClass::pe);
CHECK(condition_facts("pe.is_pe and $a").required_class == FileClass::pe);
CHECK(condition_facts("uint32(0) == 0x464c457f and any of them").required_class == FileClass::elf);
CHECK(condition_facts("uint32be(0) == 0x7f454c46").required_class == FileClass::elf);
CHECK(condition_facts("uint32(0) == 0xfeedfacf and $a").required_class == FileClass::macho);
CHECK(condition_facts("uint32be(0) == 0xcffaedfe").required_class == FileClass::macho);
CHECK(condition_facts("( uint16(0) == 0x5a4d and filesize < 100KB ) and 2 of them").filesize_lt == 100u * 1024);
CHECK(condition_facts("filesize <= 1MB and $a").filesize_lt == 1024u * 1024 + 1);
CHECK(condition_facts("filesize < 500 and filesize < 300").filesize_lt == 300u);
// Nothing provable: top-level or, not, other offsets / operators, quantifiers.
CHECK(!condition_facts("uint16(0) == 0x5a4d or $a").required_class);
CHECK(!condition_facts("not uint16(0) == 0x5a4d").required_class);
CHECK(!condition_facts("uint16(0) != 0x5a4d and $a").required_class);
CHECK(!condition_facts("uint16(2) == 0x5a4d").required_class);
CHECK(!condition_facts("filesize > 1MB and $a").filesize_lt);
CHECK(!condition_facts("for any i in (0..1) : (uint16(i) == 0x5a4d)").required_class);
CHECK(!condition_facts("(uint16(0) == 0x5a4d or uint32(0) == 0x464c457f) and $a").required_class);
CHECK(!condition_facts("uint32(0) == 0xcafebabe").required_class); // Java class or fat Mach-O: ambiguous
std::cout << " PASSED" << std::endl;
}
void test_classes_and_exclusion() {
std::cout << "Test file classes, buckets and exclusion:" << std::endl;
const unsigned char mz[] = {'M', 'Z', 0x90, 0};
const unsigned char elf[] = {0x7f, 'E', 'L', 'F'};
const unsigned char macho[] = {0xcf, 0xfa, 0xed, 0xfe};
const unsigned char txt[] = {'h', 'i', '!', '\n'};
CHECK(file_class(mz, 4) == FileClass::pe && file_class(elf, 4) == FileClass::elf);
CHECK(file_class(macho, 4) == FileClass::macho && file_class(txt, 4) == FileClass::other);
CHECK(file_class(mz, 1) == FileClass::other && file_class(nullptr, 0) == FileClass::other);
CHECK(partition_for(elf, 4, 0).bucket == 0 && partition_for(elf, 4, (1u << 20) - 1).bucket == 0);
CHECK(partition_for(mz, 4, 10).cls == ClassGroup::pe && partition_for(elf, 4, 10).cls == ClassGroup::nonpe);
CHECK(partition_for(macho, 4, 10).cls == ClassGroup::nonpe && partition_for(txt, 4, 10).cls == ClassGroup::nonpe);
CHECK(partition_for(elf, 4, 1u << 20).bucket == 1 && partition_for(elf, 4, 16u << 20).bucket == 3);
RuleFacts pe;
pe.required_class = FileClass::pe;
CHECK(excluded(pe, {ClassGroup::nonpe, 0}) && !excluded(pe, {ClassGroup::pe, 3}));
RuleFacts elf_only;
elf_only.required_class = FileClass::elf;
CHECK(excluded(elf_only, {ClassGroup::pe, 0}) && !excluded(elf_only, {ClassGroup::nonpe, 2}));
RuleFacts small;
small.filesize_lt = 1u << 20; // filesize < 1 MiB
CHECK(!excluded(small, {ClassGroup::nonpe, 0})); // [0, 1 MiB) can satisfy it
CHECK(excluded(small, {ClassGroup::nonpe, 1})); // every file here is >= 1 MiB
small.filesize_lt = (1u << 20) + 1; // filesize <= 1 MiB: a file of exactly 1 MiB matches
CHECK(!excluded(small, {ClassGroup::nonpe, 1}));
// Property: for every partition and every size in it, excluded(facts) implies the facts are false.
for (std::size_t p = 0; p < kPartitions; ++p) {
const auto key = PartitionKey::from_index(p);
CHECK(key.index() == p);
for (uint64_t lt : {uint64_t{1}, uint64_t{1} << 20, (uint64_t{1} << 20) + 1, uint64_t{5} << 20, uint64_t{1} << 40}) {
RuleFacts f;
f.filesize_lt = lt;
if (excluded(f, key)) {
const uint64_t lo = kBucketLow[key.bucket];
CHECK(!(lo < lt)); // the smallest file in the bucket already fails filesize < lt
}
}
}
std::cout << " PASSED" << std::endl;
}
void test_real_pack() {
std::cout << "Test split_rules on the bundled rule pack:" << std::endl;
const std::string path = std::string(STRAWBERRY_SOURCE_ROOT) + "/packaging/rules-snapshot/yara-forge-core/yara-rules-core.yar";
std::ifstream in(path, std::ios::binary);
if (!in) {
std::cout << " SKIP (no snapshot at " << path << ")" << std::endl;
return;
}
const std::string src((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>());
const auto r = split_rules(src);
if (!r.ok) std::cerr << "split error: " << r.error << std::endl;
CHECK(r.ok);
CHECK(r.rules.size() == 5132); // libyara's count for this pack (rules check)
std::size_t pe = 0, elf = 0, fsz = 0;
for (const auto& rule : r.rules) {
CHECK(rule.end > rule.begin && src[rule.end - 1] == '}');
if (rule.facts.required_class == FileClass::pe) ++pe;
if (rule.facts.required_class == FileClass::elf) ++elf;
if (rule.facts.filesize_lt) ++fsz;
}
std::size_t elf_big = 0;
for (const auto& rule : r.rules) {
if (!excluded(rule.facts, {ClassGroup::nonpe, 2})) ++elf_big;
}
std::cout << " " << r.rules.size() << " rules; requires MZ: " << pe << ", ELF: " << elf
<< ", filesize bound: " << fsz << "; kept for non-PE 4-16 MiB: " << elf_big << std::endl;
CHECK(pe > 1000 && fsz > 2000 && elf_big < 2500);
std::cout << " PASSED" << std::endl;
}
} // namespace
int main() {
test_split_tricky();
test_facts();
test_classes_and_exclusion();
test_real_pack();
std::cout << "All rule partition tests passed!" << std::endl;
return 0;
}