bpf: fix verification of indirect var-off stack access

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 <[email protected]>

Fixes 01f810ace9ed3 ("bpf: Allow variable-offset stack access")

Closes https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/ open here

Signed-off-by Andrei Matei <[email protected]>

---
 kernel/bpf/verifier.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c +0 -1

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

2.40.1

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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!

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

        }
 
        err = check_stack_slot_within_bounds(min_off, state, type);

[...]

Quoted 27 lines

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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.

Quoted 7 lines

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.

Quoted 14 lines

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!

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

        }
 
        err = check_stack_slot_within_bounds(min_off, state, type);

Will do.

Quoted 45 lines · Andrei Matei

[...]

Quoted 27 lines

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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.

Quoted 7 lines

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:

Quoted 6 lines

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.

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 17 lines

Quoted 15 lines

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!

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

        }
 
        err = check_stack_slot_within_bounds(min_off, state, type);

Will do.

Quoted 54 lines · Andrii Nakryiko

Quoted 45 lines · Andrei Matei

[...]

Quoted 27 lines

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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.

Quoted 7 lines

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:

Quoted 6 lines

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

Quoted 7 lines

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.

Quoted 15 lines

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 4 lines

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!

Quoted 17 lines

Quoted 17 lines

Quoted 15 lines

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!

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

        }
 
        err = check_stack_slot_within_bounds(min_off, state, type);

Will do.

Quoted 106 lines · Andrei Matei

Quoted 54 lines · Andrii Nakryiko

Quoted 45 lines · Andrei Matei

[...]

Quoted 27 lines

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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.

Quoted 7 lines

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:

Quoted 6 lines

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

Quoted 7 lines

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.

Quoted 15 lines

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 4 lines

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

Quoted 8 lines

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...

Quoted 14 lines

?

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.

Quoted 22 lines

Thank you!

Quoted 17 lines

Quoted 17 lines

Quoted 15 lines

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!

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

        }
 
        err = check_stack_slot_within_bounds(min_off, state, type);

Will do.

Quoted 140 lines · Andrii Nakryiko

Quoted 106 lines · Andrei Matei

Quoted 54 lines · Andrii Nakryiko

Quoted 45 lines · Andrei Matei

[...]

Quoted 27 lines

Quoted 6 lines

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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.

Quoted 7 lines

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:

Quoted 6 lines

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

Quoted 7 lines

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.

Quoted 15 lines

Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 4 lines

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

Quoted 8 lines

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...

Quoted 14 lines

?

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?

Quoted 4 lines

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.

Quoted 22 lines

Quoted 22 lines

Thank you!

Quoted 17 lines

Quoted 17 lines

Quoted 15 lines

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!

Quoted 3 lines

kernel/bpf/verifier.c +0 -0

        }
 
        err = check_stack_slot_within_bounds(min_off, state, type);

Will do.

Quoted 23 lines

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

Quoted 3 lines

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...

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 3 lines

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?

[...]

Quoted 35 lines · Andrei Matei

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

[...]

Quoted 56 lines · Andrii Nakryiko

Quoted 35 lines · Andrei Matei

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 6 lines

Quoted 3 lines

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.

Quoted 4 lines

Quoted 4 lines

[...]

Quoted 56 lines · Andrii Nakryiko

Quoted 35 lines · Andrei Matei

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 6 lines

Quoted 3 lines

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.

Quoted 4 lines

Quoted 4 lines

[...]

Quoted 87 lines · Kumar Kartikeya Dwivedi

Quoted 56 lines · Andrii Nakryiko

Quoted 35 lines · Andrei Matei

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 6 lines

Quoted 3 lines

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")

Quoted 7 lines

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.

[...]

Quoted 103 lines · Andrei Matei

Quoted 87 lines · Kumar Kartikeya Dwivedi

Quoted 56 lines · Andrii Nakryiko

Quoted 35 lines · Andrei Matei

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 6 lines

Quoted 3 lines

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")

Quoted 7 lines

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.

Quoted 6 lines

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.

Quoted 15 lines

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.

Quoted 3 lines

[...]

Quoted 119 lines · Kumar Kartikeya Dwivedi

Quoted 103 lines · Andrei Matei

Quoted 87 lines · Kumar Kartikeya Dwivedi

Quoted 56 lines · Andrii Nakryiko

Quoted 35 lines · Andrei Matei

[...]

Quoted 23 lines

Quoted 23 lines

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

Quoted 8 lines

Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 6 lines

Quoted 3 lines

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")

Quoted 7 lines

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.

Quoted 6 lines

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.

Quoted 2 lines

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/[email protected]/

Quoted 16 lines

Quoted 15 lines

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.

Quoted 2 lines

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.

Quoted 5 lines

Quoted 5 lines

[...]

Quoted 35 lines · 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 <[email protected]>

Fixes 01f810ace9ed3 ("bpf: Allow variable-offset stack access")

Closes https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/ open here

Signed-off-by Andrei Matei <[email protected]>

---
 kernel/bpf/verifier.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

kernel/bpf/verifier.c +0 -0

index af2819d5c8ee..b646bdde09cd 100644

kernel/bpf/verifier.c static int check_stack_access_within_bounds( · line 6821

Quoted 9 lines

kernel/bpf/verifier.c +2 -3

@@ -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!

Quoted 8 lines

kernel/bpf/verifier.c +0 -1

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

2.40.1