On Tue, Apr 21, 2020 at 02:58:22PM +0200, Daniel Borkmann wrote:
> [ no upstream commit ]
>
> See the glory details in 100605035e15 ("bpf: Verifier, do_refine_retval_range
> may clamp umin to 0 incorrectly") for why 849fa50662fb ("bpf/verifier: refine
> retval R0 state for bpf_get_stack helper") is buggy. The whole series however
> is not suitable for stable since it adds significant amount [0] of verifier
> complexity in order to add 32bit subreg tracking. Something simpler is needed.
>
> Unfortunately, reverting 849fa50662fb ("bpf/verifier: refine retval R0 state
> for bpf_get_stack helper") or just cherry-picking 100605035e15 ("bpf: Verifier,
> do_refine_retval_range may clamp umin to 0 incorrectly") is not an option since
> it will break existing tracing programs badly (at least those that are using
> bpf_get_stack() and bpf_probe_read_str() helpers). Not fixing it in stable is
> also not an option since on 4.19 kernels an error will cause a soft-lockup due
> to hitting dead-code sanitized branch since we don't hard-wire such branches
> in old kernels yet. But even then for 5.x 849fa50662fb ("bpf/verifier: refine
> retval R0 state for bpf_get_stack helper") would cause wrong bounds on the
> verifier simluation when an error is hit.
>
> In one of the earlier iterations of mentioned patch series for upstream there
> was the concern that just using smax_value in do_refine_retval_range() would
> nuke bounds by subsequent <<32 >>32 shifts before the comparison against 0 [1]
> which eventually led to the 32bit subreg tracking in the first place. While I
> initially went for implementing the idea [1] to pattern match the two shift
> operations, it turned out to be more complex than actually needed, meaning, we
> could simply treat do_refine_retval_range() similarly to how we branch off
> verification for conditionals or under speculation, that is, pushing a new
> reg state to the stack for later verification. This means, instead of verifying
> the current path with the ret_reg in [S32MIN, msize_max_value] interval where
> later bounds would get nuked, we split this into two: i) for the success case
> where ret_reg can be in [0, msize_max_value], and ii) for the error case with
> ret_reg known to be in interval [S32MIN, -1]. Latter will preserve the bounds
> during these shift patterns and can match reg < 0 test. test_progs also succeed
> with this approach.
>
> [0] https://lore.kernel.org/bpf/158507130343.15666.8018068546764556975.stgit@john-Precision-5820-Tower/
> [1] https://lore.kernel.org/bpf/158015334199.28573.4940395881683556537.stgit@john-XPS-13-9370/T/#m2e0ad1d5949131014748b6daa48a3495e7f0456d
>
> Fixes: 849fa50662fb ("bpf/verifier: refine retval R0 state for bpf_get_stack helper")
> Reported-by: Lorenzo Fontana <fontanalorenz@xxxxxxxxx>
> Reported-by: Leonardo Di Donato <leodidonato@xxxxxxxxx>
> Reported-by: John Fastabend <john.fastabend@xxxxxxxxx>
> Signed-off-by: Daniel Borkmann <daniel@xxxxxxxxxxxxx>
> Acked-by: Alexei Starovoitov <ast@xxxxxxxxxx>
> Acked-by: John Fastabend <john.fastabend@xxxxxxxxx>
> Tested-by: John Fastabend <john.fastabend@xxxxxxxxx>
> ---
> [ Lorenzo, Leonardo, I did check my local checkout of driver/bpf/probe.o,
> but please make sure to double check 4.19 with this patch here also from
> your side, so we can add a Tested-by from one of you before Greg takes
> it into stable. Thanks guys! ]
>
> kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++-----------
> 1 file changed, 34 insertions(+), 11 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index e85636fb81b9..daf0a9637d73 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -188,8 +188,7 @@ struct bpf_call_arg_meta {
> bool pkt_access;
> int regno;
> int access_size;
> - s64 msize_smax_value;
> - u64 msize_umax_value;
> + u64 msize_max_value;
> };
>
> static DEFINE_MUTEX(bpf_verifier_lock);
> @@ -2076,8 +2075,7 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
> /* remember the mem_size which may be used later
> * to refine return values.
> */
> - meta->msize_smax_value = reg->smax_value;
> - meta->msize_umax_value = reg->umax_value;
> + meta->msize_max_value = reg->umax_value;
>
> /* The register is SCALAR_VALUE; the access check
> * happens using its boundaries.
> @@ -2448,21 +2446,44 @@ 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_call_arg_meta *meta)
> +static int do_refine_retval_range(struct bpf_verifier_env *env,
> + struct bpf_reg_state *regs, int ret_type,
> + int func_id, struct bpf_call_arg_meta *meta)
> {
> struct bpf_reg_state *ret_reg = ®s[BPF_REG_0];
> + struct bpf_reg_state tmp_reg = *ret_reg;
> + bool ret;
>
> if (ret_type != RET_INTEGER ||
> (func_id != BPF_FUNC_get_stack &&
> func_id != BPF_FUNC_probe_read_str))
> - return;
> + return 0;
> +
> + /* Error case where ret is in interval [S32MIN, -1]. */
> + ret_reg->smin_value = S32_MIN;
> + ret_reg->smax_value = -1;
> +
> + __reg_deduce_bounds(ret_reg);
> + __reg_bound_offset(ret_reg);
> + __update_reg_bounds(ret_reg);
> +
> + ret = push_stack(env, env->insn_idx + 1, env->insn_idx, false);
> + if (!ret)
> + return -EFAULT;
> +
> + *ret_reg = tmp_reg;
> +
> + /* Success case where ret is in range [0, msize_max_value]. */
> + ret_reg->smin_value = 0;
> + ret_reg->smax_value = meta->msize_max_value;
> + ret_reg->umin_value = ret_reg->smin_value;
> + ret_reg->umax_value = ret_reg->smax_value;
>
> - ret_reg->smax_value = meta->msize_smax_value;
> - ret_reg->umax_value = meta->msize_umax_value;
> __reg_deduce_bounds(ret_reg);
> __reg_bound_offset(ret_reg);
> + __update_reg_bounds(ret_reg);
> +
> + return 0;
> }
>
> static int
> @@ -2617,7 +2638,9 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
> return -EINVAL;
> }
>
> - do_refine_retval_range(regs, fn->ret_type, func_id, &meta);
> + err = do_refine_retval_range(env, regs, fn->ret_type, func_id, &meta);
> + if (err)
> + return err;
>
> err = check_map_func_compatibility(env, meta.map_ptr, func_id);
> if (err)
> --
> 2.20.1
>
Hi Daniel,
Leonardo and I applied this on top of 8e2406c85187 and our old probe works as
expected, as well as the new one.
We produced a dot graph [0] of the in memory xlated representation [1], it clearly
shows that this patch solves the bug. A rendered [2] version is
available for the lazy.
So, Daniel please add a Tested-by for each one of us.
Thanks Daniel!
Lorenzo and Leonardo
[0] https://fs.fntlnz.wtf/kernel/bpf-retval-refinement-4-19/prog.dot
[1] https://fs.fntlnz.wtf/kernel/bpf-retval-refinement-4-19/xlated.txt
[2] https://fs.fntlnz.wtf/kernel/bpf-retval-refinement-4-19/render.png
