From mboxrd@z Thu Jan 1 00:00:00 1970 From: Yonghong Song Subject: Re: [PATCH bpf-next v2 3/9] bpf/verifier: refine retval R0 state for bpf_get_stack helper Date: Thu, 19 Apr 2018 16:37:52 -0700 Message-ID: <349e3459-d54a-cb05-7c27-1e0cd613dc6f@fb.com> References: <20180418165444.2263237-1-yhs@fb.com> <20180418165444.2263237-4-yhs@fb.com> <20180419043322.zmwxapw3vcimlgg6@ast-mbp> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit Cc: , , , To: Alexei Starovoitov Return-path: Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:46964 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753581AbeDSXiZ (ORCPT ); Thu, 19 Apr 2018 19:38:25 -0400 In-Reply-To: <20180419043322.zmwxapw3vcimlgg6@ast-mbp> Content-Language: en-US Sender: netdev-owner@vger.kernel.org List-ID: On 4/18/18 9:33 PM, Alexei Starovoitov wrote: > On Wed, Apr 18, 2018 at 09:54:38AM -0700, Yonghong Song wrote: >> The special property of return values for helpers bpf_get_stack >> and bpf_probe_read_str are captured in verifier. >> Both helpers return a negative error code or >> a length, which is equal to or smaller than the buffer >> size argument. This additional information in the >> verifier can avoid the condition such as "retval > bufsize" >> in the bpf program. For example, for the code blow, >> usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK); >> if (usize < 0 || usize > max_len) >> return 0; >> The verifier may have the following errors: >> 52: (85) call bpf_get_stack#65 >> R0=map_value(id=0,off=0,ks=4,vs=1600,imm=0) R1_w=ctx(id=0,off=0,imm=0) >> R2_w=map_value(id=0,off=0,ks=4,vs=1600,imm=0) R3_w=inv800 R4_w=inv256 >> R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0) >> R9_w=inv800 R10=fp0,call_-1 >> 53: (bf) r8 = r0 >> 54: (bf) r1 = r8 >> 55: (67) r1 <<= 32 >> 56: (bf) r2 = r1 >> 57: (77) r2 >>= 32 >> 58: (25) if r2 > 0x31f goto pc+33 >> R0=inv(id=0) R1=inv(id=0,smax_value=9223372032559808512, >> umax_value=18446744069414584320, >> var_off=(0x0; 0xffffffff00000000)) >> R2=inv(id=0,umax_value=799,var_off=(0x0; 0x3ff)) >> R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0) >> R8=inv(id=0) R9=inv800 R10=fp0,call_-1 >> 59: (1f) r9 -= r8 >> 60: (c7) r1 s>>= 32 >> 61: (bf) r2 = r7 >> 62: (0f) r2 += r1 >> math between map_value pointer and register with unbounded >> min value is not allowed >> The failure is due to llvm compiler optimization where register "r2", >> which is a copy of "r1", is tested for condition while later on "r1" >> is used for map_ptr operation. The verifier is not able to track such >> inst sequence effectively. >> >> Without the "usize > max_len" condition, there is no llvm optimization >> and the below generated code passed verifier: >> 52: (85) call bpf_get_stack#65 >> R0=map_value(id=0,off=0,ks=4,vs=1600,imm=0) R1_w=ctx(id=0,off=0,imm=0) >> R2_w=map_value(id=0,off=0,ks=4,vs=1600,imm=0) R3_w=inv800 R4_w=inv256 >> R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0) >> R9_w=inv800 R10=fp0,call_-1 >> 53: (b7) r1 = 0 >> 54: (bf) r8 = r0 >> 55: (67) r8 <<= 32 >> 56: (c7) r8 s>>= 32 >> 57: (6d) if r1 s> r8 goto pc+24 >> R0=inv(id=0,umax_value=800) R1=inv0 R6=ctx(id=0,off=0,imm=0) >> R7=map_value(id=0,off=0,ks=4,vs=1600,imm=0) >> R8=inv(id=0,umax_value=800,var_off=(0x0; 0x3ff)) R9=inv800 >> R10=fp0,call_-1 >> 58: (bf) r2 = r7 >> 59: (0f) r2 += r8 >> 60: (1f) r9 -= r8 >> 61: (bf) r1 = r6 >> >> Signed-off-by: Yonghong Song >> --- >> kernel/bpf/verifier.c | 31 ++++++++++++++++++++++++++++++- >> 1 file changed, 30 insertions(+), 1 deletion(-) >> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >> index aba9425..a8302c3 100644 >> --- a/kernel/bpf/verifier.c >> +++ b/kernel/bpf/verifier.c >> @@ -2333,10 +2333,32 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) >> return 0; >> } >> >> +static void do_refine_retval_range(struct bpf_reg_state *regs, int ret_type, >> + int func_id, >> + struct bpf_reg_state *retval_state, >> + bool is_check) >> +{ >> + struct bpf_reg_state *src_reg, *dst_reg; >> + >> + if (ret_type != RET_INTEGER || >> + (func_id != BPF_FUNC_get_stack && >> + func_id != BPF_FUNC_probe_read_str)) >> + return; >> + >> + dst_reg = is_check ? retval_state : ®s[BPF_REG_0]; >> + if (func_id == BPF_FUNC_get_stack) >> + src_reg = is_check ? ®s[BPF_REG_3] : retval_state; >> + else >> + src_reg = is_check ? ®s[BPF_REG_2] : retval_state; >> + >> + dst_reg->smax_value = src_reg->smax_value; >> + dst_reg->umax_value = src_reg->umax_value; >> +} > > I think this part can be made more generic, by using 'meta' logic. > check_func_arg(.. &meta); > can remember smax/umax into meta for arg_type_is_mem_size() > and later refine_retval_range() can be applied to r0. > This will help avoid mistakes with specifying reg by position (r2 or r3) > like above snippet is doing. Good suggestion. Let me try this. > >> + >> static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn_idx) >> { >> const struct bpf_func_proto *fn = NULL; >> - struct bpf_reg_state *regs; >> + struct bpf_reg_state *regs, retval_state; >> struct bpf_call_arg_meta meta; >> bool changes_data; >> int i, err; >> @@ -2415,6 +2437,10 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn >> } >> >> regs = cur_regs(env); >> + >> + /* before reset caller saved regs, check special ret value */ >> + do_refine_retval_range(regs, fn->ret_type, func_id, &retval_state, 1); >> + >> /* reset caller saved regs */ >> for (i = 0; i < CALLER_SAVED_REGS; i++) { >> mark_reg_not_init(env, regs, caller_saved[i]); >> @@ -2456,6 +2482,9 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn >> return -EINVAL; >> } >> >> + /* apply additional constraints to ret value */ >> + do_refine_retval_range(regs, fn->ret_type, func_id, &retval_state, 0); >> + >> err = check_map_func_compatibility(env, meta.map_ptr, func_id); >> if (err) >> return err; >> -- >> 2.9.5 >>