Out-of-bounds Read

[saethlin]

This bounds check is wrong:

atoi_simd/src/fallback.rs

Line 145 in 293e4e8

let mut val: u64 = unsafe { read_unaligned(s.get_safe_unchecked(8..).as_ptr().cast()) };

It should be

 let mut val: u64 = unsafe { read_unaligned(s.get_safe_unchecked(8..16).as_ptr().cast()) }; 

Applying this change causes a number of tests to fail.

This issue can also be observed using Miri, if I run cargo +nightly miri test without the .cargo/config in this repo, I can get at least these two UB reports:

196 |             let val: u64 = unsafe { read_unaligned(s.get_safe_unchecked(8..).as_ptr().cast()) };
    |                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ using uninitialized data, but this operation requires initialized memory
    |

   --> src/fallback.rs:145:41
    |
145 |             let mut val: u64 = unsafe { read_unaligned(s.get_safe_unchecked(8..).as_ptr().cast()) };
    |                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ memory access failed: alloc29045 has size 9, so pointer to 8 bytes starting at offset 8 is out-of-bounds

[RoDmitry]

Hi. It should not be 8..16. There is no problem with getting slice of s. You might not understand the concept of how this works.
For example we have code:

let s = "123";
let val: u64 = unsafe { read_unaligned(s.as_ptr().cast()) };

val at that point might be something like 0xAF3534_333231, that's why it warns us that it might be UB, because it has read extra memory, that we don't own. But on the next line we have:

let len = check_8(val).min(s.len()); // In this example it will be choosing the min between 5 and 3

which makes sure we have the correct len of our data.

[saethlin]

let s = "123";
let val: u64 = unsafe { read_unaligned(s.as_ptr().cast()) };

This program is UB. It executes a buffer overflow.

[Shnatsel]

To elaborate on what @saethlin said: it does not matter if data read from out of bounds is never used; the very act of reading from out of bounds is already a problem.

Languages like C or Rust define what is legal and illegal to do within them. Reading out of bounds is always illegal, and since it is illegal, the compiler assumes it will never happen. Such illegal operations are (somewhat confusingly) called "undefined behavior"; you can learn more about the concept here. In C and Rust any operation that reads out of bounds is undefined behavior, and should never be performed. Programs that read out of bounds are a typical cause of security vulnerabilities; they are #7 on the CWE list of most dangerous software vulnerabilities.

An out-of-bounds read would be legal in assembly, if and only if you also took precautions to never cross the page boundary, but using an unaligned read makes it illegal even in pure assembly.

That is to say, this is a genuine problem that needs to be fixed.

[RoDmitry]

I have read about it, and I still don't understand why it is illegal. The only thing I have found is that it has access to that extra memory, but it does not write there, it just reads with read_unaligned. @Shnatsel, you definitely has more experience than me about it. Can you give me examples of what bad can happen, and how dangerous it can be?

[Shnatsel]

The best case for your current code is that it is lowered into assembly exactly as written, but when the buffer happens to be near the page boundary so that your read crosses it, your program is killed by the OS due to the illegal memory access.

The worst-case scenario for an out-of-bounds read is this: https://en.wikipedia.org/wiki/Heartbleed

Once you have performed an operation that the language explicitly specifies must never be performed, literally anything can happen. It may work for some inputs but not others; or it may work on some compiler version or not others, or with certain compiler flags or not others, or allow an attacker that provides a carefully crafted string for your code to parse execute arbitrary code on your computer. Absolutely anything can happen because you have broken the basic rules of reality.

[Shnatsel]

Perhaps a more accessible explanation of undefined behavior can be found here: https://www.ralfj.de/blog/2019/07/14/uninit.html

atoi_simd also performs reads from uninitialized memory, so this is going to be relevant here as well.

[RoDmitry]

Thanks. Will have to read about it more.
Any solution to read an array into integer without causing UB? (and not as slow as one char by one)

[RoDmitry]

I think about cloning the data in an Array with bigger capacity, then the bounds will be right. But I think the speed will be worse. Have to benchmark it.

[Shnatsel]

u64::from_ne_bytes lowers into a load. Here is proof on godbolt: https://godbolt.org/z/a5GPfs61s The function is just a bounds check and a load. (I have written a very detailed article on avoiding bounds checks that also covers inspecting the generated assembly, it might come in handy). However, u64::from_ne_bytes requires the input slice to be 8 bytes in length.

There is no way to read from a variable-length slice that may be under 8 bytes in length to a u64 efficiently and without UB. This is why when the compiler processes a slice in a loop with SIMD instructions, it has to insert special handling of the end that may be shorter than SIMD allows, where it reads byte-by-byte.

I think about cloning the data in an Array with bigger capacity, then the bounds will be right. But I think the speed will be worse. Have to benchmark it.

If you do this on a variable-length input, it will lower to a memcpy() call: https://godbolt.org/z/1P5hbr6jP

memcpy() is usually optimized for large inputs and will not be great for this use case. You could try writing a manual loop that copies byte-by-byte and see if that helps at all; I don't know if it will, but at least it's worth a shot.

[RoDmitry]

Is this also UB for s = b"123"?

[Shnatsel]

Yes. b"123" is 3 bytes (24 bits) long, while the SIMD load performs a 16-byte (128-bit) load and goes out of bounds. The original blog post gets away with this only because in their case the input is always 16 characters long.

You could still make use of SIMD if you pad the input with zeroes up to 16 characters, turning b"123" into b"000000000123". You can achieve this by making a [b'0'; 16] and copying the actual input to the end, but the copy still has to be done byte-by-byte. However, a 16 characters long buffer is not going to be enough for many numeric types. For example, the maximum value representable by a u64 is 18446744073709551615 which is 21 characters long. And u128 maximum value is 40 characters long. So you might have to use bigger buffers than 16 if you want to keep using SIMD.

[RoDmitry]

For the record, at some point, I did use an array, and it was slower. Will test it again

[RoDmitry]

I have made separate functions read_8 and read_16, and have tested this:

fn read_8(s: &[u8]) -> u64 {
    let mut buf = [0u8; 8];
    let len = s.len().min(8);
    buf[..len].copy_from_slice(&s[..len]);
    u64::from_ne_bytes(buf)
}

And also this:

fn read_8(s: &[u8]) -> u64 {
    if s.len() < 8 {
        let mut buf = [0u8; 8];
        buf[..s.len()].copy_from_slice(s);

        return u64::from_ne_bytes(buf);
    }

    unsafe { read_unaligned(s.as_ptr().cast()) }
}

It's more than 2x slower. (In case anybody wants, you can test it with cargo bench -- "parse u64/9", without the .cargo/config)
And Miri is happy now (with also changed read_16), but not me..

[Shnatsel]

I agree that this performance degradation is frustrating.

You might want to check if a manual loop is faster than a copy_from_slice which is a memcpy() behind the scenes. memcpy() is usually optimized for big copies, not small ones, so a manual loop over a number of elements known to be small might be faster.