bpf: dont report verifier bug for missing bpf_scc_visit on speculative path
Subsystems (4)
Eduard Zingerman
maintainerPATCH 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.
--- kernel/bpf/verifier.c | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +18 -3
@@ -1950,9 +1950,24 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_statreturn 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
Eduard Zingerman
maintainerPATCH 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
@@ -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 voidmaybe_exit_scc_bug1 (void) +{ + asmvolatile ( +"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
Quoted 49 lines · Eduard Zingerman
Syzbot generated a program that triggers a
verifier_bug()call inmaybe_exit_scc().maybe_exit_scc()assumes that, when called for a state withinsn_idxin some SCC, there should be an instance of structbpf_scc_visitallocated 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 fromupdate_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 levelBPF_EXITis reached. Such instructions are never a part of
an SCC, socompute_scc_callchain()inmaybe_scc_exit()will return false, andmaybe_scc_exit()will return early.
c. A checkpoint is reached and matched. Checkpoints are created by
is_state_visited(), which callsmaybe_enter_scc(), which allocatesbpf_scc_visitinstances 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_visitinstance 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]Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-)kernel/bpf/verifier.c +3
-3@@ -1950,9 +1950,24 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_statreturn 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
Eduard Zingerman
maintainerOn 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_statreturn 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
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_statreturn 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
Eduard Zingerman
maintainerOn 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.
[...]
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 inmaybe_exit_scc().maybe_exit_scc()assumes that, when called for a state withinsn_idxin some SCC, there should be an instance of structbpf_scc_visitallocated 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