bpf: Fix reg_set_min_max corruption of fake_reg
Subsystems (4)
Daniel Borkmann
maintainerPATCH v2 1/3 bpf: Fix reg_set_min_max corruption of fake_reg
Juan reported that after doing some changes to buzzer [0] and implementing a new fuzzing strategy guided by coverage, they noticed the following in one of the probes:
[...]
13: (79) r6 = *(u64 *)(r0 +0) ; R0=map_value(ks=4,vs=8) R6_w=scalar() 14: (b7) r0 = 0 ; R0_w=0 15: (b4) w0 = -1 ; R0_w=0xffffffff 16: (74) w0 >>= 1 ; R0_w=0x7fffffff 17: (5c) w6 &= w0 ; R0_w=0x7fffffff R6_w=scalar(smin=smin32=0,smax=umax=umax32=0x7fffffff,var_off=(0x0; 0x7fffffff)) 18: (44) w6 |= 2 ; R6_w=scalar(smin=umin=smin32=umin32=2,smax=umax=umax32=0x7fffffff,var_off=(0x2; 0x7ffffffd))
19: (56) if w6 != 0x7ffffffd goto pc+1
REG INVARIANTS VIOLATION (true_reg2): range bounds violation u64=[0x7fffffff, 0x7ffffffd] s64=[0x7fffffff, 0x7ffffffd] u32=[0x7fffffff, 0x7ffffffd] s32=[0x7fffffff, 0x7ffffffd] var_off=(0x7fffffff, 0x0) REG INVARIANTS VIOLATION (false_reg1): range bounds violation u64=[0x7fffffff, 0x7ffffffd] s64=[0x7fffffff, 0x7ffffffd] u32=[0x7fffffff, 0x7ffffffd] s32=[0x7fffffff, 0x7ffffffd] var_off=(0x7fffffff, 0x0) REG INVARIANTS VIOLATION (false_reg2): const tnum out of sync with range bounds u64=[0x0, 0xffffffffffffffff] s64=[0x8000000000000000, 0x7fffffffffffffff] u32=[0x0, 0xffffffff] s32=[0x80000000, 0x7fffffff] var_off=(0x7fffffff, 0x0) 19: R6_w=0x7fffffff
20: (95) exit
from 19 to 21: R0=0x7fffffff R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=0x7ffffffe,var_off=(0x2; 0x7ffffffd)) R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm 21: R0=0x7fffffff R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=0x7ffffffe,var_off=(0x2; 0x7ffffffd)) R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm
21: (14) w6 -= 2147483632 ; R6_w=scalar(smin=umin=umin32=2,smax=umax=0xffffffff,smin32=0x80000012,smax32=14,var_off=(0x2; 0xfffffffd))
22: (76) if w6 s>= 0xe goto pc+1 ; R6_w=scalar(smin=umin=umin32=2,smax=umax=0xffffffff,smin32=0x80000012,smax32=13,var_off=(0x2; 0xfffffffd))
23: (95) exit
from 22 to 24: R0=0x7fffffff R6_w=14 R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm 24: R0=0x7fffffff R6_w=14 R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm
24: (14) w6 -= 14 ; R6_w=0
[...]
What can be seen here is a register invariant violation on line 19. After the binary-or in line 18, the verifier knows that bit 2 is set but knows nothing about the rest of the content which was loaded from a map value, meaning, range is [2,0x7fffffff] with var_off=(0x2; 0x7ffffffd). When in line 19 the verifier analyzes the branch, it splits the register states in reg_set_min_max() into the registers of the true branch (true_reg1, true_reg2) and the registers of the false branch (false_reg1, false_reg2).
Since the test is w6 != 0x7ffffffd, the src_reg is a known constant. Internally, the verifier creates a "fake" register initialized as scalar to the value of 0x7ffffffd, and then passes it onto reg_set_min_max(). Now, for line 19, it is mathematically impossible to take the false branch of this program, yet the verifier analyzes it. It is impossible because the second bit of r6 will be set due to the prior or operation and the constant in the condition has that bit unset (hex(fd) == binary(1111 1101).
When the verifier first analyzes the false / fall-through branch, it will compute an intersection between the var_off of r6 and of the constant. This is because the verifier creates a "fake" register initialized to the value of the constant. The intersection result later refines both registers in regs_refine_cond_op():
[...] t = tnum_intersect(tnum_subreg(reg1->var_off), tnum_subreg(reg2->var_off)); reg1->var_off = tnum_with_subreg(reg1->var_off, t); reg2->var_off = tnum_with_subreg(reg2->var_off, t); [...]
Since the verifier is analyzing the false branch of the conditional jump, reg1 is equal to false_reg1 and reg2 is equal to false_reg2, i.e. the reg2 is the "fake" register that was meant to hold a constant value. The resulting var_off of the intersection says that both registers now hold a known value of var_off=(0x7fffffff, 0x0) or in other words: this operation manages to make the verifier think that the "constant" value that was passed in the jump operation now holds a different value.
Normally this would not be an issue since it should not influence the true branch, however, false_reg2 and true_reg2 are pointers to the same "fake" register. Meaning, the false branch can influence the results of the true branch. In line 24, the verifier assumes R6_w=0, but the actual runtime value in this case is 1. The fix is simply not passing in the same "fake" register location as inputs to reg_set_min_max(), but instead making a copy. Moving the fake_reg into the env also reduces stack consumption by 120 bytes. With this, the verifier successfully rejects invalid accesses from the test program.
[0] https://github.com/google/buzzer
---
v1 -> v2:
- Reduce stack space consumption (Alexei)
include/linux/bpf_verifier.h | 2 ++ kernel/bpf/verifier.c | 14 ++++++++++---- 2 files changed, 12 insertions(+), 4 deletions(-)
include/linux/bpf_verifier.h +2 -0
@@ -746,6 +746,8 @@ struct bpf_verifier_env {/* Same as scratched_regs but for stack slots */ u64 scratched_stack_slots;u64 prev_log_pos, prev_insn_print_pos; +/* buffer used to temporary hold constants as scalar registers */ +struct bpf_reg_state fake_reg[2 ];/* buffer used to generate temporary string representations, * e.g., in reg_type_str() to generate reg_type string */
kernel/bpf/verifier.c +10 -4
@@ -15113,7 +15113,6 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg =NULL ;struct bpf_reg_state *eq_branch_regs; -struct bpf_reg_state fake_reg = {};u8 opcode =BPF_OP (insn->code);bool is_jmp32;int pred =-1 ;
@@ -15179,7 +15178,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,verbose (env,"BPF_JMP/JMP32 uses reserved fields\n" );return -EINVAL ; } - src_reg = &fake_reg; + src_reg = &env->fake_reg[0 ]; +memset (src_reg,0 ,sizeof (*src_reg)); src_reg->type =SCALAR_VALUE ;__mark_reg_known (src_reg, insn->imm); }
@@ -15239,10 +15239,16 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, &other_branch_regs[insn->src_reg], dst_reg, src_reg, opcode, is_jmp32); }else /* BPF_SRC(insn->code) == BPF_K */ { +/* reg_set_min_max() can mangle the fake_reg. Make a copy +* so that these are two different memory locations. The +* src_reg is not used beyond here in context of K. +*/ +memcpy (&env->fake_reg[1 ], &env->fake_reg[0 ], +sizeof (env->fake_reg[0 ])); err =reg_set_min_max (env, &other_branch_regs[insn->dst_reg], - src_reg/* fake one */ , - dst_reg, src_reg/* same fake one */ , + &env->fake_reg[0 ], + dst_reg, &env->fake_reg[1 ], opcode, is_jmp32); }if (err)
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v2 2/3 bpf: Reduce stack consumption in check_stack_write_fixed_off
The fake_reg moved into env->fake_reg given it consumes a lot of stack space (120 bytes). Migrate the fake_reg in check_stack_write_fixed_off() as well now that we have it.
--- kernel/bpf/verifier.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +5 -4
@@ -4549,11 +4549,12 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env, state->stack[spi].spilled_ptr.id =0 ; }else if (!reg && !(off %BPF_REG_SIZE ) &&is_bpf_st_mem (insn) && env->bpf_capable) { -struct bpf_reg_state fake_reg = {}; +struct bpf_reg_state *tmp_reg = &env->fake_reg[0 ]; -__mark_reg_known (&fake_reg, insn->imm); - fake_reg.type =SCALAR_VALUE ; -save_register_state (env, state, spi, &fake_reg, size); +memset (tmp_reg,0 ,sizeof (*tmp_reg)); +__mark_reg_known (tmp_reg, insn->imm); + tmp_reg->type =SCALAR_VALUE ; +save_register_state (env, state, spi, tmp_reg, size); }else if (reg &&is_spillable_regtype (reg->type)) {/* register containing pointer is being spilled into stack */ if (size !=BPF_REG_SIZE ) {
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH v2 3/3 selftests/bpf: Add test coverage for reg_set_min_max handling
In reply to Daniel BorkmannAdd a test case for the jmp32/k fix to ensure selftests have coverage.
Before fix:
# ./vmtest.sh -- ./test_progs -t verifier_or_jmp32_k [...] ./test_progs -t verifier_or_jmp32_k tester_init:PASS:tester_log_buf 0 nsec process_subtest:PASS:obj_open_mem 0 nsec process_subtest:PASS:specs_alloc 0 nsec run_subtest:PASS:obj_open_mem 0 nsec run_subtest:FAIL:unexpected_load_success unexpected success: 0 #492/1 verifier_or_jmp32_k/or_jmp32_k: bit ops + branch on unknown value:FAIL #492 verifier_or_jmp32_k:FAIL Summary: 0/0 PASSED, 0 SKIPPED, 1 FAILED
After fix:
# ./vmtest.sh -- ./test_progs -t verifier_or_jmp32_k [...] ./test_progs -t verifier_or_jmp32_k #492/1 verifier_or_jmp32_k/or_jmp32_k: bit ops + branch on unknown value:OK #492 verifier_or_jmp32_k:OK Summary: 1/1 PASSED, 0 SKIPPED, 0 FAILED
--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_or_jmp32_k.c | 41 +++++++++++++++++++ 2 files changed, 43 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_or_jmp32_k.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -53,6 +53,7 @@#include "verifier_movsx.skel.h" #include "verifier_netfilter_ctx.skel.h" #include "verifier_netfilter_retcode.skel.h" +#include "verifier_or_jmp32_k.skel.h" #include "verifier_precision.skel.h" #include "verifier_prevent_map_lookup.skel.h" #include "verifier_raw_stack.skel.h"
@@ -170,6 +171,7 @@ void test_verifier_meta_access(void) { RUN(verifier_meta_access); }void test_verifier_movsx (void ) {RUN (verifier_movsx); }void test_verifier_netfilter_ctx (void ) {RUN (verifier_netfilter_ctx); }void test_verifier_netfilter_retcode (void ) {RUN (verifier_netfilter_retcode); } +void test_verifier_or_jmp32_k (void ) {RUN (verifier_or_jmp32_k); }void test_verifier_precision (void ) {RUN (verifier_precision); }void test_verifier_prevent_map_lookup (void ) {RUN (verifier_prevent_map_lookup); }void test_verifier_raw_stack (void ) {RUN (verifier_raw_stack); }
tools/testing/selftests/bpf/progs/verifier_or_jmp32_k.c new file +41 -0
41 lines not on this page · raw message
Signature · 1 line
2.43.0
Quoted 75 lines · Daniel Borkmann
Juan reported that after doing some changes to buzzer [0] and implementing a new fuzzing strategy guided by coverage, they noticed the following in one of the probes:
[...]
13: (79) r6 = *(u64 *)(r0 +0) ; R0=map_value(ks=4,vs=8) R6_w=scalar() 14: (b7) r0 = 0 ; R0_w=0 15: (b4) w0 = -1 ; R0_w=0xffffffff 16: (74) w0 >>= 1 ; R0_w=0x7fffffff 17: (5c) w6 &= w0 ; R0_w=0x7fffffff R6_w=scalar(smin=smin32=0,smax=umax=umax32=0x7fffffff,var_off=(0x0; 0x7fffffff)) 18: (44) w6 |= 2 ; R6_w=scalar(smin=umin=smin32=umin32=2,smax=umax=umax32=0x7fffffff,var_off=(0x2; 0x7ffffffd))19: (56) if w6 !=
0x7ffffffdgoto pc+1
REG INVARIANTS VIOLATION (true_reg2): range bounds violation u64=[0x7fffffff,0x7ffffffd] s64=[0x7fffffff,0x7ffffffd] u32=[0x7fffffff,0x7ffffffd] s32=[0x7fffffff,0x7ffffffd] var_off=(0x7fffffff,0x0) REG INVARIANTS VIOLATION (false_reg1): range bounds violation u64=[0x7fffffff,0x7ffffffd] s64=[0x7fffffff,0x7ffffffd] u32=[0x7fffffff,0x7ffffffd] s32=[0x7fffffff,0x7ffffffd] var_off=(0x7fffffff,0x0) REG INVARIANTS VIOLATION (false_reg2): const tnum out of sync with range bounds u64=[0x0,0xffffffffffffffff] s64=[0x8000000000000000,0x7fffffffffffffff] u32=[0x0,0xffffffff] s32=[0x80000000,0x7fffffff] var_off=(0x7fffffff,0x0) 19: R6_w=0x7fffffff
20: (95) exitfrom 19 to 21: R0=0x7fffffff R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=0x7ffffffe,var_off=(0x2;
0x7ffffffd)) R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm 21: R0=0x7fffffff R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=0x7ffffffe,var_off=(0x2;0x7ffffffd)) R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm
21: (14) w6 -= 2147483632 ; R6_w=scalar(smin=umin=umin32=2,smax=umax=0xffffffff,smin32=0x80000012,smax32=14,var_off=(0x2;0xfffffffd))
22: (76) if w6 s>=0xegoto pc+1 ; R6_w=scalar(smin=umin=umin32=2,smax=umax=0xffffffff,smin32=0x80000012,smax32=13,var_off=(0x2;0xfffffffd))
23: (95) exitfrom 22 to 24: R0=0x7fffffff R6_w=14 R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm 24: R0=0x7fffffff R6_w=14 R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm
24: (14) w6 -= 14 ; R6_w=0
[...]What can be seen here is a register invariant violation on line 19. After the binary-or in line 18, the verifier knows that bit 2 is set but knows nothing about the rest of the content which was loaded from a map value, meaning, range is [2,0x7fffffff] with var_off=(0x2;
0x7ffffffd). When in line 19 the verifier analyzes the branch, it splits the register states inreg_set_min_max()into the registers of the true branch (true_reg1,true_reg2) and the registers of the false branch (false_reg1,false_reg2).Since the test is w6 !=
0x7ffffffd, thesrc_regis a known constant. Internally, the verifier creates a "fake" register initialized as scalar to the value of0x7ffffffd, and then passes it ontoreg_set_min_max(). Now, for line 19, it is mathematically impossible to take the false branch of this program, yet the verifier analyzes it. It is impossible because the second bit of r6 will be set due to the prior or operation and the constant in the condition has that bit unset (hex(fd) == binary(1111 1101).When the verifier first analyzes the false / fall-through branch, it will compute an intersection between the
var_offof r6 and of the constant. This is because the verifier creates a "fake" register initialized to the value of the constant. The intersection result later refines both registers inregs_refine_cond_op():[...] t = tnum_intersect(tnum_subreg(reg1->var_off), tnum_subreg(reg2->var_off)); reg1->var_off = tnum_with_subreg(reg1->var_off, t); reg2->var_off = tnum_with_subreg(reg2->var_off, t); [...]Since the verifier is analyzing the false branch of the conditional jump, reg1 is equal to
false_reg1and reg2 is equal tofalse_reg2, i.e. the reg2 is the "fake" register that was meant to hold a constant value. The resultingvar_offof the intersection says that both registers now hold a known value of var_off=(0x7fffffff,0x0) or in other words: this operation manages to make the verifier think that the "constant" value that was passed in the jump operation now holds a different value.Normally this would not be an issue since it should not influence the true branch, however,
false_reg2andtrue_reg2are pointers to the same "fake" register. Meaning, the false branch can influence the results of the true branch. In line 24, the verifier assumes R6_w=0, but the actual runtime value in this case is 1. The fix is simply not passing in the same "fake" register location as inputs toreg_set_min_max(), but instead making a copy. Moving thefake_reginto the env also reduces stack consumption by 120 bytes. With this, the verifier successfully rejects invalid accesses from the test program.
Quoted 8 lines
[0] https://github.com/google/buzzer
Fixes 67420501e868 ("bpf: generalize reg_set_min_max() to handle non-const register comparisons")Reported-by Juan José López Jaimez <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>---
v1 -> v2:
- Reduce stack space consumption (Alexei)
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 11 lines · On Thu, 13 Jun 2024 13:53:08 +0200 you wrote:
Juan reported that after doing some changes to buzzer [0] and implementing a new fuzzing strategy guided by coverage, they noticed the following in one of the probes:
[...]
13: (79) r6 = *(u64 *)(r0 +0) ; R0=map_value(ks=4,vs=8) R6_w=scalar() 14: (b7) r0 = 0 ; R0_w=0 15: (b4) w0 = -1 ; R0_w=0xffffffff 16: (74) w0 >>= 1 ; R0_w=0x7fffffff 17: (5c) w6 &= w0 ; R0_w=0x7fffffff R6_w=scalar(smin=smin32=0,smax=umax=umax32=0x7fffffff,var_off=(0x0; 0x7fffffff)) 18: (44) w6 |= 2 ; R6_w=scalar(smin=umin=smin32=umin32=2,smax=umax=umax32=0x7fffffff,var_off=(0x2; 0x7ffffffd))
Quoted 8 lines
19: (56) if w6 !=
0x7ffffffdgoto pc+1
REG INVARIANTS VIOLATION (true_reg2): range bounds violation u64=[0x7fffffff,0x7ffffffd] s64=[0x7fffffff,0x7ffffffd] u32=[0x7fffffff,0x7ffffffd] s32=[0x7fffffff,0x7ffffffd] var_off=(0x7fffffff,0x0) REG INVARIANTS VIOLATION (false_reg1): range bounds violation u64=[0x7fffffff,0x7ffffffd] s64=[0x7fffffff,0x7ffffffd] u32=[0x7fffffff,0x7ffffffd] s32=[0x7fffffff,0x7ffffffd] var_off=(0x7fffffff,0x0) REG INVARIANTS VIOLATION (false_reg2): const tnum out of sync with range bounds u64=[0x0,0xffffffffffffffff] s64=[0x8000000000000000,0x7fffffffffffffff] u32=[0x0,0xffffffff] s32=[0x80000000,0x7fffffff] var_off=(0x7fffffff,0x0) 19: R6_w=0x7fffffff
20: (95) exit[...]
Here is the summary with links:
- [bpf,v2,1/3] bpf: Fix reg_set_min_max corruption of fake_reg
https://git.kernel.org/bpf/bpf/c/92424801261d - [bpf,v2,2/3] bpf: Reduce stack consumption in check_stack_write_fixed_off https://git.kernel.org/bpf/bpf/c/e73cd1cfc217 - [bpf,v2,3/3] selftests/bpf: Add test coverage for reg_set_min_max handling https://git.kernel.org/bpf/bpf/c/ceb65eb60026
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html