UAF/double-free in RcNode::clone and downgrade / upgrade from a broken ref_cnt invariant

[azchin]

Hello! Not sure if this crate is maintained, but I want to report bug I found. A suggested fix is included as well.

Use-after-free / double-free in RcNode::clone, RcNode::downgrade/WeakNode::drop, and WeakNode::upgrade from a broken ref_cnt invariant in the Piled reference-counting path.

• Crate: trees 0.4.2 (general-purpose tree data structures; the bugs are in the Piled / NodeVec reference-counting path — the Scattered / Rc path is clean)
• Git revision: repository https://github.com/oooutlk/trees; 0.4.2 is the latest release (crates.io published 2021-02-20). Default branch master, HEAD = commit e4fcc93f37c5a3e06dce485816698139ba07e545 (2021-02-20) — identical to the 0.4.2 release.
• OS / environment: Ubuntu 24.04.4 LTS (Linux 6.11.0-rc3-sev-es x86_64); rustc 1.91.0-nightly (f34ba774c 2025-08-03); cargo-miri 0.1.0 (f34ba774c7 2025-08-03).
• Type: Memory-safety / unsoundness (UB) — use-after-free / double-free from a reference-count miscount.

Reported by Andrew Chin, an academic researcher from Team Atlanta / Georgia Tech

Threat model

Both defects are reachable from 100% safe code, with no untrusted input and no concurrency (the types are single-threaded Cell-based reference counting). Safe entry points:

• Bug 1 — RcNode::clone() on a Piled RcNode: cloning then dropping the clone frees the shared buffer while other handles still point into it.
• Bug 2 — RcNode::downgrade() followed by dropping the resulting WeakNode (and, sharing the same root cause, WeakNode::upgrade()): creating and dropping a weak handle under-counts the shared buffer's reference count, freeing it one drop early.

Both are trivially reachable — an ordinary .clone() or .downgrade() on a reference-counted node, which is the crate's headline feature, is enough. Neither trigger is contrived.

Reproduction

Two PoCs, one per bug (both use Cargo.toml dependency trees = "=0.4.2"). Both are run with MIRIFLAGS="-Zmiri-disable-stacked-borrows".

Why Stacked Borrows is disabled: the Piled construction path (Tree::from_tuple → NodeVec::node_mut) contains a separate, already-known aliasing issue — upstream issue #16 — that Stacked Borrows flags first, before the ref_cnt free under test, which would otherwise mask the use-after-free. That issue is not the subject of this report; disabling SB isolates the ref_cnt UAF. (Tree Borrows behaves the same way.)

Bug 1 — clone → drop clone → read through a live &Node into the freed buffer (main.rs):

use trees::{Tree, RcNode};
fn main() {
    let r: RcNode<i32> = RcNode::from(Tree::<i32>::from_tuple((0, 1, 2)));
    let c = r.clone();               // bumps node.count, NOT ref_cnt
    let f = r.front().unwrap();      // live ref into the NodeVec buf
    println!("[poc] dropping clone (over-decrements ref_cnt -> frees buf while `f` is live)...");
    drop(c);                         // ref_cnt hits 0 early -> buf freed
    let _ = f.data();                // read through a ref into the freed buf -> UAF
    println!("[poc] survived (Miri should have flagged the UAF)");
}

MIRIFLAGS="-Zmiri-disable-stacked-borrows" cargo +nightly miri run

[poc] dropping clone (over-decrements ref_cnt -> frees buf while `f` is live)...
[poc] survived (Miri should have flagged the UAF)
error: Undefined Behavior: constructing invalid value: encountered a dangling reference (use-after-free)
   --> .../core/src/ptr/non_null.rs:437:18
    = note: inside `trees::RcNode::<i32>::node_borrow_mut` at trees-0.4.2/src/rc.rs:204
    = note: inside `trees::RcNode::<i32>::pop_front`      at trees-0.4.2/src/rc.rs:335
    = note: inside `<trees::RcNode<i32> as Drop>::drop`   at trees-0.4.2/src/rc.rs:138

Bug 2 — downgrade → drop weak → read into the buffer freed one drop early (bug2.rs):

