| Message ID | 20231204153919.11967-1-andreimatei1@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | bpf: fix verification of indirect var-off stack access | expand |
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 >
[...] > > > > 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.
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.
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.
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.
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.
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.
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 > >
[...] > > > > 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? [...]
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. > > [...]
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. > > > > > [...]
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! :) > > > > > > > > > [...]
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. > > > > > > > > > [...]
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. > > [...]
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. > > > > > [...]
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. > > > > > > > > > > [...]
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);
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(-)