[bpf-next PATCH 0/4] verifier, improve ptr is_branch_taken logic

[bpf-next PATCH 0/4] verifier, improve ptr is_branch_taken logic

[John Fastabend]

Verifier logic to track pointer is_branch_taken logic to prune paths
that can not be taken. For many types we track if the pointer is null
or not. We can then use this information when calculating if branches
are taken when jump is comparing if pointer is null or not.

First patch is the verifier logic, patches 2/3 are tests for sock
pointers and map values. The final patch adds a printk to one of
the C test cases where the issue was initially reported. Feel free
to drop this if we think its overkill. OTOH it keeps a nice test
of a pattern folks might actually try and also doesn't add much in
the way of test overhead.

---

John Fastabend (4):
      bpf: verifier track null pointer branch_taken with JNE and JEQ
      bpf: selftests, verifier case for non null pointer check branch taken
      bpf: selftests, verifier case for non null pointer map value branch
      bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check


 .../selftests/bpf/progs/test_sk_lookup_kern.c      |    1 +
 .../testing/selftests/bpf/verifier/ref_tracking.c  |   16 ++++++++++++++++
 .../testing/selftests/bpf/verifier/value_or_null.c |   19 +++++++++++++++++++
 3 files changed, 36 insertions(+)

--
Signature

[bpf-next PATCH 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ

[John Fastabend]

Current verifier when considering which branch may be taken on a
conditional test with pointer returns -1 meaning either branch may
be taken. But, we track if pointers can be NULL by using dedicated
types for valid pointers (pointers that can not be NULL). For example,
we have PTR_TO_SOCK and PTR_TO_SOCK_OR_NULL to indicate a pointer
that is valid or not, PTR_TO_SOCK being the validated pointer type.

We can then use this extra information when we encounter null tests
against pointers. Consider,

  if (sk_ptr == NULL) ... else ...

if the sk_ptr has type PTR_TO_SOCK we know the null check will fail
and the null branch can not be taken.

In this patch we extend is_branch_taken to consider this extra
information and to return only the branch that will be taken. This
resolves a verifier issue reported with this C code,

 sk = bpf_sk_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0);
 bpf_printk("sk=%d\n", sk ? 1 : 0);
 if (sk)
   bpf_sk_release(sk);
 return sk ? TC_ACT_OK : TC_ACT_UNSPEC;

The generated asm then looks like this,

 43: (85) call bpf_sk_lookup_tcp#84
 44: (bf) r6 = r0                    <- do the lookup and put result in r6
 ...                                 <- do some more work
 51: (55) if r6 != 0x0 goto pc+1     <- test sk ptr for printk use
 ...
 56: (85) call bpf_trace_printk#6
 ...
 61: (15) if r6 == 0x0 goto pc+1     <- do the if (sk) test from C code
 62: (b7) r0 = 0                     <- skip release because both branches
                                        are taken in verifier
 63: (95) exit
 Unreleased reference id=3 alloc_insn=43

In the verifier path the flow is,

 51 -> 53 ... 61 -> 62

Because at 51->53 jmp verifier promoted reg6 from type PTR_TO_SOCK_OR_NULL
to PTR_TO_SOCK but then at 62 we still test both paths ignoring that we
already promoted the type. So we incorrectly conclude an unreleased
reference. To fix this we add logic in is_branch_taken to test the
OR_NULL portion of the type and if its not possible for a pointer to
be NULL we can prune the branch taken where 'r6 == 0x0'.

After the above additional logic is added the C code above passes
as expected.

This makes the assumption that all pointer types PTR_TO_* that can be null
have an equivalent type PTR_TO_*_OR_NULL logic.

Suggested-by: Alexei Starovoitov <ast@kernel.org>
Reported-by: Andrey Ignatov <rdna@fb.com>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 0 files changed

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 180933f..8f576e2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -393,6 +393,14 @@ static bool type_is_sk_pointer(enum bpf_reg_type type)
 		type == PTR_TO_XDP_SOCK;
 }
 
