On Tue, Dec 12, 2023 at 6:47 PM Andrii Nakryiko
<andrii.nakryiko@xxxxxxxxx> wrote:
>
> On Sun, Dec 10, 2023 at 2:55 PM Andrei Matei <andreimatei1@xxxxxxxxx> 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.
>
> yeah, I think for PTR_TO_BTF_ID (at least conceptually, I don't know
> if we support this now or not) actual range is important, we can't
> just assume [0, umax] range. [umin, umax] might be valid if it falls
> completely inside, say, array, but if it crosses two fields, then it
> would be rejected. Again, not saying we do these checks today, but
> this is where I see the problem. Simplifying [umin, umax] into [0,
> umax] will be valid only for dumb opaque memory regions, which
> PTR_TO_BTF_ID isn't really
I'm not sure I know how to interpret what you're saying here :). I think you're
saying that... patch is OK, right?
There are two ranges at play - the offset range and the size range - and I'm
not entirely sure which one you're talking about. So, before, for PTR_TO_BTF_ID
(just like for every other kind of pointer) we were doing two checks:
1. offset: [range from regno-1], size: 0
2. offset: [range from @regno-1], size: umax of @regno
This patch removes check 1.
Note that the umin for @regno never came into play - neither before this patch,
nor after this patch.
For PTR_TO_BTF_ID, just like for every other kind of pointer, I think using
(umax of @regno) for the size is enough. I imagine that the considerations are
about whether the read can potentially cross fields, like you're saying. But
considering the maximum possible size I think is enough for that check -- I
don't think we should take the minimum possible size into consideration. So,
the range to check would be [minimum possible offset + maximum possible size,
maximum possible offset + maximum possible size]. In other words, given a
certain offset, there's no such thing as a read that's "too small", only a read
that's "too large", correct?
>
> >
> > Signed-off-by: Andrei Matei <andreimatei1@xxxxxxxxx>
> > ---
> > kernel/bpf/verifier.c | 34 ++++++++++----
> > .../bpf/progs/verifier_helper_value_access.c | 45 +++++++++++++++++--
> > .../selftests/bpf/progs/verifier_raw_stack.c | 2 +-
> > 3 files changed, 68 insertions(+), 13 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index fb690539d5f6..022833903157 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -7258,6 +7258,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.
> > @@ -7272,7 +7273,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
> > @@ -7286,12 +7287,17 @@ 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) {
> > + if (size_is_const) {
> > + verbose(env, "R%d invalid zero-sized read\n", regno);
> > + } else {
> > + char tn_buf[48];
> > +
> > + tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
> > + verbose(env, "R%d invalid possibly-zero-sized read: u64=[%#llx, %#llx] var_off=%s\n",
> > + regno, reg->umin_value, reg->umax_value, tn_buf);
>
> for retval checks we decided to not care about tnum at all, so I think
> it makes sense to do that here as well. tnum provides no benefits in
> range checking and will be just an eye sore for users
>
>
> > + }
> > + return -EACCES;
> > }
> >
> > if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
> > @@ -7299,9 +7305,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..7c99c7bae09e 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("R2 invalid zero-sized read")
> > __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("R2 invalid possibly-zero-sized read: u64=[0x0, 0x4] var_off=(0x0; 0x4)")
> > +__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("R2 invalid zero-sized read")
>
> I wouldn't say this the new message is strictly an improvement, tbh.
> Offset is definitely useful, value_size is a nice hint as well. So I
> personally would prefer details in the original message
>
> > __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("R2 invalid zero-sized read")
> > __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("R2 invalid zero-sized read")
>
> btw, it's "*possible" zero-sized read", right?
>
> > __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..3dbda85e2997 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("R4 invalid zero-sized read")
> > __naked void skb_load_bytes_zero_len(void)
> > {
> > asm volatile (" \
> > --
> > 2.40.1
> >
