diff mbox series

[RFC,v1,02/14] bpf: Process global subprog's exception propagation

Message ID 20240201042109.1150490-3-memxor@gmail.com (mailing list archive)
State RFC
Delegated to: BPF
Headers show
Series Exceptions - Resource Cleanup | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
netdev/tree_selection success Guessing tree name failed - patch did not apply, async
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-9 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-4 fail Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-34 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-8 fail Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for s390x-gcc / test
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-12 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-13 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-17 pending Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-25 pending Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-32 pending Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-33 pending Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-15 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-16 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18

Commit Message

Kumar Kartikeya Dwivedi Feb. 1, 2024, 4:20 a.m. UTC 
Global subprogs are not descended during symbolic execution, but we
summarized whether they can throw an exception (reachable from another
exception throwing subprog) in mark_exception_reachable_subprogs added
by the previous patch.

We must now ensure that we explore the path of the program where
invoking the call instruction leads to an exception being thrown, so
that we can correctly reject programs where it is not permissible to
throw an exception.  For instance, it might be permissible to throw from
a global subprog, but its caller may hold references. Without this
patch, the verifier will accept such programs.

To do this, we use push_stack to push a separate branch into the branch
stack of the verifier, with the same current and previous insn_idx.
Then, we set a bit in the verifier state of the branch to indicate that
the next instruction it will process is of a global subprog call which
will throw an exception. When we encounter this instruction, this bit
will be cleared.

Special care must be taken to update the state pruning logic, as without
any changes, it is possible that we end up pruning when popping the
exception throwing state for exploration. Therefore, while we can never
have the 'global_subprog_call_exception' bit set in the verifier state
of an explored state, we will see it in the current state, and use this
to reject pruning requests and continue its exploration.

Note that we process the exception after processing the call
instruction, similar to how we do a process_bpf_exit_full jump in case
of bpf_throw kfuncs.

Fixes: f18b03fabaa9 ("bpf: Implement BPF exceptions")
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 22 ++++++++++++++++++++++
 2 files changed, 23 insertions(+)

Comments

Eduard Zingerman Feb. 15, 2024, 1:10 a.m. UTC | #1 
On Thu, 2024-02-01 at 04:20 +0000, Kumar Kartikeya Dwivedi wrote:
> Global subprogs are not descended during symbolic execution, but we
> summarized whether they can throw an exception (reachable from another
> exception throwing subprog) in mark_exception_reachable_subprogs added
> by the previous patch.

[...]

> Fixes: f18b03fabaa9 ("bpf: Implement BPF exceptions")
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

Also, did you consider global subprograms that always throw?
E.g. do some logging and unconditionally call bpf_throw().

[...]

> @@ -9505,6 +9515,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
>  		mark_reg_unknown(env, caller->regs, BPF_REG_0);
>  		caller->regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
>  
> +		if (env->cur_state->global_subprog_call_exception)
> +			verbose(env, "Func#%d ('%s') may throw exception, exploring program path where exception is thrown\n",
> +				subprog, sub_name);

Nit: Maybe move this log entry to do_check?
     It would be printed right before returning to do_check() anyways.
     Maybe add a log level check?

>  		/* continue with next insn after call */
>  		return 0;
>  	}

[...]

> @@ -17675,6 +17692,11 @@ static int do_check(struct bpf_verifier_env *env)
>  				}
>  				if (insn->src_reg == BPF_PSEUDO_CALL) {
>  					err = check_func_call(env, insn, &env->insn_idx);
> +					if (!err && env->cur_state->global_subprog_call_exception) {
> +						env->cur_state->global_subprog_call_exception = false;
> +						exception_exit = true;
> +						goto process_bpf_exit_full;
> +					}
>  				} else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
>  					err = check_kfunc_call(env, insn, &env->insn_idx);
>  					if (!err && is_bpf_throw_kfunc(insn)) {
Kumar Kartikeya Dwivedi Feb. 16, 2024, 9:50 p.m. UTC | #2 
On Thu, 15 Feb 2024 at 02:10, Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2024-02-01 at 04:20 +0000, Kumar Kartikeya Dwivedi wrote:
> > Global subprogs are not descended during symbolic execution, but we
> > summarized whether they can throw an exception (reachable from another
> > exception throwing subprog) in mark_exception_reachable_subprogs added
> > by the previous patch.
>
> [...]
>
> > Fixes: f18b03fabaa9 ("bpf: Implement BPF exceptions")
> > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> > ---
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
>
> Also, did you consider global subprograms that always throw?
> E.g. do some logging and unconditionally call bpf_throw().
>

I have an example for that in the exception test suite, but I will add
a test for that with lingering references around.

> [...]
>
> > @@ -9505,6 +9515,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> >               mark_reg_unknown(env, caller->regs, BPF_REG_0);
> >               caller->regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
> >
> > +             if (env->cur_state->global_subprog_call_exception)
> > +                     verbose(env, "Func#%d ('%s') may throw exception, exploring program path where exception is thrown\n",
> > +                             subprog, sub_name);
>
> Nit: Maybe move this log entry to do_check?
>      It would be printed right before returning to do_check() anyways.
>      Maybe add a log level check?
>

Hmm, true. I was actually even considering whether all frame_desc logs
should also be LOG_LEVEL2?

> >               /* continue with next insn after call */
> >               return 0;
> >       }
>
> [...]
Eduard Zingerman Feb. 17, 2024, 2:04 p.m. UTC | #3 
On Fri, 2024-02-16 at 22:50 +0100, Kumar Kartikeya Dwivedi wrote:
[...]

