Safely reading uninitialized memory

[canndrew]

So I just learned that there are algorithms that involve reading from uninitialized memory. See here for an example. It doesn’t seem like it’s possible to implement this data structure in Rust because reading uninitialized bytes is always undefined behaviour. Could we maybe add an intrinsic which “initializes” a &mut [u8] by setting it to arbitrary bytes? (This would in practice be a no-op).

I don’t have a particular need for this, I just hate to think that this cool little data structure is unimplementable in Rust for such an easily-fixable reason.

[Tom-Phinney]

It seems to me that this proposal would open a big security hole. If the sparse array is allocated on the heap, as seems likely, and that space formerly contained your credit card numbers and login username/password information for your various accounts, you’d probably be very unhappy that that information had just been exposed to the user whose program used this technique.

[sfackler]

@canndrew

reading uninitialized bytes is always undefined behaviour.

I don't think this is the case. The uninitialized bytes have an undefined value but that isn't the same as invoking undefined behavior.

[scottmcm]

@canndrew

It doesn’t seem like it’s possible to implement this data structure in Rust because reading uninitialized bytes is always undefined behaviour.

Hmm, so reading uninitialized values in LLVM isn't UB; it's undef (LLVM Language Reference Manual — LLVM 18.0.0git documentation). But that doesn't save you, I don't think. In the code from the paper,

is-member(i):
    return sparse[i] < n && dense[sparse[i]] == i

I think that if sparse[i] is potentially undef, so that whole expression can probably become undef, since the guard just becomes undef.

I think what you need is freeze, which has been talked about for LLVM but I don't think it exists yet.

[anp]

@sfackler looks like the API docs say it’s UB as does the reference.

[anp]

For the posted example, it seems like it would be possible to amortize the cost of initialization over all further operations, unless I’m missing something.

[canndrew]

@Tom-Phinney

It seems to me that this proposal would open a big security hole. If the sparse array is allocated on the heap, as seems likely, and that space formerly contained your credit card numbers and login username/password information for your various accounts, you’d probably be very unhappy that that information had just been exposed to the user whose program used this technique.

It's the responsibility of the code handling the password to zero the memory before deallocating it, otherwise another program could always read that memory even after your program has closed.

@sfackler

I don’t think this is the case. The uninitialized bytes have an undefined value but that isn’t the same as invoking undefined behavior.

It should be undefined behaviour. It's semantically simpler and gives more freedom to the optimizer that way.

[canndrew]

@anp

For the posted example, it seems like it would be possible to amortize the cost of initialization over all further operations, unless I’m missing something.

But "all further operations" may never end up touching all the memory you've allocated, or even necessarily come close.

[eternaleye]

@canndrew The problems of reading uninitialized memory are not something the compiler can just define away without runtime cost (initialization or special instructions), in general.

Some hardware, including Itanium, distinguishes uninitialized memory and considers reads of it invalid. This cannot be avoided without telling the hardware otherwise.

[mark-i-m]

@Tom-Phinney

It seems to me that this proposal would open a big security hole. If the sparse array is allocated on the heap, as seems likely, and that space formerly contained your credit card numbers and login username/password information for your various accounts, you’d probably be very unhappy that that information had just been exposed to the user whose program used this technique.

This is the job of the OS, not the language. For example, Linux kernel will zero out pages allocated for user space by default (see the mmap MAP_UNITIALIZED flag) unless you are on some embedded platforms with certain kernel compile-time configurations.

Rustc keeps track of initialization to avoid undefined behavior bugs -- a matter of memory safety, not security.

[Centril]

@eternaleye

Some hardware, including Itanium , distinguishes uninitialized memory and considers reads of it invalid. This cannot be avoided without telling the hardware otherwise.

I suppose this could be handled via #[target_features(..)] then?

[felix.s]

@canndrew

Could we maybe add an intrinsic which “initializes” a &mut [u8] by setting it to arbitrary bytes? (This would in practice be a no-op).

I think technically &mut T is supposed to point to an already-initialized T... this doesn't compile. You're thinking of &out T (or whatever else you call it), but we don't have that yet.

@mark-i-m

This is the job of the OS, not the language. For example, Linux kernel will zero out pages allocated for user space by default (see the mmap MAP_UNITIALIZED flag) unless you are on some embedded platforms with certain kernel compile-time configurations.

Who said that all allocations come directly from mmap? It's not unheard of to have, say, malloc work by putting memory obtained from sbrk in a heap managed by the C library, and reusing memory that was previously freed. I haven't looked how exactly memory allocation is done in Rust, but if it goes through a similar intermediary (and I believe it does), then taking care of deallocated sensitive data being inaccessible indeed becomes a job of the language.

[hanna-kruppe]

@sfackler

I don’t think this is the case. The uninitialized bytes have an undefined value but that isn’t the same as invoking undefined behavior.

AFAIK the unsafe code guidelines are anywhere near settled on this point, but making it UB is certainly the most conservative option. Besides, many reasonable notions of "undefined bytes" that allow some useful operations (e.g. memcpy such values) still behave weirdly if you try to do any sort of computations on it. For example, in LLVM every use of the undef is a different arbitrary byte pattern, and with the proposed poison, it's UB to branch on a value derived from poison (whereas with undef it would non-deterministically pick one branch). And this is not because LLVM is being antagonistic, giving stronger guarantees would severely curtail some desirable optimizations.

