Re: [BUG] verifier escape with iteration helpers (bpf_loop, ...)

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2023-09-20 at 09:37 -0700, Andrii Nakryiko wrote:
> On Tue, Sep 19, 2023 at 5:06 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
[...]
> > 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.
> > 
> 
> I guess then r0 setting would have to happen at BPF_EXIT as well,
> right? Is that a problem?

Ideally yes, r0 should be set at BPF_EXIT, but that would require:
- splitting check_helper_call() in two parts;
- separate handling for helpers that don't call callbacks.

For now I decided against it and r0 in caller's frame is modified
immediately. This is safe, because check_helper_call() logic does not
rely on r0 value (and check_helper_call() would be called again and
again for each new iteration). But it is a hack and maybe change in
check_helper_call() structure is indeed necessary. I leave it out for
now as a secondary concern.

[...]
> > > > - 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.
> 
> wouldn't this be a problem for just any subprog if we don't check the
> looping condition on the entry instruction? Perhaps that's a separate
> issue that needs generic fix?

This didn't occur to me. In the following example loop detection does
not work indeed, however verifier still bails out correctly upon
instruction processing limit:

    SEC("fentry/" SYS_PREFIX "sys_nanosleep")
    __failure
    int iter_next_infinite_loop(const void *ctx)
    {
    	struct bpf_iter_num it;

    	bpf_iter_num_new(&it, 0, 10);
    	for (;;)
    		bpf_iter_num_next(&it);
    	bpf_iter_num_destroy(&it);
    	return 0;
    }

[...]