// Stage 7a: LogGC (LogStore::reduce_telemetry), causality-preserving telemetry // reduction. Properties over a randomized fixture store: // // P1 causality: for every flagged node, ancestry U descendants (process_exec // parent edges) over the reduced store contains the full-store set // P2 evidence stream is byte-identical before and after // P3 label / rules_generation records (evidence) are never removed // P4 flagged telemetry retained: every scan_result-with-rules, and every // process_exec of a flagged node and its chain // P5 deterministic per seed: same store bytes + seed -> identical output; // another seed keeps the same flagged-reachable set // P6 a benign reservoir survives (per entity), kept causally complete // // Stage 7b (skeleton): reduce_telemetry({seed, true}) additionally keeps the process_exec but drops the // leaf telemetry of dead benign nodes 7a could not drop whole (test_skeletonize): // P7 no process_exec lost vs 7a P8 skeleton nodes are exec-only P9 skeleton=false == 7a bytes, // skeleton=true removes a superset plus P1/P2/P5/P6 re-asserted and a keep-closure negative. // // plus: verify_store clean; records and bytes go down on benign churn; a // live subtree, unattributed records and a node touched by an active // (unsealed) record are retained; a dead subtree with a flagged descendant // is not dropped. #include "strawberry/store/log_store.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace strawberry::store; namespace fs = std::filesystem; namespace { constexpr uint64_t kDay = 86'400ull * 1'000'000'000ull; constexpr uint64_t kT0 = 1'700'000'000ull * 1'000'000'000ull; uint64_t g_clock = 1'800'000'000'000'000'000ull; const uint64_t kTotal = 1000ull << 30; StoreOptions options_for(const std::string& dir) { StoreOptions o = default_store_options(dir); o.now_ns = [] { return g_clock; }; o.disk_space = [](uint64_t& free_bytes, uint64_t& total_bytes) { free_bytes = 100ull << 30; total_bytes = kTotal; return true; }; o.min_free_bytes = 2ull << 30; o.min_free_pct = 5; o.hard_min_free_bytes = 256ull << 20; o.seal_age = std::chrono::hours(24 * 365); // only the explicit rolls below return o; } fs::path fresh(const std::string& name) { const fs::path p = fs::temp_directory_path() / ("sb-reduce-" + std::to_string(::getpid())) / name; fs::remove_all(p); fs::create_directories(p.parent_path()); return p; } std::string exec_payload(uint64_t ts, uint64_t pid, const std::string& node, const std::string& parent, const std::string& exe) { FieldWriter w; w.u64(1, ts); w.u64(2, pid); w.bytes(5, "boot-1"); w.bytes(6, exe); w.bytes(9, node); w.bytes(10, parent); return w.take(); } std::string connect_payload(uint64_t ts, uint64_t pid) { FieldWriter w; w.u64(1, ts); w.u64(2, pid); w.bytes(6, "198.51.100.7"); return w.take(); } std::string scan_payload(uint64_t ts, const std::string& node, bool rules) { FieldWriter w; w.u64(1, ts); w.bytes(3, node); if (rules) w.bytes(9, "Evil_Rule"); return w.take(); } std::string label_payload(uint64_t ts, const std::string& node) { FieldWriter w; w.u64(1, ts); w.u64(2, 1); w.bytes(3, "operator"); w.bytes(9, node); return w.take(); } std::string generation_payload(uint64_t ts) { FieldWriter w; w.u64(1, ts); w.u64(2, 7); return w.take(); } struct Builder { LogStore& store; uint64_t next_pid = 100; std::map pid_of{}; uint64_t exec(uint64_t ts, const std::string& node, const std::string& parent, const std::string& exe) { const uint64_t pid = next_pid++; pid_of[node] = pid; assert(store.append(Stream::telemetry, RecordType::process_exec, exec_payload(ts, pid, node, parent, exe))); return pid; } void connect(uint64_t ts, const std::string& node) { assert(store.append(Stream::telemetry, RecordType::connect, connect_payload(ts, pid_of.at(node)))); } void scan(uint64_t ts, const std::string& node, bool rules) { assert(store.append(Stream::telemetry, RecordType::scan_result, scan_payload(ts, node, rules))); } void seal() { assert(store.flush(Stream::telemetry, true) && store.flush(Stream::evidence, true)); assert(store.roll(Stream::telemetry)); } }; constexpr int kRoots = 150; // "make" entity constexpr int kTarRoots = 30; // Builds the fixture; returns after closing the store (the caller copies the directory). void build(const std::string& dir, uint64_t rng_seed) { StoreOpenReport report; std::string error; auto store = LogStore::open(options_for(dir), report, error); assert(store); Builder b{*store}; std::mt19937_64 rng(rng_seed); auto jitter = [&] { return static_cast(rng() % 1000) * 1'000'000ull; }; // Segment 1: init (live later), attack chain A, label-flagged L, negative case N, dead churn. b.exec(kT0, "n:init", "", "/sbin/init"); b.exec(kT0 + 1, "n:A0", "n:init", "/bin/bash"); b.exec(kT0 + 2, "n:A1", "n:A0", "/usr/bin/curl"); b.exec(kT0 + 3, "n:A2", "n:A1", "/tmp/dropper"); b.exec(kT0 + 4, "n:A4", "n:A2", "/tmp/payload"); // descendant of the flagged node b.exec(kT0 + 5, "n:A3", "n:A0", "/usr/bin/ls"); // dead benign sibling, not an ancestor b.exec(kT0 + 6, "n:L0", "n:init", "/usr/bin/python"); b.exec(kT0 + 7, "n:L1", "n:L0", "/usr/bin/nc"); // flagged by an evidence label only b.exec(kT0 + 8, "n:N0", "n:init", "/usr/bin/sshd"); b.exec(kT0 + 9, "n:N1", "n:N0", "/usr/bin/scp"); b.exec(kT0 + 10, "n:N2", "n:N1", "/tmp/implant"); // dead subtree with a flagged descendant b.exec(kT0 + 11, "n:N3", "n:N0", "/usr/bin/id"); // dead benign sibling b.connect(kT0 + 12, "n:A0"); // leaf event inside the flagged keep-closure (7b negative) b.exec(kT0 + 13, "n:P0", "n:init", "/usr/bin/part"); // dead benign prefix of a partially-live subtree (7b) b.exec(kT0 + 14, "n:P1", "n:P0", "/usr/bin/part-child"); // made live by an active record below b.connect(kT0 + 15, "n:P0"); for (int i = 0; i < kRoots; ++i) { const std::string root = "n:B" + std::to_string(i); const uint64_t ts = kT0 + kDay / 4 + jitter(); b.exec(ts, root, "n:init", "/usr/bin/make"); b.exec(ts + 1, root + "c0", root, "/usr/bin/cc"); b.exec(ts + 2, root + "c1", root, "/usr/bin/ld"); b.connect(ts + 3, root + "c0"); b.connect(ts + 4, root + "c1"); b.connect(ts + 5, root); } b.seal(); // Segment 2: more churn of another entity, the detections, an unattributed event. for (int i = 0; i < kTarRoots; ++i) { const std::string root = "n:T" + std::to_string(i); const uint64_t ts = kT0 + kDay / 2 + jitter(); b.exec(ts, root, "n:init", "/usr/bin/tar"); b.exec(ts + 1, root + "c0", root, "/usr/bin/gzip"); b.connect(ts + 2, root + "c0"); } b.connect(kT0 + kDay / 2 + 1000, "n:A3"); b.scan(kT0 + kDay / 2 + 2000, "n:A2", true); b.scan(kT0 + kDay / 2 + 2001, "n:N2", true); b.scan(kT0 + kDay / 2 + 2002, "n:B7", false); // a clean scan: kept either way assert(store->append(Stream::telemetry, RecordType::connect, connect_payload(kT0 + kDay / 2 + 3000, 999'999))); // no exec b.seal(); // Segment 3: the live subtree (newest sealed ts, so it sets the horizon) and init activity. const uint64_t live = kT0 + 10 * kDay; b.exec(live, "n:V0", "n:init", "/usr/bin/live"); b.exec(live + 1, "n:V1", "n:V0", "/usr/bin/live-child"); b.connect(live + 2, "n:V1"); b.connect(live + 3, "n:init"); b.seal(); // Evidence: a label for L1 (the only flag besides the scan results), a generation. assert(store->append(Stream::evidence, RecordType::label, label_payload(kT0 + 20, "n:L1"))); assert(store->append(Stream::evidence, RecordType::rules_generation, generation_payload(kT0 + 21))); assert(store->flush(Stream::evidence, true)); assert(store->roll(Stream::evidence)); // Active (unsealed) telemetry touching a dead churn node: it must stay whole. assert(store->append(Stream::telemetry, RecordType::connect, connect_payload(kT0 + kDay / 4 + 50, b.pid_of.at("n:B5c0")))); assert(store->append(Stream::telemetry, RecordType::connect, connect_payload(kT0 + kDay / 4 + 60, b.pid_of.at("n:P1")))); assert(store->flush(Stream::telemetry, true)); // `store` is destroyed here: flush + unlock. } struct Rec { uint32_t type; std::string payload; }; std::vector read_stream(const LogStore& store, Stream stream) { std::vector out; store.scan(stream, [&](uint32_t type, std::string_view p) { out.push_back({type, std::string(p)}); }); return out; } std::string bytes_field(const std::string& payload, uint32_t tag) { FieldReader r(payload); Field f; std::string out; while (r.next(f)) { if (f.tag == tag && f.type == WireType::bytes) out = std::string(f.bytes); } return out; } std::map parents_of(const std::vector& recs) { std::map out; for (const auto& r : recs) { if (r.type == static_cast(RecordType::process_exec)) out[bytes_field(r.payload, 9)] = bytes_field(r.payload, 10); } return out; } std::set reach(const std::map& parent, const std::string& node) { std::set out; for (std::string cur = node; !cur.empty() && out.insert(cur).second;) { const auto it = parent.find(cur); if (it == parent.end()) break; cur = it->second; } std::vector stack{node}; std::set down; while (!stack.empty()) { const std::string cur = stack.back(); stack.pop_back(); if (!down.insert(cur).second) continue; for (const auto& [child, par] : parent) { if (par == cur) stack.push_back(child); } } out.insert(down.begin(), down.end()); return out; } std::set exec_nodes(const std::vector& recs) { std::set out; for (const auto& r : recs) { if (r.type == static_cast(RecordType::process_exec)) out.insert(bytes_field(r.payload, 9)); } return out; } uint64_t count_type(const std::vector& recs, RecordType type) { uint64_t n = 0; for (const auto& r : recs) n += r.type == static_cast(type); return n; } std::string dir_bytes(const std::string& dir) { std::vector files; for (const auto& e : fs::directory_iterator(dir)) { if (e.is_regular_file()) files.push_back(e.path()); } std::sort(files.begin(), files.end()); std::string out; for (const auto& f : files) { std::ifstream in(f, std::ios::binary); out += f.filename().string() + "\n"; out.append(std::istreambuf_iterator(in), std::istreambuf_iterator()); } return out; } struct Outcome { ReduceReport report; bool ok = false; std::vector telemetry_before, telemetry_after; std::string evidence_before, evidence_after; std::string telemetry_files_after; std::vector evidence_recs_before, evidence_recs_after; }; Outcome reduce_dir_opts(const std::string& dir, const ReduceOptions* opts, uint64_t seed) { Outcome o; { StoreOpenReport report; std::string error; auto store = LogStore::open(options_for(dir), report, error); assert(store); o.telemetry_before = read_stream(*store, Stream::telemetry); o.evidence_recs_before = read_stream(*store, Stream::evidence); o.evidence_before = dir_bytes(dir + "/evidence"); o.ok = opts ? store->reduce_telemetry(*opts, o.report) : store->reduce_telemetry(seed, o.report); o.telemetry_after = read_stream(*store, Stream::telemetry); o.evidence_recs_after = read_stream(*store, Stream::evidence); o.evidence_after = dir_bytes(dir + "/evidence"); } o.telemetry_files_after = dir_bytes(dir + "/telemetry"); return o; } Outcome reduce_dir(const std::string& dir, uint64_t seed) { return reduce_dir_opts(dir, nullptr, seed); } Outcome reduce_dir(const std::string& dir, const ReduceOptions& opts) { return reduce_dir_opts(dir, &opts, opts.seed); } const std::vector kFlagged = {"n:A2", "n:N2", "n:L1"}; void check_flagged_reachability(const Outcome& o) { const auto full = parents_of(o.telemetry_before); const auto reduced = parents_of(o.telemetry_after); for (const auto& f : kFlagged) { const auto before = reach(full, f); const auto after = reach(reduced, f); for (const auto& n : before) assert(after.contains(n)); // P1: superset (in fact equal) } } void test_reduce() { const auto base = fresh("base").string(); build(base, 42); const auto copy_a = (fs::path(base).parent_path() / "copy_a").string(); const auto copy_b = (fs::path(base).parent_path() / "copy_b").string(); const auto copy_c = (fs::path(base).parent_path() / "copy_c").string(); for (const auto& c : {copy_a, copy_b, copy_c}) { fs::remove_all(c); fs::copy(base, c, fs::copy_options::recursive); } const Outcome a = reduce_dir(copy_a, 1); assert(a.ok && a.report.problems.empty()); assert(a.report.segments >= 1 && a.report.flagged_nodes == 3); assert(a.report.subtrees_dropped > 0 && a.report.subtrees_reserved >= 1); assert(a.report.unattributed_records >= 1); // Golden: records and bytes down on heavy benign churn. assert(a.report.records_after < a.report.records_before && a.report.bytes_after < a.report.bytes_before); assert(a.telemetry_after.size() < a.telemetry_before.size()); // P1 check_flagged_reachability(a); // P2 + P3: evidence byte-identical, label/generation present. assert(a.evidence_before == a.evidence_after); assert(count_type(a.evidence_recs_after, RecordType::label) == 1); assert(count_type(a.evidence_recs_after, RecordType::rules_generation) == 1); assert(a.evidence_recs_before.size() == a.evidence_recs_after.size()); // P4: scan_results (all kept), the flagged chains, and the negative case. assert(count_type(a.telemetry_after, RecordType::scan_result) == count_type(a.telemetry_before, RecordType::scan_result)); const auto kept = exec_nodes(a.telemetry_after); for (const char* n : {"n:init", "n:A0", "n:A1", "n:A2", "n:A4", "n:L0", "n:L1", "n:N0", "n:N1", "n:N2"}) { assert(kept.contains(n)); } // A live subtree and the node touched by an active record survive whole. for (const char* n : {"n:V0", "n:V1", "n:B5", "n:B5c0"}) assert(kept.contains(n)); uint64_t connects_before = count_type(a.telemetry_before, RecordType::connect); assert(count_type(a.telemetry_after, RecordType::connect) < connects_before); bool unattributed_kept = false; for (const auto& r : a.telemetry_after) { if (r.type != static_cast(RecordType::connect)) continue; FieldReader rd(r.payload); Field f; while (rd.next(f)) unattributed_kept |= f.tag == 2 && f.value == 999'999; } assert(unattributed_kept); // P6: a benign reservoir survives per entity, each kept subtree causally complete. uint64_t make_roots = 0, tar_roots = 0; for (int i = 0; i < kRoots; ++i) { const std::string root = "n:B" + std::to_string(i); const bool has_root = kept.contains(root); assert(has_root == kept.contains(root + "c0")); if (i != 5) assert(has_root == kept.contains(root + "c1")); // B5c1 is its own GC root under a live parent make_roots += has_root; } for (int i = 0; i < kTarRoots; ++i) { const std::string root = "n:T" + std::to_string(i); assert(kept.contains(root) == kept.contains(root + "c0")); tar_roots += kept.contains(root); } assert(make_roots >= 1 && make_roots < static_cast(kRoots)); // some negatives kept, most dropped assert(tar_roots >= 1 && tar_roots < static_cast(kTarRoots)); // verify_store clean after. const VerifyReport verify = verify_store(copy_a); assert(verify.manifest_ok && verify.problems.empty()); // P5: same bytes + same seed -> identical output; another seed keeps the flagged-reachable set. const Outcome b = reduce_dir(copy_b, 1); assert(b.ok && b.telemetry_files_after == a.telemetry_files_after); const Outcome c = reduce_dir(copy_c, 2); assert(c.ok && c.report.problems.empty()); check_flagged_reachability(c); assert(c.evidence_before == c.evidence_after); const auto kept_c = exec_nodes(c.telemetry_after); for (const char* n : {"n:A2", "n:L1", "n:N2", "n:V1", "n:B5c0"}) assert(kept_c.contains(n)); std::cout << "store reduce (P1-P6, golden, determinism): PASSED" << std::endl; } // node -> pid from the process_exec records. std::map pids_of(const std::vector& recs) { std::map out; for (const auto& r : recs) { if (r.type != static_cast(RecordType::process_exec)) continue; FieldReader rd(r.payload); Field f; while (rd.next(f)) { if (f.tag == 2 && f.type == WireType::varint) out[bytes_field(r.payload, 9)] = f.value; } } return out; } uint64_t leaf_count(const std::vector& recs, uint64_t pid) { uint64_t n = 0; for (const auto& r : recs) { const auto t = static_cast(r.type); if (t != RecordType::connect && t != RecordType::file_write && t != RecordType::ptrace && t != RecordType::module_load && t != RecordType::guard_decision) { continue; } FieldReader rd(r.payload); Field f; while (rd.next(f)) n += (f.tag == 2 && f.value == pid) ? 1 : 0; } return n; } std::multiset record_bag(const std::vector& recs) { std::multiset out; for (const auto& r : recs) out.insert(std::to_string(r.type) + ":" + r.payload); return out; } void test_skeletonize() { const auto base = fresh("skel_base").string(); build(base, 42); const auto parent = fs::path(base).parent_path(); std::vector copies; for (const char* name : {"s_7a", "s_off", "s_on", "s_on2"}) { const auto c = (parent / name).string(); fs::remove_all(c); fs::copy(base, c, fs::copy_options::recursive); copies.push_back(c); } const Outcome a = reduce_dir(copies[0], 1); // one-arg 7a wrapper const Outcome off = reduce_dir(copies[1], ReduceOptions{1, false, false}); // options, skeleton off const Outcome on = reduce_dir(copies[2], ReduceOptions{1, true, false}); const Outcome on2 = reduce_dir(copies[3], ReduceOptions{1, true, false}); assert(a.ok && off.ok && on.ok && on2.ok); assert(a.report.problems.empty() && on.report.problems.empty()); // P9: skeleton=false is byte-identical to 7a (and does no skeleton work). assert(off.telemetry_files_after == a.telemetry_files_after); assert(a.report.nodes_skeletonized == 0 && a.report.leaf_records_dropped == 0); assert(off.report.nodes_skeletonized == 0 && off.report.leaf_records_dropped == 0); // P9: skeleton=true removes strictly more, and a superset of what 7a removes. assert(on.report.records_after < a.report.records_after && a.report.records_after <= a.report.records_before); assert(on.report.leaf_records_dropped > 0 && on.report.nodes_skeletonized >= 2); assert(a.telemetry_after.size() - on.telemetry_after.size() == on.report.leaf_records_dropped); { const auto bag_a = record_bag(a.telemetry_after); const auto bag_on = record_bag(on.telemetry_after); for (const auto& r : bag_on) assert(bag_a.count(r) > 0); // every survivor of 7b survived 7a } assert(on.report.subtrees_dropped == a.report.subtrees_dropped && on.report.subtrees_reserved == a.report.subtrees_reserved); // P7: no process_exec lost relative to 7a; the parent graph is identical. assert(exec_nodes(on.telemetry_after) == exec_nodes(a.telemetry_after)); assert(parents_of(on.telemetry_after) == parents_of(a.telemetry_after)); // P8: skeleton nodes keep their exec and have zero leaf telemetry; 7a kept their leaves. const auto pids = pids_of(on.telemetry_after); const auto execs_on = exec_nodes(on.telemetry_after); for (const char* n : {"n:P0", "n:B5"}) { assert(execs_on.contains(n)); assert(leaf_count(a.telemetry_after, pids.at(n)) > 0); assert(leaf_count(on.telemetry_after, pids.at(n)) == 0); } // Never skeletonized: the flagged keep-closure (A0), live nodes (V1, init, and the nodes with an active // record B5c0 / P1), and unattributed records. for (const char* n : {"n:A0", "n:V1", "n:init", "n:B5c0", "n:P1"}) { assert(leaf_count(on.telemetry_after, pids.at(n)) == leaf_count(on.telemetry_before, pids.at(n))); assert(leaf_count(on.telemetry_after, pids.at(n)) > 0); } assert(leaf_count(on.telemetry_after, 999'999) == 1); assert(count_type(on.telemetry_after, RecordType::scan_result) == count_type(on.telemetry_before, RecordType::scan_result)); // P6: reservoir roots still carry their full-detail leaf telemetry (7b never touches them). uint64_t reserved_with_leaf = 0; for (int i = 0; i < kRoots; ++i) { if (i == 5) continue; const std::string root = "n:B" + std::to_string(i); if (!pids.contains(root)) continue; assert(leaf_count(on.telemetry_after, pids.at(root)) == 1); ++reserved_with_leaf; } assert(reserved_with_leaf >= 1); // P1, P2, P3: flagged reachability, evidence untouched. check_flagged_reachability(on); assert(on.evidence_before == on.evidence_after); assert(count_type(on.evidence_recs_after, RecordType::label) == 1); assert(count_type(on.evidence_recs_after, RecordType::rules_generation) == 1); const VerifyReport verify = verify_store(copies[2]); assert(verify.manifest_ok && verify.problems.empty()); // P5: deterministic per (seed, options). assert(on2.telemetry_files_after == on.telemetry_files_after); std::cout << "store reduce skeleton (P5-P9, keep-closure negative): PASSED" << std::endl; } // 7c fixture helpers. std::string connect_to_payload(uint64_t ts, uint64_t pid, const std::string& addr, uint64_t port) { FieldWriter w; w.u64(1, ts); w.u64(2, pid); w.bytes(6, addr); w.u64(7, port); return w.take(); } // Counts connect records of `pid` to `addr` with ts >= min_ts. uint64_t connects_to(const std::vector& recs, uint64_t pid, const std::string& addr, uint64_t min_ts = 0) { uint64_t n = 0; for (const auto& r : recs) { if (r.type != static_cast(RecordType::connect)) continue; uint64_t rec_pid = 0, ts = 0; std::string a; FieldReader rd(r.payload); Field f; while (rd.next(f)) { if (f.tag == 1 && f.type == WireType::varint) ts = f.value; if (f.tag == 2 && f.type == WireType::varint) rec_pid = f.value; if (f.tag == 6 && f.type == WireType::bytes) a = std::string(f.bytes); } n += (rec_pid == pid && a == addr && ts >= min_ts) ? 1 : 0; } return n; } constexpr uint64_t kMergeKeepHeadT = 4, kMergeKeepTailT = 1; // mirror of the store's kMergeKeepHead/kMergeKeepTail void build_merge(const std::string& dir, uint64_t& pid_d, uint64_t& pid_f) { StoreOpenReport report; std::string error; auto store = LogStore::open(options_for(dir), report, error); assert(store); Builder b{*store}; // Segment 1 (OLD): init, live daemon D, flagged F, with repeated connects. b.exec(kT0, "n:init", "", "/sbin/init"); pid_d = b.exec(kT0 + 1, "n:D", "n:init", "/usr/bin/daemon"); pid_f = b.exec(kT0 + 2, "n:F", "n:init", "/tmp/implant"); for (uint64_t i = 0; i < 1000; ++i) { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(kT0 + kDay + i, pid_d, "203.0.113.1", 443))); } for (uint64_t i = 0; i < 6; ++i) { // second target, <= kMergeMinRepeat: kept in full assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(kT0 + kDay + 2000 + i, pid_d, "203.0.113.2", 443))); } for (uint64_t i = 0; i < 40; ++i) { // flagged node, same repetition: must never be merged assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(kT0 + kDay + 3000 + i, pid_f, "203.0.113.1", 443))); } b.scan(kT0 + kDay + 4000, "n:F", true); b.seal(); // Segment 2 (newest sealed; sets the horizon = newest - 2 days): RECENT connects of D to the SAME target. const uint64_t recent = kT0 + 10 * kDay; for (uint64_t i = 0; i < 10; ++i) { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(recent + i, pid_d, "203.0.113.1", 443))); } b.exec(recent + 100, "n:V", "n:init", "/usr/bin/live"); b.seal(); // Active (unsealed) record keeps D live. assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(recent + 200, pid_d, "203.0.113.3", 80))); assert(store->flush(Stream::telemetry, true)); } void test_merge() { const auto base = fresh("merge_base").string(); uint64_t pid_d = 0, pid_f = 0; build_merge(base, pid_d, pid_f); const auto parent = fs::path(base).parent_path(); std::vector copies; for (const char* name : {"m_7a", "m_off", "m_skel", "m_on", "m_on2"}) { const auto c = (parent / name).string(); fs::remove_all(c); fs::copy(base, c, fs::copy_options::recursive); copies.push_back(c); } const Outcome a = reduce_dir(copies[0], 1); // one-arg 7a wrapper const Outcome off = reduce_dir(copies[1], ReduceOptions{1, false, false}); // merge off const Outcome skel = reduce_dir(copies[2], ReduceOptions{1, true, false}); // 7b path const Outcome on = reduce_dir(copies[3], ReduceOptions{1, false, true}); const Outcome on2 = reduce_dir(copies[4], ReduceOptions{1, false, true}); assert(a.ok && off.ok && skel.ok && on.ok && on2.ok); assert(on.report.problems.empty()); // P14: merge=false is byte-identical to 7a (one-arg wrapper) and does no merge work. assert(off.telemetry_files_after == a.telemetry_files_after); assert(off.report.merge_groups == 0 && off.report.records_merged == 0); assert(skel.report.merge_groups == 0 && skel.report.records_merged == 0); // P14: deterministic per (seed, options). assert(on2.telemetry_files_after == on.telemetry_files_after); // P11: the 1000-record group keeps head + tail + a sample (not 0, not all); the small group is whole. const uint64_t recent_floor = kT0 + 5 * kDay; // well above the old records, below the horizon + recent ones const uint64_t old_x = connects_to(on.telemetry_after, pid_d, "203.0.113.1", 0) - connects_to(on.telemetry_after, pid_d, "203.0.113.1", recent_floor); assert(old_x >= kMergeKeepHeadT + kMergeKeepTailT && old_x < 1000); assert(connects_to(on.telemetry_after, pid_d, "203.0.113.2") == 6); assert(connects_to(on.telemetry_after, pid_d, "203.0.113.3") == 1); // active segment untouched // P12: all 10 recent connects (same tuple, ts >= horizon) survive. assert(connects_to(on.telemetry_after, pid_d, "203.0.113.1", recent_floor) == 10); // P13: the flagged node's connects all survive. assert(connects_to(on.telemetry_after, pid_f, "203.0.113.1") == 40); // P10: execs and the parent graph are identical to merge=false. assert(exec_nodes(on.telemetry_after) == exec_nodes(off.telemetry_after)); assert(parents_of(on.telemetry_after) == parents_of(off.telemetry_after)); assert(count_type(on.telemetry_after, RecordType::process_exec) == count_type(off.telemetry_after, RecordType::process_exec)); assert(count_type(on.telemetry_after, RecordType::scan_result) == count_type(off.telemetry_after, RecordType::scan_result)); // P15: bookkeeping is exact and merge only removes (survivors are a subset of the merge=false survivors). assert(on.report.merge_groups == 1); assert(on.report.records_merged > 0); assert(on.report.records_after < off.report.records_after); assert(off.telemetry_after.size() - on.telemetry_after.size() == on.report.records_merged); assert(on.report.records_before - on.report.records_after == off.report.records_before - off.report.records_after + on.report.records_merged); assert(on.report.subtrees_dropped == off.report.subtrees_dropped && on.report.leaf_records_dropped == 0); { const auto bag_off = record_bag(off.telemetry_after); for (const auto& r : record_bag(on.telemetry_after)) assert(bag_off.count(r) > 0); } assert(on.evidence_before == on.evidence_after); const VerifyReport verify = verify_store(copies[3]); assert(verify.manifest_ok && verify.problems.empty()); std::cout << "store reduce merge (P10-P15; old kept " << old_x << "/1000, recent 10/10, merged " << on.report.records_merged << "): PASSED" << std::endl; } // ---- 7c horizon / 7d CPR fixtures ---- ReduceOptions merge_opts(MergeMode mode, int64_t horizon_ns) { ReduceOptions o; o.seed = 1; o.merge_redundant = true; o.merge_mode = mode; o.merge_horizon_ns = horizon_ns; return o; } // H1/H2: a live node with 30 accesses 1.5 days before the newest sealed record and 20 accesses 30 min before it. void build_horizon(const std::string& dir, uint64_t& pid_d) { StoreOpenReport report; std::string error; auto store = LogStore::open(options_for(dir), report, error); assert(store); Builder b{*store}; const uint64_t newest = kT0 + 10 * kDay; b.exec(kT0, "n:init", "", "/sbin/init"); pid_d = b.exec(kT0 + 1, "n:D", "n:init", "/usr/bin/daemon"); for (uint64_t i = 0; i < 30; ++i) { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(newest - 36 * kDay / 24 + i, pid_d, "203.0.113.9", 443))); } b.seal(); for (uint64_t i = 0; i < 20; ++i) { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(newest - 30 * 60 * 1'000'000'000ull + i, pid_d, "203.0.113.9", 443))); } b.exec(newest, "n:V", "n:init", "/usr/bin/live"); b.seal(); assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(newest + 200, pid_d, "203.0.113.3", 80))); assert(store->flush(Stream::telemetry, true)); } void test_horizon() { const auto base = fresh("hor_base").string(); uint64_t pid_d = 0; build_horizon(base, pid_d); const auto parent = fs::path(base).parent_path(); const char* names[] = {"h_def", "h_2d", "h_6h", "h_1ns", "h_cpr6h", "h_cpr1ns"}; std::vector copies; for (const char* name : names) { const auto c = (parent / name).string(); fs::remove_all(c); fs::copy(base, c, fs::copy_options::recursive); copies.push_back(c); } const uint64_t newest = kT0 + 10 * kDay; const uint64_t recent_floor = newest - 3600ull * 1'000'000'000ull; const Outcome def = reduce_dir(copies[0], merge_opts(MergeMode::sample, 0)); const Outcome two = reduce_dir(copies[1], merge_opts(MergeMode::sample, static_cast(2 * kDay))); const Outcome h6 = reduce_dir(copies[2], merge_opts(MergeMode::sample, static_cast(6 * kDay / 24))); const Outcome h1 = reduce_dir(copies[3], merge_opts(MergeMode::sample, 1)); // clamped up to 1 h const Outcome c6 = reduce_dir(copies[4], merge_opts(MergeMode::cpr, static_cast(6 * kDay / 24))); const Outcome c1 = reduce_dir(copies[5], merge_opts(MergeMode::cpr, 1)); assert(def.ok && two.ok && h6.ok && h1.ok && c6.ok && c1.ok); // H1: default (0) == explicit 2 days, byte for byte; the 1.5-day-old accesses are not merged. assert(def.report.records_after == two.report.records_after); assert(def.report.records_merged == two.report.records_merged && def.report.merge_groups == two.report.merge_groups); assert(def.telemetry_files_after == two.telemetry_files_after); assert(connects_to(def.telemetry_after, pid_d, "203.0.113.9") == 50); // H2: a 6 h horizon merges the 1.5-day-old group; the 30-min-old accesses survive any horizon (clamped to 1 h). assert(h6.report.records_merged > 0 && h6.report.merge_groups == 1); assert(connects_to(h6.telemetry_after, pid_d, "203.0.113.9") < 50); assert(connects_to(h6.telemetry_after, pid_d, "203.0.113.9", recent_floor) == 20); assert(h1.report.records_merged > 0); assert(connects_to(h1.telemetry_after, pid_d, "203.0.113.9", recent_floor) == 20); // CPR: the old uninterrupted run collapses to its first + last; the recent run is untouched. assert(c6.report.records_merged == 28 && c6.report.merge_groups == 1); assert(connects_to(c6.telemetry_after, pid_d, "203.0.113.9") == 22); assert(c1.report.records_merged == 28); assert(connects_to(c1.telemetry_after, pid_d, "203.0.113.9", recent_floor) == 20); assert(exec_nodes(c1.telemetry_after) == exec_nodes(def.telemetry_after)); std::cout << "store reduce merge horizon (H1-H2): PASSED" << std::endl; } // CPR: events per node: action 0..2 = connect to X/Y/Z, 3 = exec a child of the node. struct CprEv { std::size_t node; int action; }; const char* const kCprAddr[3] = {"203.0.113.10", "203.0.113.11", "203.0.113.12"}; struct CprFixture { std::vector pids; // per node std::vector names; // per node std::vector ev_ts; // per event }; CprFixture build_cpr(const std::string& dir, std::size_t nodes, const std::vector& events) { StoreOpenReport report; std::string error; auto store = LogStore::open(options_for(dir), report, error); assert(store); Builder b{*store}; CprFixture fx; b.exec(kT0, "n:init", "", "/sbin/init"); for (std::size_t i = 0; i < nodes; ++i) { fx.names.push_back("n:P" + std::to_string(i)); fx.pids.push_back(b.exec(kT0 + 1 + i, fx.names.back(), "n:init", "/usr/bin/p")); } uint64_t ts = kT0 + kDay; uint64_t child_no = 0; std::vector child_pids; for (const auto& ev : events) { fx.ev_ts.push_back(ts); if (ev.action == 3) { const std::string name = "n:C" + std::to_string(child_no++); child_pids.push_back(b.exec(ts, name, fx.names[ev.node], "/usr/bin/c")); } else { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(ts, fx.pids[ev.node], kCprAddr[ev.action], 443))); } ++ts; } b.seal(); b.exec(kT0 + 10 * kDay, "n:V", "n:init", "/usr/bin/live"); b.seal(); // Active records keep every node and child live, so 7a never drops an exec the interleave check saw. for (const uint64_t pid : fx.pids) { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(kT0 + 10 * kDay + 5, pid, "203.0.113.99", 80))); } for (const uint64_t pid : child_pids) { assert(store->append(Stream::telemetry, RecordType::connect, connect_to_payload(kT0 + 10 * kDay + 5, pid, "203.0.113.99", 80))); } assert(store->flush(Stream::telemetry, true)); return fx; } struct KeyTs { std::string key; uint64_t ts; }; // The per-node action sequence (connect target or "E" for a child exec), in store order, excluding the // active-segment records (ts > the fixture's old window). std::vector node_sequence(const std::vector& recs, const std::string& node, uint64_t pid) { std::vector out; for (const auto& r : recs) { uint64_t rec_pid = 0, ts = 0; FieldReader rd(r.payload); Field f; while (rd.next(f)) { if (f.tag == 1 && f.type == WireType::varint) ts = f.value; if (f.tag == 2 && f.type == WireType::varint) rec_pid = f.value; } if (ts >= kT0 + 5 * kDay || ts < kT0 + kDay) continue; if (r.type == static_cast(RecordType::connect) && rec_pid == pid) { out.push_back({bytes_field(r.payload, 6), ts}); } else if (r.type == static_cast(RecordType::process_exec) && bytes_field(r.payload, 10) == node) { out.push_back({"E", ts}); } } return out; } std::vector collapse_runs(const std::vector& seq) { std::vector out; for (const auto& k : seq) { if (out.empty() || out.back() != k.key) out.push_back(k.key); } return out; } void check_cpr_properties(const CprFixture& fx, const Outcome& o) { for (std::size_t n = 0; n < fx.names.size(); ++n) { const auto before = node_sequence(o.telemetry_before, fx.names[n], fx.pids[n]); const auto after = node_sequence(o.telemetry_after, fx.names[n], fx.pids[n]); // C1: the run-length-collapsed sequence is exactly preserved. assert(collapse_runs(before) == collapse_runs(after)); // C1: every group's first and last occurrence survives; exec records are never dropped. std::set kept_ts; for (const auto& k : after) kept_ts.insert(k.ts); std::map> first_last; for (const auto& k : before) { auto it = first_last.find(k.key); if (it == first_last.end()) first_last[k.key] = {k.ts, k.ts}; else it->second.second = k.ts; if (k.key == "E") assert(kept_ts.contains(k.ts)); } for (const auto& [key, fl] : first_last) { assert(kept_ts.contains(fl.first) && kept_ts.contains(fl.second)); } } } void test_cpr() { // C2 (scripted): node0 X*50, child, X*50, Y, X*5; node1 X, child, X; node2 X*100. { std::vector ev; for (int i = 0; i < 50; ++i) ev.push_back({0, 0}); ev.push_back({0, 3}); for (int i = 0; i < 50; ++i) ev.push_back({0, 0}); ev.push_back({0, 1}); for (int i = 0; i < 5; ++i) ev.push_back({0, 0}); ev.push_back({1, 0}); ev.push_back({1, 3}); ev.push_back({1, 0}); for (int i = 0; i < 100; ++i) ev.push_back({2, 0}); const auto dir = fresh("cpr_c2").string(); const CprFixture fx = build_cpr(dir, 3, ev); const Outcome o = reduce_dir(dir, merge_opts(MergeMode::cpr, static_cast(6 * kDay / 24))); assert(o.ok && o.report.problems.empty()); const auto n0 = node_sequence(o.telemetry_after, fx.names[0], fx.pids[0]); std::size_t x0 = 0, y0 = 0, e0 = 0; for (const auto& k : n0) { x0 += k.key == kCprAddr[0] ? 1 : 0; y0 += k.key == kCprAddr[1] ? 1 : 0; e0 += k.key == "E" ? 1 : 0; } assert(x0 == 4 && y0 == 1 && e0 == 1); // run1 first, run2 first, run3 first + final occurrence const auto n1 = node_sequence(o.telemetry_after, fx.names[1], fx.pids[1]); assert(n1.size() == 3 && n1[0].key == kCprAddr[0] && n1[1].key == "E" && n1[2].key == kCprAddr[0]); const auto n2 = node_sequence(o.telemetry_after, fx.names[2], fx.pids[2]); assert(n2.size() == 2 && n2[0].ts == fx.ev_ts[ev.size() - 100] && n2[1].ts == fx.ev_ts[ev.size() - 1]); assert(o.report.merge_groups == 2 && o.report.records_merged == 49 + 49 + 3 + 98); check_cpr_properties(fx, o); } // C1 (property, seeded): random interleaved per-node sequences with long runs. for (uint64_t seed = 1; seed <= 6; ++seed) { std::mt19937_64 rng(seed * 7919); constexpr std::size_t kNodes = 4; std::vector last(kNodes, -1); std::vector ev; for (int i = 0; i < 400; ++i) { const std::size_t n = rng() % kNodes; int action; if (last[n] >= 0 && last[n] != 3 && rng() % 10 < 7) action = last[n]; else action = static_cast(rng() % (rng() % 6 == 0 ? 4 : 3)); last[n] = action; ev.push_back({n, action}); } const auto dir = fresh("cpr_c1_" + std::to_string(seed)).string(); const CprFixture fx = build_cpr(dir, kNodes, ev); const Outcome o = reduce_dir(dir, merge_opts(MergeMode::cpr, static_cast(6 * kDay / 24))); assert(o.ok && o.report.problems.empty()); check_cpr_properties(fx, o); assert(o.report.records_merged > 0); assert(o.evidence_before == o.evidence_after); } std::cout << "store reduce cpr (C1-C2): PASSED" << std::endl; } } // namespace int main() { test_reduce(); test_skeletonize(); test_merge(); test_horizon(); test_cpr(); fs::remove_all(fs::temp_directory_path() / ("sb-reduce-" + std::to_string(::getpid()))); std::cout << "store reduce: all properties hold" << std::endl; return 0; }