Re: [PATCH bpf-next 1/7] bpf: regsafe() must not skip check_ids()

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > The verifier.c:regsafe() has the following shortcut:
> > 
> >         equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
> >         ...
> >         if (equal)
> >                 return true;
> > 
> > Which is executed regardless old register type. This is incorrect for
> > register types that might have an ID checked by check_ids(), namely:
> >  - PTR_TO_MAP_KEY
> >  - PTR_TO_MAP_VALUE
> >  - PTR_TO_PACKET_META
> >  - PTR_TO_PACKET
> > 
> > The following pattern could be used to exploit this:
> > 
> >   0: r9 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
> >   1: r8 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
> >   2: r7 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
> >   3: r6 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
> >   4: if r6 > r7 goto +1         ; No new information about the state
> >                                 ; is derived from this check, thus
> >                                 ; produced verifier states differ only
> >                                 ; in 'insn_idx'.
> >   5: r9 = r8                    ; Optionally make r9.id == r8.id.
> >   --- checkpoint ---            ; Assume is_state_visisted() creates a
> >                                 ; checkpoint here.
> >   6: if r9 == 0 goto <exit>     ; Nullness info is propagated to all
> >                                 ; registers with matching ID.
> >   7: r1 = *(u64 *) r8           ; Not always safe.
> > 
> > Verifier first visits path 1-7 where r8 is verified to be not null
> > at (6). Later the jump from 4 to 6 is examined. The checkpoint for (6)
> > looks as follows:
> >   R8_rD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0)
> >   R9_rwD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0)
> >   R10=fp0
> > 
> > The current state is:
> >   R0=... R6=... R7=... fp-8=...
> >   R8=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0)
> >   R9=map_value_or_null(id=1,off=0,ks=4,vs=8,imm=0)
> >   R10=fp0
> > 
> > Note that R8 states are byte-to-byte identical, so regsafe() would
> > exit early and skip call to check_ids(), thus ID mapping 2->2 will not
> > be added to 'idmap'. Next, states for R9 are compared: these are not
> > identical and check_ids() is executed, but 'idmap' is empty, so
> > check_ids() adds mapping 2->1 to 'idmap' and returns success.
> > 
> > This commit pushes the 'equal' down to register types that don't need
> > check_ids().
> > 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  kernel/bpf/verifier.c | 29 ++++++++---------------------
> >  1 file changed, 8 insertions(+), 21 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 3194e9d9e4e4..d05c5d0344c6 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > 
> >         equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
> > 
> > -       if (rold->type == PTR_TO_STACK)
> > -               /* two stack pointers are equal only if they're pointing to
> > -                * the same stack frame, since fp-8 in foo != fp-8 in bar
> > -                */
> > -               return equal && rold->frameno == rcur->frameno;
> > -
> > -       if (equal)
> > -               return true;
> > -
> >         if (rold->type == NOT_INIT)
> >                 /* explored state can't have used this */
> >                 return true;
> > @@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> >                 return false;
> >         switch (base_type(rold->type)) {
> >         case SCALAR_VALUE:
> > +               if (equal)
> > +                       return true;
> >                 if (env->explore_alu_limits)
> >                         return false;
> >                 if (rcur->type == SCALAR_VALUE) {
> > @@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> >                 /* new val must satisfy old val knowledge */
> >                 return range_within(rold, rcur) &&
> >                        tnum_in(rold->var_off, rcur->var_off);
> > -       case PTR_TO_CTX:
> > -       case CONST_PTR_TO_MAP:
> > -       case PTR_TO_PACKET_END:
> > -       case PTR_TO_FLOW_KEYS:
> > -       case PTR_TO_SOCKET:
> > -       case PTR_TO_SOCK_COMMON:
> > -       case PTR_TO_TCP_SOCK:
> > -       case PTR_TO_XDP_SOCK:
> > -               /* Only valid matches are exact, which memcmp() above
> > -                * would have accepted
> > +       case PTR_TO_STACK:
> > +               /* two stack pointers are equal only if they're pointing to
> > +                * the same stack frame, since fp-8 in foo != fp-8 in bar
> >                  */
> > +               return equal && rold->frameno == rcur->frameno;
> >         default:
> > -               /* Don't know what's going on, just say it's not safe */
> > -               return false;
> > +               /* Only valid matches are exact, which memcmp() */
> > +               return equal;
> 
> Is it safe to assume this for any possible register type? Wouldn't
> register types that use id and/or ref_obj_id need extra checks here? I
> think preexisting default was a safer approach, in which if we forgot
> to explicitly add support for some new or updated register type, the
> worst thing is that for that *new* register we'd have suboptimal
> verification performance, but not safety concerns.

Well, I don't think that this commit changes regsafe() behavior in
this regard. Here is how the code was structured before this commit:

static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
		    struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)
{
	bool equal;

	if (!(rold->live & REG_LIVE_READ))
		return true;
	equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
	if (rold->type == PTR_TO_STACK)
		return equal && rold->frameno == rcur->frameno;
--->	if (equal)
		return true;
	if (rold->type == NOT_INIT)
		return true;
	if (rcur->type == NOT_INIT)
		return false;
	switch (base_type(rold->type)) {
	case SCALAR_VALUE:
        	... it's own logic, always returns ...
	case PTR_TO_MAP_KEY:
	case PTR_TO_MAP_VALUE:
        	... it's own logic, always returns ...
	case PTR_TO_PACKET_META:
	case PTR_TO_PACKET:
        	... it's own logic, always returns ...
	case PTR_TO_CTX:
	case CONST_PTR_TO_MAP:
	case PTR_TO_PACKET_END:
	case PTR_TO_FLOW_KEYS:
	case PTR_TO_SOCKET:
	case PTR_TO_SOCK_COMMON:
	case PTR_TO_TCP_SOCK:
	case PTR_TO_XDP_SOCK:
	default:
		return false;
	}

	/* Shouldn't get here; if we do, say it's not safe */
	WARN_ON_ONCE(1);
	return false;
}

So the "safe if byte-to-byte equal" behavior was present already.
I can add an explicit list of types to the "return equal;" branch
and add a default "return false;" branch if you think that it is
more fool-proof.

> 
> 
> >         }
> > 
> >         /* Shouldn't get here; if we do, say it's not safe */
> > --
> > 2.34.1
> >