On Tue, 2023-09-19 at 16:14 -0700, Andrii Nakryiko wrote:
[...]
> > Hi All,
> >
> > This issue seems stalled, so I took a look over the weekend.
> > I have a work in progress fix, please let me know if you don't agree
> > with direction I'm taking or if I'm stepping on anyone's toes.
> >
> > After some analysis I decided to go with Alexei's suggestion and
> > implement something similar to iterators for selected set of helper
> > functions that accept "looping" callbacks, such as:
> > - bpf_loop
> > - bpf_for_each_map_elem
> > - bpf_user_ringbuf_drain
> > - bpf_timer_set_callback (?)
Hi Andrii, thank you for taking a look.
> As Kumar mentioned, pretty much all helpers with callbacks are either
> 0-1, or 0-1-many cases, so all of them (except for the async callback
> ones that shouldn't be accepting parent stack pointers) should be
> validated.
Yes, makes sense. I need to finish the fix for bpf_loop first, as it
seems as a good representative for many possible issues.
> > The sketch of the fix looks as follows:
> > - extend struct bpf_func_state with callback iterator state information:
> > - active/non-active flag
>
> not sure why you need this flag
Note:
I have a better version of the fix locally but will share it a bit later.
It actually depends on states_equal() discussion in the sibling thread.
In mu upgraded version I use non-zero depth as an indicator the.
So no separate flag in the end.
> > - depth
>
> yep, this seems necessary
>
> > - r1-r5 state at the entry to callback;
>
> not sure why you need this, this should be part of func_state already?
This was a bit tricky but I think I figured an acceptable solution w/o
extra copies for r1-r5. The tricky part is the structure of
check_helper_call():
- collect arguments 'meta' info & check arguments
- call __check_func_call():
- setup frame for callback;
- schedule next instruction index to be callback entry;
- reset r1-r5 in caller's frame;
- set r0 in caller's frame.
The problem is that check_helper_call() resets caller's r1-r5
immediately. I figured that this reset could be done at BPF_EXIT
processing for callback instead => no extra copy needed.
> > - extend __check_func_call() to setup callback iterator state when
> > call to suitable helper function is processed;
>
> this logic is "like iterator", but it's not exactly the same, so I
> don't think we should reuse bpf_iter state (as you can see above with
> active/non-active flag, for example)
Yes, I agree, already removed this locally.
> > - extend BPF_EXIT processing (prepare_func_exit()) to queue new
> > callback visit upon return from iterating callback
> > (similar to process_iter_next_call());
>
> as mentioned above, we should simulate "no callback called" situation
> as well, don't forget about that
Yeap
> > - extend is_state_visited() to account for callback iterator hits in a
> > way similar to regular iterators;
> > - extend backtrack_insn() to correctly react to jumps from callback
> > exit to callback entry.
> >
> > I have a patch (at the end of this email) that correctly recognizes
> > the bpf_loop example in this thread as unsafe. However this patch has
> > a few deficiencies:
> >
> > - verif_scale_strobemeta_bpf_loop selftest is not passing, because
> > read_map_var function invoked from the callback continuously
> > increments 'payload' pointer used in subsequent iterations.
> >
> > In order to handle such code I need to add an upper bound tracking
> > for iteration depth (when such bound could be deduced).
>
> if the example is broken and really can get out of bounds, we should
> fix an example to be provable within bounds no matter how many
> iterations it was called with
For that particular case number of iterations guarantees that payload
pointer will not get out of bounds. It is bumped up 4 bytes on each
iteration, but the number of iterations and buffer size correlate to
avoid out of bound access.
> > - loop detection is broken for simple callback as below:
> >
> > static int loop_callback_infinite(__u32 idx, __u64 *data)
> > {
> > for (;;)
> > (*ctx)++;
> > return 0;
> > }
> >
> > To handle such code I need to change is_state_visited() to do
> > callback iterator loop/hit detection on exit from callback
> > (returns are not prune points at the moment), currently it is done
> > on entry.
>
> I'm a bit confused. What's ctx in the above example? And why loop
> detection doesn't detect for(;;) loop right now?
It's an implementation detail for the fix sketch shared in the parent
email. It can catch cases like this:
... any insn ...;
for (;;)
(*ctx)++;
return 0;
But cannot catch case like this:
for (;;)
(*ctx)++;
return 0;
In that sketch I jump to the callback start from callback return and
callback entry needs two checks:
- iteration convergence
- simple looping
Because of the code structure only iteration convergence check was done.
Locally, I fixed this issue by jumping to the callback call instruction
instead.
> > - the callback as bellow currently causes state explosion:
> >
> > static int precise1_callback(__u32 idx, struct precise1_ctx *ctx)
> > {
> > if (idx == 0)
> > ctx->a = 1;
> > if (idx == 1 && ctx->a == 1)
> > ctx->b = 1;
> > return 0;
> > }
>
> why state explosion? there should be a bunch of different branches
> (idx 0, 1, something else x ctx->a = 1 or not 1 and ctx->b being 1 or
> not), but it should be a fixed number of states? Do you know what
> causes the explosion?
I forgot to do mark_force_checkpoint() at callback entry. Fixed locally.
>
> >
> > I'm not sure yet what to do about this, there are several possibilities:
> > - tweak the order in which states are visited (need to think about it);
> > - check states in bpf_verifier_env::head (not explored yet) for
> > equivalence and avoid enqueuing duplicate states.
> >
> > I'll proceed addressing the issues above on Monday.
> >
> > Thanks,
> > Eduard
> >
> > ---
> >
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index a3236651ec64..5589f55e42ba 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -70,6 +70,17 @@ enum bpf_iter_state {
> > BPF_ITER_STATE_DRAINED,
> > };
> >
> > +struct bpf_iter {
> > + /* BTF container and BTF type ID describing
> > + * struct bpf_iter_<type> of an iterator state
> > + */
> > + struct btf *btf;
> > + u32 btf_id;
> > + /* packing following two fields to fit iter state into 16 bytes */
> > + enum bpf_iter_state state:2;
> > + int depth:30;
> > +};
> > +
> > struct bpf_reg_state {
> > /* Ordering of fields matters. See states_equal() */
> > enum bpf_reg_type type;
> > @@ -115,16 +126,7 @@ struct bpf_reg_state {
> > } dynptr;
> >
> > /* For bpf_iter stack slots */
> > - struct {
> > - /* BTF container and BTF type ID describing
> > - * struct bpf_iter_<type> of an iterator state
> > - */
> > - struct btf *btf;
> > - u32 btf_id;
> > - /* packing following two fields to fit iter state into 16 bytes */
> > - enum bpf_iter_state state:2;
> > - int depth:30;
> > - } iter;
> > + struct bpf_iter iter;
>
> Let's not do this, conceptually processes are similar, but bpf_iter is
> one thing, and this callback validation is another thing. Let's not
> conflate things.
>
> >
> > /* Max size from any of the above. */
> > struct {
>
> [...]
