aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-12 22:23:15 +0000
committertv <tv@krebsco.de>2026-11-12 22:23:15 +0000
commite519ade32a87811f287bb851e3e1dfcde6b064c9 (patch)
tree9fff94327105957f3a958d55a668cc3a5cf6bf9a
parentbfe93eea9b707b29b78e1f9a7a425e6f891701a0 (diff)
screen: refuse changes Automerge wouldn't have written
Automerge 0.12.0 applies a change that lists an actor none of its operations names, or whose first operation is numbered below its dependencies' or near 2^32. It then gives back another change than the one it was given and saves a document that doesn't load, or panics at the next write. A member sending one stops the nodes that take it. Every change from elsewhere is looked at before Automerge sees it (`document::changes::Written`, from `access::screen::apply`, with or without a policy), and refused like one breaking a rule unless: * encoded again, it has the hash it came with; * its first operation is numbered one after the highest of its dependencies, 1 without any, as a transaction at the document's heads numbers it; * every operation it names (an object, a list's element, an operation replaced) is its own, or was made before it, in the document or by a change of the batch looked at before.
-rw-r--r--docs/access.md6
-rw-r--r--src/access/screen.rs8
-rw-r--r--src/document/changes.rs254
-rw-r--r--src/document/testing.rs64
4 files changed, 331 insertions, 1 deletions
diff --git a/docs/access.md b/docs/access.md
index 5a1e04b..1b40ed2 100644
--- a/docs/access.md
+++ b/docs/access.md
@@ -309,6 +309,12 @@ its change and the node's changes it builds on, no others: a change made under a
node's actor is forged, refused, and logged as its sender's (`A peer brought changes
forged`). A member can then no longer write as another member; the user a change names is still its node's word.
+Whatever the policy, and without one, a change is refused that Automerge itself
+wouldn't have written: bytes that aren't Automerge's encoding of the change, a first
+operation not numbered one after the highest of its dependencies, an operation that
+names one nobody made before it (an object written into, a value replaced). Automerge
+applies some of those, and then panics or saves a document that doesn't load.
+
In a swarm without a registry, whatever a user would need, any member may. A refused
change stays out, and so does whatever builds on it; the node logs it (`Refused a
change`) and lists the last thousand (`GET /admin/refused`). Offered again, as its
diff --git a/src/access/screen.rs b/src/access/screen.rs
index 8fd2c61..becf3bc 100644
--- a/src/access/screen.rs
+++ b/src/access/screen.rs
@@ -415,6 +415,8 @@ pub(crate) fn apply(
// The values their users sign, under a strict policy, as the document holds them:
// read again once the document takes the accepted (`reaches_signed`).
let mut signed: Option<Option<Vec<Vec<String>>>> = None;
+ // What those looked at so far made (`changes::Written`).
+ let mut written = crate::document::changes::Written::default();
for (index, change) in ready.into_iter().enumerate() {
let hash = change.hash();
let committer = committers[index].as_deref();
@@ -442,6 +444,12 @@ pub(crate) fn apply(
.push(refuse(format!("it builds on refused change {dep}")));
continue;
}
+ // None that Automerge writes: refused before Automerge sees it.
+ if let Some(why) = written.check(doc, &change, &decoded[index]) {
+ refused.insert(hash, hash);
+ screened.refused.push(refuse(why));
+ continue;
+ }
// Made under an actor whose change at its seq the document holds: forged, by
// whoever brought it, not by the node the actor is.
if signatures
diff --git a/src/document/changes.rs b/src/document/changes.rs
index fd14a4e..6e3fb51 100644
--- a/src/document/changes.rs
+++ b/src/document/changes.rs
@@ -6,7 +6,7 @@ use std::collections::{HashMap, HashSet};
use anyhow::{Result, anyhow, bail};
-use super::{Change, ChangeHash, Document, ReadDoc};
+use super::{ActorId, Change, ChangeHash, Document, ExpandedChange, ReadDoc};
/// Whether `doc` has applied the change `hash`. Without `get_change_by_hash`, which
/// builds the change again from the document's operations, at a cost growing with its
@@ -283,6 +283,113 @@ pub(crate) fn changes_in(mut data: &[u8]) -> Option<Vec<Change>> {
Some(changes)
}
+/// What the changes of a batch made that passed [`Written::check`]: those after them
+/// in the batch build on them before the document holds them.
+#[derive(Default)]
+pub(crate) struct Written {
+ /// The highest operation counter of each.
+ max_ops: HashMap<ChangeHash, u64>,
+ /// The operation counters each made, by its actor: first and last.
+ ops: HashMap<ActorId, Vec<(u64, u64)>>,
+}
+
+impl Written {
+ /// Why `change` (`expanded`: it, decoded) is none that Automerge writes, building
+ /// on `doc` and the changes checked before it; None if it is one, which is then
+ /// among those. Automerge 0.12 applies changes that aren't, and is broken by them:
+ /// it then gives back another change than the one it was given and saves a
+ /// document that doesn't load, or panics. No honest node makes such a change, so
+ /// each from elsewhere is looked at first:
+ ///
+ /// * Its bytes are the ones Automerge encodes for it. (One listing an actor none
+ /// of its operations names loads, with another hash than its own encoding has.)
+ /// * Its first operation is numbered one after the highest of its dependencies, 1
+ /// without any: what a transaction at the document's heads gives it. (One
+ /// numbered below them saves to a document that doesn't load; one numbered
+ /// near 2^32 makes the next write panic.)
+ /// * Every operation it names (an object written into, an element of a list, an
+ /// operation replaced) is one of its own, or one made before it, in `doc` or by
+ /// a change checked before.
+ pub(crate) fn check(
+ &mut self,
+ doc: &Document,
+ change: &Change,
+ expanded: &ExpandedChange,
+ ) -> Option<String> {
+ use automerge::legacy::{ElementId, Key, ObjectId, OpId};
+ let hash = change.hash();
+ if Change::from(expanded.clone()).hash() != hash {
+ return Some("its bytes aren't the ones Automerge encodes for it".to_owned());
+ }
+ let start = change.start_op().get();
+ let last = change.max_op();
+ let before: Option<u64> = change
+ .deps()
+ .iter()
+ .map(|dep| {
+ self.max_ops
+ .get(dep)
+ .copied()
+ .or_else(|| doc.get_change_meta_by_hash(dep).map(|meta| meta.max_op))
+ })
+ .try_fold(0, |highest, max_op| {
+ max_op.map(|max_op| highest.max(max_op))
+ });
+ // A dependency neither here nor there: not ready, and Automerge doesn't apply
+ // it (callers judge those whose dependencies they hold).
+ if let Some(before) = before
+ && start != before + 1
+ {
+ return Some(format!(
+ "its first operation is numbered {start}, not {}, one after the highest of its dependencies",
+ before + 1
+ ));
+ }
+ let actor = change.actor_id();
+ let made = |OpId(counter, by): &OpId| {
+ if by == actor && (start..=last).contains(counter) {
+ return true;
+ }
+ *counter < start
+ && (self.ops.get(by).is_some_and(|ranges| {
+ ranges
+ .iter()
+ .any(|(first, last)| (*first..=*last).contains(counter))
+ }) || doc
+ .hash_for_opid(&automerge::ObjId::Id(*counter, by.clone(), 0))
+ .is_some())
+ };
+ for op in &expanded.operations {
+ let object = match &op.obj {
+ ObjectId::Id(id) => Some(id),
+ ObjectId::Root => None,
+ };
+ let element = match &op.key {
+ Key::Seq(ElementId::Id(id)) => Some(id),
+ Key::Seq(ElementId::Head) | Key::Map(_) => None,
+ };
+ if let Some(OpId(counter, by)) = object
+ .into_iter()
+ .chain(element)
+ .chain(op.pred.iter())
+ .find(|id| !made(id))
+ {
+ return Some(format!(
+ "it names an operation nobody made before it ({counter}@{by})"
+ ));
+ }
+ }
+ self.max_ops.insert(hash, last);
+ if last >= start {
+ self.ops
+ .entry(actor.clone())
+ .or_default()
+ .push((start, last));
+ }
+ None
+ }
+}
+
/// `change`, if it names an author but isn't its actor's first (`misplaced_author`).
fn misplaced_in(change: &Change) -> Option<MisplacedAuthor> {
let author = change.author()?;
@@ -539,4 +646,149 @@ mod tests {
// Still whole: it saves and loads.
crate::document::load(&doc.save()).unwrap();
}
+
+ /// A document written the ways the store writes: maps within maps, lists, text,
+ /// values replaced and deleted, by two nodes at once.
+ fn written() -> Document {
+ use automerge::ObjType;
+ let mut doc = Document::new();
+ let (map, list) = change(&mut doc, |doc| {
+ let map = doc.put_object(ROOT, "map", ObjType::Map).unwrap();
+ doc.put(&map, "k", "v").unwrap();
+ let list = doc.put_object(&map, "list", ObjType::List).unwrap();
+ doc.insert(&list, 0, 1).unwrap();
+ doc.insert(&list, 1, "two").unwrap();
+ (map, list)
+ });
+ change(&mut doc, |doc| {
+ doc.put(&map, "k", vec![1u8, 2, 3]).unwrap();
+ doc.delete(&list, 0).unwrap();
+ doc.insert(&list, 1, true).unwrap();
+ let text = doc.put_object(ROOT, "text", ObjType::Text).unwrap();
+ doc.splice_text(&text, 0, 0, "hello").unwrap();
+ });
+ let mut other = doc.fork();
+ change(&mut other, |doc| doc.put(&map, "k", 2.5).unwrap());
+ change(&mut other, |doc| doc.delete(&map, "list").unwrap());
+ change(&mut doc, |doc| doc.put(&map, "k", ()).unwrap());
+ change(&mut doc, |doc| doc.delete(ROOT, "text").unwrap());
+ doc.merge(&mut other).unwrap();
+ change(&mut doc, |doc| doc.put(&map, "k", "merged").unwrap());
+ doc
+ }
+
+ /// What Automerge writes passes: checked against a document taking the changes
+ /// one by one, and as one batch against an empty one.
+ #[test]
+ fn changes_automerge_writes_pass() {
+ let theirs = written();
+ let changes = theirs.get_changes(&[]);
+ let mut ours = Document::new();
+ for change in &changes {
+ assert_eq!(
+ Written::default().check(&ours, change, &change.decode()),
+ None
+ );
+ ours.apply_changes([change.clone()]).unwrap();
+ }
+ let empty = Document::new();
+ let mut written = Written::default();
+ for change in &changes {
+ assert_eq!(written.check(&empty, change, &change.decode()), None);
+ }
+ }
+
+ /// Bytes that load as a change and aren't Automerge's encoding of it: refused.
+ #[test]
+ fn bytes_automerge_wouldnt_encode_are_refused() {
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap());
+ let honest = theirs.get_changes(&[]).remove(0);
+ let ours = Document::new();
+ assert_eq!(
+ Written::default().check(&ours, &honest, &honest.decode()),
+ None
+ );
+ let crafted = crate::document::testing::with_spare_actor(honest.raw_bytes(), &[0xab; 16]);
+ let crafted = Change::try_from(&crafted[..]).expect("it loads");
+ assert_ne!(crafted.hash(), honest.hash());
+ let why = Written::default()
+ .check(&ours, &crafted, &crafted.decode())
+ .expect("refused");
+ assert!(why.contains("encodes"), "{why}");
+ }
+
+ /// A first operation numbered ahead of the dependencies', or below them: refused.
+ #[test]
+ fn operations_numbered_against_their_dependencies_are_refused() {
+ let mut theirs = Document::new();
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap());
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 2).unwrap());
+ let mut ours = Document::new();
+ ours.apply_changes(theirs.get_changes(&[])).unwrap();
+ change(&mut theirs, |doc| doc.put(ROOT, "other", 3).unwrap());
+ let honest = theirs.get_last_local_change().unwrap();
+ assert_eq!(honest.start_op().get(), 3);
+ for start in [1, 2, 4, (1 << 32) - 1] {
+ let mut expanded = honest.decode();
+ expanded.start_op = std::num::NonZeroU64::new(start).unwrap();
+ expanded.hash = None;
+ let crafted = Change::from(expanded);
+ let why = Written::default()
+ .check(&ours, &crafted, &crafted.decode())
+ .expect("refused");
+ assert!(why.contains("numbered"), "{start}: {why}");
+ }
+ assert_eq!(
+ Written::default().check(&ours, &honest, &honest.decode()),
+ None
+ );
+ // A root: numbered 1.
+ let root = theirs.get_changes(&[]).remove(0);
+ let mut expanded = root.decode();
+ expanded.start_op = std::num::NonZeroU64::new(7).unwrap();
+ expanded.hash = None;
+ let crafted = Change::from(expanded);
+ assert!(
+ Written::default()
+ .check(&Document::new(), &crafted, &crafted.decode())
+ .is_some()
+ );
+ }
+
+ /// An operation on an object nobody made, by an actor the document doesn't hold or
+ /// at a counter its actor never reached: refused.
+ #[test]
+ fn operations_naming_what_nobody_made_are_refused() {
+ use automerge::legacy::{ObjectId, OpId};
+ let mut theirs = Document::new();
+ let map = change(&mut theirs, |doc| {
+ doc.put_object(ROOT, "map", automerge::ObjType::Map)
+ .unwrap()
+ });
+ change(&mut theirs, |doc| doc.put(ROOT, "k", 1).unwrap());
+ let mut ours = Document::new();
+ ours.apply_changes(theirs.get_changes(&[])).unwrap();
+ change(&mut theirs, |doc| doc.put(&map, "k", 2).unwrap());
+ let honest = theirs.get_last_local_change().unwrap();
+ assert_eq!(
+ Written::default().check(&ours, &honest, &honest.decode()),
+ None
+ );
+ let known = theirs.get_actor().clone();
+ for object in [
+ OpId(1, ActorId::from([0xab; 16])),
+ OpId(honest.start_op().get() + 5, known.clone()),
+ OpId(honest.start_op().get(), ActorId::from([0xab; 16])),
+ ] {
+ let mut expanded = honest.decode();
+ expanded.operations[0].obj = ObjectId::Id(object.clone());
+ expanded.hash = None;
+ let crafted = Change::from(expanded);
+ let why = Written::default()
+ .check(&ours, &crafted, &crafted.decode())
+ .expect("refused");
+ assert!(why.contains("nobody made"), "{object:?}: {why}");
+ }
+ }
}
diff --git a/src/document/testing.rs b/src/document/testing.rs
index cd6c15b..1e83db2 100644
--- a/src/document/testing.rs
+++ b/src/document/testing.rs
@@ -74,3 +74,67 @@ pub(crate) fn with_author_footer(raw: &[u8], author: &[u8]) -> Vec<u8> {
out.extend(body);
out
}
+
+/// `raw` (an uncompressed change chunk whose operations name no actor but its own)
+/// listing `spare` among its other actors, its checksum made right again: bytes that
+/// load as a change and aren't the ones Automerge encodes for it (`changes::Written`).
+pub(crate) fn with_spare_actor(raw: &[u8], spare: &[u8]) -> Vec<u8> {
+ use sha2::{Digest, Sha256};
+ fn leb(mut n: usize, out: &mut Vec<u8>) {
+ loop {
+ let byte = (n & 0x7f) as u8;
+ n >>= 7;
+ if n == 0 {
+ out.push(byte);
+ return;
+ }
+ out.push(byte | 0x80);
+ }
+ }
+ // A number (LEB128) at `at`, and how many bytes it takes.
+ fn read(bytes: &[u8], at: usize) -> (usize, usize) {
+ let (mut n, mut read, mut shift) = (0usize, 0, 0);
+ loop {
+ let byte = bytes[at + read];
+ n |= usize::from(byte & 0x7f) << shift;
+ read += 1;
+ if byte & 0x80 == 0 {
+ return (n, read);
+ }
+ shift += 7;
+ }
+ }
+ assert_eq!(raw[8], 1, "an uncompressed change chunk");
+ let (length, taken) = read(raw, 9);
+ let body = &raw[9 + taken..9 + taken + length];
+ // Its dependencies, its actor, its seq and first operation, its time, its message:
+ // then the other actors.
+ let (deps, taken) = read(body, 0);
+ let mut at = taken + 32 * deps;
+ let (actor, taken) = read(body, at);
+ at += taken + actor;
+ for _ in 0..3 {
+ at += read(body, at).1;
+ }
+ let (message, taken) = read(body, at);
+ at += taken + message;
+ let (others, taken) = read(body, at);
+ assert_eq!(others, 0, "a change naming no other actor");
+ let mut crafted = body[..at].to_vec();
+ crafted.push(1);
+ leb(spare.len(), &mut crafted);
+ crafted.extend_from_slice(spare);
+ crafted.extend_from_slice(&body[at + taken..]);
+ let mut header = Vec::new();
+ leb(crafted.len(), &mut header);
+ let mut summed = vec![1u8];
+ summed.extend(&header);
+ summed.extend(&crafted);
+ let sum = Sha256::digest(&summed);
+ let mut out = raw[..4].to_vec();
+ out.extend(&sum[..4]);
+ out.push(1);
+ out.extend(header);
+ out.extend(crafted);
+ out
+}