use trees::{Tree, RcNode};
fn main() {
    let r: RcNode<i32> = RcNode::from(Tree::<i32>::from_tuple((0, 1, 2)));
    let w = r.downgrade();           // no ref_cnt.incr()
    println!("[poc2] dropping weak (WeakNode::drop decrements ref_cnt -> frees buf early)...");
    drop(w);                         // ref_cnt under-counted -> buf freed while `r` alive
    let f = r.front().unwrap();      // read into the (now freed) NodeVec buf -> UAF
    let _ = f.data();
    println!("[poc2] survived (Miri should have flagged the UAF)");
}

MIRIFLAGS="-Zmiri-disable-stacked-borrows" cargo +nightly miri run --bin bug2

[poc2] dropping weak (WeakNode::drop decrements ref_cnt -> frees buf early)...
[poc2] survived (Miri should have flagged the UAF)
error: Undefined Behavior: constructing invalid value: encountered a dangling reference (use-after-free)
   --> .../core/src/ptr/non_null.rs:437:18
    = note: inside `std::ptr::NonNull::<trees::node_vec::NodeVec<i32>>::as_ref` at .../core/src/ptr/non_null.rs:437
    = note: inside `trees::RcNode::<i32>::node_borrow_mut` at trees-0.4.2/src/rc.rs:204
    = note: inside `trees::RcNode::<i32>::pop_front`      at trees-0.4.2/src/rc.rs:335
    = note: inside `<trees::RcNode<i32> as Drop>::drop`   at trees-0.4.2/src/rc.rs:138

After applying the ref_cnt fix below (verified against a patched local checkout via [patch.crates-io]), both PoCs print [poc] survived (...) and exit cleanly with no UAF.

The bug

Model. In the Piled path, nodes live in a single NodeVec { buf: Vec<Shared<RefCell<Node<T>>>>, ref_cnt: Cell<usize> } (src/node_vec.rs). Each per-node Shared::count (src/rc.rs:8-15) starts at 1, and ref_cnt is initialized to the node count cap (src/node_vec.rs:20). The buffer is freed exactly when ref_cnt reaches 0 (NodeVec::decr_ref, src/node_vec.rs:171, and WeakNode::drop, src/rc.rs:559). Every live handle — strong RcNode or weak WeakNode — owns one unit of ref_cnt, because every handle's Drop decrements ref_cnt. The canonical constructor Node::rc() respects this, bumping both counters:

// src/rc.rs, Node::rc()  (Piled arm)
let node_vec = owner.as_ref();
node_vec.ref_cnt.incr();          // buffer-level count
let node = node_vec.buf.get_unchecked( index );
node.count.incr();                // per-node strong count

All three affected methods (clone, downgrade, upgrade) break the invariant by bumping only count (or neither), while Drop always decrements ref_cnt.

Bug 1 — RcNode::clone() omits ref_cnt.incr() (src/rc.rs:110-123) — UAF / double-free

impl<T> Clone for RcNode<T> {
    fn clone( &self ) -> RcNode<T> {
        match self {
            RcNode::Scattered(...) => ...,
            RcNode::Piled( PiledRcNode( node_vec, index )) => {
                unsafe {
                    let node = node_vec.as_ref().buf.get_unchecked( *index );
                    node.count.incr();          // <-- bumps per-node count only
                    // MISSING: node_vec.as_ref().ref_cnt.incr();
                }
                RcNode::Piled( PiledRcNode( node_vec.clone(), *index ))  // NonNull copy, no ref_cnt.incr()
            },
        }
    }
}

Drop for RcNode (src/rc.rs:125-149) always calls NodeVec::decr_ref (:148), decrementing ref_cnt. So each clone()→drop nets one extra ref_cnt decrement. Once the extra decrement drives ref_cnt to 0, NodeVec::decr_ref runs Box::from_raw(owner.as_ptr()) and frees the buf while other live RcNodes (and &Node references handed out from them) still point into it → use-after-free, and a subsequent handle drop double-frees.

Bug 2 — RcNode::downgrade() omits ref_cnt.incr() (src/rc.rs:456-460); WeakNode::upgrade() shares the cause (:543-551) — UAF

pub fn downgrade( &self ) -> WeakNode<T> {
    match self {
        RcNode::Scattered(...) => ...,
        RcNode::Piled( PiledRcNode( node_vec, index )) =>
            WeakNode::Piled( PiledWeakNode( *node_vec, *index )),  // <-- no ref_cnt.incr()
    }
}

