[PATCH bpf v3 0/2] bpf: mark registers in all frames after pkt/null checks

[PATCH bpf v3 0/2] bpf: mark registers in all frames after pkt/null checks

[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_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(-)

-- 
2.17.1

[PATCH bpf v3 1/2] bpf: mark registers in all frames after pkt/null checks

[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.  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.

Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
---
 kernel/bpf/verifier.c | 76 ++++++++++++++++++++++++++-----------------
 1 file changed, 46 insertions(+), 30 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 423f242a5efb..cc2d85bd5a3a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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, &regs[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,
-- 
2.17.1

[PATCH bpf v3 2/2] selftests/bpf: test cases for pkt/null checks in subprogs

[Paul Chaignon]

The 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;

Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
---
 tools/testing/selftests/bpf/verifier/calls.c  | 25 +++++++++++++++++++
 .../bpf/verifier/direct_packet_access.c       | 22 ++++++++++++++++
 2 files changed, 47 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index fb11240b758b..9093a8f64dc6 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -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 = {
diff --git a/tools/testing/selftests/bpf/verifier/direct_packet_access.c b/tools/testing/selftests/bpf/verifier/direct_packet_access.c
index e3fc22e672c2..d5c596fdc4b9 100644
--- a/tools/testing/selftests/bpf/verifier/direct_packet_access.c
+++ b/tools/testing/selftests/bpf/verifier/direct_packet_access.c
@@ -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,
+},
-- 
2.17.1

Re: [PATCH bpf v3 0/2] bpf: mark registers in all frames after pkt/null checks

[Yonghong Song]

On 4/24/19 12:49 PM, Paul Chaignon wrote:
> 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(-)

Ack for the whole series.
Acked-by: Yonghong Song <yhs@fb.com>

Re: [PATCH bpf v3 0/2] bpf: mark registers in all frames after pkt/null checks

[Alexei Starovoitov]

On Wed, Apr 24, 2019 at 09:49:58PM +0200, Paul Chaignon wrote:
> 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.

Applied to bpf tree, thanks!

Re: [PATCH bpf v3 0/2] bpf: mark registers in all frames after pkt/null checks

[Daniel Borkmann]

On 04/25/2019 10:46 PM, Alexei Starovoitov wrote:
> On Wed, Apr 24, 2019 at 09:49:58PM +0200, Paul Chaignon wrote:
>> 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.
[...]
>>
>> 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.

Sorry for the delay, looks good to me, thanks!

>>     - 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!
>