False positive when int-to-ptr "confuses" which allocation (provenance) to use for new ptr

[niluxv]

Miri accepts dereferencing a (fat) pointer to a slice of ZSTs, except when the pointer to the slice lies in a previously freed allocation.

Example 1 (fresh dangling pointer, succeeds):

fn main() {
    // create fresh dangling ptr `ptr`
    let ptr: *const () = std::ptr::NonNull::<()>::dangling().as_ptr();
    let slice_ptr: *const [()] = std::ptr::slice_from_raw_parts(ptr, 1);
    let slice_ref: &[()] = unsafe { &*slice_ptr } ;
}

playground

Example 2 (pointer to freed allocation, errors):

fn main() {
    let vec: Vec<u8> = vec![1, 2, 3];
    let vec_ptr: *const u8 = vec.as_ptr();
    drop(vec);
    // now `vec_ptr` is dangling, and we create a dangling `ptr` from it
    let ptr: *const () = vec_ptr as *const ();
    let slice_ptr: *const [()] = std::ptr::slice_from_raw_parts(ptr, 1);
    let slice_ref: &[()] = unsafe { &*slice_ptr } ; // ERROR
    // error: Undefined Behavior: pointer to alloc1414 was dereferenced after this allocation got freed
}

playground

But soundness of code does not depend on previous allocations (I hope); in both cases ptr is 'just' a *const () dangling non-null pointer. Therefore either both examples are unsound/UB, or both are sound.

(I think both examples are sound, so that this is a false positive. At least the entire bitvec crate seems to be build around the idea that this is sound. Issue #135 in bitvec an example of this issue in the wild.)

[RalfJung]

Thanks for the report!

This is surprising, but deliberate. See for example here

Even for operations of size zero, the pointer must not be pointing to deallocated memory, i.e., deallocation makes pointers invalid even for zero-sized operations. However, casting any non-zero integer literal to a pointer is valid for zero-sized accesses, even if some memory happens to exist at that address and gets deallocated. This corresponds to writing your own allocator: allocating zero-sized objects is not very hard. The canonical way to obtain a pointer that is valid for zero-sized accesses is NonNull::dangling.

I would love to change this, but LLVM currently won't let me -- see rust-lang/unsafe-code-guidelines#299 and rust-lang/unsafe-code-guidelines#93. I hope some day we can convince LLVM to adjust its spec so that we can make Rust have more reasonable behavior.

So, closing as "Miri works according to its spec; the spec might be strange but that's a separate and complicated problem".

[niluxv]

Interesting, I didn't know that. Working with ZSTs is even trickier than I thought!

But there still seems to be a problem. The documentation you linked says

However, casting any non-zero integer literal to a pointer is valid for zero-sized accesses, even if some memory happens to exist at that address and gets deallocated.

But miri errors on the following example (which is sound by the previous citation):

fn main() {
    let vec: Vec<u8> = vec![1, 2, 3];
    drop(vec);
    let zst_ptr: *const () = 165000 as *const ();
    let zst_ref: &() = unsafe { &*zst_ptr } ; // ERROR
    // error: Undefined Behavior: pointer to alloc1415 was dereferenced after this allocation got freed
}

playground

[RalfJung]

Hm... yeah that's a nasty example. :/ (It becomes even more nasty if you move the drop down by one line.)

165000 happens to be inside a former allocation so Miri "confuses" the pointers. We might need a much more complicated model of provenance to more precisely describe this. OTOH that would be a huge waste of effort if we can convince LLVM to slightly adjust their spec.^^

I'll reopen this because the "pointer confusion" parts is more of a Miri issue than a spec issue (though writing a precise spec that avoids this problem is on its own a hard problem).

[tavianator]

Here is a reproducer of what I think is happening in the bitvec tests.

$ cat foo.rs
fn foo() -> u64 {
    0
}

fn main() {
    for _ in 0..1024 {
        let n = 0u64;
        let ptr: *const u64 = &n;
        foo();
        let iptr = ptr as usize;
        unsafe {
            let start = &*std::ptr::slice_from_raw_parts(iptr as *const (), 1);
            let end = &*std::ptr::slice_from_raw_parts((iptr + 8) as *const (), 1);
            assert_eq!(start.len(), end.len());
        }
    }
}
$ ./miri run foo.rs
error: Undefined Behavior: pointer to alloc2000 was dereferenced after this allocation got freed
  --> ./foo.rs:13:23
   |
13 |             let end = &*std::ptr::slice_from_raw_parts((iptr + 8) as *const (), 1);
   |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pointer to alloc2000 was dereferenced after this allocation got freed

Basically we try to create a ZST slice at the very end of an allocation (&iptr + 8). But sometimes that's the start of another allocation that's already deallocated. ptr_from_addr() will find the start of the dead alloc rather than the end of the live one. The loop is just to try for a zero-slack allocation.

This patch might be too simplistic but it fixes it:

diff --git a/src/intptrcast.rs b/src/intptrcast.rs
index 665a1341..c61b3675 100644
--- a/src/intptrcast.rs
+++ b/src/intptrcast.rs
@@ -92,7 +92,7 @@ impl<'mir, 'tcx> GlobalState {
                 let slack = {
                     let mut rng = memory.extra.rng.borrow_mut();
                     // This means that `(global_state.next_base_addr + slack) % 16` is uniformly distributed.
-                    rng.gen_range(0..16)
+                    rng.gen_range(1..16)
                 };
                 // From next_base_addr + slack, round up to adjust for alignment.
                 let base_addr = global_state.next_base_addr.checked_add(slack).unwrap();

[RalfJung]

Ah, integer-pointer-casts and one-past-the-end pointers... fun, fun, fun...

I don't have a proper fix for this. Your patch avoids the problem by simply never having allocations touch so you need more than just-at-the-edge pointers to cause issues, you need to go OOB for real. In principle there will still be correct programs that this rejects but they are much less likely. Though instead of changing slack, we should change this to always add size+1 when computing next_base_addr.

However, I am also curious why the code is going through an integer in the first place. Is there no way to preserve the original provenance by keeping things at pointer type?

Ptr-to-int casts are evil and should be avoided at all cost. ;) Well actually I am only half-joking... they do require the operational semantics to "guess" a provenance, and I am not sure if there is a right answer here. An operation like this is much more well-behaved since it avoids the guessing:

// Converts 'addr' to a pointer using the provenance of 'prov'.
fn int_to_ptr_with_provenance<T>(addr: usize, prov: *const T) -> *const T {
  let ptr = prov.cast::<u8>();
  ptr.wrapping_add(addr.wrapping_sub(ptr as usize)).cast()
}

[tavianator]

The bitvec implementation uses the trailing bits of aligned pointers to store some extra information. This necessitates bit operations on pointers. It's possible that the provenance could be preserved through those operations but I'm not familiar enough with the bitvec code to ensure that.

[RalfJung]

In theory, what could be done is to do the bitops on usize but then cast back to a ptr using int_to_ptr_with_provenance to get a ptr with the encoded extra information and the original provenance. Then you never have to use <int> as <ptr>, avoiding all these nasty problems. Whether that actually works well in practice I do not know. ;)

