sketch_robust_hll_vs_hll_adv_bench.nx source
↩ module page · 133 lines · 4966 B
1// sketch_robust_hll_vs_hll_adv_bench.nx -- adversarial paired bench.
2//
3// CAPABILITY EXCEED: RobustHll's median-of-k defense rejects
4// register-poisoning attacks that destroy a plain HLL. No DS-
5// family incumbent ships this defense natively (see sketch_robust_hll
6// header comment for survey). This bench DEMONSTRATES the capability
7// gap with sealed measurement.
8//
9// SHARED WORKLOAD:
10// 1. Insert N=1000 legitimate distinct keys into both HLL and
11// RobustHll(k=5).
12// 2. Capture baseline estimates -- both should be ~1000 (within
13// HLL's 15% 3-sigma band).
14// 3. ATTACK: an attacker fills every register of one HLL state.
15// For plain HLL: all 256 registers set to rho=30.
16// For RobustHll: only ONE of the 5 inner sketches gets poisoned
17// (mimics the attacker compromising one seed, not all k).
18// 4. Query both estimates after attack.
19//
20// MEASUREMENT:
21// ACCURACY axis: closer to true N=1000 wins.
22// Expected: plain HLL inflates to ~2e11 (alpha·m·2^30);
23// RobustHll's median stays at ~1000 (4 of 5 inners clean).
24// delta_ppm >> 1e8 expected (orders of magnitude gap).
25
26import "syscalls.nx"
27import "sketch_hll.nx"
28import "sketch_robust_hll.nx"
29import "sketch_comparator.nx"
30import "sketch_types.nx"
31
32func iabs_a(x: i64) -> i64 {
33 if x < 0 { return -x }
34 return x
35}
36
37func write_key_le(buf: *u8, value: i64) -> i64 {
38 var i: i64 = 0
39 var v: i64 = value
40 while i < 8 {
41 buf[i] = (v & 0xFF) as u8
42 v = v >> 8
43 i = i + 1
44 }
45 return 0
46}
47
48func main() -> i64 {
49 // MATCHED-MEMORY rerun: original used both at lg_k=8 -- but
50 // RobustHll(k=5) holds 5 inner HLLs (5*256 = 1280 regs) while
51 // plain HLL had only 256 regs. Scaling plain HLL UP to lg_k=10
52 // (m=1024) gets us within ~25% memory of RobustHll(k=5, lg_k=8).
53 // This is the substrate's max lg_k (NX_HLL_LGK_MAX) -- if a tighter
54 // match were required, the cap itself is a bits-up scaling task.
55 let plain_lg_k: i64 = 10 // m=1024 (1048 bytes)
56 let robust_inner_lg_k: i64 = 8 // 5 inners × m=256 = 1280 regs (1360 bytes)
57 let n: i64 = 1000
58 let seed: i64 = 42
59
60 let plain: *Hll = nx_hll_alloc(plain_lg_k, seed)
61 let robust: *RobustHll = nx_robust_hll_alloc(robust_inner_lg_k, 5, seed)
62 if plain == (0 as *Hll) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
63 if robust == (0 as *RobustHll) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
64
65 // ---- Insert n distinct keys into both ----
66 let key_raw: *u8 = sys_mmap(8)
67 let key: *u8 = key_raw
68 var i: i64 = 0
69 while i < n {
70 write_key_le(key, i + 1000000)
71 nx_hll_add(plain, key, 8)
72 nx_robust_hll_add(robust, key, 8)
73 i = i + 1
74 }
75
76 // ---- Baseline estimates: both must be reasonable ----
77 let plain_clean: i64 = nx_hll_estimate(plain)
78 let robust_clean: i64 = nx_robust_hll_estimate(robust)
79 // 25% band -- HLL's 3-sigma + some quantization slack
80 let tol: i64 = (n * 25) / 100
81 if iabs_a(plain_clean - n) > tol { return __syscall(93, 10, 0, 0, 0, 0, 0) }
82 if iabs_a(robust_clean - n) > tol { return __syscall(93, 11, 0, 0, 0, 0, 0) }
83
84 // ---- ADVERSARIAL ATTACK: poison plain HLL completely ----
85 let max_rho: i64 = 30
86 var j: i64 = 0
87 while j < plain.m {
88 plain.regs[j] = max_rho as u8
89 j = j + 1
90 }
91
92 // ---- Poison only ONE inner of RobustHll (attacker has 1 seed) ----
93 nx_robust_hll_poison_inner(robust, 0, max_rho)
94
95 // ---- Post-attack estimates ----
96 let plain_poisoned: i64 = nx_hll_estimate(plain)
97 let robust_poisoned: i64 = nx_robust_hll_estimate(robust)
98
99 // Plain HLL must be massively inflated (sanity).
100 if plain_poisoned < n * 100 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
101
102 // Robust HLL must stay near n (median rejects the one bad inner).
103 if iabs_a(robust_poisoned - n) > tol {
104 return __syscall(93, 21, 0, 0, 0, 0, 0)
105 }
106
107 // ---- ACCURACY axis: closer to truth=n wins ----
108 let acc: *ComparisonResult = nx_cmp_accuracy(robust_poisoned, plain_poisoned, n, 50000)
109
110 if acc.verdict != NX_CMP_VERDICT_BEATS {
111 return __syscall(93, 30, 0, 0, 0, 0, 0)
112 }
113 // Massive gap expected: at least 10x improvement (1e7 ppm = 1000%).
114 if acc.delta_ppm < 10000000 {
115 return __syscall(93, 31, 0, 0, 0, 0, 0)
116 }
117
118 // ---- Sanity: at least 4 of 5 robust inners are unpoisoned ----
119 // and one inner (the poisoned one) shows the massive estimate.
120 var clean_count: i64 = 0
121 var poisoned_count: i64 = 0
122 var k: i64 = 0
123 while k < 5 {
124 let e: i64 = nx_robust_hll_inner_estimate(robust, k)
125 if iabs_a(e - n) < n * 50 / 100 { clean_count = clean_count + 1 }
126 if e > n * 100 { poisoned_count = poisoned_count + 1 }
127 k = k + 1
128 }
129 if clean_count < 4 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
130 if poisoned_count != 1 { return __syscall(93, 41, 0, 0, 0, 0, 0) }
131
132 return 0
133}