#include "strawberry/rule_partition.hpp" #include #include #include namespace strawberry::rules { namespace { bool is_ident_start(char c) { return std::isalpha(static_cast(c)) || c == '_'; } bool is_ident_char(char c) { return std::isalnum(static_cast(c)) || c == '_'; } uint32_t le32(const unsigned char* p) { return static_cast(p[0]) | static_cast(p[1]) << 8 | static_cast(p[2]) << 16 | static_cast(p[3]) << 24; } bool is_macho_magic(uint64_t v) { return v == 0xfeedfaceULL || v == 0xfeedfacfULL || v == 0xcefaedfeULL || v == 0xcffaedfeULL; } // ---- source scanning helpers (return the index just past the construct, or npos on error) ---- constexpr std::size_t npos = std::string_view::npos; std::size_t skip_line_comment(std::string_view s, std::size_t i) { const auto e = s.find('\n', i); return e == npos ? s.size() : e + 1; } std::size_t skip_block_comment(std::string_view s, std::size_t i) { const auto e = s.find("*/", i + 2); return e == npos ? npos : e + 2; } std::size_t skip_text_string(std::string_view s, std::size_t i) { // s[i] == '"' for (std::size_t j = i + 1; j < s.size(); ++j) { if (s[j] == '\\') { ++j; continue; } if (s[j] == '"') return j + 1; if (s[j] == '\n') return npos; // text strings cannot span lines } return npos; } std::size_t skip_regex(std::string_view s, std::size_t i) { // s[i] == '/' for (std::size_t j = i + 1; j < s.size(); ++j) { if (s[j] == '\\') { ++j; continue; } if (s[j] == '/') { std::size_t k = j + 1; while (k < s.size() && std::isalpha(static_cast(s[k]))) ++k; // modifiers (i, s) return k; } if (s[j] == '\n') return npos; } return npos; } std::size_t skip_hex(std::string_view s, std::size_t i) { // s[i] == '{' for (std::size_t j = i + 1; j < s.size();) { if (s.compare(j, 2, "//") == 0) { j = skip_line_comment(s, j); } else if (s.compare(j, 2, "/*") == 0) { j = skip_block_comment(s, j); if (j == npos) return npos; } else if (s[j] == '}') { return j + 1; } else if (s[j] == '{') { return npos; // no nesting in hex strings } else { ++j; } } return npos; } std::size_t skip_ws_comments(std::string_view s, std::size_t i) { while (i < s.size()) { if (std::isspace(static_cast(s[i]))) { ++i; } else if (s.compare(i, 2, "//") == 0) { i = skip_line_comment(s, i); } else if (s.compare(i, 2, "/*") == 0) { const auto e = skip_block_comment(s, i); if (e == npos) return npos; i = e; } else { break; } } return i; } std::string_view read_ident(std::string_view s, std::size_t i) { std::size_t j = i; while (j < s.size() && is_ident_char(s[j])) ++j; return s.substr(i, j - i); } // Lex a rule body starting just after '{'. Returns the index of the closing '}' (body end) and // the condition's start, or npos on anything unexpected. std::size_t lex_body(std::string_view s, std::size_t i, std::size_t& condition_start) { enum class Section { none, meta, strings, condition } section = Section::none; condition_start = npos; bool after_matches = false; while (i < s.size()) { const char c = s[i]; if (std::isspace(static_cast(c))) { ++i; continue; } if (s.compare(i, 2, "//") == 0) { i = skip_line_comment(s, i); continue; } if (s.compare(i, 2, "/*") == 0) { i = skip_block_comment(s, i); if (i == npos) return npos; continue; } if (c == '"') { i = skip_text_string(s, i); if (i == npos) return npos; after_matches = false; continue; } if (c == '}') return i; if (c == '{') { return npos; // only valid as a hex string value (handled after '=') } if (c == '/') { if (section == Section::condition && after_matches) { i = skip_regex(s, i); if (i == npos) return npos; after_matches = false; continue; } ++i; // division operator in a condition continue; } if (c == '=' && section == Section::strings && (i + 1 >= s.size() || s[i + 1] != '=')) { std::size_t j = skip_ws_comments(s, i + 1); if (j == npos || j >= s.size()) return npos; if (s[j] == '"') { i = skip_text_string(s, j); } else if (s[j] == '{') { i = skip_hex(s, j); } else if (s[j] == '/') { i = skip_regex(s, j); } else { return npos; } if (i == npos) return npos; continue; } if (is_ident_start(c)) { const auto word = read_ident(s, i); std::size_t j = i + word.size(); const std::size_t after = skip_ws_comments(s, j); const bool colon = after != npos && after < s.size() && s[after] == ':' && (after + 1 >= s.size() || s[after + 1] != ':'); if (colon && (word == "meta" || word == "strings" || word == "condition")) { section = word == "meta" ? Section::meta : word == "strings" ? Section::strings : Section::condition; i = after + 1; if (section == Section::condition) condition_start = i; continue; } after_matches = section == Section::condition && word == "matches"; i = j; continue; } after_matches = false; ++i; } return npos; } // ---- condition tokens ---- struct Tok { enum Kind { ident, number, op, lparen, rparen, other } kind = other; std::string text; uint64_t value = 0; // numbers (suffix KB/MB applied) }; std::vector tokenize(std::string_view c, bool& ok) { std::vector out; ok = true; bool after_matches = false; for (std::size_t i = 0; i < c.size();) { const char ch = c[i]; if (std::isspace(static_cast(ch))) { ++i; continue; } if (c.compare(i, 2, "//") == 0) { i = skip_line_comment(c, i); continue; } if (c.compare(i, 2, "/*") == 0) { i = skip_block_comment(c, i); if (i == npos) { ok = false; return out; } continue; } if (ch == '"') { const auto e = skip_text_string(c, i); if (e == npos) { ok = false; return out; } out.push_back({Tok::other, std::string(c.substr(i, e - i))}); i = e; after_matches = false; continue; } if (ch == '/' && after_matches) { const auto e = skip_regex(c, i); if (e == npos) { ok = false; return out; } out.push_back({Tok::other, std::string(c.substr(i, e - i))}); i = e; after_matches = false; continue; } if (ch == '(') { out.push_back({Tok::lparen, "("}); ++i; after_matches = false; continue; } if (ch == ')') { out.push_back({Tok::rparen, ")"}); ++i; after_matches = false; continue; } if (std::isdigit(static_cast(ch))) { std::size_t j = i; uint64_t v = 0; bool parsed = false; if (c.compare(i, 2, "0x") == 0 || c.compare(i, 2, "0X") == 0) { j = i + 2; while (j < c.size() && std::isxdigit(static_cast(c[j]))) ++j; parsed = std::from_chars(c.data() + i + 2, c.data() + j, v, 16).ec == std::errc{} && j > i + 2; } else { while (j < c.size() && std::isdigit(static_cast(c[j]))) ++j; parsed = std::from_chars(c.data() + i, c.data() + j, v, 10).ec == std::errc{}; } if (!parsed) { ok = false; return out; } std::size_t k = j; while (k < c.size() && std::isspace(static_cast(c[k]))) ++k; if (c.compare(k, 2, "KB") == 0 && (k + 2 >= c.size() || !is_ident_char(c[k + 2]))) { v *= 1024; j = k + 2; } else if (c.compare(k, 2, "MB") == 0 && (k + 2 >= c.size() || !is_ident_char(c[k + 2]))) { v *= 1024 * 1024; j = k + 2; } out.push_back({Tok::number, std::string(c.substr(i, j - i)), v}); i = j; after_matches = false; continue; } if (is_ident_start(ch)) { const auto w = read_ident(c, i); out.push_back({Tok::ident, std::string(w)}); after_matches = w == "matches"; i += w.size(); continue; } // Operators: two-char first. static constexpr std::string_view two[] = {"==", "!=", "<=", ">=", "<<", ">>", ".."}; bool matched = false; for (auto op : two) { if (c.compare(i, 2, op) == 0) { out.push_back({Tok::op, std::string(op)}); i += 2; matched = true; break; } } if (!matched) { out.push_back({Tok::op, std::string(1, ch)}); ++i; } after_matches = false; } return out; } // Does [b, e) form one parenthesized group "( ... )" spanning the whole range? bool wrapped(const std::vector& t, std::size_t b, std::size_t e) { if (e - b < 2 || t[b].kind != Tok::lparen || t[e - 1].kind != Tok::rparen) return false; int depth = 0; for (std::size_t i = b; i < e; ++i) { if (t[i].kind == Tok::lparen) ++depth; if (t[i].kind == Tok::rparen) --depth; if (depth == 0 && i + 1 < e) return false; } return true; } std::optional header_term(const std::vector& t, std::size_t b, std::size_t e) { // fn ( 0 ) == N or N == fn ( 0 ) const auto is_fn = [&](std::size_t i) { return i + 3 < e && t[i].kind == Tok::ident && t[i + 1].kind == Tok::lparen && t[i + 2].kind == Tok::number && t[i + 2].value == 0 && t[i + 3].kind == Tok::rparen; }; std::string fn; uint64_t value = 0; if (e - b == 6 && is_fn(b) && t[b + 4].text == "==" && t[b + 5].kind == Tok::number) { fn = t[b].text; value = t[b + 5].value; } else if (e - b == 6 && t[b].kind == Tok::number && t[b + 1].text == "==" && is_fn(b + 2)) { fn = t[b + 2].text; value = t[b].value; } else if (e - b == 3 && t[b].kind == Tok::ident && t[b].text == "pe" && t[b + 1].text == "." && t[b + 2].kind == Tok::ident && t[b + 2].text == "is_pe") { // pe.is_pe is true only for a file with a valid DOS (MZ) header at offset 0. return FileClass::pe; } else { return std::nullopt; } const bool le16 = fn == "uint16" || fn == "uint16le"; const bool be16 = fn == "uint16be"; const bool le32 = fn == "uint32" || fn == "uint32le"; const bool be32 = fn == "uint32be"; if ((le16 && value == 0x5a4d) || (be16 && value == 0x4d5a)) return FileClass::pe; if ((le32 && value == 0x464c457f) || (be32 && value == 0x7f454c46)) return FileClass::elf; if ((le32 || be32) && is_macho_magic(value)) return FileClass::macho; // set is closed under byte swap return std::nullopt; } std::optional filesize_term(const std::vector& t, std::size_t b, std::size_t e) { if (e - b != 3 || t[b].kind != Tok::ident || t[b].text != "filesize" || t[b + 2].kind != Tok::number) { return std::nullopt; } if (t[b + 1].text == "<") return t[b + 2].value; if (t[b + 1].text == "<=" && t[b + 2].value < UINT64_MAX) return t[b + 2].value + 1; return std::nullopt; } void collect_facts(const std::vector& t, std::size_t b, std::size_t e, RuleFacts& f, int depth) { if (depth > 32 || b >= e) return; while (wrapped(t, b, e)) { ++b; --e; } // A top-level `or` (or a top-level `not`) proves nothing. int d = 0; for (std::size_t i = b; i < e; ++i) { if (t[i].kind == Tok::lparen) ++d; else if (t[i].kind == Tok::rparen) --d; else if (d == 0 && t[i].kind == Tok::ident && t[i].text == "or") return; } if (t[b].kind == Tok::ident && t[b].text == "not") return; // Split at top-level `and`. std::size_t start = b; d = 0; std::vector> conjuncts; for (std::size_t i = b; i <= e; ++i) { if (i < e && t[i].kind == Tok::lparen) ++d; else if (i < e && t[i].kind == Tok::rparen) --d; if (i == e || (d == 0 && t[i].kind == Tok::ident && t[i].text == "and")) { if (i > start) conjuncts.emplace_back(start, i); start = i + 1; } } if (conjuncts.size() == 1 && conjuncts[0].first == b && conjuncts[0].second == e) { if (const auto h = header_term(t, b, e)) { if (!f.required_class) f.required_class = *h; } else if (const auto s = filesize_term(t, b, e)) { f.filesize_lt = f.filesize_lt ? std::min(*f.filesize_lt, *s) : *s; } return; } for (const auto& [cb, ce] : conjuncts) collect_facts(t, cb, ce, f, depth + 1); } } // namespace FileClass file_class(const unsigned char* head, std::size_t head_len) { if (head == nullptr) return FileClass::other; if (head_len >= 4 && head[0] == 0x7f && head[1] == 'E' && head[2] == 'L' && head[3] == 'F') return FileClass::elf; if (head_len >= 4 && is_macho_magic(le32(head))) return FileClass::macho; if (head_len >= 2 && head[0] == 'M' && head[1] == 'Z') return FileClass::pe; return FileClass::other; } PartitionKey partition_for(const unsigned char* head, std::size_t head_len, uint64_t file_size) { uint8_t bucket = 0; for (std::size_t i = 0; i < kSizeBuckets; ++i) { if (file_size >= kBucketLow[i]) bucket = static_cast(i); } return {file_class(head, head_len) == FileClass::pe ? ClassGroup::pe : ClassGroup::nonpe, bucket}; } const char* class_group_name(ClassGroup g) { return g == ClassGroup::pe ? "pe" : "nonpe"; } const char* file_class_name(FileClass cls) { switch (cls) { case FileClass::pe: return "pe"; case FileClass::elf: return "elf"; case FileClass::macho: return "macho"; case FileClass::other: return "other"; } return "other"; } RuleFacts condition_facts(std::string_view condition) { RuleFacts f; bool ok = false; const auto toks = tokenize(condition, ok); if (!ok || toks.empty()) return f; collect_facts(toks, 0, toks.size(), f, 0); return f; } bool excluded(const RuleFacts& facts, PartitionKey key) { if (facts.required_class) { const bool needs_pe = *facts.required_class == FileClass::pe; // A PE file never has ELF/Mach-O magic; a non-PE file never starts with MZ. (Other non-PE // classes share one partition, so an ELF-only rule stays in it for Mach-O / other files.) if (key.cls == ClassGroup::pe && !needs_pe) return true; if (key.cls == ClassGroup::nonpe && needs_pe) return true; } // filesize < N is false for every file of size >= N; every file here has size >= bucket low. if (facts.filesize_lt && *facts.filesize_lt <= kBucketLow[key.bucket]) return true; return false; } std::vector condition_identifiers(std::string_view condition) { bool ok = false; const auto toks = tokenize(condition, ok); std::vector out; for (std::size_t i = 0; i < toks.size(); ++i) { // skip module members (x.y): only the left-most identifier can name a rule if (toks[i].kind == Tok::ident && !(i > 0 && toks[i - 1].text == ".")) out.push_back(toks[i].text); } return out; } SplitResult split_rules(std::string_view s) { SplitResult r; std::size_t i = 0; std::size_t text_from = 0; // start of top-level text not yet copied into the preamble while (true) { const std::size_t j = skip_ws_comments(s, i); if (j == npos) { r.error = "unterminated comment"; return r; } if (j >= s.size()) break; if (!is_ident_start(s[j])) { r.error = "unexpected top-level character at offset " + std::to_string(j); return r; } const auto word = read_ident(s, j); if (word == "import") { const std::size_t q = skip_ws_comments(s, j + word.size()); if (q == npos || q >= s.size() || s[q] != '"') { r.error = "malformed import"; return r; } const auto e = skip_text_string(s, q); if (e == npos) { r.error = "malformed import"; return r; } i = e; continue; } if (word == "include") { r.error = "include directives are not supported for partitioning"; return r; } // [private] [global] rule NAME [: tags] { const std::size_t rule_begin = j; std::size_t k = j; bool is_global = false; while (true) { k = skip_ws_comments(s, k); if (k == npos || k >= s.size() || !is_ident_start(s[k])) { r.error = "expected rule at offset " + std::to_string(j); return r; } const auto w = read_ident(s, k); k += w.size(); if (w == "private") continue; if (w == "global") { is_global = true; continue; } if (w == "rule") break; r.error = "unexpected top-level word '" + std::string(w) + "'"; return r; } k = skip_ws_comments(s, k); if (k == npos || k >= s.size() || !is_ident_start(s[k])) { r.error = "rule without a name"; return r; } const auto name = read_ident(s, k); k += name.size(); k = skip_ws_comments(s, k); if (k != npos && k < s.size() && s[k] == ':') { // tags ++k; while (true) { k = skip_ws_comments(s, k); if (k == npos || k >= s.size() || !is_ident_start(s[k])) break; k += read_ident(s, k).size(); } } if (k == npos || k >= s.size() || s[k] != '{') { r.error = "rule '" + std::string(name) + "': expected '{'"; return r; } std::size_t cond_start = npos; const std::size_t body_end = lex_body(s, k + 1, cond_start); if (body_end == npos || cond_start == npos || cond_start > body_end) { r.error = "rule '" + std::string(name) + "': could not lex body"; return r; } r.preamble.append(s.substr(text_from, rule_begin - text_from)); SplitRule rule; rule.name = std::string(name); rule.begin = rule_begin; rule.end = body_end + 1; rule.is_global = is_global; rule.condition = std::string(s.substr(cond_start, body_end - cond_start)); rule.facts = condition_facts(rule.condition); r.rules.push_back(std::move(rule)); i = body_end + 1; text_from = i; } r.preamble.append(s.substr(text_from)); r.ok = true; return r; } } // namespace strawberry::rules