On Wed, Dec 14, 2022 at 5:26 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> > On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@xxxxxxxxx> 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@xxxxxxxxx>
> > > ---
> > > 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.
Sorry, I didn't claim you made it worse. But given we are refactoring
this piece of code, let's make it more "safe-by-default".
So yeah, I think an explicit list of all the recognized register types
would be better, IMO.
>
> >
> >
> > > }
> > >
> > > /* Shouldn't get here; if we do, say it's not safe */
> > > --
> > > 2.34.1
> > >
>
