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

[Yonghong Song <yhs@meta.com>]

On 3/30/23 2:14 PM, Dave Marchevsky wrote:
> 
> 
> 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.
> 

Sounds good. I agree reg->u32_max_value < val should ensure the branch
not taken too. Will accommodate this change in the next revision.

>>   	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)