Re: [PATCH bpf v3 1/2] bpf: Fix verifier tracking scalars on spill

[Yonghong Song <yhs@meta.com>]

On 6/6/23 2:42 PM, Maxim Mikityanskiy wrote:
> From: Maxim Mikityanskiy <maxim@isovalent.com>
> 
> The following scenario describes a verifier bypass in privileged mode
> (CAP_BPF or CAP_SYS_ADMIN):
> 
> 1. Prepare a 32-bit rogue number.
> 2. Put the rogue number into the upper half of a 64-bit register, and
>     roll a random (unknown to the verifier) bit in the lower half. The
>     rest of the bits should be zero (although variations are possible).
> 3. Assign an ID to the register by MOVing it to another arbitrary
>     register.
> 4. Perform a 32-bit spill of the register, then perform a 32-bit fill to
>     another register. Due to a bug in the verifier, the ID will be
>     preserved, although the new register will contain only the lower 32
>     bits, i.e. all zeros except one random bit.
> 
> At this point there are two registers with different values but the same
> ID, which means the integrity of the verifier state has been corrupted.
> Next steps show the actual bypass:
> 
> 5. Compare the new 32-bit register with 0. In the branch where it's
>     equal to 0, the verifier will believe that the original 64-bit
>     register is also 0, because it has the same ID, but its actual value
>     still contains the rogue number in the upper half.
>     Some optimizations of the verifier prevent the actual bypass, so
>     extra care is needed: the comparison must be between two registers,
>     and both branches must be reachable (this is why one random bit is
>     needed). Both branches are still suitable for the bypass.
> 6. Right shift the original register by 32 bits to pop the rogue number.
> 7. Use the rogue number as an offset with any pointer. The verifier will
>     believe that the offset is 0, while in reality it's the given number.
> 
> The fix is similar to the 32-bit BPF_MOV handling in check_alu_op for
> SCALAR_VALUE. If the spill is narrowing the actual register value, don't
> keep the ID, make sure it's reset to 0.
> 
> Fixes: 354e8f1970f8 ("bpf: Support <8-byte scalar spill and refill")
> Signed-off-by: Maxim Mikityanskiy <maxim@isovalent.com>

LGTM with a small nit below.

Acked-by: Yonghong Song <yhs@fb.com>

> ---
>   kernel/bpf/verifier.c | 7 +++++++
>   1 file changed, 7 insertions(+)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5871aa78d01a..7be23eced561 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3856,6 +3856,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>   	mark_stack_slot_scratched(env, spi);
>   	if (reg && !(off % BPF_REG_SIZE) && register_is_bounded(reg) &&
>   	    !register_is_null(reg) && env->bpf_capable) {
> +		bool reg_value_fits;
> +
>   		if (dst_reg != BPF_REG_FP) {
>   			/* The backtracking logic can only recognize explicit
>   			 * stack slot address like [fp - 8]. Other spill of
> @@ -3867,7 +3869,12 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
>   			if (err)
>   				return err;
>   		}
> +
> +		reg_value_fits = fls64(reg->umax_value) <= BITS_PER_BYTE * size;
>   		save_register_state(state, spi, reg, size);
> +		/* Break the relation on a narrowing spill. */
> +		if (!reg_value_fits)
> +			state->stack[spi].spilled_ptr.id = 0;

I think the code can be simplied like below:

--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4230,6 +4230,8 @@ static int check_stack_write_fixed_off(struct 
bpf_verifier_env *env,
                                 return err;
                 }
                 save_register_state(state, spi, reg, size);
+               if (fls64(reg->umax_value) > BITS_PER_BYTE * size)
+                       state->stack[spi].spilled_ptr.id = 0;
         } else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) &&
                    insn->imm != 0 && env->bpf_capable) {
                 struct bpf_reg_state fake_reg = {};

>   	} else if (!reg && !(off % BPF_REG_SIZE) && is_bpf_st_mem(insn) &&
>   		   insn->imm != 0 && env->bpf_capable) {
>   		struct bpf_reg_state fake_reg = {};