There is a theoretical data structure that uses arbitrarily initialized memory and can be used for hash tables: Using Uninitialized Memory for Fun and Profit.
Which may expose you to a side channel attack.
See here for an ancient RFC that lays out the problems with freeze
:
The RFC was not accepted, so no decision has been made either way, but maybe this helps explain why freeze
is a non-trivial language extension that deserves thorough consideration.
This argues against making it a safe method. But how about making it an unsafe
method? It could still be useful.
That means we'd have to change the requirements for sound unsafe code from "must not cause UB" to "must not cause UB nor expose the contents of uninitialized memory". After years of repeating that unsafe
is about UB and UB only, this seems like a non-trivial communication challenge. And it's not just about communication and community norms: for instance, I don't think Miri could ever help you find a problem like this; "not expose contents of uninitialized memory" is a form of non-interference and cannot be tested on a single program execution.
I think at best we could make this a soft requirement, and encourage people to document clearly when their safe API can leak uninitialized memory contents. Hopefully this will be enough.
I think I agree with @RalfJung here. In my concept, if arbitrary()
produces a value N
, the output of the program must be indistinguishable from a program in which you had supplied N
yourself. Hence if arbitrary()
is considered unsafe then any variable assignment is unsafe, which is clearly absurd. It seems like mandating unsafe
here has more of a psychological goal: "make sure you know what you're doing" (sort of like React's dangerouslySetInnerHTML
). Of course I agree that it's reasonable to ask people to be careful with uninitialized memory but locking it behind unsafe
could be the wrong way to go about it.
Doesn't that contradict the core argument in the RFC you linked to? It's arguing precisely for that policy -- that sound unsafe code must not expose the contents of uninitialized memory:
While we do not have a formal spec/contract for unsafe code, this RFC will serve to set an explicit policy that:
Uninitialized memory can never be exposed in safe Rust, even when it would not lead to undefined behavior.
Like other aspects of the definition of "safe Rust", this is part of the contract that all unsafe code must abide by, whether part of
std
or external libraries or applications.
Since it's not the policy, how about just doing it by naming convention or documentation warnings? freeze_dangerous
.
Indeed, the way the RFC proposes to phrase this suggests to add a non-UB requirement to unsafe
. Fair point, it's been so long since I read the RFC that I had forgotten about that.
The way that we have so far realized the intent of the RFC is to just make this UB, and have it be covered by the usual no-UB requirement. Over the 10 years since the RFC was written, the stance that unsafe
is exclusively used for soundness/UB has been solidified -- I don't know if that was even already explicitly expressed back then (IIRC, the first time this came up was around the question of whether mem::forget
should remain unsafe after Leakpocalypse made memory leaks safe).
I think I may have crammed too many words into one sentence up above; it was not my intention to suggest a new API that "relies on the compiler" to prove anything. What I was trying to say was that this thread is discussing several different kinds of code at once, and that appropriate facilities might be different for each, and it might help to explicitly categorize them.
Present-day Rust code that doesn't use MaybeUninit
or an abstraction over it is already relying on the compiler to prove that no memory location is read before it's written in order to eliminate redundant initialization, and the compiler does a darn good job of it.
simple example: these three functions compile to identical assembly language in release mode
use std::array;
pub const LENGTH: usize = 16;
#[inline(never)]
pub fn fill_0(val: u16) -> [u16; LENGTH] {
[val; LENGTH]
}
#[inline(never)]
pub fn fill_1(val: u16) -> [u16; LENGTH] {
array::from_fn(|_| val)
}
#[inline(never)]
pub fn fill_2(val: u16) -> [u16; LENGTH] {
let mut arr = [0; LENGTH];
for i in 0..LENGTH {
arr[i] = val;
}
arr
}
for small output sizes the same is true for Fibonacci series generation
const LENGTH: usize = 16;
#[inline(never)]
pub fn fibonacci_array_unsafe() -> [u64; LENGTH] {
use std::mem::{transmute, MaybeUninit};
let mut output = [MaybeUninit::<u64>::uninit(); LENGTH];
output[0].write(1);
output[1].write(1);
for i in 2..LENGTH {
output[i].write(unsafe { output[i - 1].assume_init() + output[i - 2].assume_init() });
}
unsafe { transmute(output) }
}
#[inline(never)]
pub fn fibonacci_array_safe() -> [u64; LENGTH] {
let mut output = [0; LENGTH];
output[0] = 1;
output[1] = 1;
for i in 2..LENGTH {
output[i] = output[i - 1] + output[i - 2];
}
output
}
#[inline(never)]
pub fn fibonacci_array_from_fn() -> [u64; LENGTH] {
struct FibGen(u64, u64);
impl FibGen {
fn new() -> Self { Self(1, 1) }
fn next(&mut self) -> u64 {
let a = self.0;
self.0 = self.1;
self.1 += a;
a
}
}
let mut fibgen = FibGen::new();
std::array::from_fn(|_| fibgen.next())
}
But suppose that's not good enough. Suppose the compiler doesn't manage to clean out all the redundant initialization, so we want to consider using this hypothetical safe abstraction over uninitialized memory. There's at least three different kinds of code like that:
- The most exotic case is when code intentionally reads from memory that the author knows is uninitialized, with the desired semantics being for the read to return an arbitrary valid value. This is the case for the data structure mentioned earlier by @tczajka, and (I hope!) the only case where a language-exposed
freeze
is what one actually wants.[1]
-
A much more common case is when some function only needs to write to memory that may or may not already be initialized, and then attest to its callers that it has done so. The Fibonacci series generator is like this, but as discussed above, the existing
array::from_fn
handles it fine.[2] RFC 2390 "borrowed" buffers and cursors (tracking issue) aim to solve a different subset of this case. Can anyone think of any examples that are handled by neitherarray::from_fn
nor RFC 2390? -
And the case I think @abgros was originally talking about: a human auditor can tell that the code never actually reads from uninitialized memory, but the compiler is not sophisticated enough to do the same, so either we have redundant initializations in the compiled program, or it fails to compile at all, or the human applies
MaybeUninit
and finds the additional ceremony obscures the actual logic too much.freeze
should not be necessary for this, but I don't think we know what the right abstraction is yet. I would like to see examples for this case that are more complicated than the original Fibonnaci series generator, and in particular where there isn't a straightforward way to swap in an algorithm that doesn't read from (potentially) uninitialized memory at all.
I do not agree with the suggestion that it's automatically a bug in the language to have such a primitive even for integer types. In the conventional multiprocessing model, there are no true security boundaries within a process, and it is the operating system's responsibility to clear sensitive data out of memory newly allocated to each process. In an environment with finer-grained memory capabilities, like what would be possible with CHERI, some of that responsibility moves to the in-process allocator --
free
needs to wipe the "this is a capability" bit on each word of storage, for instance -- but I still don't buy the argument that allowing an integer to leak from one part of the process to another is unacceptable. I could be convinced otherwise with concrete examples of why it's a problem. ↩︎There's an unnecessary
memcpy
from scratch storage in the generator's stack frame into the output buffer provided by the caller, but that also happens for the version usingMaybeUninit
, and it might be eliminated if the function were allowed to be inlined into a realistic caller. ↩︎
I can give other examples for 1 and 2...
(2) has the more straightforward case: you might be generating a slice of data but the individual slice elements aren't produced in sequential order. Maybe the algorithm generates them in reverse order, generates even elements before the odd ones, or some more complicated permutation.
A case of (1) can occur when implementing a LZ decompressor. LZ compression essentially works by encoding a series of push_byte(b)
and extend_from_within(start, length)
operations and using them to progressively initialize a buffer. However, it turns out that a straightforward implementation of extend_from_within
isn't friendly to the branch predictor because every value for the length results in a different number of loop iterations being executed. A better strategy is to handle all short cases with a single copy of 8 or 16 bytes, but only advance the buffer by the true length. If the start location is close to the end of the initialized portion of the buffer then a few uninitialized bytes might be copied and overwrite other uninitialized bytes, but that'll be harmless.
Yes. But if it actually is impossible to prove whether some program foo
might access uninitialized memory—then it is also impossible to prove that it is impossible to prove whether foo
might access uninitialized memory.
This is because, if foo
could in fact access uninitialized memory, that could be proved via an example. Therefore, a proof that proving whether foo
accesses uninitialized memory is impossible, would imply that no such example exists, which would be proof that foo
does not access uninitialized memory, which is a contradiction.
Therefore, no matter how smart your compiler is in determining whether a program might access uninitialized memory, it’s always possible that a human (or a different compiler) might be even smarter. There is no way to have a compiler that is provably as smart as possible.
Yes. For example, you could let a compiler think longer (given an optimization algorithm that has that setting), and then it will be able to prove more things about the program.
There is one notable safe abstraction over uninitialized memory you can use today: the MaybeUninit::write
family of functions.
I tried to walk over various threads on the topic of uninit memory and "freeze", and in one of those threads there was a more detailed explanation of technical details why abstract machine is different from physical machine - mainly because if it's not kernel level of single-core system without interrupts, then uninit memory can be not even "claimed" from the OS (valid for both heap and stack), and so reading it twice can return different value (this is not so important for stack as OS will map it in a different way, but we can ignore it for a moment).
So what if such unsafety would be resolved by language on "best effort" basis, by basically writing to the last word of MaybeUnint<T>
if it's size is less than page size on the target OS (and this information is anyway available to the compiler and/or can be specified in compile target properties the same way as single/multicore, atomic width, etc), or two writes if it's less than two pages, etc. Maybe it can be indeed some other abstraction/type (and that really should try to avoid stack-to-stack copies when calling assume_init()
), but from implementation perspective (that I believe 99% of users of MaybeUnit
would care) it would completely remove inequality between abstract and physical machine as much as possible. It'll not be zero cost, but 1-2-3 machine words write cost, but still would be a good first simple approximation
Coming at this from a different angle, if one specific concern here is that MaybeUninit
arrays make the logic too opaque, can that be improved? For example, could the situation be sufficiently better if Index/Mut
could be made unsafe
for a type somehow? (You can already make a MaybeUninitArray
newtype with unsafe get/set methods)
This can be done without freeze
; copy_nonoverlapping
and copy
work just fine with uninit bytes (the target bytes and then also uninit, ofc).
Unless you mean that those bytes are out-of-bounds; that is definitely UB but it's a different kind of UB from uninit memory issues. LLVM sadly currently has no way to express out-of-bounds reads in a UB-free way so there's no way we can offer them; I think the API would have nothing to do with MaybeUninit
.
While true…I don't know that Rust can guarantee no side-channels exist, so it seems like a weak reason to discount the language feature as a whole ("Generator functions can't make me a pizza, so what use are they?").[1]
That said, I don't think network checksums are a good use case for utilizing uninitialized memory. IIUC, they are not "tight" enough that I would trust their behaviors against uninit memory as they are (usually) intended to uncover some low-number of bit errors against the actual data. I feel that there's a higher chance that garbage data erroneously passes a checksum rather than any 1- or 2-bit error during read of the intended data.
I have no opinion on the
freeze
feature as discussed here or from the linked RFC that I've not read. ↩︎
Ah, you're right. copy
does provide the required semantics.
Out of bounds reads aren't a problem. Or rather, they are a problem, but one that the surrounding code is already expected to do the necessary bounds checks.