Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check

[Yonghong Song <yonghong.song@linux.dev>]

On 4/19/24 2:47 AM, Cupertino Miranda wrote:
> Eduard Zingerman writes:
>
>> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>>
>> [...]
>>
>>>   static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>> +					    struct bpf_reg_state dst_reg,
>>>   					    struct bpf_reg_state src_reg)
>> Nit: there is no need to pass {dst,src}_reg by value,
>>       struct bpf_reg_state is 120 bytes in size
>>      (but maybe compiler handles this).
>>
>>>   {
>>> -	bool src_known;
>>> +	bool src_known, dst_known;
>>>   	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>>>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>>   	u8 opcode = BPF_OP(insn->code);
>>>
>>> -	bool valid_known = true;
>>> -	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
>>> +	bool valid_known_src = true;
>>> +	bool valid_known_dst = true;
>>> +	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>>> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>>
>>>   	/* Taint dst register if offset had invalid bounds
>>>   	 * derived from e.g. dead branches.
>>>   	 */
>>> -	if (valid_known == false)
>>> +	if (valid_known_src == false)
>>>   		return UNCOMPUTABLE_RANGE;
>>>
>>>   	switch (opcode) {
>>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>   	case BPF_OR:
>>>   		return COMPUTABLE_RANGE;
>>>
>>> -	/* Compute range for the following only if the src_reg is known.
>>> +	/* Compute range for MUL if at least one of its registers is known.
>>>   	 */
>>>   	case BPF_MUL:
>>> -		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>>> +		if (src_known || (dst_known && valid_known_dst))
>>> +			return COMPUTABLE_RANGE;
>>> +		break;
>> Is it even necessary to restrict src or dst to be known?
>> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>>
>> 	case BPF_MUL:
>> 		dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
>> 		scalar32_min_max_mul(dst_reg, &src_reg);
>> 		scalar_min_max_mul(dst_reg, &src_reg);
>> 		break;
>>
>> Where tnum_mul() refers to a paper, and that paper does not restrict
>> abstract multiplication algorithm to constant values on either side.
>> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
>> - if both src and dst are positive
>> - if overflow is not possible
>> - adjust dst->min *= src->min
>> - adjust dst->max *= src->max
>>
>> I think this should work just fine if neither of src or dst is a known constant.
>> What do you think?
>>
> With the refactor this looked like an armless change. Indeed if we agree
> that the algorithm covers all scenarios, then why not.
> I did not study the paper or the scalar_min_max_mul function nearly
> enough to know for sure.

I double checked and I think Eduard is correct. src_known checking
is not necessary for multiplication. It would be great if you can
add this change as well in the patch set.

>> [...]