> > Also, did you consider global subprograms that always throw?
> > E.g. do some logging and unconditionally call bpf_throw().
> > 
> 
> I have an example for that in the exception test suite, but I will add
> a test for that with lingering references around.

I meant that for some global subprograms it is not necessary to
explore both throwing and non-throwing branches, e.g.:

  void my_throw(void) {
    bpf_printk("oh no, oh no, oh no-no-no-...");
    bpf_throw(0);
  }

  SEC("tp")
  int foo(...) {
    ...
    if (a > 10)
      my_throw();
    ... here 'a' is always <= 10 ...
  }

[...]

> > Nit: Maybe move this log entry to do_check?
> >      It would be printed right before returning to do_check() anyways.
> >      Maybe add a log level check?
> > 
> 
> Hmm, true. I was actually even considering whether all frame_desc logs
> should also be LOG_LEVEL2?

Right, makes sense.
diff mbox series

Patch

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 1d666b6c21e6..5482701e6ad9 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -426,6 +426,7 @@  struct bpf_verifier_state {
 	 * while they are still in use.
 	 */
 	bool used_as_loop_entry;
+	bool global_subprog_call_exception;
 
 	/* first and last insn idx of this verifier state */
 	u32 first_insn_idx;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index bba53c4e3a0c..622c638b123b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1418,6 +1418,7 @@  static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 	dst_state->dfs_depth = src->dfs_depth;
 	dst_state->callback_unroll_depth = src->callback_unroll_depth;
 	dst_state->used_as_loop_entry = src->used_as_loop_entry;
+	dst_state->global_subprog_call_exception = src->global_subprog_call_exception;
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
 		if (!dst) {
@@ -9497,6 +9498,15 @@  static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 
 		verbose(env, "Func#%d ('%s') is global and assumed valid.\n",
 			subprog, sub_name);
+		if (subprog_info(env, subprog)->is_throw_reachable && !env->cur_state->global_subprog_call_exception) {
+			struct bpf_verifier_state *branch = push_stack(env, env->insn_idx, env->prev_insn_idx, false);
+
+			if (!branch) {
+				verbose(env, "verifier internal error: cannot push branch to explore exception of global subprog\n");
+				return -EFAULT;
+			}
+			branch->global_subprog_call_exception = true;
+		}
 		/* mark global subprog for verifying after main prog */
 		subprog_aux(env, subprog)->called = true;
 		clear_caller_saved_regs(env, caller->regs);
@@ -9505,6 +9515,9 @@  static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		mark_reg_unknown(env, caller->regs, BPF_REG_0);
 		caller->regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
 
+		if (env->cur_state->global_subprog_call_exception)
+			verbose(env, "Func#%d ('%s') may throw exception, exploring program path where exception is thrown\n",
+				subprog, sub_name);
 		/* continue with next insn after call */
 		return 0;
 	}
@@ -16784,6 +16797,10 @@  static bool states_equal(struct bpf_verifier_env *env,
 	if (old->active_rcu_lock != cur->active_rcu_lock)
 		return false;
 
+	/* Prevent pruning to explore state where global subprog call throws an exception. */
+	if (cur->global_subprog_call_exception)
+		return false;
+
 	/* for states to be equal callsites have to be the same
 	 * and all frame states need to be equivalent
 	 */
@@ -17675,6 +17692,11 @@  static int do_check(struct bpf_verifier_env *env)
 				}
 				if (insn->src_reg == BPF_PSEUDO_CALL) {
 					err = check_func_call(env, insn, &env->insn_idx);
+					if (!err && env->cur_state->global_subprog_call_exception) {
+						env->cur_state->global_subprog_call_exception = false;
+						exception_exit = true;
+						goto process_bpf_exit_full;
+					}
 				} else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
 					err = check_kfunc_call(env, insn, &env->insn_idx);
 					if (!err && is_bpf_throw_kfunc(insn)) {