Re: [PATCH bpf-next v4 06/10] bpf: Track provenance for pointers formed from referenced PTR_TO_BTF_ID

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

On Sun, Dec 19, 2021 at 09:30:32AM IST, Alexei Starovoitov wrote:
> On Sat, Dec 18, 2021 at 7:18 PM Kumar Kartikeya Dwivedi
> <memxor@gmail.com> wrote:
> >
> > On Sun, Dec 19, 2021 at 07:58:39AM IST, Alexei Starovoitov wrote:
> > > On Fri, Dec 17, 2021 at 07:20:27AM +0530, Kumar Kartikeya Dwivedi wrote:
> > > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > > index b80fe5bf2a02..a6ef11db6823 100644
> > > > --- a/include/linux/bpf_verifier.h
> > > > +++ b/include/linux/bpf_verifier.h
> > > > @@ -128,6 +128,16 @@ struct bpf_reg_state {
> > > >      * allowed and has the same effect as bpf_sk_release(sk).
> > > >      */
> > > >     u32 ref_obj_id;
> > > > +   /* This is set for pointers which are derived from referenced
> > > > +    * pointer (e.g. PTR_TO_BTF_ID pointer walking), so that the
> > > > +    * pointers obtained by walking referenced PTR_TO_BTF_ID
> > > > +    * are appropriately invalidated when the lifetime of their
> > > > +    * parent object ends.
> > > > +    *
> > > > +    * Only one of ref_obj_id and parent_ref_obj_id can be set,
> > > > +    * never both at once.
> > > > +    */
> > > > +   u32 parent_ref_obj_id;
> > >
> > > How would it handle parent of parent?
> >
> > When you do:
> >
> > r1 = acquire();
> >
> > it gets ref_obj_id as N, then when you load r1->next, it does mark_btf_ld_reg
> > with reg->ref_obj_id ?: reg->parent_ref_obj_id, the latter is zero so it copies
> > ref, but into parent_ref_obj_id.
> >
> > r2 = r1->next;
> >
> > From here on, parent_ref_obj_id is propagated into all further mark_btf_ld_reg,
> > so if we do since ref_obj_id will be zero from previous mark_btf_ld_reg:
> >
> > r3 = r2->next; // it will copy parent_ref_obj_id
> >
> > I think it even works fine when you reach it indirectly, like foo->bar->foo,
> > if first foo is referenced.
> >
> > ... but maybe I missed some detail, do you see a problem in this approach?
> >
> > > Did you consider map_uid approach ?
> > > Similar uid can be added for PTR_TO_BTF_ID.
> > > Then every such pointer will be unique. Each deref will get its own uid.
> >
> > I'll look into it, I didn't consider it before. My idea was to invalidate
> > pointers obtained from a referenced ptr_to_btf_id so I copied the same
> > ref_obj_id into parent_ref_obj_id, so that it can be matched during release. How
> > would that work in the btf_uid approach if they are unique? Do we copy the same
> > ref_obj_id into btf_uid? Then it's not very different except being btf_id ptr
> > specific state, right?
> >
> > Or we can copy ref_obj_id and also set uid to disallow it from being released,
> > but still allow invalidation.
>
> The goal is to disallow:
> struct foo { struct foo *next; };
>
> r1 = acquire(...); // BTF ID of struct foo
> if (r1) {
>         r2 = r1->next;
>         release(r2);
> }
>
> right?

Yes, but not just that, we also want to prevent use of r2 after release(r1).
Then snippet above is problematic if we get same BTF ID ptr in r2 and try to
solve that in the naive way (just copy ref_obj_id in dst_reg), because
verifier will not be able to distinguish between r1 and r2 for purposes of
release kfunc call.

> With btf_uid approach each deref gets its own uid.
> r2 = r1->next
> and
> r3 = r1->next
> will get different uids.
> When type == PTR_TO_BTF_ID its reg->ref_obj_id will be considered
> together with btf_uid.
> Both ref_obj_id and btf_uid need to be the same.
>

That will indeed work, I can rework it this way. After acquire_reference_state
we can set btf_uid = ref_obj_id, then simply assign fresh btf_uid on
mark_btf_ld_reg.

Not pushing back, but I am trying to understand why you think this is better
than simply doing it the way in this patch? What additional cases is btf_uid
approach considering that I am missing? I don't understand what we get if each
deref gets its own unique btf_uid.

There are only two objectives: prevent use of r2 after r1 is gone, and prevent
r2 being passed into release kfunc (discovered when I simply copied ref_obj_id).

> But let's go back a bit.
> Why ref_obj_id is copied on deref?

It is, but into parent_ref_obj_id, to match during release_reference.

> Shouldn't r2 get a different ref_obj_id after r2 = r1->next ?

It's ref_obj_id is still 0.

Thinking about this more, we actually only need 1 extra bit of information in
reg_state, not even a new member. We can simply copy ref_obj_id and set this
bit, then we can reject this register during release but consider it during
release_reference.

--
Kartikeya