Out of bounds array access in `lr_stripe`

[randomPoison]

In converting Rav1dFrameContext_lf's lr_line_buf field to a Vec and lr_lpf_line to offsets within that allocation (#793) I've run into an issue where we appear to be using a pointer that is offset to before the allocation it originates from.

in lr_stripe (in lr_apply.rs) we're calculating a pointer lpf from one of the pointers in lr_lpf_line. The pointers in lr_lpf_line point into the allocation owned by by lr_line_buf, so lpf can't point outside of that allocation. But in practice I'm finding that we sometimes calculate a value for lpf that points to before the allocation in lr_line_buf.

I confirmed this by adding an assert before the call to lr_fn (where lpf is used) checking that lpf >= lr_line_buf. The issue seems to be only happening when using --framedelay 2, otherwise the assert never triggers.

The version of the logic for calculating lpf was changed in #746 which makes it a bit different than the original C. To determine if that change was the cause of the issue I checked out the commit from before it was merged (e0b5aa4) where the code we have is still the same as the original C as far as I can tell. I was still able to reproduce the issue on this earlier commit so it seems unrelated to the changes in #746.

Since the code we have here is basically the same as the original C, I attempted to reproduce this issue in dav1d to see if it's also present upstream. I was not able to reproduce the issue under the same conditions, so it looks like this is an issue we introduced at some point.

[randomPoison]

Some additional details I've confirmed:

• The initial calculation of lpf is out of bounds. We also do lpf += 4 * stride in the loop, but it looks like the pointer is already incorrect before we get to the loop.
• The issue is happening when plane == 0, so it's the first pointer in lr_lpf_line that's being used to create lpf.

[fbossen]

AFAICT, the issue is also present in dav1d, i.e., (uint8_t *)lpf < f->lf.lr_line_buf can be true in lr_stripe after initializing lpf. I think I have seen this before. lpf can point outside the allocated memory area but the area that is actually referenced is within the allocated memory.

[randomPoison]

lpf can point outside the allocated memory area but the area that is actually referenced is within the allocated memory.

What do you mean by this? That even if lpf is pointing to outside the allocation, it's only used when the pointer is in bounds? Or that we always offset it back to being in bounds before it's used?

If this issue is present in dav1d, have you been able to reproduce it? I've been trying to do so but haven't been able to get the assert to trigger the way I can in the Rust version.

[fbossen]

lpf can point outside the allocated memory area but the area that is actually referenced is within the allocated memory.

What do you mean by this? That even if lpf is pointing to outside the allocation, it's only used when the pointer is in bounds? Or that we always offset it back to being in bounds before it's used?

Offsets are added such that memory accesses are valid.

If this issue is present in dav1d, have you been able to reproduce it? I've been trying to do so but haven't been able to get the assert to trigger the way I can in the Rust version.

I've added the following after the declaration of lpf in the C code: if ((uint8_t *)lpf < f->lf.lr_line_buf) *(volatile char *)0 = 0;. Basically forcing a crash if the condition is satisfied.

lpf essentially points to the x-th value (where x < stride) in an array of pixel blocks, where each block contains 4 * stride values. Sometimes, lpf may point inside the block immediately preceding the first block in the allocated array of pixel blocks. However, in those cases, the block pointed to by lpf (i.e., the block with index -1 in the allocated array) is not accessed.

[randomPoison]

I've added the following after the declaration of lpf in the C code: if ((uint8_t *)lpf < f->lf.lr_line_buf) *(volatile char *)0 = 0;. Basically forcing a crash if the condition is satisfied.

Are you actually getting it to crash in practice? I tried the same thing with an assert but haven't been able to run the tests in a way that actually triggers the assert.

[randomPoison]

Sometimes, lpf may point inside the block immediately preceding the first block in the allocated array of pixel blocks. However, in those cases, the block pointed to by lpf (i.e., the block with index -1 in the allocated array) is not accessed.

Hrm, I'm not sure how to address this in Rust. In theory we'd like to pass the base pointer plus and offset so that the code that eventually dereferences lpf can calculate a final in-bounds pointer before dereferencing, but the function lpf is being passed to is an asm function and we don't want to touch those to change their signature/behavior.

We also have to be careful about how we're calculating the pointer if it's going to point out of bounds of the allocation, even temporarily. It's UB to use offset to to create an OOB pointer, so I think we have to use wrapping_offset instead.

[fbossen]

Hrm, I'm not sure how to address this in Rust. In theory we'd like to pass the base pointer plus and offset so that the code that eventually dereferences lpf can calculate a final in-bounds pointer before dereferencing, but the function lpf is being passed to is an asm function and we don't want to touch those to change their signature/behavior.

One way to address the issue in Rust without changing asm functions is to increase the amount of memory that is allocated such that pointers always point to a valid address. The amount of additional memory would be in the order of 4*stride here.

[kkysen]

@randomPoison, is this still something we need to fix?

[randomPoison]

Nope, this was fixed by making the offset an isize allowing it to be negative and adding additional offsets to it so that it's positive before we do any indexing. We can close this issue.