impl<T> Drop for WeakNode<T> {
    fn drop( &mut self ) {
        if let WeakNode::Piled( PiledWeakNode( node_vec, _ )) = self {
            unsafe {
                if node_vec.as_ref().ref_cnt.decr() == 0 {          // <-- always decrements
                    drop( Box::from_raw( node_vec.as_ptr() ));
                }
            }
        }
    }
}

downgrade copies (node_vec, index) into a WeakNode without touching ref_cnt, but WeakNode::drop unconditionally decrements it. Creating and dropping a single weak handle therefore under-counts ref_cnt by one and frees the buffer one drop early, while strong handles are still alive. WeakNode::upgrade (:543) has the mirror defect: it bumps node.count for the new strong RcNode but not ref_cnt, so the upgraded strong handle's eventual drop over-decrements ref_cnt.

Note (separate, not reported here). The Piled construction path also forms a &mut from a shared try_borrow_unguarded() borrow in NodeVec::non_null_node/node_mut, which Miri's Stacked/Tree Borrows reject. This is an aliasing-model violation with no observed miscompilation, and it is already loosely tracked upstream as issue #16; it is out of scope for this report and is only why the PoCs above disable Stacked Borrows.

Potential Fix

Restore the ref_cnt == (number of live strong + weak handles) invariant by incrementing ref_cnt in lockstep wherever a new handle is created — clone, downgrade, and upgrade — mirroring what the canonical Node::rc() already does and what every Drop already decrements.

diff --git a/src/rc.rs b/src/rc.rs
index c8e7be2..37ca4a1 100644
--- a/src/rc.rs
+++ b/src/rc.rs
@@ -115,6 +115,7 @@ impl<T> Clone for RcNode<T> {
                 unsafe {
                     let node = node_vec.as_ref().buf.get_unchecked( *index );
                     node.count.incr();
+                    node_vec.as_ref().ref_cnt.incr(); // keep ref_cnt in lockstep with the new strong handle
                 }
                 RcNode::Piled( PiledRcNode( node_vec.clone(), *index ))
             },
@@ -455,7 +456,11 @@ impl<T> RcNode<T> {
     pub fn downgrade( &self ) -> WeakNode<T> {
         match self {
             RcNode::Scattered( ScatteredRcNode( rc )) => WeakNode::Scattered( ScatteredWeakNode( Rc::downgrade( &rc ))),
-            RcNode::Piled( PiledRcNode( node_vec, index )) => WeakNode::Piled( PiledWeakNode( *node_vec, *index )),
+            RcNode::Piled( PiledRcNode( node_vec, index )) => unsafe {
+                // A `WeakNode` also owns one `ref_cnt` unit (its `Drop` decrements it).
+                node_vec.as_ref().ref_cnt.incr();
+                WeakNode::Piled( PiledWeakNode( *node_vec, *index ))
+            },
         }
     }
 
@@ -545,6 +550,7 @@ impl<T> WeakNode<T> {
                     None
                 } else {
                     node.count.incr();
+                    node_vec.as_ref().ref_cnt.incr(); // new strong handle also owns one ref_cnt unit
                     Some( RcNode::Piled( PiledRcNode( *node_vec, *index )))
                 }
             },

Deduplication Check

Fresh upstream search on 2026-07-14 confirms both defects are unfixed and unreported:

• Latest release: 0.4.2 (2021-02-20) is still the newest crate on crates.io — no 0.4.3+ and no newer line. The reported version is the latest.
• Default branch (master): HEAD (e4fcc93, 2021-02-20, message "version 0.4.2") is identical to the 0.4.2 release — no post-release fixes. Both claims reproduce verbatim in current source: RcNode::clone (Piled arm) still does node.count.incr() without ref_cnt.incr(); downgrade/upgrade (Piled arms) still omit ref_cnt.incr(). (The Scattered/Rc arms are clean, matching the report.)
• No advisory: https://rustsec.org/packages/trees.html → 404 — no RUSTSEC entry.

Advisory

• Advisory: Present in trees 0.4.2 (latest release) and on master. The Piled RcNode/NodeVec reference-counting path is present since the 0.4.x series, so treat as affecting all 0.4.x (≤ 0.4.2); no fixed release exists. Recommend a RUSTSEC advisory (memory-corruption / use-after-free; informational = "unsound" at minimum).