+static bool reg_type_not_null(enum bpf_reg_type type)
+{
+	return type == PTR_TO_SOCKET ||
+		type == PTR_TO_TCP_SOCK ||
+		type == PTR_TO_MAP_VALUE ||
+		type == PTR_TO_SOCK_COMMON;
+}
+
 static bool reg_type_may_be_null(enum bpf_reg_type type)
 {
 	return type == PTR_TO_MAP_VALUE_OR_NULL ||
@@ -1970,8 +1978,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
 	if (regno >= 0) {
 		reg = &func->regs[regno];
 		if (reg->type != SCALAR_VALUE) {
-			WARN_ONCE(1, "backtracing misuse");
-			return -EFAULT;
+			if (unlikely(!reg_type_not_null(reg->type)))
+				WARN_ONCE(1, "backtracing misuse");
+			return 0;
 		}
 		if (!reg->precise)
 			new_marks = true;
@@ -6306,8 +6315,26 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
 static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode,
 			   bool is_jmp32)
 {
-	if (__is_pointer_value(false, reg))
-		return -1;
+	if (__is_pointer_value(false, reg)) {
+		if (!reg_type_not_null(reg->type))
+			return -1;
+
+		/* If pointer is valid tests against zero will fail so we can
+		 * use this to direct branch taken.
+		 */
+		switch (opcode) {
+		case BPF_JEQ:
+			if (val == 0)
+				return 0;
+			return 1;
+		case BPF_JNE:
+			if (val == 0)
+				return 1;
+			return 0;
+		default:
+			return -1;
+		}
+	}
 
 	if (is_jmp32)
 		return is_branch32_taken(reg, val, opcode);

[bpf-next PATCH 2/4] bpf: selftests, verifier case for non null pointer check branch taken

[John Fastabend]

When we have pointer type that is known to be non-null we only follow
the non-null branch. This adds tests to cover this case for reference
tracking.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 .../testing/selftests/bpf/verifier/ref_tracking.c  |   16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/ref_tracking.c b/tools/testing/selftests/bpf/verifier/ref_tracking.c
index 604b461..d8f7c04 100644
--- a/tools/testing/selftests/bpf/verifier/ref_tracking.c
+++ b/tools/testing/selftests/bpf/verifier/ref_tracking.c
@@ -821,3 +821,19 @@
 	.result = REJECT,
 	.errstr = "invalid mem access",
 },
+{
+	"reference tracking: branch tracking valid pointer null comparison",
+	.insns = {
+	BPF_SK_LOOKUP(sk_lookup_tcp),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
+	BPF_MOV64_IMM(BPF_REG_3, 1),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 1),
+	BPF_MOV64_IMM(BPF_REG_3, 0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 2),
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+	BPF_EMIT_CALL(BPF_FUNC_sk_release),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.result = ACCEPT,
+},

[bpf-next PATCH 3/4] bpf: selftests, verifier case for non null pointer map value branch

[John Fastabend]

When we have pointer type that is known to be non-null we only follow
the non-null branch. This adds tests to cover the map_value pointer
returned from a map lookup. To force an error if both branches are
followed we do an ALU op on R10.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 .../testing/selftests/bpf/verifier/value_or_null.c |   19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/value_or_null.c b/tools/testing/selftests/bpf/verifier/value_or_null.c
index 860d4a7..3ecb70a 100644
--- a/tools/testing/selftests/bpf/verifier/value_or_null.c
+++ b/tools/testing/selftests/bpf/verifier/value_or_null.c
@@ -150,3 +150,22 @@
 	.result_unpriv = REJECT,
 	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
 },
+{
+	"map lookup and null branch prediction",
+	.insns = {
+	BPF_MOV64_IMM(BPF_REG_1, 10),
+	BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_1, -8),
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 2),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 1),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_10, 10),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 4 },
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.result = ACCEPT,
+},

[bpf-next PATCH 4/4] bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check

[John Fastabend]

