Skip to contentSkip to conversation

bpf: dont report verifier bug for missing bpf_scc_visit on speculative path

PATCH Applied Eduard Zingerman 3 participants 7 messages Sep 16, 2025 – Sep 17, 2025

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

PATCH 1/2 bpf: dont report verifier bug for missing bpf_scc_visit on speculative path

Syzbot generated a program that triggers a verifier_bug() call in maybe_exit_scc(). maybe_exit_scc() assumes that, when called for a state with insn_idx in some SCC, there should be an instance of struct bpf_scc_visit allocated for that SCC. Turns out the assumption does not hold for speculative execution paths. See example in the next patch.

maybe_scc_exit() is called from update_branch_counts() for states that reach branch count of zero, meaning that path exploration for a particular path is finished. Path exploration can finish in one of three ways:
a. Verification error is found. In this case, update_branch_counts()
is called only for non-speculative paths.
b. Top level BPF_EXIT is reached. Such instructions are never a part of
an SCC, so compute_scc_callchain() in maybe_scc_exit() will return false, and maybe_scc_exit() will return early.
c. A checkpoint is reached and matched. Checkpoints are created by
is_state_visited(), which calls maybe_enter_scc(), which allocates bpf_scc_visit instances for checkpoints within SCCs.

Hence, for non-speculative symbolic execution paths, the assumption still holds: if maybe_scc_exit() is called for a state within an SCC, bpf_scc_visit instance must exist.

This patch removes the verifier_bug() call for speculative paths.

Fixes c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
Reported-by [email protected]
---
 kernel/bpf/verifier.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +18 -3
index 1029380f84db..beaa391e02fb 100644
@@ -1950,9 +1950,24 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
 		return 0;
 	visit = scc_visit_lookup(env, callchain);
 	if (!visit) {
-		verifier_bug(env, "scc exit: no visit info for call chain %s",
-			     format_callchain(env, callchain));
-		return -EFAULT;
+		/*
+		 * If path traversal stops inside an SCC, corresponding bpf_scc_visit
+		 * must exist for non-speculative paths. For non-speculative paths
+		 * traversal stops when:
+		 * a. Verification error is found, maybe_exit_scc() is not called.
+		 * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member
+		 *    of any SCC.
+		 * c. A checkpoint is reached and matched. Checkpoints are created by
+		 *    is_state_visited(), which calls maybe_enter_scc(), which allocates
+		 *    bpf_scc_visit instances for checkpoints within SCCs.
+		 * (c) is the only case that can reach this point.
+		 */
+		if (!st->speculative) {
+			verifier_bug(env, "scc exit: no visit info for call chain %s",
+				     format_callchain(env, callchain));
+			return -EFAULT;
+		}
+		return 0;
 	}
 	if (visit->entry_state != st)
 		return 0;
Signature · 1 line
2.51.0
author maintainer
#1 lore raw

PATCH 2/2 selftests/bpf: trigger verifier.c:maybe_exit_scc() for a speculative state

This is a test case minimized from a syzbot reproducer from [1]. The test case triggers verifier.c:maybe_exit_scc() w/o preceding call to verifier.c:maybe_enter_scc() on a speculative symbolic execution path.

Here is verifier log for the test case:

Live regs before insn:

        0: .......... (b7) r0 = 100
    1   1: 0......... (7b) *(u64 *)(r10 -512) = r0
    1   2: 0......... (b5) if r0 <= 0x0 goto pc-2
        3: 0......... (95) exit

0: R1=ctx() R10=fp0
0: (b7) r0 = 100 ; R0_w=100
1: (7b) *(u64 *)(r10 -512) = r0 ; R0_w=100 R10=fp0 fp-512_w=100
2: (b5) if r0 <= 0x0 goto pc-2
mark_precise: ...
2: R0_w=100
3: (95) exit

from 2 to 1 (speculative execution): R0_w=scalar() R1=ctx() R10=fp0 fp-512_w=100 1: R0_w=scalar() R1=ctx() R10=fp0 fp-512_w=100
1: (7b) *(u64 *)(r10 -512) = r0
processed 5 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0

- Non-speculative execution path 0-3 does not allocate any checkpoints (and hence does not call maybe_enter_scc()), and schedules a speculative jump from 2 to 1.
- Speculative execution path stops immediately because of an infinite loop detection and triggers verifier.c:update_branch_counts() -> maybe_exit_scc() calls.

[1] https://lore.kernel.org/bpf/[email protected]/

---
 .../selftests/bpf/progs/verifier_loops1.c     | 21 +++++++++++++++++++
 1 file changed, 21 insertions(+)
tools/testing/selftests/bpf/progs/verifier_loops1.c +21 -0
index e07b43b78fd2..fbdde80e7b90 100644
@@ -283,4 +283,25 @@ exit_%=:						\
 	: __clobber_all);
 }
 
