From mboxrd@z Thu Jan 1 00:00:00 1970 From: Yonghong Song Subject: Re: [PATCH bpf-next v3 4/9] bpf/verifier: improve register value range tracking with ARSH Date: Mon, 23 Apr 2018 09:19:53 -0700 Message-ID: References: <20180420221842.742330-1-yhs@fb.com> <20180420221842.742330-5-yhs@fb.com> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 8bit Cc: To: Edward Cree , , , Return-path: Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:51522 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1755831AbeDWQUV (ORCPT ); Mon, 23 Apr 2018 12:20:21 -0400 In-Reply-To: Content-Language: en-US Sender: netdev-owner@vger.kernel.org List-ID: 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;