Adding a printk to test_sk_lookup_kern created the reported failure
where a pointer type is checked twice for NULL. Lets add it to the
progs test test_sk_lookup_kern.c so we test the case from C all the
way into the verifier.

We already have printk's in selftests so seems OK to add another one.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 .../selftests/bpf/progs/test_sk_lookup_kern.c      |    1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c b/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c
index d2b38fa..e83d0b4 100644
--- a/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c
+++ b/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c
@@ -73,6 +73,7 @@ int bpf_sk_lookup_test0(struct __sk_buff *skb)
 
 	tuple_len = ipv4 ? sizeof(tuple->ipv4) : sizeof(tuple->ipv6);
 	sk = bpf_sk_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0);
+	bpf_printk("sk=%d\n", sk ? 1 : 0);
 	if (sk)
 		bpf_sk_release(sk);
 	return sk ? TC_ACT_OK : TC_ACT_UNSPEC;

RE: [bpf-next PATCH 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ

[John Fastabend]

John Fastabend wrote:
> Current verifier when considering which branch may be taken on a
> conditional test with pointer returns -1 meaning either branch may
> be taken. But, we track if pointers can be NULL by using dedicated
> types for valid pointers (pointers that can not be NULL). For example,
> we have PTR_TO_SOCK and PTR_TO_SOCK_OR_NULL to indicate a pointer
> that is valid or not, PTR_TO_SOCK being the validated pointer type.

[...]

> Because at 51->53 jmp verifier promoted reg6 from type PTR_TO_SOCK_OR_NULL
> to PTR_TO_SOCK but then at 62 we still test both paths ignoring that we
> already promoted the type. So we incorrectly conclude an unreleased
> reference. To fix this we add logic in is_branch_taken to test the
> OR_NULL portion of the type and if its not possible for a pointer to
> be NULL we can prune the branch taken where 'r6 == 0x0'.
> 
> After the above additional logic is added the C code above passes
> as expected.
> 
> This makes the assumption that all pointer types PTR_TO_* that can be null
> have an equivalent type PTR_TO_*_OR_NULL logic.

I can send a v2 to update the last sentence here it is not true with code
below. Initially I thought to negate reg_type_may_be_null() so that the
guard in the branch_taken on this logic was

 if (__is_pointer_value(false, reg)) {
    if (!reg_type_may_be_null(reg->type))
       return -1;

But this pulls in other pointers which are meaningless in this context.
For example PTR_TO_STACK, PTR_TO_BTF_ID, etc. I think its easier to avoid
thinking about these contexts and also safer to just be explicit and
built a new type filter, reg_type_not_null() below. Better name suggestions
welcome.

> 
> Suggested-by: Alexei Starovoitov <ast@kernel.org>
> Reported-by: Andrey Ignatov <rdna@fb.com>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>  0 files changed

With the v2 I'll fix this '0 files changed' issue here messed up my
branch mgmt a bit here when moving patches around.

Will wait a bit though to catch any other feedback.

Thanks,
John

> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 180933f..8f576e2 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -393,6 +393,14 @@ static bool type_is_sk_pointer(enum bpf_reg_type type)
>  		type == PTR_TO_XDP_SOCK;
>  }
>  
> +static bool reg_type_not_null(enum bpf_reg_type type)
> +{
k> +	return type == PTR_TO_SOCKET ||
> +		type == PTR_TO_TCP_SOCK ||
> +		type == PTR_TO_MAP_VALUE ||
> +		type == PTR_TO_SOCK_COMMON;
> +}
> +
>  static bool reg_type_may_be_null(enum bpf_reg_type type)
>  {
>  	return type == PTR_TO_MAP_VALUE_OR_NULL ||
> @@ -1970,8 +1978,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
>  	if (regno >= 0) {
>  		reg = &func->regs[regno];
>  		if (reg->type != SCALAR_VALUE) {
> -			WARN_ONCE(1, "backtracing misuse");
> -			return -EFAULT;
> +			if (unlikely(!reg_type_not_null(reg->type)))
> +				WARN_ONCE(1, "backtracing misuse");
> +			return 0;
>  		}
>  		if (!reg->precise)
>  			new_marks = true;
> @@ -6306,8 +6315,26 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>  static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode,
>  			   bool is_jmp32)
>  {
> -	if (__is_pointer_value(false, reg))
> -		return -1;
> +	if (__is_pointer_value(false, reg)) {
> +		if (!reg_type_not_null(reg->type))
> +			return -1;
> +
> +		/* If pointer is valid tests against zero will fail so we can
> +		 * use this to direct branch taken.
> +		 */
> +		switch (opcode) {
> +		case BPF_JEQ:
> +			if (val == 0)
> +				return 0;
> +			return 1;
> +		case BPF_JNE:
> +			if (val == 0)
> +				return 1;
> +			return 0;
> +		default:
> +			return -1;
> +		}
> +	}
>  
>  	if (is_jmp32)
>  		return is_branch32_taken(reg, val, opcode);
> 

Re: [bpf-next PATCH 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ

[Andrii Nakryiko]

On Mon, May 18, 2020 at 1:05 PM John Fastabend <john.fastabend@gmail.com> wrote:
>
> Current verifier when considering which branch may be taken on a
> conditional test with pointer returns -1 meaning either branch may
> be taken. But, we track if pointers can be NULL by using dedicated
> types for valid pointers (pointers that can not be NULL). For example,
> we have PTR_TO_SOCK and PTR_TO_SOCK_OR_NULL to indicate a pointer
> that is valid or not, PTR_TO_SOCK being the validated pointer type.
>
> We can then use this extra information when we encounter null tests
> against pointers. Consider,
>
>   if (sk_ptr == NULL) ... else ...
>
> if the sk_ptr has type PTR_TO_SOCK we know the null check will fail
> and the null branch can not be taken.
>
> In this patch we extend is_branch_taken to consider this extra
> information and to return only the branch that will be taken. This
> resolves a verifier issue reported with this C code,
>
>  sk = bpf_sk_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0);
>  bpf_printk("sk=%d\n", sk ? 1 : 0);
>  if (sk)
>    bpf_sk_release(sk);
>  return sk ? TC_ACT_OK : TC_ACT_UNSPEC;
>
> The generated asm then looks like this,
>
>  43: (85) call bpf_sk_lookup_tcp#84
>  44: (bf) r6 = r0                    <- do the lookup and put result in r6
>  ...                                 <- do some more work
>  51: (55) if r6 != 0x0 goto pc+1     <- test sk ptr for printk use
>  ...
>  56: (85) call bpf_trace_printk#6
>  ...
>  61: (15) if r6 == 0x0 goto pc+1     <- do the if (sk) test from C code
>  62: (b7) r0 = 0                     <- skip release because both branches
>                                         are taken in verifier
>  63: (95) exit
>  Unreleased reference id=3 alloc_insn=43
>

bpf_sk_release call in above assembler would be really nice for
completeness. As written, this code never calls and never will call
bpf_sk_release().

> In the verifier path the flow is,
>
>  51 -> 53 ... 61 -> 62
>
> Because at 51->53 jmp verifier promoted reg6 from type PTR_TO_SOCK_OR_NULL
> to PTR_TO_SOCK but then at 62 we still test both paths ignoring that we

Seems like your description got a bit out of sync with the code above.
There is no line 53, check is actually on line 61, not 62, etc. Can
you please update it in your v2 as well?

> already promoted the type. So we incorrectly conclude an unreleased
> reference. To fix this we add logic in is_branch_taken to test the
> OR_NULL portion of the type and if its not possible for a pointer to
> be NULL we can prune the branch taken where 'r6 == 0x0'.
>
> After the above additional logic is added the C code above passes
> as expected.
>
> This makes the assumption that all pointer types PTR_TO_* that can be null
> have an equivalent type PTR_TO_*_OR_NULL logic.
>
> Suggested-by: Alexei Starovoitov <ast@kernel.org>
> Reported-by: Andrey Ignatov <rdna@fb.com>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>  0 files changed
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 180933f..8f576e2 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -393,6 +393,14 @@ static bool type_is_sk_pointer(enum bpf_reg_type type)
>                 type == PTR_TO_XDP_SOCK;
>  }
>
> +static bool reg_type_not_null(enum bpf_reg_type type)
> +{
> +       return type == PTR_TO_SOCKET ||
> +               type == PTR_TO_TCP_SOCK ||
> +               type == PTR_TO_MAP_VALUE ||
> +               type == PTR_TO_SOCK_COMMON;

PTR_TO_BTF_ID should probably be here as well (we do have
PTR_TO_BTF_ID_OR_NULL now).

> +}
> +
>  static bool reg_type_may_be_null(enum bpf_reg_type type)
>  {
>         return type == PTR_TO_MAP_VALUE_OR_NULL ||
> @@ -1970,8 +1978,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
>         if (regno >= 0) {
>                 reg = &func->regs[regno];
>                 if (reg->type != SCALAR_VALUE) {
> -                       WARN_ONCE(1, "backtracing misuse");
> -                       return -EFAULT;
> +                       if (unlikely(!reg_type_not_null(reg->type)))
> +                               WARN_ONCE(1, "backtracing misuse");
> +                       return 0;

I think it's safer to instead add check in check_cond_jmp_op, in case
branch is known, to only mark precision if register is not a non-null
pointer. __mark_chain_precision is used in many places, so it's better
to guard against this particular situation and leave warning for
general case, IMO.

>                 }
>                 if (!reg->precise)
>                         new_marks = true;
> @@ -6306,8 +6315,26 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>  static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode,
>                            bool is_jmp32)
>  {
> -       if (__is_pointer_value(false, reg))
> -               return -1;
> +       if (__is_pointer_value(false, reg)) {
> +               if (!reg_type_not_null(reg->type))
> +                       return -1;
> +
> +               /* If pointer is valid tests against zero will fail so we can
> +                * use this to direct branch taken.
> +                */
> +               switch (opcode) {
> +               case BPF_JEQ:
> +                       if (val == 0)
> +                               return 0;
> +                       return 1;

if val != 0, then we can't really tell whether point is equal to our
scalar or not, right? What if we leaked pointer into a global
variable, now we are checking against that stored value? It can go
both ways. So unless I'm missing something, it should be -1 here.

> +               case BPF_JNE:
> +                       if (val == 0)
> +                               return 1;
> +                       return 0;

same here, unless value we compare against is zero, we can't really
tell for sure, so -1?


> +               default:
> +                       return -1;
> +               }
> +       }
>
>         if (is_jmp32)
>                 return is_branch32_taken(reg, val, opcode);
>

Re: [bpf-next PATCH 0/4] verifier, improve ptr is_branch_taken logic

[Andrii Nakryiko]

On Mon, May 18, 2020 at 1:05 PM John Fastabend <john.fastabend@gmail.com> wrote:
>
> Verifier logic to track pointer is_branch_taken logic to prune paths
> that can not be taken. For many types we track if the pointer is null

I re-read first sentence many times, still not sure what it is saying.
Do you mind rephrasing it a bit for clarity? Thanks!

> or not. We can then use this information when calculating if branches
> are taken when jump is comparing if pointer is null or not.
>
> First patch is the verifier logic, patches 2/3 are tests for sock
> pointers and map values. The final patch adds a printk to one of
> the C test cases where the issue was initially reported. Feel free
> to drop this if we think its overkill. OTOH it keeps a nice test
> of a pattern folks might actually try and also doesn't add much in
> the way of test overhead.
>
> ---
>
> John Fastabend (4):
>       bpf: verifier track null pointer branch_taken with JNE and JEQ
>       bpf: selftests, verifier case for non null pointer check branch taken
>       bpf: selftests, verifier case for non null pointer map value branch
>       bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check
>
>
>  .../selftests/bpf/progs/test_sk_lookup_kern.c      |    1 +
>  .../testing/selftests/bpf/verifier/ref_tracking.c  |   16 ++++++++++++++++
>  .../testing/selftests/bpf/verifier/value_or_null.c |   19 +++++++++++++++++++
>  3 files changed, 36 insertions(+)
>
> --
> Signature

Re: [bpf-next PATCH 2/4] bpf: selftests, verifier case for non null pointer check branch taken

[Andrii Nakryiko]

On Mon, May 18, 2020 at 1:06 PM John Fastabend <john.fastabend@gmail.com> wrote:
>
> When we have pointer type that is known to be non-null we only follow
> the non-null branch. This adds tests to cover this case for reference
> tracking.
>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>  .../testing/selftests/bpf/verifier/ref_tracking.c  |   16 ++++++++++++++++
>  1 file changed, 16 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/verifier/ref_tracking.c b/tools/testing/selftests/bpf/verifier/ref_tracking.c
> index 604b461..d8f7c04 100644
> --- a/tools/testing/selftests/bpf/verifier/ref_tracking.c
> +++ b/tools/testing/selftests/bpf/verifier/ref_tracking.c
> @@ -821,3 +821,19 @@
>         .result = REJECT,
>         .errstr = "invalid mem access",
>  },
> +{
> +       "reference tracking: branch tracking valid pointer null comparison",
> +       .insns = {
> +       BPF_SK_LOOKUP(sk_lookup_tcp),
> +       BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
> +       BPF_MOV64_IMM(BPF_REG_3, 1),
> +       BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 1),
> +       BPF_MOV64_IMM(BPF_REG_3, 0),
> +       BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 2),
> +       BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
> +       BPF_EMIT_CALL(BPF_FUNC_sk_release),
> +       BPF_EXIT_INSN(),
> +       },
> +       .prog_type = BPF_PROG_TYPE_SCHED_CLS,
> +       .result = ACCEPT,
> +},

Can you please add another test where you test against non-zero value
to verify that both branches are considered to be taken and verifier
actually complaints that sk_release happens only in one of branches.

>

Re: [bpf-next PATCH 4/4] bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check

[Andrii Nakryiko]

On Mon, May 18, 2020 at 1:05 PM John Fastabend <john.fastabend@gmail.com> wrote:
>
> Adding a printk to test_sk_lookup_kern created the reported failure
> where a pointer type is checked twice for NULL. Lets add it to the
> progs test test_sk_lookup_kern.c so we test the case from C all the
> way into the verifier.
>
> We already have printk's in selftests so seems OK to add another one.
>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---

Yeah, I think it's fine.

Acked-by: Andrii Nakryiko <andriin@fb.com>

>  .../selftests/bpf/progs/test_sk_lookup_kern.c      |    1 +
>  1 file changed, 1 insertion(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c b/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c
> index d2b38fa..e83d0b4 100644
> --- a/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c
> +++ b/tools/testing/selftests/bpf/progs/test_sk_lookup_kern.c
> @@ -73,6 +73,7 @@ int bpf_sk_lookup_test0(struct __sk_buff *skb)
>
>         tuple_len = ipv4 ? sizeof(tuple->ipv4) : sizeof(tuple->ipv6);
>         sk = bpf_sk_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0);
> +       bpf_printk("sk=%d\n", sk ? 1 : 0);
>         if (sk)
>                 bpf_sk_release(sk);
>         return sk ? TC_ACT_OK : TC_ACT_UNSPEC;
>

Re: [bpf-next PATCH 3/4] bpf: selftests, verifier case for non null pointer map value branch

[Andrii Nakryiko]

On Mon, May 18, 2020 at 1:07 PM John Fastabend <john.fastabend@gmail.com> wrote:
>
> When we have pointer type that is known to be non-null we only follow
> the non-null branch. This adds tests to cover the map_value pointer
> returned from a map lookup. To force an error if both branches are
> followed we do an ALU op on R10.
>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---

LGTM. Here likelihood of someone comparing map value pointer against
non-zero scalar is much less likely, so I won't bother you to add test
for that.

Acked-by: Andrii Nakryiko <andriin@fb.com>


>  .../testing/selftests/bpf/verifier/value_or_null.c |   19 +++++++++++++++++++
>  1 file changed, 19 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/verifier/value_or_null.c b/tools/testing/selftests/bpf/verifier/value_or_null.c
> index 860d4a7..3ecb70a 100644
> --- a/tools/testing/selftests/bpf/verifier/value_or_null.c
> +++ b/tools/testing/selftests/bpf/verifier/value_or_null.c
> @@ -150,3 +150,22 @@
>         .result_unpriv = REJECT,
>         .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
>  },
> +{
> +       "map lookup and null branch prediction",
> +       .insns = {
> +       BPF_MOV64_IMM(BPF_REG_1, 10),
> +       BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_1, -8),
> +       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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
> +       BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
> +       BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 2),
> +       BPF_JMP_IMM(BPF_JNE, BPF_REG_6, 0, 1),
> +       BPF_ALU64_IMM(BPF_ADD, BPF_REG_10, 10),
> +       BPF_EXIT_INSN(),
> +       },
> +       .fixup_map_hash_8b = { 4 },
> +       .prog_type = BPF_PROG_TYPE_SCHED_CLS,
> +       .result = ACCEPT,
> +},
>

