Message ID | 20231217010649.577814-2-andreimatei1@gmail.com (mailing list archive) |
---|---|
State | Superseded |
Delegated to: | BPF |
Headers | show |
Series | bpf: Simplify checking size of helper accesses | expand |
On Sat, 2023-12-16 at 20:06 -0500, Andrei Matei wrote: [...] > (*) Besides standing to reason that the checks for a bigger size access > are a super-set of the checks for a smaller size access, I have also > mechanically verified this by reading the code for all types of > pointers. I could convince myself that it's true for all but > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > line-by-line does not immediately prove what we want. If anyone has any > qualms, let me know. check_help_mem_access() is a bit obfuscated :) After staring at it for a bit I have a question regarding check_ptr_to_btf_access(): - it can call btf_struct_access(), which in can call btf_struct_walk(), which has the following check: if (btf_type_is_ptr(mtype)) { const struct btf_type *stype, *t; enum bpf_type_flag tmp_flag = 0; u32 id; if (msize != size || off != moff) { bpf_log(log, "cannot access ptr member %s with moff %u in struct %s with off %u size %u\n", mname, moff, tname, off, size); return -EACCES; } - previously this code was executed twice, for size 0 and for size umax_value of the size register; - now this code is executed only for umax_value of the size register; - is it possible that with size 0 this code could have reported error -EACCESS error, which would be missed now? Except for the question above I don't see any issues, but check_help_mem_access() has many sub-cases, so I might have missed something. Also a few nits below. [...] > @@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, > } > } > > +/* Helper function for logging an error about an invalid attempt to perform a > + * (possibly) zero-sized memory access. The pointer being dereferenced is in > + * register @ptr_regno, and the size of the access is in register @size_regno. > + * The size register is assumed to either be a constant zero or have a zero lower > + * bound. > + * > + * Logs a message like: > + * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48 > + */ > +static void log_zero_size_access_err(struct bpf_verifier_env *env, > + int ptr_regno, > + int size_regno) > +{ > + struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno]; > + struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno]; > + const bool size_is_const = tnum_is_const(size_reg->var_off); > + const char *ptr_type_str = reg_type_str(env, ptr_reg->type); > + /* allocate a few buffers to be used as parts of the error message */ > + char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0}; > + s64 min_off, max_off; Nit: empty is needed here [...] > /* verify arguments to helpers or kfuncs consisting of a pointer and an access > * size. > * > @@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > struct bpf_call_arg_meta *meta) > { > int err; > + const bool size_is_const = tnum_is_const(reg->var_off); Nit: please swap definitions to get the "reverse Christmas tree": const bool size_is_const = tnum_is_const(reg->var_off); int err; > > /* This is used to refine r0 return value bounds for helpers > * that enforce this value as an upper bound on return values. > @@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > /* The register is SCALAR_VALUE; the access check > * happens using its boundaries. > */ > - if (!tnum_is_const(reg->var_off)) > + if (!size_is_const) > /* For unprivileged variable accesses, disable raw > * mode so that the program is required to > * initialize all the memory that the helper could > @@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > return -EACCES; > } > > - if (reg->umin_value == 0) { > - err = check_helper_mem_access(env, regno - 1, 0, > - zero_size_allowed, > - meta); > - if (err) > - return err; > + if (reg->umin_value == 0 && !zero_size_allowed) { > + log_zero_size_access_err(env, regno-1, regno); > + return -EACCES; > } > > if (reg->umax_value >= BPF_MAX_VAR_SIZ) { > @@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > regno); > return -EACCES; > } > + /* If !zero_size_allowed, we already checked that umin_value > 0, so > + * umax_value should also be > 0. > + */ > + if (reg->umax_value == 0 && !zero_size_allowed) { > + verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); > + return -EFAULT; > + } > err = check_helper_mem_access(env, regno - 1, > reg->umax_value, > - zero_size_allowed, meta); > + /* zero_size_allowed: we asserted above that umax_value is > + * not zero if !zero_size_allowed, so we don't need any > + * further checks. > + */ > + true , ^ Nit: extra space ---------' > + meta); > if (!err) > err = mark_chain_precision(env, regno); > return err; [...]
On Mon, Dec 18, 2023 at 7:04 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Sat, 2023-12-16 at 20:06 -0500, Andrei Matei wrote: > [...] > > > (*) Besides standing to reason that the checks for a bigger size access > > are a super-set of the checks for a smaller size access, I have also > > mechanically verified this by reading the code for all types of > > pointers. I could convince myself that it's true for all but > > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > > line-by-line does not immediately prove what we want. If anyone has any > > qualms, let me know. > > check_help_mem_access() is a bit obfuscated :) > After staring at it for a bit I have a question regarding > check_ptr_to_btf_access(): > - it can call btf_struct_access(), > which in can call btf_struct_walk(), > which has the following check: > > if (btf_type_is_ptr(mtype)) { > const struct btf_type *stype, *t; > enum bpf_type_flag tmp_flag = 0; > u32 id; > > if (msize != size || off != moff) { > bpf_log(log, > "cannot access ptr member %s with moff %u in struct %s with off %u size %u\n", > mname, moff, tname, off, size); > return -EACCES; > } > > - previously this code was executed twice, for size 0 and for size > umax_value of the size register; > - now this code is executed only for umax_value of the size register; > - is it possible that with size 0 this code could have reported error > -EACCESS error, which would be missed now? I don't have a good answer. I too have looked at check_ptr_to_btf_access() and ended up confused -- but then again, I don't know what's supposed to be allowed and what's supposed to not be allowed. I will say, though, that I don't think the code as it stands make sense, and I don't think any interaction between the zero-size check and btf access is intentional. Around [1] we've looked a bit at the history of this zero-size check, and it's been there forever, predating most of the code around it. What convinces me personally that the zero-size check was not load-bearing is the fact that we were only performing the check iff umin == 0 -- we were not consistently performing a check for the umin value. Also, obviously, we were not performing a check for every possible value in between umin and umax. So I can't really imagine positive benefits of the inconsistent check we were doing. But then again, I cannot actually speak with confidence about it. As a btw, I'll say that we don't allow variable-offset accesses to btf ptr [2]. I don't know if this should influence how we treat the access size... but maybe? Like, should we disallow variable-sized accesses on the same argument as disallowing variable-offset ones (whatever that argument may be)? I don't know what I'm talking about (generally BTF is foreign to me), but I imagine this all means that currently the verifier allows one to read from an array field by starting at a compile-time constant offset, and extending to a variable size. However, you cannot start from an arbitrary offset, though. Does this combination of being strict about the offset but permissive about the size make sense? I'll take guidance. If people prefer we don't touch this code at all, that's fine. Although it doesn't feel good to be driven simply by fear. [1] https://lore.kernel.org/bpf/CAP01T77M=SyNviMYCO-koxizvD6eGm=5KQ1Wv=ahbRU5XQB4bA@mail.gmail.com/ [2] https://github.com/torvalds/linux/blob/ee5cc0363ea0d587f62349ff3b3e2dfa751832e4/kernel/bpf/verifier.c#L3318-L3326 > > Except for the question above I don't see any issues, > but check_help_mem_access() has many sub-cases, > so I might have missed something. > > Also a few nits below. > > [...] > > > @@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, > > } > > } > > > > +/* Helper function for logging an error about an invalid attempt to perform a > > + * (possibly) zero-sized memory access. The pointer being dereferenced is in > > + * register @ptr_regno, and the size of the access is in register @size_regno. > > + * The size register is assumed to either be a constant zero or have a zero lower > > + * bound. > > + * > > + * Logs a message like: > > + * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48 > > + */ > > +static void log_zero_size_access_err(struct bpf_verifier_env *env, > > + int ptr_regno, > > + int size_regno) > > +{ > > + struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno]; > > + struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno]; > > + const bool size_is_const = tnum_is_const(size_reg->var_off); > > + const char *ptr_type_str = reg_type_str(env, ptr_reg->type); > > + /* allocate a few buffers to be used as parts of the error message */ > > + char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0}; > > + s64 min_off, max_off; > > Nit: empty is needed here > > [...] > > > /* verify arguments to helpers or kfuncs consisting of a pointer and an access > > * size. > > * > > @@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > struct bpf_call_arg_meta *meta) > > { > > int err; > > + const bool size_is_const = tnum_is_const(reg->var_off); > > Nit: please swap definitions to get the "reverse Christmas tree": > > const bool size_is_const = tnum_is_const(reg->var_off); > int err; > > > > > /* This is used to refine r0 return value bounds for helpers > > * that enforce this value as an upper bound on return values. > > @@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > /* The register is SCALAR_VALUE; the access check > > * happens using its boundaries. > > */ > > - if (!tnum_is_const(reg->var_off)) > > + if (!size_is_const) > > /* For unprivileged variable accesses, disable raw > > * mode so that the program is required to > > * initialize all the memory that the helper could > > @@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > return -EACCES; > > } > > > > - if (reg->umin_value == 0) { > > - err = check_helper_mem_access(env, regno - 1, 0, > > - zero_size_allowed, > > - meta); > > - if (err) > > - return err; > > + if (reg->umin_value == 0 && !zero_size_allowed) { > > + log_zero_size_access_err(env, regno-1, regno); > > + return -EACCES; > > } > > > > if (reg->umax_value >= BPF_MAX_VAR_SIZ) { > > @@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > regno); > > return -EACCES; > > } > > + /* If !zero_size_allowed, we already checked that umin_value > 0, so > > + * umax_value should also be > 0. > > + */ > > + if (reg->umax_value == 0 && !zero_size_allowed) { > > + verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); > > + return -EFAULT; > > + } > > err = check_helper_mem_access(env, regno - 1, > > reg->umax_value, > > - zero_size_allowed, meta); > > + /* zero_size_allowed: we asserted above that umax_value is > > + * not zero if !zero_size_allowed, so we don't need any > > + * further checks. > > + */ > > + true , > ^ > Nit: extra space ---------' > > > + meta); > > if (!err) > > err = mark_chain_precision(env, regno); > > return err; > > [...]
On Mon, 2023-12-18 at 21:54 -0500, Andrei Matei wrote: > On Mon, Dec 18, 2023 at 7:04 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > On Sat, 2023-12-16 at 20:06 -0500, Andrei Matei wrote: > > [...] > > > > > (*) Besides standing to reason that the checks for a bigger size access > > > are a super-set of the checks for a smaller size access, I have also > > > mechanically verified this by reading the code for all types of > > > pointers. I could convince myself that it's true for all but > > > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > > > line-by-line does not immediately prove what we want. If anyone has any > > > qualms, let me know. > > > > check_help_mem_access() is a bit obfuscated :) > > After staring at it for a bit I have a question regarding > > check_ptr_to_btf_access(): > > - it can call btf_struct_access(), > > which in can call btf_struct_walk(), > > which has the following check: > > > > if (btf_type_is_ptr(mtype)) { > > const struct btf_type *stype, *t; > > enum bpf_type_flag tmp_flag = 0; > > u32 id; > > > > if (msize != size || off != moff) { > > bpf_log(log, > > "cannot access ptr member %s with moff %u in struct %s with off %u size %u\n", > > mname, moff, tname, off, size); > > return -EACCES; > > } > > > > - previously this code was executed twice, for size 0 and for size > > umax_value of the size register; > > - now this code is executed only for umax_value of the size register; > > - is it possible that with size 0 this code could have reported error > > -EACCESS error, which would be missed now? > > I don't have a good answer. I too have looked at check_ptr_to_btf_access() and > ended up confused -- but then again, I don't know what's supposed to be allowed > and what's supposed to not be allowed. I will say, though, that I don't think > the code as it stands make sense, and I don't think any interaction between the > zero-size check and btf access is intentional. Around [1] we've looked a bit at > the history of this zero-size check, and it's been there forever, predating > most of the code around it. What convinces me personally that the zero-size > check was not load-bearing is the fact that we were only performing > the check iff > umin == 0 -- we were not consistently performing a check for the umin value. > Also, obviously, we were not performing a check for every possible value in > between umin and umax. So I can't really imagine positive benefits of the > inconsistent check we were doing. But then again, I cannot actually speak with > confidence about it. Not checking consistently for all possible offsets is a good argument, thank you. > As a btw, I'll say that we don't allow variable-offset accesses to btf ptr [2]. > I don't know if this should influence how we treat the access size... but > maybe? Like, should we disallow variable-sized accesses on the same argument as > disallowing variable-offset ones (whatever that argument may be)? I don't know > what I'm talking about (generally BTF is foreign to me), but I imagine this all > means that currently the verifier allows one to read from an array field by > starting at a compile-time constant offset, and extending to a variable size. > However, you cannot start from an arbitrary offset, though. Does this > combination of being strict about the offset but permissive about the size make > sense? I agree with you, that disallowing variable size access in BTF case might make sense. check_ptr_to_btf_access() calls either: a. env->ops->btf_struct_access(), which is one of the following: 1. _tc_cls_act_btf_struct_access() (through a function pointer), which allows accessing exactly one field: struct nf_conn->mark; 2. bpf_tcp_ca_btf_struct_access, which allows accessing several fields in sock, tcp_sock and inet_connection_sock structures. b. btf_struct_access(), which checks the following: 1. part with btf_find_struct_meta() checks that access does not reach to some forbidden field; 2. btf_struct_walk() checks that offset and size of the access match offset and size of some field in the target BTF structure; Technically, checks a.1, a.2 and b.1 are ok with variable size access, but b.2 is not and it does not seem to be verified. I tried a patch below and test_progs seem to pass locally (but I have some troubles with my local setup at the moment, so it should be double-checked). > I'll take guidance. If people prefer we don't touch this code at all, that's > fine. Although it doesn't feel good to be driven simply by fear. Would be good if others could comment. [...] --- diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index cf2a09408bdc..946415d11338 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -7328,6 +7328,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, { int err; const bool size_is_const = tnum_is_const(reg->var_off); + struct bpf_reg_state *ptr_reg = &cur_regs(env)[regno - 1]; /* This is used to refine r0 return value bounds for helpers * that enforce this value as an upper bound on return values. @@ -7373,6 +7374,13 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); return -EFAULT; } + + if (base_type(ptr_reg->type) == PTR_TO_BTF_ID && !size_is_const) { + verbose(env, "variable length access to r%d %s is not allowed", + regno - 1, reg_type_str(env, ptr_reg->type)); + return -EACCES; + } + err = check_helper_mem_access(env, regno - 1, reg->umax_value, /* zero_size_allowed: we asserted above that umax_value is
On Sat, Dec 16, 2023 at 5:07 PM Andrei Matei <andreimatei1@gmail.com> wrote: > > This patch simplifies the verification of size arguments associated to > pointer arguments to helpers and kfuncs. Many helpers take a pointer > argument followed by the size of the memory access performed to be > performed through that pointer. Before this patch, the handling of the > size argument in check_mem_size_reg() was confusing and wasteful: if the > size register's lower bound was 0, then the verification was done twice: > once considering the size of the access to be the lower-bound of the > respective argument, and once considering the upper bound (even if the > two are the same). The upper bound checking is a super-set of the > lower-bound checking(*), except: the only point of the lower-bound check > is to handle the case where zero-sized-accesses are explicitly not > allowed and the lower-bound is zero. This static condition is now > checked explicitly, replacing a much more complex, expensive and > confusing verification call to check_helper_mem_access(). > > Now that check_mem_size_reg() deals directly with the zero_size_allowed > checking, the single remaining call to check_helper_mem_access() can > pass a static value for the zero_size_allowed arg, instead of > propagating a dynamic one. I think this is an improvement, as tracking > the wide propagation of zero_sized_allowed is already complicated. > > This patch also results in better error messages for rejected zero-size > reads. Before, the message one would get depended on the type of the > pointer and on other conditions, and sometimes the message was plain > wrong: in some tests that changed you'll see that the old message was > something like "R1 min value is outside of the allowed memory range", > where R1 is the pointer register; the error was wrongly claiming that > the pointer was bad instead of the size being bad. Other times the > information that the size came for a register with a possible range of > values was wrong, and the error presented the size as a fixed zero. > > (*) Besides standing to reason that the checks for a bigger size access > are a super-set of the checks for a smaller size access, I have also > mechanically verified this by reading the code for all types of > pointers. I could convince myself that it's true for all but > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > line-by-line does not immediately prove what we want. If anyone has any > qualms, let me know. > > Signed-off-by: Andrei Matei <andreimatei1@gmail.com> > --- > kernel/bpf/verifier.c | 85 +++++++++++++++++-- > .../bpf/progs/verifier_helper_value_access.c | 45 +++++++++- > .../selftests/bpf/progs/verifier_raw_stack.c | 4 +- > 3 files changed, 120 insertions(+), 14 deletions(-) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 1863826a4ac3..cf2a09408bdc 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, > } > } > > +/* Helper function for logging an error about an invalid attempt to perform a > + * (possibly) zero-sized memory access. The pointer being dereferenced is in > + * register @ptr_regno, and the size of the access is in register @size_regno. > + * The size register is assumed to either be a constant zero or have a zero lower > + * bound. > + * > + * Logs a message like: > + * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48 > + */ > +static void log_zero_size_access_err(struct bpf_verifier_env *env, > + int ptr_regno, > + int size_regno) > +{ > + struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno]; > + struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno]; > + const bool size_is_const = tnum_is_const(size_reg->var_off); > + const char *ptr_type_str = reg_type_str(env, ptr_reg->type); > + /* allocate a few buffers to be used as parts of the error message */ > + char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0}; this is quite a lot of stack usage, adding this on top of all the other stuff we have feels a bit bad > + s64 min_off, max_off; > + if (!size_is_const) { > + snprintf(size_range_buf, sizeof(size_range_buf), > + "[0,%lld]", size_reg->umax_value); > + } > + > + if (tnum_is_const(ptr_reg->var_off)) { > + min_off = (s64)ptr_reg->var_off.value + ptr_reg->off; > + snprintf(off_buf, sizeof(off_buf), "%lld", min_off); > + } else { > + min_off = ptr_reg->smin_value + ptr_reg->off; > + max_off = ptr_reg->smax_value + ptr_reg->off; > + snprintf(off_buf, sizeof(off_buf), "[%lld,%lld]", min_off, max_off); > + } > + > + /* attempt to figure out info about the maximum offset that could be allowed */ > + switch (ptr_reg->type) { > + case PTR_TO_MAP_KEY: > + snprintf(max_size_buf, sizeof(max_size_buf), "key_size=%d", ptr_reg->map_ptr->key_size); > + break; > + case PTR_TO_MAP_VALUE: > + snprintf(max_size_buf, sizeof(max_size_buf), "value_size=%d", ptr_reg->map_ptr->value_size); > + break; > + case PTR_TO_PACKET: > + case PTR_TO_PACKET_META: > + snprintf(max_size_buf, sizeof(max_size_buf), "packet_size=%d", ptr_reg->range); > + break; > + case PTR_TO_MEM: > + default: > + snprintf(max_size_buf, sizeof(max_size_buf), "max_size=N/A"); we do know the size, reg->mem_size contains addressable memory range size for PTR_TO_MEM > + } > + > + verbose(env, "invalid %szero-size read. Size comes from R%d=%s. " > + "Attempting to dereference *%s R%d: off=%s %s\n", > + size_is_const ? "" : "possibly ", > + size_regno, size_is_const ? "0" : size_range_buf, > + ptr_type_str, ptr_regno, off_buf, max_size_buf); > +} > + > + > /* verify arguments to helpers or kfuncs consisting of a pointer and an access > * size. > * > @@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > struct bpf_call_arg_meta *meta) > { > int err; > + const bool size_is_const = tnum_is_const(reg->var_off); > > /* This is used to refine r0 return value bounds for helpers > * that enforce this value as an upper bound on return values. > @@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > /* The register is SCALAR_VALUE; the access check > * happens using its boundaries. > */ > - if (!tnum_is_const(reg->var_off)) > + if (!size_is_const) > /* For unprivileged variable accesses, disable raw > * mode so that the program is required to > * initialize all the memory that the helper could > @@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > return -EACCES; > } > > - if (reg->umin_value == 0) { > - err = check_helper_mem_access(env, regno - 1, 0, > - zero_size_allowed, > - meta); > - if (err) > - return err; > + if (reg->umin_value == 0 && !zero_size_allowed) { > + log_zero_size_access_err(env, regno-1, regno); > + return -EACCES; > } > > if (reg->umax_value >= BPF_MAX_VAR_SIZ) { > @@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > regno); > return -EACCES; > } > + /* If !zero_size_allowed, we already checked that umin_value > 0, so > + * umax_value should also be > 0. > + */ > + if (reg->umax_value == 0 && !zero_size_allowed) { > + verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); > + return -EFAULT; > + } > err = check_helper_mem_access(env, regno - 1, > reg->umax_value, > - zero_size_allowed, meta); > + /* zero_size_allowed: we asserted above that umax_value is > + * not zero if !zero_size_allowed, so we don't need any > + * further checks. > + */ > + true , if this is the last remaining call, why even have this true parameter instead of assuming zero_size_allowed inside check_helper_mem_access() ? nit: dangling space > + meta); > if (!err) > err = mark_chain_precision(env, regno); > return err; > diff --git a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > index 692216c0ad3d..9fe10f63c931 100644 > --- a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > +++ b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > @@ -89,9 +89,14 @@ l0_%=: exit; \ > : __clobber_all); > } > > +/* Call a function taking a pointer and a size which doesn't allow the size to > + * be zero (i.e. bpf_trace_printk() declares the second argument to be > + * ARG_CONST_SIZE, not ARG_CONST_SIZE_OR_ZERO). We attempt to pass zero for the > + * size and expect to fail. > + */ > SEC("tracepoint") > __description("helper access to map: empty range") > -__failure __msg("invalid access to map value, value_size=48 off=0 size=0") > +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48") This comes from "BPF old-timer", so take it with a grain of salt, but current error doesn't feel too bad already and is quite understandable, tbh. In any case, let's split off the error formatting changes (they are quire big) from the check logic change and post it as two separate patches (they might be in a single patch set) > __naked void access_to_map_empty_range(void) > { > asm volatile (" \ [...]
On Tue, Dec 19, 2023 at 9:01 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Mon, 2023-12-18 at 21:54 -0500, Andrei Matei wrote: > > On Mon, Dec 18, 2023 at 7:04 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > On Sat, 2023-12-16 at 20:06 -0500, Andrei Matei wrote: > > > [...] > > > > > > > (*) Besides standing to reason that the checks for a bigger size access > > > > are a super-set of the checks for a smaller size access, I have also > > > > mechanically verified this by reading the code for all types of > > > > pointers. I could convince myself that it's true for all but > > > > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > > > > line-by-line does not immediately prove what we want. If anyone has any > > > > qualms, let me know. > > > > > > check_help_mem_access() is a bit obfuscated :) > > > After staring at it for a bit I have a question regarding > > > check_ptr_to_btf_access(): > > > - it can call btf_struct_access(), > > > which in can call btf_struct_walk(), > > > which has the following check: > > > > > > if (btf_type_is_ptr(mtype)) { > > > const struct btf_type *stype, *t; > > > enum bpf_type_flag tmp_flag = 0; > > > u32 id; > > > > > > if (msize != size || off != moff) { > > > bpf_log(log, > > > "cannot access ptr member %s with moff %u in struct %s with off %u size %u\n", > > > mname, moff, tname, off, size); > > > return -EACCES; > > > } > > > > > > - previously this code was executed twice, for size 0 and for size > > > umax_value of the size register; > > > - now this code is executed only for umax_value of the size register; > > > - is it possible that with size 0 this code could have reported error > > > -EACCESS error, which would be missed now? > > > > I don't have a good answer. I too have looked at check_ptr_to_btf_access() and > > ended up confused -- but then again, I don't know what's supposed to be allowed > > and what's supposed to not be allowed. I will say, though, that I don't think > > the code as it stands make sense, and I don't think any interaction between the > > zero-size check and btf access is intentional. Around [1] we've looked a bit at > > the history of this zero-size check, and it's been there forever, predating > > most of the code around it. What convinces me personally that the zero-size > > check was not load-bearing is the fact that we were only performing > > the check iff > > umin == 0 -- we were not consistently performing a check for the umin value. > > Also, obviously, we were not performing a check for every possible value in > > between umin and umax. So I can't really imagine positive benefits of the > > inconsistent check we were doing. But then again, I cannot actually speak with > > confidence about it. > > Not checking consistently for all possible offsets is a good argument, thank you. > > > As a btw, I'll say that we don't allow variable-offset accesses to btf ptr [2]. > > I don't know if this should influence how we treat the access size... but > > maybe? Like, should we disallow variable-sized accesses on the same argument as > > disallowing variable-offset ones (whatever that argument may be)? I don't know > > what I'm talking about (generally BTF is foreign to me), but I imagine this all > > means that currently the verifier allows one to read from an array field by > > starting at a compile-time constant offset, and extending to a variable size. > > However, you cannot start from an arbitrary offset, though. Does this > > combination of being strict about the offset but permissive about the size make > > sense? > > I agree with you, that disallowing variable size access in BTF case > might make sense. check_ptr_to_btf_access() calls either: > a. env->ops->btf_struct_access(), which is one of the following: > 1. _tc_cls_act_btf_struct_access() (through a function pointer), > which allows accessing exactly one field: struct nf_conn->mark; > 2. bpf_tcp_ca_btf_struct_access, which allows accessing several > fields in sock, tcp_sock and inet_connection_sock structures. > b. btf_struct_access(), which checks the following: > 1. part with btf_find_struct_meta() checks that access does not reach > to some forbidden field; wouldn't variable size access be problematic here without properly working with size range (instead of a max offset)? Just because max offset falls into allowed field, doesn't mean that min offset falls into allowed field. What's even worth, both min and max by themselves can fall into allowed fields (different ones, though), but between those two fields there will be a forbidden one? > 2. btf_struct_walk() checks that offset and size of the access match > offset and size of some field in the target BTF structure; > > Technically, checks a.1, a.2 and b.1 are ok with variable size access, > but b.2 is not and it does not seem to be verified. > > I tried a patch below and test_progs seem to pass locally > (but I have some troubles with my local setup at the moment, > so it should be double-checked). > > > I'll take guidance. If people prefer we don't touch this code at all, that's > > fine. Although it doesn't feel good to be driven simply by fear. > > Would be good if others could comment. Given the current (seemingly incomplete) checking logic Andrei change makes sense. But the variable-sized BTF access throws a wrinkle into this, no? It can't be checked just at min/max offset boundaries, as I mentioned above. I don't know if variable-sized BTF access is important (Alexei?, Martin?), but maybe BTF access has to be checked separately and then we can keep the check that does pure dump memory access checks simply and correctly? > > [...] > > --- > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index cf2a09408bdc..946415d11338 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -7328,6 +7328,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > { > int err; > const bool size_is_const = tnum_is_const(reg->var_off); > + struct bpf_reg_state *ptr_reg = &cur_regs(env)[regno - 1]; > > /* This is used to refine r0 return value bounds for helpers > * that enforce this value as an upper bound on return values. > @@ -7373,6 +7374,13 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); > return -EFAULT; > } > + > + if (base_type(ptr_reg->type) == PTR_TO_BTF_ID && !size_is_const) { > + verbose(env, "variable length access to r%d %s is not allowed", > + regno - 1, reg_type_str(env, ptr_reg->type)); > + return -EACCES; > + } > + > err = check_helper_mem_access(env, regno - 1, > reg->umax_value, > /* zero_size_allowed: we asserted above that umax_value is
On Tue, 2023-12-19 at 11:08 -0800, Andrii Nakryiko wrote: [...] > > > As a btw, I'll say that we don't allow variable-offset accesses to btf ptr [2]. > > > I don't know if this should influence how we treat the access size... but > > > maybe? Like, should we disallow variable-sized accesses on the same argument as > > > disallowing variable-offset ones (whatever that argument may be)? I don't know > > > what I'm talking about (generally BTF is foreign to me), but I imagine this all > > > means that currently the verifier allows one to read from an array field by > > > starting at a compile-time constant offset, and extending to a variable size. > > > However, you cannot start from an arbitrary offset, though. Does this > > > combination of being strict about the offset but permissive about the size make > > > sense? > > > > I agree with you, that disallowing variable size access in BTF case > > might make sense. check_ptr_to_btf_access() calls either: > > a. env->ops->btf_struct_access(), which is one of the following: > > 1. _tc_cls_act_btf_struct_access() (through a function pointer), > > which allows accessing exactly one field: struct nf_conn->mark; > > 2. bpf_tcp_ca_btf_struct_access, which allows accessing several > > fields in sock, tcp_sock and inet_connection_sock structures. > > b. btf_struct_access(), which checks the following: > > 1. part with btf_find_struct_meta() checks that access does not reach > > to some forbidden field; > > wouldn't variable size access be problematic here without properly > working with size range (instead of a max offset)? Just because max > offset falls into allowed field, doesn't mean that min offset falls > into allowed field. What's even worth, both min and max by themselves > can fall into allowed fields (different ones, though), but between > those two fields there will be a forbidden one? As far as I understand that part, it checks for each forbidden field that it does not intersect with full range [off, off + max_size]. > > 2. btf_struct_walk() checks that offset and size of the access match > > offset and size of some field in the target BTF structure; > > > > Technically, checks a.1, a.2 and b.1 are ok with variable size access, > > but b.2 is not and it does not seem to be verified. > > > > I tried a patch below and test_progs seem to pass locally > > (but I have some troubles with my local setup at the moment, > > so it should be double-checked). > > > > > I'll take guidance. If people prefer we don't touch this code at all, that's > > > fine. Although it doesn't feel good to be driven simply by fear. > > > > Would be good if others could comment. > > Given the current (seemingly incomplete) checking logic Andrei change > makes sense. But the variable-sized BTF access throws a wrinkle into > this, no? It can't be checked just at min/max offset boundaries, as I > mentioned above. Yes, probably this patch makes sense as-is, as a logic is already not consistent. [...] > but maybe BTF access has to be checked separately and then > we can keep the check that does pure dump memory access checks simply > and correctly? check_helper_mem_access() is called form many places, so BTF handling should probably remain there. What it lacks is a notion of variable size access. [...]
On Tue, Dec 19, 2023 at 11:24 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Tue, 2023-12-19 at 11:08 -0800, Andrii Nakryiko wrote: > [...] > > > > As a btw, I'll say that we don't allow variable-offset accesses to btf ptr [2]. > > > > I don't know if this should influence how we treat the access size... but > > > > maybe? Like, should we disallow variable-sized accesses on the same argument as > > > > disallowing variable-offset ones (whatever that argument may be)? I don't know > > > > what I'm talking about (generally BTF is foreign to me), but I imagine this all > > > > means that currently the verifier allows one to read from an array field by > > > > starting at a compile-time constant offset, and extending to a variable size. > > > > However, you cannot start from an arbitrary offset, though. Does this > > > > combination of being strict about the offset but permissive about the size make > > > > sense? > > > > > > I agree with you, that disallowing variable size access in BTF case > > > might make sense. check_ptr_to_btf_access() calls either: > > > a. env->ops->btf_struct_access(), which is one of the following: > > > 1. _tc_cls_act_btf_struct_access() (through a function pointer), > > > which allows accessing exactly one field: struct nf_conn->mark; > > > 2. bpf_tcp_ca_btf_struct_access, which allows accessing several > > > fields in sock, tcp_sock and inet_connection_sock structures. > > > b. btf_struct_access(), which checks the following: > > > 1. part with btf_find_struct_meta() checks that access does not reach > > > to some forbidden field; > > > > wouldn't variable size access be problematic here without properly > > working with size range (instead of a max offset)? Just because max > > offset falls into allowed field, doesn't mean that min offset falls > > into allowed field. What's even worth, both min and max by themselves > > can fall into allowed fields (different ones, though), but between > > those two fields there will be a forbidden one? > > As far as I understand that part, it checks for each forbidden field that > it does not intersect with full range [off, off + max_size]. Ah, that's great. I probably should go and read that code before asking questions and making suggestions :) > > > > 2. btf_struct_walk() checks that offset and size of the access match > > > offset and size of some field in the target BTF structure; > > > > > > Technically, checks a.1, a.2 and b.1 are ok with variable size access, > > > but b.2 is not and it does not seem to be verified. > > > > > > I tried a patch below and test_progs seem to pass locally > > > (but I have some troubles with my local setup at the moment, > > > so it should be double-checked). > > > > > > > I'll take guidance. If people prefer we don't touch this code at all, that's > > > > fine. Although it doesn't feel good to be driven simply by fear. > > > > > > Would be good if others could comment. > > > > Given the current (seemingly incomplete) checking logic Andrei change > > makes sense. But the variable-sized BTF access throws a wrinkle into > > this, no? It can't be checked just at min/max offset boundaries, as I > > mentioned above. > > Yes, probably this patch makes sense as-is, as a logic is already not > consistent. +1, I'd just factor out error message changes, they are separate, IMO > > [...] > > > but maybe BTF access has to be checked separately and then > > we can keep the check that does pure dump memory access checks simply > > and correctly? > > check_helper_mem_access() is called form many places, so BTF handling > should probably remain there. What it lacks is a notion of variable > size access. > agreed > [...]
On Tue, Dec 19, 2023 at 2:03 PM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Sat, Dec 16, 2023 at 5:07 PM Andrei Matei <andreimatei1@gmail.com> wrote: > > > > This patch simplifies the verification of size arguments associated to > > pointer arguments to helpers and kfuncs. Many helpers take a pointer > > argument followed by the size of the memory access performed to be > > performed through that pointer. Before this patch, the handling of the > > size argument in check_mem_size_reg() was confusing and wasteful: if the > > size register's lower bound was 0, then the verification was done twice: > > once considering the size of the access to be the lower-bound of the > > respective argument, and once considering the upper bound (even if the > > two are the same). The upper bound checking is a super-set of the > > lower-bound checking(*), except: the only point of the lower-bound check > > is to handle the case where zero-sized-accesses are explicitly not > > allowed and the lower-bound is zero. This static condition is now > > checked explicitly, replacing a much more complex, expensive and > > confusing verification call to check_helper_mem_access(). > > > > Now that check_mem_size_reg() deals directly with the zero_size_allowed > > checking, the single remaining call to check_helper_mem_access() can > > pass a static value for the zero_size_allowed arg, instead of > > propagating a dynamic one. I think this is an improvement, as tracking > > the wide propagation of zero_sized_allowed is already complicated. > > > > This patch also results in better error messages for rejected zero-size > > reads. Before, the message one would get depended on the type of the > > pointer and on other conditions, and sometimes the message was plain > > wrong: in some tests that changed you'll see that the old message was > > something like "R1 min value is outside of the allowed memory range", > > where R1 is the pointer register; the error was wrongly claiming that > > the pointer was bad instead of the size being bad. Other times the > > information that the size came for a register with a possible range of > > values was wrong, and the error presented the size as a fixed zero. > > > > (*) Besides standing to reason that the checks for a bigger size access > > are a super-set of the checks for a smaller size access, I have also > > mechanically verified this by reading the code for all types of > > pointers. I could convince myself that it's true for all but > > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > > line-by-line does not immediately prove what we want. If anyone has any > > qualms, let me know. > > > > Signed-off-by: Andrei Matei <andreimatei1@gmail.com> > > --- > > kernel/bpf/verifier.c | 85 +++++++++++++++++-- > > .../bpf/progs/verifier_helper_value_access.c | 45 +++++++++- > > .../selftests/bpf/progs/verifier_raw_stack.c | 4 +- > > 3 files changed, 120 insertions(+), 14 deletions(-) > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index 1863826a4ac3..cf2a09408bdc 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, > > } > > } > > > > +/* Helper function for logging an error about an invalid attempt to perform a > > + * (possibly) zero-sized memory access. The pointer being dereferenced is in > > + * register @ptr_regno, and the size of the access is in register @size_regno. > > + * The size register is assumed to either be a constant zero or have a zero lower > > + * bound. > > + * > > + * Logs a message like: > > + * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48 > > + */ > > +static void log_zero_size_access_err(struct bpf_verifier_env *env, > > + int ptr_regno, > > + int size_regno) > > +{ > > + struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno]; > > + struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno]; > > + const bool size_is_const = tnum_is_const(size_reg->var_off); > > + const char *ptr_type_str = reg_type_str(env, ptr_reg->type); > > + /* allocate a few buffers to be used as parts of the error message */ > > + char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0}; > > this is quite a lot of stack usage, adding this on top of all the > other stuff we have feels a bit bad I could be less wasteful and have a single, smaller buffer. But do we really care for a leaf function? > > > + s64 min_off, max_off; > > + if (!size_is_const) { > > + snprintf(size_range_buf, sizeof(size_range_buf), > > + "[0,%lld]", size_reg->umax_value); > > + } > > + > > + if (tnum_is_const(ptr_reg->var_off)) { > > + min_off = (s64)ptr_reg->var_off.value + ptr_reg->off; > > + snprintf(off_buf, sizeof(off_buf), "%lld", min_off); > > + } else { > > + min_off = ptr_reg->smin_value + ptr_reg->off; > > + max_off = ptr_reg->smax_value + ptr_reg->off; > > + snprintf(off_buf, sizeof(off_buf), "[%lld,%lld]", min_off, max_off); > > + } > > + > > + /* attempt to figure out info about the maximum offset that could be allowed */ > > + switch (ptr_reg->type) { > > + case PTR_TO_MAP_KEY: > > + snprintf(max_size_buf, sizeof(max_size_buf), "key_size=%d", ptr_reg->map_ptr->key_size); > > + break; > > + case PTR_TO_MAP_VALUE: > > + snprintf(max_size_buf, sizeof(max_size_buf), "value_size=%d", ptr_reg->map_ptr->value_size); > > + break; > > + case PTR_TO_PACKET: > > + case PTR_TO_PACKET_META: > > + snprintf(max_size_buf, sizeof(max_size_buf), "packet_size=%d", ptr_reg->range); > > + break; > > + case PTR_TO_MEM: > > + default: > > + snprintf(max_size_buf, sizeof(max_size_buf), "max_size=N/A"); > > we do know the size, reg->mem_size contains addressable memory range > size for PTR_TO_MEM > > > + } > > + > > + verbose(env, "invalid %szero-size read. Size comes from R%d=%s. " > > + "Attempting to dereference *%s R%d: off=%s %s\n", > > + size_is_const ? "" : "possibly ", > > + size_regno, size_is_const ? "0" : size_range_buf, > > + ptr_type_str, ptr_regno, off_buf, max_size_buf); > > +} > > + > > + > > /* verify arguments to helpers or kfuncs consisting of a pointer and an access > > * size. > > * > > @@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > struct bpf_call_arg_meta *meta) > > { > > int err; > > + const bool size_is_const = tnum_is_const(reg->var_off); > > > > /* This is used to refine r0 return value bounds for helpers > > * that enforce this value as an upper bound on return values. > > @@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > /* The register is SCALAR_VALUE; the access check > > * happens using its boundaries. > > */ > > - if (!tnum_is_const(reg->var_off)) > > + if (!size_is_const) > > /* For unprivileged variable accesses, disable raw > > * mode so that the program is required to > > * initialize all the memory that the helper could > > @@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > return -EACCES; > > } > > > > - if (reg->umin_value == 0) { > > - err = check_helper_mem_access(env, regno - 1, 0, > > - zero_size_allowed, > > - meta); > > - if (err) > > - return err; > > + if (reg->umin_value == 0 && !zero_size_allowed) { > > + log_zero_size_access_err(env, regno-1, regno); > > + return -EACCES; > > } > > > > if (reg->umax_value >= BPF_MAX_VAR_SIZ) { > > @@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > regno); > > return -EACCES; > > } > > + /* If !zero_size_allowed, we already checked that umin_value > 0, so > > + * umax_value should also be > 0. > > + */ > > + if (reg->umax_value == 0 && !zero_size_allowed) { > > + verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); > > + return -EFAULT; > > + } > > err = check_helper_mem_access(env, regno - 1, > > reg->umax_value, > > - zero_size_allowed, meta); > > + /* zero_size_allowed: we asserted above that umax_value is > > + * not zero if !zero_size_allowed, so we don't need any > > + * further checks. > > + */ > > + true , > > if this is the last remaining call, why even have this true parameter > instead of assuming zero_size_allowed inside > check_helper_mem_access() ? This is the last remaining call to check_helper_mem_access() in this function, but not globally. There are many other calls to check_helper_mem_access(), and some pass `false`. E.g. [1]. Btw, I did generally try to get a better code structure that would not require this zero_size_allowed in a million places, but so far failed. [1] https://github.com/torvalds/linux/blob/ee5cc0363ea0d587f62349ff3b3e2dfa751832e4/kernel/bpf/verifier.c#L4279 > > nit: dangling space > > > + meta); > > if (!err) > > err = mark_chain_precision(env, regno); > > return err; > > diff --git a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > > index 692216c0ad3d..9fe10f63c931 100644 > > --- a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > > +++ b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > > @@ -89,9 +89,14 @@ l0_%=: exit; \ > > : __clobber_all); > > } > > > > +/* Call a function taking a pointer and a size which doesn't allow the size to > > + * be zero (i.e. bpf_trace_printk() declares the second argument to be > > + * ARG_CONST_SIZE, not ARG_CONST_SIZE_OR_ZERO). We attempt to pass zero for the > > + * size and expect to fail. > > + */ > > SEC("tracepoint") > > __description("helper access to map: empty range") > > -__failure __msg("invalid access to map value, value_size=48 off=0 size=0") > > +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48") > > This comes from "BPF old-timer", so take it with a grain of salt, but > current error doesn't feel too bad already and is quite > understandable, tbh. > > In any case, let's split off the error formatting changes (they are > quire big) from the check logic change and post it as two separate > patches (they might be in a single patch set) Just to clarify -- in v1 I had not done anything about error handling, and you observed that some error messages now had less information than before (but, for the record, at the same time some of the errors before were misleading or even wrong because sometimes they didn't even reference the size register and even when they did, they pretended that the size register was the constant zero). In order to keep the information that the errors had before, somehow the type of pointer involved needs to be taken into account; the error needs to look differently for different kinds of pointers. That's how I ended up going medieval and writing the error logging function. You don't seem enthused about all the code that was required; neither was I. I spent some time looking around for something better and more code reuse. I've considered writing some more generic register-printing functions because it seems to me that the verifier has too many duplicate and incomplete printing logic in error messages. But in the end I didn't come up with anything better. Now, one might argue that getting a proper per-pointer-type was an advantage of calling check_helper_mem_access() twice -- so maybe this whole patch is misguided. But then again, the error messages were not actually good, and also I'd argue that it'd be a case of the tail wagging the dog to leave the check_helper_mem_access() call for the benefit of the errors. Having said all this, I definitely don't want to push unwanted code on you, so please confirm that you don't hate the error logging function or... something else. > > > __naked void access_to_map_empty_range(void) > > { > > asm volatile (" \ > > [...]
On Tue, Dec 19, 2023 at 11:08 AM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > > I don't know if variable-sized BTF access is important (Alexei?, > Martin?), but maybe BTF access has to be checked separately and then > we can keep the check that does pure dump memory access checks simply > and correctly? Walking structs with BTF is certainly special and variable size BTF is necessary to access flex arrays at the end of structs. iirc we have a test case for it. On todo list we had a task to implement variable access to different array elements (while preserving BTF types).
On Tue, Dec 19, 2023 at 11:54 AM Andrei Matei <andreimatei1@gmail.com> wrote: > > On Tue, Dec 19, 2023 at 2:03 PM Andrii Nakryiko > <andrii.nakryiko@gmail.com> wrote: > > > > On Sat, Dec 16, 2023 at 5:07 PM Andrei Matei <andreimatei1@gmail.com> wrote: > > > > > > This patch simplifies the verification of size arguments associated to > > > pointer arguments to helpers and kfuncs. Many helpers take a pointer > > > argument followed by the size of the memory access performed to be > > > performed through that pointer. Before this patch, the handling of the > > > size argument in check_mem_size_reg() was confusing and wasteful: if the > > > size register's lower bound was 0, then the verification was done twice: > > > once considering the size of the access to be the lower-bound of the > > > respective argument, and once considering the upper bound (even if the > > > two are the same). The upper bound checking is a super-set of the > > > lower-bound checking(*), except: the only point of the lower-bound check > > > is to handle the case where zero-sized-accesses are explicitly not > > > allowed and the lower-bound is zero. This static condition is now > > > checked explicitly, replacing a much more complex, expensive and > > > confusing verification call to check_helper_mem_access(). > > > > > > Now that check_mem_size_reg() deals directly with the zero_size_allowed > > > checking, the single remaining call to check_helper_mem_access() can > > > pass a static value for the zero_size_allowed arg, instead of > > > propagating a dynamic one. I think this is an improvement, as tracking > > > the wide propagation of zero_sized_allowed is already complicated. > > > > > > This patch also results in better error messages for rejected zero-size > > > reads. Before, the message one would get depended on the type of the > > > pointer and on other conditions, and sometimes the message was plain > > > wrong: in some tests that changed you'll see that the old message was > > > something like "R1 min value is outside of the allowed memory range", > > > where R1 is the pointer register; the error was wrongly claiming that > > > the pointer was bad instead of the size being bad. Other times the > > > information that the size came for a register with a possible range of > > > values was wrong, and the error presented the size as a fixed zero. > > > > > > (*) Besides standing to reason that the checks for a bigger size access > > > are a super-set of the checks for a smaller size access, I have also > > > mechanically verified this by reading the code for all types of > > > pointers. I could convince myself that it's true for all but > > > PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking > > > line-by-line does not immediately prove what we want. If anyone has any > > > qualms, let me know. > > > > > > Signed-off-by: Andrei Matei <andreimatei1@gmail.com> > > > --- > > > kernel/bpf/verifier.c | 85 +++++++++++++++++-- > > > .../bpf/progs/verifier_helper_value_access.c | 45 +++++++++- > > > .../selftests/bpf/progs/verifier_raw_stack.c | 4 +- > > > 3 files changed, 120 insertions(+), 14 deletions(-) > > > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > index 1863826a4ac3..cf2a09408bdc 100644 > > > --- a/kernel/bpf/verifier.c > > > +++ b/kernel/bpf/verifier.c > > > @@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, > > > } > > > } > > > > > > +/* Helper function for logging an error about an invalid attempt to perform a > > > + * (possibly) zero-sized memory access. The pointer being dereferenced is in > > > + * register @ptr_regno, and the size of the access is in register @size_regno. > > > + * The size register is assumed to either be a constant zero or have a zero lower > > > + * bound. > > > + * > > > + * Logs a message like: > > > + * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48 > > > + */ > > > +static void log_zero_size_access_err(struct bpf_verifier_env *env, > > > + int ptr_regno, > > > + int size_regno) > > > +{ > > > + struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno]; > > > + struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno]; > > > + const bool size_is_const = tnum_is_const(size_reg->var_off); > > > + const char *ptr_type_str = reg_type_str(env, ptr_reg->type); > > > + /* allocate a few buffers to be used as parts of the error message */ > > > + char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0}; > > > > this is quite a lot of stack usage, adding this on top of all the > > other stuff we have feels a bit bad > > I could be less wasteful and have a single, smaller buffer. > But do we really care for a leaf function? > It's kernel, so that's at least a consideration, I think. > > > > > + s64 min_off, max_off; > > > + if (!size_is_const) { > > > + snprintf(size_range_buf, sizeof(size_range_buf), > > > + "[0,%lld]", size_reg->umax_value); > > > + } > > > + > > > + if (tnum_is_const(ptr_reg->var_off)) { > > > + min_off = (s64)ptr_reg->var_off.value + ptr_reg->off; > > > + snprintf(off_buf, sizeof(off_buf), "%lld", min_off); > > > + } else { > > > + min_off = ptr_reg->smin_value + ptr_reg->off; > > > + max_off = ptr_reg->smax_value + ptr_reg->off; > > > + snprintf(off_buf, sizeof(off_buf), "[%lld,%lld]", min_off, max_off); > > > + } > > > + > > > + /* attempt to figure out info about the maximum offset that could be allowed */ > > > + switch (ptr_reg->type) { > > > + case PTR_TO_MAP_KEY: > > > + snprintf(max_size_buf, sizeof(max_size_buf), "key_size=%d", ptr_reg->map_ptr->key_size); > > > + break; > > > + case PTR_TO_MAP_VALUE: > > > + snprintf(max_size_buf, sizeof(max_size_buf), "value_size=%d", ptr_reg->map_ptr->value_size); > > > + break; > > > + case PTR_TO_PACKET: > > > + case PTR_TO_PACKET_META: > > > + snprintf(max_size_buf, sizeof(max_size_buf), "packet_size=%d", ptr_reg->range); > > > + break; > > > + case PTR_TO_MEM: > > > + default: > > > + snprintf(max_size_buf, sizeof(max_size_buf), "max_size=N/A"); > > > > we do know the size, reg->mem_size contains addressable memory range > > size for PTR_TO_MEM > > > > > + } > > > + > > > + verbose(env, "invalid %szero-size read. Size comes from R%d=%s. " > > > + "Attempting to dereference *%s R%d: off=%s %s\n", > > > + size_is_const ? "" : "possibly ", > > > + size_regno, size_is_const ? "0" : size_range_buf, > > > + ptr_type_str, ptr_regno, off_buf, max_size_buf); > > > +} > > > + > > > + > > > /* verify arguments to helpers or kfuncs consisting of a pointer and an access > > > * size. > > > * > > > @@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > > struct bpf_call_arg_meta *meta) > > > { > > > int err; > > > + const bool size_is_const = tnum_is_const(reg->var_off); > > > > > > /* This is used to refine r0 return value bounds for helpers > > > * that enforce this value as an upper bound on return values. > > > @@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > > /* The register is SCALAR_VALUE; the access check > > > * happens using its boundaries. > > > */ > > > - if (!tnum_is_const(reg->var_off)) > > > + if (!size_is_const) > > > /* For unprivileged variable accesses, disable raw > > > * mode so that the program is required to > > > * initialize all the memory that the helper could > > > @@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > > return -EACCES; > > > } > > > > > > - if (reg->umin_value == 0) { > > > - err = check_helper_mem_access(env, regno - 1, 0, > > > - zero_size_allowed, > > > - meta); > > > - if (err) > > > - return err; > > > + if (reg->umin_value == 0 && !zero_size_allowed) { > > > + log_zero_size_access_err(env, regno-1, regno); > > > + return -EACCES; > > > } > > > > > > if (reg->umax_value >= BPF_MAX_VAR_SIZ) { > > > @@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, > > > regno); > > > return -EACCES; > > > } > > > + /* If !zero_size_allowed, we already checked that umin_value > 0, so > > > + * umax_value should also be > 0. > > > + */ > > > + if (reg->umax_value == 0 && !zero_size_allowed) { > > > + verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); > > > + return -EFAULT; > > > + } > > > err = check_helper_mem_access(env, regno - 1, > > > reg->umax_value, > > > - zero_size_allowed, meta); > > > + /* zero_size_allowed: we asserted above that umax_value is > > > + * not zero if !zero_size_allowed, so we don't need any > > > + * further checks. > > > + */ > > > + true , > > > > if this is the last remaining call, why even have this true parameter > > instead of assuming zero_size_allowed inside > > check_helper_mem_access() ? > > This is the last remaining call to check_helper_mem_access() > in this function, but not globally. There > are many other calls to check_helper_mem_access(), > and some pass `false`. E.g. [1]. Btw, I did generally try to get > a better code structure that would not require this zero_size_allowed > in a million places, but so far failed. > > [1] https://github.com/torvalds/linux/blob/ee5cc0363ea0d587f62349ff3b3e2dfa751832e4/kernel/bpf/verifier.c#L4279 > > > > > nit: dangling space > > > > > + meta); > > > if (!err) > > > err = mark_chain_precision(env, regno); > > > return err; > > > diff --git a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > > > index 692216c0ad3d..9fe10f63c931 100644 > > > --- a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > > > +++ b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c > > > @@ -89,9 +89,14 @@ l0_%=: exit; \ > > > : __clobber_all); > > > } > > > > > > +/* Call a function taking a pointer and a size which doesn't allow the size to > > > + * be zero (i.e. bpf_trace_printk() declares the second argument to be > > > + * ARG_CONST_SIZE, not ARG_CONST_SIZE_OR_ZERO). We attempt to pass zero for the > > > + * size and expect to fail. > > > + */ > > > SEC("tracepoint") > > > __description("helper access to map: empty range") > > > -__failure __msg("invalid access to map value, value_size=48 off=0 size=0") > > > +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48") > > > > This comes from "BPF old-timer", so take it with a grain of salt, but > > current error doesn't feel too bad already and is quite > > understandable, tbh. > > > > In any case, let's split off the error formatting changes (they are > > quire big) from the check logic change and post it as two separate > > patches (they might be in a single patch set) > > Just to clarify -- in v1 I had not done anything about error handling, and you > observed that some error messages now had less information than before (but, > for the record, at the same time some of the errors before were misleading or > even wrong because sometimes they didn't even reference the size register and > even when they did, they pretended that the size register was the constant > zero). In order to keep the information that the errors had before, somehow the > type of pointer involved needs to be taken into account; the error needs to > look differently for different kinds of pointers. That's how I ended up going > medieval and writing the error logging function. You don't seem enthused about medieval, lol :) > all the code that was required; neither was I. I spent some time looking around > for something better and more code reuse. I've considered writing some more > generic register-printing functions because it seems to me that the verifier > has too many duplicate and incomplete printing logic in error messages. But in > the end I didn't come up with anything better. yes, I already replied to the latest version of the patch. It feels like a bit too much code and effort for just saying "you might dereference memory with zero size read from register Rx". Duplicating register states nicely inside that message seems to be the source of most verbosity in code, and we already do that generically in verifier log anyways. So perhaps just keeping what you have in patch #1 is the way to go. Again, sorry for making you go "medieval" (still lol) and doing all this extra work. > > Now, one might argue that getting a proper per-pointer-type was an advantage of > calling check_helper_mem_access() twice -- so maybe this whole patch is > misguided. But then again, the error messages were not actually good, and also > I'd argue that it'd be a case of the tail wagging the dog to leave the > check_helper_mem_access() call for the benefit of the errors. agreed, that seems like an overkill > > Having said all this, I definitely don't want to push unwanted code on you, so > please confirm that you don't hate the error logging function or... something > else. > > > > > > __naked void access_to_map_empty_range(void) > > > { > > > asm volatile (" \ > > > > [...]
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 1863826a4ac3..cf2a09408bdc 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, } } +/* Helper function for logging an error about an invalid attempt to perform a + * (possibly) zero-sized memory access. The pointer being dereferenced is in + * register @ptr_regno, and the size of the access is in register @size_regno. + * The size register is assumed to either be a constant zero or have a zero lower + * bound. + * + * Logs a message like: + * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48 + */ +static void log_zero_size_access_err(struct bpf_verifier_env *env, + int ptr_regno, + int size_regno) +{ + struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno]; + struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno]; + const bool size_is_const = tnum_is_const(size_reg->var_off); + const char *ptr_type_str = reg_type_str(env, ptr_reg->type); + /* allocate a few buffers to be used as parts of the error message */ + char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0}; + s64 min_off, max_off; + if (!size_is_const) { + snprintf(size_range_buf, sizeof(size_range_buf), + "[0,%lld]", size_reg->umax_value); + } + + if (tnum_is_const(ptr_reg->var_off)) { + min_off = (s64)ptr_reg->var_off.value + ptr_reg->off; + snprintf(off_buf, sizeof(off_buf), "%lld", min_off); + } else { + min_off = ptr_reg->smin_value + ptr_reg->off; + max_off = ptr_reg->smax_value + ptr_reg->off; + snprintf(off_buf, sizeof(off_buf), "[%lld,%lld]", min_off, max_off); + } + + /* attempt to figure out info about the maximum offset that could be allowed */ + switch (ptr_reg->type) { + case PTR_TO_MAP_KEY: + snprintf(max_size_buf, sizeof(max_size_buf), "key_size=%d", ptr_reg->map_ptr->key_size); + break; + case PTR_TO_MAP_VALUE: + snprintf(max_size_buf, sizeof(max_size_buf), "value_size=%d", ptr_reg->map_ptr->value_size); + break; + case PTR_TO_PACKET: + case PTR_TO_PACKET_META: + snprintf(max_size_buf, sizeof(max_size_buf), "packet_size=%d", ptr_reg->range); + break; + case PTR_TO_MEM: + default: + snprintf(max_size_buf, sizeof(max_size_buf), "max_size=N/A"); + } + + verbose(env, "invalid %szero-size read. Size comes from R%d=%s. " + "Attempting to dereference *%s R%d: off=%s %s\n", + size_is_const ? "" : "possibly ", + size_regno, size_is_const ? "0" : size_range_buf, + ptr_type_str, ptr_regno, off_buf, max_size_buf); +} + + /* verify arguments to helpers or kfuncs consisting of a pointer and an access * size. * @@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta) { int err; + const bool size_is_const = tnum_is_const(reg->var_off); /* This is used to refine r0 return value bounds for helpers * that enforce this value as an upper bound on return values. @@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, /* The register is SCALAR_VALUE; the access check * happens using its boundaries. */ - if (!tnum_is_const(reg->var_off)) + if (!size_is_const) /* For unprivileged variable accesses, disable raw * mode so that the program is required to * initialize all the memory that the helper could @@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, return -EACCES; } - if (reg->umin_value == 0) { - err = check_helper_mem_access(env, regno - 1, 0, - zero_size_allowed, - meta); - if (err) - return err; + if (reg->umin_value == 0 && !zero_size_allowed) { + log_zero_size_access_err(env, regno-1, regno); + return -EACCES; } if (reg->umax_value >= BPF_MAX_VAR_SIZ) { @@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env, regno); return -EACCES; } + /* If !zero_size_allowed, we already checked that umin_value > 0, so + * umax_value should also be > 0. + */ + if (reg->umax_value == 0 && !zero_size_allowed) { + verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n"); + return -EFAULT; + } err = check_helper_mem_access(env, regno - 1, reg->umax_value, - zero_size_allowed, meta); + /* zero_size_allowed: we asserted above that umax_value is + * not zero if !zero_size_allowed, so we don't need any + * further checks. + */ + true , + meta); if (!err) err = mark_chain_precision(env, regno); return err; diff --git a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c index 692216c0ad3d..9fe10f63c931 100644 --- a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c +++ b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c @@ -89,9 +89,14 @@ l0_%=: exit; \ : __clobber_all); } +/* Call a function taking a pointer and a size which doesn't allow the size to + * be zero (i.e. bpf_trace_printk() declares the second argument to be + * ARG_CONST_SIZE, not ARG_CONST_SIZE_OR_ZERO). We attempt to pass zero for the + * size and expect to fail. + */ SEC("tracepoint") __description("helper access to map: empty range") -__failure __msg("invalid access to map value, value_size=48 off=0 size=0") +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48") __naked void access_to_map_empty_range(void) { asm volatile (" \ @@ -113,6 +118,38 @@ l0_%=: exit; \ : __clobber_all); } +/* Like the test above, but this time the size register is not known to be zero; + * its lower-bound is zero though, which is still unacceptible. + */ +SEC("tracepoint") +__description("helper access to map: possibly-empty range") +__failure __msg("invalid possibly zero-size read. Size comes from R2=[0,4]. Attempting to dereference *map_value R1: off=0 value_size=48") +__naked void access_to_map_possibly_empty_range(void) +{ + asm volatile (" \ + r2 = r10; \ + r2 += -8; \ + r1 = 0; \ + *(u64*)(r2 + 0) = r1; \ + r1 = %[map_hash_48b] ll; \ + call %[bpf_map_lookup_elem]; \ + if r0 == 0 goto l0_%=; \ + r1 = r0; \ + /* Read an unknown value */ \ + r7 = *(u64*)(r0 + 0); \ + /* Make it small and positive, to avoid other errors */ \ + r7 &= 4; \ + r2 = 0; \ + r2 += r7; \ + call %[bpf_trace_printk]; \ +l0_%=: exit; \ +" : + : __imm(bpf_map_lookup_elem), + __imm(bpf_trace_printk), + __imm_addr(map_hash_48b) + : __clobber_all); +} + SEC("tracepoint") __description("helper access to map: out-of-bound range") __failure __msg("invalid access to map value, value_size=48 off=0 size=56") @@ -221,7 +258,7 @@ l0_%=: exit; \ SEC("tracepoint") __description("helper access to adjusted map (via const imm): empty range") -__failure __msg("invalid access to map value, value_size=48 off=4 size=0") +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=4 value_size=48") __naked void via_const_imm_empty_range(void) { asm volatile (" \ @@ -386,7 +423,7 @@ l0_%=: exit; \ SEC("tracepoint") __description("helper access to adjusted map (via const reg): empty range") -__failure __msg("R1 min value is outside of the allowed memory range") +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48") __naked void via_const_reg_empty_range(void) { asm volatile (" \ @@ -556,7 +593,7 @@ l0_%=: exit; \ SEC("tracepoint") __description("helper access to adjusted map (via variable): empty range") -__failure __msg("R1 min value is outside of the allowed memory range") +__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48") __naked void map_via_variable_empty_range(void) { asm volatile (" \ diff --git a/tools/testing/selftests/bpf/progs/verifier_raw_stack.c b/tools/testing/selftests/bpf/progs/verifier_raw_stack.c index f67390224a9c..c133d9d2c45e 100644 --- a/tools/testing/selftests/bpf/progs/verifier_raw_stack.c +++ b/tools/testing/selftests/bpf/progs/verifier_raw_stack.c @@ -64,7 +64,7 @@ __naked void load_bytes_negative_len_2(void) SEC("tc") __description("raw_stack: skb_load_bytes, zero len") -__failure __msg("invalid zero-sized read") +__failure __msg("invalid zero-size read. Size comes from R4=0. Attempting to dereference *fp R3: off=-8 max_size=N/A") __naked void skb_load_bytes_zero_len(void) { asm volatile (" \ @@ -333,7 +333,7 @@ __naked void load_bytes_invalid_access_5(void) SEC("tc") __description("raw_stack: skb_load_bytes, invalid access 6") -__failure __msg("invalid zero-sized read") +__failure __msg("invalid zero-size read. Size comes from R4=0. Attempting to dereference *fp R3: off=-512 max_size=N/A") __naked void load_bytes_invalid_access_6(void) { asm volatile (" \
This patch simplifies the verification of size arguments associated to pointer arguments to helpers and kfuncs. Many helpers take a pointer argument followed by the size of the memory access performed to be performed through that pointer. Before this patch, the handling of the size argument in check_mem_size_reg() was confusing and wasteful: if the size register's lower bound was 0, then the verification was done twice: once considering the size of the access to be the lower-bound of the respective argument, and once considering the upper bound (even if the two are the same). The upper bound checking is a super-set of the lower-bound checking(*), except: the only point of the lower-bound check is to handle the case where zero-sized-accesses are explicitly not allowed and the lower-bound is zero. This static condition is now checked explicitly, replacing a much more complex, expensive and confusing verification call to check_helper_mem_access(). Now that check_mem_size_reg() deals directly with the zero_size_allowed checking, the single remaining call to check_helper_mem_access() can pass a static value for the zero_size_allowed arg, instead of propagating a dynamic one. I think this is an improvement, as tracking the wide propagation of zero_sized_allowed is already complicated. This patch also results in better error messages for rejected zero-size reads. Before, the message one would get depended on the type of the pointer and on other conditions, and sometimes the message was plain wrong: in some tests that changed you'll see that the old message was something like "R1 min value is outside of the allowed memory range", where R1 is the pointer register; the error was wrongly claiming that the pointer was bad instead of the size being bad. Other times the information that the size came for a register with a possible range of values was wrong, and the error presented the size as a fixed zero. (*) Besides standing to reason that the checks for a bigger size access are a super-set of the checks for a smaller size access, I have also mechanically verified this by reading the code for all types of pointers. I could convince myself that it's true for all but PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking line-by-line does not immediately prove what we want. If anyone has any qualms, let me know. Signed-off-by: Andrei Matei <andreimatei1@gmail.com> --- kernel/bpf/verifier.c | 85 +++++++++++++++++-- .../bpf/progs/verifier_helper_value_access.c | 45 +++++++++- .../selftests/bpf/progs/verifier_raw_stack.c | 4 +- 3 files changed, 120 insertions(+), 14 deletions(-)