sketch_robust_hll_test.nx source
↩ module page · 95 lines · 3281 B
1// sketch_robust_hll_test.nx -- adversarial-safety smoke for the
2// median-of-k HLL wrapper.
3//
4// Two cases:
5// 1. Honest input: stream N distinct keys, verify median estimate
6// within +-15% of N (same tolerance as basic HLL). Verifies
7// the wrapper doesn't regress accuracy.
8// 2. Adversarial input: stream the same N keys, then explicitly
9// saturate one inner sketch's registers (simulates an attacker
10// who found a hash collision against that seed). Verify the
11// median estimate STILL within 25% of N -- one poisoned sketch
12// out of 5 doesn't move the median.
13// 3. Typed envelope: query returns adv_safety = NX_ADV_ADVERSARIAL
14// (distinguishes from basic HLL which is Honest).
15
16import "syscalls.nx"
17import "sketch_robust_hll.nx"
18import "sketch_types.nx"
19
20func write_i64_le(buf: *u8, value: i64) -> i64 {
21 var i: i64 = 0
22 var v: i64 = value
23 while i < 8 {
24 buf[i] = v & 0xFF
25 v = v >> 8
26 i = i + 1
27 }
28 return 0
29}
30
31func iabs(x: i64) -> i64 {
32 if x < 0 { return -x }
33 return x
34}
35
36func main() -> i64 {
37 // lgK=10 inner sketches, k=5 inner copies -> ~5KB total.
38 let r: *RobustHll = nx_robust_hll_alloc(10, 5, 0)
39 if r == (0 as *RobustHll) {
40 return __syscall(93, 5, 0, 0, 0, 0, 0)
41 }
42
43 let N: i64 = 5000
44
45 let key: *u8 = sys_mmap(8)
46 var i: i64 = 0
47 while i < N {
48 write_i64_le(key, i)
49 nx_robust_hll_add(r, key, 8)
50 i = i + 1
51 }
52
53 // ---- Case 1: honest-input accuracy ----
54 let est_honest: i64 = nx_robust_hll_estimate(r)
55 let lo: i64 = (N * 85) / 100
56 let hi: i64 = (N * 115) / 100
57 if est_honest < lo { return __syscall(93, 10, 0, 0, 0, 0, 0) }
58 if est_honest > hi { return __syscall(93, 11, 0, 0, 0, 0, 0) }
59
60 // ---- Case 2: poison one inner sketch and re-query ----
61 // Set every register of inner sketch index 2 to rho=53 (max for
62 // lg_k=10's 54-bit suffix). This simulates a worst-case
63 // attacker-induced register inflation.
64 nx_robust_hll_poison_inner(r, 2, 53)
65
66 // The poisoned sketch's estimate should be astronomically high
67 // (close to 2^53 ish). Verify it diverged.
68 let poisoned_est: i64 = nx_robust_hll_inner_estimate(r, 2)
69 if poisoned_est < (est_honest * 10) {
70 // Poison didn't take effect, test setup wrong.
71 return __syscall(93, 20, 0, 0, 0, 0, 0)
72 }
73
74 // Median across the other 4 honest sketches + 1 poisoned should
75 // STILL be near N (within 25%).
76 let est_poisoned: i64 = nx_robust_hll_estimate(r)
77 let lo_p: i64 = (N * 75) / 100
78 let hi_p: i64 = (N * 125) / 100
79 if est_poisoned < lo_p { return __syscall(93, 30, 0, 0, 0, 0, 0) }
80 if est_poisoned > hi_p { return __syscall(93, 31, 0, 0, 0, 0, 0) }
81
82 // ---- Case 3: typed envelope is Adversarial ----
83 let q: *ApproxI64 = nx_robust_hll_query(r)
84 if q.adv_safety != NX_ADV_ADVERSARIAL {
85 return __syscall(93, 40, 0, 0, 0, 0, 0)
86 }
87 if q.envelope_kind != NX_ENV_REL_STDDEV {
88 return __syscall(93, 41, 0, 0, 0, 0, 0)
89 }
90 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
91 return __syscall(93, 42, 0, 0, 0, 0, 0)
92 }
93
94 return 0
95}