// Tokenizer and rarity model. A failure prints the seed; re-run with // STRAWBERRY_PROPERTY_SEED=. // // tokenize cases: users, pids, versions, temp names, flags, URLs, ... // T1 path_template is idempotent and bounded; cmdline_shape is bounded // K1 count-min never underestimates (also after decay) // K2 deterministic: same observations, same scores // K3 never-seen is more surprising than common; decay halves counts per // half-life; first-seen is bounded and remembers the first time // R1 a rarity state file restores the same scores, decay clock and // first-seen table, and re-encodes to the same bytes // R2 a corrupt, truncated, inconsistent or other-settings file is refused // with a reason, and leaves the model unchanged #include "strawberry/hash_utils.hpp" #include "strawberry/learn/rarity.hpp" #include "strawberry/learn/tokenize.hpp" #include #include #include #include #include #include #include #include #include using namespace strawberry::learn; namespace { uint64_t seed_from_env() { if (const char* text = std::getenv("STRAWBERRY_PROPERTY_SEED")) return std::strtoull(text, nullptr, 10); return std::random_device{}(); } const uint64_t kSeed = seed_from_env(); #define PROPERTY(cond) \ do { \ if (!(cond)) { \ std::cerr << "PROPERTY FAILED: " #cond " (seed " << kSeed << ", " << __FILE__ << ":" \ << __LINE__ << ")" << std::endl; \ std::abort(); \ } \ } while (0) void expect(const std::string& got, const std::string& want, const std::string& input) { if (got != want) { std::cerr << "shape(\"" << input << "\")\n got \"" << got << "\"\n want \"" << want << "\"" << std::endl; std::abort(); } } void path_is(const std::string& in, const std::string& want) { expect(path_template(in), want, in); } void shape_is(const std::string& in, const std::string& want) { expect(cmdline_shape(in), want, in); } void test_tokenize_cases() { path_is("/usr/bin/bash", "/usr/bin/bash"); path_is("/home/alice/.local/bin/tool", "/home//.local/bin/tool"); path_is("/home/bob/.cache/tmp.Xk29fQ/run-1234.sh", "/home//.cache/tmp./run-.sh"); path_is("/run/user/1000/app/x", "/run/user//app/x"); path_is("/proc/4242/exe", "/proc//exe"); path_is("/usr/lib/python3.12/site.py", "/usr/lib/python./site.py"); path_is("/opt/app/0f3a9c2b7e/bin", "/opt/app//bin"); path_is("/var/lib/x/123e4567-e89b-12d3-a456-426614174000/y", "/var/lib/x//y"); path_is("/tmp/aB3dEf9", "/tmp/"); path_is("/usr/bin/x (deleted)", "/usr/bin/x"); path_is("/memfd:payload (deleted)", "memfd:payload"); path_is("/usr/bin/sha256sum", "/usr/bin/shasum"); path_is("relative/dir", "relative/dir"); path_is("", ""); shape_is("/usr/bin/curl -fsSL https://x.example/a.sh -o /tmp/a.sh", "curl -fsSL -o "); shape_is("/usr/bin/git clone https://h/r.git /home/a/src", "git clone "); shape_is("python3 -c import os; os.system(x)", "python -c import "); // first word kept shape_is("ssh -p 2222 user@203.0.113.9", "ssh -p "); shape_is("ping 8.8.8.8", "ping "); shape_is("app --token= --level=3", "app --token= --level="); shape_is("mysql -p db", "mysql -p db"); shape_is("sh -c echo aGVsbG8gd29ybGQgaGVsbG8gd29ybGQgaGVsbG8gd29ybGQ=", "sh -c echo "); shape_is(" /bin/ls -la ", "ls -la"); shape_is("", ""); std::string many = "tool"; for (int i = 0; i < 40; ++i) many += " x"; std::string want = "tool x"; // first word kept, 15 more , the other 24 summarized for (int i = 1; i < 16; ++i) want += " "; shape_is(many, want + " <+some>"); PROPERTY(location_class("/tmp/x") == "tmp" && location_class("/dev/shm/x") == "tmp"); PROPERTY(location_class("/home/a/x") == "home" && location_class("/usr/bin/x") == "system"); PROPERTY(location_class("/memfd:x") == "memfd" && location_class("x") == "relative"); std::cout << "tokenize cases: PASSED" << std::endl; } void test_tokenize_properties() { std::mt19937_64 rng(kSeed); const std::string alphabet = "/abcXYZ0129.-_:<> "; for (int i = 0; i < 50000; ++i) { std::string s; const auto n = rng() % 80; for (std::size_t k = 0; k < n; ++k) s.push_back(alphabet[rng() % alphabet.size()]); const auto t = path_template(s); PROPERTY(t.size() <= kMaxShapeBytes); PROPERTY(path_template(t) == t); // T1 PROPERTY(cmdline_shape(s).size() <= kMaxShapeBytes + 16); } std::cout << "T1 tokenize properties: PASSED" << std::endl; } void test_sketch_properties() { std::mt19937_64 rng(kSeed); CountMinSketch sketch(8, 4); // small: plenty of collisions std::map truth; for (int i = 0; i < 20000; ++i) { const auto key = "k" + std::to_string(rng() % 2000); sketch.add(key); truth[key] += 1; if (i % 5000 == 4999) { sketch.decay(0.5); for (auto& [k, v] : truth) v *= 0.5; } } for (const auto& [k, v] : truth) PROPERTY(sketch.estimate(k) >= v - 1e-3 * v - 1e-6); // K1 std::cout << "K1 count-min never underestimates: PASSED" << std::endl; RarityModel a, b; // K2 for (int i = 0; i < 5000; ++i) { const auto t = "p" + std::to_string(rng() % 300); a.observe(TupleKind::parent_child, t); b.observe(TupleKind::parent_child, t); } for (int i = 0; i < 300; ++i) { const auto t = "p" + std::to_string(i); PROPERTY(a.surprisal(TupleKind::parent_child, t).bits == b.surprisal(TupleKind::parent_child, t).bits); } std::cout << "K2 deterministic: PASSED" << std::endl; } void test_rarity_model() { RarityModel model; const int64_t day = 24LL * 3600 * 1'000'000'000; int64_t now = 1'800'000'000LL * 1'000'000'000; model.advance_to(now); ExecContext common{"/usr/lib/systemd/systemd", "/usr/bin/bash", "/usr/bin/ls", "ls -la /home/a"}; for (int i = 0; i < 1000; ++i) (void) score_and_observe(model, exec_tuples(common)); ExecContext odd{"/usr/lib/systemd/systemd", "/usr/bin/evince", "/usr/bin/python3", "python3 -c x"}; const auto common_score = score_and_observe(model, exec_tuples(common)); const auto odd_score = score_and_observe(model, exec_tuples(odd)); PROPERTY(odd_score.bits > common_score.bits + 8); // K3 PROPERTY(odd_score.parts.front().kind == TupleKind::lineage3 || odd_score.parts.front().kind == TupleKind::parent_child || odd_score.parts.front().kind == TupleKind::exe_cmdline); PROPERTY(odd_score.parts.size() == 3 && odd_score.parts.front().count < 1.0); const auto before = model.surprisal(TupleKind::parent_child, "/usr/bin/bash > /usr/bin/ls").count; model.advance_to(now + 7 * day); // one half-life const auto after = model.surprisal(TupleKind::parent_child, "/usr/bin/bash > /usr/bin/ls").count; PROPERTY(std::fabs(after - before / 2) < before * 0.01); PROPERTY(!model.first_seen("hash-a", now).has_value()); PROPERTY(model.first_seen("hash-a", now + 5) == now); RarityOptions small; small.first_seen_capacity = 4; RarityModel bounded(small); for (int i = 0; i < 10; ++i) (void) bounded.first_seen("k" + std::to_string(i), i); PROPERTY(!bounded.first_seen("k0", 99).has_value()); // evicted: new again PROPERTY(bounded.first_seen("k9", 99) == 9); PROPERTY(address_class("127.0.0.1") == "loopback" && address_class("10.1.2.3") == "private"); PROPERTY(address_class("192.168.1.1") == "private" && address_class("8.8.8.8") == "public"); PROPERTY(address_class("::1") == "loopback" && address_class("fe80::1") == "link_local"); PROPERTY(address_class("::ffff:10.0.0.1") == "private" && address_class("999.1.1.1") == "unknown"); PROPERTY(connect_tuple("/usr/bin/curl", 2, "8.8.8.8", 443) == "/usr/bin/curl | v4 public:443"); PROPERTY(connect_tuple("/home/a/x", 2, "10.0.0.1", 40000) == "/home//x | v4 private:high"); std::cout << "K3 rarity model: PASSED (odd " << odd_score.bits << " bits vs common " << common_score.bits << ", " << model.memory_bytes() / 1024 << " KiB)" << std::endl; } void test_extreme_decay_clock() { // Checksum-valid state files can carry any signed clock value. Decay // must work even when the ordered difference cannot fit in int64_t. std::mt19937_64 rng(kSeed); RarityOptions small; small.width_log2 = 4; small.depth = 1; small.first_seen_capacity = 8; constexpr int64_t hour = 3600LL * 1'000'000'000; for (int i = 0; i < 128; ++i) { const auto begin = std::numeric_limits::min() + static_cast(rng() % hour); const auto end = std::numeric_limits::max() - static_cast(rng() % hour); RarityModel original(small); original.advance_to(begin); original.observe(TupleKind::parent_child, "a > b"); RarityModel restored(small); int64_t saved = 0; std::string error; PROPERTY(restored.decode_state(original.encode_state(end), saved, error)); PROPERTY(saved == end); restored.advance_to(saved); const auto score = restored.surprisal(TupleKind::parent_child, "a > b"); PROPERTY(score.count == 0 && std::isfinite(score.bits)); // Backward clocks still reset the decay clock without dropping data. restored.observe(TupleKind::parent_child, "a > b"); restored.advance_to(begin); PROPERTY(restored.surprisal(TupleKind::parent_child, "a > b").count == 1); } std::cout << "K3 extreme restored decay clocks: PASSED" << std::endl; } void test_rarity_state() { std::mt19937_64 rng(kSeed); const int64_t day = 24LL * 3600 * 1'000'000'000; const int64_t t0 = 1'800'000'000LL * 1'000'000'000; RarityModel a; a.advance_to(t0); std::vector> seen; for (int i = 0; i < 2000; ++i) { const auto kind = static_cast(rng() % kTupleKinds); const auto tuple = "tuple-" + std::to_string(rng() % 300); a.observe(kind, tuple); if (i % 50 == 0) seen.emplace_back(kind, tuple); } a.advance_to(t0 + 2 * day); // decayed once, decay clock moved for (int i = 0; i < 20; ++i) (void) a.first_seen("hash-" + std::to_string(i), t0 + i); const auto bytes = a.encode_state(t0 + 3 * day); RarityModel b; int64_t saved = 0; std::string error; PROPERTY(b.decode_state(bytes, saved, error) && saved == t0 + 3 * day); // R1 PROPERTY(b.encode_state(saved) == bytes); seen.emplace_back(TupleKind::exe_connect, "never seen"); for (const auto& [kind, tuple] : seen) { PROPERTY(a.surprisal(kind, tuple).bits == b.surprisal(kind, tuple).bits); PROPERTY(a.surprisal(kind, tuple).count == b.surprisal(kind, tuple).count); } PROPERTY(b.first_seen("hash-3", t0 + day) == t0 + 3); a.advance_to(t0 + 9 * day); // the restored decay clock continues b.advance_to(t0 + 9 * day); for (const auto& [kind, tuple] : seen) PROPERTY(a.surprisal(kind, tuple).count == b.surprisal(kind, tuple).count); // R2: every refusal names a reason and leaves the target as it was. RarityModel c; const auto empty = c.encode_state(0); const auto refused = [&](std::string_view file, const std::string& want) { std::string why; int64_t ts = -1; const bool ok = c.decode_state(file, ts, why); PROPERTY(!ok && why.find(want) != std::string::npos && ts == -1); PROPERTY(c.encode_state(0) == empty); }; auto flipped = bytes; flipped[rng() % (flipped.size() - 64)] ^= static_cast(1u << (rng() % 8)); refused(flipped, "checksum"); refused(std::string_view(bytes).substr(0, bytes.size() / 2), "checksum"); refused("short", "too short"); RarityOptions other; other.width_log2 = 12; refused(RarityModel(other).encode_state(0), "other rarity settings"); // A well-formed checksum over bad contents: a negative count. std::string body = bytes.substr(0, bytes.size() - 64); const float negative = -1.0f; std::memcpy(body.data() + 52 + 8, &negative, sizeof negative); // header, total, first cell body += strawberry::HashUtils::sha256_data(reinterpret_cast(body.data()), body.size()); refused(body, "bad sketch count"); std::cout << "R1 rarity state round trip, R2 refusals: PASSED (" << bytes.size() / 1024 << " KiB)" << std::endl; } } // namespace int main() { std::cout << "learn properties, seed " << kSeed << std::endl; test_tokenize_cases(); test_tokenize_properties(); test_sketch_properties(); test_rarity_model(); test_rarity_state(); test_extreme_decay_clock(); return 0; }