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@xxxxxxxxx>
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:
signature.asc
Description: PGP signature
