Re: [PATCH bpf-next v3 4/9] bpf/verifier: improve register value range tracking with ARSH

[Yonghong Song <yhs@fb.com>]

On 4/23/18 5:25 AM, Edward Cree wrote:
> On 20/04/18 23:18, Yonghong Song wrote:
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 3c8bb92..01c215d 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2975,6 +2975,32 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>   		/* We may learn something more from the var_off */
>>   		__update_reg_bounds(dst_reg);
>>   		break;
>> +	case BPF_ARSH:
>> +		if (umax_val >= insn_bitness) {
>> +			/* Shifts greater than 31 or 63 are undefined.
>> +			 * This includes shifts by a negative number.
>> +			 */
>> +			mark_reg_unknown(env, regs, insn->dst_reg);
>> +			break;
>> +		}
>> +		if (dst_reg->smin_value < 0)
>> +			dst_reg->smin_value >>= umin_val;
>> +		else
>> +			dst_reg->smin_value >>= umax_val;
>> +		if (dst_reg->smax_value < 0)
>> +			dst_reg->smax_value >>= umax_val;
>> +		else
>> +			dst_reg->smax_value >>= umin_val;
>> +		if (src_known)
>> +			dst_reg->var_off = tnum_rshift(dst_reg->var_off,
>> +						       umin_val);
> tnum_rshift is an unsigned shift, it won't do what you want here.
> I think you could write a tnum_arshift that looks something like this
>   (UNTESTED!):
> 
>      struct tnum tnum_arshift(struct tnum a, u8 shift)
>      {
>          return TNUM(((s64)a.value) >> shift, ((s64)a.mask) >> shift);
>      }
> Theory: if value sign bit is 1 then number is known negative so populate
>   upper bits with known 1s.  If mask sign bit is 1 then number might be
>   negative so populate upper bits with unknown.  Otherwise, number is
>   known positive so populate upper bits with known 0s.

Right, my last version just used this tnum_arshift :-).


>> +		else
>> +			dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val);
> Applying the above here, tnum_arshift(tnum_unknown, ...) would always just
>   return tnum_unknown, so just do "dst_reg->var_off = tnum_unknown;".
> The reason for the corresponding logic in the BPF_RSH case is that a right
>   logical shift _always_ populates upper bits with zeroes.
> In any case these 'else' branches are currently never taken because they
>   fall foul of the check Alexei added just before the switch,
>      if (!src_known &&
>          opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>          __mark_reg_unknown(dst_reg);
>          return 0;
>      }
> So I can guarantee you haven't tested this code :-)

I just noticed this last night and removed the !src_known branch all 
together here and from LSH/RSH.

> 
>> +		dst_reg->umin_value >>= umax_val;
>> +		dst_reg->umax_value >>= umin_val;
> FWIW I think the way to handle umin/umax here is to blow them away and
>   just rely on inferring new ubounds from the sbounds (i.e. the inverse of
>   what we do just above in case BPF_RSH) since BPF_ARSH is essentially an
>   operation on the signed value.  I don't think there is a need to support
>   cases where the unsigned bounds of a signed shift of a value that may
>   cross the sign boundary at (1<<63) are needed to verify a program.
> (Unlike in the unsigned shift case, it is at least _possible_ for there to
>   be information from the ubounds that we can't get from the sbounds - but
>   it's a contrived case that isn't likely to be useful in real programs.)

This makes sense and will make code simpler and easy to understand.
Will make the change.

Thanks!

> 
> -Ed
>> +		/* We may learn something more from the var_off */
>> +		__update_reg_bounds(dst_reg);
>> +		break;
>>   	default:
>>   		mark_reg_unknown(env, regs, insn->dst_reg);
>>   		break;