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