[PATCH bpf 1/2] bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks

[PATCH bpf 1/2] bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks

[Eduard Zingerman]

When processing calls to bpf_loop() verifier marks R1 (and R4) as
precise. R1 tracks loop iterations number and because of the
'callback_depth < R1' mechanics in check_helper_call() must be marked
precise. However, precision propagation for R1 was broken,
when bpf_loop() call was verified on a second iteration.

Consider the following verification trace:
- main: bpf_loop(nr_loops, callback ...)
- callback: BPF_EXIT
- main: bpf_loop(nr_loops, callback ...)
- ...

While the first visit of the call to bpf_loop() propagated R1
precision as expected, the second call to mark_chain_precision() in
the check_helper_call() set R1, but it was immediately reset when
backtrack_insn() processed preceding BPF_EXIT in the loop deleted in
this patch.

Because of that, the second visit of the call to bpf_loop() injected
checkpoint with R1 not marked as precise. Which could trick the
verifier into accepting unsafe programs. See the next patch for an
example of such program.

Commit is structured in a way to minimize conflicts when
'bpf' would be eventually merged with 'bpf-next'.

Fixes: ab5cfac139ab ("bpf: verify callbacks as if they are called unknown number of times")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/backtrack.c | 37 +++++++++++++++++--------------------
 1 file changed, 17 insertions(+), 20 deletions(-)

diff --git a/kernel/bpf/backtrack.c b/kernel/bpf/backtrack.c
index a2b18a9f1694..4fe906510673 100644
--- a/kernel/bpf/backtrack.c
+++ b/kernel/bpf/backtrack.c
@@ -520,37 +520,34 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
 					return -EFAULT;
 			}
 		} else if (opcode == BPF_EXIT) {
-			bool r0_precise;
+			bool from_subprog_call, r0_precise;
+
+			/* BPF_EXIT in subprog or callback always returns
+			 * right after the call instruction, so by checking
+			 * whether the instruction at subseq_idx-1 is subprog
+			 * call or not we can distinguish actual exit from
+			 * *subprog* from exit from *callback*. In the former
+			 * case, we need to propagate r0 precision, if
+			 * necessary. In the former we never do that.
+			 */
+			from_subprog_call = subseq_idx - 1 >= 0 &&
+					    bpf_pseudo_call(&env->prog->insnsi[subseq_idx - 1]);
+
+			r0_precise = from_subprog_call && bt_is_reg_set(bt, BPF_REG_0);
 
 			/* Backtracking to a nested function call, 'idx' is a part of
 			 * the inner frame 'subseq_idx' is a part of the outer frame.
 			 * In case of a regular function call, instructions giving
 			 * precision to registers R1-R5 should have been found already.
-			 * In case of a callback, it is ok to have R1-R5 marked for
-			 * backtracking, as these registers are set by the function
-			 * invoking callback.
+			 * In case of a callback from bpf_loop(), R{1,4} in the calling
+			 * frame would be set as precise and that is correct.
 			 */
-			if (subseq_idx >= 0 && bpf_calls_callback(env, subseq_idx))
-				for (i = BPF_REG_1; i <= BPF_REG_5; i++)
-					bt_clear_reg(bt, i);
-			if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) {
+			if (from_subprog_call && (bt_reg_mask(bt) & BPF_REGMASK_ARGS)) {
 				verifier_bug(env, "backtracking exit unexpected regs %x",
 					     bt_reg_mask(bt));
 				return -EFAULT;
 			}
 
-			/* BPF_EXIT in subprog or callback always returns
-			 * right after the call instruction, so by checking
-			 * whether the instruction at subseq_idx-1 is subprog
-			 * call or not we can distinguish actual exit from
-			 * *subprog* from exit from *callback*. In the former
-			 * case, we need to propagate r0 precision, if
-			 * necessary. In the former we never do that.
-			 */
-			r0_precise = subseq_idx - 1 >= 0 &&
-				     bpf_pseudo_call(&env->prog->insnsi[subseq_idx - 1]) &&
-				     bt_is_reg_set(bt, BPF_REG_0);
-
 			bt_clear_reg(bt, BPF_REG_0);
 			if (bt_subprog_enter(bt))
 				return -EFAULT;

-- 
2.53.0

[PATCH bpf 2/2] selftests/bpf: test case for unsafe pruning of bpf_loop checkpoints

[Eduard Zingerman]

The following BPF program was erroneously accepted by the verifier:

  static int cb(int i, __u64 *ctx)
  {
	/* unsafe on a second iteration */
	small_arr[*ctx] = i;
	*ctx = 100500;
	return 0;
  }
  int main(void *ctx)
  {
        int nr_loops = 1;
        u64 ctx = 0;
  	if (unlikely(bpf_get_prandom_u32() == 42))
        	nr_loops = 2;
        bpf_loop(nr_loops, cb, &ctx, 0);
        return 0;
  }

The branch with nr_loops == 1 was explored first and injected a
checkpoint at the entry to 'cb', such that nr_loops in the main's
frame was not marked as precise. This checkpoint pruned the state with
nr_loops == 2 and the program was accepted.

This test case corresponds to the program above.
Entry point is written in assembly to ensure branch processing order.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/iters.c | 39 +++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 62d7df9e80be..c6699159dacd 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -2149,4 +2149,43 @@ __naked int stack_misc_vs_scalar_in_a_loop(void)
 	);
 }
 
