diff options
| author | tv <tv@krebsco.de> | 2026-11-19 12:46:42 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-19 13:52:29 +0100 |
| commit | 03105d40322dff9c18f0571872ab0f643aded0f7 (patch) | |
| tree | a96b625f4d57d23ee12a6db72780446530b413cd | |
| parent | e8f0760a9b08e6b1a7372e79c48744035d1e4e1a (diff) | |
federation: checked against the release a federation-<F>.<R> tag namesfederation-1.1
A corpus of generated histories, committed, said what this code made of them, right or
not, and held hundreds of kilobytes a revision; generated from code that changes, it
could only be checked, never written again.
Each release that makes a revision is tagged `federation-<F>.<R>`, the federation's
number and the revision's (`federation-1.1`, revision 1 of federation 1).
`scripts/federation-check` writes histories from this tree (`write_histories`, an ignored
test): of each revision it knows and each kind the properties generate, those of a few
seeds from a random one it says, and the attack tests' crafted ones, as each test offered
them where nothing but offers made them. It judges them with `continuum-party judge` here
and with the continuum the latest such tag names (or one given), built in a worktree and
kept between runs, leaves out those whose root the tagged one reads as none, and says
where the two differ. Run before a release, not by `cargo quick`.
The corpus and its test are gone; the test plan and `federation.md` say how a release is
checked.
| -rw-r--r-- | docs/federation-tests.md | 38 | ||||
| -rw-r--r-- | docs/federation.md | 11 | ||||
| -rwxr-xr-x | scripts/federation-check | 78 | ||||
| -rw-r--r-- | src/federation/corpus.rs | 315 | ||||
| -rw-r--r-- | src/federation/judge.rs | 60 | ||||
| -rw-r--r-- | src/federation/mod.rs | 2 |
6 files changed, 167 insertions, 337 deletions
diff --git a/docs/federation-tests.md b/docs/federation-tests.md index c22f300..eeb90b6 100644 --- a/docs/federation-tests.md +++ b/docs/federation-tests.md @@ -124,22 +124,26 @@ and a key set `ssh-keygen` signed with it. A vector that changes is a change to every node must agree on ([`federation.md`](federation.md), [Changing the federation](federation.md#changing-the-federation)). -## The corpus +## Against released revisions -What each revision takes, refuses and reads, as fixed bytes: for each revision this -continuum knows, a file in `src/federation/corpus/` of histories generated at that -revision (of every kind the properties generate, those of the first two seeds, and of the -next few hundred those showing what the ones kept don't: of each kind of event, what -became of one, a version written, a move, a stop; eight at most), each event's bytes with -what became of it, by kind (taken, refused and why, by kind, waiting, held back, gone with -a move), and what the store reads after. Together they show a version written, a move to -a checkpoint, a stop, and a merge event taken where the revision has merge events, else -refused. A revision's file is written once, as the -revision is made (`write_the_corpus`, run by hand), and never edited after: every later -continuum judges it alike (`every_revision_judges_as_its_corpus_says`), so that a change -to judging that alters an earlier revision's comes as a later revision. Its first line -names the revision by its ID: a feature renamed fails as a judgment changed does. It holds -only what its histories exercise. +A release judges every history under the revisions an earlier release knows as that one +did, the earlier one's continuum built and asked. Each release that makes a revision is +tagged `federation-<F>.<R>`, the federation's number and the revision's +(`federation-1.1`, revision 1 of federation 1); `scripts/federation-check` judges the same +histories with the continuum the latest such tag names (or one given) and with the tree it +runs in, and says where they differ. The histories: of each revision this tree knows and +each kind the properties generate, those of a few seeds (`write_histories`, from a random +seed it says, `CONTINUUM_TEST_SEED` to rerun them), and the attack tests' crafted ones, as +each test offered them where nothing but offers made them (`attacks::recording`); those +whose root the tagged continuum reads as none, of a revision after it, it leaves out. Both +judge with `continuum-party judge`, whose format no release changes (`federation::judge`): +what became of each event, by kind and never by a refusal's words, and what the store +reads after. + +So a change to judging that alters what an earlier revision does comes as a later +revision, and the check, run before a release, says so where one doesn't. It needs the +tags and a build of the tagged commit, kept between runs; a tree without git's history +can't run it, nor a release before `judge`. ## Fuzzing and mutants @@ -154,8 +158,10 @@ only what its histories exercise. * `cargo quick`: the rules and attacks by example, the properties at small sizes and a few hundred seeds, the store on Automerge by crafted changes and seeded runs, the - vectors, the corpus, and the check that every row has its test. + vectors, and the check that every row has its test. * `cargo sim`: the simulations. +* Before a release: `scripts/federation-check`, against the latest `federation-<F>.<R>` + tag ([Against released revisions](#against-released-revisions)). * Longer runs, by hand or on a schedule: the properties and the store on Automerge with many more seeds (a count from the environment), fuzzing, mutants. diff --git a/docs/federation.md b/docs/federation.md index 30bff6e..8dc23b3 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -881,10 +881,13 @@ version names: a change there splits the swarm until every node runs it A version leaves `revision` out for the base revision, and names a revision no earlier than that of the version it changes. What a revision adds counts at a history only where the version current there names that revision or a later one: before, every node judges -as before, so that what a party uses early, every node refuses alike. A version is read by -the revision it names, so one moving to a revision may already hold what that revision -adds to a version; its proposal, the votes on it and its version event are judged under -the version before. A node voting by itself backs no version changing the revision +as before, so that what a party uses early, every node refuses alike. A release making a +revision is tagged `federation-<F>.<R>`, and every later one is checked to judge as it +does under the revisions it knows ([`federation-tests.md`](federation-tests.md), +[Against released revisions](federation-tests.md#against-released-revisions)). A version +is read by the revision it names, so one moving to a revision may already hold what that +revision adds to a version; its proposal, the votes on it and its version event are judged +under the version before. A node voting by itself backs no version changing the revision ([Votes a node casts by itself](#votes-a-node-casts-by-itself)): its party's operators vote on it. diff --git a/scripts/federation-check b/scripts/federation-check new file mode 100755 index 0000000..e31e002 --- /dev/null +++ b/scripts/federation-check @@ -0,0 +1,78 @@ +#!/bin/sh +# Judges the same histories with continuum as a federation tag names it and with this +# tree, and says where they differ (docs/federation-tests.md: Against released +# revisions). Each release that makes a revision of the federation is tagged +# federation-<F>.<R>, the federation's number and the revision's (federation-1.1 for +# revision 1 of federation 1); a later one judges every history under the revisions that +# release knows as it did. Run before a release, from a checkout with its tags. +# +# scripts/federation-check [TAG] +# +# TAG is the latest federation-<F>.<R> unless given. The histories: of each +# revision and kind, generated from CONTINUUM_TEST_SEED on (a random one, said, unless +# given), CONTINUUM_TEST_CASES times as many as `write_histories` writes; and those the +# attack tests offer. CONTINUUM_FEATURES are the features both are built with, a +# transport among them (federation,mycelium unless given); the tag's build is kept in +# CONTINUUM_CHECK_TARGET (~/.cache/continuum/federation-check unless given) for the +# next run. + +set -eu + +cd "$(git rev-parse --show-toplevel)" + +tag=${1:-$(git tag --list 'federation-[0-9]*.[0-9]*' --sort=-version:refname | head -n 1)} +if [ -z "$tag" ]; then + echo "federation-check: no federation-<F>.<R> tag to check against" >&2 + exit 2 +fi +features=${CONTINUUM_FEATURES:-federation,mycelium} +seed=${CONTINUUM_TEST_SEED:-$(od -An -N4 -tu4 /dev/urandom | tr -d ' ')} +cache=${XDG_CACHE_HOME:-$HOME/.cache} +target=${CONTINUUM_CHECK_TARGET:-$cache/continuum/federation-check} + +work=$(mktemp -d) +clean() { + git worktree remove --force "$work/tagged" >/dev/null 2>&1 || true + rm -rf "$work" +} +trap clean EXIT +trap 'exit 130' INT TERM + +echo "federation-check: $tag against this tree, histories from seed $seed" >&2 +echo "federation-check: CONTINUUM_TEST_SEED=$seed reruns them" >&2 + +CONTINUUM_HISTORIES="$work/histories" CONTINUUM_TEST_SEED=$seed \ + cargo test -q --features "$features" --lib write_histories -- --ignored >&2 +cargo run -q --features "$features" --bin continuum-party -- judge \ + <"$work/histories" >"$work/here" + +git worktree add -q --detach "$work/tagged" "$tag" +(cd "$work/tagged" && CARGO_TARGET_DIR=$target \ + cargo run -q --features "$features" --bin continuum-party -- judge) \ + <"$work/histories" >"$work/there" + +# Histories whose root the tag's continuum reads as none, of a revision after it, it +# doesn't judge: left out on both sides. +awk '/^case /{label=substr($0, 6)} $0 == "root none"{print label}' "$work/there" \ + >"$work/unread" +keep() { + awk -v unread="$work/unread" ' + BEGIN { while ((getline line < unread) > 0) skip[line] = 1 } + /^case / { label = substr($0, 6) } + !(label in skip) + ' "$1" +} +keep "$work/there" >"$work/there.kept" +keep "$work/here" >"$work/here.kept" + +judged=$(grep -c '^case ' "$work/there.kept" || true) +left=$(wc -l <"$work/unread" | tr -d ' ') +if diff -u --label "$tag" --label "this tree" "$work/there.kept" "$work/here.kept" \ + >"$work/differ"; then + echo "federation-check: $judged histories judged alike" \ + "($left of revisions after $tag left out)" +else + head -n 200 "$work/differ" + echo "federation-check: this tree judges otherwise than $tag (seed $seed): above" >&2 + exit 1 +fi diff --git a/src/federation/corpus.rs b/src/federation/corpus.rs deleted file mode 100644 index f19e2b1..0000000 --- a/src/federation/corpus.rs +++ /dev/null @@ -1,315 +0,0 @@ -//! What each revision of federation 1 takes, refuses and reads, as fixed bytes -//! (`docs/federation-tests.md`, The corpus): for each revision this continuum knows, a file -//! in `corpus/` of histories generated at that revision, each with what became of every -//! event and what the store reads after, written once when the revision is made -//! (`write_the_corpus`) and never edited after. Every later continuum judges them alike: a -//! change to judging that alters what an earlier revision's corpus says comes as a later -//! revision. - -use std::collections::{BTreeMap, BTreeSet}; -use std::fmt::Write as _; -use std::path::PathBuf; - -use super::event::{Does, Event}; -use super::fold::Federation; -use super::properties::{self, History, Kind}; -use super::revision::{Feature, Revision}; -use super::store::Id; -use super::store::memory::{Refusal, Store}; -use crate::testrand::Rng; - -/// Of each kind, the seeds histories are generated from, the first so many kept -/// whatever they show, and at most how many kept. -const SCANNED: u64 = 400; -const FIRST: u64 = 2; -const MOST: usize = 8; - -/// The kinds of history generated: with an adversary or not, versions naming checkpoints -/// or not, and versions this continuum doesn't read or not. -fn kinds() -> Vec<Kind> { - let mut kinds = Vec::new(); - for adversary in [false, true] { - for checkpoints in [false, true] { - for unread in [false, true] { - kinds.push(Kind { - adversary, - checkpoints, - unread, - }); - } - } - } - kinds -} - -fn dir() -> PathBuf { - PathBuf::from(env!("CARGO_MANIFEST_DIR")).join("src/federation/corpus") -} - -/// The file of `revision`'s corpus: by its number and the feature it adds, or `base`. -fn file(revision: Revision) -> PathBuf { - let name = match revision.features().last() { - None => "0-base".to_owned(), - Some(feature) => format!("{}-{}", revision.0, feature.name()), - }; - dir().join(format!("{name}.txt")) -} - -/// The first line of `revision`'s corpus, naming it by its ID, so that a renamed feature -/// fails as a changed judgment does. -fn header(revision: Revision) -> String { - format!( - "continuum federation 1, {revision}, ID {}: never edited once released", - revision.id() - ) -} - -/// What became of `id` in `store`, by kind: never a refusal's words, which may change. -fn became(store: &Store<Federation>, id: &Id) -> String { - if store.stopped().is_some_and(|(at, ..)| at == id) { - return "stopped at".to_owned(); - } - if store.held_back().iter().any(|(held, _)| held == id) { - return "held back".to_owned(); - } - if store.holds(id) { - return "taken".to_owned(); - } - if store.get(id).is_some() { - return "kept".to_owned(); - } - match store.refusal(id) { - Some(Refusal::None) => "refused: none".to_owned(), - Some(Refusal::Judged(_)) => "refused: judged".to_owned(), - Some(Refusal::BuiltOn(_)) => "refused: built on a refused one".to_owned(), - Some(Refusal::NotAbove) => "refused: not above the checkpoint".to_owned(), - Some(Refusal::Own) => "refused: its own".to_owned(), - Some(Refusal::Dropped) => "refused: dropped".to_owned(), - None if store.is_waiting(id) => "waiting".to_owned(), - None => "gone with a move".to_owned(), - } -} - -/// What `store` reads: its checkpoint, the current version, the values at places, the -/// members, and the event it stopped at; a line of JSON. -fn reads(store: &Store<Federation>) -> String { - let state = store.state(); - let values: BTreeMap<String, String> = state - .values() - .into_iter() - .map(|(path, value)| (path, String::from_utf8_lossy(&value.bytes()).into_owned())) - .collect(); - serde_json::json!({ - "checkpoint": Id::of(store.checkpoint()).to_string(), - "current": state.current().hash.to_string(), - "values": values, - "members": state.members(), - "stopped": store.stopped().map(|(id, ..)| id.to_string()), - }) - .to_string() -} - -/// A store from `root`, offered `events` in their order. -fn offered(root: &[u8], events: &[Vec<u8>]) -> Store<Federation> { - let mut store = Store::new(root.to_vec(), Vec::new()).expect("a root"); - for event in events { - store.offer(event.clone()); - } - store -} - -/// What a history shows of what a corpus is to hold: of each kind of event, what became -/// of one; and whether a version was written, the store moved to a checkpoint, or stopped. -fn shows(history: &History) -> BTreeSet<String> { - let store = offered(&history.root, &history.events); - let mut shown = BTreeSet::new(); - if store.state().current().number > 0 { - shown.insert("a version written".to_owned()); - } - if Id::of(store.checkpoint()) != store.id() { - shown.insert("a move to a checkpoint".to_owned()); - } - if store.stopped().is_some() { - shown.insert("a stop".to_owned()); - } - for event in &history.events { - let kind = match Event::read_taken(event) { - Some(Event::Signed(signed)) => match signed.does { - Does::Write { .. } => "a write", - Does::Keys(_) => "a key set", - Does::Nodes(_) => "a node list", - Does::Proposal { .. } => "a proposal", - Does::Vote { .. } => "a vote", - Does::Merge => "a merge event", - }, - Some(Event::Version { .. }) => "a version event", - None => "no event", - }; - shown.insert(format!("{kind}: {}", became(&store, &Id::of(event)))); - } - shown -} - -/// A case: a root, and its events offered in the order written; what each became, and -/// what the store reads after, as the corpus spells them. -fn case(label: &str, root: &[u8], events: &[Vec<u8>]) -> String { - let store = offered(root, events); - let mut text = format!("case {label}\nroot {}\n", String::from_utf8_lossy(root)); - for event in events { - let _ = writeln!(text, "event {}", String::from_utf8_lossy(event)); - let _ = writeln!(text, "became {}", became(&store, &Id::of(event))); - } - let _ = writeln!(text, "reads {}", reads(&store)); - text -} - -/// `revision`'s corpus, generated: of each kind, histories whose first version follows -/// `revision`, those of the first seeds, and of the rest those showing what the ones kept -/// don't (`shows`), up to `MOST`. -fn generated(revision: Revision) -> String { - let mut text = header(revision) + "\n"; - for kind in kinds() { - let mut held = BTreeSet::new(); - let mut kept = 0; - for seed in 0..SCANNED { - if kept == MOST { - break; - } - let history = properties::generate_at(&mut Rng::new(seed), kind, Some(revision)); - let shown = shows(&history); - if seed >= FIRST && shown.is_subset(&held) { - continue; - } - held.extend(shown); - kept += 1; - let label = format!("seed {seed}, {kind:?}"); - text += &case(&label, &history.root, &history.events); - } - } - text -} - -/// A corpus's cases, read: each its label, its root, and its events with what each -/// became, and what the store reads after. -struct Case { - label: String, - root: Vec<u8>, - events: Vec<(Vec<u8>, String)>, - reads: String, -} - -fn parse(text: &str) -> Result<(String, Vec<Case>), String> { - let mut lines = text.lines(); - let header = lines.next().ok_or("an empty corpus")?.to_owned(); - let mut cases: Vec<Case> = Vec::new(); - let mut event: Option<Vec<u8>> = None; - for line in lines { - let (word, rest) = line.split_once(' ').ok_or(format!("no line: {line:?}"))?; - let current = cases.last_mut(); - match (word, current) { - ("case", _) => cases.push(Case { - label: rest.to_owned(), - root: Vec::new(), - events: Vec::new(), - reads: String::new(), - }), - ("root", Some(case)) => case.root = rest.as_bytes().to_vec(), - ("event", Some(_)) => event = Some(rest.as_bytes().to_vec()), - ("became", Some(case)) => { - let bytes = event.take().ok_or("`became` without its event")?; - case.events.push((bytes, rest.to_owned())); - } - ("reads", Some(case)) => case.reads = rest.to_owned(), - _ => return Err(format!("no line of a corpus: {line:?}")), - } - } - Ok((header, cases)) -} - -/// Writes the corpus of every revision this continuum knows that has none: once, when a -/// revision is made, its file then committed and never edited. Run by hand: -/// `cargo test --features federation write_the_corpus -- --ignored`. -#[test] -#[ignore = "writes into the source tree: run by hand when a revision is made"] -fn write_the_corpus() { - std::fs::create_dir_all(dir()).expect("the corpus's directory"); - for revision in Revision::known() { - let path = file(revision); - if !path.exists() { - std::fs::write(&path, generated(revision)).expect("the corpus written"); - println!("wrote {}", path.display()); - } - } -} - -/// Every revision this continuum knows has its corpus, which it judges and reads as the -/// corpus says; and which shows a version written, a move to a checkpoint and a stop, and -/// what became of a merge event at that revision: taken where it has merge events, else -/// refused. -#[test] -fn every_revision_judges_as_its_corpus_says() { - for revision in Revision::known() { - let path = file(revision); - let text = std::fs::read_to_string(&path).unwrap_or_else(|_| { - panic!( - "no corpus of {revision} ({}): write it once, as the revision is made, with \ - `cargo test --features federation write_the_corpus -- --ignored`, and \ - commit it", - path.display() - ) - }); - let (named, cases) = parse(&text).unwrap_or_else(|why| panic!("{}: {why}", path.display())); - assert_eq!( - named, - header(revision), - "{}: another revision", - path.display() - ); - assert!(!cases.is_empty(), "{}: no case", path.display()); - let mut shown = BTreeSet::new(); - for case in cases { - let events: Vec<Vec<u8>> = case.events.iter().map(|(bytes, _)| bytes.clone()).collect(); - let judged = self::case(&case.label, &case.root, &events); - shown.extend(shows(&History { - root: case.root.clone(), - events, - })); - let (_, again) = parse(&format!("{named}\n{judged}")).expect("as written"); - let again = &again[0]; - for ((bytes, was), (_, is)) in case.events.iter().zip(&again.events) { - assert_eq!( - was, - is, - "{}, {}: the event {} became otherwise", - path.display(), - case.label, - Id::of(bytes) - ); - } - assert_eq!( - case.reads, - again.reads, - "{}, {}: the store reads otherwise", - path.display(), - case.label - ); - } - let merged = if revision.has(Feature::MergeEvents) { - "a merge event: taken" - } else { - "a merge event: refused: judged" - }; - for wanted in [ - "a version written", - "a move to a checkpoint", - "a stop", - merged, - ] { - assert!( - shown.contains(wanted), - "{}: no case shows {wanted}", - path.display() - ); - } - } -} diff --git a/src/federation/judge.rs b/src/federation/judge.rs index 4fc4ce8..2936bdc 100644 --- a/src/federation/judge.rs +++ b/src/federation/judge.rs @@ -142,7 +142,67 @@ fn reads(store: &Store<Federation>) -> String { #[cfg(test)] mod tests { use super::*; + use crate::federation::attacks; use crate::federation::harness::{self, Party, Spec}; + use crate::federation::properties::{self, Kind}; + use crate::federation::revision::Revision; + use crate::testrand::Rng; + + /// Of each revision and kind, how many seeds' histories are written, times + /// `CONTINUUM_TEST_CASES`. + const CASES: u64 = 25; + + /// Writes the histories to judge to the file `CONTINUUM_HISTORIES` names + /// (`scripts/federation-check`): of each revision this continuum knows and each kind + /// the properties generate, the histories of `CASES` seeds from `CONTINUUM_TEST_SEED` + /// on; and those the attack tests offer, where nothing but offers made them. + #[test] + #[ignore = "writes the file CONTINUUM_HISTORIES names: run by scripts/federation-check"] + fn write_histories() { + let path = std::env::var("CONTINUUM_HISTORIES").expect("CONTINUUM_HISTORIES: a file"); + let env = |name: &str| { + std::env::var(name) + .ok() + .and_then(|value| value.parse::<u64>().ok()) + }; + let first = env("CONTINUUM_TEST_SEED").unwrap_or(0); + let cases = CASES.saturating_mul(env("CONTINUUM_TEST_CASES").unwrap_or(1)); + let mut histories = Vec::new(); + for revision in Revision::known() { + for adversary in [false, true] { + for checkpoints in [false, true] { + for unread in [false, true] { + let kind = Kind { + adversary, + checkpoints, + unread, + }; + for seed in first..first.saturating_add(cases) { + let generated = + properties::generate_at(&mut Rng::new(seed), kind, Some(revision)); + histories.push(History { + label: format!("{revision}, seed {seed}, {kind:?}"), + root: generated.root, + events: generated.events, + }); + } + } + } + } + } + for (name, test) in attacks::TESTS { + for (n, recorded) in attacks::recording(*test).into_iter().enumerate() { + if recorded.offers_only { + histories.push(History { + label: format!("{name}, store {n}"), + root: recorded.root, + events: recorded.events, + }); + } + } + } + std::fs::write(&path, spelled(&histories)).expect("the histories written"); + } /// Histories read back as spelled, and judged as the format says: an event taken, one /// refused, and a root of a revision this continuum doesn't know read as none. diff --git a/src/federation/mod.rs b/src/federation/mod.rs index 18fc70d..b86bc53 100644 --- a/src/federation/mod.rs +++ b/src/federation/mod.rs @@ -11,8 +11,6 @@ pub(crate) mod agent; #[cfg(test)] mod attacks; pub(crate) mod client; -#[cfg(test)] -mod corpus; pub(crate) mod event; pub(crate) mod fold; pub(crate) mod fork; |
