Unsoundness in tokio-util's LinkedList/ListNode APIs

[thomcc]

Version: master branch
Platform: Any

Description

The LinkedList/ListNode apis are unsound, and can be used to gain multiple mutable pointers to objects in the list, access freed memory, etc.

#[test]
fn example_uaf() {
    let mut list = LinkedList::new();
    let mut a = ListNode::new(vec!["foo".to_string()]);
    // Safety: According to `add_front`, this should be safe, as
    // `a` is not moved, dropped, or added to any other lists while
    // `list` is alive
    unsafe {
        list.add_front(&mut a);
    }
    let s = list.peek_last().unwrap()[0].as_str();
    let v = list.peek_last().unwrap();
    v.clear();
    println!("already been freed: {}", s);
}

This prints garbage that has been freed. Additionally some of the existing tests fail under miri, and it's easy to cause issues like that in the API.

I don't see an obvious way to actually trigger the bad behavior in tokio's public API as it stands, but someone should audit uses of this. Because of that, I didn't report this as a security issue.

It's also arguable that the fix for this is to adjust add_front's docs to say not to do this. I suspect the peek methods would still violate stacked borrows in this case, but I could be wrong... It also isn't really great IMO to have an unsafe function that is "I promise everything from here on out is fine" but either way, yeah.

[hawkw]

Just to clarify for others: this is referring to the LinkedList in tokio-util, not to the LinkedList in the tokio crate. I was confused for a minute because I didn't think the tokio version had a method called add_front (it's pop_front there).

[thomcc]

Ah, I'm sorry!

[hawkw]

@thomcc not a problem I just wanted to make sure that was clear for future readers.

[pandaman64]

I don't think the implementations of peek methods are necessarily violating Stacked Borrows. &self grants shared-read-only access to a pointer, and the unique reference comes from the pointee, associating the lifetime with that of &self. Thus the methods are safe as long as the pointer is valid (aligned correctly, points to a valid object, has a valid tag according to SB, ...).
For example, Miri doesn't complain about the following code:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ade598b102dc0e595312339b482de677

I agree that the API can be error-prone though.

[carllerche]

Is there a bug in the LinkedList right now? Are there any bugs that need to fix?

If there is a soundness bug to fix, we should do that ASAP. It does not seem like there is though and this is more a discussion of how to tweak the internal API.

[Darksonn]

I haven't looked at this LinkedList before now, but I agree it looks pretty sketchy stacked-borrows wise.

[Darksonn]

This triggers UB according to miri:

use futures::future::FutureExt;
use tokio_util::sync::CancellationToken;

fn main() {
    let token = CancellationToken::new();
    let fut = token.cancelled();
    tokio::pin!(fut);
    
    fut.now_or_never();
}

[Darksonn]

This is almost a duplicate of #3399. It is possible to make a change in tokio-util similar to #4397 that will make miri stop complaining.

[thomcc]

At the moment it actually may no longer fail because miri currently opts to ignore aliasing violation in !Unpin types. This is probably just a workaround at the moment though, and may still be UB (presumably there are still some tules for these types, even if they may need to be looser). There’s a discussion in the miri channel on zulip which is currently going on about it, fwiw.

[Darksonn]

Closed by #4652, which completely removes the linked list in tokio-util.