Is it possible to read uninitialized memory without invoking UB?

help
1

This question is minor practical import, but it has been bugging me for a while so I decided to ask.

Is it possible to write the following program in Rust without UV ruining everything?

use std::mem::MaybeUninit;

fn main() {
    let page: [MaybeUninit<u8>; 4*1024] = Box::new(); // doesn't compile but you get the idea
    assert!(page.assume_init().iter().sum(), 0); // definitely UB
}

The motivation for the above code was that I wanted to write code to verify that the OS is giving zeroed pages, but couldn't figure out how to write such code in Rust or C that doesn't invoke all the UB.

Would I have to write that program in assembly?

2 Likes
2

AFAIU one option is to use black_box function between these two lines of code. Compiler does not know what happens across black_box invocation, so it won't do any UB-dependent optimizations.

3

I think it's fundamentally UB in the abstract machine, because if you get back uninit memory, branching on any sort of comparison against that uninit memory is UB, and that's what you have to do to run the test. (There are ways to demote it from UB to "arbitrary value", but that doesn't help you since it'd plausibly pick 0 for the arbitrary value.)

You probably need to drop to a different level where the semantics are defined. Perhaps with inline assembly you can do it, assuming you're on a target where memory itself cannot be uninit.

6 Likes
4

Thanks for the tip. That is an interesting function and would probably make the code run correctly.

I am more looking for a long term solution that wouldn't count on the compiler being too dumb to catch me out. The documentation for that function explicitly doesn't prevent optimizations based on UB.

5

I suspected as much and am posting this as a last ditch effort for ideas.

I checked out the asm guide and it looks like while I could make a bit of asm that makes the compiler think I have written to the array, it would be similar to the black box trick @stepancheg mentioned above.

6

In C at least I do not think that this code has UB:

#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>

