implement intptrcast model

Since right now miri's pointer comparison bails out on &x as *const T < &y as *const T but allows &x as *const T == &y as *const T, I suggest to also allow <. This will not impact ctfe-mode, since ctfe mode disallows any binary ops on pointers into different allocs, even ==.

It's deterministic between multiple miri runs, doesn't leak HashMap ordering and only depends on optimizations and codegen from rustc (but that's already true for ==).

Steps to do:

Implement force_bits, force_int and basic address assignment.
force_bits when doing primitive operations.
force_bits when doing casts.
force_ptr when creating a non-ZST reference. (Ideally through check_ptr_access? Redundant with validity checks but whatever.) We may need a force_ptr_place method or so; the freeze-sensitive visitor also needs that.
Make force_bits infallible (in Miri, not CTFE) -- see Make force_ptr a total operation, and ptr-to-int-casts not require extra machine state #841.
force_bits when doing partial loads of a pointer -- and really everywhere we need a ptr, once it is total. (For now let's not do this, also see const-eval: load of partially initialized scalar produces entirely uninitialized result rust#69488 for a similar problem around partially initialized data.)
Exploit "real" pointer alignment for alignment checks, but warn when we do. (But also see align_offset guarantees rust#62420.)
Ptr-to-int of a dangling pointer (possible in safe code).
Fix the FIXMEs added in Add tests for Intptrcast when doing explicit casts #803.
Audit all remaining uses of to_bits (this includes the to_<int type> methods...), to_ptr and to_bits_or_ptr, all uses of is_ptr and is_bits, and also all uses of force_ptr and force_mplace_ptr (also mplace_access_checked, check_mplace_access) outside of check_ptr_access. Maybe replace to_{bits,ptr} by assert_{bits,ptr}?

My plan was to go even further and essentially implement the intptrcast-model. That would immediately make us support all pointer arithmetic.

Essentially, I think at some point miri should (in non-CTFE mode!) guarantee that safe Rust code can not error out (if the unsafe libraries it uses don't contain bugs). So hashing raw pointers and printing them and stuff like that all have to work.

Sounds reasonable to me. Once a pointer has been observed and thus it's integral representation is available, there's no way in safe code to go from that pointer back to the allocation, so we don't even need to support that direction, right? All we need to ensure is hat the integral representation doesn't change when obtaining it multiple times from a real pointer

We'll also need to generate an integer address when offsetting pointers due to overflow concerns. Overflowing exposes the address essentially.

We'll also need to generate an integer address when offsetting pointers due to overflow concerns. Overflowing exposes the address essentially.

That's only true when you do the offsetting after casting to integer though, is it? The offset operations on pointers don't let safe code observe whether an overflow actually happened. Really, we could just generate an integer address immediately on allocation.

Doing lookup on a Pointer is still more efficient, so that may be a reason to convert back.

Well... You can do wrapping_offset (safe and stable method), and then do a <= comparison between the resulting pointer and the new one.

let x = 5;
for i in 1.. {
    let ptr = &x as *const i32;
    let ptr2 = ptr.wrapping_offset(i);
    if ptr2 <= ptr {
        println!("Address of `x` is {}", std::usize::max_value() - i);
    }
}

Really, we could just generate an integer address immediately on allocation.

We'd run out of integer addresses eventually (and quickly on 32bit emulation) if we don't reuse integer addresses and create a unique integer address for every allocation.

Heh, nice catch.

We'd run out of integer addresses eventually (and quickly on 32bit emulation) if we don't reuse integer addresses and create a unique integer address for every allocation.

"Quickly"? 2^32 is still a large number, I feel.^^
But anyway, I guess there's no problem with lazy allocation. That also gives us a nice single point of control for rejecting everything that could potentially leak the base address when in CTFE mode -- we just always make the allocation of an integer address fail in that mode.

The problem is, that once you leak the base address of an array, you also leak the address of the last element's last byte. So allocatingand deallocating 100MB 50 times would fill the address space unless we allow reusing it.

Actually, given what I wrote in https://internals.rust-lang.org/t/types-as-contracts/5562/81, I think it would make sense for miri to both support pointer comparisons on "abstract" pointers and only provide intptrcast optionally. Without intptrcast, there will always be safe code that miri cannot run (like printing the value of a pointer), but currently there still seems to be value in also having a mode that keeps pointers and integers more separate.

This code currently fails on miri:

fn main() {
    let x: Vec<u32> = Vec::new();
    &x == &[];
}

error[E0080]: constant evaluation error: attempted to do invalid arithmetic on pointers that would leak base addresses, e.g., comparing pointers into different allocations
    --> /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/slice/mod.rs:5024:12
     |
5024 |         if self.as_ptr() == other.as_ptr() {
     |            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ attempted to do invalid arithmetic on pointers that would leak base addresses, e.g., comparing pointers into different allocations
     |
     = note: inside call to `<[A] as core::slice::SlicePartialEq<A>><u32>::equal` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/slice/mod.rs:4962:9
     = note: inside call to `core::slice::<impl std::cmp::PartialEq<[B]> for [A]><u32, u32>::eq` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/liballoc/vec.rs:2069:50
     = note: inside call to `<std::vec::Vec<A> as std::cmp::PartialEq<[B; _]>><u32, u32>::eq` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libcore/cmp.rs:1009:48
note: inside call to `std::cmp::impls::<impl std::cmp::PartialEq<&'b B> for &'a A><std::vec::Vec<u32>, [u32; 0]>::eq` at src/main.rs:3:5
    --> src/main.rs:3:5
     |
3    |     &x == &[];
     |     ^^^^^^^^^
     = note: inside call to `main` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:64:34

Blocked on #653

cc @christianpoveda

Basic (meaning probably incomplete) implementation instructions:

add a fn int_to_ptr(&self, ptr: Scalar) -> InterpResult<'tcx, Pointer> method to Machine (in rustc). This function should have a default impl that matches on Scalar, returns the Pointer if it's the Ptr variant and returns the ReadBytesAsPointer error variant otherwise
find all current sites where ReadBytesAsPointer is being emitted and call M::int_to_ptr(self, scalar) at said sites instead of emitting the error.
Do the same trick for ReadPointerAsBytes (but name the newly added method ptr_to_int(&self, ptr: Pointer) -> InterpResult<'tcx, Scalar> and fully ignore the argument and just emit the error variant)
Up to now, there should be zero change in behaviour by const eval or miri
go back to miri, all further changes should be doable completely within miri
add a FxHashMap<AllocId, u64> to

miri/src/lib.rs

Line 324 in 3c930e4

pub struct Evaluator<'tcx> {

which should then be used in the implementation of Machine::ptr_to_int inside miri
add a u64 to Evaluator, which is the current number of bytes used up by the intptr "memory".
whenever there's no entry in the FxHashMap during ptr_to_int, do name_of_the_hash_map.insert(ptr.alloc_id, name_of_the_u64);, compute name_of_the_u64 + ptr.offset in a variable, add memory.get(id).bytes.len() to the u64, and return a new Scalar created from the u64 + offset` variable. This will allow us to go the one way and do it deterministically
for the other direction, you need another field in the Evaluator, this time to go from an integer to an AllocId (so the inverse of the other map). But since we may have added integers to the base address, you can't just compute the inverse map as that would not have entries for every single pointer. Instead we need something like a BTreeMap<u64, AllocId> (which also needs to be filled in in ptr_to_int). Unfortunately BTreeMap doesn't quite support our use case. What we want to find is the entry which our integer points into. So I guess we go with a Vec<(u64, AllocId)> and do a binary search on it, which should be just as fast for finding elements as searching in a BTreeMap.
add an if self.seed.is_none() { return err!(...); } to both of the methods to make sure we only do this behavior in nondeterministic mode.

Ok I'll start working on this :D

i'll be working on this branch: https://github.com/christianpoveda/rust/tree/intptrcast-model

Auto merge of #779 - christianpoveda:intptrcast-model, r=RalfJung,oli…

Some discussion between eddyb and me about miri and threads came to the conclusion that for certain kind of checks it would be helpful to only have the intptrcast part where you can go from ptr to int, but not the other way. I believe that would even cover most real use cases, as I've only seen the other direction in artificial examples so far

I don't understand what you even mean by that. Could you give some concrete examples of programs we should not support and why?

Also see this Zulip discussion.

well, basically I want to forbid (on 64 bit)

union Foo {
    a: (u32, u32),
    b: usize,
}
let (x, y) = Foo { b: &1 as *const i32 as usize }.a;
let ptr = ((x as usize) << 32) | (y as usize);
let ptr = *(ptr as *const i32);

or any other bit modifying operations beyond those below the alignment (so those that will happen on the integer representation instead of on the abstract representation).

You can do these reading operations, so you can print all bits of a pointer, I just want to forbid int2ptr everywhere.

I'd rather get rid of all the code that performs arithmetic on the Pointer representation. That code is a mess.

Why don't you want to allow that code? I do want to forbid this code which is why I added a test for this, but yours seems fine to me.

Why don't you want to allow that code?

Essentially to be able to do full thread separation via our symbolic pointers. I want to be able to leverage the knowledge about what is accessible where. If we have integer pointers, that becomes impossible.

I'm afraid you will have to tell me more, I still don't know what this is all about.^^

Can you open a new issue for this specific restriction, and describe in more detail the why and how? My plan is to close this one once everything works.

I should probably put a checklist in the first comment here for what is still on @christianpoveda's TODO list. ;)

Plz do

Done. :)

Turns out instead of calling force_ptr in Ref, we can have the invariant that places are actually "normalized" to Pointer on Deref, which happens in rust-lang/rust#63075. So that checkbox is also taken care of.

Auto merge of #1851 - RalfJung:provenance-overhaul, r=RalfJung

Navigation Menu

Repository navigation

implement intptrcast model #224

20 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

implement intptrcast model #224

Description

Activity

RalfJung commented on Jun 28, 2017

oli-obk commented on Jun 29, 2017

RalfJung commented on Jun 29, 2017

oli-obk commented on Jun 30, 2017

RalfJung commented on Jul 3, 2017

oli-obk commented on Jul 3, 2017

RalfJung commented on Aug 4, 2017

Amanieu commented on Feb 6, 2019

RalfJung commented on Mar 8, 2019

oli-obk commented on May 27, 2019

pvdrz commented on May 27, 2019

20 remaining items

oli-obk commented on Jun 28, 2019

RalfJung commented on Jun 28, 2019

oli-obk commented on Jun 28, 2019

RalfJung commented on Jun 28, 2019

oli-obk commented on Jun 28, 2019

RalfJung commented on Jun 28, 2019

pvdrz commented on Jun 28, 2019

RalfJung commented on Jun 28, 2019

RalfJung commented on Jul 28, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions