From 65e9d86e48e3fd182882ceb54b9b8b1ff475369d Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 16 Nov 2026 22:47:30 +0000 Subject: store: a test per attack row marked unit Each row of `docs/store.md`, Attacks, marked unit has its test, `store_attack_`: where it is judged (`access::holding`, `access::token`), where the store held in memory meets it (`federation::store::memory`), and where a node reads its store from its document (`federation::held`). Tests that checked a row already take its name; a check reads the doc's rows and fails on a unit row without its test, but for rows 21 and 22, which the remakes bring. --- src/access/holding.rs | 106 +++++++++++++++----- src/access/token.rs | 5 +- src/document/events.rs | 16 +++ src/federation/held.rs | 220 ++++++++++++++++++++++++++++++++++++++--- src/federation/store/memory.rs | 54 ++++++++-- 5 files changed, 355 insertions(+), 46 deletions(-) (limited to 'src') diff --git a/src/access/holding.rs b/src/access/holding.rs index 631b36a..3ff3e3e 100644 --- a/src/access/holding.rs +++ b/src/access/holding.rs @@ -184,26 +184,6 @@ mod tests { }], }; assert!(judge(&at, &again, "federation").is_err()); - // At another key, or too large: refused. - let mut doc = swarm(); - assert!( - judged(&mut doc, "node-a", |doc| put( - doc, - &Id::of(b"else").to_string(), - &event - )) - .is_err() - ); - let mut doc = swarm(); - let large = vec![b' '; crate::federation::event::LARGEST + 1]; - assert!( - judged(&mut doc, "node-a", |doc| put( - doc, - &Id::of(&large).to_string(), - &large - )) - .is_err() - ); // A string, not bytes: refused. let mut doc = swarm(); assert!( @@ -214,8 +194,9 @@ mod tests { ); } + /// An event deleted, or replaced: refused. #[test] - fn nothing_deletes_or_replaces_an_event() { + fn store_attack_4() { let root = Id::of(ROOT).to_string(); let mut doc = swarm(); assert!( @@ -228,8 +209,10 @@ mod tests { assert!(judged(&mut doc, "node-a", |doc| put(doc, &root, b"other bytes")).is_err()); } + /// A node writing another node's entry, or under `_continuum` where it may not: + /// refused; its own entry it writes. #[test] - fn a_node_writes_its_own_entry_and_nothing_else() { + fn store_attack_18() { let entry = |node: &str| meta::path(&[meta::MEMBERS, node]); let mut doc = swarm(); assert_eq!( @@ -245,7 +228,7 @@ mod tests { .is_err() ); for closed in [ - vec!["config".to_owned()], + meta::path(&["else"]), meta::path(&[meta::USERS, "alice"]), meta::path(&[meta::SWARM]), meta::path(&[meta::NEIGHBOURS]), @@ -289,4 +272,81 @@ mod tests { .is_err() ); } + + // The store's attack rows (`docs/store.md`, Attacks) judged here. + + /// A change writing outside `_continuum/events` and the protocol data listed: refused. + #[test] + fn store_attack_1() { + let mut doc = swarm(); + assert!( + judged(&mut doc, "node-a", |doc| store::write_path( + doc, + &["config".to_owned()], + &json!(1) + )) + .is_err() + ); + } + + /// An event at a key its bytes don't hash to: refused. + #[test] + fn store_attack_2() { + let mut doc = swarm(); + assert!( + judged(&mut doc, "node-a", |doc| put( + doc, + &Id::of(b"else").to_string(), + b"an event" + )) + .is_err() + ); + } + + /// A change by a node that isn't a member, brought by one that is: taken, as nothing + /// here asks who is a member. + #[test] + fn store_attack_7() { + let event = b"an event".to_vec(); + let mut doc = swarm(); + assert_eq!( + judged(&mut doc, "a-node-no-party-lists", |doc| put( + doc, + &Id::of(&event).to_string(), + &event + )), + Ok(()) + ); + } + + /// A decision or abort written by a node not its coordinator: refused, as a swarm + /// holding a store takes no remake records. + #[test] + fn store_attack_14() { + for part in ["decision", "abortRequested"] { + let mut doc = swarm(); + assert!( + judged(&mut doc, "node-a", |doc| { + store::write_path(doc, &meta::path(&[meta::REMAKES, "r", part]), &json!({})) + }) + .is_err() + ); + } + } + + /// An event larger than the fold allows, put by a change: refused, by the change's own + /// bytes. + #[test] + fn store_attack_32() { + let large = vec![b' '; crate::federation::event::LARGEST + 1]; + let mut doc = swarm(); + assert!( + judged(&mut doc, "node-a", |doc| put( + doc, + &Id::of(&large).to_string(), + &large + )) + .is_err() + ); + } } diff --git a/src/access/token.rs b/src/access/token.rs index 54dd7f8..0b6521a 100644 --- a/src/access/token.rs +++ b/src/access/token.rs @@ -288,10 +288,11 @@ mod tests { serde_json::from_slice(&BASE64URL.decode(payload).unwrap()).unwrap() } - /// In a swarm holding a store, a node takes only the tokens it issued. + /// In a swarm holding a store, a node takes only the tokens it issued (`docs/store.md`, + /// Attacks, 17: a token from another node). #[cfg(feature = "federation")] #[test] - fn a_store_node_takes_its_own_tokens_only() { + fn store_attack_17() { let key = NodeKey::from_seed([1; 32]); let other = NodeKey::from_seed([2; 32]); let mut doc = crate::document::events::started("federation", b"a root").unwrap(); diff --git a/src/document/events.rs b/src/document/events.rs index 5fce55d..ab8675b 100644 --- a/src/document/events.rs +++ b/src/document/events.rs @@ -132,6 +132,22 @@ pub(crate) fn is_genesis(change: &Change, fold: &str, id: &Id) -> bool { root.is_some_and(|root| genesis(fold, &root).hash() == change.hash()) } +/// `events`, each at its ID, put into `doc` by one change. +#[cfg(test)] +pub(crate) fn put(doc: &mut Document, events: &[&[u8]]) { + super::testing::change(doc, |doc| { + for bytes in events { + store::write_val_path( + doc, + &event(&Id::of(bytes)), + &Val::Scalar(ScalarValue::Bytes(bytes.to_vec())), + store::Writing::sticky(TimestampFormat::default()), + ) + .expect("an event written"); + } + }); +} + #[cfg(test)] mod tests { use super::*; diff --git a/src/federation/held.rs b/src/federation/held.rs index f48778d..3c8bafb 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -790,10 +790,10 @@ async fn put_again(state: &crate::state::AppState) { #[cfg(test)] mod tests { use super::*; - use crate::document::typed::{TimestampFormat, Val}; - use crate::document::{Document, ScalarValue}; + use crate::document::Document; use crate::federation::event::Checkpoint; use crate::federation::harness::{self, Party, Spec}; + use crate::federation::store::memory::Refusal; use crate::federation::version::Version; fn root_of(spec: &Spec) -> Vec { @@ -806,15 +806,7 @@ mod tests { } fn put(doc: &mut Document, event: &[u8]) { - crate::document::testing::change(doc, |doc| { - store::write_val_path( - doc, - &events::event(&Id::of(event)), - &Val::Scalar(ScalarValue::Bytes(event.to_vec())), - store::Writing::sticky(TimestampFormat::default()), - ) - .unwrap(); - }); + events::put(doc, &[event]); } fn read(holding: &Holding, doc: &Document, epoch_seq: u32) { @@ -1034,4 +1026,210 @@ mod tests { std::fs::write(&path, b"{\"refused\": [\"not an ID\"]}").unwrap(); assert!(Holding::open(Some(path), files, None, None).is_err()); } + + // The store's attack rows (`docs/store.md`, Attacks) read from a document. + + /// tv's federation, its root, and a document started from it. + fn tv_alone() -> (Party, Vec, Document) { + let tv = Party::new("tv", 1); + let root = root_of(&Spec::first(&[&tv], &[])); + let doc = events::started(Federation::NAME, &root).unwrap(); + (tv, root, doc) + } + + /// An event whose dependencies never come: taken by no node; it stays in the document. + #[test] + fn store_attack_3() { + let (tv, _, mut doc) = tv_alone(); + let on = tv.write(&[Id::of(b"never")], "home/tv/x", harness::str("1")); + put(&mut doc, &on); + let holding = Holding::default(); + read(&holding, &doc, 0); + assert_eq!( + holding.with(|store| store.is_waiting(&Id::of(&on))), + Some(true) + ); + assert!(events::ids(&doc).contains(&Id::of(&on))); + } + + /// The same event put by two changes at once, or again later: one event. + #[test] + fn store_attack_5() { + let (tv, root, mut doc) = tv_alone(); + let write = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); + let mut other = doc.fork(); + put(&mut doc, &write); + put(&mut other, &write); + doc.merge(&mut other).unwrap(); + assert_eq!(events::ids(&doc).len(), 2); + let holding = Holding::default(); + read(&holding, &doc, 0); + read(&holding, &doc.fork(), 1); + assert_eq!( + holding.with(|store| store.taken().to_vec()), + Some(vec![Id::of(&write)]) + ); + } + + /// An event the fold refuses, beside others in one change: the store takes the others, + /// and not that one, nor what is built on it. + #[test] + fn store_attack_6() { + let (tv, root, mut doc) = tv_alone(); + let good = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); + let bad = tv.write(&[Id::of(&root)], "elsewhere/x", harness::str("1")); + let on_bad = tv.write(&[Id::of(&bad)], "home/tv/y", harness::str("1")); + events::put(&mut doc, &[&good, &bad, &on_bad]); + let holding = Holding::default(); + read(&holding, &doc, 0); + assert_eq!( + holding.with(|store| store.taken().to_vec()), + Some(vec![Id::of(&good)]) + ); + assert!(matches!( + holding.with(|store| store.refusal(&Id::of(&on_bad)).cloned()), + Some(Some(Refusal::BuiltOn(_))) + )); + } + + /// Bytes that are none of the fold's events, or a root other than the store's: refused. + #[test] + fn store_attack_8() { + let (_, _, mut doc) = tv_alone(); + let junk = b"{\"not\":\"an event\"}".to_vec(); + let other = root_of(&Spec::first(&[&Party::new("lass", 2)], &[])); + put(&mut doc, &junk); + put(&mut doc, &other); + let holding = Holding::default(); + read(&holding, &doc, 0); + for bytes in [&junk, &other] { + assert_eq!( + holding.with(|store| store.refusal(&Id::of(bytes)).cloned()), + Some(Some(Refusal::None)) + ); + } + assert_eq!(holding.with(|store| store.taken().len()), Some(0)); + } + + /// A node whose operator had it drop an event is sent it again, in another change, + /// before or after a restart: not taken, with everything built on it. + #[test] + fn store_attack_20() { + let (tv, root, mut doc) = tv_alone(); + let write = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); + let on = tv.write(&[Id::of(&write)], "home/tv/x", harness::str("2")); + put(&mut doc, &write); + let dir = crate::files::scratch_dir("held-attack-20"); + let path = dir.join("store.json"); + let files = Arc::new(Files::default()); + let holding = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); + read(&holding, &doc, 0); + holding.drop_taken(&[Id::of(&write)]).unwrap().unwrap(); + // Another document, the event in another change. + let mut again = events::started(Federation::NAME, &root).unwrap(); + events::put(&mut again, &[&write, &on]); + read(&holding, &again, 1); + assert_eq!(holding.with(|store| store.taken().len()), Some(0)); + let restarted = Holding::open(Some(path), files, None, None).unwrap(); + read(&restarted, &again, 0); + assert_eq!(restarted.with(|store| store.taken().len()), Some(0)); + } + + /// An event not above the heads of the checkpoint a node moved to: not taken; it stays + /// in the document. + #[test] + fn store_attack_23() { + let (tv, lass) = (Party::new("tv", 1), Party::new("lass", 2)); + let makefu = Party::new("makefu", 3); + let first = Spec::first(&[&tv, &lass, &makefu], &[]); + let root = root_of(&first); + let on = first.hash(); + let head = tv.write(&[Id::of(&root)], "home/tv/a", harness::str("1")); + let mut next = first.after(on); + next.checkpoint = Some(vec![Id::of(&head)]); + let proposal = tv.propose(&[Id::of(&head)], &next.json()); + let votes = [ + tv.vote(&[Id::of(&proposal)], on, next.hash(), true), + lass.vote(&[Id::of(&proposal)], on, next.hash(), true), + ]; + let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], next.hash()); + let mut doc = events::started(Federation::NAME, &root).unwrap(); + for event in [&head, &proposal] + .into_iter() + .chain(&votes) + .chain([&written]) + { + put(&mut doc, event); + } + let holding = Holding::default(); + read(&holding, &doc, 0); + assert_ne!( + holding.with(|store| Id::of(store.checkpoint())), + Some(Id::of(&root)) + ); + let beside = makefu.write(&[Id::of(&root)], "home/makefu/b", harness::str("1")); + put(&mut doc, &beside); + read(&holding, &doc, 0); + assert_eq!( + holding.with(|store| store.refusal(&Id::of(&beside)).cloned()), + Some(Some(Refusal::NotAbove)) + ); + assert!(events::ids(&doc).contains(&Id::of(&beside))); + } + + /// Rows the next stages test. + const LATER: &[u32] = &[21, 22]; + + #[test] + fn every_row_marked_unit_has_its_test() { + let doc = include_str!("../../docs/store.md"); + let attacks = doc.split("\n## Attacks").nth(1).expect("its attacks"); + let attacks = attacks.split("\n## ").next().unwrap_or(attacks); + let sources = [ + include_str!("held.rs"), + include_str!("store/memory.rs"), + include_str!("../access/holding.rs"), + include_str!("../access/token.rs"), + ]; + let rows: BTreeMap = attacks + .lines() + .filter_map(|line| { + let cells: Vec<&str> = line.split('|').map(str::trim).collect(); + let n = cells.get(1)?.parse().ok()?; + Some((n, cells.get(4)?.to_string())) + }) + .collect(); + let tested: Vec = sources + .iter() + .flat_map(|source| source.lines()) + .filter_map(|line| { + line.trim() + .strip_prefix("fn store_attack_")? + .split('(') + .next()? + .parse() + .ok() + }) + .collect(); + let missing: Vec<&u32> = rows + .iter() + .filter(|(n, kind)| { + kind.starts_with("unit") && !tested.contains(n) && !LATER.contains(n) + }) + .map(|(n, _)| n) + .collect(); + assert!(missing.is_empty(), "rows without their test: {missing:?}"); + for n in &tested { + assert!(rows.contains_key(n), "a test of row {n}, which isn't there"); + assert_eq!( + tested.iter().filter(|m| *m == n).count(), + 1, + "row {n} tested twice" + ); + } + for n in LATER { + assert!(!tested.contains(n), "row {n} has its test now"); + assert!(rows[n].starts_with("unit"), "row {n} isn't marked unit"); + } + } } diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index b8035d7..bc0c672 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -805,6 +805,47 @@ mod tests { assert_eq!(anew.own(), (own, drops)); } + /// Heads for a checkpoint before the store's, or one in another's history: no move + /// (`docs/store.md`, Attacks, 25). + #[test] + fn store_attack_25() { + let (mut store, cut, _, first) = cut_at_a_lock(); + let checkpoint = store.checkpoint().to_vec(); + store.offer(testfold::cut(&[cut], 2, &[first])); + assert_eq!(store.checkpoint(), checkpoint.as_slice()); + let mut store = self::store(); + let root = store.id(); + let one = taken(store.offer(testfold::put(&[root], "a", "1"))); + let two = taken(store.offer(testfold::put(&[one], "a", "2"))); + let checkpoint = store.checkpoint().to_vec(); + store.offer(testfold::cut(&[two], 1, &[one, two])); + assert_eq!(store.checkpoint(), checkpoint.as_slice()); + } + + /// A head brought again after a move: taken as held, and not read anew; so is what + /// came before it (`docs/store.md`, Attacks, 26). + #[test] + fn store_attack_26() { + let (mut store, _, lock, first) = cut_at_a_lock(); + let root = store.id(); + let second = Id::of(&testfold::put(&[first], "a", "2")); + let state = store.state().clone(); + assert_eq!(store.offer(testfold::lock(&[second], "b")), Offered::Held); + assert_eq!(Id::of(&testfold::lock(&[second], "b")), lock); + assert_eq!(store.offer(testfold::put(&[root], "a", "1")), Offered::Held); + assert!(store.state() == &state); + } + + /// An operator has its node drop an event its checkpoint keeps, or one of its heads: + /// refused (`docs/store.md`, Attacks, 27). + #[test] + fn store_attack_27() { + let (mut store, _, lock, first) = cut_at_a_lock(); + let second = Id::of(&testfold::put(&[first], "a", "2")); + assert!(store.drop_taken(&[second]).is_err()); + assert!(store.drop_taken(&[lock]).is_err()); + } + /// Heads leave out what is neither among them, in their history, nor above them. #[test] fn heads_leave_out_what_is_beside_them() { @@ -869,15 +910,6 @@ mod tests { store.offer(testfold::put(&[root], "c", "1")), Offered::Refused(Refusal::NotAbove) ); - // A head brought again is held; so is what came before it. - assert_eq!( - store.offer(testfold::lock( - &[Id::of(&testfold::put(&[first], "a", "2"))], - "b" - )), - Offered::Held - ); - assert_eq!(store.offer(testfold::put(&[root], "a", "1")), Offered::Held); } /// The checkpoint a store builds at heads it holds is the one it moves to there. @@ -932,8 +964,10 @@ mod tests { ); } + /// A fork's events brought to the store it came from, or the other way: never taken + /// (`docs/store.md`, Attacks, 9). #[test] - fn a_fork_and_the_store_it_left_take_nothing_of_each_other() { + fn store_attack_9() { let mut store = store(); let root = store.id(); let here = taken(store.offer(testfold::put(&[root], "a", "1"))); -- cgit v1.3.1