strawberry/tests/test_invariants.cpp
trvon 2e94ae1485
Some checks failed
Build and Test / build (debug, clang) (push) Has been cancelled
Build and Test / build (debug, gcc) (push) Has been cancelled
Build and Test / build (release, clang) (push) Has been cancelled
Build and Test / build (release, gcc) (push) Has been cancelled
Build and Test / macos (push) Has been cancelled
Build and Test / docker (push) Has been cancelled
Privacy: tracker list feeds (advisory only, never block)
First piece of tracker attribution (docs/tracker-attribution.md): which
programs reach advertising and tracking domains, built with the
measurement rules of the CarolinaCon 2026 privacy talk (bridgescope):
a listed domain is a circumstantial label, never proof.

- Feed kind "trackers": hosts lines, plain domains and adblock
  whole-domain rules (||host^, ||host^$third-party). Cosmetic rules,
  exceptions, paths and other options are skipped; the comment cut used
  to turn "site.example##.ad" into a domain.
- TrackerSet: suffix matching (a.b.t.example matches t.example, never
  nott.example, an IP literal or a bare TLD); first feed reported.
- List parsing moves from rule_updater.cpp to ioc_list.cpp (no network
  code) so the query-side core can use it.
- Source invariant R11: tracker lists never meet exec-guard or OpenSnitch
  code. They are not in the OpenSnitch blocklist sync.

Tests: T1-T3 (test_tracker_set), trackers in the list-parsing property
and the list fuzzer (60 s clean), R11 self-test fixture.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-28 05:25:53 -06:00

463 lines
22 KiB
C++

