Skip to contentSkip to conversation

bpf: Fix unsound scalar forking for BPF_OR

PATCH Superseded Daniel Wade 3 participants 8 messages Mar 13 – Mar 14

Subsystems (4)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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.

Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
index a9e2380327..68fa308520 100644
@@ -14206,7 +14206,7 @@ static int maybe_fork_scalars(struct bpf_verifier_env *env, struct bpf_insn *ins
 	else
 		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
Reviewed-by on v3 1/2
#2 lore raw

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 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.

Quoted 6 lines

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.

Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")
Quoted 20 lines
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -2
index a9e2380327..68fa308520 100644
@@ -14206,7 +14206,7 @@ static int maybe_fork_scalars(struct bpf_verifier_env *env, struct bpf_insn *ins
        else
                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

maintainer Acked-by on v3 1/2
#3 lore raw

Re: [PATCH bpf v3 1/2] bpf: Fix unsound scalar forking in maybe_fork_scalars() for BPF_OR

In reply to Daniel Wade
Quoted 12 lines · Daniel Wade

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.

Quoted 7 lines

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.

Fixes bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")

---

#4 lore raw

PATCH v3 2/2 selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling

In reply to Daniel Wade

Add 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
index a0bb7fb40e..bf834414ea 100644
@@ -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)
+{
+	asm volatile ("					\
+	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)
+{
+	asm volatile ("					\
+	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;					\
+	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
Reviewed-by on v3 2/2
#5 lore raw

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.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.

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.

---
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
index a0bb7fb40e..bf834414ea 100644
@@ -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)
+{
+       asm volatile ("                                 \
+       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)
+{
+       asm volatile ("                                 \
+       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

#6 lore raw

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.

maintainer Acked-by on v3 2/2
#7 lore raw

Re: [PATCH bpf v3 2/2] selftests/bpf: Add tests for maybe_fork_scalars() OR vs AND handling

In reply to Daniel Wade
Quoted 16 lines · Daniel Wade

Add 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.

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.

---

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")