Skip to contentSkip to conversation

bpf: Fix unsound scalar forking for BPF_OR

PATCH Superseded Daniel Wade 3 participants 7 messages Mar 10 – Mar 12

Subsystems (4)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

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

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

Fixes 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
index a9e2380327..2e644f489e 100644
@@ -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 *ins
 		return 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(&regs[insn->dst_reg], 0);
+		__mark_reg32_known(&regs[insn->dst_reg],
+				   opcode == BPF_OR ? (u32)insn->imm : 0);
 		__mark_reg32_known(dst_reg, -1ull);
 	} else {
-		__mark_reg_known(&regs[insn->dst_reg], 0);
+		__mark_reg_known(&regs[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
maintainer
#2 lore raw

Re: [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 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)

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

---

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 *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);
 

Just to keep maybe_fork_scalars() more generic for potential future uses?

[...]

#3 lore raw

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

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

---

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 *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);
 

Just to keep maybe_fork_scalars() more generic for potential future uses?

[...]

#4 lore raw

PATCH 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 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
index a0bb7fb40e..541d70fa46 100644
@@ -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)
+{
+	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 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)
+{
+	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 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)
+{
+	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 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
Reviewed-by on the v1 series
#5 lore raw
In reply to Daniel Wade
Quoted 7 lines · Daniel Wade

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.

Quoted 9 lines

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

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

#6 lore raw
Quoted 19 lines · Amery Hung
Quoted 7 lines · Daniel Wade

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.

Quoted 9 lines

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

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:
commit bffacdb80b93 ("bpf: Recognize special arithmetic shift in the verifier")

oops. It is in patch 1. Please ignore my comment...

Quoted 11 lines
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