Trying to carve out a well-defined subset of operations on "undefined values" is fraught with issues, so it's prudent to make it UB.

Relatedly but distinct, something is needed to deal with padding bytes, but they could very well be special cased. Even though we certainly want to be able to initialize a struct by initializing each field separately (and thus leaving padding uninitialized), uninitialized bytes in padding could be treated differently from uninitialized bytes that are not padding.

[rpjohnst]

@felix.s

Who said that all allocations come directly from mmap? It’s not unheard of to have, say, malloc work by putting memory obtained from sbrk in a heap managed by the C library, and reusing memory that was previously freed.

That still doesn't allow freed memory values to cross processes. sbrk also zeros its pages.

What it does mean is that you should zero your own memory if you want to prevent something in the same process from reading it.

This is arguably still important (it's how Heartbleed worked) but it doesn't really apply to things like this algorithm.

[Tom-Phinney]

@felix.s

It’s not unheard of to have, say, malloc work by putting memory obtained from sbrk in a heap managed by the C library, and reusing memory that was previously freed. I haven’t looked how exactly memory allocation is done in Rust, but if it goes through a similar intermediary (and I believe it does), then taking care of deallocated sensitive data being inaccessible indeed becomes a job of the language.

This is precisely my concern. libstd/heap.rs contains four related memory deallocation/reallocation functions that each seem to have the potential to leak prior contents unless the released memory is overwritten as part of the release process. Here is the relevant code:

pub use alloc_system::System;
…
    #[no_mangle]
    #[rustc_std_internal_symbol]
    pub unsafe extern fn __rdl_dealloc(ptr: *mut u8,
                                       size: usize,
                                       align: usize) {
        System.dealloc(ptr, Layout::from_size_align_unchecked(size, align))
    }
…
    #[no_mangle]
    #[rustc_std_internal_symbol]
    pub unsafe extern fn __rdl_realloc(ptr: *mut u8,
                                       old_size: usize,
                                       old_align: usize,
                                       new_size: usize,
                                       new_align: usize,
                                       err: *mut u8) -> *mut u8 {
        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
        match System.realloc(ptr, old_layout, new_layout) {
            Ok(p) => p,
            Err(e) => {
                ptr::write(err as *mut AllocErr, e);
                0 as *mut u8
            }
        }
    }
…
    #[no_mangle]
    #[rustc_std_internal_symbol]
    pub unsafe extern fn __rdl_realloc_excess(ptr: *mut u8,
                                              old_size: usize,
                                              old_align: usize,
                                              new_size: usize,
                                              new_align: usize,
                                              excess: *mut usize,
                                              err: *mut u8) -> *mut u8 {
        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
        match System.realloc_excess(ptr, old_layout, new_layout) {
            Ok(p) => {
                *excess = p.1;
                p.0
            }
            Err(e) => {
                ptr::write(err as *mut AllocErr, e);
                0 as *mut u8
            }
        }
    }
…
    #[no_mangle]
    #[rustc_std_internal_symbol]
    pub unsafe extern fn __rdl_shrink_in_place(ptr: *mut u8,
                                               old_size: usize,
                                               old_align: usize,
                                               new_size: usize,
                                               new_align: usize) -> u8 {
        let old_layout = Layout::from_size_align_unchecked(old_size, old_align);
        let new_layout = Layout::from_size_align_unchecked(new_size, new_align);
        match System.shrink_in_place(ptr, old_layout, new_layout) {
            Ok(()) => 1,
            Err(_) => 0,
        }
    }
}

Replacing the standard underlying system allocator with a custom one that always block-overwrote released memory would be overkill. What seems desirable is some sort of indicator, perhaps via a new ZST, that specific structures (e.g., a specific vector containing sensitive information) should have its prior memory cleared whenever it is dropped or reallocated.

@rpjohnst

That still doesn’t allow freed memory values to cross processes.

I have been unable to find the code for alloc_system::System, and thus unable to convince myself that this would be true for all ports of Rust, particularly for embedded ports to the various SoCs used in IoT.

(As a reminder, do remember the oft-quoted joke,

"The S in IoT stands for security."

Current IoT practices are notoriously insecure.)

Edit: FWIW, I found Rust's two standard allocators, in liballoc_system/lib.rs and in liballoc_jemalloc/lib.rs.

[mark-i-m]

@felix.s

Who said that all allocations come directly from mmap? It’s not unheard of to have, say, malloc work by putting memory obtained from sbrk in a heap managed by the C library, and reusing memory that was previously freed.

sbrk is mmap on Linux... but I do see the point that the heap may reuse data. My perspective was that of protecting one process from another, which is the kernel's job, so I missed that point

[josh]

Couldn’t this just use mem::uninitialized?

[scottmcm]

But that’s just undef, so the problems I mentioned above apply, AFAIK.

[areilly]

Just to play devils-advocate in the hope of learning something: Why wouldn’t a sufficiently-aware compiler see writing zeros to memory that is immediately freed as unused values, which it was free to optimize away? With a side order of: (does any compiler actually do that?) How could you tell? It’s not something that you can write a test-case for.

[hanna-kruppe]

This indeed happens and is a real problem in practice (https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/yang). But it’s (edit:) not impossible to solve this.