Represent full-range ordered clock differences without signed overflow and allow complete decay. Add seeded restore-clock regressions and a dedicated fuzz seed.
281 lines
13 KiB
C++
281 lines
13 KiB
C++
// Tokenizer and rarity model. A failure prints the seed; re-run with
|
|
// STRAWBERRY_PROPERTY_SEED=<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 <cstring>
|
|
|
|
#include <cmath>
|
|
#include <cstdlib>
|
|
#include <iostream>
|
|
#include <limits>
|
|
#include <map>
|
|
#include <random>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
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/<U>/.local/bin/tool");
|
|
path_is("/home/bob/.cache/tmp.Xk29fQ/run-1234.sh", "/home/<U>/.cache/tmp.<R>/run-<N>.sh");
|
|
path_is("/run/user/1000/app/x", "/run/user/<U>/app/x");
|
|
path_is("/proc/4242/exe", "/proc/<N>/exe");
|
|
path_is("/usr/lib/python3.12/site.py", "/usr/lib/python<N>.<N>/site.py");
|
|
path_is("/opt/app/0f3a9c2b7e/bin", "/opt/app/<H>/bin");
|
|
path_is("/var/lib/x/123e4567-e89b-12d3-a456-426614174000/y", "/var/lib/x/<UUID>/y");
|
|
path_is("/tmp/aB3dEf9", "/tmp/<R>");
|
|
path_is("/usr/bin/x (deleted)", "/usr/bin/x");
|
|
path_is("/memfd:payload (deleted)", "memfd:payload");
|
|
path_is("/usr/bin/sha256sum", "/usr/bin/sha<N>sum");
|
|
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 <URL:https> -o <P:tmp>");
|
|
shape_is("/usr/bin/git clone https://h/r.git /home/a/src", "git clone <URL:https> <P:home>");
|
|
shape_is("python3 -c import os; os.system(x)", "python<N> -c import <W> <W>"); // first word kept
|
|
shape_is("ssh -p 2222 user@203.0.113.9", "ssh -p <N> <W>");
|
|
shape_is("ping 8.8.8.8", "ping <IP>");
|
|
shape_is("app --token=<redacted> --level=3", "app --token=<V> --level=<V>");
|
|
shape_is("mysql -p<redacted> db", "mysql -p<V> db");
|
|
shape_is("sh -c echo aGVsbG8gd29ybGQgaGVsbG8gd29ybGQgaGVsbG8gd29ybGQ=", "sh -c echo <B64>");
|
|
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 <W>, the other 24 summarized
|
|
for (int i = 1; i < 16; ++i) want += " <W>";
|
|
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<std::string, double> 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/<U>/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<int64_t>::min() + static_cast<int64_t>(rng() % hour);
|
|
const auto end = std::numeric_limits<int64_t>::max() - static_cast<int64_t>(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<std::pair<TupleKind, std::string>> seen;
|
|
for (int i = 0; i < 2000; ++i) {
|
|
const auto kind = static_cast<TupleKind>(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<char>(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<const unsigned char*>(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;
|
|
}
|