bpf: Skip bounds adjustment for conditional jumps on same register
Subsystems (4)
cover bpf: Skip bounds adjustment for conditional jumps on same register
This small patchset is about avoid verifier bug warning when conditional
jumps on same register when the register holds a scalar with range.
---
KaFai Wan (2):
bpf: Skip bounds adjustment for conditional jumps on same register selftests/bpf: Add test for conditional jumps on same register
kernel/bpf/verifier.c | 4 ++++ .../selftests/bpf/progs/verifier_bounds.c | 17 +++++++++++++++++ 2 files changed, 21 insertions(+)
Signature · 1 line
2.43.0
PATCH 1/2 bpf: Skip bounds adjustment for conditional jumps on same register
When conditional jumps are performed on the same register (e.g., r0 <= r0, r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier incorrectly attempts to adjust the register's min/max bounds. This leads to invalid range bounds and triggers a BUG warning:
verifier bug: REG INVARIANTS VIOLATION (true_reg1): range bounds violation u64=[0x1, 0x0] s64=[0x1, 0x0] u32=[0x1, 0x0] s32=[0x1, 0x0] var_off=(0x0, 0x0)
WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0 ...
The issue occurs in reg_set_min_max() function where bounds adjustment logic is applied even when both registers being compared are the same. Comparing a register with itself should not change its bounds since the comparison result is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).
Fix this by adding an early return in reg_set_min_max() when false_reg1 and false_reg2 point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.
--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)
kernel/bpf/verifier.c +4 -0
@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (false_reg1->type !=SCALAR_VALUE || false_reg2->type !=SCALAR_VALUE )return 0 ; +/* If conditional jumps on the same register, skip the adjustment */ +if (false_reg1 == false_reg2) +return 0 ; +/* fallthrough (FALSE) branch */ regs_refine_cond_op (false_reg1, false_reg2,rev_opcode (opcode), is_jmp32);reg_bounds_sync (false_reg1);
Signature · 1 line
2.43.0
Yonghong Song
reviewerQuoted 42 lines · KaFai Wan
When conditional jumps are performed on the same register (e.g., r0 <= r0, r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier incorrectly attempts to adjust the register's min/max bounds. This leads to invalid range bounds and triggers a BUG warning:
verifier bug: REG INVARIANTS VIOLATION (
true_reg1): range bounds violation u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0] var_off=(0x0,0x0)WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0 ...The issue occurs in
reg_set_min_max()function where bounds adjustment logic is applied even when both registers being compared are the same. Comparing a register with itself should not change its bounds since the comparison result is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).Fix this by adding an early return in
reg_set_min_max()whenfalse_reg1andfalse_reg2point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.Reported-by Kaiyan Mei <[email protected]>Reported-by Yinhao Hu <[email protected]>Fixes 0df1a55afa83 ("bpf: Warn on internal verifier errors")Signed-off-by KaFai Wan <[email protected]>--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static int reg_set_min_max(struct bpf_verifier_env *env, · line 16434
Quoted 6 lines
kernel/bpf/verifier.c +3
-0@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (false_reg1->type !=SCALAR_VALUE || false_reg2->type !=SCALAR_VALUE )return 0 ; +/* If conditional jumps on the same register, skip the adjustment */ +if (false_reg1 == false_reg2) +return 0 ;
Your change looks good. But this is a special case and it should not happen for any compiler generated code. So could you investigate why regs_refine_cond_op() does not work? Since false_reg1 and false_reg2 is the same, so register refinement should keep the same. Probably some minor change in regs_refine_cond_op(...) should work?
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+/* fallthrough (FALSE) branch */ regs_refine_cond_op (false_reg1, false_reg2,rev_opcode (opcode), is_jmp32);reg_bounds_sync (false_reg1);
Eduard Zingerman
maintainerQuoted 47 lines · Yonghong Song
Quoted 45 lines · KaFai Wan
When conditional jumps are performed on the same register (e.g., r0 <= r0, r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier incorrectly attempts to adjust the register's min/max bounds. This leads to invalid range bounds and triggers a BUG warning:
verifier bug: REG INVARIANTS VIOLATION (
true_reg1): range bounds violation u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0] var_off=(0x0,0x0)WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0 ...The issue occurs in
reg_set_min_max()function where bounds adjustment logic is applied even when both registers being compared are the same. Comparing a register with itself should not change its bounds since the comparison result is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).Fix this by adding an early return in
reg_set_min_max()whenfalse_reg1andfalse_reg2point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.Reported-by Kaiyan Mei <[email protected]>Reported-by Yinhao Hu <[email protected]>Fixes 0df1a55afa83 ("bpf: Warn on internal verifier errors")Signed-off-by KaFai Wan <[email protected]>--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)kernel/bpf/verifier.c +0
-0@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (false_reg1->type !=SCALAR_VALUE || false_reg2->type !=SCALAR_VALUE )return 0 ;
Quoted 14 lines
kernel/bpf/verifier.c static int reg_set_min_max(struct bpf_verifier_env *env, · line 16434
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+/* If conditional jumps on the same register, skip the adjustment */ +if (false_reg1 == false_reg2) +return 0 ;Your change looks good. But this is a special case and it should not happen for any compiler generated code. So could you investigate why
regs_refine_cond_op()does not work? Sincefalse_reg1andfalse_reg2is the same, so register refinement should keep the same. Probably some minor change inregs_refine_cond_op(...)should work?Quoted 4 lines
kernel/bpf/verifier.c +1
-0+/* fallthrough (FALSE) branch */ regs_refine_cond_op (false_reg1, false_reg2,rev_opcode (opcode), is_jmp32);reg_bounds_sync (false_reg1);
I think regs_refine_cond_op() is not written in a way to handle same registers passed as reg1 and reg2. E.g. in this particular case the condition is reformulated as "r0 < r0", and then the following branch is taken:
static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
u8 opcode, bool is_jmp32)
{
...
case BPF_JLT: // condition is rephrased as r0 < r0
if (is_jmp32) {
...
} else {
reg1->umax_value = min(reg1->umax_value, reg2->umax_value - 1);
reg2->umin_value = max(reg1->umin_value + 1, reg2->umin_value);
}
break; ...
}
Note that intent is to adjust umax of the LHS (reg1) register and umin of the RHS (reg2) register. But here it ends up adjusting the same register.
(a) before refinement: u64=[0x0, 0x80000000] s64=[0x0, 0x80000000] u32=[0x0, 0x80000000] s32=[0x80000000, 0x0]
(b) after refinement: u64=[0x1, 0x7fffffff] s64=[0x0, 0x80000000] u32=[0x0, 0x80000000] s32=[0x80000000, 0x0]
(c) after sync : u64=[0x1, 0x0] s64=[0x1, 0x0] u32=[0x1, 0x0] s32=[0x1, 0x0]
At (b) the u64 range translated to s32 is > 0, while s32 range is <= 0, hence the invariant violation.
I think it's better to move the reg1 == reg2 check inside regs_refine_cond_op(), or to handle this case in is_branch_taken().
Quoted 91 lines · Eduard Zingerman
Quoted 47 lines · Yonghong Song
Quoted 45 lines · KaFai Wan
When conditional jumps are performed on the same register (e.g., r0 <= r0, r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier incorrectly attempts to adjust the register's min/max bounds. This leads to invalid range bounds and triggers a BUG warning:
verifier bug: REG INVARIANTS VIOLATION (
true_reg1): range bounds violation u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0] var_off=(0x0,0x0)WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0 ...The issue occurs in
reg_set_min_max()function where bounds adjustment logic is applied even when both registers being compared are the same. Comparing a register with itself should not change its bounds since the comparison result is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).Fix this by adding an early return in
reg_set_min_max()whenfalse_reg1andfalse_reg2point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.Reported-by Kaiyan Mei <[email protected]>Reported-by Yinhao Hu <[email protected]>Fixes 0df1a55afa83 ("bpf: Warn on internal verifier errors")Signed-off-by KaFai Wan <[email protected]>--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)kernel/bpf/verifier.c +0
-0@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (false_reg1->type !=SCALAR_VALUE || false_reg2->type !=SCALAR_VALUE )return 0 ;Quoted 14 lines
kernel/bpf/verifier.c static int reg_set_min_max(struct bpf_verifier_env *env, · line 16434
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+/* If conditional jumps on the same register, skip the adjustment */ +if (false_reg1 == false_reg2) +return 0 ;Your change looks good. But this is a special case and it should not happen for any compiler generated code. So could you investigate why
regs_refine_cond_op()does not work? Sincefalse_reg1andfalse_reg2is the same, so register refinement should keep the same. Probably some minor change inregs_refine_cond_op(...)should work?Quoted 4 lines
kernel/bpf/verifier.c +1
-0+/* fallthrough (FALSE) branch */ regs_refine_cond_op (false_reg1, false_reg2,rev_opcode (opcode), is_jmp32);reg_bounds_sync (false_reg1);I think
regs_refine_cond_op()is not written in a way to handle same registers passed as reg1 and reg2. E.g. in this particular case the condition is reformulated as "r0 < r0", and then the following branch is taken:static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32) { ... case BPF_JLT: // condition is rephrased as r0 < r0 if (is_jmp32) { ... } else { reg1->umax_value = min(reg1->umax_value, reg2->umax_value - 1); reg2->umin_value = max(reg1->umin_value + 1, reg2->umin_value); } break; ... }Note that intent is to adjust umax of the LHS (reg1) register and umin of the RHS (reg2) register. But here it ends up adjusting the same register.
(a) before refinement: u64=[0x0,
0x80000000] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(b) after refinement: u64=[0x1,0x7fffffff] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(c) after sync : u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0]
Quoted 5 lines
At (b) the u64 range translated to s32 is > 0, while s32 range is <= 0, hence the invariant violation.
I think it's better to move the reg1 == reg2 check inside
regs_refine_cond_op(), or to handle this case inis_branch_taken().
hmm. bu then regs_refine_cond_op() will skip it, yet reg_set_min_max() will still be doing pointless work with reg_bounds_sync() and sanity check. The current patch makes more sense to me.
Eduard Zingerman
maintainerQuoted 95 lines · Alexei Starovoitov
Quoted 94 lines · Eduard Zingerman
Quoted 47 lines · Yonghong Song
Quoted 45 lines · KaFai Wan
When conditional jumps are performed on the same register (e.g., r0 <= r0, r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier incorrectly attempts to adjust the register's min/max bounds. This leads to invalid range bounds and triggers a BUG warning:
verifier bug: REG INVARIANTS VIOLATION (
true_reg1): range bounds violation u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0] var_off=(0x0,0x0)WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0 ...The issue occurs in
reg_set_min_max()function where bounds adjustment logic is applied even when both registers being compared are the same. Comparing a register with itself should not change its bounds since the comparison result is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).Fix this by adding an early return in
reg_set_min_max()whenfalse_reg1andfalse_reg2point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.Reported-by Kaiyan Mei <[email protected]>Reported-by Yinhao Hu <[email protected]>Fixes 0df1a55afa83 ("bpf: Warn on internal verifier errors")Signed-off-by KaFai Wan <[email protected]>--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)kernel/bpf/verifier.c +0
-0@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (false_reg1->type !=SCALAR_VALUE || false_reg2->type !=SCALAR_VALUE )return 0 ;Quoted 14 lines
kernel/bpf/verifier.c static int reg_set_min_max(struct bpf_verifier_env *env, · line 16434
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+/* If conditional jumps on the same register, skip the adjustment */ +if (false_reg1 == false_reg2) +return 0 ;Your change looks good. But this is a special case and it should not happen for any compiler generated code. So could you investigate why
regs_refine_cond_op()does not work? Sincefalse_reg1andfalse_reg2is the same, so register refinement should keep the same. Probably some minor change inregs_refine_cond_op(...)should work?Quoted 4 lines
kernel/bpf/verifier.c +1
-0+/* fallthrough (FALSE) branch */ regs_refine_cond_op (false_reg1, false_reg2,rev_opcode (opcode), is_jmp32);reg_bounds_sync (false_reg1);I think
regs_refine_cond_op()is not written in a way to handle same registers passed as reg1 and reg2. E.g. in this particular case the condition is reformulated as "r0 < r0", and then the following branch is taken:static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32) { ... case BPF_JLT: // condition is rephrased as r0 < r0 if (is_jmp32) { ... } else { reg1->umax_value = min(reg1->umax_value, reg2->umax_value - 1); reg2->umin_value = max(reg1->umin_value + 1, reg2->umin_value); } break; ... }Note that intent is to adjust umax of the LHS (reg1) register and umin of the RHS (reg2) register. But here it ends up adjusting the same register.
(a) before refinement: u64=[0x0,
0x80000000] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(b) after refinement: u64=[0x1,0x7fffffff] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(c) after sync : u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0]At (b) the u64 range translated to s32 is > 0, while s32 range is <= 0, hence the invariant violation.
Quoted 6 lines
Quoted 2 lines
I think it's better to move the reg1 == reg2 check inside
regs_refine_cond_op(), or to handle this case inis_branch_taken().hmm. bu then
regs_refine_cond_op()will skip it, yetreg_set_min_max()will still be doing pointless work withreg_bounds_sync()and sanity check. The current patch makes more sense to me.
Well, if we want to avoid useless work, we need something like:
@@ -16173,6 +16173,25 @@ static int is_pkt_ptr_branch_taken(struct bpf_reg_state *dst_reg,
static int is_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
u8 opcode, bool is_jmp32)
{
+ if (reg1 == reg2) {
+ switch (opcode) {
+ case BPF_JGE:
+ case BPF_JLE:
+ case BPF_JSGE:
+ case BPF_JSLE:
+ case BPF_JEQ:
+ case BPF_JSET:
+ return 1;
+ case BPF_JGT:
+ case BPF_JLT:
+ case BPF_JSGT:
+ case BPF_JSLT:
+ case BPF_JNE:+ return 0;
+ default:
+ return -1;
+ }
+ }
But that's too much code for an artificial case.
Idk, either way is fine with me.
Quoted 130 lines · Eduard Zingerman
Quoted 95 lines · Alexei Starovoitov
Quoted 94 lines · Eduard Zingerman
Quoted 47 lines · Yonghong Song
Quoted 45 lines · KaFai Wan
When conditional jumps are performed on the same register (e.g., r0 <= r0, r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier incorrectly attempts to adjust the register's min/max bounds. This leads to invalid range bounds and triggers a BUG warning:
verifier bug: REG INVARIANTS VIOLATION (
true_reg1): range bounds violation u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0] var_off=(0x0,0x0)WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0 ...The issue occurs in
reg_set_min_max()function where bounds adjustment logic is applied even when both registers being compared are the same. Comparing a register with itself should not change its bounds since the comparison result is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).Fix this by adding an early return in
reg_set_min_max()whenfalse_reg1andfalse_reg2point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.Reported-by Kaiyan Mei <[email protected]>Reported-by Yinhao Hu <[email protected]>Fixes 0df1a55afa83 ("bpf: Warn on internal verifier errors")Signed-off-by KaFai Wan <[email protected]>--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)kernel/bpf/verifier.c +0
-0@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (false_reg1->type !=SCALAR_VALUE || false_reg2->type !=SCALAR_VALUE )return 0 ;Quoted 14 lines
kernel/bpf/verifier.c static int reg_set_min_max(struct bpf_verifier_env *env, · line 16434
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+/* If conditional jumps on the same register, skip the adjustment */ +if (false_reg1 == false_reg2) +return 0 ;Your change looks good. But this is a special case and it should not happen for any compiler generated code. So could you investigate why
regs_refine_cond_op()does not work? Sincefalse_reg1andfalse_reg2is the same, so register refinement should keep the same. Probably some minor change inregs_refine_cond_op(...)should work?Quoted 4 lines
kernel/bpf/verifier.c +1
-0+/* fallthrough (FALSE) branch */ regs_refine_cond_op (false_reg1, false_reg2,rev_opcode (opcode), is_jmp32);reg_bounds_sync (false_reg1);I think
regs_refine_cond_op()is not written in a way to handle same registers passed as reg1 and reg2. E.g. in this particular case the condition is reformulated as "r0 < r0", and then the following branch is taken:static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32) { ... case BPF_JLT: // condition is rephrased as r0 < r0 if (is_jmp32) { ... } else { reg1->umax_value = min(reg1->umax_value, reg2->umax_value - 1); reg2->umin_value = max(reg1->umin_value + 1, reg2->umin_value); } break; ... }Note that intent is to adjust umax of the LHS (reg1) register and umin of the RHS (reg2) register. But here it ends up adjusting the same register.
(a) before refinement: u64=[0x0,
0x80000000] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(b) after refinement: u64=[0x1,0x7fffffff] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(c) after sync : u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0]At (b) the u64 range translated to s32 is > 0, while s32 range is <= 0, hence the invariant violation.
Quoted 6 lines
Quoted 2 lines
I think it's better to move the reg1 == reg2 check inside
regs_refine_cond_op(), or to handle this case inis_branch_taken().hmm. bu then
regs_refine_cond_op()will skip it, yetreg_set_min_max()will still be doing pointless work withreg_bounds_sync()and sanity check. The current patch makes more sense to me.Well, if we want to avoid useless work, we need something like:
(quoted diff) +19
-0@@ -16173,6 +16173,25 @@ static int is_pkt_ptr_branch_taken(struct bpf_reg_state *dst_reg, static int is_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32) { + if (reg1 == reg2) { + switch (opcode) { + case BPF_JGE: + case BPF_JLE: + case BPF_JSGE: + case BPF_JSLE: + case BPF_JEQ: + case BPF_JSET: + return 1; + case BPF_JGT: + case BPF_JLT: + case BPF_JSGT: + case BPF_JSLT: + case BPF_JNE: + return 0; + default: + return -1; + } + }
Quoted 2 lines
But that's too much code for an artificial case.
Idk, either way is fine with me.
Makes sense to me.
Quoted 99 lines · Eduard Zingerman
Quoted 98 lines · Alexei Starovoitov
Quoted 97 lines · Eduard Zingerman
Quoted 63 lines · Yonghong Song
Quoted 61 lines · KaFai Wan
When conditional jumps are performed on the same register (e.g., r0 <= r0,
r0 > r0, r0 < r0) where the register holds a scalar with range, the verifier
incorrectly attempts to adjust the register's min/max bounds. This leads to
invalid range bounds and triggers a BUG warning:verifier bug: REG INVARIANTS VIOLATION (
true_reg1): range bounds violation u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0] var_off=(0x0,0x0)WARNING: CPU: 0 PID: 93 at kernel/bpf/verifier.c:2731 reg_bounds_sanity_check+0x163/0x220 Modules linked in: CPU: 0 UID: 0 PID: 93 Comm: repro-x-3 Tainted: G W 6.18.0-rc1-ge7586577b75f-dirty #218 PREEMPT(full) Tainted: [W]=WARN Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:reg_bounds_sanity_check+0x163/0x220 Call Trace: <TASK> reg_set_min_max.part.0+0x1b1/0x360 check_cond_jmp_op+0x1195/0x1a60 do_check_common+0x33ac/0x33c0...
The issue occurs in
reg_set_min_max()function where bounds adjustment logic
is applied even when both registers being compared are the same. Comparing a
register with itself should not change its bounds since the comparison result
is always known (e.g., r0 == r0 is always true, r0 < r0 is always false).Fix this by adding an early return in
reg_set_min_max()whenfalse_reg1andfalse_reg2point to the same register, skipping the unnecessary bounds adjustment that leads to the verifier bug.Reported-by Kaiyan Mei <[email protected]>Reported-by Yinhao Hu <[email protected]>Closes:
https://lore.kernel.org/all/[email protected]/Fixes 0df1a55afa83 ("bpf: Warn on internal verifier errors")Signed-off-by KaFai Wan <[email protected]>---
kernel/bpf/verifier.c| 4 ++++1 file changed, 4 insertions(+)kernel/bpf/verifier.c +0
-0@@ -16429,6 +16429,10 @@ static int reg_set_min_max(struct bpf_verifier_env *env,if (
false_reg1->type!=SCALAR_VALUE||false_reg2->type!=SCALAR_VALUE)
return 0;Quoted 16 lines
Quoted 4 lines
+ /* If conditional jumps on the same register, skip the adjustment */
+ if (false_reg1==false_reg2)
+ return 0;Your change looks good. But this is a special case and it should not happen for any compiler generated code. So could you investigate why
regs_refine_cond_op()does not work? Sincefalse_reg1andfalse_reg2is the same, so register refinement should keep the same. Probably some minor change inregs_refine_cond_op(...)should work?Quoted 5 lines
+
/* fallthrough (FALSE) branch */regs_refine_cond_op(false_reg1, false_reg2, rev_opcode(opcode), is_jmp32);
reg_bounds_sync(false_reg1);I think
regs_refine_cond_op()is not written in a way to handle same registers passed as reg1 and reg2. E.g. in this particular case the condition is reformulated as "r0 < r0", and then the following branch is taken:static void regs_refine_cond_op(struct
bpf_reg_state*reg1, structbpf_reg_state*reg2,
u8 opcode, boolis_jmp32)
{
...
caseBPF_JLT: // condition is rephrased as r0 < r0 if (is_jmp32) {
...
} else {
reg1->umax_value= min(reg1->umax_value, reg2-
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 1 line
umax_value- 1);
reg2->umin_value=max(reg1->umin_value + 1, reg2->umin_value);
Yes, that's the root cause.
Quoted 34 lines
Quoted 19 lines
Quoted 19 lines
}
break;
...
}Note that intent is to adjust umax of the LHS (reg1) register and umin of the RHS (reg2) register. But here it ends up adjusting the same register.
(a) before refinement: u64=[0x0,
0x80000000] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(b) after refinement: u64=[0x1,0x7fffffff] s64=[0x0,0x80000000] u32=[0x0,0x80000000] s32=[0x80000000,0x0]
(c) after sync : u64=[0x1,0x0] s64=[0x1,0x0] u32=[0x1,0x0] s32=[0x1,0x0]At (b) the u64 range translated to s32 is > 0, while s32 range is <= 0, hence the invariant violation.
Quoted 6 lines
Quoted 2 lines
I think it's better to move the reg1 == reg2 check inside
regs_refine_cond_op(), or to handle this case inis_branch_taken().hmm. bu then
regs_refine_cond_op()will skip it, yetreg_set_min_max()will still be doing pointless work withreg_bounds_sync()and sanity check. The current patch makes more sense to me.Well, if we want to avoid useless work, we need something like:
(quoted diff) +0
-0@@ -16173,6 +16173,25 @@ static int is_pkt_ptr_branch_taken(struct bpf_reg_state *dst_reg,static int is_branch_taken(struct
bpf_reg_state*reg1, structbpf_reg_state*reg2,
u8 opcode, boolis_jmp32)
{
Quoted 8 lines
+ if (reg1 == reg2) {
+ switch (opcode) {
+ caseBPF_JGE:
+ caseBPF_JLE:
+ caseBPF_JSGE:
+ caseBPF_JSLE:
+ caseBPF_JEQ:
+ caseBPF_JSET:
Others are fine, but BPF_JSET on the same register could be 0 (if value is 0). And it's unknown to take the branch if 0 within the range.
Quoted 12 lines
+ return 1;
+ caseBPF_JGT:
+ caseBPF_JLT:
+ caseBPF_JSGT:
+ caseBPF_JSLT:
+ caseBPF_JNE:
+ return 0;
+ default:
+ return -1;
+ }
+ }
Quoted 2 lines
But that's too much code for an artificial case.
Idk, either way is fine with me.
There is is_scalar_branch_taken() in is_branch_taken(), I missed it. I'll a) check the opcode one by one in is_scalar_branch_taken(), and b) keep this patch for unknown BPF_JSET branch.
Signature · 2 lines
Thanks, KaFai
Eduard Zingerman
maintainerOn Thu, 2025-10-23 at 19:26 +0800, KaFai Wan wrote:
[...]
Quoted 9 lines
Quoted 9 lines
(quoted diff) +0
-0@@ -16173,6 +16173,25 @@ static int is_pkt_ptr_branch_taken(struct bpf_reg_state *dst_reg,static int is_branch_taken(struct
bpf_reg_state*reg1, structbpf_reg_state*reg2,
u8 opcode, boolis_jmp32)
{
+ if (reg1 == reg2) {
+ switch (opcode) {
+ caseBPF_JGE:
Quoted 8 lines
Quoted 5 lines
+ case
BPF_JLE:
+ caseBPF_JSGE:
+ caseBPF_JSLE:
+ caseBPF_JEQ:
+ caseBPF_JSET:Others are fine, but
BPF_JSETon the same register could be 0 (if value is 0). And it's unknown to take the branch if 0 within the range.
Right, missed that one.
Quoted 13 lines
Quoted 13 lines
+ return 1;
+ caseBPF_JGT:
+ caseBPF_JLT:
+ caseBPF_JSGT:
+ caseBPF_JSLT:
+ caseBPF_JNE:
+ return 0;
+ default:
+ return -1;
+ }
+ }
Quoted 6 lines
Quoted 2 lines
But that's too much code for an artificial case.
Idk, either way is fine with me.There is
is_scalar_branch_taken()inis_branch_taken(), I missed it. I'll a) check the opcode one by one inis_scalar_branch_taken(), and b) keep this patch for unknownBPF_JSETbranch.
Sounds good to me. Note that the logic is correct for both scalar and non-scalar cases, so I don't think we have to constrain it to is_scalar_branch_taken() (don't think there is a need to check if pointer comparisons are allowed, as no new information is inferred from comparisons with self).
Quoted 44 lines · Eduard Zingerman
On Thu, 2025-10-23 at 19:26 +0800, KaFai Wan wrote:
[...]
Quoted 9 lines
Quoted 9 lines
(quoted diff) +0
-0@@ -16173,6 +16173,25 @@ static int is_pkt_ptr_branch_taken(struct bpf_reg_state *dst_reg,static int is_branch_taken(struct
bpf_reg_state*reg1, structbpf_reg_state*reg2,
u8 opcode, boolis_jmp32)
{
+ if (reg1 == reg2) {
+ switch (opcode) {
+ caseBPF_JGE:Quoted 8 lines
Quoted 5 lines
+ case
BPF_JLE:
+ caseBPF_JSGE:
+ caseBPF_JSLE:
+ caseBPF_JEQ:
+ caseBPF_JSET:Others are fine, but
BPF_JSETon the same register could be 0 (if value is 0). And it's unknown to take the branch if 0 within the range.Right, missed that one.
Quoted 13 lines
Quoted 13 lines
+ return 1;
+ caseBPF_JGT:
+ caseBPF_JLT:
+ caseBPF_JSGT:
+ caseBPF_JSLT:
+ caseBPF_JNE:
+ return 0;
+ default:
+ return -1;
+ }
+ }Quoted 6 lines
Quoted 2 lines
But that's too much code for an artificial case.
Idk, either way is fine with me.There is
is_scalar_branch_taken()inis_branch_taken(), I missed it. I'll a) check the opcode one by one inis_scalar_branch_taken(), and b) keep this patch for unknownBPF_JSETbranch.
Quoted 5 lines
Sounds good to me. Note that the logic is correct for both scalar and non-scalar cases, so I don't think we have to constrain it to
is_scalar_branch_taken()(don't think there is a need to check if pointer comparisons are allowed, as no new information is inferred from comparisons with self).
For non-scalar cases we only allow pointer comparison on pkt_ptr, this check is before is_branch_taken()
src_reg = ®s[insn->src_reg];
if (!(reg_is_pkt_pointer_any(dst_reg) && reg_is_pkt_pointer_any(src_reg)) &&
is_pointer_value(env, insn->src_reg)) {
verbose(env, "R%d pointer comparison prohibited\n",
insn->src_reg);
return -EACCES;
} and in the end of check_cond_jmp_op() (after is_branch_taken()), we checked again
} else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg],
this_branch, other_branch) &&
is_pointer_value(env, insn->dst_reg)) {
verbose(env, "R%d pointer comparison prohibited\n",
insn->dst_reg);
return -EACCES;
}this time we check if it is valid comparison on pkt_ptr in try_match_pkt_pointers().
Currently we just allow 4 opcode (BPF_JGT, BPF_JLT, BPF_JGE, BPF_JLE) on pkt_ptr, and with conditions. But we bypass these prohibits in privileged mode (is_pointer_value() always return false in privileged mode).
So the logic skip these prohibits for pkt_ptr in unprivileged mode.
Signature · 2 lines
Thanks, KaFai
Eduard Zingerman
maintainerOn Sat, 2025-10-25 at 00:13 +0800, KaFai Wan wrote:
[...]
Quoted 21 lines
For non-scalar cases we only allow pointer comparison on
pkt_ptr, this check is beforeis_branch_taken()src_reg = ®s[insn->src_reg]; if (!(reg_is_pkt_pointer_any(dst_reg) && reg_is_pkt_pointer_any(src_reg)) && is_pointer_value(env, insn->src_reg)) { verbose(env, "R%d pointer comparison prohibited\n", insn->src_reg); return -EACCES; }and in the end of
check_cond_jmp_op()(afteris_branch_taken()), we checked again} else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], this_branch, other_branch) && is_pointer_value(env, insn->dst_reg)) { verbose(env, "R%d pointer comparison prohibited\n", insn->dst_reg); return -EACCES; }
Quoted 7 lines
this time we check if it is valid comparison on
pkt_ptrintry_match_pkt_pointers().Currently we just allow 4 opcode (
BPF_JGT,BPF_JLT,BPF_JGE,BPF_JLE) onpkt_ptr, and with conditions. But we bypass these prohibits in privileged mode (is_pointer_value()always return false in privileged mode).So the logic skip these prohibits for
pkt_ptrin unprivileged mode.
Well, yes, but do you really need to do forbid if r0 > r0 goto ... in unpriv?
Quoted 27 lines · Eduard Zingerman
On Sat, 2025-10-25 at 00:13 +0800, KaFai Wan wrote:
[...]
Quoted 23 lines
For non-scalar cases we only allow pointer comparison on
pkt_ptr, this check is beforeis_branch_taken()src_reg = ®s[insn->src_reg]; if (!(reg_is_pkt_pointer_any(dst_reg) && reg_is_pkt_pointer_any(src_reg)) && is_pointer_value(env, insn->src_reg)) { verbose(env, "R%d pointer comparison prohibited\n", insn->src_reg); return -EACCES; }and in the end of
check_cond_jmp_op()(afteris_branch_taken()), we checked again} else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], this_branch, other_branch) && is_pointer_value(env, insn->dst_reg)) { verbose(env, "R%d pointer comparison prohibited\n", insn->dst_reg); return -EACCES; }this time we check if it is valid comparison on
pkt_ptrintry_match_pkt_pointers().
Quoted 7 lines
Quoted 5 lines
Currently we just allow 4 opcode (
BPF_JGT,BPF_JLT,BPF_JGE,BPF_JLE) onpkt_ptr, and with conditions. But we bypass these prohibits in privileged mode (is_pointer_value()always return false in privileged mode).So the logic skip these prohibits for
pkt_ptrin unprivileged mode.Well, yes, but do you really need to do forbid
if r0 > r0 goto ...in unpriv?
Currently if r0 > r0 goto ... is forbid in unpriv, but we can allow it.
Signature · 2 lines
Thanks, KaFai
Quoted 33 lines · KaFai Wan
Quoted 31 lines · Eduard Zingerman
On Sat, 2025-10-25 at 00:13 +0800, KaFai Wan wrote:
[...]
Quoted 27 lines
For non-scalar cases we only allow pointer comparison on
pkt_ptr, this check is beforeis_branch_taken()src_reg = ®s[insn->src_reg]; if (!(reg_is_pkt_pointer_any(dst_reg) && reg_is_pkt_pointer_any(src_reg)) && is_pointer_value(env, insn->src_reg)) { verbose(env, "R%d pointer comparison prohibited\n", insn->src_reg); return -EACCES; }and in the end of
check_cond_jmp_op()(afteris_branch_taken()), we checked again} else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], this_branch, other_branch) && is_pointer_value(env, insn->dst_reg)) { verbose(env, "R%d pointer comparison prohibited\n", insn->dst_reg); return -EACCES; }this time we check if it is valid comparison on
pkt_ptrintry_match_pkt_pointers().Currently we just allow 4 opcode (
BPF_JGT,BPF_JLT,BPF_JGE,BPF_JLE) onpkt_ptr, and with conditions. But we bypass these prohibits in privileged mode (is_pointer_value()always return false in privileged mode).
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
So the logic skip these prohibits for
pkt_ptrin unprivileged mode.Well, yes, but do you really need to do forbid
if r0 > r0 goto ...in unpriv?Currently
if r0 > r0 goto ...is forbid in unpriv, but we can allow it.
Let's not relax unpriv. We don't need new threads with researchers whether such things can be exploited.
Quoted 34 lines · Alexei Starovoitov
Quoted 33 lines · KaFai Wan
Quoted 31 lines · Eduard Zingerman
On Sat, 2025-10-25 at 00:13 +0800, KaFai Wan wrote:
[...]
Quoted 27 lines
For non-scalar cases we only allow pointer comparison on
pkt_ptr, this check is beforeis_branch_taken()
src_reg= ®s[insn->src_reg];
if (!(reg_is_pkt_pointer_any(dst_reg) &®_is_pkt_pointer_any(src_reg)) &&is_pointer_value(env, insn->src_reg)) {
verbose(env, "R%d pointer comparison prohibited\n", insn->src_reg);
return-EACCES;
}and in the end of
check_cond_jmp_op()(afteris_branch_taken()), we checked again} else if (!try_match_pkt_pointers(insn,
dst_reg, ®s[insn->src_reg],this_branch,other_branch) &&is_pointer_value(env, insn->dst_reg)) {verbose(env, "R%d pointer comparison prohibited\n", insn->dst_reg);
return-EACCES;
}this time we check if it is valid comparison on
pkt_ptrintry_match_pkt_pointers().Currently we just allow 4 opcode (
BPF_JGT,BPF_JLT,BPF_JGE,BPF_JLE) onpkt_ptr, and with conditions. But we bypass these prohibits in privileged mode (is_pointer_value()always return false in privileged mode).
Quoted 9 lines
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
So the logic skip these prohibits for
pkt_ptrin unprivileged mode.Well, yes, but do you really need to do forbid
if r0 > r0 goto ...in unpriv?Currently
if r0 > r0 goto ...is forbid in unpriv, but we can allow it.Let's not relax unpriv. We don't need new threads with researchers whether such things can be exploited.
Ok, I'll keep the logic for both scalar and non-scalar cases.
Signature · 2 lines
Thanks, KaFai
PATCH 2/2 selftests/bpf: Add test for conditional jumps on same register
In reply to KaFai WanAdd a test case to verify that conditional jumps on the same register (e.g., JGT r0 > r0) do not trigger verifier BUG warnings when the register holds a scalar with range.
--- .../selftests/bpf/progs/verifier_bounds.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +17 -0
@@ -1709,4 +1709,21 @@ __naked void jeq_disagreeing_tnums(void *ctx) : __clobber_all); } +SEC("socket") +__description("JGT on same register") +__success __log_level(2) +__naked void jgt_same_register (void *ctx) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w8 = 0x80000000; \ +r0 &= r8; \ +if r0 > r0 goto +1; \ +call %[bpf_get_prandom_u32]; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0