diff options
| author | tv <tv@krebsco.de> | 2026-11-17 04:54:24 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-17 05:58:28 +0100 |
| commit | d55f7c258eb76a4169014dd5ae7ed3465305002b (patch) | |
| tree | 1a560b7950225806abe5d660882591f2f106cdee | |
| parent | b501bbe41976769c7ea2f1976e26cd8ccb778515 (diff) | |
simtest: the remake rows of a swarm holding a store
Simulations of the store's attack rows on remakes (`docs/store.md`,
Attacks): a snapshot other than its base's isn't followed (11); one
coordinator's two decisions for an epoch, shown to different nodes, end on
the lower epoch (13); a node away while the others switch rejoins and puts
again what it wrote meanwhile (16); after a compaction whose snapshot holds
a checkpoint, a node away all along follows only once its operator pins it
(24); a compaction whose base comes before a checkpoint, switched after
nodes moved to it, leaves them there, and a node starting with nothing
reads the new document to it (28); a member deciding many compactions at
once moves every node to the lowest epoch, losing no event (30).
| -rw-r--r-- | src/federation/held.rs | 2 | ||||
| -rw-r--r-- | src/simtest/holding.rs | 401 |
2 files changed, 397 insertions, 6 deletions
diff --git a/src/federation/held.rs b/src/federation/held.rs index 2eac8b2..744e959 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -1788,7 +1788,7 @@ mod tests { } /// Rows whose tests wait: remakes (stage 5), and flooding. - const LATER: &[u32] = &[11, 13, 15, 16, 22, 28, 29, 30, 31]; + const LATER: &[u32] = &[15, 22, 29, 31]; #[test] fn every_row_has_its_test() { diff --git a/src/simtest/holding.rs b/src/simtest/holding.rs index 187488e..4a60129 100644 --- a/src/simtest/holding.rs +++ b/src/simtest/holding.rs @@ -433,13 +433,15 @@ fn checkpoint_at( /// A node away while the others moved to a checkpoint and forgot what came before: c, /// back, builds the checkpoint from the document, which holds what came before, and -/// reads what a and b read, what came after it too. +/// reads what a and b read, what came after it too. Then a compaction, whose snapshot +/// holds that checkpoint: d, away all along, can't build it from its document and +/// doesn't follow the new epoch; started again with it pinned, it does. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] async fn store_attack_24() { let sim = Sim::with_identity(83); let parties = three(); let (tv, lass, makefu) = &parties; - let (first, root, id) = federation(&[(tv, &["a"]), (lass, &["b"]), (makefu, &["c"])]); + let (first, root, id) = federation(&[(tv, &["a"]), (lass, &["b"]), (makefu, &["c", "d"])]); let nodes = started( &sim, &root, @@ -447,10 +449,12 @@ async fn store_attack_24() { ("a", holding("tv")), ("b", holding("lass")), ("c", holding("makefu")), + ("d", holding("makefu")), ], ) .await; sim.net.take_down("c"); + sim.net.take_down("d"); let gone = tv.write(&[id], "home/tv/a", s("0")); let head = tv.write(&[Id::of(&gone)], "home/tv/a", s("1")); let (next, [proposal, tv_yes, lass_yes]) = checkpoint_at(&parties, &first, &[Id::of(&head)]); @@ -490,6 +494,45 @@ async fn store_attack_24() { .await; assert_eq!(counts(&nodes[2]), counts(&nodes[0])); assert!(events::ids(&nodes[2].doc.read().await.doc).contains(&Id::of(&gone))); + + compact(&nodes[0]).await; + on_generation(&sim, &nodes[..3], 1, Duration::from_secs(60)).await; + { + let replica = nodes[0].doc.read().await; + let held = events::checkpoint(&replica.doc).map(|checkpoint| Id::of(&checkpoint)); + assert_eq!(held, Some(moved)); + assert!(!events::ids(&replica.doc).contains(&Id::of(&gone))); + } + sim.net.bring_up("d"); + let d = &nodes[3]; + sim.wait_until( + "d doesn't follow an epoch whose checkpoint it can't build", + Duration::from_secs(60), + move || async move { + d.remake + .catch_up() + .and_then(|catch_up| catch_up.error) + .is_some_and(|error| error.contains("not followed")) + }, + ) + .await; + assert_eq!(d.local_epoch().generation, 0); + let d = sim.restart_with("d", &["a"], Start::Join, move |config| { + of_the_store(config, id, None, pinned("makefu", moved)) + }); + let d = &d; + sim.wait_until( + "d, pinning the checkpoint, follows the new epoch", + Duration::from_secs(60), + move || async move { + d.local_epoch().generation == 1 + && d.is_ready().await + && checkpoint(d) == Some(moved) + && holds(d, &[after]) + }, + ) + .await; + assert_eq!(counts(d), counts(&nodes[0])); } /// Keys voting twice part honest nodes: tv backs a proposal of its own with lass, and one @@ -942,13 +985,59 @@ async fn on_generation(sim: &Sim, nodes: &[AppState], generation: u64, timeout: /// The compaction `node` proposes: its ID. async fn compact(node: &AppState) -> String { - let (status, report) = - crate::remake::testing::start(node.clone(), serde_json::json!({ "kind": "compact" }), None) - .await; + compact_with(node, serde_json::json!({ "kind": "compact" })).await +} + +/// The compaction `node` proposes by `request`: its ID. +async fn compact_with(node: &AppState, request: serde_json::Value) -> String { + let (status, report) = crate::remake::testing::start(node.clone(), request, None).await; assert!(status.is_success(), "proposal refused: {status} {report}"); report["id"].as_str().expect("a remake's ID").to_owned() } +/// Whether `node` holds the remake `id` committed. +async fn committed(node: &AppState, id: &str) -> bool { + crate::remake::testing::report(node, id) + .await + .is_some_and(|report| report["phase"] == "committed") +} + +/// Every node of `nodes` on one epoch of generation 1, ready, holding every event of +/// `ids`, within `timeout`. +async fn together(sim: &Sim, nodes: &[AppState], ids: &[Id], timeout: Duration) { + sim.wait_until( + "every node is ready on one epoch, holding every event", + timeout, + move || async move { + let epoch = nodes[0].local_epoch(); + for node in nodes { + if node.local_epoch() != epoch + || epoch.generation != 1 + || !node.is_ready().await + || !holds(node, ids) + { + return false; + } + } + true + }, + ) + .await; +} + +/// The links from `from` to `to`, cut or whole. +fn cut(sim: &Sim, from: &str, to: &str, cut: bool) { + let params = if cut { + LinkParams { + loss: 1.0, + ..LinkParams::default() + } + } else { + LinkParams::default() + }; + sim.net.set_link(from, to, params); +} + /// Events written beyond a base, on nodes that switch and on nodes that don't yet: put /// again in the new epoch, the same events, the same state; and no change refused. #[tokio::test(flavor = "multi_thread", worker_threads = 4)] @@ -1014,3 +1103,305 @@ async fn store_attack_12() { assert_eq!(refused, 0, "a change refused"); } } + +/// A node away while the others switch: c, back, rejoins the new epoch, reads what is +/// above its checkpoint, and puts again what the new document lacks, its own write while +/// away among it. +#[tokio::test(flavor = "multi_thread", worker_threads = 4)] +async fn store_attack_16() { + let sim = Sim::with_identity(92); + let (tv, lass, makefu) = three(); + let (_, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); + let nodes = started( + &sim, + &root, + vec![ + ("a", holding("tv")), + ("b", holding("lass")), + ("c", holding("makefu")), + ], + ) + .await; + sim.net.take_down("c"); + let before = tv.write(&[id], "home/tv/before", s("1")); + put(&nodes[0], &[&before]).await; + compact(&nodes[0]).await; + on_generation(&sim, &nodes[..2], 1, Duration::from_secs(60)).await; + let away = makefu.write(&[id], "home/makefu/away", s("2")); + put(&nodes[2], &[&away]).await; + let after = tv.write(&[Id::of(&before)], "home/tv/after", s("3")); + put(&nodes[0], &[&after]).await; + + sim.net.bring_up("c"); + let every = [&before, &away, &after].map(|event| Id::of(event)); + together(&sim, &nodes, &every, Duration::from_secs(60)).await; + let read: Vec<Option<Counts>> = nodes.iter().map(counts).collect(); + assert!(read.iter().all(|counts| counts == &read[0]), "{read:?}"); +} + +/// A compaction whose base comes before a checkpoint, switched after nodes moved to it: +/// they switch, keep their checkpoint, read none of what it forgot, and put again from +/// the old document what a store starting at the snapshot's checkpoint takes to reach +/// theirs: c, started again with nothing, reads the new document to it. +#[tokio::test(flavor = "multi_thread", worker_threads = 4)] +async fn store_attack_28() { + let sim = Sim::with_identity(93); + let parties = three(); + let (tv, lass, makefu) = &parties; + let (first, root, id) = federation(&[(tv, &["a"]), (lass, &["b"]), (makefu, &["c"])]); + let nodes = started( + &sim, + &root, + vec![ + ("a", holding("tv")), + ("b", holding("lass")), + ("c", holding("makefu")), + ], + ) + .await; + let all = &nodes; + let gone = tv.write(&[id], "home/tv/a", s("0")); + let head = tv.write(&[Id::of(&gone)], "home/tv/a", s("1")); + put(&nodes[0], &[&gone, &head]).await; + let held = [Id::of(&head)]; + sim.wait_until("every node holds tv's writes", LONG, move || async move { + all.iter().all(|node| holds(node, &held)) + }) + .await; + let remake = compact_with( + &nodes[0], + serde_json::json!({ "kind": "compact", "switchDelay": "20s" }), + ) + .await; + let remake = remake.as_str(); + sim.wait_until("every node holds it committed", LONG, move || async move { + for node in all { + if !committed(node, remake).await { + return false; + } + } + true + }) + .await; + // After its base, before the switch: a checkpoint passes. + let (next, [proposal, tv_yes, lass_yes]) = checkpoint_at(&parties, &first, &[Id::of(&head)]); + put(&nodes[0], &[&proposal, &tv_yes]).await; + put(&nodes[1], &[&lass_yes]).await; + let passed = next.hash(); + sim.wait_until( + "every node moved to the checkpoint", + LONG, + move || async move { + all.iter() + .all(|node| current(node) == Some(passed) && checkpoint(node) != Some(id)) + }, + ) + .await; + let moved = checkpoint(&nodes[0]).expect("a store"); + let after = tv.write(&[Id::of(&head)], "home/tv/b", s("2")); + put(&nodes[0], &[&after]).await; + + let every = [Id::of(&head), Id::of(&after)]; + together(&sim, &nodes, &every, Duration::from_secs(60)).await; + for node in &nodes { + assert_eq!(checkpoint(node), Some(moved)); + assert_eq!(read(node, |store| store.holds(&Id::of(&gone))), Some(false)); + } + let after = Id::of(&after); + let c = sim.restart_with("c", &["a"], Start::Join, move |config| { + of_the_store(config, id, None, holding("makefu")) + }); + let c = &c; + sim.wait_until( + "c, started again with nothing, reads the new document to the checkpoint", + Duration::from_secs(60), + move || async move { + c.local_epoch().generation == 1 && checkpoint(c) == Some(moved) && holds(c, &[after]) + }, + ) + .await; + assert_eq!(counts(c), counts(&nodes[0])); +} + +/// A snapshot holding other than its base's: a coordinator commits its compaction to an +/// epoch no node builds. Not followed: each builds its own and checks it against the +/// epoch, and every node stays where it is, taking what is written on. +#[tokio::test(flavor = "multi_thread", worker_threads = 4)] +async fn store_attack_11() { + let sim = Sim::with_identity(94); + let (tv, lass, makefu) = three(); + let (_, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); + let nodes = started( + &sim, + &root, + vec![ + ("a", holding("tv")), + ("b", holding("lass")), + ("c", holding("makefu")), + ], + ) + .await; + let all = &nodes; + // a hears no ack: it commits only as it likes. + cut(&sim, "b", "a", true); + cut(&sim, "c", "a", true); + let remake = compact(&nodes[0]).await; + let remake = remake.as_str(); + let made_up = crate::document::replica::Epoch { + generation: 1, + id: [7; 32], + }; + crate::remake::testing::commit_as(&nodes[0], remake, Some(made_up)).await; + cut(&sim, "b", "a", false); + cut(&sim, "c", "a", false); + sim.wait_until( + "every node tried the switch and failed", + Duration::from_secs(60), + move || async move { + all.iter().all(|node| { + node.remake + .status(remake) + .is_some_and(|status| status.error.is_some()) + }) + }, + ) + .await; + let later = lass.write(&[id], "home/lass/later", s("1")); + put(&nodes[1], &[&later]).await; + let held = [Id::of(&later)]; + sim.wait_until( + "every node takes what is written on", + LONG, + move || async move { all.iter().all(|node| holds(node, &held)) }, + ) + .await; + for node in &nodes { + assert_eq!(node.local_epoch().generation, 0); + } +} + +/// A coordinator shows one of two decisions for an epoch to some nodes, the other to the +/// rest: b, apart, switches to the one, a and c to the other, or the lower of both. Once +/// together, the nodes on the higher epoch rejoin the lower: no operator needed, and no +/// event lost. +#[tokio::test(flavor = "multi_thread", worker_threads = 4)] +async fn store_attack_13() { + let sim = Sim::with_identity(95); + let (tv, lass, makefu) = three(); + let (_, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); + let nodes = started( + &sim, + &root, + vec![ + ("a", holding("tv")), + ("b", holding("lass")), + ("c", holding("makefu")), + ], + ) + .await; + let all = &nodes; + let before = tv.write(&[id], "home/tv/before", s("1")); + put(&nodes[0], &[&before]).await; + let held = [Id::of(&before)]; + sim.wait_until("every node holds tv's write", LONG, move || async move { + all.iter().all(|node| holds(node, &held)) + }) + .await; + // a hears no ack, and c nothing: a commits only as it likes, to b first. + cut(&sim, "b", "a", true); + cut(&sim, "c", "a", true); + sim.net.take_down("c"); + let one = compact_with( + &nodes[0], + serde_json::json!({ "kind": "compact", "switchDelay": "20s" }), + ) + .await; + let two = crate::remake::testing::propose_again(&nodes[0], &one).await; + let first = crate::remake::testing::commit_as(&nodes[0], &one, None).await; + let one = one.as_str(); + let b = &nodes[1]; + sim.wait_until("b holds the one committed", LONG, move || async move { + committed(b, one).await + }) + .await; + sim.net.take_down("b"); + sim.net.bring_up("c"); + let second = crate::remake::testing::commit_as(&nodes[0], &two, None).await; + assert_ne!(first, second); + cut(&sim, "b", "a", false); + cut(&sim, "c", "a", false); + sim.wait_until( + "b switched to the one", + Duration::from_secs(60), + move || async move { b.local_epoch() == first }, + ) + .await; + sim.wait_until( + "a and c switched", + Duration::from_secs(60), + move || async move { + all[0].local_epoch().generation == 1 && all[2].local_epoch().generation == 1 + }, + ) + .await; + sim.net.bring_up("b"); + let during = makefu.write(&[id], "home/makefu/during", s("2")); + put(&nodes[2], &[&during]).await; + let every = [Id::of(&before), Id::of(&during)]; + together(&sim, &nodes, &every, Duration::from_secs(90)).await; + let lowest = if first.id < second.id { first } else { second }; + assert_eq!(nodes[0].local_epoch(), lowest); +} + +/// A member decides compactions, each its own, at once, to grind an epoch's ID lower +/// than another's: every node follows the lowest, putting again what the new document +/// lacks; no event is lost: slow, not wrong. +#[tokio::test(flavor = "multi_thread", worker_threads = 4)] +async fn store_attack_30() { + let sim = Sim::with_identity(96); + let (tv, lass, makefu) = three(); + let (_, root, id) = federation(&[(&tv, &["a"]), (&lass, &["b"]), (&makefu, &["c"])]); + let nodes = started( + &sim, + &root, + vec![ + ("a", holding("tv")), + ("b", holding("lass")), + ("c", holding("makefu")), + ], + ) + .await; + let all = &nodes; + let before = tv.write(&[id], "home/tv/before", s("1")); + put(&nodes[0], &[&before]).await; + let held = [Id::of(&before)]; + sim.wait_until("every node holds tv's write", LONG, move || async move { + all.iter().all(|node| holds(node, &held)) + }) + .await; + cut(&sim, "b", "a", true); + cut(&sim, "c", "a", true); + let first = compact_with( + &nodes[0], + serde_json::json!({ "kind": "compact", "switchDelay": "20s" }), + ) + .await; + let mut epochs = Vec::new(); + for _ in 0..4 { + let again = crate::remake::testing::propose_again(&nodes[0], &first).await; + epochs.push(crate::remake::testing::commit_as(&nodes[0], &again, None).await); + } + epochs.push(crate::remake::testing::commit_as(&nodes[0], &first, None).await); + cut(&sim, "b", "a", false); + cut(&sim, "c", "a", false); + let during = lass.write(&[id], "home/lass/during", s("2")); + put(&nodes[1], &[&during]).await; + let lowest = epochs + .iter() + .copied() + .min_by_key(|epoch| epoch.id) + .expect("epochs"); + let every = [Id::of(&before), Id::of(&during)]; + together(&sim, &nodes, &every, Duration::from_secs(90)).await; + assert_eq!(nodes[0].local_epoch(), lowest); +} |