Re: [bpf-next PATCH 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ

[John Fastabend]

Andrii Nakryiko wrote:
> On Mon, May 18, 2020 at 1:05 PM John Fastabend <john.fastabend@gmail.com> wrote:
> >
> > Current verifier when considering which branch may be taken on a
> > conditional test with pointer returns -1 meaning either branch may
> > be taken. But, we track if pointers can be NULL by using dedicated
> > types for valid pointers (pointers that can not be NULL). For example,
> > we have PTR_TO_SOCK and PTR_TO_SOCK_OR_NULL to indicate a pointer
> > that is valid or not, PTR_TO_SOCK being the validated pointer type.
> >
> > We can then use this extra information when we encounter null tests
> > against pointers. Consider,
> >
> >   if (sk_ptr == NULL) ... else ...
> >
> > if the sk_ptr has type PTR_TO_SOCK we know the null check will fail
> > and the null branch can not be taken.
> >
> > In this patch we extend is_branch_taken to consider this extra
> > information and to return only the branch that will be taken. This
> > resolves a verifier issue reported with this C code,
> >
> >  sk = bpf_sk_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0);
> >  bpf_printk("sk=%d\n", sk ? 1 : 0);
> >  if (sk)
> >    bpf_sk_release(sk);
> >  return sk ? TC_ACT_OK : TC_ACT_UNSPEC;
> >
> > The generated asm then looks like this,
> >
> >  43: (85) call bpf_sk_lookup_tcp#84
> >  44: (bf) r6 = r0                    <- do the lookup and put result in r6
> >  ...                                 <- do some more work
> >  51: (55) if r6 != 0x0 goto pc+1     <- test sk ptr for printk use
> >  ...
> >  56: (85) call bpf_trace_printk#6
> >  ...
> >  61: (15) if r6 == 0x0 goto pc+1     <- do the if (sk) test from C code
> >  62: (b7) r0 = 0                     <- skip release because both branches
> >                                         are taken in verifier
> >  63: (95) exit
> >  Unreleased reference id=3 alloc_insn=43
> >
> 
> bpf_sk_release call in above assembler would be really nice for
> completeness. As written, this code never calls and never will call
> bpf_sk_release().
> 
> > In the verifier path the flow is,
> >
> >  51 -> 53 ... 61 -> 62
> >
> > Because at 51->53 jmp verifier promoted reg6 from type PTR_TO_SOCK_OR_NULL
> > to PTR_TO_SOCK but then at 62 we still test both paths ignoring that we
> 
> Seems like your description got a bit out of sync with the code above.
> There is no line 53, check is actually on line 61, not 62, etc. Can
> you please update it in your v2 as well?

