[adwn]

> abusing a vector in this way is not a safe interface and is instead a good way to introduce several memory safety bugs (for example, UAFs)

No, as long as you don't use the unsafe keyword, an out-of-bounds vector access won't lead to use-after-free or other memory safety bugs.

[Arnavion]

Out-of-bounds access is not required for the pseudo-UAF we're talking about here. Deleting a node in the middle of a linked list will leave a "hole" in the backing Vec. You cannot shift the next elements down to fill the hole because that will invalidate all handles to them. If the backing Vec holds the nodes directly, as TFA's implementation does, then there is no way to mark the hole as a hole. So any bug where a different node's handle accidentally ends up accessing this hole instead will lead to that code observing a "freed" node.

One workaround is to make the backing Vec hold Option of Node instead so that deleting a node can set the hole to None, in which case the bug I described above has the opportunity to unwrap() and panic instead of silent UAF. Though you'll also need additional tracking for those holes so that you can fill them with new nodes later, at which point you'd be better off using a proper freelist / slab instead of a Vec anyway (as TFA also mentions).

[kelnos]

Well, we're not talking about "pseudo-UAF", we're talking about actual-UAF and actual-memory-safety.

You use scare quotes around "freed" for a reason: the data has not actually been freed.

The bug you're talking about is a logic error. It could be a bad bug, depending on circumstances, but there's no memory safety issue here.

[Arnavion]

>You use scare quotes around "freed" for a reason: the data has not actually been freed.

Who said it hasn't? I would assume such a node to have been given to `std::ptr::drop_in_place`. Not doing that would be a leak until the list as a whole was dropped.

[cmeacham98]

I don't mean a literal UAF, but a "use array index after free" because you're using indexes (which only have bounds checking) as heap pointers.

Rust's borrow checker doesn't account for when you re-implement parts of memory management as array indexes.

[im3w1l]

Safe rust is a turing complete language. That implies that it is possible to build an emulator for any other programming language in safe rust. That emulated language and programs running on it can have memory-safety issues, even if the emulator itself cannot be corrupted.

When writing such an emulator the natural way to set up the memory is to use an array, and the natural way to implement pointers is indices into that array. In other words, this pattern is part-ways there to creating an emulator with internal safety issues.

However guaranteeing that any corruption will be contained to the array is certainly a lot better than nothing.

[Chabsff]

Rust's safety mechanisms don't exist just to prevent bugs from escalating into security issues, they exist to prevent the whole class of bugs related to reference handling from being present in the first place. That's supposed to mean programs that work more consistently. Handwaving techniques that lead to programs panicking as "Well at least it doesn't become a security concern" is missing the forest for the trees.

[potatochup]

This is generally true, but afaik there are still some (fairly complex) ways to write memory unsafe code in safe rust https://faultlore.com/blah/everyone-poops/

[mandarax8]

How is reusing a freed index not a UAF? If I roll my own allocator I can still get UAFs even though the memory accessed is not yet free'd.

[kelnos]

Because that's not what "UAF" means. Also not what "freed" means.

To have a UAF, there has to be memory that is actually freed, and you have to attempt to access that memory. No memory is freed here (in the OP's implementation). Even if it was, at worst you'd get a panic for trying to access past the end of the Vec.

None of that is a UAF or a memory safety issue. It's just a logic bug.

[amichal]

Nope but "handle confusion" safety perhpas?