bpf: Fix unsound scalar forking for BPF_OR
Subsystems (4)
cover bpf: Fix unsound scalar forking for BPF_OR
maybe_fork_scalars() unconditionally sets the pushed path dst register to 0 for both BPF_AND and BPF_OR. For AND this is correct (0 & K == 0), but for OR it is wrong (0 | K == K, not 0). This causes the verifier to track an incorrect value on the pushed path, leading to a verifier/runtime divergence that allows out-of-bounds map value access.
Patch 1 fixes the bug by passing the opcode into maybe_fork_scalars() so it sets the pushed value to K for BPF_OR, and 0 for BPF_AND.
Patch 2 adds three selftests to verifier_bounds.c exercising the fix.
Daniel Wade (2):
bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling
kernel/bpf/verifier.c | 15 ++- .../selftests/bpf/progs/verifier_bounds.c | 102 ++++++++++++++++++ 2 files changed, 112 insertions(+), 5 deletions(-)
Signature · 1 line
2.43.0
PATCH 1/2 bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR
maybe_fork_scalars() is called for both BPF_AND and BPF_OR when the source operand is a constant. When dst has signed range [-1, 0], it forks the verifier state, setting the pushed path dst to 0 and the current path dst to -1.
For BPF_AND this is correct: 0 & K == 0. For BPF_OR this is wrong: 0 | K == K, not 0.
The pushed path therefore tracks dst as 0 when the runtime value is K, producing an exploitable verifier/runtime divergence that allows out-of-bounds map access.
Fix this by passing the opcode into maybe_fork_scalars() so it can set the correct value for the pushed state:
- BPF_AND: pushed dst = 0 (unchanged)
- BPF_OR: pushed dst = insn->imm (the constant K)
The bug was introduced by commit bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier").
--- kernel/bpf/verifier.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +10 -5
@@ -14193,7 +14193,7 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn, }static int maybe_fork_scalars (struct bpf_verifier_env *env,struct bpf_insn *insn, -struct bpf_reg_state *dst_reg) +struct bpf_reg_state *dst_reg,u8 opcode) {struct bpf_verifier_state *branch;struct bpf_reg_state *regs;
@@ -14211,11 +14211,16 @@ static int maybe_fork_scalars(struct bpf_verifier_env *env, struct bpf_insn *insreturn PTR_ERR (branch); regs = branch->frame[branch->curframe]->regs; +/* For AND: 0 & K == 0, so pushed dst = 0 is correct. +* For OR: 0 | K == K, so pushed dst must be set to K. +*/ if (alu32) { -__mark_reg32_known (®s[insn->dst_reg],0 ); +__mark_reg32_known (®s[insn->dst_reg], + opcode ==BPF_OR ? (u32 )insn->imm :0 );__mark_reg32_known (dst_reg,-1ull ); }else { -__mark_reg_known (®s[insn->dst_reg],0 ); +__mark_reg_known (®s[insn->dst_reg], + opcode ==BPF_OR ? insn->imm :0 );__mark_reg_known (dst_reg,-1ull ); }return 0 ;
@@ -14277,7 +14282,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,break ;case BPF_AND :if (tnum_is_const (src_reg.var_off)) { - ret =maybe_fork_scalars (env, insn, dst_reg); + ret =maybe_fork_scalars (env, insn, dst_reg,BPF_AND );if (ret)return ret; }
@@ -14287,7 +14292,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,break ;case BPF_OR :if (tnum_is_const (src_reg.var_off)) { - ret =maybe_fork_scalars (env, insn, dst_reg); + ret =maybe_fork_scalars (env, insn, dst_reg,BPF_OR );if (ret)return ret; }
Signature · 1 line
2.43.0
Eduard Zingerman
maintainerRe: [PATCH bpf 1/2] bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR
Quoted 17 lines · Daniel Wade
maybe_fork_scalars()is called for bothBPF_ANDandBPF_ORwhen the source operand is a constant. When dst has signed range [-1, 0], it forks the verifier state, setting the pushed path dst to 0 and the current path dst to -1.For BPF_AND this is correct: 0 & K == 0. For BPF_OR this is wrong: 0 | K == K, not 0.The pushed path therefore tracks dst as 0 when the runtime value is K, producing an exploitable verifier/runtime divergence that allows out-of-bounds map access.
Fix this by passing the opcode into
maybe_fork_scalars()so it can set the correct value for the pushed state:
-BPF_AND: pushed dst = 0 (unchanged)
-BPF_OR: pushed dst =insn->imm(the constant K)
Quoted 6 lines
The bug was introduced by commit
bffacdb80b93("bpf: Recognize special arithmetic shift in the verifier").Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")Signed-off-by Daniel Wade <[email protected]>---
Uh-oh, what a bug... Thank you for spotting this.
Let's, maybe, go for a smaller fix:
kernel/bpf/verifier.c +1 -1
@@ -15999,7 +15999,7 @@ static int maybe_fork_scalars(struct bpf_verifier_env *env, struct bpf_insn *inselse return 0 ; - branch =push_stack (env, env->insn_idx +1 , env->insn_idx, false); + branch =push_stack (env, env->insn_idx, env->insn_idx, false);if (IS_ERR (branch))return PTR_ERR (branch);
Just to keep maybe_fork_scalars() more generic for potential future uses?
[...]
Re: [PATCH bpf 1/2] bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR
Agreed, much cleaner. Will send v2.
Daniel
Quoted 43 lines · Eduard Zingerman
Quoted 17 lines · Daniel Wade
maybe_fork_scalars()is called for bothBPF_ANDandBPF_ORwhen the source operand is a constant. When dst has signed range [-1, 0], it forks the verifier state, setting the pushed path dst to 0 and the current path dst to -1.For BPF_AND this is correct: 0 & K == 0. For BPF_OR this is wrong: 0 | K == K, not 0.The pushed path therefore tracks dst as 0 when the runtime value is K, producing an exploitable verifier/runtime divergence that allows out-of-bounds map access.
Fix this by passing the opcode into
maybe_fork_scalars()so it can set the correct value for the pushed state:
-BPF_AND: pushed dst = 0 (unchanged)
-BPF_OR: pushed dst =insn->imm(the constant K)Quoted 6 lines
The bug was introduced by commit
bffacdb80b93("bpf: Recognize special arithmetic shift in the verifier").Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")Signed-off-by Daniel Wade <[email protected]>---
Uh-oh, what a bug... Thank you for spotting this.
Let's, maybe, go for a smaller fix:kernel/bpf/verifier.c +1
-1@@ -15999,7 +15999,7 @@ static int maybe_fork_scalars(struct bpf_verifier_env *env, struct bpf_insn *inselse return 0 ; - branch =push_stack (env, env->insn_idx +1 , env->insn_idx, false); + branch =push_stack (env, env->insn_idx, env->insn_idx, false);if (IS_ERR (branch))return PTR_ERR (branch);Just to keep
maybe_fork_scalars()more generic for potential future uses?[...]
PATCH 2/2 selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling
In reply to Daniel WadeAdd three test cases to verifier_bounds.c to verify that maybe_fork_scalars() correctly tracks register values for BPF_OR operations with constant source operands:
1. or_scalar_fork_rejects_oob: After ARSH 63 + OR 8, the pushed path should have dst = 8. With value_size = 8, accessing map_value + 8 is out of bounds and must be rejected.
2. and_scalar_fork_still_works: Regression test ensuring AND forking continues to work. ARSH 63 + AND 4 produces pushed dst = 0 and current dst = 4, both within value_size = 8.
3. or_scalar_fork_allows_inbounds: After ARSH 63 + OR 4, the pushed path has dst = 4, which is within value_size = 8 and should be accepted.
These tests exercise the fix in the previous patch, which passes the opcode into maybe_fork_scalars() so it sets the pushed path value to K (not 0) for BPF_OR.
--- .../selftests/bpf/progs/verifier_bounds.c | 102 ++++++++++++++++++ 1 file changed, 102 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +102 -0
@@ -1200,4 +1200,106 @@ l0_%=: r0 = 0; \ : __clobber_all); } +SEC("socket") +__description("maybe_fork_scalars: OR with constant rejects OOB") +__failure __msg("invalid access to map value") +__naked void or_scalar_fork_rejects_oob(void) +{ + asmvolatile (" \ +r1 = 0; \ +*(u64*)(r10 - 8) = r1; \ +r2 = r10; \ +r2 += -8; \ +r1 = %[map_hash_8b] ll; \ +call %[bpf_map_lookup_elem]; \ +if r0 == 0 goto l0_%=; \ +r9 = r0; \ +r6 = *(u64*)(r9 + 0); \ +r6 s>>= 63; \ +r6 |= 8; \ +/* r6 is now either -1 (current) or 8 (pushed). \ +* Current path: r6 < 0, branch taken, exits. \ +* Pushed path: r6 = 8, branch not taken. \ +*/ \ +if r6 s< 0 goto l0_%=; \ +/* Pushed path: verifier must know r6 = 8. \ +* map_hash_8b has value_size=8, so r9 + 8 \ +* is one byte past the end -- must be rejected. \ +*/ \ +r9 += r6; \ +r0 = *(u8*)(r9 + 0); \ +l0_%=: r0 = 0; \ +exit; \ +" : + : __imm(bpf_map_lookup_elem), +__imm_addr (map_hash_8b) + : __clobber_all); +} + +SEC("socket") +__description("maybe_fork_scalars: AND with constant still works") +__success __retval(0) +__naked void and_scalar_fork_still_works(void) +{ + asmvolatile (" \ +r1 = 0; \ +*(u64*)(r10 - 8) = r1; \ +r2 = r10; \ +r2 += -8; \ +r1 = %[map_hash_8b] ll; \ +call %[bpf_map_lookup_elem]; \ +if r0 == 0 goto l0_%=; \ +r9 = r0; \ +r6 = *(u64*)(r9 + 0); \ +r6 s>>= 63; \ +r6 &= 4; \ +/* r6 is now either 0 (pushed, 0&4==0) or \ +* 4 (current, -1&4==4 in AND path). \ +* Both paths: r6 >= 0, falls through. \ +* Both offsets within bounds of value_size=8. \ +*/ \ +if r6 s< 0 goto l0_%=; \ +r9 += r6; \ +r0 = *(u8*)(r9 + 0); \ +l0_%=: r0 = 0; \ +exit; \ +" : + : __imm(bpf_map_lookup_elem), +__imm_addr (map_hash_8b) + : __clobber_all); +} + +SEC("socket") +__description("maybe_fork_scalars: OR with constant allows in-bounds") +__success __retval(0) +__naked void or_scalar_fork_allows_inbounds(void) +{ + asmvolatile (" \ +r1 = 0; \ +*(u64*)(r10 - 8) = r1; \ +r2 = r10; \ +r2 += -8; \ +r1 = %[map_hash_8b] ll; \ +call %[bpf_map_lookup_elem]; \ +if r0 == 0 goto l0_%=; \ +r9 = r0; \ +r6 = *(u64*)(r9 + 0); \ +r6 s>>= 63; \ +r6 |= 4; \ +/* r6 is now either -1 (current) or 4 (pushed). \ +* Current path: r6 < 0, branch taken, exits. \ +* Pushed path: r6 = 4, offset 4 within \ +* value_size=8, so byte access at r9+4 is valid. \ +*/ \ +if r6 s< 0 goto l0_%=; \ +r9 += r6; \ +r0 = *(u8*)(r9 + 0); \ +l0_%=: r0 = 0; \ +exit; \ +" : + : __imm(bpf_map_lookup_elem), +__imm_addr (map_hash_8b) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
Quoted 7 lines · Daniel Wade
maybe_fork_scalars()unconditionally sets the pushed path dst register to 0 for bothBPF_ANDandBPF_OR. For AND this is correct (0 & K == 0), but for OR it is wrong (0 | K == K, not 0). This causes the verifier to track an incorrect value on the pushed path, leading to a verifier/runtime divergence that allows out-of-bounds map value access.
Quoted 9 lines
Patch 1 fixes the bug by passing the opcode into
maybe_fork_scalars()so it sets the pushed value to K forBPF_OR, and 0 forBPF_AND.Patch 2 adds three selftests to
verifier_bounds.cexercising the fix.Daniel Wade (2):
bpf: Fix unsound scalar forking inmaybe_fork_scalars()forBPF_ORselftests/bpf: Add tests formaybe_fork_scalars()OR vs AND handling
The fix and selftest make sense to me. To observe it, I also vibe-coded a poc to lookup an array map element and OOB write to another element and confirm the issue.
May be missing a fix tag though:
commit bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")
Quoted 8 lines
kernel/bpf/verifier.c | 15 ++- .../selftests/bpf/progs/verifier_bounds.c | 102 ++++++++++++++++++ 2 files changed, 112 insertions(+), 5 deletions(-)--
2.43.0
Quoted 19 lines · Amery Hung
Quoted 7 lines · Daniel Wade
maybe_fork_scalars()unconditionally sets the pushed path dst register to 0 for bothBPF_ANDandBPF_OR. For AND this is correct (0 & K == 0), but for OR it is wrong (0 | K == K, not 0). This causes the verifier to track an incorrect value on the pushed path, leading to a verifier/runtime divergence that allows out-of-bounds map value access.Quoted 9 lines
Patch 1 fixes the bug by passing the opcode into
maybe_fork_scalars()so it sets the pushed value to K forBPF_OR, and 0 forBPF_AND.Patch 2 adds three selftests to
verifier_bounds.cexercising the fix.Daniel Wade (2):
bpf: Fix unsound scalar forking inmaybe_fork_scalars()forBPF_ORselftests/bpf: Add tests formaybe_fork_scalars()OR vs AND handling
Quoted 6 lines
The fix and selftest make sense to me. To observe it, I also vibe-coded a poc to lookup an array map element and OOB write to another element and confirm the issue.
May be missing a fix tag though:
commitbffacdb80b93("bpf: Recognize special arithmetic shift in the verifier")
oops. It is in patch 1. Please ignore my comment...
Quoted 11 lines
Reviewed-by Amery Hung <[email protected]>Quoted 8 lines
kernel/bpf/verifier.c | 15 ++- .../selftests/bpf/progs/verifier_bounds.c | 102 ++++++++++++++++++ 2 files changed, 112 insertions(+), 5 deletions(-)--
2.43.0