Re: [PATCH bpf-next v2 1/4] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2023-05-31 at 13:12 -0700, Andrii Nakryiko wrote:
> On Wed, May 31, 2023 at 12:30 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Wed, 2023-05-31 at 11:29 -0700, Andrii Nakryiko wrote:
> > > On Wed, May 31, 2023 at 10:21 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > 
> > > > On Tue, 2023-05-30 at 14:37 -0700, Andrii Nakryiko wrote:
> > > > [...]
> > > > > Also, it might make sense to drop SCALAR register IDs as soon as we
> > > > > have only one instance of it left (e.g., if "paired" register was
> > > > > overwritten already). I.e., aggressively drop IDs when they become
> > > > > useless. WDYT?
> > > > 
> > > > I added modification which resets sole scalar IDs to zero before
> > > > states comparison, it shows some speedup but is still slow:
> > > > 
> > > >   Filter        | Number of programs | Number of programs
> > > >                 | patch #1           | patch #1 + sole scalar ID pruning
> > > >   ----------------------------------------------------------------------
> > > >   states_pct>10 | 40                 | 40
> > > >   states_pct>20 | 20                 | 19
> > > >   states_pct>30 | 15                 | 13
> > > >   states_pct>40 | 11                 | 8
> > > > 
> > > > (Out of 177 programs).
> > > > 
> > > > I'll modify mark_chain_precision() to propagate precision marks for
> > > > find_equal_scalars(), so that it could be compared to current patch #3
> > > > in terms of code complexity and verification performance.
> > > > 
> > > > If you have any thoughts regarding my previous email, please share.
> > > > 
> > > 
> > > Yep, I do. Given SCALAR registers with the same ID are meant to "share
> > > the destiny", shouldn't it be required that when we mark r6 as precise
> > > we should automatically mark linked r7 as precise at the same point.
> > > So in your example:
> > > 
> > > 7: r9 += r6
> > > 
> > > should be where we request both r6 and r7 (and whatever other register
> > > has the same ID) to be marked as precise. It should be very easy to
> > > implement, especially given my recent refactoring with
> > > mark_chain_precision_batch.
> > 
> > Ok, I'll modify the `struct backtrack_state` as follows:
> > 
> >   struct backtrack_state {
> >         struct bpf_verifier_env *env;
> >         u32 frame;
> >         u32 reg_masks[MAX_CALL_FRAMES];
> > +       u32 reg_ids[MAX_CALL_FRAMES];
> >         u64 stack_masks[MAX_CALL_FRAMES];
> > +       u64 stack_ids[MAX_CALL_FRAMES];
> >   };
> > 
> > And add corresponding logic to backtrack_insn().
> 
> I don't see why you need to change anything about backtrack_state at
> all, so we are not on the same page.
> 
> What I propose is that in mark_chain_precision(), when given regno, go
> over all *current* registers with the same ID, and set all of them as
> "to be marked precise". And then call mark_chain_precision_batch().
> See propagate_precision() for how we do similar stuff for bulk
> precision propagation.
> 
> backtrack_state shouldn't need to know about IDs, unless I'm missing something

Consider a modified version of the original example:

  1: r9 = ... some pointer with range X ...
  2: r6 = ... unbound scalar ID=a ...
  3: r7 = ... unbound scalar ID=b ...
  4: if (r6 > r7) goto +1
  5: r7 = r6
  6: if (r7 > X) goto ...
  7: r7 = 0
  8: r9 += r6

Suppose verification path is 1-8, the ID assignments are:

                            r6.id r7.id
  4: if (r6 > r7) goto +1   a     b
  5: r7 = r6                a     a
  6: if (r7 > X) goto ...   a     a
  7: r7 = 0                 a     -
  8: r9 += r6               a     -

When mark_chain_precision() is called at (8) it no longer knows that
r6 and r7 shared the same ID at some point in the past. What you
suggest won't work in this case, what I suggest won't work as well.

Looks like the only way to do it correctly is to save ID assignments
after each find_equal_scalars() (for (6) in this example) in the
bpf_verifier_state, and use this information in backtrack_insn().
For example, extend jmp_history.

> 
> > 
> > > The question I have (and again, haven't spent any time thinking about
> > > any other corner cases, sorry) is whether that alone would be a proper
> > > fix?
> > 
> > As far as I understand, in terms of correctness it would be a proper fix.
> > In terms of performance, I hope that it would be enough but we will see.
> 
> ok, let's try that then, before we commit to u32_hashset stuff
> 
> > 
> > > As for this u32_hashset, it just feels like a big overkill, tbh. If we
> > > have to do something like that, wouldn't it be better to, say, set
> > > highest bit in reg->id (for all linked registers, of course) to mark
> > > it as "used for range checks" instead of maintaining a separate check?
> > 
> > Unfortunately no, because this ID change would have to be propagated
> > backwards. It was the first implementation I tried.
> > 
> > > But just the whole idea of keeping track of some special circumstances
> > > under which IDs are meaningful seems wrong... All this logic is
> > > complicated, now we are adding another layer of complexity on top. And
> > > the complexity is not in the code, it's in thinking about all possible
> > > scenarios and their interactions.
> > 
> > I agree that adding more layers is a complication in itself.
> > Thank you for your input.
> > 
> > > > [...]
> >