Too much undefined behavior

[gnzlbg]

I started to write a PR to just show how using #[target_feature] would look like but I encountered too much undefined behavior in the process (fixing it was taking more time than actually dealing with target feature).

I've only taken a look at a tiny fraction of the aesni crate, but it seems that references to uninitialized memory are created pretty much everywhere (all references must point to initialized memory [0]):
* https://github.com/RustCrypto/block-ciphers/blob/master/aes/aesni/src/aes128/expand.rs#L21
* https://github.com/RustCrypto/block-ciphers/blob/master/aes/aesni/src/aes128/expand.rs#L36

The way I fixed these was by using ptr::write to write to uninitialized memory without creating a reference.

There are also reads memory out-of-bounds: https://github.com/RustCrypto/block-ciphers/blob/master/aes/aesni/src/aes192/expand.rs#L51

The way I fixed this was by creating a stack buffer of appropriate size in the mod.rs file which I initialized with mem::uninitialized, and then using ptr::write to write the GenericArray into the head of the buffer, so that the vector load never reads memory out of bounds - the memory read is only partially initialized though, and reading vector lanes with uninitialized memory should be done with care (so that no UB is introduced).

---

[0] &T as *const T and &mut T as *mut T might not end up being undefined behavior because they might end up being atomic operations in the memory model that create a raw pointer directly without creating a reference (so that no reference to uninitialized memory is ever created by these expressions, preventing them from invoking undefined behavior).

[newpavlov]

This uninitialized memory is stack allocated, we always fully fill it and never read uninitialized values from it. I don't see how it can cause UB. Essentially we just ask compiler to reserve N bytes on stack for us to fill later. Also I don't quite get why you think that _mm_loadu_si128(key.as_ptr() as *const __m128i) is UB. As I see it it's the most basic way to load data into __m128i (essentially xmm register). Can you be more explicit with your arguments?

As for out-of-bound read Intel AES-NI white-paper (p. 32) uses essentially the same code. I knew about out-of-bound access (see comment), but I don't see how it can cause problems in practice, as we always overwrite garbage data. Theoretically it may cause problems if key pointer has address 2^64 - 24 on 64 bit machines, but isn't it a bit too theoretical?

As for migration to #[target_feature] I would be grateful if you discuss proposed changes first, via issue or #rust-crypto IRC channel.

[gnzlbg]

This uninitialized memory is stack allocated, we always fully fill it and never read uninitialized values from it. I don't see how it can cause UB.

As mentioned, the undefined behavior in the library is not of type "read of uninitialized memory", but "reference to uninitialized memory". This code never reads uninitialized memory:

let x: i32 = mem::uninitialized();
let y = &x; // UB

yet it has undefined behavior because it creates a reference to memory that is uninitialized - raw pointers can point to uninitialized memory, but references always must point to initialized memory and creating a reference that points to uninitialized memory is undefined behavior.

In the code, x[i] = 2; creates a reference &mut to the uninitialized memory at x.as_ptr().offset(i), which is undefined behavior, and then uses that reference to write 2 to that memory.

What the code probably wants to do here is:

ptr::write(x.as_mut_ptr().offset(i), 2);

which creates a raw pointer instead of a reference, and writes to it using ptr::write. Raw pointers can point to uninitialized memory without introducing undefined behavior.

Also I don't quite get why you think that _mm_loadu_si128(key.as_ptr() as *const __m128i) is UB.

