bpf: mark registers in all frames after pkt/null checks
Subsystems (6)
v3 cover bpf: mark registers in all frames after pkt/null checks
In case of a null check on a pointer inside a subprog, we should mark all registers with this pointer as either safe or unknown, in both the current and previous frames. Currently, only spilled registers and registers in the current frame are marked. Packet bound checks in subprogs have the same issue. The first patch fixes it to mark registers in previous frames as well.
A good reproducer for null checks looks as follow:
1: ptr = bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3: return ptr != NULL;
4: }
5: if (ret)
6: value = *ptr;
With the above, the verifier will complain on line 6 because it sees ptr as map_value_or_null despite the null check in subprog 1. The second patch implements the above as a new test case.
Note that this patch fixes another resulting bug when using bpf_sk_release():
1: sk = bpf_sk_lookup_tcp(...);
2: subprog(sk) {
3: if (sk)
4: bpf_sk_release(sk);
5: }
6: if (!sk)
7: return 0;
8: return 1;
In the above, mark_ptr_or_null_regs will warn on line 6 because it will try to free the reference state, even though it was already freed on line 3.
Changelogs:
Changes in v3:
- Fix same issue in find_good_pkt_pointers().
- Add test case for find_good_pkt_pointers() issue.
- Change title to account for the above change. Old title was "bpf: mark registers as safe or unknown in all frames".
- Refactor find_good_pkt_pointers and mark_ptr_or_null_regs.
- I did not keep Yonghong's ack because of the above changes.
Changes in v2:
- Fix example codes in commit message.
Paul Chaignon (2):
bpf: mark registers in all frames after pkt/null checks selftests/bpf: test cases for pkt/null checks in subprogs
kernel/bpf/verifier.c | 76 +++++++++++-------- tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++ .../bpf/verifier/direct_packet_access.c | 22 ++++++ 3 files changed, 93 insertions(+), 30 deletions(-)
Signature · 1 line
2.17.1
PATCH v3 1/2 bpf: mark registers in all frames after pkt/null checks
In case of a null check on a pointer inside a subprog, we should mark all registers with this pointer as either safe or unknown, in both the current and previous frames. Currently, only spilled registers and registers in the current frame are marked. Packet bound checks in subprogs have the same issue. This patch fixes it to mark registers in previous frames as well.
A good reproducer for null checks looks as follow:
1: ptr = bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3: return ptr != NULL;
4: }
5: if (ret)
6: value = *ptr;
With the above, the verifier will complain on line 6 because it sees ptr as map_value_or_null despite the null check in subprog 1.
Note that this patch fixes another resulting bug when using bpf_sk_release():
1: sk = bpf_sk_lookup_tcp(...);
2: subprog(sk) {
3: if (sk)
4: bpf_sk_release(sk);
5: }
6: if (!sk)
7: return 0;
8: return 1;
In the above, mark_ptr_or_null_regs will warn on line 6 because it will try to free the reference state, even though it was already freed on line 3.
--- kernel/bpf/verifier.c | 76 ++++++++++++++++++++++++++----------------- 1 file changed, 46 insertions(+), 30 deletions(-)
kernel/bpf/verifier.c +46 -30
@@ -4297,15 +4297,35 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)return 0 ; } +static void __find_good_pkt_pointers (struct bpf_func_state *state, +struct bpf_reg_state *dst_reg, +enum bpf_reg_type type,u16 new_range) +{ +struct bpf_reg_state *reg; +int i; + +for (i =0 ; i <MAX_BPF_REG ; i++) { + reg = &state->regs[i]; +if (reg->type == type && reg->id == dst_reg->id) +/* keep the maximum range already checked */ + reg->range =max (reg->range, new_range); + } + +bpf_for_each_spilled_reg (i, state, reg) { +if (!reg) +continue ; +if (reg->type == type && reg->id == dst_reg->id) + reg->range =max (reg->range, new_range); + } +} +static void find_good_pkt_pointers (struct bpf_verifier_state *vstate,struct bpf_reg_state *dst_reg,enum bpf_reg_type type,bool range_right_open) { -struct bpf_func_state *state = vstate->frame[vstate->curframe]; -struct bpf_reg_state *regs = state->regs, *reg;u16 new_range; -int i, j; +int i;if (dst_reg->off <0 || (dst_reg->off ==0 && range_right_open))
@@ -4370,20 +4390,9 @@ static void find_good_pkt_pointers(struct bpf_verifier_state *vstate,* the range won't allow anything. * dst_reg->off is known < MAX_PACKET_OFF, therefore it fits in a u16. */ -for (i =0 ; i <MAX_BPF_REG ; i++) -if (regs[i].type == type && regs[i].id == dst_reg->id) -/* keep the maximum range already checked */ - regs[i].range =max (regs[i].range, new_range); - -for (j =0 ; j <= vstate->curframe; j++) { - state = vstate->frame[j]; -bpf_for_each_spilled_reg (i, state, reg) { -if (!reg) -continue ; -if (reg->type == type && reg->id == dst_reg->id) - reg->range =max (reg->range, new_range); - } - } +for (i =0 ; i <= vstate->curframe; i++) +__find_good_pkt_pointers (vstate->frame[i], dst_reg, type, + new_range); }/* compute branch direction of the expression "if (reg opcode val) goto target;"
@@ -4857,6 +4866,22 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state, } } +static void __mark_ptr_or_null_regs (struct bpf_func_state *state,u32 id, +bool is_null) +{ +struct bpf_reg_state *reg; +int i; + +for (i =0 ; i <MAX_BPF_REG ; i++) +mark_ptr_or_null_reg (state, &state->regs[i], id, is_null); + +bpf_for_each_spilled_reg (i, state, reg) { +if (!reg) +continue ; +mark_ptr_or_null_reg (state, reg, id, is_null); + } +} +/* The logic is similar to find_good_pkt_pointers(), both could eventually * be folded together at some point. */
@@ -4864,10 +4889,10 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno, bool is_null) {struct bpf_func_state *state = vstate->frame[vstate->curframe]; -struct bpf_reg_state *reg, *regs = state->regs; +struct bpf_reg_state *regs = state->regs;u32 ref_obj_id = regs[regno].ref_obj_id;u32 id = regs[regno].id; -int i, j; +int i;if (ref_obj_id && ref_obj_id == id && is_null)/* regs[regno] is in the " == NULL" branch.
@@ -4876,17 +4901,8 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,*/ WARN_ON_ONCE (release_reference_state (state, id)); -for (i =0 ; i <MAX_BPF_REG ; i++) -mark_ptr_or_null_reg (state, ®s[i], id, is_null); - -for (j =0 ; j <= vstate->curframe; j++) { - state = vstate->frame[j]; -bpf_for_each_spilled_reg (i, state, reg) { -if (!reg) -continue ; -mark_ptr_or_null_reg (state, reg, id, is_null); - } - } +for (i =0 ; i <= vstate->curframe; i++) +__mark_ptr_or_null_regs (vstate->frame[i], id, is_null); } static bool try_match_pkt_pointers(const struct bpf_insn *insn,
Signature · 1 line
2.17.1
PATCH v3 2/2 selftests/bpf: test cases for pkt/null checks in subprogs
In reply to Paul ChaignonThe first test case, for pointer null checks, is equivalent to the following pseudo-code. It checks that the verifier does not complain on line 6 and recognizes that ptr isn't null.
1: ptr = bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3: return ptr != NULL;
4: }
5: if (ret)
6: value = *ptr;
The second test case, for packet bound checks, is equivalent to the following pseudo-code. It checks that the verifier does not complain on line 7 and recognizes that the packet is at least 1 byte long.
1: pkt_end = ctx.pkt_end;
2: ptr = ctx.pkt + 8;
3: ret = subprog(ptr, pkt_end) {
4: return ptr <= pkt_end;
5: }
6: if (ret)
7: value = *(u8 *)ctx.pkt;
--- tools/testing/selftests/bpf/verifier/calls.c | 25 +++++++++++++++++++ .../bpf/verifier/direct_packet_access.c | 22 ++++++++++++++++ 2 files changed, 47 insertions(+)
tools/testing/selftests/bpf/verifier/calls.c +25 -0
@@ -374,6 +374,31 @@ .prog_type = BPF_PROG_TYPE_XDP, .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS, }, +{ + "calls: ptr null check in subprog", + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,1 ,0 ,3 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_6 ,0 ), +BPF_EXIT_INSN (), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_1 ,0 ,1 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .errstr_unpriv ="function calls to other bpf functions are allowed for root only" , + .fixup_map_hash_48b = { 3 }, + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 0, +}, {"calls: two calls with args" , .insns = {
tools/testing/selftests/bpf/verifier/direct_packet_access.c +22 -0
@@ -631,3 +631,25 @@ .errstr = "invalid access to packet", .prog_type = BPF_PROG_TYPE_SCHED_CLS, }, +{ + "direct packet access: test29 (reg > pkt_end in subprog)", + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_6 ,BPF_REG_1 , + offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct __sk_buff , data_end)), +BPF_MOV64_REG (BPF_REG_3 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_3 ,8 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,1 ,0 ,4 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_6 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_JMP_REG (BPF_JGT ,BPF_REG_3 ,BPF_REG_2 ,1 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .prog_type = BPF_PROG_TYPE_SCHED_CLS, +},
Signature · 1 line
2.17.1
Quoted 47 lines · Paul Chaignon
In case of a null check on a pointer inside a subprog, we should mark all registers with this pointer as either safe or unknown, in both the current and previous frames. Currently, only spilled registers and registers in the current frame are marked. Packet bound checks in subprogs have the same issue. The first patch fixes it to mark registers in previous frames as well.
A good reproducer for null checks looks as follow:
1: ptr =
bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3: return ptr != NULL;
4: }
5: if (ret)
6: value = *ptr;With the above, the verifier will complain on line 6 because it sees ptr as
map_value_or_nulldespite the null check in subprog 1. The second patch implements the above as a new test case.Note that this patch fixes another resulting bug when using
bpf_sk_release():1: sk =
bpf_sk_lookup_tcp(...);
2: subprog(sk) {
3: if (sk)
4:bpf_sk_release(sk);
5: }
6: if (!sk)
7: return 0;
8: return 1;In the above,
mark_ptr_or_null_regswill warn on line 6 because it will try to free the reference state, even though it was already freed on line 3.Changelogs:
Changes in v3:
- Fix same issue infind_good_pkt_pointers().
- Add test case forfind_good_pkt_pointers()issue.
- Change title to account for the above change. Old title was "bpf: mark registers as safe or unknown in all frames".
- Refactorfind_good_pkt_pointersandmark_ptr_or_null_regs.
- I did not keep Yonghong's ack because of the above changes.
Changes in v2:
- Fix example codes in commit message.
Quoted 8 lines
Paul Chaignon (2):
bpf: mark registers in all frames after pkt/null checks selftests/bpf: test cases for pkt/null checks in subprogskernel/bpf/verifier.c | 76 +++++++++++-------- tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++ .../bpf/verifier/direct_packet_access.c | 22 ++++++ 3 files changed, 93 insertions(+), 30 deletions(-)
Ack for the whole series.
Alexei Starovoitov
AppliedQuoted 36 lines · Paul Chaignon
In case of a null check on a pointer inside a subprog, we should mark all registers with this pointer as either safe or unknown, in both the current and previous frames. Currently, only spilled registers and registers in the current frame are marked. Packet bound checks in subprogs have the same issue. The first patch fixes it to mark registers in previous frames as well.
A good reproducer for null checks looks as follow:
1: ptr =
bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3: return ptr != NULL;
4: }
5: if (ret)
6: value = *ptr;With the above, the verifier will complain on line 6 because it sees ptr as
map_value_or_nulldespite the null check in subprog 1. The second patch implements the above as a new test case.Note that this patch fixes another resulting bug when using
bpf_sk_release():1: sk =
bpf_sk_lookup_tcp(...);
2: subprog(sk) {
3: if (sk)
4:bpf_sk_release(sk);
5: }
6: if (!sk)
7: return 0;
8: return 1;In the above,
mark_ptr_or_null_regswill warn on line 6 because it will try to free the reference state, even though it was already freed on line 3.
Quoted 10 lines
Changelogs:
Changes in v3:
- Fix same issue infind_good_pkt_pointers().
- Add test case forfind_good_pkt_pointers()issue.
- Change title to account for the above change. Old title was "bpf: mark registers as safe or unknown in all frames".
- Refactorfind_good_pkt_pointersandmark_ptr_or_null_regs.
- I did not keep Yonghong's ack because of the above changes.
Changes in v2:
- Fix example codes in commit message.
Applied to bpf tree, thanks!
Daniel Borkmann
maintainerQuoted 7 lines · Alexei Starovoitov
Quoted 6 lines · Paul Chaignon
In case of a null check on a pointer inside a subprog, we should mark all registers with this pointer as either safe or unknown, in both the current and previous frames. Currently, only spilled registers and registers in the current frame are marked. Packet bound checks in subprogs have the same issue. The first patch fixes it to mark registers in previous frames as well.
[...]
Quoted 8 lines
Quoted 8 lines
Changelogs:
Changes in v3:
- Fix same issue infind_good_pkt_pointers().
- Add test case forfind_good_pkt_pointers()issue.
- Change title to account for the above change. Old title was "bpf: mark registers as safe or unknown in all frames".
- Refactorfind_good_pkt_pointersandmark_ptr_or_null_regs.
Sorry for the delay, looks good to me, thanks!
Quoted 6 lines
Quoted 3 lines
- I did not keep Yonghong's ack because of the above changes.
Changes in v2:
- Fix example codes in commit message.Applied to bpf tree, thanks!