bpf: Recognize special arithmetic shift in the verifier
Subsystems (4)
v4 cover bpf: Recognize special arithmetic shift in the verifier
v3: https://lore.kernel.org/all/[email protected]/
Changes in v3->v4:
- Fork verifier state while processing BPF_OR when src_reg has [-1,0] range and 2nd operand is a constant. This is to detect the following pattern:
i32 X > -1 ? C1 : -1 --> (X >>s 31) | C1
- Add selftests for above.
- Remove __description("s>>=63") (Eduard in another patchset)
v2: https://lore.kernel.org/bpf/[email protected]/
Changes in v2->v3:
- fork verifier state while processing BPF_AND when src_reg has [-1,0] range and 2nd operand is a constant.
v1->v2:
Use __mark_reg32_known() or __mark_reg_known() for zero too. Add comment to selftest.
v1:
https://lore.kernel.org/bpf/[email protected]/
Alexei Starovoitov (2):
bpf: Recognize special arithmetic shift in the verifier selftests/bpf: Add tests for s>>=31 and s>>=63
kernel/bpf/verifier.c | 39 +++++++++ .../selftests/bpf/progs/verifier_subreg.c | 85 +++++++++++++++++++ 2 files changed, 124 insertions(+)
base-commit: 5714ca8cba5ed736f3733663c446cbee63a10a64
Signature · 1 line
2.47.3
PATCH v4 1/2 bpf: Recognize special arithmetic shift in the verifier
From: Alexei Starovoitov <[email protected]>
cilium bpf_wiregard.bpf.c when compiled with -O1 fails to load with the following verifier log:
192: (79) r2 = *(u64 *)(r10 -304) ; R2=pkt(r=40) R10=fp0 fp-304=pkt(r=40)
...
227: (85) call bpf_skb_store_bytes#9 ; R0=scalar()
228: (bc) w2 = w0 ; R0=scalar() R2=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) 229: (c4) w2 s>>= 31 ; R2=scalar(smin=0,smax=umax=0xffffffff,smin32=-1,smax32=0,var_off=(0x0; 0xffffffff)) 230: (54) w2 &= -134 ; R2=scalar(smin=0,smax=umax=umax32=0xffffff7a,smax32=0x7fffff7a,var_off=(0x0; 0xffffff7a))
...
232: (66) if w2 s> 0xffffffff goto pc+125 ; R2=scalar(smin=umin=umin32=0x80000000,smax=umax=umax32=0xffffff7a,smax32=-134,var_off=(0x80000000; 0x7fffff7a))
...
238: (79) r4 = *(u64 *)(r10 -304) ; R4=scalar() R10=fp0 fp-304=scalar()
239: (56) if w2 != 0xffffff78 goto pc+210 ; R2=0xffffff78 // -136
...
258: (71) r1 = *(u8 *)(r4 +0)
R4 invalid mem access 'scalar'
The error might confuse most bpf authors, since fp-304 slot had 'pkt' pointer at insn 192 and became 'scalar' at 238. That happened because bpf_skb_store_bytes() clears all packet pointers including those in the stack. On the first glance it might look like a bug in the source code, since ctx->data pointer should have been reloaded after the call to bpf_skb_store_bytes().
The relevant part of cilium source code looks like this:
// bpf/lib/nodeport.h
int dsr_set_ipip6()
{
if (ctx_adjust_hroom(...))
return DROP_INVALID; // -134
if (ctx_store_bytes(...))
return DROP_WRITE_ERROR; // -141
return 0;
}bool dsr_fail_needs_reply(int code)
{
if (code == DROP_FRAG_NEEDED) // -136
return true;
return false;
}tail_nodeport_ipv6_dsr()
{
ret = dsr_set_ipip6(...);
if (!IS_ERR(ret)) {
...
} else {
if (dsr_fail_needs_reply(ret))
return dsr_reply_icmp6(...);
}
}The code doesn't have arithmetic shift by 31 and it reloads ctx->data every time it needs to access it. So it's not a bug in the source code.
The reason is DAGCombiner::foldSelectCCToShiftAnd() LLVM transformation:
// If this is a select where the false operand is zero and the compare is a // check of the sign bit, see if we can perform the "gzip trick":
// select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A
// select_cc setgt X, 0, A, 0 -> and (not (sra X, size(X)-1)), A
The conditional branch in dsr_set_ipip6() and its return values are optimized into BPF_ARSH plus BPF_AND:
227: (85) call bpf_skb_store_bytes#9
228: (bc) w2 = w0
229: (c4) w2 s>>= 31 ; R2=scalar(smin=0,smax=umax=0xffffffff,smin32=-1,smax32=0,var_off=(0x0; 0xffffffff))
230: (54) w2 &= -134 ; R2=scalar(smin=0,smax=umax=umax32=0xffffff7a,smax32=0x7fffff7a,var_off=(0x0; 0xffffff7a))
after insn 230 the register w2 can only be 0 or -134, but the verifier approximates it, since there is no way to represent two scalars in bpf_reg_state.
After fallthough at insn 232 the w2 can only be -134, hence the branch at insn
239: (56) if w2 != -136 goto pc+210
should be always taken, and trapping insn 258 should never execute. LLVM generated correct code, but the verifier follows impossible path and rejects valid program. To fix this issue recognize this special LLVM optimization and fork the verifier state. So after insn 229: (c4) w2 s>>= 31
the verifier has two states to explore:
one with w2 = 0 and another with w2 = 0xffffffff
which makes the verifier accept bpf_wiregard.c
A similar pattern exists were OR operation is used in place of the AND operation, the verifier detects that pattern as well by forking the state before the OR operation with a scalar in range [-1,0].
Note there are 20+ such patterns in bpf_wiregard.o compiled with -O1 and -O2, but they're rarely seen in other production bpf programs, so push_stack() approach is not a concern.
--- kernel/bpf/verifier.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)
kernel/bpf/verifier.c +39 -0
@@ -15495,6 +15495,35 @@ 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_verifier_state *branch; +struct bpf_reg_state *regs; +bool alu32; + +if (dst_reg->smin_value ==-1 && dst_reg->smax_value ==0 ) + alu32 = false; +else if (dst_reg->s32_min_value ==-1 && dst_reg->s32_max_value ==0 ) + alu32 = true; +else +return 0 ; + + branch =push_stack (env, env->insn_idx +1 , env->insn_idx, false); +if (IS_ERR (branch)) +return PTR_ERR (branch); + + regs = branch->frame[branch->curframe]->regs; +if (alu32) { +__mark_reg32_known (®s[insn->dst_reg],0 ); +__mark_reg32_known (dst_reg,-1ull ); + }else { +__mark_reg_known (®s[insn->dst_reg],0 ); +__mark_reg_known (dst_reg,-1ull ); + } +return 0 ; +} +/* WARNING: This function does calculations on 64-bit values, but the actual * execution may occur on 32-bit values. Therefore, things like bitshifts * need extra checks in the 32-bit case.
@@ -15557,11 +15586,21 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,scalar_min_max_mul (dst_reg, &src_reg);break ;case BPF_AND : +if (tnum_is_const (src_reg.var_off)) { + ret =maybe_fork_scalars (env, insn, dst_reg); +if (ret) +return ret; + } dst_reg->var_off =tnum_and (dst_reg->var_off, src_reg.var_off);scalar32_min_max_and (dst_reg, &src_reg);scalar_min_max_and (dst_reg, &src_reg);break ;case BPF_OR : +if (tnum_is_const (src_reg.var_off)) { + ret =maybe_fork_scalars (env, insn, dst_reg); +if (ret) +return ret; + } dst_reg->var_off =tnum_or (dst_reg->var_off, src_reg.var_off);scalar32_min_max_or (dst_reg, &src_reg);scalar_min_max_or (dst_reg, &src_reg);
Signature · 1 line
2.47.3
PATCH v4 2/2 selftests/bpf: Add tests for s>>=31 and s>>=63
In reply to Puranjay MohanFrom: Alexei Starovoitov <[email protected]>
Add tests for special arithmetic shift right.
--- .../selftests/bpf/progs/verifier_subreg.c | 85 +++++++++++++++++++ 1 file changed, 85 insertions(+)
tools/testing/selftests/bpf/progs/verifier_subreg.c +85 -0
@@ -738,4 +738,89 @@ __naked void ldx_w_zero_extend_check(void) : __clobber_all); } +SEC("socket") +__success __success_unpriv __retval(0) +__naked void arsh_31_and(void) +{ +/* Below is what LLVM generates in cilium's bpf_wiregard.o */ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w2 = w0; \ +w2 s>>= 31; \ +w2 &= -134; /* w2 becomes 0 or -134 */ \ +if w2 s> -1 goto +2; \ +/* Branch always taken because w2 = -134 */ \ +if w2 != -136 goto +1; \ +w0 /= 0; \ +w0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__success __success_unpriv __retval(0) +__naked void arsh_63_and(void) +{ +/* Copy of arsh_31 with s/w/r/ */ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r2 = r0; \ +r2 <<= 32; \ +r2 s>>= 63; \ +r2 &= -134; \ +if r2 s> -1 goto +2; \ +/* Branch always taken because w2 = -134 */ \ +if r2 != -136 goto +1; \ +r0 /= 0; \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__success __success_unpriv __retval(0) +__naked void arsh_31_or(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w2 = w0; \ +w2 s>>= 31; \ +w2 |= 134; /* w2 becomes -1 or 134 */ \ +if w2 s> -1 goto +2; \ +/* Branch always taken because w2 = -1 */ \ +if w2 == -1 goto +1; \ +w0 /= 0; \ +w0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") +__success __success_unpriv __retval(0) +__naked void arsh_63_or(void) +{ +/* Copy of arsh_31 with s/w/r/ */ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +r2 = r0; \ +r2 <<= 32; \ +r2 s>>= 63; \ +r2 |= 134; /* r2 becomes -1 or 134 */ \ +if r2 s> -1 goto +2; \ +/* Branch always taken because w2 = -1 */ \ +if r2 == -1 goto +1; \ +r0 /= 0; \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.3
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Mon, 12 Jan 2026 12:13:56 -0800 you wrote:
v3: https://lore.kernel.org/all/[email protected]/
Changes inv3->v4:
- Fork verifier state while processingBPF_ORwhensrc_reghas [-1,0] range and 2nd operand is a constant. This is to detect the following pattern:i32 X > -1 ? C1 : -1 --> (X >>s 31) | C1- Add selftests for above.
- Remove__description("s>>=63")(Eduard in another patchset)[...]
Here is the summary with links:
- [bpf-next,v4,1/2] bpf: Recognize special arithmetic shift in the verifier
https://git.kernel.org/bpf/bpf-next/c/bffacdb80b93 - [bpf-next,v4,2/2] selftests/bpf: Add tests for s>>=31 and s>>=63 https://git.kernel.org/bpf/bpf-next/c/9160335317cb
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html