The code is using _mm_loadu_si128 twice, to read 256bit of data (32 bytes), from an [u8; 24] (a 24 byte long array. You read the first 128-bits (16 bytes) of the array using the first _mm_loadu_si128, which is ok. Then, the code offset the pointer by 16 bytes, to read another 16 bytes using the second _mm_loadu_si128. However, only 24 - 16 = 8 bytes are in the array, which means that the program read 8 bytes out-of-bounds. That's undefined behavior.

As for migration to #[target_feature] I would be grateful if you discuss proposed changes first.

Yeah, I just wanted to submit a PR with a small prototype, so that you could see what the changes look like, so that we have something concrete to talk about. I think that would be more productive than just talking about this in an abstract way without looking at any code.

[gnzlbg]

FYI the mem::uninitialized docs list the only safe ways of initializing uninitialized memory: https://doc.rust-lang.org/std/mem/fn.uninitialized.html#undefined-behavior

The only way to safely initialize an uninitialized value is with ptr::write, ptr::copy, or ptr::copy_nonoverlapping.

Using ptr::write everywhere sucks, but that's the most common way.

Because mem::uninitialized is such a huge footgun and so annoying to use correctly, what people often do is use an union instead. I don't remember exactly how to do it, but I think you can just do:

union U {
    x: i32,
    y: (),
}
let mut u = U { y: () }; // "uninitialized" memory
u.x = 3; // initializes the memory

// this should always work though:
ptr::write(&mut u as *mut i32, 3);
// note that u is initialized, 
// so &mut u can never become undefined behavior

In the ptr::write, note that because u is initialized, &mut u is a reference to initialized memory, which makes it defined behavior in all currently memory model proposals. Some people feel that making &mut T as *mut T syntax for directly creating a pointer without creating a reference is too clever, and these people would like the simplicity of &mut T is undefined behavior if T is uninitialized - no exceptions. Under that harsh memory model, the union snippet would still be correct, because &mut u is a reference to initialized memory.

[newpavlov]

In the code, x[i] = 2; creates a reference &mut to the uninitialized memory at x.as_ptr().offset(i), which is undefined behavior, and then uses that reference to write 2 to that memory.

It's a bit pedantic to my taste, as for me when we work with plain bytes one is just a sugar around another. But, ok, I'll change it, though it will make code a bit noisier.

FYI the mem::uninitialized docs list the only safe ways of initializing uninitialized memory:

Note, that your link talks only about types which implement Drop, which is obviously not the case here. I don't see how plain bytes can cause issues here.

However, only 24 - 16 = 8 bytes are in the array, which means that the program read 8 bytes out-of-bounds. That's undefined behavior.

I know about it. Intel code example does absolutely the same. I don't see how it can cause problems in practice, as we never use out-of-bound bits. But if we are being pedantic, we can change it, luckily this part of the code can tolerate one or two redundant instructions.

[newpavlov]

I'll write a PR with the discussed changes. Do you have any other places which you think cause UB?

[gnzlbg]

I know about it. Intel code example does absolutely the same.

Then Intel code example has undefined behavior as well would have undefined behavior as well, but the AES_192_Key_Expansion function there is never passed any arguments. If you pass it a pointer to a 32-byte wide memory region, it doesn't have UB.

But if we are being pedantic, we can change it, luckily this part of the code can tolerate one or two redundant instructions.

I think it can be changed without redundant instructions if you do something like this (I haven't fully checked this code though):

let key: GenericArray<u8, 24>;
let mut x: [u8; 32] = mem::uninitialized();
ptr::write(x.as_mut_ptr() as *mut GenericArray<u8, 24>, key);
encrypt(x.as_ptr());
// note that we can't pass x by & because that would 
// create a reference to uninitialized memory :( 

fn encrypt(key: *const [u8; 32]) {
    let u : __m128i = _mm_loadu_si128((key as *const u8).offset(16) as *const __m128i);
    // ^^^ the last 8 bytes of u are uninitialized 
    // as long as we overwrite them before we use them everything should be ok
    // but in the mean time one cannot create references to u :(
}

though it will make code a bit noisier.

It makes the code a lot noisier sadly, I have no good ideas about how to make it less noisy here :/ Maybe just use raw pointers instead? Or use mem::zeroed instead of mem::uninitialized.. but that might add overhead, I don't know.

Note, that your link talks only about types which implement Drop, which is obviously not the case here.

None of the Drop stuff applies here (if you are interested, it applies only to drop types, and then you also have to be careful when using the ptr::read/write methods because they do not drop values, so you can end up with double drops).

It's a bit pedantic to my taste,

For my taste too, but undefined behavior is undefined.

I'd like to think that the Rust from the future might use this to optimize in some cases. Those cases are not the one in this crate, but if the behavior is undefined other programs might behave incorrectly as a consequence of the optimization. So Rust from the future decides to assert! on debug builds if this undefined behavior is triggered, which is fine, since Rust is allowed to generate any code if you invoke undefined behavior, and an assert! alerting you is one of the nicest things it can do.

So even though your program doesn't benefit from the optimization, because of the UB, it might some day panic.

I don't know if that motivates you to fix these, but that's what I tell myself to motivate myself.

---

FWIW the root issue here is that the code uses mem::uninitialized, which is extremely easy to use incorrectly.

Before you start fixing these, I'd recommend you to read on these issues, and play with unions. An union makes uninitialized memory much nicer to use, and much harder to use incorrectly (e.g. see the MaybeUninit RFC which actually proposes to deprecate mem::uninitialized).

I haven't removed all uses of mem::uninitialized from all my code, but I've removed most from the code that isn't part of tests and moved that to unions because of this.

---

Do you have any other places which you think cause UB?

I've just looked at a tiny portion of the library, sorry. I can go through the PR if you wish, and I will try to prototype the #[target_feature] thing afterwards, so I guess that trip will show me more of the library.

[newpavlov]

Before you start fixing these, I'd recommend you to read on these issues, and play with unions. An union makes uninitialized memory much nicer to use, and much harder to use incorrectly.

Can you, please, show how MaybeUninit union can be used here? Create uninit variant, then pointer to it, do writing and convert to an array variant? IIUC it does not bring much to the table here and even worse will make code even noisier.

[gnzlbg]

Can you show how MaybeUninit union can be used here?

Not really, I've never used MaybeUninit myself. I just read the RFC a couple of days ago.

What I currently always do in std::arch and std::simd is:

union U {
    x: i32,
    y: (), // uninitialized variant
}
// create uninitialized value:
let u = U { y: () };
// initialize it to some value:
let value = 42_i32;  
ptr::write(&mut u  /* always ok: u is initialized */ as *mut i32, value);

What you want here is to have an array that contains partially initialized values, so I would do:

union U {
    x: u8,
    y: (), // uninitialized variant
}
let array: [U; 32] = [U { y: () }; 32]; // uninitialized values
// note: array itself is initialized, and so are the elements of it
ptr::write(&mut array[3] /* ok: the array, array[3] are initialized */ as *mut u8, some_value);

Does that make sense?

IIRC, to use MaybeUninit you would just write let x: [MaybeUninit<u8>; 32] = ...;. It should work on a similar way, where you initialize the elements of the array with the uninit variant.

The point is that the array object is initialized, and each element is initialized to the () variant. So because these objects are initialized, you can construct references to them, and they always are references to initialized memory. Reading from it using ptr::read gives you initialized memory if you read () (it gives you a initialized memory region of length zero). If you, OTOH, read an u8 from it, you read uninitialized memory, which is something that you can read via a pointer. You can read and write uninitialized memory, but not use it in any other way IIRC (e.g you can read an uninitialized u8 but you cannot add it to another u8).

These is all this complicated because of the uninitialized memory. In std::arch what I've done is move some of the tests to mem::zeroed(), and call it a day (for the primitive number and pointer types mem::zeroed produces valid values, so memory is always properly initialized). But for the intrinsics themselves I couldn't do that.

[newpavlov]

While I see the motivation behind making creation of uninitialized data safe and moving unsafety to final conversion from union to "plain" type, currently I think that for small cases like this where you essentially deal with one unsafe block in which you handle everything, union based code makes code less readable, and thus less reviewable. But I guess, it's a matter of preference and habits.

I think it can be changed without redundant instructions if you do something like this (I haven't fully checked this code though):

I've checked your approach on godbolt, and surprisingly it has produced a good result. (movups got replaced with movsd)

[gnzlbg]

I've checked your approach on godbolt, and surprisingly it has produced a good result. (movups got replaced with movsd)

Yeah, you should really check the code generation for all these changes. You don't want to inadvertently produce a regression.

union based code makes code less readable, and thus less reviewable. But I guess, it's a matter of preference and habits.

FWIW, I started with that opinion, and it took me about 2 weeks to change it because I started discovering more and more undefined behavior due to uninitialized in my programs. I guess that at some point, I might even like MaybeUninit<T>.

For example, for the array indexing case (x[i]), when is undefined behavior introduced? I wrote above that creating a reference to an element of the array was UB, because the element is uninitialized, but actually UB is introduced in the program well before that. There is an implementation of IndexMut for arrays somewhere, where the index_mut(&mut self, usize) takes a &mut self. That &mut self right there is already UB because the array itself is uninitialized, and we haven't even started indexing anything yet.

I started to like the union approach (and MaybeUninit is just an union with convenience methods) because it makes invoking UB in subtle ways like via &self much harder to trigger.

If you want to keep the x[i] syntax, you could add an index_assign!(array, index, value) that abstracts the boilerplate away and is safe.

[gnzlbg]

Nice, this was really quick!