bpf: reject pointer operands for 32-bit recurrences/latches
Subsystems (3)
Eduard Zingerman
maintainerPATCH 1/2 bpf: reject pointer operands for 32-bit recurrences/latches
Avoid inferring loop bounds for the following program shapes:
32-bit latch | 32-bit recurrence
-------------------------+--------------------------
r1 = ... pointer ... | r1 = ... pointer ...
r2 = ... pointer ... | r2 = ... pointer ...
l: r1 += 8 | l: w1 += 8
... | ...
if w1 < w2 goto l | if r1 < r2 goto lScalar bounds for pointers represent only offsets from their common origin values. The 32-bit operations above also depend on the runtime base address: the addresses can wrap at 32 bits without the tracked offsets wrapping. Thus, offsets alone do not determine the iteration count.
--- kernel/bpf/scev.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-)
kernel/bpf/scev.c +4 -3
@@ -2024,7 +2024,8 @@ static void log_incompatible_scev_values(struct bpf_verifier_env *env, const cha }static bool scev_value_compatible (struct bpf_verifier_env *env,struct bpf_func_state *st, -const struct scev_value *a,const struct scev_value *b) +const struct scev_value *a,const struct scev_value *b, +const struct linear_latch *latch) {const struct bpf_reg_state *ra, *rb;
@@ -2035,7 +2036,7 @@ static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_ } ra =scev_reg_for_read (env, st, a->ptr_reg); rb =scev_reg_for_read (env, st, b->ptr_reg); -if (ra && rb &&bpf_same_memory_origin (ra, rb)) +if (ra && rb &&bpf_same_memory_origin (ra, rb) && !latch->zext32 && !latch->jmp32)return true; incompatible:
@@ -2267,7 +2268,7 @@ static bool compute_max_iters(struct bpf_verifier_env *env, }return false; } -if (!scev_value_compatible (env, st, &initial_val, &bound_val)) +if (!scev_value_compatible (env, st, &initial_val, &bound_val, latch))return false; initial = initial_val.value;
Signature · 1 line
2.56.0
Eduard Zingerman
maintainerPATCH 2/2 selftests/bpf: pointer operands for 32-bit recurrences/latches
Two test cases checking that loop bounds are not inferred for the following program shapes:
32-bit latch | 32-bit recurrence
-------------------------+--------------------------
r6 = ... pointer ... | r6 = ... pointer ...
r7 = ... pointer ... | r7 = ... pointer ...
l: r6 += 1 | l: w6 += 1
... | ...
if w6 < w7 goto l | if r6 < r7 goto l--- .../selftests/bpf/progs/verifier_scev.c | 56 +++++++++++++++++++ 1 file changed, 56 insertions(+)
tools/testing/selftests/bpf/progs/verifier_scev.c +56 -0
@@ -2971,6 +2971,62 @@ __naked void ptr_stack_other_frame(void) " ::: __clobber_all); } +SEC("xdp") +__success +__log_level(2) +__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)") +__msg("loop header at 11, can't compute iterations count at 14") +__naked void ptr_map_value_jmp32 (void ) +{ + asmvolatile (" \ +*(u64 *)(r10 - 8) = 0; \ +r2 = r10; \ +r2 += -8; \ +r1 = %[map] ll; \ +call %[bpf_map_lookup_elem]; \ +if r0 == 0 goto 2f; \ +r6 = r0; \ +r7 = r6; \ +r7 += 4; \ +r9 = 0; \ +1:" LIMIT_ITERATIONS \ +" r6 += 1; \ +if w6 < w7 goto 1b; \ +2: r0 = 0; \ +exit; \ +" : + : __imm(bpf_map_lookup_elem), __imm_addr(map) + : __clobber_all); +} + +SEC("xdp") +__failure +__log_level(2) +__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)") +__msg("loop header at 11, can't compute iterations count at 14") +__naked void ptr_map_value_alu32 (void ) +{ + asmvolatile (" \ +*(u64 *)(r10 - 8) = 0; \ +r2 = r10; \ +r2 += -8; \ +r1 = %[map] ll; \ +call %[bpf_map_lookup_elem]; \ +if r0 == 0 goto 2f; \ +r6 = r0; \ +r7 = r6; \ +r7 += 4; \ +r9 = 0; \ +1:" LIMIT_ITERATIONS \ +" w6 += 1; \ +if r6 < r7 goto 1b; \ +2: r0 = 0; \ +exit; \ +" : + : __imm(bpf_map_lookup_elem), __imm_addr(map) + : __clobber_all); +} +/* Metadata and packet data have different origins. */ SEC ("xdp" ) __success
Signature · 1 line
2.56.0
[email protected]
AI reviewRe: [PATCH bpf-next 2/2] selftests/bpf: pointer operands for 32-bit recurrences/latches
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] bpf: 32-bit linear SCEVs on pointers not rejected outside latch check --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: 32-bit linear SCEVs on pointers not rejected outside latch check --
commit 674e2a043732fe1343763547170250d3fb165111
Author: Eduard Zingerman <[email protected]>
selftests/bpf: pointer operands for 32-bit recurrences/latches
This commit adds two selftests checking that loop bounds are not inferred when latch operands are pointers involved in a 32-bit comparison or a 32-bit recurrence.
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scev.c +0
-0@@ -2971,6 +2971,62 @@ __naked void ptr_stack_other_frame(void) " ::: __clobber_all); }
[ ... ]
Quoted 17 lines
tools/testing/selftests/bpf/progs/verifier_scev.c +17
-0+SEC("xdp") +__failure +__log_level(2) +__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)") +__msg("loop header at 11, can't compute iterations count at 14") +__naked void ptr_map_value_alu32 (void ) +{ + asm volatile (" \ + *(u64 *)(r10 - 8) = 0; \ + r2 = r10; \ + r2 += -8; \ + r1 = %[map] ll; \ + call %[bpf_map_lookup_elem]; \ + if r0 == 0 goto 2f; \ + r6 = r0; \ + r7 = r6; \ + r7 += 4; \
tools/testing/selftests/bpf/progs/verifier_scev.c __naked void ptr_stack_other_frame(void) · line 3028
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scev.c +10
-0+ r9 =0 ; \ +1:" LIMIT_ITERATIONS \ +" w6 += 1; \ + if r6 < r7 goto 1b; \ +2: r0 = 0; \ + exit; \ +" : + : __imm(bpf_map_lookup_elem), __imm_addr(map) + : __clobber_all); +}
[Severity: High]
In ptr_map_value_alu32(), w6 += 1 is applied directly to a pointer register while r6 is also the latch operand. The companion commit ("bpf: reject pointer operands for 32-bit recurrences/latches") rejects this via !latch->zext32 in scev_value_compatible():
kernel/bpf/scev.c:scev_value_compatible() {
...
ra = scev_reg_for_read(env, st, a->ptr_reg);
rb = scev_reg_for_read(env, st, b->ptr_reg);
if (ra && rb && bpf_same_memory_origin(ra, rb) && !latch->zext32 && !latch->jmp32)
return true;
}However, what happens when a pointer register has a 32-bit linear recurrence (such as r6 += 1; w6 = w6; or w6 = w6; w6 += 1;, which simplify() folds into (zext32 (linear r6 1))) while a separate scalar register controls the loop latch?
When allow_ptr_leaks is enabled (as in SEC("xdp") with CAP_BPF), check_alu_op() permits 32-bit BPF_MOV on a pointer without calling adjust_ptr_min_max_vals(), converting r6 into a SCALAR_VALUE holding the low 32 bits of the runtime pointer address.
Because scev_value_compatible() only checks the latch operands, bpf_compute_loop_iters() accepts r6 as widenable even when coefs.zext32 is true:
kernel/bpf/scev.c:bpf_compute_loop_iters() {
...
r_scev = header_env->reg2scev[r];
reg = scev_reg_for_linear(cur_func, r);
/* If SCEV for r is (linear <reg> <slope>) */
if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) {
...
}Subsequently, bpf_widen_scev_regs() widens the pointer offset using 32-bit linear_bounds(), and on the backedge bpf_clamp_scev_regs() computes 32-bit linear_bounds() from entry_reg (the loop-entry PTR_TO_MAP_VALUE with offset 0) and intersects that small offset range with the backedge register reg (now a SCALAR_VALUE holding the truncated 32-bit runtime kernel address):
kernel/bpf/scev.c:bpf_clamp_scev_regs() {
...
linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
...
}Can this corrupt the verifier's scalar bounds for r6 by clamping a runtime 32-bit kernel address to a small offset range like [0, 1], and should coefs.zext32 on pointer registers also be rejected in bpf_compute_loop_iters(), bpf_widen_scev_regs(), and bpf_clamp_scev_regs() (with corresponding selftests covering w6 = w6 and non-latch pointer recurrences)?
Quoted 4 lines
/* Metadata and packet data have different origins. */
SEC("xdp")
__success
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
kernel/bpf/scev.c static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_ · line 2040
Quoted 3 lines · Eduard Zingerman
kernel/bpf/scev.c +1
-1-if (ra && rb &&bpf_same_memory_origin (ra, rb)) +if (ra && rb &&bpf_same_memory_origin (ra, rb) && !latch->zext32 && !latch->jmp32)return true;
This covers the latch only. A 32-bit recurrence on a pointer that is not part of the latch is still widened and clamped, it seems:
r7 = map_value, r1 = 0
l: if r7 > 24 goto a
goto n
a: r0 = *(u8 *)(r7 + 0)
n: w7 = w7
w7 += 8
r1 += 1
if r1 != 4 goto lr7 at the header is (zext32 (linear r7 8)) and is_widenable_reg_type() is fine with map_value. 'w7 = w7' makes it a scalar. At the backedge bpf_clamp_scev_regs() takes linear_bounds() of the entry reg, which is the offset of map_value, and clamps that scalar to 0..24. Then 'if r7 > 24' is never taken, so 'a:' is verified with r7 == map_value only. At run time in the 2nd iteration r7 is the low 32 bits of the address + 8 and the prog reads from there.
Should bpf_compute_loop_iters() also have
(!coefs.zext32 || reg->type == SCALAR_VALUE)
next to is_widenable_reg_type() ?
pls follow up.
[email protected]
AI reviewThank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [Critical] bpf: 32-bit pointer recurrences not rejected in bpf_compute_loop_iters() - [High] bpf: missing…
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Critical] bpf: 32-bit pointer recurrences not rejected in bpf_compute_loop_iters()
- [High] bpf: missing pointer and type checks for linear SCEV widening and clamping --
commit ea9c83878323b0365b4124b8b3e8c881f6513530
Author: Eduard Zingerman <[email protected]>
bpf: reject pointer operands for 32-bit recurrences/latches
This commit updates scev_value_compatible() to reject pointer operands when the loop latch uses a 32-bit comparison or a 32-bit recurrence, preventing loop iteration counts from being inferred solely from pointer offsets.
Quoted 15 lines
kernel/bpf/scev.c +2
-1@@ -2024,7 +2024,8 @@ static void log_incompatible_scev_values(struct bpf_verifier_env *env, const cha }static bool scev_value_compatible (struct bpf_verifier_env *env,struct bpf_func_state *st, -const struct scev_value *a,const struct scev_value *b) +const struct scev_value *a,const struct scev_value *b, +const struct linear_latch *latch) {const struct bpf_reg_state *ra, *rb;
kernel/bpf/scev.c static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_ · line 2040
Quoted 6 lines
kernel/bpf/scev.c +1
-1@@ -2035,7 +2036,7 @@ static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_ } ra =scev_reg_for_read (env, st, a->ptr_reg); rb =scev_reg_for_read (env, st, b->ptr_reg); -if (ra && rb &&bpf_same_memory_origin (ra, rb)) +if (ra && rb &&bpf_same_memory_origin (ra, rb) && !latch->zext32 && !latch->jmp32)return true;
[Severity: Critical]
Checking !latch->zext32 && !latch->jmp32 in scev_value_compatible() only rejects 32-bit pointer recurrences when the pointer register is one of the latch comparison operands in compute_max_iters(). What happens if the loop iteration count is bounded by a separate scalar latch, while another live pointer register undergoes a 32-bit linear recurrence in the loop body (for example, w1 = w1; w1 += 8)?
In kernel/bpf/scev.c, is_simple_linear() matches both 64-bit and 32-bit linear recurrences:
static bool is_simple_linear(struct scev *scev, u32 id, struct linear_coefs *out)
{
u32 base, slope;
return is_linear_or_linear32(scev, id, &base, &slope, &out->zext32) &&
is_reg(scev, base, &out->base_reg) &&
is_imm(scev, slope, &out->slope) &&
out->slope <= S16_MAX &&
out->slope >= S16_MIN &&
out->slope != 0;
}Then bpf_compute_loop_iters() accepts the register for widening because is_widenable_reg_type(reg) allows pointer register types without checking coefs.zext32:
r_scev = header_env->reg2scev[r];
reg = scev_reg_for_linear(cur_func, r);
/* If SCEV for r is (linear <reg> <slope>) */
if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) {At loop entry, bpf_widen_scev_regs() calls linear_bounds() on the pointer register with coefs.zext32 set:
if (coefs->zext32) {
r32 = cnum32_from_cnum64(r64);
r64 = cnum64_zext32(r32);This truncates and zero-extends the pointer's tracked offset at 32 bits while keeping reg->type as a pointer (for example, turning a negative stack pointer offset such as [-16, -8] into [0xfffffff0, 0xfffffff8]).
Furthermore, when env->allow_ptr_leaks is enabled, 32-bit operations in the loop body such as w1 = w1; w1 += 8 convert r1 into a scalar holding the truncated 32-bit runtime address. When the backedge reaches the loop header, bpf_clamp_scev_regs() computes linear_bounds() from entry_reg's pointer offset and intersects that offset range with the backedge scalar in reg:
linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
if (cnum64_is_empty(bounds.r64)) {
verifier_bug(env, "scev clamp produced empty range for r%d", r);
return -EFAULT;
}Can this either clamp the runtime-address scalar to the small pointer offset range (allowing out-of-bounds memory access if the scalar is subsequently added to a pointer) or produce an empty intersection and trigger verifier_bug() if the scalar was narrowed in the loop body?
kernel/bpf/scev.c static bool compute_max_iters(struct bpf_verifier_env *env, · line 2274
Quoted 11 lines
kernel/bpf/scev.c +1
-1incompatible:@@ -2267,7 +2268,7 @@ static bool compute_max_iters(struct bpf_verifier_env *env, }return false; } -if (!scev_value_compatible (env, st, &initial_val, &bound_val)) +if (!scev_value_compatible (env, st, &initial_val, &bound_val, latch))return false; initial = initial_val.value;
[Severity: High]
Related to the issue above, can a pointer register at loop entry also be degraded to a scalar in the loop body even when coefs.zext32 is false, causing bpf_clamp_scev_regs() to intersect a backedge scalar range with loop-entry pointer offset bounds?
In kernel/bpf/scev.c:transfer(), a 64-bit native-endian byte swap (such as r1 = le64 r1 on a little-endian host) sets need_bswap to false and op to 0, treating the instruction as an identity operation in the expression graph:
need_bswap = class == BPF_ALU64 || ((x_or_k == BPF_TO_LE) != little_endian);
switch (insn->imm) {
case 16: op = need_bswap ? BSWAP16 : ZEXT16; break;
case 32: op = need_bswap ? BSWAP32 : ZEXT32; break;
case 64: op = need_bswap ? BSWAP64 : 0; break;
default:
goto mark_dst_unknown;
}
id = reg2expr[dst];
if (op)
id = expr1(scev, op, reg2expr[dst]);If a loop body executes r1 = le64 r1; r1 += 8 on a register that holds a pointer at loop entry, transfer() produces a 64-bit linear recurrence with coefs.zext32 == false, while check_alu_op() degrades r1 to an unbounded scalar value.
When bpf_clamp_scev_regs() runs on the backedge, it does not check whether entry_reg and reg have matching register types before clamping reg to the bounds computed from entry_reg:
entry_reg = scev_reg_for_linear(entry_st, r); reg = scev_reg_for_linear(cur_func_state, r); if (!entry_reg || !reg || entry_reg->type == NOT_INIT || reg->type == NOT_INIT || is_unbound_scev_reg(env, entry_st, r)) continue; linear_bounds(entry_reg, max_header_count, &coefs, &bounds); bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
Should bpf_compute_loop_iters() reject coefs.zext32 on non-scalar registers, and should transfer() or bpf_clamp_scev_regs() also ensure that a pointer register at loop entry is not widened or clamped when degraded to a scalar in the loop body?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
[email protected]
AI reviewTL;DR: - Pointer with 32-bit recurrence still gets widened/clamped, so the verifier may accept an unsafe scalar-address load - Commit message example "w1 += 8" on a pointer can't pass verification
Quoted 1 line
bpf: reject pointer operands for 32-bit recurrences/latches
TL;DR:
- Pointer with 32-bit recurrence still gets widened/clamped, so the verifier may accept an unsafe scalar-address load
- Commit message example "w1 += 8" on a pointer can't pass verification
Quoted 4 lines
kernel/bpf/scev.c +0
-0
[ ... ]
kernel/bpf/scev.c static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_ · line 2042
Quoted 9 lines
kernel/bpf/scev.c +1
-1@@ -2035,7 +2036,7 @@ static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_ } ra =scev_reg_for_read (env, st, a->ptr_reg); rb =scev_reg_for_read (env, st, b->ptr_reg); -if (ra && rb &&bpf_same_memory_origin (ra, rb)) +if (ra && rb &&bpf_same_memory_origin (ra, rb) && !latch->zext32 && !latch->jmp32)return true; incompatible:
[ ... ]
Does this leave the 32-bit recurrence case open for a pointer register that is not one of the latch operands?
bpf_compute_loop_iters() accepts a register whose SCEV is a simple linear form as long as is_widenable_reg_type() allows its type:
reg = scev_reg_for_linear(cur_func, r);
/* If SCEV for r is (linear <reg> <slope>) */
if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) {is_simple_linear() accepts (zext32 (linear rX imm)), and is_widenable_reg_type() accepts PTR_TO_MAP_VALUE and similar types. So a pointer with a 32-bit recurrence is still reported as bounded by bpf_compute_loop_iters(), and bpf_widen_scev_regs() and bpf_clamp_scev_regs() then apply linear_bounds() to it. The new check only looks at the latch operands (initial/bound), not at the recurrence register.
Here is an example (needs CAP_BPF and CAP_PERFMON, i.e. allow_ptr_leaks and allow_uninit_stack). r1 is a map value pointer at offset 0 and value_size is at least 73:
r0 = 0
l: if r1 s> 72 goto C // exit; latch fails: ptr vs scalar
w1 = w1 // verifier: ptr -> unknown scalar
w1 += 8 // SCEV: r1 = (zext32 (linear r1 8)) r0 += 1
if r0 < 10 goto l // scalar latch, 10 header executions
exit
C: r3 = *(u8 *)(r1 + 0)
exit
On the first pass, after bpf_widen_scev_regs(), r1 is a PTR_TO_MAP_VALUE with offsets [0,72]. is_branch_taken() returns -1 for pointer vs 72, so C is checked with r1 as a pointer, which is valid.
On the backedge, handle_loop_entry_exit() calls maybe_clamp_scev_regs() and bpf_clamp_scev_regs(). The latter only checks for NOT_INIT, not that the register types match. It computes linear_bounds(entry_reg, ...) from the entry pointer's offsets and intersects the result with the now-scalar r1, so r1 becomes a scalar in [0,72] with step 8.
On the second pass, 'if r1 s> 72' is never taken, so C is never checked with r1 as a scalar. The next backedge prunes.
At runtime, r1 on the second iteration is zext32(lo32(map_addr) + 8). That value is almost always s> 72, so execution jumps to C and loads from a scalar address. The clamp is unsound here because the register's value depends on the runtime base address and not only on the tracked offset, which is the same reasoning the commit message gives for the latch operands.
Should the widenability check in bpf_compute_loop_iters() also refuse zext32 coefficients for non-SCALAR_VALUE registers, or should widening and clamping be refused when the entry and current register types differ?
Is this case meant to be covered by this patch? None of the later commits in this series appear to address it.
Also, quoting the commit message:
Quoted 8 lines
Avoid inferring loop bounds for the following program shapes:
32-bit latch | 32-bit recurrence
-------------------------+--------------------------
r1 = ... pointer ... | r1 = ... pointer ...
r2 = ... pointer ... | r2 = ... pointer ...
l: r1 += 8 | l: w1 += 8
... | ...
if w1 < w2 goto l | if r1 < r2 goto l
This isn't a bug, but the 32-bit recurrence example ("w1 += 8" on the pointer r1) cannot pass verification as written, because adjust_ptr_min_max_vals() rejects it with "32-bit pointer arithmetic prohibited".
The reachable form uses 'w1 = w1' (allowed under allow_ptr_leaks) followed by a scalar 'w1 += 8'. Could the example be changed to show that form?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/39518152729