Re: [PATCH bpf-next 1/7] bpf: Improve verifier JEQ/JNE insn branch taken checking

[Dave Marchevsky <davemarchevsky@meta.com>]

On 3/30/23 1:56 AM, Yonghong Song wrote:
> Currently, for BPF_JEQ/BPF_JNE insn, verifier determines
> whether the branch is taken or not only if both operands
> are constants. Therefore, for the following code snippet,
>   0: (85) call bpf_ktime_get_ns#5       ; R0_w=scalar()
>   1: (a5) if r0 < 0x3 goto pc+2         ; R0_w=scalar(umin=3)
>   2: (b7) r2 = 2                        ; R2_w=2
>   3: (1d) if r0 == r2 goto pc+2 6
> 
> At insn 3, since r0 is not a constant, verifier assumes both branch
> can be taken which may lead inproper verification failure.
> 
> Add comparing umin value and the constant. If the umin value
> is greater than the constant, for JEQ the branch must be
> not-taken, and for JNE the branch must be taken.
> The jmp32 mode JEQ/JNE branch taken checking is also
> handled similarly.
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  kernel/bpf/verifier.c | 8 ++++++++
>  1 file changed, 8 insertions(+)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 20eb2015842f..90bb6d25bc9c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -12597,10 +12597,14 @@ static int is_branch32_taken(struct bpf_reg_state *reg, u32 val, u8 opcode)
>  	case BPF_JEQ:
>  		if (tnum_is_const(subreg))
>  			return !!tnum_equals_const(subreg, val);
> +		else if (reg->u32_min_value > val)
> +			return 0;
>  		break;

The explanation makes sense to me, and I see similar min_value logic elsewhere
in the switch for other jmp types. But those other jmp types are bounding the
value from one side. Since JEQ and JNE test equality, can't we also add logic
for u32_max_value here? e.g.

        case BPF_JEQ:
                if (tnum_is_const(subreg))
                        return !!tnum_equals_const(subreg, val);
                else if (reg->u32_min_value > val || reg->u32_max_value < val)
                        return 0;
                break;

Similar comment for rest of additions.

>  	case BPF_JNE:
>  		if (tnum_is_const(subreg))
>  			return !tnum_equals_const(subreg, val);
> +		else if (reg->u32_min_value > val)
> +			return 1;
>  		break;
>  	case BPF_JSET:
>  		if ((~subreg.mask & subreg.value) & val)
> @@ -12670,10 +12674,14 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>  	case BPF_JEQ:
>  		if (tnum_is_const(reg->var_off))
>  			return !!tnum_equals_const(reg->var_off, val);
> +		else if (reg->umin_value > val)
> +			return 0;
>  		break;
>  	case BPF_JNE:
>  		if (tnum_is_const(reg->var_off))
>  			return !tnum_equals_const(reg->var_off, val);
> +		else if (reg->umin_value > val)
> +			return 1;
>  		break;
>  	case BPF_JSET:
>  		if ((~reg->var_off.mask & reg->var_off.value) & val)