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 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().

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

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

> > [...]