GHSA-cc53-p78w-23w9: 
Rust vulnerability analysis and mitigation

Summary

OrderedSkipList, SkipSet and SkipMap can free a node that is still linked when a Comparator or Ord implementation gives different answers for the same pair of values during one mutating call. A later call reads the freed memory. The caller needs no unsafe: a safe impl Ord with the default comparator is enough. A comparator that is a pure function of its two arguments cannot trigger this, even if it is not transitive. The trigger is a stateful or non-deterministic implementation, for example one that advances a counter or a random state on every call.

Details

The mutating traversals (OrdMutVisitor and OrdIndexMutVisitor) walk down the levels of the list. At each level they record a precursor: the last node whose link at that level points at a node comparing not-Less than the target. They then keep descending. The splice code assumes every recorded precursor's link points at or past the final position. If a later comparison reports one of those nodes as Less, the walk steps past it and that assumption breaks:

• take_first, take, remove and the SkipMap removals rewire the wrong link. They then free the target while its real predecessor still points at it.
• insert builds crossed links and wrong skip distances from the same precursors. The index-based methods (remove(index), get(index), cursors) trust those distances. The corrupted structure turns into a use-after-free on the next access to the dangling link.

PoC

[dependencies]
skiplist = "1.2.0"

use skiplist::OrderedSkipList;
use std::cell::Cell;
use std::cmp::Ordering;
thread_local!(static S: Cell<u32> = const { Cell::new(2) });
#[derive(Debug)]
struct K(u8);
impl PartialEq for K { fn eq(&self, o: &Self) -> bool { self.cmp(o) == Ordering::Equal } }
impl Eq for K {}
impl PartialOrd for K { fn partial_cmp(&self, o: &Self) -> Option<Ordering> { Some(self.cmp(o)) } }
impl Ord for K {
    // Safe, but answers from a pseudo-random sequence instead of the values.
    fn cmp(&self, _o: &Self) -> Ordering {
        S.with(|s| {
            let c = s.get().wrapping_mul(1103515245).wrapping_add(12345);
            s.set(c);
            [Ordering::Less, Ordering::Equal, Ordering::Greater][(c >> 16) as usize % 3]
        })
    }
}
fn main() {
    for seed in 0..200u32 {
        S.with(|s| s.set(seed));
        let mut l: OrderedSkipList<K> = OrderedSkipList::new();
        let mut r = seed.wrapping_mul(2654435761) | 1;
        let mut next = |n: u32| { r = r.wrapping_mul(1664525).wrapping_add(1013904223); (r >> 16) % n };
        for _ in 0..60 {
            let k = K(next(8) as u8);
            match next(7) {
                0 | 1 | 2 => l.insert(k),
                3 => drop(l.take(&k)),
                4 => drop(l.pop_last()),
                5 => drop(l.pop_first()),
                _ => if l.len() > 0 { drop(l.remove(next(l.len() as u32) as usize)) },
            }
        }
    }
}

MIRIFLAGS=-Zmiri-tree-borrows cargo +nightly miri run

Miri reports undefined behaviour (a dangling reference to freed memory) within the first few seeds. The program uses only insert, take, pop_first, pop_last and remove. On 1.3.0 the same program panics with "comparator does not implement a total order".

Impact

CWE-416 (use after free), reachable from safe Rust. Affected code supplies an Ord or Comparator whose answer for a pair can change between calls within one operation: comparisons that read a counter, a cache, a clock, a random source or other shared mutable state. Comparators that are merely non-transitive or otherwise inconsistent, but deterministic, are not affected. After the corruption, any later access may read or free memory that has already been freed. That includes iteration, lookups, further mutation and the collection's own Drop.

Patches

Fixed in 1.3.0 (#407):

• The mutating traversals track the link target of the lowest recorded precursor. A Less answer on reaching that node contradicts the earlier answer, and the traversal panics with "comparator does not implement a total order". The check compares pointers only, so it adds no comparator calls.
• Every splice site checks that each precursor's link reaches the target before the first write.
• take_fast derives its precursors from the list structure without calling the comparator.
• SkipSet entries panic if their element disappears between lookup and use. Every detected contradiction panics before any link, value or length changes, so the collection stays well-formed and safe to drop. A method that chains several steps (append, remove_all, Extend) may panic after earlier steps took effect, still leaving a valid collection. A bad comparator remains a logic error: results may be wrong, but never undefined behaviour.

Workarounds

Make Ord and any custom Comparator a pure function of the two values compared.