+/*
+ * This test case triggered a bug in verifier.c:maybe_exit_scc().
+ * Speculative execution path reaches stack access instruction,
+ * stops and triggers maybe_exit_scc() w/o accompanying maybe_enter_scc() call.
+ */
+SEC("socket")
+__arch_x86_64
+__caps_unpriv(CAP_BPF)
+__naked void maybe_exit_scc_bug1(void)
+{
+	asm volatile (
+	"r0 = 100;"
+"1:"
+	/* Speculative execution path reaches and stops here. */
+	"*(u64 *)(r10 - 512) = r0;"
+	/* Condition is always false, but verifier speculatively executes the true branch. */
+	"if r0 <= 0x0 goto 1b;"
+	"exit;"
+	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.51.0
#2 lore raw
In reply to Eduard Zingerman
Quoted 49 lines · Eduard Zingerman

Syzbot generated a program that triggers a verifier_bug() call in maybe_exit_scc(). maybe_exit_scc() assumes that, when called for a state with insn_idx in some SCC, there should be an instance of struct bpf_scc_visit allocated for that SCC. Turns out the assumption does not hold for speculative execution paths. See example in the next patch.

maybe_scc_exit() is called from update_branch_counts() for states that reach branch count of zero, meaning that path exploration for a particular path is finished. Path exploration can finish in one of three ways:
a. Verification error is found. In this case, update_branch_counts()
is called only for non-speculative paths.
b. Top level BPF_EXIT is reached. Such instructions are never a part of
an SCC, so compute_scc_callchain() in maybe_scc_exit() will return false, and maybe_scc_exit() will return early.
c. A checkpoint is reached and matched. Checkpoints are created by
is_state_visited(), which calls maybe_enter_scc(), which allocates bpf_scc_visit instances for checkpoints within SCCs.

Hence, for non-speculative symbolic execution paths, the assumption still holds: if maybe_scc_exit() is called for a state within an SCC, bpf_scc_visit instance must exist.

This patch removes the verifier_bug() call for speculative paths.

Fixes c9e31900b54c ("bpf: propagate read/precision marks over state graph backedges")
Reported-by [email protected]
---
 kernel/bpf/verifier.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +3 -3
index 1029380f84db..beaa391e02fb 100644
@@ -1950,9 +1950,24 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
                return 0;
        visit = scc_visit_lookup(env, callchain);
        if (!visit) {
-               verifier_bug(env, "scc exit: no visit info for call chain %s",
-                            format_callchain(env, callchain));
-               return -EFAULT;
+               /*
+                * If path traversal stops inside an SCC, corresponding bpf_scc_visit
+                * must exist for non-speculative paths. For non-speculative paths

kernel/bpf/verifier.c static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat · line 1965

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+                * traversal stops when:
+                * a. Verification error is found, maybe_exit_scc() is not called.
+                * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member
+                *    of any SCC.
+                * c. A checkpoint is reached and matched. Checkpoints are created by
+                *    is_state_visited(), which calls maybe_enter_scc(), which allocates
+                *    bpf_scc_visit instances for checkpoints within SCCs.
+                * (c) is the only case that can reach this point.
+                */
+               if (!st->speculative) {

grumpy nit:

if (st->speculative)

    return 0;

... leave the rest untouched ...

?

Quoted 11 lines
kernel/bpf/verifier.c +5 -1
+                       verifier_bug(env, "scc exit: no visit info for call chain %s",
+                                    format_callchain(env, callchain));
+                       return -EFAULT;
+               }
+               return 0;
        }
        if (visit->entry_state != st)
                return 0;
--

2.51.0

author maintainer
#3 lore raw

On Tue, 2025-09-16 at 15:33 -0700, Andrii Nakryiko wrote:

[...]

Quoted 23 lines
Quoted 10 lines
kernel/bpf/verifier.c +3 -3
@@ -1950,9 +1950,24 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
                return 0;
        visit = scc_visit_lookup(env, callchain);
        if (!visit) {
-               verifier_bug(env, "scc exit: no visit info for call chain %s",
-                            format_callchain(env, callchain));
-               return -EFAULT;
+               /*
+                * If path traversal stops inside an SCC, corresponding bpf_scc_visit
+                * must exist for non-speculative paths. For non-speculative paths

kernel/bpf/verifier.c static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat · line 1965

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+                * traversal stops when:
+                * a. Verification error is found, maybe_exit_scc() is not called.
+                * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member
+                *    of any SCC.
+                * c. A checkpoint is reached and matched. Checkpoints are created by
+                *    is_state_visited(), which calls maybe_enter_scc(), which allocates
+                *    bpf_scc_visit instances for checkpoints within SCCs.
+                * (c) is the only case that can reach this point.
+                */
+               if (!st->speculative) {

grumpy nit:

Quoted 6 lines

if (st->speculative)

    return 0;

... leave the rest untouched ...

?

I did this on purpose. In the comment above I explain why the error is valid only for non-speculative path, so want to have code and comment in sync. Tried inverting the comment to explain why it's not an error on a speculative path and it is confusing.

Quoted 12 lines
Quoted 12 lines
kernel/bpf/verifier.c +5 -1
+                       verifier_bug(env, "scc exit: no visit info for call chain %s",
+                                    format_callchain(env, callchain));
+                       return -EFAULT;
+               }
+               return 0;
        }
        if (visit->entry_state != st)
                return 0;
--

2.51.0

#4 lore raw
Quoted 31 lines · Eduard Zingerman

On Tue, 2025-09-16 at 15:33 -0700, Andrii Nakryiko wrote:

[...]

Quoted 26 lines
Quoted 10 lines
kernel/bpf/verifier.c +3 -3
@@ -1950,9 +1950,24 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
                return 0;
        visit = scc_visit_lookup(env, callchain);
        if (!visit) {
-               verifier_bug(env, "scc exit: no visit info for call chain %s",
-                            format_callchain(env, callchain));
-               return -EFAULT;
+               /*
+                * If path traversal stops inside an SCC, corresponding bpf_scc_visit
+                * must exist for non-speculative paths. For non-speculative paths

kernel/bpf/verifier.c static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat · line 1965

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+                * traversal stops when:
+                * a. Verification error is found, maybe_exit_scc() is not called.
+                * b. Top level BPF_EXIT is reached. Top level BPF_EXIT is not a member
+                *    of any SCC.
+                * c. A checkpoint is reached and matched. Checkpoints are created by
+                *    is_state_visited(), which calls maybe_enter_scc(), which allocates
+                *    bpf_scc_visit instances for checkpoints within SCCs.
+                * (c) is the only case that can reach this point.
+                */
+               if (!st->speculative) {

grumpy nit:

if (st->speculative)

    return 0;
Quoted 8 lines
Quoted 3 lines

... leave the rest untouched ...

?

I did this on purpose. In the comment above I explain why the error is valid only for non-speculative path, so want to have code and comment in sync. Tried inverting the comment to explain why it's not an error on a speculative path and it is confusing.

...
* (c) is the only reason we can error out below for non-speculative path". */
if (!st->speculative)

      return 0;
  verifier_buf(...);

(even as is your comment read just fine in my head, tbh).

But I don't insist, if you find this confusing, I just don't like deeply nested code when less nested would work.

Quoted 13 lines
Quoted 13 lines
Quoted 13 lines
kernel/bpf/verifier.c +5 -1
+                       verifier_bug(env, "scc exit: no visit info for call chain %s",
+                                    format_callchain(env, callchain));
+                       return -EFAULT;
+               }
+               return 0;
        }
        if (visit->entry_state != st)
                return 0;
--

2.51.0

author maintainer
#5 lore raw

On Tue, 2025-09-16 at 15:47 -0700, Andrii Nakryiko wrote:

[...]

Quoted 18 lines
Quoted 5 lines
Quoted 5 lines

grumpy nit:

if (st->speculative)

    return 0;
Quoted 8 lines
Quoted 3 lines

... leave the rest untouched ...

?

I did this on purpose. In the comment above I explain why the error is valid only for non-speculative path, so want to have code and comment in sync. Tried inverting the comment to explain why it's not an error on a speculative path and it is confusing.

...
* (c) is the only reason we can error out below for non-speculative path". */
if (!st->speculative)

Quoted 8 lines
      return 0;
  verifier_buf(...);

(even as is your comment read just fine in my head, tbh).

But I don't insist, if you find this confusing, I just don't like deeply nested code when less nested would work.

Don't like nested code either, but in this particular case like mine version a bit more:
- same nesting level in both cases
- error condition is explicit
- in sync with the comment.

[...]

#6 lore raw
In reply to Eduard Zingerman
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 8 lines · On Tue, 16 Sep 2025 14:22:50 -0700 you wrote:

Syzbot generated a program that triggers a verifier_bug() call in maybe_exit_scc(). maybe_exit_scc() assumes that, when called for a state with insn_idx in some SCC, there should be an instance of struct bpf_scc_visit allocated for that SCC. Turns out the assumption does not hold for speculative execution paths. See example in the next patch.

[...]

Here is the summary with links:
- [bpf-next,v1,1/2] bpf: dont report verifier bug for missing bpf_scc_visit on speculative path

    https://git.kernel.org/bpf/bpf-next/c/a3c73d629ea1
  - [bpf-next,v1,2/2] selftests/bpf: trigger verifier.c:maybe_exit_scc() for a speculative state
    https://git.kernel.org/bpf/bpf-next/c/a24a2dda70fb

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html