bpf: Fix unsound scalar forking for BPF_OR
Subsystems (4)
v3 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.
v3: Use single-line comment style in selftests (Alexei Starovoitov)
v2: Use push_stack(env, env->insn_idx, ...) to re-execute the insn
on the pushed path (Eduard Zingerman)
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 | 2 +- .../selftests/bpf/progs/verifier_bounds.c | 90 +++++++++++++++++++ 2 files changed, 91 insertions(+), 1 deletion(-)
Signature · 1 line
2.43.0
PATCH v3 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: the pushed path gets dst = 0, the current path gets dst = -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 env->insn_idx (instead of env->insn_idx + 1) to push_stack(), so the pushed path re-executes the ALU instruction with dst = 0 and naturally computes the correct result for any opcode.
--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
@@ -14206,7 +14206,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);
Signature · 1 line
2.43.0
Re: [PATCH bpf v3 1/2] bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR
Quoted 13 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: the pushed path gets dst = 0, the current path gets dst = -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.
Quoted 6 lines
Fix this by passing
env->insn_idx(instead ofenv->insn_idx+ 1) topush_stack(), so the pushed path re-executes the ALU instruction with dst = 0 and naturally computes the correct result for any opcode.Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")Signed-off-by Daniel Wade <[email protected]>
Quoted 20 lines
--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)kernel/bpf/verifier.c +1
-2@@ -14206,7 +14206,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); --2.43.0
Re: [PATCH bpf v3 1/2] bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR
In reply to Daniel WadeQuoted 12 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: the pushed path gets dst = 0, the current path gets dst = -1.For
BPF_ANDthis is correct: 0 & K == 0.
ForBPF_ORthis 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.
Quoted 7 lines
Fix this by passing
env->insn_idx(instead ofenv->insn_idx+ 1) topush_stack(), so the pushed path re-executes the ALU instruction with dst = 0 and naturally computes the correct result for any opcode.Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")Signed-off-by Daniel Wade <[email protected]>---
PATCH v3 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 makes the pushed path re-execute the ALU instruction so it computes the correct result for BPF_OR.
---
v3: Use single-line comment style (Alexei Starovoitov)
v2: Update tests for re-execute fix approach (Eduard Zingerman)
--- .../selftests/bpf/progs/verifier_bounds.c | 90 +++++++++++++++++++ 1 file changed, 90 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +90 -0
@@ -1200,4 +1200,94 @@ 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 -1 (current) or 8 (pushed) */ \ +if r6 s< 0 goto l0_%=; \ +/* pushed path: r6 = 8, OOB for value_size=8 */ \ +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 0 (pushed, 0&4==0) or 4 (current) */ \ +/* both within 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 -1 (current) or 4 (pushed) */ \ +/* pushed path: r6 = 4, within 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); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
Re: [PATCH bpf v3 2/2] selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling
Quoted 17 lines · Daniel Wade
Add three test cases to
verifier_bounds.cto verify thatmaybe_fork_scalars()correctly tracks register values forBPF_ORoperations with constant source operands:1.
or_scalar_fork_rejects_oob: After ARSH 63 + OR 8, the pushed path should have dst = 8. Withvalue_size= 8, accessingmap_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 withinvalue_size= 8.3.
or_scalar_fork_allows_inbounds: After ARSH 63 + OR 4, the pushed path has dst = 4, which is withinvalue_size= 8 and should be accepted.
Quoted 8 lines
These tests exercise the fix in the previous patch, which makes the pushed path re-execute the ALU instruction so it computes the correct result for
BPF_OR.Signed-off-by Daniel Wade <[email protected]>---
v3: Use single-line comment style (Alexei Starovoitov)
v2: Update tests for re-execute fix approach (Eduard Zingerman)
Quoted 81 lines
--- .../selftests/bpf/progs/verifier_bounds.c | 90 +++++++++++++++++++ 1 file changed, 90 insertions(+)tools/testing/selftests/bpf/progs/verifier_bounds.c +69
-0@@ -1200,4 +1200,94 @@ 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 -1 (current) or 8 (pushed) */ \ +if r6 s< 0 goto l0_%=; \ +/* pushed path: r6 = 8, OOB for value_size=8 */ \ +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 0 (pushed, 0&4==0) or 4 (current) */ \ +/* both within 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) +{ + asm volatile (" \ + r1 = 0; \ + *(u64*)(r10 - 8) = r1; \ + r2 = r10; \
tools/testing/selftests/bpf/progs/verifier_bounds.c l0_%=: r0 = 0; \ · line 1281
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +10
-0+ 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 -1 (current) or 4 (pushed) */ \ +/* pushed path: r6 = 4, within value_size=8 */ \
I think the proper multi-line comment styles mean something like below instead of the netdev style you were using in v1
/*
* r6 is -1 (current) or 4 (pushed)
* pushed path: r6 = 4, within value_size=8
*/
Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +11
-1+ 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"; --2.43.0
Re: [PATCH bpf v3 2/2] selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling
Quoted 7 lines · Amery Hung
I think the proper multi-line comment styles mean something like below instead of the netdev style you were using in v1
/*
* r6 is -1 (current) or 4 (pushed)
* pushed path: r6 = 4, within value_size=8
*/
Thanks Amery. I have updated the comment blocks in tests 2 and 3 to match this format and just sent v4 to the list with the Reviewed-by and Acked-by tags included.
Re: [PATCH bpf v3 2/2] selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling
In reply to Daniel WadeQuoted 16 lines · Daniel Wade
Add three test cases to
verifier_bounds.cto verify thatmaybe_fork_scalars()correctly tracks register values forBPF_ORoperations with constant source operands:1.
or_scalar_fork_rejects_oob: After ARSH 63 + OR 8, the pushed path should have dst = 8. Withvalue_size= 8, accessingmap_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 withinvalue_size= 8.3.
or_scalar_fork_allows_inbounds: After ARSH 63 + OR 4, the pushed path has dst = 4, which is withinvalue_size= 8 and should be accepted.
Quoted 6 lines
These tests exercise the fix in the previous patch, which makes the pushed path re-execute the ALU instruction so it computes the correct result for
BPF_OR.Signed-off-by Daniel Wade <[email protected]>---
I think that test-cases 'and_scalar_fork_still_works' and 'or_scalar_fork_allows_inbounds' are somewhat redundant, but given that [1] only added negative tests let's keep these.
[1] 9160335317cb ("selftests/bpf: Add tests for s>>=31 and s>>=63")