Re: [PATCH bpf-next] bpf: Simplify checking size of helper accesses

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux