hopr_protocol_hopr/replay_filter.rs
1//! Replay detection for incoming HOPR packets.
2//!
3//! A packet is replayed when the same wire bytes are delivered twice. Recognising that matters: the alternative is
4//! a header MAC verification, a payload permutation and a message parse for every duplicate an attacker cares to
5//! send.
6//!
7//! The token is the packet's Sphinx authentication tag, derived from the shared secret with the local node. That
8//! secret requires the elliptic-curve Diffie-Hellman, which cannot be avoided - but everything after it can, which
9//! is why the tag is handed to the filter from inside the Sphinx decode rather than after it (see
10//! [`HoprPacket::from_incoming_checked`](hopr_crypto_packet::prelude::HoprPacket::from_incoming_checked)).
11//!
12//! Keying on the derived tag rather than on the wire `alpha` matters because the tag depends on the node's
13//! private key. Anybody can *compute* a tag from a chosen alpha and the node's public key, so the early
14//! [`TagReplayFilter::contains`] check is not a proof of anything; what costs an attacker a well-formed packet is
15//! getting a token *recorded*, which [`TagReplayFilter::commit`] does only after the header MAC has verified.
16//! Rotating the filter out therefore needs packets the sender could actually authenticate, not merely bytes whose
17//! first field the attacker chose.
18//!
19//! # Why a rolling filter rather than one Bloom filter that resets
20//!
21//! A Bloom filter is sized for a fixed number of items and cannot grow. The previous implementation answered
22//! overflow by clearing the entire bitmap, which forgets *every* packet at once. It cleared once per capacity: the
23//! insertion that found the filter full of other tags reset it, so the history of all peers was dropped on a
24//! single packet.
25//!
26//! Instead, each shard keeps two generations. When the current one fills it becomes the previous one and a fresh
27//! current is allocated, so a token is remembered for at least one full generation *of its shard* - a floor that no
28//! insertion pattern can take away, where the old design had none. The floor is per shard rather than global: a
29//! token's shard is chosen by a keyed hash and ages out with that shard alone, so the configured count is a bound on
30//! total retention only when traffic spreads evenly across shards (see [`ReplayFilterConfig::max_tracked_packets`]).
31//!
32//! Aging out is proportional to insert volume (a packet count, not wall time). The cost of shortening the window is
33//! *authenticated* packets, not paid ones: a token is committed once the header MAC verifies, which still precedes
34//! ticket validation, so a direct neighbour can rotate generations with packets it does not pay for. Each must
35//! still authenticate under the shared secret, which costs it the same elliptic-curve work a legitimate sender
36//! pays, and the window it shortens is bounded below by one full generation.
37//!
38//! The shard a token lands in is chosen by a hash keyed per filter instance, so a sender - who computes the tag -
39//! cannot aim its packets at one shard and evict only that shard's history.
40//!
41//! # Why sharded
42//!
43//! The filter is consulted by every concurrent decode task. A single mutex serialized them on one cache line;
44//! sharding by token hash divides that contention by the shard count without changing the semantics, because the
45//! filter is a set either way.
46//!
47//! The namespace is deliberately global rather than per previous hop: the token names the packet, not the sender,
48//! so a replay injected through a different peer ID is still caught. The cost is that one high-volume peer
49//! advances rotations for everyone; that residual is bounded by the generation floor rather than eliminated.
50
51use hopr_api::types::crypto_random::random_bytes;
52
53/// The token a replay filter is keyed on: the packet's Sphinx authentication tag.
54///
55/// The tag is derived from the shared secret with the local node, so only a party that can derive that secret can
56/// produce one - an attacker cannot insert arbitrary tokens to age the filter out without paying the same
57/// elliptic-curve work per packet that a legitimate sender does.
58pub type ReplayToken = hopr_api::types::crypto::types::PacketTag;
59
60/// Configuration of the [`TagReplayFilter`].
61///
62/// The two fields are validated together: `shards` must be a power of two in range, `max_tracked_packets` must be
63/// at least [`MIN_TRACKED_PACKETS`], and the capacity must leave every shard at least [`MIN_CAPACITY_PER_SHARD`]
64/// slots, i.e. `max_tracked_packets >= shards * MIN_CAPACITY_PER_SHARD`. That last condition is what the field-wise
65/// ranges cannot express on their own - the floor capacity together with the shard ceiling satisfies both of them
66/// yet leaves a shard with a single slot, which rotates on every distinct token.
67#[derive(Clone, Copy, Debug, PartialEq, Eq, smart_default::SmartDefault, validator::Validate)]
68#[cfg_attr(
69 feature = "serde",
70 derive(serde::Serialize, serde::Deserialize),
71 serde(deny_unknown_fields)
72)]
73#[validate(schema(function = "validate_capacity_per_shard"))]
74pub struct ReplayFilterConfig {
75 /// Number of tokens the filter remembers per generation, across all shards.
76 ///
77 /// This is the capacity of one generation, split evenly across the shards, and retention is **per shard**: a
78 /// token stays known until its shard has taken `max_tracked_packets / shards` further distinct tokens, twice
79 /// over (once to retire it, once more to drop the retired generation). So a token survives roughly this many
80 /// *total* inserts only if traffic spreads evenly across shards - which a keyed shard hash makes the expected
81 /// case, but it is not a hard global bound. Must leave every shard at least [`MIN_CAPACITY_PER_SHARD`] slots,
82 /// i.e. be at least `shards * MIN_CAPACITY_PER_SHARD` (and at least [`MIN_TRACKED_PACKETS`]).
83 ///
84 /// At the default false-positive rate the bitmap costs roughly three bytes per token per generation, so a
85 /// decoder ultimately holds about this many megabytes, twice over once a shard has rotated. Generations are
86 /// allocated on first insertion, so the footprint grows with traffic rather than being paid at construction;
87 /// at the default it reaches a little under 32 MB per decoder, rising to about 63 MB after every shard has
88 /// rotated once.
89 ///
90 /// Default is 10 000 000.
91 #[default(default_max_tracked_packets())]
92 // Concrete numbers in the message: `validator` takes a literal, so the constants cannot be interpolated here.
93 // The test `the_tracked_packet_floor_agrees_with_the_validator` keeps them in step.
94 #[validate(
95 range(
96 min = MIN_TRACKED_PACKETS,
97 max = MAX_TRACKED_PACKETS,
98 message = "max_tracked_packets must be between 4096 and 100000000"
99 )
100 )]
101 #[cfg_attr(feature = "serde", serde(default = "default_max_tracked_packets"))]
102 pub max_tracked_packets: usize,
103 /// Number of independent shards.
104 ///
105 /// Each shard has its own generation state and lock, so this divides both the memory high-water mark and the
106 /// lock contention. It must be a power of two, which the validator enforces so that shard selection is a mask
107 /// rather than a division.
108 ///
109 /// Default is 64.
110 #[default(default_shards())]
111 #[validate(custom(function = "validate_shards"))]
112 #[cfg_attr(feature = "serde", serde(default = "default_shards"))]
113 pub shards: usize,
114}
115
116/// Lower bound on the number of tokens a single shard holds per generation, enforced by the validator.
117///
118/// The check and the insertion are two separate lock acquisitions with the whole decode between them, so a token
119/// committed by one decode can be lost to a second one only if the shard rotates *twice* in that window - that is,
120/// if two full generations are inserted into one shard while a single packet is being decoded. One slot per shard
121/// would make that two packets; this floor keeps the window at the same order as the default configuration's.
122pub const MIN_CAPACITY_PER_SHARD: usize = 64;
123/// Lower bound on [`ReplayFilterConfig::max_tracked_packets`], enforced by the validator.
124///
125/// Sized so that the default shard count gets [`MIN_CAPACITY_PER_SHARD`] slots each.
126pub const MIN_TRACKED_PACKETS: usize = MIN_CAPACITY_PER_SHARD * DEFAULT_SHARDS;
127/// Lower bound on [`ReplayFilterConfig::shards`], enforced by the validator.
128pub const MIN_SHARDS: usize = 1;
129/// Upper bound on [`ReplayFilterConfig::shards`], enforced by the validator.
130pub const MAX_SHARDS: usize = 4096;
131/// Upper bound on [`ReplayFilterConfig::max_tracked_packets`], enforced by the validator.
132///
133/// The bound exists because generations are allocated lazily: without it, a typo in the capacity would surface as a
134/// failed allocation inside the decode path on the first packet for a shard, rather than as a rejected
135/// configuration at startup. One hundred million tokens is about 320 MB per generation at the default rate, which
136/// is the point past which a node's own memory, not its traffic, is the constraint.
137pub const MAX_TRACKED_PACKETS: usize = 100_000_000;
138/// Default for [`ReplayFilterConfig::shards`].
139const DEFAULT_SHARDS: usize = 64;
140/// Default for [`ReplayFilterConfig::max_tracked_packets`].
141const DEFAULT_MAX_TRACKED_PACKETS: usize = 10_000_000;
142/// False-positive rate of a single generation.
143///
144/// [`TagReplayFilter::contains`] consults two generations, so the rate a caller observes is the union of the two.
145/// Halving the per-generation rate keeps that union at the 1e-5 the single-filter design used; because the bitmap
146/// size grows with `ln(1/p)`, halving `p` costs only a few percent per generation. Holding two generations is what
147/// doubles the total: a decoder now allocates roughly twice the bitmap it did, against a retention floor that is no
148/// longer zero.
149const GENERATION_FALSE_POSITIVE_RATE: f64 = 0.000_005;
150
151/// Keyed hash over `token`, used to pick a shard.
152///
153/// `SipHasher13` with an explicit key, not `std::hash::DefaultHasher`: the latter's keys are fixed, so a sender who
154/// computes the tag could predict the shard exactly as well as with no hash at all.
155fn keyed_hash(key: &[u8; 16], token: &ReplayToken) -> u64 {
156 use std::hash::Hasher as _;
157 let mut hasher = siphasher::sip::SipHasher13::new_with_key(key);
158 hasher.write(token);
159 hasher.finish()
160}
161
162/// `serde`/`SmartDefault` default for [`ReplayFilterConfig::max_tracked_packets`].
163fn default_max_tracked_packets() -> usize {
164 DEFAULT_MAX_TRACKED_PACKETS
165}
166
167/// `serde`/`SmartDefault` default for [`ReplayFilterConfig::shards`].
168fn default_shards() -> usize {
169 DEFAULT_SHARDS
170}
171
172/// Rejects a configuration whose capacity does not give every shard [`MIN_CAPACITY_PER_SHARD`] slots.
173///
174/// The field-wise ranges cannot express this: `max_tracked_packets` has a floor and `shards` has a ceiling, but
175/// nothing stops the ceiling from exceeding the floor divided by the shard count. [`TagReplayFilter::new`] would
176/// otherwise have to clamp, silently remembering fewer tokens than the configuration asked for.
177///
178/// The per-shard floor is more than "at least one": a shard with a single slot rotates on every distinct token, and
179/// since the check and the commit are separate lock acquisitions, two rotations during one decode would let the
180/// same packet through twice. See [`MIN_CAPACITY_PER_SHARD`].
181fn validate_capacity_per_shard(cfg: &ReplayFilterConfig) -> Result<(), validator::ValidationError> {
182 if cfg.shards == 0 {
183 return Ok(());
184 }
185
186 let per_shard = cfg.max_tracked_packets / cfg.shards;
187 if per_shard < MIN_CAPACITY_PER_SHARD {
188 let required = cfg.shards * MIN_CAPACITY_PER_SHARD;
189 let mut err = validator::ValidationError::new("max_tracked_packets");
190 err.message = Some(
191 format!(
192 "max_tracked_packets must be at least {required} for {} shards ({} per shard), got {}",
193 cfg.shards, MIN_CAPACITY_PER_SHARD, cfg.max_tracked_packets
194 )
195 .into(),
196 );
197 return Err(err);
198 }
199 Ok(())
200}
201
202/// Rejects a shard count that is out of range or not a power of two.
203///
204/// Power of two so [`TagReplayFilter::shard_for`] can mask rather than divide, and so every shard stays addressable.
205fn validate_shards(shards: usize) -> Result<(), validator::ValidationError> {
206 if !(MIN_SHARDS..=MAX_SHARDS).contains(&shards) || !shards.is_power_of_two() {
207 let mut err = validator::ValidationError::new("shards");
208 err.message = Some(format!("shards must be a power of two between {MIN_SHARDS} and {MAX_SHARDS}").into());
209 return Err(err);
210 }
211 Ok(())
212}
213
214#[cfg(all(feature = "telemetry", not(test)))]
215lazy_static::lazy_static! {
216 /// Counts shard rotations, i.e. how often a generation of replay history was dropped.
217 ///
218 /// Initialised lazily on first use; a sustained rate here means the replay window is shrinking faster than the
219 /// configured capacity suggests it should.
220 static ref METRIC_REPLAY_FILTER_ROTATIONS: hopr_api::types::telemetry::SimpleCounter =
221 hopr_api::types::telemetry::SimpleCounter::new(
222 "hopr_replay_filter_rotations_total",
223 "Replay filter generations dropped because their shard filled; each rotation shortens the window in which a packet is still recognised as a replay",
224 )
225 .unwrap();
226}
227
228/// One generation pair of a shard.
229#[derive(Debug)]
230struct ReplayShard {
231 /// The generation currently accepting insertions.
232 ///
233 /// Allocated on the first insertion, not when the filter is built: at the default configuration a generation
234 /// is tens of megabytes, and a node that has not yet received a packet should not have paid for every shard of
235 /// it - nor should every `HoprDecoder` construction in a test or a bench.
236 current: Option<bloomfilter::Bloom<ReplayToken>>,
237 /// The generation that was current until the last rotation, if any.
238 ///
239 /// Allocated lazily too: a shard that never fills its first generation never pays for a second bitmap.
240 previous: Option<bloomfilter::Bloom<ReplayToken>>,
241 /// Number of tokens inserted into [`Self::current`].
242 count: usize,
243 /// Number of tokens a single generation holds before the shard rotates.
244 capacity: usize,
245}
246
247impl ReplayShard {
248 /// Creates an empty shard that will hold `capacity` tokens per generation.
249 fn new(capacity: usize) -> Self {
250 Self {
251 current: None,
252 previous: None,
253 count: 0,
254 capacity,
255 }
256 }
257
258 /// Allocates one generation sized for `capacity` tokens.
259 fn generation(capacity: usize) -> bloomfilter::Bloom<ReplayToken> {
260 bloomfilter::Bloom::new_for_fp_rate_with_seed(capacity, GENERATION_FALSE_POSITIVE_RATE, &random_bytes())
261 .expect("bloom filter with the specified capacity is constructible")
262 }
263
264 /// Whether either generation holds `token`.
265 fn contains(&self, token: &ReplayToken) -> bool {
266 self.current.as_ref().is_some_and(|current| current.check(token))
267 || self.previous.as_ref().is_some_and(|previous| previous.check(token))
268 }
269
270 /// Inserts `token` unless it is already known. Returns `true` if it was already known.
271 fn check_and_set(&mut self, token: &ReplayToken) -> bool {
272 // Both generations are consulted *before* any rotation. Checking them after would mis-handle the exact
273 // case where it matters most: a duplicate that is the token which filled the generation is in the
274 // outgoing `current`, which the rotation is about to move into `previous` - so a check made before the
275 // rotation would miss it and re-admit it into the fresh generation as a brand-new packet.
276 if self.contains(token) {
277 return true;
278 }
279
280 if self.count == self.capacity {
281 // The current generation is full. The oldest one goes, the current one becomes the previous one, and
282 // the token is recorded in a fresh generation.
283 //
284 // A rotation is normal in this design, so it is `debug`: at the default capacity a busy node rotates
285 // every few tens of seconds, and warning on each would be noise. The counter is the signal an operator
286 // alerts on; this line is for chasing a single rotation, and it is logged while the shard is locked.
287 tracing::debug!(
288 capacity = self.capacity,
289 "replay filter shard rotated; its oldest generation was dropped"
290 );
291 #[cfg(all(feature = "telemetry", not(test)))]
292 METRIC_REPLAY_FILTER_ROTATIONS.increment();
293 self.previous = Some(std::mem::replace(
294 self.current.get_or_insert_with(|| Self::generation(self.capacity)),
295 Self::generation(self.capacity),
296 ));
297 self.count = 0;
298 }
299
300 self.current
301 .get_or_insert_with(|| Self::generation(self.capacity))
302 .set(token);
303 self.count += 1;
304 false
305 }
306}
307
308/// Replay-detecting filter over packet replay tokens.
309///
310/// Each of the shards keeps two generations of a Bloom filter. When the current one fills it becomes the previous
311/// one and a fresh current is allocated, so a token is remembered for at least one full generation of its shard -
312/// the floor the previous single-filter design did not have, since it answered overflow by clearing every tag at
313/// once. See [`ReplayFilterConfig::max_tracked_packets`] for what that means for the configured total.
314///
315/// Sharding by token divides both the lock contention of the decode path and the memory high-water mark. The
316/// namespace is global rather than per previous hop: the token names the packet, not the sender, so a replay
317/// injected through a different peer ID is still caught.
318#[derive(Debug)]
319pub struct TagReplayFilter {
320 /// Shards, each independently locked. The count is a power of two, so selection is a mask.
321 shards: Box<[parking_lot::Mutex<ReplayShard>]>,
322 /// Key for shard selection, derived per filter instance.
323 ///
324 /// The tag is computed by the packet's creator, so indexing shards on its raw bytes would let a sender aim
325 /// every packet at one shard - 1/64 of the traffic would evict that shard's history. Hashing with a
326 /// per-instance key makes the shard unpredictable until a token has been seen, which restores the spread.
327 shard_key: [u8; 16],
328}
329
330impl TagReplayFilter {
331 /// Creates a filter holding `cfg.max_tracked_packets` tokens per generation, split evenly across `cfg.shards`.
332 ///
333 /// A validated configuration gives every shard at least [`MIN_CAPACITY_PER_SHARD`] slots, and the total is then
334 /// `capacity / shards * shards`, i.e. within `shards - 1` of the configured value. Only an unvalidated
335 /// configuration can land here with a smaller share, which the `.max(1)` below keeps from producing a
336 /// zero-sized Bloom filter.
337 pub fn new(cfg: &ReplayFilterConfig) -> Self {
338 // Clamped first, because an unvalidated `shards` - `new` is public and `HoprDecoder::new` does not
339 // validate - could otherwise overflow `next_power_of_two` (panic in debug, zero in release) or try to
340 // allocate an unbounded number of shards.
341 //
342 // Then rounded up to a power of two: `shard_for`'s mask addresses only the first `2^k` shards, so an odd
343 // count would silently waste the rest of the configured capacity.
344 let shards = cfg.shards.clamp(MIN_SHARDS, MAX_SHARDS).next_power_of_two();
345 // A validated configuration is already in range; an unvalidated one - `new` is public and the decoder does
346 // not validate - is clamped here rather than left to fail allocating a generation inside the decode path.
347 let capacity_per_shard = (cfg.max_tracked_packets.min(MAX_TRACKED_PACKETS) / shards).max(1);
348
349 Self {
350 shards: (0..shards)
351 .map(|_| parking_lot::Mutex::new(ReplayShard::new(capacity_per_shard)))
352 .collect(),
353 shard_key: random_bytes(),
354 }
355 .with_metrics_registered()
356 }
357
358 /// Registers this type's telemetry at construction, so the series exists before the first rotation.
359 ///
360 /// Registering lazily on first use would leave `hopr_replay_filter_rotations_total` absent until a rotation
361 /// happened - and `rate()`/`increase()` do not count the first increment of a series that did not exist before
362 /// it - and would run the registration, and its `unwrap`, inside the decode path while a shard is locked.
363 fn with_metrics_registered(self) -> Self {
364 #[cfg(all(feature = "telemetry", not(test)))]
365 lazy_static::initialize(&METRIC_REPLAY_FILTER_ROTATIONS);
366 self
367 }
368
369 /// Number of shards, for tests and telemetry.
370 pub fn shards(&self) -> usize {
371 self.shards.len()
372 }
373
374 /// Total number of tokens the filter remembers per generation.
375 pub fn capacity(&self) -> usize {
376 self.shards.iter().map(|shard| shard.lock().capacity).sum()
377 }
378
379 /// Number of tokens inserted into the current generations, summed across shards, for tests and telemetry.
380 pub fn count(&self) -> usize {
381 self.shards.iter().map(|shard| shard.lock().count).sum()
382 }
383
384 /// Returns `true` if `token` is known to the filter. False positives are possible, false negatives are not
385 /// until the token's generation rotates out.
386 ///
387 /// A hit here means "seen before" up to the filter's false-positive rate; a miss means "new" without exception.
388 /// The value is only meaningful once a header MAC has verified it - a tag is computable by anyone from the
389 /// node's public key, so an *unrecorded* tag proves nothing.
390 pub fn contains(&self, token: &ReplayToken) -> bool {
391 self.shard_for(token).lock().contains(token)
392 }
393
394 /// Records `token` and returns whether it was already known.
395 ///
396 /// A `true` return means the token was inserted by a concurrent decode of the same packet between the
397 /// [`Self::contains`] check and this call, so the caller holds the duplicate.
398 pub fn commit(&self, token: &ReplayToken) -> bool {
399 self.shard_for(token).lock().check_and_set(token)
400 }
401
402 /// The shard `token` is assigned to, under the instance's keyed hash.
403 fn shard_for(&self, token: &ReplayToken) -> &parking_lot::Mutex<ReplayShard> {
404 // Keyed hash, so the sender - who computes the tag - cannot choose the shard. The mask is enough because
405 // the shard count is a power of two.
406 let index = keyed_hash(&self.shard_key, token) as usize & (self.shards.len() - 1);
407 &self.shards[index]
408 }
409}
410
411impl Default for TagReplayFilter {
412 /// A filter at the default configuration.
413 fn default() -> Self {
414 Self::new(&ReplayFilterConfig::default())
415 }
416}
417
418#[cfg(test)]
419mod tests {
420 use std::collections::HashSet;
421
422 use anyhow::Context;
423
424 use super::*;
425
426 /// Builds a config from the two raw fields.
427 fn config(max_tracked_packets: usize, shards: usize) -> ReplayFilterConfig {
428 ReplayFilterConfig {
429 max_tracked_packets,
430 shards,
431 }
432 }
433
434 /// Commits exactly `inserts` distinct fresh tokens into a single-shard filter, skipping Bloom false positives.
435 ///
436 /// A false positive makes `commit` report a fresh token as known, which would leave the generation short of
437 /// full and silently skip the rotation a test depends on. Skipping such tokens keeps the arithmetic exact.
438 /// Returns the token of the final successful insert.
439 fn commit_exactly(filter: &TagReplayFilter, inserts: usize) -> ReplayToken {
440 let mut candidate = 0u64;
441 let mut inserted = 0;
442 let mut last = token(0);
443
444 while inserted < inserts {
445 let t = token(candidate);
446 candidate += 1;
447 if filter.commit(&t) {
448 continue; // false positive: already "known", so it did not take a slot
449 }
450 last = t;
451 inserted += 1;
452 }
453
454 last
455 }
456
457 /// A deterministic synthetic token whose bytes vary with `value`.
458 fn token(value: u64) -> ReplayToken {
459 // Spread the counter across the token so that shard selection and the Bloom hashes both see variety.
460 let mut token: ReplayToken = hopr_api::types::crypto::types::PacketTag::default();
461 for (i, byte) in token.iter_mut().enumerate() {
462 *byte = ((value >> (i % 8 * 8)) as u8).wrapping_add((i as u8).wrapping_mul(31));
463 }
464 token
465 }
466
467 #[test]
468 fn a_committed_token_is_then_known() {
469 let filter = TagReplayFilter::new(&config(1024, 4));
470 let t = token(1);
471
472 assert!(!filter.contains(&t));
473 assert!(!filter.commit(&t), "first commit must see a new token");
474 assert!(filter.contains(&t));
475 assert!(filter.commit(&t), "second commit must see the token");
476 assert_eq!(1, filter.count(), "a duplicate must not be counted twice");
477 }
478
479 /// The property the old clear-on-overflow design lacked: after a shard rotates, a token from the generation
480 /// just retired is still known.
481 #[test]
482 fn a_token_survives_exactly_one_rotation() {
483 // A single shard, so every token lands in it and the generations turn over deterministically.
484 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
485 let capacity = filter.capacity();
486
487 let target = token(0);
488 assert!(!filter.commit(&target), "the target is fresh");
489
490 // Fill the generation, which rotates it once. Counting successful inserts keeps a Bloom false positive
491 // from leaving the generation short and skipping the rotation.
492 commit_exactly(&filter, capacity);
493 assert!(filter.contains(&target), "the retired generation still remembers it");
494
495 // Fill again, which rotates the retired generation out.
496 commit_exactly(&filter, capacity);
497 assert!(
498 !filter.contains(&target),
499 "after two rotations the token may age out; the floor is one generation"
500 );
501 }
502
503 #[test]
504 fn rotation_does_not_lose_the_newest_tokens() {
505 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
506
507 // Two generations' worth, so at least one rotation happens mid-run.
508 let mut recent = Vec::new();
509 for i in 0..(2 * filter.capacity() as u64) {
510 let t = token(i);
511 if filter.commit(&t) {
512 continue; // a false positive; it did not take a slot, so it does not count as recent
513 }
514 recent.push(t);
515 if recent.len() > 100 {
516 recent.remove(0);
517 }
518 }
519 assert!(!recent.is_empty(), "the run must have inserted tokens");
520
521 for t in recent {
522 assert!(
523 filter.contains(&t),
524 "the current generation must remember its own inserts"
525 );
526 }
527 }
528
529 #[test]
530 fn commit_is_a_single_winner_under_concurrency() {
531 let filter = std::sync::Arc::new(TagReplayFilter::new(&config(1024, 4)));
532 let t = token(7);
533
534 let winners = std::sync::Arc::new(std::sync::atomic::AtomicUsize::new(0));
535 std::thread::scope(|scope| {
536 for _ in 0..16 {
537 let filter = filter.clone();
538 let winners = winners.clone();
539 scope.spawn(move || {
540 if !filter.commit(&t) {
541 winners.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
542 }
543 });
544 }
545 });
546
547 assert_eq!(
548 1,
549 winners.load(std::sync::atomic::Ordering::SeqCst),
550 "exactly one commit may see a fresh token"
551 );
552 }
553
554 /// The token that fills a generation must be reported by the next `commit`, not re-admitted.
555 ///
556 /// It sits in the outgoing `current` at that moment, so a check made only against `previous` - or made after
557 /// the rotation using a stale view - misses it, rotates it into the retired generation, and inserts it into the
558 /// fresh one as a new packet. That is the boundary at which two concurrent decodes of one packet could both
559 /// succeed with a single rotation.
560 #[test]
561 fn a_token_that_filled_the_generation_must_not_be_readmitted() {
562 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
563 let filling = commit_exactly(&filter, filter.capacity());
564 assert_eq!(filter.capacity(), filter.count(), "the generation is exactly full");
565
566 assert!(
567 filter.commit(&filling),
568 "the token that filled the generation must be reported, not re-admitted"
569 );
570 assert_eq!(
571 filter.capacity(),
572 filter.count(),
573 "a duplicate must neither rotate the shard nor add to it"
574 );
575 }
576
577 /// A token that lives only in the retired generation must still be reported by `commit`, not just by
578 /// `contains`. The decoder calls `commit` directly, so this is the path a duplicate takes there.
579 #[test]
580 fn commit_should_report_a_token_from_the_retired_generation() {
581 // One shard, so every token lands in it and the rotation is deterministic.
582 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
583 let ours = token(0);
584 filter.commit(&ours);
585
586 // Fill the generation so that `ours` is retired into `previous`.
587 commit_exactly(&filter, filter.capacity());
588 assert!(filter.contains(&ours), "the retired generation still knows it");
589
590 assert!(
591 filter.commit(&ours),
592 "commit must report a token only the retired generation knows"
593 );
594 assert_eq!(
595 filter.count(),
596 1,
597 "a commit that found the token in the retired generation must not also insert it"
598 );
599 }
600
601 /// `count` reports the current generations only: it is reset by a rotation and never includes the retired one.
602 #[test]
603 fn count_should_track_the_current_generation_only() {
604 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
605 assert_eq!(0, filter.count(), "a new filter has inserted nothing");
606
607 let capacity = filter.capacity();
608 commit_exactly(&filter, capacity);
609 assert_eq!(capacity, filter.count(), "a full generation is counted");
610
611 // One more distinct token rotates the shard and starts a fresh generation.
612 filter.commit(&token(u64::MAX));
613 assert_eq!(1, filter.count(), "the count restarts with the new generation");
614 assert_eq!(capacity, filter.capacity(), "capacity is unaffected by rotation");
615 }
616
617 #[test]
618 fn shard_selection_spreads_tokens() {
619 let filter = TagReplayFilter::new(&config(1024, 64));
620 let mut used = HashSet::new();
621 for i in 0..10_000u64 {
622 used.insert(filter.shard_for(&token(i)) as *const _ as usize);
623 }
624 assert!(used.len() > 32, "tokens must reach most shards, saw {}", used.len());
625 }
626
627 /// A shard count that is not a power of two is rounded up rather than leaving part of the filter unaddressed,
628 /// since `TagReplayFilter::new` is public and the decoder does not validate its configuration.
629 #[test]
630 fn an_odd_shard_count_should_still_use_the_whole_filter() {
631 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 3));
632 assert_eq!(4, filter.shards(), "3 shards must round up to 4");
633
634 let mut used = HashSet::new();
635 for i in 0..10_000u64 {
636 used.insert(filter.shard_for(&token(i)) as *const _ as usize);
637 }
638 assert_eq!(4, used.len(), "every shard must be addressable, saw {}", used.len());
639 }
640
641 /// The bounds and their message are spelled out as literals in the `range` validator, because `validator`
642 /// cannot interpolate constants. This keeps the exported constants, the enforced bounds and the numbers an
643 /// operator reads in the error message from drifting apart.
644 #[test]
645 fn the_tracked_packet_bounds_agree_with_the_validator() -> anyhow::Result<()> {
646 let mut cfg = config(MIN_TRACKED_PACKETS, 64);
647 validator::Validate::validate(&cfg).context("the floor itself must be accepted")?;
648
649 cfg.max_tracked_packets = MIN_TRACKED_PACKETS - 1;
650 let err = validator::Validate::validate(&cfg)
651 .err()
652 .context("one below the exported floor must be rejected")?;
653 let message = format!("{}", err.field_errors()["max_tracked_packets"][0]);
654 assert!(
655 message.contains(&MIN_TRACKED_PACKETS.to_string()),
656 "the message must state the real lower bound, got: {message}"
657 );
658
659 cfg.max_tracked_packets = MAX_TRACKED_PACKETS + 1;
660 let err = validator::Validate::validate(&cfg)
661 .err()
662 .context("one above the exported ceiling must be rejected")?;
663 let message = format!("{}", err.field_errors()["max_tracked_packets"][0]);
664 assert!(
665 message.contains(&MAX_TRACKED_PACKETS.to_string()),
666 "the message must state the real upper bound, got: {message}"
667 );
668 Ok(())
669 }
670
671 /// The field-wise ranges accept the floor capacity together with the shard ceiling, yet that leaves far fewer
672 /// slots per shard than [`MIN_CAPACITY_PER_SHARD`]. The config-level check is what rejects it - and it must not
673 /// reject a configuration whose capacity merely does not divide evenly.
674 #[test]
675 fn a_configuration_with_too_little_capacity_per_shard_must_be_rejected() {
676 assert!(
677 validator::Validate::validate(&config(MIN_TRACKED_PACKETS, MAX_SHARDS)).is_err(),
678 "the floor capacity split across the shard ceiling leaves too few slots per shard"
679 );
680 assert!(
681 validator::Validate::validate(&config(MIN_CAPACITY_PER_SHARD * 63, 64)).is_err(),
682 "one below the per-shard floor must be rejected"
683 );
684 assert!(
685 validator::Validate::validate(&config(MIN_CAPACITY_PER_SHARD * 64, 64)).is_ok(),
686 "exactly the per-shard floor must be accepted"
687 );
688 assert!(
689 validator::Validate::validate(&config(MIN_CAPACITY_PER_SHARD * 64 + 1, 64)).is_ok(),
690 "an uneven split must still be accepted"
691 );
692 }
693
694 /// Every accepted configuration gives each shard the per-shard floor, so the filter's capacity is the configured
695 /// value up to the shard count, and never larger than it.
696 #[test]
697 fn an_accepted_configuration_never_widens_the_capacity() -> anyhow::Result<()> {
698 for (packets, shards) in [
699 (MIN_TRACKED_PACKETS, 64),
700 (MIN_TRACKED_PACKETS + 1, 64),
701 (MIN_CAPACITY_PER_SHARD * MAX_SHARDS, MAX_SHARDS),
702 ] {
703 let cfg = config(packets, shards);
704 validator::Validate::validate(&cfg).context("must be a valid configuration")?;
705 let filter = TagReplayFilter::new(&cfg);
706 assert_eq!(
707 packets / shards * shards,
708 filter.capacity(),
709 "unexpected capacity for {cfg:?}"
710 );
711 }
712 Ok(())
713 }
714
715 #[test]
716 fn shard_count_must_be_a_power_of_two() -> anyhow::Result<()> {
717 // The capacity is generous in both cases, so only the shard rule can decide.
718 let err = validator::Validate::validate(&config(65_536, 3))
719 .err()
720 .context("3 shards must be rejected")?;
721 assert!(err.field_errors().contains_key("shards"));
722 validator::Validate::validate(&config(65_536, 64)).context("64 shards must be accepted")?;
723 Ok(())
724 }
725
726 #[test]
727 fn capacity_is_shared_evenly_across_shards() {
728 let filter = TagReplayFilter::new(&config(1024, 64));
729 assert_eq!(1024, filter.capacity());
730 assert_eq!(64, filter.shards());
731 }
732
733 /// A token this filter accepts must be reported as a replay the next time it is offered, however much traffic
734 /// has passed through in between.
735 ///
736 /// This is the property a per-peer insertion allowance broke: past its allowance a peer's packets were accepted
737 /// without being recorded, so the same packet was accepted again. Exercised through the whole filter rather than
738 /// a single shard, over several rotations.
739 #[test]
740 fn a_token_accepted_now_must_be_a_replay_later() {
741 let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 4));
742
743 // Far more than a generation's worth, so several rotations happen before the token of interest.
744 for i in 0..(3 * filter.capacity() as u64) {
745 filter.commit(&token(i));
746 }
747
748 let recent = token(3 * filter.capacity() as u64 + 1);
749 assert!(!filter.commit(&recent), "the token is fresh");
750 assert!(
751 filter.commit(&recent),
752 "a token that was just accepted must be reported as a replay when repeated"
753 );
754 }
755
756 /// An unvalidated `shards` must not overflow or allocate unboundedly: `new` is public and the decoder does not
757 /// validate its configuration.
758 #[test]
759 fn an_unvalidated_shard_count_is_clamped() {
760 assert_eq!(
761 MAX_SHARDS,
762 TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, usize::MAX)).shards(),
763 "an oversized shard count must clamp to the ceiling, not overflow"
764 );
765 assert_eq!(
766 MIN_SHARDS,
767 TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 0)).shards(),
768 "a zero shard count must clamp to the floor"
769 );
770 }
771
772 #[test]
773 fn a_new_filter_knows_nothing() {
774 let filter = TagReplayFilter::default();
775 assert_eq!(0, filter.count());
776 assert!(!filter.contains(&token(0)));
777 }
778}