[PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

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@gmail.com>
Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/
Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
 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;
 	}
 
 	err = check_stack_slot_within_bounds(min_off, state, type);
-- 
2.40.1

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Mon, Dec 4, 2023 at 7:39 AM Andrei Matei <andreimatei1@gmail.com> 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@gmail.com>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---
>  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!


>         }
>
>         err = check_stack_slot_within_bounds(min_off, state, type);
> --
> 2.40.1
>

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

[...]

> >
> > 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 */

Dealing with access_size == 0 indeed feels dubious to me, but I'm not entirely
sure that your suggested code is better. min_off being inclusive and
max_off being
exclusive seems surprising. I'll do it if you want, I don't care too much.
We could keep max_off exclusive, and still not call
check_stack_slot_within_bounds() for it:

 min_off = reg->smin_value + off;
 max_off = reg->smax_value + off + access_size - 1;
 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 */

But now max_off can be below min_off, which again seems confusing.

What I'd really like to know is whether this whole zero access_size business
deserves to exist. Do you know what the point of verifying a zero-sized access
is exactly / could we turn 0-byte access into 1-byte accesses and
verify that instead?
Because then there'd be no more special case to consider.

>
>
> 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!
>
>
> >         }
> >
> >         err = check_stack_slot_within_bounds(min_off, state, type);

Will do.

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Mon, Dec 4, 2023 at 11:52 AM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> [...]
>
> > >
> > > 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 */
>
> Dealing with access_size == 0 indeed feels dubious to me, but I'm not entirely
> sure that your suggested code is better. min_off being inclusive and
> max_off being
> exclusive seems surprising. I'll do it if you want, I don't care too much.
> We could keep max_off exclusive, and still not call
> check_stack_slot_within_bounds() for it:
>
>  min_off = reg->smin_value + off;
>  max_off = reg->smax_value + off + access_size - 1;
>  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 */
>

Yeah, we can do that. The reason I go for max_off being exclusive is
because using half-opened ranges is very convenient [start, end) (end
exclusive) is much more uniform and natural to handle compared to
closed [start, end] (end inclusive), in all sorts of checks, including
handling empty ranges. The math just works out better and more
naturally. And it's not like this will be the first time where in BPF
we have half-open ranges.

> But now max_off can be below min_off, which again seems confusing.

That's ok, the point here is to validate that we don't access stack
out of bounds.

>
> What I'd really like to know is whether this whole zero access_size business
> deserves to exist. Do you know what the point of verifying a zero-sized access
> is exactly / could we turn 0-byte access into 1-byte accesses and
> verify that instead?
> Because then there'd be no more special case to consider.
>


I think zero is a natural case that can come up, at least with
helpers. As we have ARG_CONST_SIZE_OR_ZERO. So yeah, I wouldn't treat
zero-sized access as 1-byte access, that seems to be more confusing
and potentially broken.

> >
> >
> > 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!
> >
> >
> > >         }
> > >
> > >         err = check_stack_slot_within_bounds(min_off, state, type);
>
> Will do.

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

On Mon, Dec 4, 2023 at 5:05 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Dec 4, 2023 at 11:52 AM Andrei Matei <andreimatei1@gmail.com> wrote:
> >
> > [...]
> >
> > > >
> > > > 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 */
> >
> > Dealing with access_size == 0 indeed feels dubious to me, but I'm not entirely
> > sure that your suggested code is better. min_off being inclusive and
> > max_off being
> > exclusive seems surprising. I'll do it if you want, I don't care too much.
> > We could keep max_off exclusive, and still not call
> > check_stack_slot_within_bounds() for it:
> >
> >  min_off = reg->smin_value + off;
> >  max_off = reg->smax_value + off + access_size - 1;
> >  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 */
> >
>
> Yeah, we can do that. The reason I go for max_off being exclusive is
> because using half-opened ranges is very convenient [start, end) (end
> exclusive) is much more uniform and natural to handle compared to
> closed [start, end] (end inclusive), in all sorts of checks, including
> handling empty ranges. The math just works out better and more
> naturally. And it's not like this will be the first time where in BPF
> we have half-open ranges.

Yeah, after hitting send, I was also thinking that half-open is the more common
interval representation; it just wasn't how this code right here was written.
Will do.

>
> > But now max_off can be below min_off, which again seems confusing.
>
> That's ok, the point here is to validate that we don't access stack
> out of bounds.
>
> >
> > What I'd really like to know is whether this whole zero access_size business
> > deserves to exist. Do you know what the point of verifying a zero-sized access
> > is exactly / could we turn 0-byte access into 1-byte accesses and
> > verify that instead?
> > Because then there'd be no more special case to consider.
> >
>
>
> I think zero is a natural case that can come up, at least with
> helpers. As we have ARG_CONST_SIZE_OR_ZERO. So yeah, I wouldn't treat
> zero-sized access as 1-byte access, that seems to be more confusing
> and potentially broken.

Ack. Still, if you don't mind entertaining me further, two more questions:

1. What do you make of the code in check_mem_size_reg() [1] where we do

