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.
>
>
> > }
> >
> > /* Shouldn't get here; if we do, say it's not safe */
> > --
> > 2.34.1
> >