[RalfJung]

I created rust-lang/unsafe-code-guidelines#313 for the underlying problem here.

[niluxv]

Edit: as pointed out in the comment below this comment was wrong

@tavianator Hm, I was thinking of the following explanation for `bitvec`s test failures under miri (but when reconsidering the probability that this occurs really should be negligible): In `bitvec::ptr::span::BitSpan` there is this function: ```rust pub(crate) fn to_bitslice_ref<'a>(self) -> &'a BitSlice { unsafe { &*self.to_bitslice_ptr() } } ``` (it is crate local but ends up being called all over the place) which creates something which should function as a 'reference to a bit in a bitvector/bitarray'. What is important: - `BitSlice` is a ZST - `self.to_bitslice_ptr()` returns a pointer that doesn't directly point into the allocation where the bits are stored; instead it uses a pointer which is essentially computed like this: `ptr_data | ptr_head`, where `ptr_data` is the real pointer and `ptr_head` codes the bit index (inside the byte) in the high bits (head) of the pointer (it is a [tagged pointer](https://en.wikipedia.org/wiki/Tagged_pointer)) - dereferencing `self.to_bitslice_ptr()` (or casting this raw ptr to a reference) is fine as long as this part of the address space is never used for allocations (EDIT: well, fine is too big a word; I don't think the current UB rules say that this is fine, but `miri` at least doesn't complain in this case) - on 64 bit systems the high bits of addresses are never used, as the address space doesn't span the entire 2^{64} possible addresses (IIUC), so this assumption should hold in practise (on 64-bit machines) - miri is platform independent and can freely use the entire address space of 2^{64} addresses, so it is possible that the memory at the `self.to_bitslice_ptr()` address has been part of an allocation, which is now deallocated

@RalfJung
I don't think a int_to_ptr_with_provenance would work here because there is no source of correct provenance for the tagged pointer.

[tavianator]

@niluxv The BitSpan type already contains a pointer. It is that pointer that needs the correct provenance. That pointer is created here, and doing int_to_ptr_with_provenance(ptr_data | ptr_head, addr.to_const()) instead does fix the errors reported by Miri. I'm not sure that's the only int->ptr cast that needs to be adjusted, but it's the main one.

The pointer tagging scheme used by bitvec is described here. It is the low bits that are used for tag data, the high bits come from the actual pointer to a live allocation so it should be safe.

[niluxv]

Oops, yes. I should have looked up the precise encoding again.

[RalfJung]

That pointer is created here, and doing int_to_ptr_with_provenance(ptr_data | ptr_head, addr.to_const()) instead does fix the errors reported by Miri.

Nice. :)
Indeed the idea is that when you have data that might have provenance, you should use a pointer type to store it -- even if the pointer is dangling (since the data is not a plain pointer but somewhat modified). This approach probably doesn't always work, and it wouldn't work in C with its strict rules on pointers always being inbounds, but in Rust it works well and it can maintain provenance with our current set of language primitives and no special new rules for how provenance behaves.

[the8472]

The bitvec implementation uses the trailing bits of aligned pointers to store some extra information. This necessitates bit operations on pointers.

Wouldn't it be possible to use a *const () + PhantomData instead so that the pointer is u8-aligned which allows you to manipulate all bits as needed via ptr.offset?
It's practically the same as int_to_ptr_with_provenance but perhaps more readable.