if (reg->umin_value == 0) {
  err = check_helper_mem_access(env, regno - 1, 0,
        zero_size_allowed,
        meta);

followed by

err = check_helper_mem_access(env, regno - 1,
      reg->umax_value,
      zero_size_allowed, meta);

[1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489

What's the point of the first check_helper_mem_access() call - the
zero-sized one
(given that we also have the second, broader, check)? Could it be
simply replaced by a

if (reg->umin_value == 0 && !zero_sized_allowed)
    err = no_bueno;

?

2. I believe you're saying that, if we were to verify zero-sized
accesses as 1-byte-sized accesses, we
might refuse some accesses that we permit today, and that wouldn't be
good. But what about
permitting zero-sized accesses with no further checks - i.e.
considering *any* pointer value to
be ok when the access_size == 0 ? Would that be bad? The question is,
morally, what checks are
important (if any) when the size of access is zero?
Or to phrase another way - when a helper is called with a zero access
size, do we expect the helper
to do anything with that pointer, or do we expect the helper to be a no-op?

Thank you!


>
> > >
> > >
> > > 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!
> > >
> > >
> > > >         }
> > > >
> > > >         err = check_stack_slot_within_bounds(min_off, state, type);
> >
> > Will do.

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Mon, Dec 4, 2023 at 3:28 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> On Mon, Dec 4, 2023 at 5:05 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Dec 4, 2023 at 11:52 AM Andrei Matei <andreimatei1@gmail.com> wrote:
> > >
> > > [...]
> > >
> > > > >
> > > > > 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 */
> > >
> > > Dealing with access_size == 0 indeed feels dubious to me, but I'm not entirely
> > > sure that your suggested code is better. min_off being inclusive and
> > > max_off being
> > > exclusive seems surprising. I'll do it if you want, I don't care too much.
> > > We could keep max_off exclusive, and still not call
> > > check_stack_slot_within_bounds() for it:
> > >
> > >  min_off = reg->smin_value + off;
> > >  max_off = reg->smax_value + off + access_size - 1;
> > >  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 */
> > >
> >
> > Yeah, we can do that. The reason I go for max_off being exclusive is
> > because using half-opened ranges is very convenient [start, end) (end
> > exclusive) is much more uniform and natural to handle compared to
> > closed [start, end] (end inclusive), in all sorts of checks, including
> > handling empty ranges. The math just works out better and more
> > naturally. And it's not like this will be the first time where in BPF
> > we have half-open ranges.
>
> Yeah, after hitting send, I was also thinking that half-open is the more common
> interval representation; it just wasn't how this code right here was written.
> Will do.
>
> >
> > > But now max_off can be below min_off, which again seems confusing.
> >
> > That's ok, the point here is to validate that we don't access stack
> > out of bounds.
> >
> > >
> > > What I'd really like to know is whether this whole zero access_size business
> > > deserves to exist. Do you know what the point of verifying a zero-sized access
> > > is exactly / could we turn 0-byte access into 1-byte accesses and
> > > verify that instead?
> > > Because then there'd be no more special case to consider.
> > >
> >
> >
> > I think zero is a natural case that can come up, at least with
> > helpers. As we have ARG_CONST_SIZE_OR_ZERO. So yeah, I wouldn't treat
> > zero-sized access as 1-byte access, that seems to be more confusing
> > and potentially broken.
>
> Ack. Still, if you don't mind entertaining me further, two more questions:
>
> 1. What do you make of the code in check_mem_size_reg() [1] where we do
>
> if (reg->umin_value == 0) {
>   err = check_helper_mem_access(env, regno - 1, 0,
>         zero_size_allowed,
>         meta);
>
> followed by
>
> err = check_helper_mem_access(env, regno - 1,
>       reg->umax_value,
>       zero_size_allowed, meta);
>
> [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
>
> What's the point of the first check_helper_mem_access() call - the
> zero-sized one
> (given that we also have the second, broader, check)? Could it be
> simply replaced by a
>
> if (reg->umin_value == 0 && !zero_sized_allowed)
>     err = no_bueno;
>

Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
this, and kind of similar to the min_off/max_off discussion we had. So
yes, I suspect the above simple and straightforward check would be
much more meaningful and targeted.

I gotta say that the reg->smin_value < 0 check is confusing, though,
I'm not sure why we are mixing smin and umin/umax in this change...

> ?
>
> 2. I believe you're saying that, if we were to verify zero-sized
> accesses as 1-byte-sized accesses, we
> might refuse some accesses that we permit today, and that wouldn't be
> good. But what about
> permitting zero-sized accesses with no further checks - i.e.
> considering *any* pointer value to
> be ok when the access_size == 0 ? Would that be bad? The question is,
> morally, what checks are
> important (if any) when the size of access is zero?
> Or to phrase another way - when a helper is called with a zero access
> size, do we expect the helper
> to do anything with that pointer, or do we expect the helper to be a no-op?

Helper itself might not be a no-op, but it should not write back to
that pointer for sure. But I'd hate to have more special casing for
zero-size read/write than necessary. So if we can structure the logic
in a way that zero is a natural extension, I'd do that.

>
> Thank you!
>
>
> >
> > > >
> > > >
> > > > 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!
> > > >
> > > >
> > > > >         }
> > > > >
> > > > >         err = check_stack_slot_within_bounds(min_off, state, type);
> > >
> > > Will do.

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

On Mon, Dec 4, 2023 at 6:59 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Dec 4, 2023 at 3:28 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> >
> > On Mon, Dec 4, 2023 at 5:05 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Mon, Dec 4, 2023 at 11:52 AM Andrei Matei <andreimatei1@gmail.com> wrote:
> > > >
> > > > [...]
> > > >
> > > > > >
> > > > > > 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 */
> > > >
> > > > Dealing with access_size == 0 indeed feels dubious to me, but I'm not entirely
> > > > sure that your suggested code is better. min_off being inclusive and
> > > > max_off being
> > > > exclusive seems surprising. I'll do it if you want, I don't care too much.
> > > > We could keep max_off exclusive, and still not call
> > > > check_stack_slot_within_bounds() for it:
> > > >
> > > >  min_off = reg->smin_value + off;
> > > >  max_off = reg->smax_value + off + access_size - 1;
> > > >  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 */
> > > >
> > >
> > > Yeah, we can do that. The reason I go for max_off being exclusive is
> > > because using half-opened ranges is very convenient [start, end) (end
> > > exclusive) is much more uniform and natural to handle compared to
> > > closed [start, end] (end inclusive), in all sorts of checks, including
> > > handling empty ranges. The math just works out better and more
> > > naturally. And it's not like this will be the first time where in BPF
> > > we have half-open ranges.
> >
> > Yeah, after hitting send, I was also thinking that half-open is the more common
> > interval representation; it just wasn't how this code right here was written.
> > Will do.
> >
> > >
> > > > But now max_off can be below min_off, which again seems confusing.
> > >
> > > That's ok, the point here is to validate that we don't access stack
> > > out of bounds.
> > >
> > > >
> > > > What I'd really like to know is whether this whole zero access_size business
> > > > deserves to exist. Do you know what the point of verifying a zero-sized access
> > > > is exactly / could we turn 0-byte access into 1-byte accesses and
> > > > verify that instead?
> > > > Because then there'd be no more special case to consider.
> > > >
> > >
> > >
> > > I think zero is a natural case that can come up, at least with
> > > helpers. As we have ARG_CONST_SIZE_OR_ZERO. So yeah, I wouldn't treat
> > > zero-sized access as 1-byte access, that seems to be more confusing
> > > and potentially broken.
> >
> > Ack. Still, if you don't mind entertaining me further, two more questions:
> >
> > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> >
> > if (reg->umin_value == 0) {
> >   err = check_helper_mem_access(env, regno - 1, 0,
> >         zero_size_allowed,
> >         meta);
> >
> > followed by
> >
> > err = check_helper_mem_access(env, regno - 1,
> >       reg->umax_value,
> >       zero_size_allowed, meta);
> >
> > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> >
> > What's the point of the first check_helper_mem_access() call - the
> > zero-sized one
> > (given that we also have the second, broader, check)? Could it be
> > simply replaced by a
> >
> > if (reg->umin_value == 0 && !zero_sized_allowed)
> >     err = no_bueno;
> >
>
> Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> this, and kind of similar to the min_off/max_off discussion we had. So
> yes, I suspect the above simple and straightforward check would be
> much more meaningful and targeted.
>
> I gotta say that the reg->smin_value < 0 check is confusing, though,
> I'm not sure why we are mixing smin and umin/umax in this change...
>
> > ?
> >
> > 2. I believe you're saying that, if we were to verify zero-sized
> > accesses as 1-byte-sized accesses, we
> > might refuse some accesses that we permit today, and that wouldn't be
> > good. But what about
> > permitting zero-sized accesses with no further checks - i.e.
> > considering *any* pointer value to
> > be ok when the access_size == 0 ? Would that be bad? The question is,
> > morally, what checks are
> > important (if any) when the size of access is zero?
> > Or to phrase another way - when a helper is called with a zero access
> > size, do we expect the helper
> > to do anything with that pointer, or do we expect the helper to be a no-op?
>
> Helper itself might not be a no-op, but it should not write back to
> that pointer for sure. But I'd hate to have more special casing for
> zero-size read/write than necessary. So if we can structure the logic
> in a way that zero is a natural extension, I'd do that.

Well but the thing is, the way I see it, we *currently* have a lot of
special casing for
zero access_size - we carry this zero_sized_allowed argument to a
bunch of places.
So I was thinking that maybe we could get rid of all that by terminating
the verification of zero sized access in check_helper_mem_access() --
if access_size == 0, either return an error if !zero_sized_allowed,
otherwise return
success with no further verification.

>
> >
> > Thank you!
> >
> >
> > >
> > > > >
> > > > >
> > > > > 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!
> > > > >
> > > > >
> > > > > >         }
> > > > > >
> > > > > >         err = check_stack_slot_within_bounds(min_off, state, type);
> > > >
> > > > Will do.

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Mon, Dec 4, 2023 at 4:38 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> On Mon, Dec 4, 2023 at 6:59 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Dec 4, 2023 at 3:28 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> > >
> > > On Mon, Dec 4, 2023 at 5:05 PM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Mon, Dec 4, 2023 at 11:52 AM Andrei Matei <andreimatei1@gmail.com> wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > >
> > > > > > > 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 */
> > > > >
> > > > > Dealing with access_size == 0 indeed feels dubious to me, but I'm not entirely
> > > > > sure that your suggested code is better. min_off being inclusive and
> > > > > max_off being
> > > > > exclusive seems surprising. I'll do it if you want, I don't care too much.
> > > > > We could keep max_off exclusive, and still not call
> > > > > check_stack_slot_within_bounds() for it:
> > > > >
> > > > >  min_off = reg->smin_value + off;
> > > > >  max_off = reg->smax_value + off + access_size - 1;
> > > > >  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 */
> > > > >
> > > >
> > > > Yeah, we can do that. The reason I go for max_off being exclusive is
> > > > because using half-opened ranges is very convenient [start, end) (end
> > > > exclusive) is much more uniform and natural to handle compared to
> > > > closed [start, end] (end inclusive), in all sorts of checks, including
> > > > handling empty ranges. The math just works out better and more
> > > > naturally. And it's not like this will be the first time where in BPF
> > > > we have half-open ranges.
> > >
> > > Yeah, after hitting send, I was also thinking that half-open is the more common
> > > interval representation; it just wasn't how this code right here was written.
> > > Will do.
> > >
> > > >
> > > > > But now max_off can be below min_off, which again seems confusing.
> > > >
> > > > That's ok, the point here is to validate that we don't access stack
> > > > out of bounds.
> > > >
> > > > >
> > > > > What I'd really like to know is whether this whole zero access_size business
> > > > > deserves to exist. Do you know what the point of verifying a zero-sized access
> > > > > is exactly / could we turn 0-byte access into 1-byte accesses and
> > > > > verify that instead?
> > > > > Because then there'd be no more special case to consider.
> > > > >
> > > >
> > > >
> > > > I think zero is a natural case that can come up, at least with
> > > > helpers. As we have ARG_CONST_SIZE_OR_ZERO. So yeah, I wouldn't treat
> > > > zero-sized access as 1-byte access, that seems to be more confusing
> > > > and potentially broken.
> > >
> > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > >
> > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > >
> > > if (reg->umin_value == 0) {
> > >   err = check_helper_mem_access(env, regno - 1, 0,
> > >         zero_size_allowed,
> > >         meta);
> > >
> > > followed by
> > >
> > > err = check_helper_mem_access(env, regno - 1,
> > >       reg->umax_value,
> > >       zero_size_allowed, meta);
> > >
> > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > >
> > > What's the point of the first check_helper_mem_access() call - the
> > > zero-sized one
> > > (given that we also have the second, broader, check)? Could it be
> > > simply replaced by a
> > >
> > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > >     err = no_bueno;
> > >
> >
> > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > this, and kind of similar to the min_off/max_off discussion we had. So
> > yes, I suspect the above simple and straightforward check would be
> > much more meaningful and targeted.
> >
> > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > I'm not sure why we are mixing smin and umin/umax in this change...
> >
> > > ?
> > >
> > > 2. I believe you're saying that, if we were to verify zero-sized
> > > accesses as 1-byte-sized accesses, we
> > > might refuse some accesses that we permit today, and that wouldn't be
> > > good. But what about
> > > permitting zero-sized accesses with no further checks - i.e.
> > > considering *any* pointer value to
> > > be ok when the access_size == 0 ? Would that be bad? The question is,
> > > morally, what checks are
> > > important (if any) when the size of access is zero?
> > > Or to phrase another way - when a helper is called with a zero access
> > > size, do we expect the helper
> > > to do anything with that pointer, or do we expect the helper to be a no-op?
> >
> > Helper itself might not be a no-op, but it should not write back to
> > that pointer for sure. But I'd hate to have more special casing for
> > zero-size read/write than necessary. So if we can structure the logic
> > in a way that zero is a natural extension, I'd do that.
>
> Well but the thing is, the way I see it, we *currently* have a lot of
> special casing for
> zero access_size - we carry this zero_sized_allowed argument to a
> bunch of places.
> So I was thinking that maybe we could get rid of all that by terminating
> the verification of zero sized access in check_helper_mem_access() --
> if access_size == 0, either return an error if !zero_sized_allowed,
> otherwise return
> success with no further verification.
>

Maybe, but let's do it one step at a time. Let's fix the current
issue, supporting max_off with zero seems easy, let's do that for now?
We can have a separate patch/patch set to simplify zero size
arguments.


> >
> > >
> > > Thank you!
> > >
> > >
> > > >
> > > > > >
> > > > > >
> > > > > > 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!
> > > > > >
> > > > > >
> > > > > > >         }
> > > > > > >
> > > > > > >         err = check_stack_slot_within_bounds(min_off, state, type);
> > > > >
> > > > > Will do.

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

On Mon, Dec 4, 2023 at 1:32 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Dec 4, 2023 at 7:39 AM Andrei Matei <andreimatei1@gmail.com> 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@gmail.com>
> > Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> > Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/
> > Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> > ---
> >  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
> >

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

[...]

> >
> > Ack. Still, if you don't mind entertaining me further, two more questions:
> >
> > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> >
> > if (reg->umin_value == 0) {
> >   err = check_helper_mem_access(env, regno - 1, 0,
> >         zero_size_allowed,
> >         meta);
> >
> > followed by
> >
> > err = check_helper_mem_access(env, regno - 1,
> >       reg->umax_value,
> >       zero_size_allowed, meta);
> >
> > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> >
> > What's the point of the first check_helper_mem_access() call - the
> > zero-sized one
> > (given that we also have the second, broader, check)? Could it be
> > simply replaced by a
> >
> > if (reg->umin_value == 0 && !zero_sized_allowed)
> >     err = no_bueno;
> >
>
> Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> this, and kind of similar to the min_off/max_off discussion we had. So
> yes, I suspect the above simple and straightforward check would be
> much more meaningful and targeted.

I plan on trying this in a bit; sounds like you're encouraging it.

>
> I gotta say that the reg->smin_value < 0 check is confusing, though,
> I'm not sure why we are mixing smin and umin/umax in this change...

When you say "in this change", you mean in the existing code, yeah?  I'm not
familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
(the condition that the function tests first) implies that
`reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
so, are you saying that check_mem_size_reg() should exclusively use smin/smax?


[...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> [...]
>
> > >
> > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > >
> > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > >
> > > if (reg->umin_value == 0) {
> > >   err = check_helper_mem_access(env, regno - 1, 0,
> > >         zero_size_allowed,
> > >         meta);
> > >
> > > followed by
> > >
> > > err = check_helper_mem_access(env, regno - 1,
> > >       reg->umax_value,
> > >       zero_size_allowed, meta);
> > >
> > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > >
> > > What's the point of the first check_helper_mem_access() call - the
> > > zero-sized one
> > > (given that we also have the second, broader, check)? Could it be
> > > simply replaced by a
> > >
> > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > >     err = no_bueno;
> > >
> >
> > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > this, and kind of similar to the min_off/max_off discussion we had. So
> > yes, I suspect the above simple and straightforward check would be
> > much more meaningful and targeted.
>
> I plan on trying this in a bit; sounds like you're encouraging it.
>
> >
> > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > I'm not sure why we are mixing smin and umin/umax in this change...
>
> When you say "in this change", you mean in the existing code, yeah?  I'm not

Yeah, sorry, words are hard. It's clearly a question about pre-existing code.

> familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> (the condition that the function tests first) implies that
> `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing

this is probably true most of the time, but knowing how tricky this
range tracking is, there is non-zero chance that this is not always
true. Which is why I'm a bit confused why we are freely intermixing
signed/unsigned range in this code.

> smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
>

I'd like to hear from Kumar on what was the intent before suggesting
changing anything.

>
> [...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Kumar Kartikeya Dwivedi]

On Fri, 8 Dec 2023 at 23:15, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> >
> > [...]
> >
> > > >
> > > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > > >
> > > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > > >
> > > > if (reg->umin_value == 0) {
> > > >   err = check_helper_mem_access(env, regno - 1, 0,
> > > >         zero_size_allowed,
> > > >         meta);
> > > >
> > > > followed by
> > > >
> > > > err = check_helper_mem_access(env, regno - 1,
> > > >       reg->umax_value,
> > > >       zero_size_allowed, meta);
> > > >
> > > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > > >
> > > > What's the point of the first check_helper_mem_access() call - the
> > > > zero-sized one
> > > > (given that we also have the second, broader, check)? Could it be
> > > > simply replaced by a
> > > >
> > > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > > >     err = no_bueno;
> > > >
> > >
> > > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > > this, and kind of similar to the min_off/max_off discussion we had. So
> > > yes, I suspect the above simple and straightforward check would be
> > > much more meaningful and targeted.
> >
> > I plan on trying this in a bit; sounds like you're encouraging it.
> >
> > >
> > > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > > I'm not sure why we are mixing smin and umin/umax in this change...
> >
> > When you say "in this change", you mean in the existing code, yeah?  I'm not
>
> Yeah, sorry, words are hard. It's clearly a question about pre-existing code.
>
> > familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> > (the condition that the function tests first) implies that
> > `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
>
> this is probably true most of the time, but knowing how tricky this
> range tracking is, there is non-zero chance that this is not always
> true. Which is why I'm a bit confused why we are freely intermixing
> signed/unsigned range in this code.
>
> > smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> > so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
> >
>
> I'd like to hear from Kumar on what was the intent before suggesting
> changing anything.

So this was not originally from me, I just happened to move it around
when adding support for this to kfuncs into a shared helper (if you
look at the git blame), it's hard for me to comment on the original
intent, I would know as much as anyone else.

But to helpful, I digged around a bit and found the original patch
adding this snippet:

06c1c049721a ("bpf: allow helpers access to variable memory")

It seems the main reason to add that < 0 check on min value was to
tell the user in the specific case where a spilled value is reloaded
from stack that they need to mask it again using bitwise operations,
because back then a spilled constant when reloaded would become
unknown, and when passed as a parameter to a helper the program would
be rejected with a weird error trying to access size greater than the
user specified in C.

Now this change predates the signed/unsigned distinction, that came in:

b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")

That changes reg->min_value to reg->smin_value, the < 0 comparison
only makes sense for that.
Since then that part of the code has stayed the same.

So I think it would probably be better to just use smin/smax as you
discussed above upthread, also since the BPF_MAX_VAR_SIZE is INT_MAX,
so it shouldn't be a problem.

>
> >
> > [...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Fri, Dec 8, 2023 at 6:46 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
>
> On Fri, 8 Dec 2023 at 23:15, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
> >
> > On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> > >
> > > [...]
> > >
> > > > >
> > > > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > > > >
> > > > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > > > >
> > > > > if (reg->umin_value == 0) {
> > > > >   err = check_helper_mem_access(env, regno - 1, 0,
> > > > >         zero_size_allowed,
> > > > >         meta);
> > > > >
> > > > > followed by
> > > > >
> > > > > err = check_helper_mem_access(env, regno - 1,
> > > > >       reg->umax_value,
> > > > >       zero_size_allowed, meta);
> > > > >
> > > > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > > > >
> > > > > What's the point of the first check_helper_mem_access() call - the
> > > > > zero-sized one
> > > > > (given that we also have the second, broader, check)? Could it be
> > > > > simply replaced by a
> > > > >
> > > > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > > > >     err = no_bueno;
> > > > >
> > > >
> > > > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > > > this, and kind of similar to the min_off/max_off discussion we had. So
> > > > yes, I suspect the above simple and straightforward check would be
> > > > much more meaningful and targeted.
> > >
> > > I plan on trying this in a bit; sounds like you're encouraging it.
> > >
> > > >
> > > > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > > > I'm not sure why we are mixing smin and umin/umax in this change...
> > >
> > > When you say "in this change", you mean in the existing code, yeah?  I'm not
> >
> > Yeah, sorry, words are hard. It's clearly a question about pre-existing code.
> >
> > > familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> > > (the condition that the function tests first) implies that
> > > `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
> >
> > this is probably true most of the time, but knowing how tricky this
> > range tracking is, there is non-zero chance that this is not always
> > true. Which is why I'm a bit confused why we are freely intermixing
> > signed/unsigned range in this code.
> >
> > > smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> > > so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
> > >
> >
> > I'd like to hear from Kumar on what was the intent before suggesting
> > changing anything.
>
> So this was not originally from me, I just happened to move it around
> when adding support for this to kfuncs into a shared helper (if you
> look at the git blame), it's hard for me to comment on the original
> intent, I would know as much as anyone else.
>
> But to helpful, I digged around a bit and found the original patch
> adding this snippet:
>
> 06c1c049721a ("bpf: allow helpers access to variable memory")
>
> It seems the main reason to add that < 0 check on min value was to
> tell the user in the specific case where a spilled value is reloaded
> from stack that they need to mask it again using bitwise operations,
> because back then a spilled constant when reloaded would become
> unknown, and when passed as a parameter to a helper the program would
> be rejected with a weird error trying to access size greater than the
> user specified in C.
>
> Now this change predates the signed/unsigned distinction, that came in:
>
> b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
>
> That changes reg->min_value to reg->smin_value, the < 0 comparison
> only makes sense for that.
> Since then that part of the code has stayed the same.
>
> So I think it would probably be better to just use smin/smax as you
> discussed above upthread, also since the BPF_MAX_VAR_SIZE is INT_MAX,
> so it shouldn't be a problem.

Great, thanks for the code archeology tour, Kumar! :)

>
> >
> > >
> > > [...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

On Fri, Dec 8, 2023 at 9:46 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
>
> On Fri, 8 Dec 2023 at 23:15, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
> >
> > On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> > >
> > > [...]
> > >
> > > > >
> > > > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > > > >
> > > > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > > > >
> > > > > if (reg->umin_value == 0) {
> > > > >   err = check_helper_mem_access(env, regno - 1, 0,
> > > > >         zero_size_allowed,
> > > > >         meta);
> > > > >
> > > > > followed by
> > > > >
> > > > > err = check_helper_mem_access(env, regno - 1,
> > > > >       reg->umax_value,
> > > > >       zero_size_allowed, meta);
> > > > >
> > > > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > > > >
> > > > > What's the point of the first check_helper_mem_access() call - the
> > > > > zero-sized one
> > > > > (given that we also have the second, broader, check)? Could it be
> > > > > simply replaced by a
> > > > >
> > > > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > > > >     err = no_bueno;
> > > > >
> > > >
> > > > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > > > this, and kind of similar to the min_off/max_off discussion we had. So
> > > > yes, I suspect the above simple and straightforward check would be
> > > > much more meaningful and targeted.
> > >
> > > I plan on trying this in a bit; sounds like you're encouraging it.
> > >
> > > >
> > > > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > > > I'm not sure why we are mixing smin and umin/umax in this change...
> > >
> > > When you say "in this change", you mean in the existing code, yeah?  I'm not
> >
> > Yeah, sorry, words are hard. It's clearly a question about pre-existing code.
> >
> > > familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> > > (the condition that the function tests first) implies that
> > > `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
> >
> > this is probably true most of the time, but knowing how tricky this
> > range tracking is, there is non-zero chance that this is not always
> > true. Which is why I'm a bit confused why we are freely intermixing
> > signed/unsigned range in this code.
> >
> > > smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> > > so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
> > >
> >
> > I'd like to hear from Kumar on what was the intent before suggesting
> > changing anything.
>
> So this was not originally from me, I just happened to move it around
> when adding support for this to kfuncs into a shared helper (if you
> look at the git blame), it's hard for me to comment on the original
> intent, I would know as much as anyone else.
>
> But to helpful, I digged around a bit and found the original patch
> adding this snippet:
>
> 06c1c049721a ("bpf: allow helpers access to variable memory")
>
> It seems the main reason to add that < 0 check on min value was to
> tell the user in the specific case where a spilled value is reloaded
> from stack that they need to mask it again using bitwise operations,
> because back then a spilled constant when reloaded would become
> unknown, and when passed as a parameter to a helper the program would
> be rejected with a weird error trying to access size greater than the
> user specified in C.
>
> Now this change predates the signed/unsigned distinction, that came in:
>
> b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
>
> That changes reg->min_value to reg->smin_value, the < 0 comparison
> only makes sense for that.
> Since then that part of the code has stayed the same.
>
> So I think it would probably be better to just use smin/smax as you
> discussed above upthread, also since the BPF_MAX_VAR_SIZE is INT_MAX,
> so it shouldn't be a problem.

Thank you for spelunking, Kumar!
There were two discussions upthread:
1) whether the 0-size check_helper_mem_access() call in
check_mem_size_reg() can be drastically simplified
2) whether the mixed use of smin with umin/umax makes sense.

It seems that we've come up empty-handed on a good reasoning
for 1). I have a patch that simplifies it AND also improves
error messages as a result. I'm inclined to send it for your
consideration, Andrii, if that's cool, as you also didn't
seem to like the current code.

About 2) -- the current mixing of smin/umin/umax actually
makes sense to me.  I'd rationalize the (smin < 0) check as
"does this value *look* like a negative value? If so,
opportunistically give the user a nice error message". Even
if the value did not actually come from a signed variable,
but instead came for a very large unsigned, the program
shouldn't verify anyway, so it's no big deal if the negative
interpretation is erroneous. After that check, the value is
exclusively treated as unsigned, since the size argument for
which it is intended is unsigned.
So, I think you can argue either way for the combinations of
signed/unsigned checks that could be done, but I personally
am not inclined to change the current code.


>
> >
> > >
> > > [...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Kumar Kartikeya Dwivedi]

On Sun, 10 Dec 2023 at 23:46, Andrei Matei <andreimatei1@gmail.com> wrote:
>
> On Fri, Dec 8, 2023 at 9:46 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
> >
> > On Fri, 8 Dec 2023 at 23:15, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> > > >
> > > > [...]
> > > >
> > > > > >
> > > > > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > > > > >
> > > > > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > > > > >
> > > > > > if (reg->umin_value == 0) {
> > > > > >   err = check_helper_mem_access(env, regno - 1, 0,
> > > > > >         zero_size_allowed,
> > > > > >         meta);
> > > > > >
> > > > > > followed by
> > > > > >
> > > > > > err = check_helper_mem_access(env, regno - 1,
> > > > > >       reg->umax_value,
> > > > > >       zero_size_allowed, meta);
> > > > > >
> > > > > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > > > > >
> > > > > > What's the point of the first check_helper_mem_access() call - the
> > > > > > zero-sized one
> > > > > > (given that we also have the second, broader, check)? Could it be
> > > > > > simply replaced by a
> > > > > >
> > > > > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > > > > >     err = no_bueno;
> > > > > >
> > > > >
> > > > > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > > > > this, and kind of similar to the min_off/max_off discussion we had. So
> > > > > yes, I suspect the above simple and straightforward check would be
> > > > > much more meaningful and targeted.
> > > >
> > > > I plan on trying this in a bit; sounds like you're encouraging it.
> > > >
> > > > >
> > > > > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > > > > I'm not sure why we are mixing smin and umin/umax in this change...
> > > >
> > > > When you say "in this change", you mean in the existing code, yeah?  I'm not
> > >
> > > Yeah, sorry, words are hard. It's clearly a question about pre-existing code.
> > >
> > > > familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> > > > (the condition that the function tests first) implies that
> > > > `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
> > >
> > > this is probably true most of the time, but knowing how tricky this
> > > range tracking is, there is non-zero chance that this is not always
> > > true. Which is why I'm a bit confused why we are freely intermixing
> > > signed/unsigned range in this code.
> > >
> > > > smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> > > > so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
> > > >
> > >
> > > I'd like to hear from Kumar on what was the intent before suggesting
> > > changing anything.
> >
> > So this was not originally from me, I just happened to move it around
> > when adding support for this to kfuncs into a shared helper (if you
> > look at the git blame), it's hard for me to comment on the original
> > intent, I would know as much as anyone else.
> >
> > But to helpful, I digged around a bit and found the original patch
> > adding this snippet:
> >
> > 06c1c049721a ("bpf: allow helpers access to variable memory")
> >
> > It seems the main reason to add that < 0 check on min value was to
> > tell the user in the specific case where a spilled value is reloaded
> > from stack that they need to mask it again using bitwise operations,
> > because back then a spilled constant when reloaded would become
> > unknown, and when passed as a parameter to a helper the program would
> > be rejected with a weird error trying to access size greater than the
> > user specified in C.
> >
> > Now this change predates the signed/unsigned distinction, that came in:
> >
> > b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
> >
> > That changes reg->min_value to reg->smin_value, the < 0 comparison
> > only makes sense for that.
> > Since then that part of the code has stayed the same.
> >
> > So I think it would probably be better to just use smin/smax as you
> > discussed above upthread, also since the BPF_MAX_VAR_SIZE is INT_MAX,
> > so it shouldn't be a problem.
>
> Thank you for spelunking, Kumar!
> There were two discussions upthread:
> 1) whether the 0-size check_helper_mem_access() call in
> check_mem_size_reg() can be drastically simplified
> 2) whether the mixed use of smin with umin/umax makes sense.
>
> It seems that we've come up empty-handed on a good reasoning
> for 1). I have a patch that simplifies it AND also improves
> error messages as a result. I'm inclined to send it for your
> consideration, Andrii, if that's cool, as you also didn't
> seem to like the current code.
>

While that's true, I think it should probably go into
check_helper_mem_access instead of being duplicated for handlers of
each switch statement.
It seems one of them (for PTR_TO_MAP_KEY) hardcodes it regardless of
what's passed in, and there's a special case of register_is_null which
is permitted.

So it might be better to unify the handling in check_helper_mem_access
instead of its callers. Just my $0.02.

> About 2) -- the current mixing of smin/umin/umax actually
> makes sense to me.  I'd rationalize the (smin < 0) check as
> "does this value *look* like a negative value? If so,
> opportunistically give the user a nice error message". Even
> if the value did not actually come from a signed variable,
> but instead came for a very large unsigned, the program
> shouldn't verify anyway, so it's no big deal if the negative
> interpretation is erroneous. After that check, the value is
> exclusively treated as unsigned, since the size argument for
> which it is intended is unsigned.
> So, I think you can argue either way for the combinations of
> signed/unsigned checks that could be done, but I personally
> am not inclined to change the current code.
>

I think based on the thread it would be better to atleast comments
explaining all this, even if in the end we don't decide to touch it.

>
> [...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

On Sun, Dec 10, 2023 at 6:13 PM Kumar Kartikeya Dwivedi
<memxor@gmail.com> wrote:
>
> On Sun, 10 Dec 2023 at 23:46, Andrei Matei <andreimatei1@gmail.com> wrote:
> >
> > On Fri, Dec 8, 2023 at 9:46 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
> > >
> > > On Fri, 8 Dec 2023 at 23:15, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > >
> > > > > > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > > > > > >
> > > > > > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > > > > > >
> > > > > > > if (reg->umin_value == 0) {
> > > > > > >   err = check_helper_mem_access(env, regno - 1, 0,
> > > > > > >         zero_size_allowed,
> > > > > > >         meta);
> > > > > > >
> > > > > > > followed by
> > > > > > >
> > > > > > > err = check_helper_mem_access(env, regno - 1,
> > > > > > >       reg->umax_value,
> > > > > > >       zero_size_allowed, meta);
> > > > > > >
> > > > > > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > > > > > >
> > > > > > > What's the point of the first check_helper_mem_access() call - the
> > > > > > > zero-sized one
> > > > > > > (given that we also have the second, broader, check)? Could it be
> > > > > > > simply replaced by a
> > > > > > >
> > > > > > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > > > > > >     err = no_bueno;
> > > > > > >
> > > > > >
> > > > > > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > > > > > this, and kind of similar to the min_off/max_off discussion we had. So
> > > > > > yes, I suspect the above simple and straightforward check would be
> > > > > > much more meaningful and targeted.
> > > > >
> > > > > I plan on trying this in a bit; sounds like you're encouraging it.
> > > > >
> > > > > >
> > > > > > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > > > > > I'm not sure why we are mixing smin and umin/umax in this change...
> > > > >
> > > > > When you say "in this change", you mean in the existing code, yeah?  I'm not
> > > >
> > > > Yeah, sorry, words are hard. It's clearly a question about pre-existing code.
> > > >
> > > > > familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> > > > > (the condition that the function tests first) implies that
> > > > > `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
> > > >
> > > > this is probably true most of the time, but knowing how tricky this
> > > > range tracking is, there is non-zero chance that this is not always
> > > > true. Which is why I'm a bit confused why we are freely intermixing
> > > > signed/unsigned range in this code.
> > > >
> > > > > smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> > > > > so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
> > > > >
> > > >
> > > > I'd like to hear from Kumar on what was the intent before suggesting
> > > > changing anything.
> > >
> > > So this was not originally from me, I just happened to move it around
> > > when adding support for this to kfuncs into a shared helper (if you
> > > look at the git blame), it's hard for me to comment on the original
> > > intent, I would know as much as anyone else.
> > >
> > > But to helpful, I digged around a bit and found the original patch
> > > adding this snippet:
> > >
> > > 06c1c049721a ("bpf: allow helpers access to variable memory")
> > >
> > > It seems the main reason to add that < 0 check on min value was to
> > > tell the user in the specific case where a spilled value is reloaded
> > > from stack that they need to mask it again using bitwise operations,
> > > because back then a spilled constant when reloaded would become
> > > unknown, and when passed as a parameter to a helper the program would
> > > be rejected with a weird error trying to access size greater than the
> > > user specified in C.
> > >
> > > Now this change predates the signed/unsigned distinction, that came in:
> > >
> > > b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
> > >
> > > That changes reg->min_value to reg->smin_value, the < 0 comparison
> > > only makes sense for that.
> > > Since then that part of the code has stayed the same.
> > >
> > > So I think it would probably be better to just use smin/smax as you
> > > discussed above upthread, also since the BPF_MAX_VAR_SIZE is INT_MAX,
> > > so it shouldn't be a problem.
> >
> > Thank you for spelunking, Kumar!
> > There were two discussions upthread:
> > 1) whether the 0-size check_helper_mem_access() call in
> > check_mem_size_reg() can be drastically simplified
> > 2) whether the mixed use of smin with umin/umax makes sense.
> >
> > It seems that we've come up empty-handed on a good reasoning
> > for 1). I have a patch that simplifies it AND also improves
> > error messages as a result. I'm inclined to send it for your
> > consideration, Andrii, if that's cool, as you also didn't
> > seem to like the current code.
> >
>
> While that's true, I think it should probably go into
> check_helper_mem_access instead of being duplicated for handlers of
> each switch statement.
> It seems one of them (for PTR_TO_MAP_KEY) hardcodes it regardless of
> what's passed in, and there's a special case of register_is_null which
> is permitted.
>
> So it might be better to unify the handling in check_helper_mem_access
> instead of its callers. Just my $0.02.

My initial focus is getting check_mem_size_reg() to not call
check_helper_mem_access() twice. That's what patch [1] does.

Then, I tend to agree with you that
check_helper_mem_access() forwarding zero_size_allowed() to
a bunch of switch arms seems unnecessary; it also bothered
me. I did try to do something about it for a bit - terminate
the handling of zero_sized_allowed somewhere - but the thing
is that the utilities used in that switch (e.g.
check_mem_region_access()) are also called in other places,
with both true and false for zero_sized_allowed. So I didn't
immediately come up with something better and gave up for
now. But if you have throughts, let's take it to the new
patch I'd say.

[1] https://lore.kernel.org/bpf/20231210225536.70322-1-andreimatei1@gmail.com/


>
> > About 2) -- the current mixing of smin/umin/umax actually
> > makes sense to me.  I'd rationalize the (smin < 0) check as
> > "does this value *look* like a negative value? If so,
> > opportunistically give the user a nice error message". Even
> > if the value did not actually come from a signed variable,
> > but instead came for a very large unsigned, the program
> > shouldn't verify anyway, so it's no big deal if the negative
> > interpretation is erroneous. After that check, the value is
> > exclusively treated as unsigned, since the size argument for
> > which it is intended is unsigned.
> > So, I think you can argue either way for the combinations of
> > signed/unsigned checks that could be done, but I personally
> > am not inclined to change the current code.
> >
>
> I think based on the thread it would be better to atleast comments
> explaining all this, even if in the end we don't decide to touch it.

Yeah... But comment what exactly? I could put a comment on
the (smin_value < 0) check saying something "if the value
looks negative, assume that it came from a signed variable
and give a helpful error message", and imply that the value
should be treated as unsigned from that moment on. But then
it gets confusing when, a few lines down,
check_helper_mem_access() takes the size as `int` instead of
`u32`. So the truth I'm not entirely sure what to say, plus
Andrii might have other ideas about how the bike shed should
be colored. If we build more consensus though, I'm all about
adding comments.


>
> >
> > [...]

Re: [PATCH bpf V2 1/1] bpf: fix verification of indirect var-off stack access

[Andrii Nakryiko]

On Sun, Dec 10, 2023 at 5:24 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> On Sun, Dec 10, 2023 at 6:13 PM Kumar Kartikeya Dwivedi
> <memxor@gmail.com> wrote:
> >
> > On Sun, 10 Dec 2023 at 23:46, Andrei Matei <andreimatei1@gmail.com> wrote:
> > >
> > > On Fri, Dec 8, 2023 at 9:46 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
> > > >
> > > > On Fri, 8 Dec 2023 at 23:15, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > On Thu, Dec 7, 2023 at 7:23 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> > > > > >
> > > > > > [...]
> > > > > >
> > > > > > > >
> > > > > > > > Ack. Still, if you don't mind entertaining me further, two more questions:
> > > > > > > >
> > > > > > > > 1. What do you make of the code in check_mem_size_reg() [1] where we do
> > > > > > > >
> > > > > > > > if (reg->umin_value == 0) {
> > > > > > > >   err = check_helper_mem_access(env, regno - 1, 0,
> > > > > > > >         zero_size_allowed,
> > > > > > > >         meta);
> > > > > > > >
> > > > > > > > followed by
> > > > > > > >
> > > > > > > > err = check_helper_mem_access(env, regno - 1,
> > > > > > > >       reg->umax_value,
> > > > > > > >       zero_size_allowed, meta);
> > > > > > > >
> > > > > > > > [1] https://github.com/torvalds/linux/blob/bee0e7762ad2c6025b9f5245c040fcc36ef2bde8/kernel/bpf/verifier.c#L7486-L7489
> > > > > > > >
> > > > > > > > What's the point of the first check_helper_mem_access() call - the
> > > > > > > > zero-sized one
> > > > > > > > (given that we also have the second, broader, check)? Could it be
> > > > > > > > simply replaced by a
> > > > > > > >
> > > > > > > > if (reg->umin_value == 0 && !zero_sized_allowed)
> > > > > > > >     err = no_bueno;
> > > > > > > >
> > > > > > >
> > > > > > > Maybe Kumar (cc'ed) can chime in as well, but I suspect that's exactly
> > > > > > > this, and kind of similar to the min_off/max_off discussion we had. So
> > > > > > > yes, I suspect the above simple and straightforward check would be
> > > > > > > much more meaningful and targeted.
> > > > > >
> > > > > > I plan on trying this in a bit; sounds like you're encouraging it.
> > > > > >
> > > > > > >
> > > > > > > I gotta say that the reg->smin_value < 0 check is confusing, though,
> > > > > > > I'm not sure why we are mixing smin and umin/umax in this change...
> > > > > >
> > > > > > When you say "in this change", you mean in the existing code, yeah?  I'm not
> > > > >
> > > > > Yeah, sorry, words are hard. It's clearly a question about pre-existing code.
> > > > >
> > > > > > familiar enough with the smin/umin tracking to tell if `reg->smin_value >= 0`
> > > > > > (the condition that the function tests first) implies that
> > > > > > `reg->smin_value == reg->umin_value` (i.e. the fact that we're currently mixing
> > > > >
> > > > > this is probably true most of the time, but knowing how tricky this
> > > > > range tracking is, there is non-zero chance that this is not always
> > > > > true. Which is why I'm a bit confused why we are freely intermixing
> > > > > signed/unsigned range in this code.
> > > > >
> > > > > > smin/umin in check_mem_size_reg() is confusing, but benign).  Is that true? If
> > > > > > so, are you saying that check_mem_size_reg() should exclusively use smin/smax?
> > > > > >
> > > > >
> > > > > I'd like to hear from Kumar on what was the intent before suggesting
> > > > > changing anything.
> > > >
> > > > So this was not originally from me, I just happened to move it around
> > > > when adding support for this to kfuncs into a shared helper (if you
> > > > look at the git blame), it's hard for me to comment on the original
> > > > intent, I would know as much as anyone else.
> > > >
> > > > But to helpful, I digged around a bit and found the original patch
> > > > adding this snippet:
> > > >
> > > > 06c1c049721a ("bpf: allow helpers access to variable memory")
> > > >
> > > > It seems the main reason to add that < 0 check on min value was to
> > > > tell the user in the specific case where a spilled value is reloaded
> > > > from stack that they need to mask it again using bitwise operations,
> > > > because back then a spilled constant when reloaded would become
> > > > unknown, and when passed as a parameter to a helper the program would
> > > > be rejected with a weird error trying to access size greater than the
> > > > user specified in C.
> > > >
> > > > Now this change predates the signed/unsigned distinction, that came in:
> > > >
> > > > b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
> > > >
> > > > That changes reg->min_value to reg->smin_value, the < 0 comparison
> > > > only makes sense for that.
> > > > Since then that part of the code has stayed the same.
> > > >
> > > > So I think it would probably be better to just use smin/smax as you
> > > > discussed above upthread, also since the BPF_MAX_VAR_SIZE is INT_MAX,
> > > > so it shouldn't be a problem.
> > >
> > > Thank you for spelunking, Kumar!
> > > There were two discussions upthread:
> > > 1) whether the 0-size check_helper_mem_access() call in
> > > check_mem_size_reg() can be drastically simplified
> > > 2) whether the mixed use of smin with umin/umax makes sense.
> > >
> > > It seems that we've come up empty-handed on a good reasoning
> > > for 1). I have a patch that simplifies it AND also improves
> > > error messages as a result. I'm inclined to send it for your
> > > consideration, Andrii, if that's cool, as you also didn't
> > > seem to like the current code.
> > >
> >
> > While that's true, I think it should probably go into
> > check_helper_mem_access instead of being duplicated for handlers of
> > each switch statement.
> > It seems one of them (for PTR_TO_MAP_KEY) hardcodes it regardless of
> > what's passed in, and there's a special case of register_is_null which
> > is permitted.
> >
> > So it might be better to unify the handling in check_helper_mem_access
> > instead of its callers. Just my $0.02.
>
> My initial focus is getting check_mem_size_reg() to not call
> check_helper_mem_access() twice. That's what patch [1] does.
>
> Then, I tend to agree with you that
> check_helper_mem_access() forwarding zero_size_allowed() to
> a bunch of switch arms seems unnecessary; it also bothered
> me. I did try to do something about it for a bit - terminate
> the handling of zero_sized_allowed somewhere - but the thing
> is that the utilities used in that switch (e.g.
> check_mem_region_access()) are also called in other places,
> with both true and false for zero_sized_allowed. So I didn't
> immediately come up with something better and gave up for
> now. But if you have throughts, let's take it to the new
> patch I'd say.
>
> [1] https://lore.kernel.org/bpf/20231210225536.70322-1-andreimatei1@gmail.com/
>
>
> >
> > > About 2) -- the current mixing of smin/umin/umax actually
> > > makes sense to me.  I'd rationalize the (smin < 0) check as
> > > "does this value *look* like a negative value? If so,
> > > opportunistically give the user a nice error message". Even
> > > if the value did not actually come from a signed variable,
> > > but instead came for a very large unsigned, the program
> > > shouldn't verify anyway, so it's no big deal if the negative
> > > interpretation is erroneous. After that check, the value is
> > > exclusively treated as unsigned, since the size argument for
> > > which it is intended is unsigned.
> > > So, I think you can argue either way for the combinations of
> > > signed/unsigned checks that could be done, but I personally
> > > am not inclined to change the current code.
> > >
> >
> > I think based on the thread it would be better to atleast comments
> > explaining all this, even if in the end we don't decide to touch it.
>
> Yeah... But comment what exactly? I could put a comment on
> the (smin_value < 0) check saying something "if the value
> looks negative, assume that it came from a signed variable
> and give a helpful error message", and imply that the value
> should be treated as unsigned from that moment on. But then
> it gets confusing when, a few lines down,
> check_helper_mem_access() takes the size as `int` instead of
> `u32`. So the truth I'm not entirely sure what to say, plus
> Andrii might have other ideas about how the bike shed should
> be colored. If we build more consensus though, I'm all about
> adding comments.

I'm a bit too lazy to go figure this out right now, but my general
thinking regarding smin/umin checks is that I wouldn't mix them, it's
super confusing. Then the question of smin/smax vs umin/umax comes
down to how operation/instruction is interpreting the value of the
register. If it's treated as signed value, then consistently use
smin/smax for all the checks (umin/umax are irrelevant), if it's
treated as unsigned, then do just umin/umax.

I don't know what this specific logic uses, signed or unsigned, but we
should check and make it consistent.

If we want to be "helpful" in detecting potential situations with
under/overflow, then we can express that within the same numeric
domain with appropriate range checks.

Final rant. If we can avoid assuming relationships between umin/umax
and smin/smax ranges, we should. It's a tricky part of verifier code
(though which one isn't, right?), so the fewer assumptions - the
better.

>
>
> >
> > >
> > > [...]