On Mon, Dec 4, 2023 at 1:32 PM Andrii Nakryiko
<andrii.nakryiko@xxxxxxxxx> wrote:
>
> On Mon, Dec 4, 2023 at 7:39 AM Andrei Matei <andreimatei1@xxxxxxxxx> wrote:
> >
> > This patch fixes a bug around the verification of possibly-zero-sized
> > stack accesses. When the access was done through a var-offset stack
> > pointer, check_stack_access_within_bounds was incorrectly computing the
> > maximum-offset of a zero-sized read to be the same as the register's min
> > offset. Instead, we have to take in account the register's maximum
> > possible value.
> >
> > The bug was allowing accesses to erroneously pass the
> > check_stack_access_within_bounds() checks, only to later crash in
> > check_stack_range_initialized() when all the possibly-affected stack
> > slots are iterated (this time with a correct max offset).
> > check_stack_range_initialized() is relying on
> > check_stack_access_within_bounds() for its accesses to the
> > stack-tracking vector to be within bounds; in the case of zero-sized
> > accesses, we were essentially only verifying that the lowest possible
> > slot was within bounds. We would crash when the max-offset of the stack
> > pointer was >= 0 (which shouldn't pass verification, and hopefully is
> > not something anyone's code attempts to do in practice).
> >
> > Thanks Hao for reporting!
> >
> > Reported-by: Hao Sun <sunhao.th@xxxxxxxxx>
> > Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> > Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@xxxxxxxxxxxxxx/
> > Signed-off-by: Andrei Matei <andreimatei1@xxxxxxxxx>
> > ---
> > kernel/bpf/verifier.c | 5 ++---
> > 1 file changed, 2 insertions(+), 3 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index af2819d5c8ee..b646bdde09cd 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -6816,10 +6816,9 @@ static int check_stack_access_within_bounds(
> > return -EACCES;
> > }
> > min_off = reg->smin_value + off;
> > + max_off = reg->smax_value + off;
> > if (access_size > 0)
> > - max_off = reg->smax_value + off + access_size - 1;
> > - else
> > - max_off = min_off;
> > + max_off += access_size - 1;
>
> this special casing of access_size == 0 feels wrong (and I mean before
> your patch as well).
>
> Looking at the code, we only really calculate max_off to check that we
> don't go to a non-negative stack offset, e.g., r10+0 or r10+1 (and
> beyond).
>
> So given that, I propose to calculate max_off as an exclusive bound,
> and instead of doing a mostly useless check_stack_slot_within_bounds()
> call for it, just check that max_off is <= 0.
>
> Something like this:
>
> min_off = reg->smin_value + off;
> max_off = reg->smax_value + off + access_size;
> err = check_stack_slot_within_bounds(min_off, state, type);
> if (!err && max_off > 0)
> err = -EINVAL; /* out of stack access into non-negative offsets */
>
>
> Now, one more issue that jumped out at me is that we calculate min/max
> off as a sum of smin/smax values (which are checked to be within
> +/-1<<29, all good so far) *and* insn->off, which can be a full s32,
> it seems. So we are running into overflow/underflow territory with
> using int for min_off/max_off.
>
> While you are at it, can you please use s64 for all these calculations? Thanks!
insn->off is __s16, not s32 [1], so I think we're good as far as
offsets coming from instructions are concerned.
For helpers, the offset comes from a register, but it's checked
against 1<<29 here [2].
However, there's also this code path [3] dealing with kfunc args,
where I think the size can indeed technically be a full u32. So yeah,
I'll append a patch to deal with possible overflow.
[1] https://github.com/torvalds/linux/blob/815fb87b753055df2d9e50f6cd80eb10235fe3e9/include/uapi/linux/bpf.h#L76
[2] https://github.com/torvalds/linux/blob/815fb87b753055df2d9e50f6cd80eb10235fe3e9/kernel/bpf/verifier.c#L7494-L7498
[3] https://github.com/torvalds/linux/blob/815fb87b753055df2d9e50f6cd80eb10235fe3e9/kernel/bpf/verifier.c#L7528
>
>
> > }
> >
> > err = check_stack_slot_within_bounds(min_off, state, type);
> > --
> > 2.40.1
> >
