Re: [RFC PATCH v1 01/14] bpf: Mark subprogs as throw reachable before do_check pass

[David Vernet <void@manifault.com>]

[-- Attachment #1: Type: text/plain, Size: 8424 bytes --]

On Thu, Feb 01, 2024 at 04:20:56AM +0000, Kumar Kartikeya Dwivedi wrote:
> The motivation of this patch is to figure out which subprogs participate
> in exception propagation. In other words, whichever subprog's execution
> can lead to an exception being thrown either directly or indirectly (by
> way of calling other subprogs).
> 
> With the current exceptions support, the runtime performs stack
> unwinding when bpf_throw is called. For now, any resources acquired by
> the program cannot be released, therefore bpf_throw calls made with
> non-zero acquired references must be rejected during verification.
> 
> However, there currently exists a loophole in this restriction due to
> the way the verification procedure is structured. The verifier will
> first walk over the main subprog's instructions, but not descend into
> subprog calls to ones with global linkage. These global subprogs will
> then be independently verified instead. Therefore, in a situation where
> a global subprog ends up throwing an exception (either directly by
> calling bpf_throw, or indirectly by way of calling another subprog that
> does so), the verifier will fail to notice this fact and may permit
> throwing BPF exceptions with non-zero acquired references.
> 
> Therefore, to fix this, we add a summarization pass before the do_check
> stage which walks all call chains of the program and marks all of the
> subprogs that are reachable from a bpf_throw call which unwinds the
> program stack.
> 
> We only do so if we actually see a bpf_throw call in the program though,
> since we do not want to walk all instructions unless we need to.  One we

s/Once/once

> analyze all possible call chains of the program, we will be able to mark
> them as 'is_throw_reachable' in their subprog_info.
> 
> After performing this step, we need to make another change as to how
> subprog call verification occurs. In case of global subprog, we will
> need to explore an alternate program path where the call instruction
> processing of a global subprog's call will immediately throw an
> exception. We will thus simulate a normal path without any exceptions,
> and one where the exception is thrown and the program proceeds no
> further. In this way, the verifier will be able to detect the whether
> any acquired references or locks exist in the verifier state and thus
> reject the program if needed.
> 
> Fixes: f18b03fabaa9 ("bpf: Implement BPF exceptions")
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Just had a few nits and one question. Looks reasonable to me overall.

> ---
>  include/linux/bpf_verifier.h |  2 +
>  kernel/bpf/verifier.c        | 86 ++++++++++++++++++++++++++++++++++++
>  2 files changed, 88 insertions(+)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0dcde339dc7e..1d666b6c21e6 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -626,6 +626,7 @@ struct bpf_subprog_info {
>  	bool is_async_cb: 1;
>  	bool is_exception_cb: 1;
>  	bool args_cached: 1;
> +	bool is_throw_reachable: 1;
>  
>  	u8 arg_cnt;
>  	struct bpf_subprog_arg_info args[MAX_BPF_FUNC_REG_ARGS];
> @@ -691,6 +692,7 @@ struct bpf_verifier_env {
>  	bool bypass_spec_v4;
>  	bool seen_direct_write;
>  	bool seen_exception;
> +	bool seen_throw_insn;
>  	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
>  	const struct bpf_line_info *prev_linfo;
>  	struct bpf_verifier_log log;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index cd4d780e5400..bba53c4e3a0c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2941,6 +2941,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
>  		    insn[i].src_reg == 0 &&
>  		    insn[i].imm == BPF_FUNC_tail_call)
>  			subprog[cur_subprog].has_tail_call = true;
> +		if (!env->seen_throw_insn && is_bpf_throw_kfunc(&insn[i]))
> +			env->seen_throw_insn = true;
>  		if (BPF_CLASS(code) == BPF_LD &&
>  		    (BPF_MODE(code) == BPF_ABS || BPF_MODE(code) == BPF_IND))
>  			subprog[cur_subprog].has_ld_abs = true;
> @@ -5866,6 +5868,9 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx)
>  
>  			if (!is_bpf_throw_kfunc(insn + i))
>  				continue;
> +			/* When this is allowed, don't forget to update logic for sync and
> +			 * async callbacks in mark_exception_reachable_subprogs.
> +			 */
>  			if (subprog[idx].is_cb)
>  				err = true;
>  			for (int c = 0; c < frame && !err; c++) {
> @@ -16205,6 +16210,83 @@ static int check_btf_info(struct bpf_verifier_env *env,
>  	return 0;
>  }
>  
> +/* We walk the call graph of the program in this function, and mark everything in
> + * the call chain as 'is_throw_reachable'. This allows us to know which subprog
> + * calls may propagate an exception and generate exception frame descriptors for
> + * those call instructions. We already do that for bpf_throw calls made directly,
> + * but we need to mark the subprogs as we won't be able to see the call chains
> + * during symbolic execution in do_check_common due to global subprogs.
> + *
> + * Note that unlike check_max_stack_depth, we don't explore the async callbacks
> + * apart from main subprogs, as we don't support throwing from them for now, but

Comment ending prematurely

> + */
> +static int mark_exception_reachable_subprogs(struct bpf_verifier_env *env)
> +{
> +	struct bpf_subprog_info *subprog = env->subprog_info;
> +	struct bpf_insn *insn = env->prog->insnsi;
> +	int idx = 0, frame = 0, i, subprog_end;
> +	int ret_insn[MAX_CALL_FRAMES];
> +	int ret_prog[MAX_CALL_FRAMES];
> +
> +	/* No need if we never saw any bpf_throw() call in the program. */
> +	if (!env->seen_throw_insn)
> +		return 0;
> +
> +	i = subprog[idx].start;
> +restart:
> +	subprog_end = subprog[idx + 1].start;
> +	for (; i < subprog_end; i++) {
> +		int next_insn, sidx;
> +
> +		if (bpf_pseudo_kfunc_call(insn + i) && !insn[i].off) {

When should a kfunc call ever have a nonzero offset? We use the
immediate for the BTF ID, don't we?

> +			if (!is_bpf_throw_kfunc(insn + i))
> +				continue;
> +			subprog[idx].is_throw_reachable = true;
> +			for (int j = 0; j < frame; j++)
> +				subprog[ret_prog[j]].is_throw_reachable = true;
> +		}
> +
> +		if (!bpf_pseudo_call(insn + i) && !bpf_pseudo_func(insn + i))
> +			continue;
> +		/* remember insn and function to return to */
> +		ret_insn[frame] = i + 1;
> +		ret_prog[frame] = idx;
> +
> +		/* find the callee */
> +		next_insn = i + insn[i].imm + 1;
> +		sidx = find_subprog(env, next_insn);
> +		if (sidx < 0) {
> +			WARN_ONCE(1, "verifier bug. No program starts at insn %d\n", next_insn);
> +			return -EFAULT;
> +		}
> +		/* We cannot distinguish between sync or async cb, so we need to follow
> +		 * both.  Async callbacks don't really propagate exceptions but calling
> +		 * bpf_throw from them is not allowed anyway, so there is no harm in
> +		 * exploring them.
> +		 * TODO: To address this properly, we will have to move is_cb,
> +		 * is_async_cb markings to the stage before do_check.
> +		 */
> +		i = next_insn;
> +		idx = sidx;
> +
> +		frame++;
> +		if (frame >= MAX_CALL_FRAMES) {
> +			verbose(env, "the call stack of %d frames is too deep !\n", frame);
> +			return -E2BIG;
> +		}
> +		goto restart;
> +	}
> +	/* end of for() loop means the last insn of the 'subprog'
> +	 * was reached. Doesn't matter whether it was JA or EXIT
> +	 */
> +	if (frame == 0)
> +		return 0;
> +	frame--;
> +	i = ret_insn[frame];
> +	idx = ret_prog[frame];
> +	goto restart;
> +}

If you squint youre eyes there's a non-trivial amount of duplicated
intent / logic here compared to check_max_stack_depth_subprog(). Do you
think it would be possible to combine them somehow?

> +
>  /* check %cur's range satisfies %old's */
>  static bool range_within(struct bpf_reg_state *old,
>  			 struct bpf_reg_state *cur)
> @@ -20939,6 +21021,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
>  	if (ret < 0)
>  		goto skip_full_check;
>  
> +	ret = mark_exception_reachable_subprogs(env);
> +	if (ret < 0)
> +		goto skip_full_check;
> +
>  	ret = do_check_main(env);
>  	ret = ret ?: do_check_subprogs(env);
>  
> -- 
> 2.40.1
> 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]