strawberry/tests/test_store_reduce.cpp
trvon ebade1ba80
Store 7c/7d: tunable merge horizon + CPR interleave-aware merge mode
Co-Authored-By: Claude Sonnet 5.5 <noreply@anthropic.com>
2026-11-12 06:50:09 -07:00

922 lines
41 KiB
C++

// 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 <algorithm>
#include <cassert>
#include <cstdint>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <random>
#include <set>
#include <string>
#include <vector>
#include <unistd.h>
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<std::string, uint64_t> 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<uint64_t>(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<Rec> read_stream(const LogStore& store, Stream stream) {
std::vector<Rec> 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<std::string, std::string> parents_of(const std::vector<Rec>& recs) {
std::map<std::string, std::string> out;
for (const auto& r : recs) {
if (r.type == static_cast<uint32_t>(RecordType::process_exec)) out[bytes_field(r.payload, 9)] = bytes_field(r.payload, 10);
}
return out;
}
std::set<std::string> reach(const std::map<std::string, std::string>& parent, const std::string& node) {
std::set<std::string> 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<std::string> stack{node};
std::set<std::string> 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<std::string> exec_nodes(const std::vector<Rec>& recs) {
std::set<std::string> out;
for (const auto& r : recs) {
if (r.type == static_cast<uint32_t>(RecordType::process_exec)) out.insert(bytes_field(r.payload, 9));
}
return out;
}
uint64_t count_type(const std::vector<Rec>& recs, RecordType type) {
uint64_t n = 0;
for (const auto& r : recs) n += r.type == static_cast<uint32_t>(type);
return n;
}
std::string dir_bytes(const std::string& dir) {
std::vector<fs::path> 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<char>(in), std::istreambuf_iterator<char>());
}
return out;
}
struct Outcome {
ReduceReport report;
bool ok = false;
std::vector<Rec> telemetry_before, telemetry_after;
std::string evidence_before, evidence_after;
std::string telemetry_files_after;
std::vector<Rec> 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<std::string> 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<uint32_t>(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<uint64_t>(kRoots)); // some negatives kept, most dropped
assert(tar_roots >= 1 && tar_roots < static_cast<uint64_t>(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<std::string, uint64_t> pids_of(const std::vector<Rec>& recs) {
std::map<std::string, uint64_t> out;
for (const auto& r : recs) {
if (r.type != static_cast<uint32_t>(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<Rec>& recs, uint64_t pid) {
uint64_t n = 0;
for (const auto& r : recs) {
const auto t = static_cast<RecordType>(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<std::string> record_bag(const std::vector<Rec>& recs) {
std::multiset<std::string> 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<std::string> 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<Rec>& 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<uint32_t>(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<std::string> 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<std::string> 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<int64_t>(2 * kDay)));
const Outcome h6 = reduce_dir(copies[2], merge_opts(MergeMode::sample, static_cast<int64_t>(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<int64_t>(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<uint64_t> pids; // per node
std::vector<std::string> names; // per node
std::vector<uint64_t> ev_ts; // per event
};
CprFixture build_cpr(const std::string& dir, std::size_t nodes, const std::vector<CprEv>& 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<uint64_t> 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<KeyTs> node_sequence(const std::vector<Rec>& recs, const std::string& node, uint64_t pid) {
std::vector<KeyTs> 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<uint32_t>(RecordType::connect) && rec_pid == pid) {
out.push_back({bytes_field(r.payload, 6), ts});
} else if (r.type == static_cast<uint32_t>(RecordType::process_exec) && bytes_field(r.payload, 10) == node) {
out.push_back({"E", ts});
}
}
return out;
}
std::vector<std::string> collapse_runs(const std::vector<KeyTs>& seq) {
std::vector<std::string> 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<uint64_t> kept_ts;
for (const auto& k : after) kept_ts.insert(k.ts);
std::map<std::string, std::pair<uint64_t, uint64_t>> 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<CprEv> 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<int64_t>(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<int> last(kNodes, -1);
std::vector<CprEv> 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<int>(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<int64_t>(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;
}