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>
177 lines
8.9 KiB
C++
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;
|
|
}
|