int
main()
{
    const long pgsize = sysconf(_SC_PAGE_SIZE);
    char *m = mmap(NULL, pgsize, PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    assert (m != MAP_FAILED);
    for (char *p = m; p < m + pgsize; p++)
        assert(*p == 0);
    printf("ok\n");
}

I'm sure there's a way to translate this to Rust, perhaps like it was explained to me in an earlier post about assume_init().

PS: or perhaps not with MaybeUninit since you can't construct one and point to existing memory.
But it must be possible to do so with raw pointers.

7

Box is from the allocator, and most allocators will reuse memory without zeroing for better performance.

The allocator will call the OS for more memory, on linux that's typically via mmap, but very old ones may use brk/sbrk.

If you want to test the OS, you would call mmap directly. Which should zero pages to ensure cross process security.

You maybe able to switch to or configure the allocator to zero pages. But if you want to make sure secretes don't leak via memory reuse, then you should consider something like the zeroize - Rust crate. Which zeros things when dropping, which is a bit subtle to get right since it looks like pointless work by the optimizer.

1 Like
8

As far as I know, if something is or becomes uninitialized, both the optimizers and the abstract machine consider it to stay that way until written to or frozen. And I also assume that the optimizer is free to fill it with garbage (for example) in the meanwhile (e.g. before you froze it).

So you would want something like an allocation function that returns defined (fixed, but not necessarily known) bytes. As far as I know, that doesn't exist. (E.g. LLVM and Rust both consider just-allocated memory to be full of undefined or poison values.)

Moreover, it might be harder to achieve than you think. Consider MADV_FREE as discussed in this thread; in short, uninitialized pages may change between reads given certain OS + allocator combinations.

1 Like
9

I don't think it's a matter of age, but depends on the size of the allocation.
At least the allocator that's used when I compile something with Rust 1.54.0 on my Ubuntu 18.04 box uses the traditional approach and appears to maintain a traditional heap with brk() from which to satisfy small allocations. Run this program under strace:

fn main()
{
    let mut v : Vec<Vec<f64>> = vec![];
    for _i in 0..100 {
        let a: Vec<f64> = (0..10000).map(|n| n as f64).collect();
        v.push(a);
    }
}

and I see:

brk(0x55dec76ac000)                     = 0x55dec76ac000
brk(0x55dec76d3000)                     = 0x55dec76d3000
brk(0x55dec76fa000)                     = 0x55dec76fa000
brk(0x55dec7721000)                     = 0x55dec7721000
...
10

I guess you can do it with a volatile read, using for example volatile - Rust

I'm unsure if this is UB, but would expect so

11

Quoting @RalfJung a few months ago:

This is why Rust has so far avoided to introduce non-determinism in this area; instead doing anything that might leak the contents of uninit memory is UB. Making this UB makes these issues easier to diagnose as it means any computation on uninit data is definitely wrong and can be flagged (by the compiler when detected statically, by Miri/valgrind/... when detected dynamically). If we allowed computing on uninit data, then it would become much harder to detect accidental cases of computing on uninit data.

So any native solution that happens to work is UB (unless some day an "allocate frozen bytes" method arises).

4 Likes
12

That was a big one I missed. There's a lot of tricks the other allocators do with mmap like releasing memory back to the OS and tricks with page aligned blocks, so I wonder if the system one is lacking some features sue to that. I've been using jemalloc since it made one production system many times faster than the Ubuntu 14.04 allocator. I think the newer system allocators are better at multithreaded now

13

Using black_box or volatile reads is both UB. You can't do it.

That said, if you are using a memory allocation method that guarantees that the memory is zeroed such as alloc_zeroed, then reading that memory is not UB as it isn't uninitialized. It's initialized to zero.

3 Likes
14

This is the real answer. Calling mmap directly from your code means you're dealing with the semantics of the syscalls, not the Rust abstract machine.

15

If you're calling it from Rust, you're playing by Rust's rules. Bypassing libstd doesn't change any of the UB rules.

1 Like
16

If the syscall guarantees that the memory is zeroed, then it's safe to access it. If the syscall says that the memory is uninitialized, then its UB to do so.

2 Likes
17

Fascinating question! To answer it directly: no, if the memory is uninitialized, reading it is UB.

But I think your underlying question cuts much deeper. "uninitialized" is a concept of the abstract machine, but syscalls exist outside of that. So the question can be reformulated: how syscalls (and mmap) in particular, interact with the abstract machine.

The following is my understanding, it's not necessary correct.

Here's an non-exhaustive list of things an evil/buggy OS can do when ask to map and zero-init a page of memory:

  • give you a zeroed page of memory
  • give you a page of memory with some existing data
  • give you a zerod page of memory, but, after 10 milliseconds, change the mind and remap this virtual page to a different page. Alternatively, OS could overwrite the contents of the page in place
  • give you a page of memory, which aliases some existing page (eg the one containing call stack)

To plug that into abstract machine, we need to make sure that semantics of the syscall corresponds to AM's understanding of what memory is. And that I think roughly is:

  • if you read a byte from address, you'll read the same byte later
  • if you write a byte to address, you'll read the same byte later
  • memory is not aliased -- writes/reads from any address affect only the contests of this address, and, conversely, they are the only operations that affect the contents of the address.

If what you get out of mmap fulfills those properties, then you can treat is as memory. In particular (provided a correct implementation of mmap), the following program is correct:

  1. Select "zero out" flag at runtime at random
  2. mmap a new page which might, or might be not, zero
  3. assert that the page is zero (this will panic, but will not be UB)

That is, even non-zeroing unmap is guaranteed to return a distinct memory which holds some value and won't change from under your feet. This is in contrast to, eg, uninitialized local variables, whose storage (while they are uninitialized) might be used by the compiler as a scratch space.

That's the core difference -- if the compiler knows that the stuff is uninitialized, it can play tricks. When you call random extenal C function/syscacll that "returns memory", compiler can't assume that it is uninitialized. If you call raw mmap, that's what happens: there's nothing telling the compiler that the newly returned memory can be used as a scratch space.

In contrast, if you call language own memory allocation function (alloc::alloc), that can be an explicit part of the abstract machine. Compiler is allowed to know that the returned value is allocated, but uninitialized memory, and can optimize based on that.

Finally, you don't have to treat the result of mmap as memory. Consider a program which probabilistically maps a page to a physical memory, or to a random device which returns random values for loads. For such program,

let mut p: *const u8 = lo;
while p < hi {
    let byte = *p;
    assert!(p == 0);
    p += 1;
}

would be UB. Random device is not memory, and it breaks compiler's assumption that reads always return the same value.

Instead, you can treat the addresses as non-memory, using volatile reads:

    let byte = core::ptr::read_volatile(p);

With volatile, this won't be UB.

Practically, I'd just memzero the memory if I don't trust the OS. debug-assert loop would be fine as well.

5 Likes
18

I don't think that's true if mmap is called directly (as opposed to via Rust's global allocator). From compiler's perspective, there's no difference between a mmap and a read, and we definitely allow to assume that read initializes the memory. As far as I know, there's nothing that says that mmaped memory is more uninitialized than the memory returned by read. This is under the assumption that mmap returns "normal" memory (so, no MADV_FREE).

1 Like
19

The next version of POSIX will standardize MAP_ANONYMOUS. It was proposed in 2014 and accepted in 2020 and will read:

Anonymous memory objects shall be initialized to all bits zero.

This will standardize a long standing practice.

The memory returned by brk, which is not part of POSIX but a legacy call, is guaranteed to be zero only the first time, but not on subsequent times

The newly-allocated space is set to 0. However, if the application first decrements and then increments the break value, the contents of the reallocated space are unspecified.

although in practice it's likely to be either zero or contain data previously owned by the process (otherwise it would be considered a security hole).

1 Like
20

I think this gets to why I mentioned "in the abstract machine". In the abstract machine, where "uninit" is a possible value of anything, there's no way to test for it.

Whereas the argument you're making is more from the direction of "well, it'd be impractical for the compiler to emit something other than what you want". Which might be true (and probably is today, with "normal" memory) but doesn't keep it from being UB in the abstract machine.

1 Like