GHSA-924w-mwc9-86m8: 
Rust vulnerability analysis and mitigation

Summary

Four code paths create a pointer whose permission is later revoked, then write through it. Miri reports each as undefined behaviour under the Tree Borrows aliasing model. All four are reachable from safe code with standard Ord types and no unusual comparator:

Details

1. Splice back-pointer

Node::set_head_next stored NonNull::from(&mut *self) as the prev pointer of the first spliced node, then wrote self.next through the parent reference. Under Tree Borrows that write is foreign to the stored pointer's tag, so the back-pointer is disabled before the function returns. Node::pop later writes through it. split_off, split_off_index and append call set_head_next, as does the unwind-recovery path in DropChain. Any later write through the spliced node's prev, such as pop_first or pop_front, is undefined behaviour.

2. SkipMap::range_mut back pointer

For an Included or Excluded upper bound, range_mut built its back pointer with NonNull::from(&node), from a shared reference, so the pointer only permits reads. IterMut::next_back hands out &mut V through it, and writing through that reference is undefined behaviour. OrderedSkipList::range uses the same pattern, but it never writes, so it is sound.

3. IterMut::next_back reads a yielded node

IterMut::next_back in SkipList and SkipMap checked whether the predecessor node held a value. When the front end had already yielded that node, the check reborrowed it while the caller still held its &mut. That read freezes the caller's reference, and the caller's next write through it is undefined behaviour.

4. Cursor list pointer

OrderedSkipList::lower_bound_mut and upper_bound_mut (and the SkipSet wrappers) took the cursor's *mut list pointer, then searched through &self. The comparator lives inside the list. A comparator that writes to interior-mutable state, such as a Cell call counter, therefore writes to the list's own memory through the shared borrow. That write disables the cursor's pointer, and the cursor is built from it, which is undefined behaviour before any cursor operation runs. The comparator can be a perfectly consistent order. SkipMap cursors are not affected.

PoC

[dependencies]
skiplist = { version = "1.2.0", features = ["cursor"] }

Run each with MIRIFLAGS=-Zmiri-tree-borrows cargo +nightly miri run. Each line marked // UB is reported by Miri on 1.2.0.

// 1. Splice back-pointer
use skiplist::OrderedSkipList;
fn main() {
    let mut a: OrderedSkipList<i32> = OrderedSkipList::new();
    let mut b: OrderedSkipList<i32> = [1].into_iter().collect();
    a.append(&mut b);
    a.pop_first(); // UB
}

// 2. SkipMap::range_mut back pointer
use skiplist::SkipMap;
fn main() {
    let mut m = SkipMap::<i32, i32>::new();
    for k in 0..20 {
        m.insert(k, k);
    }
    if let Some((_, v)) = m.range_mut(..=10).next_back() {
        *v = 99; // UB
    }
}

// 3. IterMut from both ends
use skiplist::SkipList;
fn main() {
    let mut list = SkipList::<i32>::new();
    list.push_back(10);
    list.push_back(20);
    let mut iter = list.iter_mut();
    let a = iter.next().unwrap();
    *a = 11;
    let b = iter.next_back().unwrap();
    *b = 21;
    *a = 12; // UB
}

// 4. Cursor with an interior-mutable comparator
use core::{cell::Cell, cmp::Ordering, ops::Bound};
use skiplist::{
    OrderedSkipList,
    comparator::{Comparator, ComparatorKey},
};
#[derive(Default)]
struct Counting(Cell<usize>);
impl Comparator<i32> for Counting {
    fn compare(&self, a: &i32, b: &i32) -> Ordering {
        self.0.set(self.0.get() + 1);
        a.cmp(b)
    }
}
impl ComparatorKey<i32, i32> for Counting {
    fn compare_key(&self, stored: &i32, key: &i32) -> Ordering {
        self.compare(stored, key)
    }
}
fn main() {
    let mut l = OrderedSkipList::<i32, 16, Counting>::with_comparator(Counting::default());
    for v in 1..=5 {
        l.insert(v);
    }
    let mut cur = l.lower_bound_mut(Bound::Included(&3)); // UB
    cur.remove_next();
}

Impact

CWE-758 (reliance on undefined behaviour), reachable from safe Rust. All four are violations of Rust's aliasing rules as modelled by Tree Borrows, which Miri detects. No miscompilation has been observed in an optimised build. They are still undefined behaviour: a future compiler is entitled to optimise on the violated assumptions, and the result would be memory corruption at these call sites.

Patches

Fixed in 1.3.0 (#407). Each fix derives the pointer used for mutation from the collection's long-lived allocation pointers:

1. set_head_next takes this: NonNull<Self> and writes through raw-pointer place expressions. Every caller passes the pointer from Box::into_raw.
2. The range_mut back pointer is the stored prev of the following node, or the stored tail. The search and its comparator calls are unchanged.
3. next_back stores the predecessor pointer without reading it. The remaining-length counter stops iteration before that pointer is used.
4. The cursor takes its list pointer after the search finishes. Each has a Miri regression test.

Workarounds

Upgrade to 1.3.0. Short of that, avoid the trigger sequences in the table above.