[PATCH bpf 0/2] bpf: mark registers as safe or unknown in all frames

[PATCH bpf 0/2] bpf: mark registers as safe or unknown in all frames

[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.  This first patch also marks registers in
previous frames.

A good reproducer 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, 0);
5: }
6: if (!sk)
7:   return 0;
8: return sk;

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.

Paul Chaignon (2):
  bpf: mark registers as safe or unknown in all frames
  selftests/bpf: test case for pointer null check in subprog

 kernel/bpf/verifier.c                        |  6 ++---
 tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++++++++++++++++
 2 files changed, 28 insertions(+), 3 deletions(-)

-- 
2.17.1

[PATCH bpf 1/2] bpf: mark registers as safe or unknown in all frames

[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.  This patch also marks registers in previous
frames.

A good reproducer 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, 0);
5: }
6: if (!sk)
7:   return 0;
8: return sk;

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 | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index db301e9b5295..777970d8c245 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4876,11 +4876,11 @@ 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];
+		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;
-- 
2.17.1

Re: [PATCH bpf 1/2] bpf: mark registers as safe or unknown in all frames

[Yonghong Song]

On 4/20/19 5:39 AM, 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.  This patch also marks registers in previous
> frames.
> 
> A good reproducer 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, 0);
> 5: }
> 6: if (!sk)
> 7:   return 0;
> 8: return sk;

The patch below looks good to me, but I would like to have 
bpf_sk_lookup_tcp() example fixed so we can further verify it
indeed fixed the bpf_sk_release() issue.

> 
> 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 | 6 +++---
>   1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index db301e9b5295..777970d8c245 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -4876,11 +4876,11 @@ 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];
> +		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;
> 

[PATCH bpf 2/2] selftests/bpf: test case for pointer null check in subprog

[Paul Chaignon]

This test case 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;

Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
---
 tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++++++++++++++++
 1 file changed, 25 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 = {
-- 
2.17.1

Re: [PATCH bpf 0/2] bpf: mark registers as safe or unknown in all frames

[Yonghong Song]

On 4/20/19 5:38 AM, 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.  This first patch also marks registers in
> previous frames.
> 
> A good reproducer 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, 0);

The specification for bpf_sk_release() in uapi/linux/bpf.h is:
  int bpf_sk_release(struct bpf_sock *sock)

Do you explain what is bpf_sk_release(sk, 0)?

> 5: }
> 6: if (!sk)
> 7:   return 0;
> 8: return sk;

If sk has been released, the program should not really return sk, right?

> 
> 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.
> 
> Paul Chaignon (2):
>    bpf: mark registers as safe or unknown in all frames
>    selftests/bpf: test case for pointer null check in subprog
> 
>   kernel/bpf/verifier.c                        |  6 ++---
>   tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++++++++++++++++
>   2 files changed, 28 insertions(+), 3 deletions(-)
> 

Re: [PATCH bpf 0/2] bpf: mark registers as safe or unknown in all frames

[Paul Chaignon]

On Mon, Apr 22, 2019 04:57PM, Yonghong Song wrote: 
> On 4/20/19 5:38 AM, 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.  This first patch also marks registers in
> > previous frames.
> > 
> > A good reproducer 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, 0);
> 
> The specification for bpf_sk_release() in uapi/linux/bpf.h is:
>   int bpf_sk_release(struct bpf_sock *sock)
> 
> Do you explain what is bpf_sk_release(sk, 0)?

Thanks for the review Yonghong.  I think I took this extra argument by
mistake from the description of the commit introducing bpf_sk_release
(6acc9b432 ("bpf: Add helper to retrieve socket in BPF")).  I'll send a v2
with a fixed commit message.  Of course, the helper on line 1 also takes
arguments, so it might be better to write it as bpf_sk_lookup_tcp(...).

> 
> > 5: }
> > 6: if (!sk)
> > 7:   return 0;
> > 8: return sk;
> 
> If sk has been released, the program should not really return sk, right?

I'll change in v2.  I don't think it matters to reproduce the warning
though.  The verifier won't complain as the return value won't be
dereferenced and the register holding sk is readable.

> 
> > 
> > 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.
> > 
> > Paul Chaignon (2):
> >    bpf: mark registers as safe or unknown in all frames
> >    selftests/bpf: test case for pointer null check in subprog
> > 
> >   kernel/bpf/verifier.c                        |  6 ++---
> >   tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++++++++++++++++
> >   2 files changed, 28 insertions(+), 3 deletions(-)
> >