Unsoundness in yrs

[ColonelThirtyTwo]

(Disclaimer: I am filing this disclosure personally and not on behalf of my employer)

YRS is a moderately popular (2M downloads according to crates.io) implementation of the y.js CRDT data structure, used for collaborative editing.

It is very unsound. Fundamental types are simple pointer wrappers and offer & and &mut access without any checks for aliasing or if the data has been deallocated, and fuzz testing reveals many panics and aborts from parsing untrusted input.

In particular, the BranchPtr structure, which forms the base of many other structures exposed in the public API, is a wrapper around a NonNull<Branch>. It implements Clone, Copy, Send, and Sync, but also offers a Deref and DerefMut that simply get a reference to the underlying object, leading to trivial aliasing issues. Additionally, it implements From<&Branch> and From<&Box<Branch>> and does no lifetime tracking, leading to trivial use-after-free issues.

As an example:

use yrs::{branch::Branch, Doc, Text as _, Transact};

fn main() {
    let doc = Doc::new();
    let item = doc.get_or_insert_text("test");

    let branch_ptr = AsRef::<Branch>::as_ref(&item).id().get_branch(
        &doc.transact()
    ).unwrap();
    std::mem::drop(doc); // item and branch_ptr are now now dangling

    branch_ptr.id(); // UB: branch_ptr is dangling

    let doc = Doc::new();
    let txn = doc.transact();
    item.len(&txn); // UB: access to dangling item
}

As another example, the Read::read_string trait in src/encoding/read.rs uses from_utf8_unchecked on untrusted input from a file.

Fuzzing the library (parsing and applying a document update to an empty doc) reveals a lot of panics and AddressSanitizer aborts. While I imagine some of the use-after-free issues could be leveraged into an actual exploit, I don't have the expertise needed to properly assess and document the issues as exploits.

I filed an issue about the BranchPtr unsoundness when I came across it a year ago as y-crdt/y-crdt#506, and emailed the author with my findings from fuzzing. I never received a response to the email, and re-running the fuzzer today on the v0.27.3 tag still yields similar crashes.

Given that this is a library routinely exposed to untrusted input from many users, the existence of these issues and crashes is very concerning.