Will do a rewrite.

> 
> > already promoted the type. So we incorrectly conclude an unreleased
> > reference. To fix this we add logic in is_branch_taken to test the
> > OR_NULL portion of the type and if its not possible for a pointer to
> > be NULL we can prune the branch taken where 'r6 == 0x0'.
> >
> > After the above additional logic is added the C code above passes
> > as expected.
> >
> > This makes the assumption that all pointer types PTR_TO_* that can be null
> > have an equivalent type PTR_TO_*_OR_NULL logic.
> >
> > Suggested-by: Alexei Starovoitov <ast@kernel.org>
> > Reported-by: Andrey Ignatov <rdna@fb.com>
> > Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> > ---
> >  0 files changed
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 180933f..8f576e2 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -393,6 +393,14 @@ static bool type_is_sk_pointer(enum bpf_reg_type type)
> >                 type == PTR_TO_XDP_SOCK;
> >  }
> >
> > +static bool reg_type_not_null(enum bpf_reg_type type)
> > +{
> > +       return type == PTR_TO_SOCKET ||
> > +               type == PTR_TO_TCP_SOCK ||
> > +               type == PTR_TO_MAP_VALUE ||
> > +               type == PTR_TO_SOCK_COMMON;
> 
> PTR_TO_BTF_ID should probably be here as well (we do have
> PTR_TO_BTF_ID_OR_NULL now).

OK.

> 
> > +}
> > +
> >  static bool reg_type_may_be_null(enum bpf_reg_type type)
> >  {
> >         return type == PTR_TO_MAP_VALUE_OR_NULL ||
> > @@ -1970,8 +1978,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> >         if (regno >= 0) {
> >                 reg = &func->regs[regno];
> >                 if (reg->type != SCALAR_VALUE) {
> > -                       WARN_ONCE(1, "backtracing misuse");
> > -                       return -EFAULT;
> > +                       if (unlikely(!reg_type_not_null(reg->type)))
> > +                               WARN_ONCE(1, "backtracing misuse");
> > +                       return 0;
> 
> I think it's safer to instead add check in check_cond_jmp_op, in case
> branch is known, to only mark precision if register is not a non-null
> pointer. __mark_chain_precision is used in many places, so it's better
> to guard against this particular situation and leave warning for
> general case, IMO.

Sure.

> 
> >                 }
> >                 if (!reg->precise)
> >                         new_marks = true;
> > @@ -6306,8 +6315,26 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
> >  static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode,
> >                            bool is_jmp32)
> >  {
> > -       if (__is_pointer_value(false, reg))
> > -               return -1;
> > +       if (__is_pointer_value(false, reg)) {
> > +               if (!reg_type_not_null(reg->type))
> > +                       return -1;
> > +
> > +               /* If pointer is valid tests against zero will fail so we can
> > +                * use this to direct branch taken.
> > +                */
> > +               switch (opcode) {
> > +               case BPF_JEQ:
> > +                       if (val == 0)
> > +                               return 0;
> > +                       return 1;
> 
> if val != 0, then we can't really tell whether point is equal to our
> scalar or not, right? What if we leaked pointer into a global
> variable, now we are checking against that stored value? It can go
> both ways. So unless I'm missing something, it should be -1 here.

Correct it should be -1 thanks. Probably worth adding a test for this case
as well.

> 
> > +               case BPF_JNE:
> > +                       if (val == 0)
> > +                               return 1;
> > +                       return 0;
> 
> same here, unless value we compare against is zero, we can't really
> tell for sure, so -1?
> 

Correct thanks.

> 
> > +               default:
> > +                       return -1;
> > +               }
> > +       }
> >
> >         if (is_jmp32)
> >                 return is_branch32_taken(reg, val, opcode);
> >