+__used
+static int loop_cb5(int i, __u64 *ctx)
+{
+	/* unsafe on a second iteration */
+	small_arr[*ctx] = i;
+	*ctx = 100500;
+	return 0;
+}
+
+SEC("raw_tp")
+__flag(BPF_F_TEST_STATE_FREQ)
+__failure __msg("memory access is {{.*}} and is outside of the object of size 64")
+__naked void loop_counter_precision_2nd_iter(void)
+{
+	asm volatile (
+		"call %[bpf_get_prandom_u32];"
+		"*(u64 *)(r10 - 8) = 0;"
+		"r1 = 2;"
+		"if r0 == 42 goto +1;"
+		"r1 = 1;"
+		"r2 = loop_cb5 ll;"
+		"r3 = r10;"
+		"r3 += -8;"
+		"r4 = 0;"
+		/*
+		 * Explore with nr_loops=1 on a first path and nr_loops=2 on a second path.
+		 * Buggy verifier did not propagate r1 precision properly,
+		 * and thus checkpoints created for nr_loops=1 case matched nr_loops=2 case.
+		 */
+		"call %[bpf_loop];"
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_loop),
+		  __imm(bpf_get_prandom_u32)
+		: __clobber_all
+	);
+}
+
 char _license[] SEC("license") = "GPL";

-- 
2.53.0

Re: [PATCH bpf 1/2] bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Flawed heuristic for distinguishing subprog exits from callback exits causes the verifier to erroneously reject safe programs that call a subprog immediately before a looping callback.
--

commit 09e9430ffafbb3bf72d2c301a4d20da098050142
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks

This commit fixes precision propagation for R1 during a second iteration of
bpf_loop(). It removes the logic in backtrack_insn() that previously cleared
R1-R5 when backtracking through a callback's BPF_EXIT, ensuring precision
marks are not incorrectly reset.