// Property (invariant) tests: properties that must hold for every input, checked
// on thousands of seeded random cases per run. A failure prints the seed;
// re-run with STRAWBERRY_PROPERTY_SEED=<seed> to reproduce.
#include "strawberry/exec_guard.hpp"
#include "strawberry/ioc_set.hpp"
#include "strawberry/perf_stats.hpp"
#include "strawberry/platform_process.hpp"
#include "strawberry/policy.hpp"
#include "strawberry/resource_governor.hpp"
#include "strawberry/rule_updater.hpp"
#include "strawberry/scanner_health.hpp"
#include <arpa/inet.h>
#include <unistd.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <limits>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace strawberry;
namespace fs = std::filesystem;
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)
template <typename T>
const T& pick(std::mt19937_64& rng, const std::vector<T>& values) {
return values[std::uniform_int_distribution<std::size_t>(0, values.size() - 1)(rng)];
}
std::string random_bytes(std::mt19937_64& rng, std::size_t max_len) {
static const std::string alphabet =
"abcdefghijklmnopqrstuvwxyzABCDEF0123456789 ./:-_#;\t\n0123456789abcdef\x01\xff{}[]\",=";
std::string out(std::uniform_int_distribution<std::size_t>(0, max_len)(rng), ' ');
for (auto& c : out) {
c = alphabet[std::uniform_int_distribution<std::size_t>(0, alphabet.size() - 1)(rng)];
}
return out;
}
// ---- Exec decisions ---------------------------------------------------------
void property_exec_decisions() {
std::cout << "Property: exec decisions" << std::endl;
std::mt19937_64 rng(kSeed);
const std::vector<std::string> modes{"off", "audit", "enforce", "bogus", ""};
const std::vector<std::string> severities{"", "low", "medium", "high", "critical", "weird"};
for (int i = 0; i < 20000; ++i) {
ExecAssessment a;
a.scanned = rng() % 8 != 0;
a.ioc_match = rng() % 3 == 0;
a.allowlisted = rng() % 3 == 0;
a.quarantined = rng() % 5 == 0;
a.degraded = rng() % 4 == 0;
a.top_severity = pick(rng, severities);
a.top_rule = a.top_severity.empty() ? "" : "Rule";
const auto mode = pick(rng, modes);
const auto min_severity = pick(rng, severities);
const bool protected_path = rng() % 2 == 0;
const auto verdict = decide_exec(mode, min_severity, a, protected_path);
// Unscanned files are always allowed (fail open).
if (!a.scanned) PROPERTY(verdict == ExecVerdict::allow);
// An operator quarantine blocks in every mode, on every path.
if (a.scanned && a.quarantined) PROPERTY(verdict == ExecVerdict::block);
if (!a.quarantined) {
// Without a quarantine nothing is blocked unless enforcing...
if (mode != "enforce") PROPERTY(verdict != ExecVerdict::block);
// ...nor on system paths (alert only)...
if (protected_path) PROPERTY(verdict != ExecVerdict::block);
// ...nor when the allowlist covers it...
if (a.allowlisted) PROPERTY(verdict == ExecVerdict::allow);
// ...and "off" never even alerts.
if (mode == "off") PROPERTY(verdict == ExecVerdict::allow);
}
// Monotone in severity: raising the match never lowers the verdict.
if (a.scanned && !a.quarantined && !a.allowlisted) {
ExecAssessment higher = a;
higher.top_severity = "critical";
PROPERTY(static_cast<int>(decide_exec(mode, min_severity, higher, protected_path))
>= static_cast<int>(verdict));
}
}
std::cout << " PASSED (seed " << kSeed << ")" << std::endl;
}
// ---- Histogram --------------------------------------------------------------
void property_histogram() {
std::cout << "Property: histogram percentiles" << std::endl;
std::mt19937_64 rng(kSeed ^ 0x9e3779b97f4a7c15ULL);
for (int round = 0; round < 200; ++round) {
Histogram h;
std::vector<uint64_t> values(std::uniform_int_distribution<int>(1, 500)(rng));
for (auto& v : values) {
v = rng() % 4 == 0 ? rng() % 10 : rng() >> std::uniform_int_distribution<int>(0, 63)(rng);
h.record(v);
}
const auto s = h.summary();
std::sort(values.begin(), values.end());
PROPERTY(s.count == values.size());
PROPERTY(s.max == values.back());
PROPERTY(s.p50 <= s.p95 && s.p95 <= s.p99 && s.p99 <= s.max);
// Bucket upper bound: never below the true percentile, at most ~2x above.
const auto true_p95 = values[static_cast<std::size_t>(std::ceil(0.95 * values.size())) - 1];
PROPERTY(s.p95 >= true_p95 || s.p95 == s.max);
PROPERTY(true_p95 == 0 || s.p95 <= 2 * true_p95 + 1 || s.p95 == s.max);
}
std::cout << " PASSED" << std::endl;
}
// ---- IOC network set vs a brute-force reference -------------------------------
bool reference_in_net(const std::array<uint8_t, 16>& a, const std::array<uint8_t, 16>& n, int prefix) {
for (int bit = 0; bit < prefix; ++bit) {
const int byte = bit / 8;
const int shift = 7 - bit % 8;
if (((a[byte] >> shift) & 1) != ((n[byte] >> shift) & 1)) {
return false;
}
}
return true;
}
void property_ioc_net_set() {
std::cout << "Property: IOC network set matches brute force" << std::endl;
std::mt19937_64 rng(kSeed ^ 0x1234);
const auto dir = fs::temp_directory_path() / ("sb-prop-" + std::to_string(::getpid()));
fs::create_directories(dir);
for (int round = 0; round < 30; ++round) {
struct RefNet {
std::array<uint8_t, 16> address{};
int prefix;
};
std::vector<RefNet> nets;
std::ofstream list(dir / "nets.txt");
for (int i = 0; i < 40; ++i) {
RefNet net;
for (int b = 0; b < 4; ++b) net.address[b] = static_cast<uint8_t>(rng() % 4); // dense space: overlaps
// Include prefixes the loader must reject (< 8, > 32).
net.prefix = std::uniform_int_distribution<int>(0, 34)(rng);
char text[INET_ADDRSTRLEN];
::inet_ntop(AF_INET, net.address.data(), text, sizeof(text));
list << text << "/" << net.prefix << "\n";
if (net.prefix >= kMinNetPrefixV4 && net.prefix <= 32) {
nets.push_back(net);
}
}
list.close();
IocNetSet set;
set.load({}, {{"feed", (dir / "nets.txt").string()}});
PROPERTY(set.size() == nets.size());
for (int probe = 0; probe < 200; ++probe) {
std::array<uint8_t, 16> address{};
for (int b = 0; b < 4; ++b) address[b] = static_cast<uint8_t>(rng() % 4);
char text[INET_ADDRSTRLEN];
::inet_ntop(AF_INET, address.data(), text, sizeof(text));
const bool expected = std::any_of(nets.begin(), nets.end(),
[&](const RefNet& n) { return reference_in_net(address, n.address, n.prefix); });
PROPERTY(set.find(text).has_value() == expected);
}
}
fs::remove_all(dir);
std::cout << " PASSED" << std::endl;
}
// ---- IOC list parsing ----------------------------------------------------------
void property_ioc_list_parsing() {
std::cout << "Property: IOC list parsing" << std::endl;
std::mt19937_64 rng(kSeed ^ 0xabcdef);
const std::vector<std::string> kinds{"hashes", "domains", "ips", "nets", "trackers"};
const std::vector<std::string> good{
"evil.example", "0.0.0.0 bad.test", "1.2.3.4", "2001:db8::1", "10.0.0.0/8", "1.10.16.0/20 ; SBL1",
std::string(64, 'a'), std::string(64, 'F'), "# comment", "", " spaced.example ", "::ffff:1.2.3.4",
"0.0.0.0/0", "::/0", "999.1.1.1", "a..b", "-bad.example", "1.2.3.4/33",
"||ads.example^", "||t.example^$third-party", "||x.example^$script", "site.example##.ad",
"@@||ok.example^", "||cdn.example/path^", "! adblock comment", "[Adblock Plus 2.0]",
};
for (int i = 0; i < 3000; ++i) {
const auto kind = pick(rng, kinds);
std::string text;
for (int line = std::uniform_int_distribution<int>(0, 30)(rng); line > 0; --line) {
text += (rng() % 3 == 0 ? random_bytes(rng, 40) : pick(rng, good)) + (rng() % 5 == 0 ? "\r\n" : "\n");
}
const std::size_t cap = std::uniform_int_distribution<std::size_t>(0, 50)(rng);
std::vector<std::string> out;
parse_ioc_list(kind, text, cap, out);
PROPERTY(out.size() <= cap);
for (const auto& entry : out) {
// Entries are normalized: non-empty, no whitespace or comment chars.
PROPERTY(!entry.empty());
PROPERTY(entry.find_first_of(" \t\r\n#;") == std::string::npos);
if (kind == "hashes") {
PROPERTY(entry.size() == 64 && entry.find_first_not_of("0123456789abcdef") == std::string::npos);
}
if (kind == "nets") {
const auto slash = entry.find('/');
PROPERTY(slash != std::string::npos);
const int prefix = std::stoi(entry.substr(slash + 1));
const bool v6 = entry.find(':') != std::string::npos;
PROPERTY(prefix >= (v6 ? kMinNetPrefixV6 : kMinNetPrefixV4) && prefix <= (v6 ? 128 : 32));
}
}
// Idempotent: normalized output parses back to itself.
std::string again_text;
for (const auto& entry : out) again_text += entry + "\n";
std::vector<std::string> again;
const auto rejected = parse_ioc_list(kind, again_text, 1u << 20, again);
PROPERTY(rejected == 0);
std::vector<std::string> a = out, b = again;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
b.erase(std::unique(b.begin(), b.end()), b.end());
PROPERTY(a == b);
}
std::cout << " PASSED" << std::endl;
}
// ---- Governor parsers never crash and stay in range ---------------------------
void property_governor_parsers() {
std::cout << "Property: governor parsers on arbitrary text" << std::endl;
std::mt19937_64 rng(kSeed ^ 0x55aa);
const std::vector<std::string> seeds{
"some avg10=1.00 avg60=0 avg300=0 total=1\n", "cpu 1 2 3 4 5 6 7 8\ncpu0 1 2 3 4\n", "MemTotal: 10 kB\nMemAvailable: 5 kB\n",
"1 (x) S 1 1 1 0 -1 0 0 0 0 0 5 6 0", "0::/a/b\n", "max\n", "100000 100000\n", "VmRSS:\t12 kB\n",
};
for (int i = 0; i < 20000; ++i) {
std::string text = pick(rng, seeds);
// Mutate: flip, insert or truncate.
for (int m = std::uniform_int_distribution<int>(0, 4)(rng); m > 0 && !text.empty(); --m) {
const auto pos = std::uniform_int_distribution<std::size_t>(0, text.size() - 1)(rng);
switch (rng() % 3) {
case 0: text[pos] = static_cast<char>(rng() & 0xff); break;
case 1: text.insert(pos, random_bytes(rng, 6)); break;
default: text.resize(pos); break;
}
}
if (const auto v = parse_psi_some_avg10(text)) PROPERTY(*v >= 0 && *v <= 100);
if (const auto v = parse_loadavg_1m(text)) PROPERTY(*v >= 0);
if (const auto m = parse_meminfo(text)) PROPERTY(m->total_bytes > 0);
if (const auto c = parse_proc_stat(text)) PROPERTY(c->online_cpus > 0);
(void) parse_self_stat_cpu(text);
(void) parse_status_rss(text);
if (const auto p = parse_cgroup_v2_path(text)) PROPERTY(p->front() == '/' && p->find("..") == std::string::npos);
if (const auto m = parse_cgroup_memory_max(text)) PROPERTY(*m > 0);
if (const auto c = parse_cgroup_cpu_max(text)) PROPERTY(*c > 0);
}
std::cout << " PASSED" << std::endl;
}
// ---- Governor admission --------------------------------------------------------
void property_governor_admission() {
std::cout << "Property: governor admission" << std::endl;
std::mt19937_64 rng(kSeed ^ 0x77);
for (const auto* name : {"efficient", "balanced", "aggressive"}) {
ResourceSample sample;
auto now = std::chrono::steady_clock::time_point{} + std::chrono::hours(1);
GovernorOptions o;
o.profile = *scan_profile_named(name);
o.max_deferral = std::chrono::seconds(60);
o.sampler = [&sample]() { return sample; };
o.clock = [&now]() { return now; };
o.sleeper = [](std::chrono::milliseconds) {};
ResourceGovernor gov(o);
for (int step = 0; step < 3000; ++step) {
sample.host_source = rng() % 4 == 0 ? "loadavg" : "psi";
sample.cpu_some_pct = std::uniform_real_distribution<double>(-1, 100)(rng);
sample.io_some_pct = std::uniform_real_distribution<double>(-1, 100)(rng);
sample.memory_some_pct = std::uniform_real_distribution<double>(-1, 100)(rng);
sample.load_per_cpu = std::uniform_real_distribution<double>(-1, 8)(rng);
sample.own_cpu_pct = std::uniform_real_distribution<double>(-1, 100)(rng);
sample.rss_bytes = rng() % (2ull << 30);
sample.mem_total_bytes = 16ull << 30;
sample.mem_available_bytes = rng() % (16ull << 30);
sample.cgroup_memory_max = rng() % 5 == 0 ? (rng() % (2ull << 30)) + 1 : 0;
now += std::chrono::milliseconds(std::uniform_int_distribution<int>(0, 2000)(rng));
gov.tick();
// The launch path is never deferred.
PROPERTY(gov.admit(WorkClass::exec_guard) == Admission::admit);
// Live exec scans are only held at emergency.
if (gov.level() < PressureLevel::emergency) PROPERTY(gov.admit(WorkClass::exec_scan) == Admission::admit);
// A calm host and a normal level always admit background work.
if (!gov.host_busy() && gov.level() == PressureLevel::normal) {
PROPERTY(gov.admit(WorkClass::inventory) == Admission::admit);
}
const auto snap = gov.snapshot();
PROPERTY(snap.memory_budget_bytes > 0);
if (sample.cgroup_memory_max > 0) PROPERTY(snap.memory_budget_bytes <= sample.cgroup_memory_max);
// Aggressive never degrades the guard for load (only for size).
if (std::string(name) == "aggressive") PROPERTY(!gov.guard_should_degrade(1));
}
}
std::cout << " PASSED" << std::endl;
}
// ---- Untrusted JSON: policy payloads and status snapshots ----------------------
void property_untrusted_json() {
std::cout << "Property: untrusted JSON never crashes or corrupts policy" << std::endl;
std::mt19937_64 rng(kSeed ^ 0x4242);
const auto dir = fs::temp_directory_path() / ("sb-prop-policy-" + std::to_string(::getpid()));
fs::create_directories(dir);
PolicyStore store((dir / "policy.json").string());
std::string error;
PROPERTY(store.load(&error));
const std::vector<std::string> verbs{"allowlist-add", "allowlist-remove", "feed-add", "feed-remove",
"feed-set-enabled", "protection-set", "nonsense"};
const std::vector<std::string> payloads{
R"({"kind":"sha256","value":"%H"})", R"({"kind":"path","value":"/opt/x/","rule":"R_1"})",
R"({"kind":"rule","value":"%S"})", R"({"id":"%S"})", R"({"id":"x","enabled":true})",
R"({"id":"f1","type":"url","kind":"nets","url":"https://example.com/%S"})",
R"({"prevention_mode":"%S"})", R"({"contain_min_severity":"high"})", R"([1,2,3])", "%S",
R"({"kind":"path","value":"../../etc/shadow"})", R"({"kind":"sha256","value":"%H","extra":1})",
};
for (int i = 0; i < 1500; ++i) {
std::string payload = pick(rng, payloads);
for (std::size_t at; (at = payload.find("%H")) != std::string::npos;) {
std::string h(64, '0');
for (auto& c : h) c = "0123456789abcdef"[rng() % 16];
payload.replace(at, 2, rng() % 4 == 0 ? random_bytes(rng, 70) : h);
}
for (std::size_t at; (at = payload.find("%S")) != std::string::npos;) {
payload.replace(at, 2, random_bytes(rng, 20));
}
if (rng() % 6 == 0 && !payload.empty()) payload.resize(rng() % payload.size());
(void) store.apply(pick(rng, verbs), payload, 1000, &error);
// Whatever was accepted keeps the policy well-formed and re-loadable.
const auto snapshot = store.snapshot();
PROPERTY(snapshot.allowlist.size() <= PolicyStore::kMaxAllowEntries);
PROPERTY(snapshot.feeds.size() <= PolicyStore::kMaxFeeds);
for (const auto& entry : snapshot.allowlist) {
PROPERTY(entry.kind == "sha256" || entry.kind == "path" || entry.kind == "rule");
if (entry.kind == "path") PROPERTY(!entry.value.empty() && entry.value.front() == '/'
&& entry.value.find("..") == std::string::npos);
if (entry.kind == "sha256") PROPERTY(entry.value.size() == 64);
}
const auto mode = snapshot.protection.prevention_mode;
PROPERTY(mode == "off" || mode == "audit" || mode == "enforce");
}
PolicyStore reloaded((dir / "policy.json").string());
PROPERTY(reloaded.load(&error));
fs::remove_all(dir);
for (int i = 0; i < 3000; ++i) {
// Status snapshots come from the daemon but are parsed by user-side
// clients; garbage must yield "unreachable", never a crash.
std::string text = R"({"monitor":{"enabled":true,"events_dropped":%S},"resources":{"deferring":[%S]},"timings":%S})";
for (std::size_t at; (at = text.find("%S")) != std::string::npos;) text.replace(at, 2, random_bytes(rng, 12));
if (rng() % 3 == 0) text = random_bytes(rng, 80);
const auto snapshot = snapshot_from_status_json(text);
(void) scanner_problems(snapshot, 0);
}
for (int i = 0; i < 128; ++i) {
const auto huge = "1e" + std::to_string(40 + rng() % 268);
const auto snapshot = snapshot_from_status_json(
"{\"resources\":{\"deferring\":[\"inventory\"],\"longest_deferral_s\":" + huge +
"},\"timings\":{\"exec_decision\":{\"count\":20,\"p95_ms\":" + huge + "}}}");
const auto problems = scanner_problems(snapshot, 0);
const auto bound = std::to_string(std::numeric_limits<int>::max());
PROPERTY(std::any_of(problems.begin(), problems.end(), [&](const auto& p) {
return p.find(bound + " min") != std::string::npos;
}));
PROPERTY(std::any_of(problems.begin(), problems.end(), [&](const auto& p) {
return p.find(bound + " ms") != std::string::npos;
}));
}
std::cout << " PASSED" << std::endl;
}
} // namespace
// ---- KERN_PROCARGS2 (macOS cmdline) -------------------------------------------
void property_procargs2_cmdline() {
std::cout << "Property: KERN_PROCARGS2 parsing recovers argv and is total on any input:" << std::endl;
std::mt19937_64 rng(kSeed ^ 0x9e3779b97f4a7c15ull);
for (int iteration = 0; iteration < 4000; ++iteration) {
std::vector<std::string> args(std::uniform_int_distribution<std::size_t>(1, 6)(rng));
for (auto& arg : args) {
arg = random_bytes(rng, 24);
}
const int argc = static_cast<int>(args.size());
std::string buffer(sizeof(argc), '\0');
std::memcpy(buffer.data(), &argc, sizeof(argc));
buffer += "/usr/bin/" + random_bytes(rng, 12);
buffer.append(std::uniform_int_distribution<std::size_t>(1, 8)(rng), '\0');
std::string expected;
for (std::size_t i = 0; i < args.size(); ++i) {
buffer += args[i];
buffer.push_back('\0');
expected += (i == 0 ? "" : " ") + args[i];
}
buffer += "PATH=/usr/bin"; // environment follows argv and is ignored
buffer.push_back('\0');
while (!expected.empty() && expected.back() == ' ') {
expected.pop_back();
}
const auto full = platform::procargs2_cmdline(buffer);
// An empty argv[0] is skipped by the padding scan; only check exact
// recovery when argv[0] is non-empty.
if (!args.front().empty()) {
PROPERTY(full == expected);
}
// Truncation (the kernel copies at most ARG_MAX) never invents data.
const auto cut = std::uniform_int_distribution<std::size_t>(0, buffer.size())(rng);
const auto partial = platform::procargs2_cmdline(std::string_view(buffer).substr(0, cut));
PROPERTY(partial.size() <= platform::kMaxCmdlineBytes);
if (!args.front().empty()) {
PROPERTY(full.starts_with(partial) || expected.starts_with(partial));
}
// Arbitrary bytes: bounded, no crash.
const auto junk = platform::procargs2_cmdline(random_bytes(rng, 256));
PROPERTY(junk.size() <= platform::kMaxCmdlineBytes);
}
std::cout << " PASSED (seed " << kSeed << ")" << std::endl;
}
int main() {
std::cout << "Running property tests (seed " << kSeed << ")..." << std::endl << std::endl;
property_exec_decisions();
property_histogram();
property_ioc_net_set();
property_ioc_list_parsing();
property_governor_parsers();
property_governor_admission();
property_untrusted_json();
property_procargs2_cmdline();
std::cout << std::endl << "All properties held." << std::endl;
return 0;
}