> diff --git a/kernel/bpf/backtrack.c b/kernel/bpf/backtrack.c
> index a2b18a9f1694c..4fe9065106739 100644
> --- a/kernel/bpf/backtrack.c
> +++ b/kernel/bpf/backtrack.c
> @@ -520,37 +520,34 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
[ ... ]
>  		} else if (opcode == BPF_EXIT) {
> -			bool r0_precise;
> +			bool from_subprog_call, r0_precise;
> +
> +			/* BPF_EXIT in subprog or callback always returns
> +			 * right after the call instruction, so by checking
> +			 * whether the instruction at subseq_idx-1 is subprog
> +			 * call or not we can distinguish actual exit from
> +			 * *subprog* from exit from *callback*. In the former
> +			 * case, we need to propagate r0 precision, if
> +			 * necessary. In the former we never do that.
> +			 */
> +			from_subprog_call = subseq_idx - 1 >= 0 &&
> +					    bpf_pseudo_call(&env->prog->insnsi[subseq_idx - 1]);

[Severity: High]
Can this heuristic misclassify a callback exit as a subprog exit?

If a program calls a subprog immediately followed by an iterating callback
helper (like bpf_loop()), and we backtrack from the callback's BPF_EXIT,
subseq_idx equals the index of bpf_loop(). Checking subseq_idx - 1 evaluates
the instruction before bpf_loop(), which happens to be the subprog call.

This makes from_subprog_call incorrectly evaluate to true for the callback.

> +
> +			r0_precise = from_subprog_call && bt_is_reg_set(bt, BPF_REG_0);
>  
>  			/* Backtracking to a nested function call, 'idx' is a part of
>  			 * the inner frame 'subseq_idx' is a part of the outer frame.
>  			 * In case of a regular function call, instructions giving
>  			 * precision to registers R1-R5 should have been found already.
> -			 * In case of a callback, it is ok to have R1-R5 marked for
> -			 * backtracking, as these registers are set by the function
> -			 * invoking callback.
> +			 * In case of a callback from bpf_loop(), R{1,4} in the calling
> +			 * frame would be set as precise and that is correct.
>  			 */
> -			if (subseq_idx >= 0 && bpf_calls_callback(env, subseq_idx))
> -				for (i = BPF_REG_1; i <= BPF_REG_5; i++)
> -					bt_clear_reg(bt, i);
> -			if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) {
> +			if (from_subprog_call && (bt_reg_mask(bt) & BPF_REGMASK_ARGS)) {
>  				verifier_bug(env, "backtracking exit unexpected regs %x",
>  					     bt_reg_mask(bt));
>  				return -EFAULT;
>  			}

[Severity: High]
Will this incorrectly trigger the verifier bug check for callbacks?

Because bpf_loop() requests R1 precision (which falls under BPF_REGMASK_ARGS),
the misclassified from_subprog_call causes this safety check to evaluate to
true. Could this prematurely abort verification with -EFAULT and falsely reject
perfectly safe BPF programs?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260831-bug-015-backtrack-cb-args-precise-v1-1-68a8e2a821e0@gmail.com?part=1

Re: [PATCH bpf 1/2] bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks

[Eduard Zingerman]

On Tue, 2026-09-01 at 02:02 +0000, sashiko-bot@kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [High] Flawed heuristic for distinguishing subprog exits from callback exits causes the verifier to erroneously reject safe programs that call a subprog immediately before a looping callback.
> --
> 
> commit 09e9430ffafbb3bf72d2c301a4d20da098050142
> Author: Eduard Zingerman <eddyz87@gmail.com>
> 
> bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks
> 
> This commit fixes precision propagation for R1 during a second iteration of
> bpf_loop(). It removes the logic in backtrack_insn() that previously cleared
> R1-R5 when backtracking through a callback's BPF_EXIT, ensuring precision
> marks are not incorrectly reset.
> 
> > diff --git a/kernel/bpf/backtrack.c b/kernel/bpf/backtrack.c
> > index a2b18a9f1694c..4fe9065106739 100644
> > --- a/kernel/bpf/backtrack.c
> > +++ b/kernel/bpf/backtrack.c
> > @@ -520,37 +520,34 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> [ ... ]
> >  		} else if (opcode == BPF_EXIT) {
> > -			bool r0_precise;
> > +			bool from_subprog_call, r0_precise;
> > +
> > +			/* BPF_EXIT in subprog or callback always returns
> > +			 * right after the call instruction, so by checking
> > +			 * whether the instruction at subseq_idx-1 is subprog
> > +			 * call or not we can distinguish actual exit from
> > +			 * *subprog* from exit from *callback*. In the former
> > +			 * case, we need to propagate r0 precision, if
> > +			 * necessary. In the former we never do that.
> > +			 */
> > +			from_subprog_call = subseq_idx - 1 >= 0 &&
> > +					    bpf_pseudo_call(&env->prog->insnsi[subseq_idx - 1]);
> 
> [Severity: High]
> Can this heuristic misclassify a callback exit as a subprog exit?
> 
> If a program calls a subprog immediately followed by an iterating callback
> helper (like bpf_loop()), and we backtrack from the callback's BPF_EXIT,
> subseq_idx equals the index of bpf_loop(). Checking subseq_idx - 1 evaluates
> the instruction before bpf_loop(), which happens to be the subprog call.
> 
> This makes from_subprog_call incorrectly evaluate to true for the callback.

But that can't really happen. If the code looks like this:

  foo(...);
  bpf_loop(...);

There should be r1-r4 setup for bpf_loop() call, because foo()
invalidates those.

> > +
> > +			r0_precise = from_subprog_call && bt_is_reg_set(bt, BPF_REG_0);
> >  
> >  			/* Backtracking to a nested function call, 'idx' is a part of
> >  			 * the inner frame 'subseq_idx' is a part of the outer frame.
> >  			 * In case of a regular function call, instructions giving
> >  			 * precision to registers R1-R5 should have been found already.
> > -			 * In case of a callback, it is ok to have R1-R5 marked for
> > -			 * backtracking, as these registers are set by the function
> > -			 * invoking callback.
> > +			 * In case of a callback from bpf_loop(), R{1,4} in the calling
> > +			 * frame would be set as precise and that is correct.
> >  			 */
> > -			if (subseq_idx >= 0 && bpf_calls_callback(env, subseq_idx))
> > -				for (i = BPF_REG_1; i <= BPF_REG_5; i++)
> > -					bt_clear_reg(bt, i);
> > -			if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) {
> > +			if (from_subprog_call && (bt_reg_mask(bt) & BPF_REGMASK_ARGS)) {
> >  				verifier_bug(env, "backtracking exit unexpected regs %x",
> >  					     bt_reg_mask(bt));
> >  				return -EFAULT;
> >  			}
> 
> [Severity: High]
> Will this incorrectly trigger the verifier bug check for callbacks?
> 
> Because bpf_loop() requests R1 precision (which falls under BPF_REGMASK_ARGS),
> the misclassified from_subprog_call causes this safety check to evaluate to
> true. Could this prematurely abort verification with -EFAULT and falsely reject
> perfectly safe BPF programs?

See above.

Re: [PATCH bpf 1/2] bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Mon, 31 Aug 2026 18:36:09 -0700 you wrote:
> When processing calls to bpf_loop() verifier marks R1 (and R4) as
> precise. R1 tracks loop iterations number and because of the
> 'callback_depth < R1' mechanics in check_helper_call() must be marked
> precise. However, precision propagation for R1 was broken,
> when bpf_loop() call was verified on a second iteration.
> 
> Consider the following verification trace:
> - main: bpf_loop(nr_loops, callback ...)
> - callback: BPF_EXIT
> - main: bpf_loop(nr_loops, callback ...)
> - ...
> 
> [...]

Here is the summary with links:
  - [bpf,1/2] bpf: backtracking shouldn't clear outer frame R1-R5 for callbacks
    https://git.kernel.org/bpf/bpf/c/e3e4f66cc4b7
  - [bpf,2/2] selftests/bpf: test case for unsafe pruning of bpf_loop checkpoints
    https://git.kernel.org/bpf/bpf/c/7ac966218906

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html