Skip to contentSkip to conversation

bpf: fix an incorrect branch elimination by verifier

PATCH In review Yonghong Song 5 participants 13 messages Jun 30, 2020

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

cover bpf: fix an incorrect branch elimination by verifier

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

As an illustration of original issue, consider the following example:

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;

}
In the xlated byte code, "arg->a == 0" condition is evaluted always false and "test8_result = 1" is removed.

This is not right. Patch #1 shows why this happens and how to fix it in verifier. Patch #2 added two subtests in test_progs to catch such cases.

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Yonghong Song (2):
bpf: fix an incorrect branch elimination by verifier
bpf: add tests for PTR_TO_BTF_ID vs. null comparison

 kernel/bpf/verifier.c                         |  3 +--
 net/bpf/test_run.c                            | 19 +++++++++++++++-
 .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
 .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
 .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
 5 files changed, 64 insertions(+), 4 deletions(-)
Signature · 1 line
2.24.1
#1 lore raw

PATCH 1/2 bpf: fix an incorrect branch elimination by verifier

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;
 }
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

We may not want to assign every PTR_TO_BTF_ID as PTR_TO_BTF_ID_OR_NULL as this will require a null test before pointer dereference which may cause inconvenience for developers. But we could avoid branch elimination to preserve original code intention.

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null() in verifier, which prevented the above branches from being eliminated.

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Fixes cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>
---
 kernel/bpf/verifier.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -2
index 8911d0576399..94cead5a43e5 100644
@@ -399,8 +399,7 @@ 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 ||
-	        type == PTR_TO_BTF_ID;
+		type == PTR_TO_SOCK_COMMON;
 }
 
 static bool reg_type_may_be_null(enum bpf_reg_type type)
Signature · 1 line
2.24.1
#2 lore raw
Quoted 37 lines · Yonghong Song

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;
 }
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

Quoted 5 lines

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

Thanks for fixing this.

But, don't we really need to check for null? I'm trying to understand how we can avoid the check. If b is NULL above we will have a problem no?

Also, we probably shouldn't name the type PTR_TO_BTF_ID if it can be NULL. How about renaming it in bpf-next then although it will be code churn... Or just fix the comments? Probably bpf-next content though. wdyt? In my opinion the comments and type names are really misleading as it stands.

include/linux/bpf.h +1 -1
index 3d2ade703a35..18051440f886 100644
@@ -337,7 +337,7 @@ enum bpf_reg_type {
 	PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
 	PTR_TO_TP_BUFFER,	 /* reg points to a writable raw tp's buffer */
 	PTR_TO_XDP_SOCK,	 /* reg points to struct xdp_sock */
-	PTR_TO_BTF_ID,		 /* reg points to kernel struct */
+	PTR_TO_BTF_ID,		 /* reg points to kernel struct or NULL */
 	PTR_TO_BTF_ID_OR_NULL,	 /* reg points to kernel struct or NULL */
 	PTR_TO_MEM,		 /* reg points to valid memory region */
 	PTR_TO_MEM_OR_NULL,	 /* reg points to valid memory region or NULL */
kernel/bpf/verifier.c +1 -1
index 7de98906ddf4..7412f9d2f0b5 100644
@@ -500,7 +500,7 @@ static const char * const reg_type_str[] = {
 	[PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
 	[PTR_TO_TP_BUFFER]	= "tp_buffer",
 	[PTR_TO_XDP_SOCK]	= "xdp_sock",
-	[PTR_TO_BTF_ID]		= "ptr_",
+	[PTR_TO_BTF_ID]		= "ptr_or_null_",
 	[PTR_TO_BTF_ID_OR_NULL]	= "ptr_or_null_",
 	[PTR_TO_MEM]		= "mem",
 	[PTR_TO_MEM_OR_NULL]	= "mem_or_null",
Quoted 38 lines

We may not want to assign every PTR_TO_BTF_ID as PTR_TO_BTF_ID_OR_NULL as this will require a null test before pointer dereference which may cause inconvenience for developers. But we could avoid branch elimination to preserve original code intention.

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null() in verifier, which prevented the above branches from being eliminated.

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Fixes cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>
---
 kernel/bpf/verifier.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -2
index 8911d0576399..94cead5a43e5 100644
@@ -399,8 +399,7 @@ 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 ||
-	        type == PTR_TO_BTF_ID;
+		type == PTR_TO_SOCK_COMMON;
 }
 
 static bool reg_type_may_be_null(enum bpf_reg_type type)
Signature · 1 line
2.24.1
#3 lore raw
Quoted 44 lines · John Fastabend
Quoted 37 lines · Yonghong Song

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

  struct bpf_fentry_test_t {
      struct bpf_fentry_test_t *a;
  };
  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
  {
      if (arg == 0)
          test7_result = 1;
      return 0;
  }
  int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
  {
      if (arg->a == 0)
          test8_result = 1;
      return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

Quoted 5 lines

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

Quoted 5 lines

Thanks for fixing this.

But, don't we really need to check for null? I'm trying to understand how we can avoid the check. If b is NULL above we will have a problem no?

It depends with particular data structure.
If users are sure once pointer 'a' is valid and a->b, a->b->c, a->b->c are all valid pointers, user may just write a->b->c->d. this happens to some bcc scripts. So non-null pointer is checked.

But if user thinks a->b->c is null, he may write
type *p = a->b->c;
if (p)

       p->d;

Or user just takes advantage of kernel bpf guarded exception handling and do a->b->c->d even if a->b->c could be null. if the result is 0, it means a->b->c is null or major fault,
otherwise it is not 0.

Quoted 6 lines

Also, we probably shouldn't name the type PTR_TO_BTF_ID if it can be NULL. How about renaming it in bpf-next then although it will be code churn... Or just fix the comments? Probably bpf-next content though. wdyt? In my opinion the comments and type names are really misleading as it stands.

So PTR_TO_BTF_ID actually means it may be null but not checking is enforced and pointer tracing is always allowed. PTR_TO_BTF_ID_OR_NULL means it may be null and checking against NULL is needed to allow further pointer tracing.

To avoid code churn, we can add these comments in bpf-next.

Quoted 66 lines
include/linux/bpf.h +1 -1
index 3d2ade703a35..18051440f886 100644
@@ -337,7 +337,7 @@ enum bpf_reg_type {
  	PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
  	PTR_TO_TP_BUFFER,	 /* reg points to a writable raw tp's buffer */
  	PTR_TO_XDP_SOCK,	 /* reg points to struct xdp_sock */
-	PTR_TO_BTF_ID,		 /* reg points to kernel struct */
+	PTR_TO_BTF_ID,		 /* reg points to kernel struct or NULL */
  	PTR_TO_BTF_ID_OR_NULL,	 /* reg points to kernel struct or NULL */
  	PTR_TO_MEM,		 /* reg points to valid memory region */
  	PTR_TO_MEM_OR_NULL,	 /* reg points to valid memory region or NULL */
kernel/bpf/verifier.c +1 -1
index 7de98906ddf4..7412f9d2f0b5 100644
@@ -500,7 +500,7 @@ static const char * const reg_type_str[] = {
  	[PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
  	[PTR_TO_TP_BUFFER]	= "tp_buffer",
  	[PTR_TO_XDP_SOCK]	= "xdp_sock",
-	[PTR_TO_BTF_ID]		= "ptr_",
+	[PTR_TO_BTF_ID]		= "ptr_or_null_",
  	[PTR_TO_BTF_ID_OR_NULL]	= "ptr_or_null_",
  	[PTR_TO_MEM]		= "mem",
  	[PTR_TO_MEM_OR_NULL]	= "mem_or_null",
Quoted 39 lines

We may not want to assign every PTR_TO_BTF_ID as PTR_TO_BTF_ID_OR_NULL as this will require a null test before pointer dereference which may cause inconvenience for developers. But we could avoid branch elimination to preserve original code intention.

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null() in verifier, which prevented the above branches from being eliminated.

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Fixes cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>
---
  kernel/bpf/verifier.c | 3 +--
  1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -2
index 8911d0576399..94cead5a43e5 100644
@@ -399,8 +399,7 @@ 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 ||
-	        type == PTR_TO_BTF_ID;
+		type == PTR_TO_SOCK_COMMON;
  }
 
  static bool reg_type_may_be_null(enum bpf_reg_type type)
Signature · 1 line
2.24.1
reviewer Acked-by
#4 lore raw
Quoted 59 lines · Yonghong Song
Quoted 44 lines · John Fastabend
Quoted 37 lines · Yonghong Song

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

  struct bpf_fentry_test_t {
      struct bpf_fentry_test_t *a;
  };
  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
  {
      if (arg == 0)
          test7_result = 1;
      return 0;
  }
  int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
  {
      if (arg->a == 0)
          test8_result = 1;
      return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

Quoted 5 lines

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

Quoted 5 lines

Thanks for fixing this.

But, don't we really need to check for null? I'm trying to understand how we can avoid the check. If b is NULL above we will have a problem no?

It depends with particular data structure.
If users are sure once pointer 'a' is valid and a->b, a->b->c, a->b->c are all valid pointers, user may just write a->b->c->d. this happens to some bcc scripts. So non-null pointer is checked.

But if user thinks a->b->c is null, he may write

Quoted 8 lines
    type *p = a->b->c;
    if (p)
        p->d;

Or user just takes advantage of kernel bpf guarded exception handling and do a->b->c->d even if a->b->c could be null.
if the result is 0, it means a->b->c is null or major fault, otherwise it is not 0.

OK.

Quoted 8 lines
Quoted 7 lines

Also, we probably shouldn't name the type PTR_TO_BTF_ID if it can be NULL. How about renaming it in bpf-next then although it will be code churn... Or just fix the comments? Probably bpf-next content though. wdyt? In my opinion the comments and type names are really misleading as it stands.

Quoted 6 lines

So PTR_TO_BTF_ID actually means it may be null but not checking is enforced and pointer tracing is always allowed. PTR_TO_BTF_ID_OR_NULL means it may be null and checking against NULL is needed to allow further pointer tracing.

To avoid code churn, we can add these comments in bpf-next.

Agreed code churn would be not worth changing type but I'll send some patches for the comment changes.

Quoted 36 lines
Quoted 36 lines
include/linux/bpf.h +1 -1
index 3d2ade703a35..18051440f886 100644
@@ -337,7 +337,7 @@ enum bpf_reg_type {
  	PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
  	PTR_TO_TP_BUFFER,	 /* reg points to a writable raw tp's buffer */
  	PTR_TO_XDP_SOCK,	 /* reg points to struct xdp_sock */
-	PTR_TO_BTF_ID,		 /* reg points to kernel struct */
+	PTR_TO_BTF_ID,		 /* reg points to kernel struct or NULL */
  	PTR_TO_BTF_ID_OR_NULL,	 /* reg points to kernel struct or NULL */
  	PTR_TO_MEM,		 /* reg points to valid memory region */
  	PTR_TO_MEM_OR_NULL,	 /* reg points to valid memory region or NULL */
kernel/bpf/verifier.c +1 -1
index 7de98906ddf4..7412f9d2f0b5 100644
@@ -500,7 +500,7 @@ static const char * const reg_type_str[] = {
  	[PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
  	[PTR_TO_TP_BUFFER]	= "tp_buffer",
  	[PTR_TO_XDP_SOCK]	= "xdp_sock",
-	[PTR_TO_BTF_ID]		= "ptr_",
+	[PTR_TO_BTF_ID]		= "ptr_or_null_",
  	[PTR_TO_BTF_ID_OR_NULL]	= "ptr_or_null_",
  	[PTR_TO_MEM]		= "mem",
  	[PTR_TO_MEM_OR_NULL]	= "mem_or_null",
Quoted 8 lines

We may not want to assign every PTR_TO_BTF_ID as PTR_TO_BTF_ID_OR_NULL as this will require a null test before pointer dereference which may cause inconvenience for developers. But we could avoid branch elimination to preserve original code intention.

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null() in verifier, which prevented the above branches from being eliminated.

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Fixes cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")

I added the BTF_ID in v2 of those patches :/ too bad. Thanks again for catching it.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>

---

Quoted 20 lines
Quoted 20 lines
Quoted 20 lines
  kernel/bpf/verifier.c | 3 +--
  1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -2
index 8911d0576399..94cead5a43e5 100644
@@ -399,8 +399,7 @@ 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 ||
-	        type == PTR_TO_BTF_ID;
+		type == PTR_TO_SOCK_COMMON;
  }
 
  static bool reg_type_may_be_null(enum bpf_reg_type type)
Signature · 1 line
2.24.1
#5 lore raw
Quoted 12 lines · John Fastabend
Quoted 12 lines
Quoted 6 lines

Also, we probably shouldn't name the type PTR_TO_BTF_ID if it can be NULL. How about renaming it in bpf-next then although it will be code churn... Or just fix the comments? Probably bpf-next content though. wdyt? In my opinion the comments and type names are really misleading as it stands.

So PTR_TO_BTF_ID actually means it may be null but not checking is enforced and pointer tracing is always allowed. PTR_TO_BTF_ID_OR_NULL means it may be null and checking against NULL is needed to allow further pointer tracing.

Quoted 4 lines
Quoted 1 line

To avoid code churn, we can add these comments in bpf-next.

Agreed code churn would be not worth changing type but I'll send some patches for the comment changes.

+1
I think for bpf tree the minimal fix is better.
So I've applied this set.
A follow up to bpf-next after bpf->net->linus->net-next->bpf-next would be really good.
We'll make sure that all trees converge soon.

#6 lore raw
In reply to John Fastabend
Quoted 45 lines · John Fastabend
Quoted 37 lines · Yonghong Song

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;
 }
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

Quoted 5 lines

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

Quoted 5 lines

Thanks for fixing this.

But, don't we really need to check for null? I'm trying to understand how we can avoid the check. If b is NULL above we will have a problem no?

BPF JIT installs an exception handler for each direct memory access, so that if it turns out to be NULL, it will be caught and 0 will be assigned to the target register and BPF program will continue execution. In that sense, it simulates bpf_probe_read() behavior and significantly improves usability.

Quoted 7 lines

Also, we probably shouldn't name the type PTR_TO_BTF_ID if it can be NULL. How about renaming it in bpf-next then although it will be code churn... Or just fix the comments? Probably bpf-next content though. wdyt? In my opinion the comments and type names are really misleading as it stands.

[...]

Acked-by on v1 1/2
#7 lore raw
In reply to Yonghong Song
Quoted 53 lines · Yonghong Song

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;
 }
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

We may not want to assign every PTR_TO_BTF_ID as PTR_TO_BTF_ID_OR_NULL as this will require a null test before pointer dereference which may cause inconvenience for developers. But we could avoid branch elimination to preserve original code intention.

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null() in verifier, which prevented the above branches from being eliminated.

Quoted 8 lines

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Fixes cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>

---

You missed Reported-by: tag, please add.

Otherwise lgtm, thanks for fixing!

Quoted 20 lines
 kernel/bpf/verifier.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -3
index 8911d0576399..94cead5a43e5 100644
@@ -399,8 +399,7 @@ 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 ||
-               type == PTR_TO_BTF_ID;
+               type == PTR_TO_SOCK_COMMON;
 }
 
 static bool reg_type_may_be_null(enum bpf_reg_type type)
--

2.24.1

maintainer
#8 lore raw
Quoted 56 lines · Andrii Nakryiko
Quoted 55 lines · Yonghong Song

Wenbo reported an issue in [1] where a checking of null pointer is evaluated as always false. In this particular case, the program type is tp_btf and the pointer to compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always reprents a non-null pointer, hence all PTR_TO_BTF_ID compares to 0 will be evaluated as always not-equal, which resulted in the branch elimination.

For example,

  struct bpf_fentry_test_t {
      struct bpf_fentry_test_t *a;
  };
  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
  {
      if (arg == 0)
          test7_result = 1;
      return 0;
  }
  int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
  {
      if (arg->a == 0)
          test8_result = 1;
      return 0;

}

In above bpf programs, both branch arg == 0 and arg->a == 0 are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ"), where PTR_TO_BTF_ID is considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we have PTR_TO_BTF_ID_OR_NULL in the verifier as well.

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assigns PTR_TO_BTF_ID so users does not need to check NULL pointer at every pointer level like a->b->c->d.

We may not want to assign every PTR_TO_BTF_ID as PTR_TO_BTF_ID_OR_NULL as this will require a null test before pointer dereference which may cause inconvenience for developers. But we could avoid branch elimination to preserve original code intention.

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null() in verifier, which prevented the above branches from being eliminated.

[1]: https://lore.kernel.org/bpf/[email protected]/T/

Quoted 8 lines
Quoted 6 lines
Fixes cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>

---

You missed Reported-by: tag, please add.

Agree, fixed up manually (and also pulled in your ACKs, Andrii).

Thanks,
Daniel

#9 lore raw

PATCH 2/2 bpf: add tests for PTR_TO_BTF_ID vs. null comparison

In reply to Yonghong Song

Add two tests for PTR_TO_BTF_ID vs. null ptr comparison, one for PTR_TO_BTF_ID in the ctx structure and the other for PTR_TO_BTF_ID after one level pointer chasing. In both cases, the test ensures condition is not removed.

For example, for this test

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;

}
Before the previous verifier change, we have xlated codes:
int test7(long long unsigned int * ctx):
; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)

     0: (79) r1 = *(u64 *)(r1 +0)
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     1: (b4) w0 = 0
     2: (95) exit
After the previous verifier change, we have:
  int test7(long long unsigned int * ctx):
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     0: (79) r1 = *(u64 *)(r1 +0)
  ; if (arg == 0)
     1: (55) if r1 != 0x0 goto pc+4
  ; test7_result = 1;
     2: (18) r1 = map[id:6][0]+48
     4: (b7) r2 = 1
     5: (7b) *(u64 *)(r1 +0) = r2
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     6: (b4) w0 = 0
     7: (95) exit
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>
---
 net/bpf/test_run.c                            | 19 +++++++++++++++-
 .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
 .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
 .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
 4 files changed, 63 insertions(+), 2 deletions(-)
net/bpf/test_run.c +18 -1
index bfd4ccd80847..b03c469cd01f 100644
@@ -147,6 +147,20 @@ int noinline bpf_fentry_test6(u64 a, void *b, short c, int d, void *e, u64 f)
 	return a + (long)b + c + d + (long)e + f;
 }
 
+struct bpf_fentry_test_t {
+	struct bpf_fentry_test_t *a;
+};
+
+int noinline bpf_fentry_test7(struct bpf_fentry_test_t *arg)
+{
+	return (long)arg;
+}
+
+int noinline bpf_fentry_test8(struct bpf_fentry_test_t *arg)
+{
+	return (long)arg->a;
+}
+
 int noinline bpf_modify_return_test(int a, int *b)
 {
 	*b += 1;
@@ -185,6 +199,7 @@ int bpf_prog_test_run_tracing(struct bpf_prog *prog,
 			      const union bpf_attr *kattr,
 			      union bpf_attr __user *uattr)
 {
+	struct bpf_fentry_test_t arg = {};
 	u16 side_effect = 0, ret = 0;
 	int b = 2, err = -EFAULT;
 	u32 retval = 0;
@@ -197,7 +212,9 @@ int bpf_prog_test_run_tracing(struct bpf_prog *prog,
 		    bpf_fentry_test3(4, 5, 6) != 15 ||
 		    bpf_fentry_test4((void *)7, 8, 9, 10) != 34 ||
 		    bpf_fentry_test5(11, (void *)12, 13, 14, 15) != 65 ||
-		    bpf_fentry_test6(16, (void *)17, 18, 19, (void *)20, 21) != 111)
+		    bpf_fentry_test6(16, (void *)17, 18, 19, (void *)20, 21) != 111 ||
+		    bpf_fentry_test7((struct bpf_fentry_test_t *)0) != 0 ||
+		    bpf_fentry_test8(&arg) != 0)
 			goto out;
 		break;
 	case BPF_MODIFY_RETURN:
tools/testing/selftests/bpf/prog_tests/fentry_fexit.c +1 -1
index 83493bd5745c..109d0345a2be 100644
@@ -36,7 +36,7 @@ void test_fentry_fexit(void)
 	fentry_res = (__u64 *)fentry_skel->bss;
 	fexit_res = (__u64 *)fexit_skel->bss;
 	printf("%lld\n", fentry_skel->bss->test1_result);
-	for (i = 0; i < 6; i++) {
+	for (i = 0; i < 8; i++) {
 		CHECK(fentry_res[i] != 1, "result",
 		      "fentry_test%d failed err %lld\n", i + 1, fentry_res[i]);
 		CHECK(fexit_res[i] != 1, "result",
tools/testing/selftests/bpf/progs/fentry_test.c +22 -0
index 9365b686f84b..5f645fdaba6f 100644
@@ -55,3 +55,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f)
 		e == (void *)20 && f == 21;
 	return 0;
 }
+
+struct bpf_fentry_test_t {
+	struct bpf_fentry_test_t *a;
+};
+
+__u64 test7_result = 0;
+SEC("fentry/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+	if (arg == 0)
+		test7_result = 1;
+	return 0;
+}
+
+__u64 test8_result = 0;
+SEC("fentry/bpf_fentry_test8")
+int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
+{
+	if (arg->a == 0)
+		test8_result = 1;
+	return 0;
+}
tools/testing/selftests/bpf/progs/fexit_test.c +22 -0
index bd1e17d8024c..0952affb22a6 100644
@@ -56,3 +56,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void *e, __u64 f, int ret)
 		e == (void *)20 && f == 21 && ret == 111;
 	return 0;
 }
+
+struct bpf_fentry_test_t {
+	struct bpf_fentry_test *a;
+};
+
+__u64 test7_result = 0;
+SEC("fexit/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+	if (arg == 0)
+		test7_result = 1;
+	return 0;
+}
+
+__u64 test8_result = 0;
+SEC("fexit/bpf_fentry_test8")
+int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
+{
+	if (arg->a == 0)
+		test8_result = 1;
+	return 0;
+}
Signature · 1 line
2.24.1
reviewer Acked-by on v1 2/2
#10 lore raw

RE: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

Quoted 37 lines · Yonghong Song

Add two tests for PTR_TO_BTF_ID vs. null ptr comparison, one for PTR_TO_BTF_ID in the ctx structure and the other for PTR_TO_BTF_ID after one level pointer chasing. In both cases, the test ensures condition is not removed.

For example, for this test

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;

}
Before the previous verifier change, we have xlated codes:
int test7(long long unsigned int * ctx):
; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)

     0: (79) r1 = *(u64 *)(r1 +0)
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     1: (b4) w0 = 0
     2: (95) exit
After the previous verifier change, we have:
  int test7(long long unsigned int * ctx):
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     0: (79) r1 = *(u64 *)(r1 +0)
  ; if (arg == 0)
     1: (55) if r1 != 0x0 goto pc+4
  ; test7_result = 1;
     2: (18) r1 = map[id:6][0]+48
     4: (b7) r2 = 1
     5: (7b) *(u64 *)(r1 +0) = r2
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     6: (b4) w0 = 0
     7: (95) exit
Quoted 5 lines
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>

---

Thanks.

Acked-by on v1 2/2
#11 lore raw

Re: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

In reply to Yonghong Song
Quoted 38 lines · Yonghong Song

Add two tests for PTR_TO_BTF_ID vs. null ptr comparison, one for PTR_TO_BTF_ID in the ctx structure and the other for PTR_TO_BTF_ID after one level pointer chasing. In both cases, the test ensures condition is not removed.

For example, for this test

 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;

}
Before the previous verifier change, we have xlated codes:
int test7(long long unsigned int * ctx):
; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)

     0: (79) r1 = *(u64 *)(r1 +0)
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     1: (b4) w0 = 0
     2: (95) exit
After the previous verifier change, we have:
  int test7(long long unsigned int * ctx):
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     0: (79) r1 = *(u64 *)(r1 +0)
  ; if (arg == 0)
     1: (55) if r1 != 0x0 goto pc+4
  ; test7_result = 1;
     2: (18) r1 = map[id:6][0]+48
     4: (b7) r2 = 1
     5: (7b) *(u64 *)(r1 +0) = r2
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     6: (b4) w0 = 0
     7: (95) exit
Quoted 5 lines
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>

---

LGTM, two nits below.

Quoted 6 lines
 net/bpf/test_run.c                            | 19 +++++++++++++++-
 .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
 .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
 .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
 4 files changed, 63 insertions(+), 2 deletions(-)

[...]

tools/testing/selftests/bpf/progs/fentry_test.c int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f) · line 61

Quoted 12 lines
tools/testing/selftests/bpf/progs/fentry_test.c +4 -0
index 9365b686f84b..5f645fdaba6f 100644
@@ -55,3 +55,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f)
                e == (void *)20 && f == 21;
        return 0;
 }
+
+struct bpf_fentry_test_t {
+       struct bpf_fentry_test_t *a;
+};

nit: __attribute__((preserve_access_index)) ?

Quoted 23 lines
tools/testing/selftests/bpf/progs/fentry_test.c +18 -0
+
+__u64 test7_result = 0;
+SEC("fentry/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+       if (arg == 0)
+               test7_result = 1;
+       return 0;
+}
+
+__u64 test8_result = 0;
+SEC("fentry/bpf_fentry_test8")
+int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
+{
+       if (arg->a == 0)
+               test8_result = 1;
+       return 0;
+}
tools/testing/selftests/bpf/progs/fexit_test.c +0 -0
index bd1e17d8024c..0952affb22a6 100644

tools/testing/selftests/bpf/progs/fexit_test.c int BPF_PROG(test6, __u64 a, void *b, short c, int d, void *e, __u64 f, int ret) · line 62

Quoted 7 lines
tools/testing/selftests/bpf/progs/fexit_test.c +4 -0
@@ -56,3 +56,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void *e, __u64 f, int ret)
                e == (void *)20 && f == 21 && ret == 111;
        return 0;
 }
+
+struct bpf_fentry_test_t {
+       struct bpf_fentry_test *a;
+};

same nit

Quoted 21 lines
tools/testing/selftests/bpf/progs/fexit_test.c +18 -1
+
+__u64 test7_result = 0;
+SEC("fexit/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+       if (arg == 0)
+               test7_result = 1;
+       return 0;
+}
+
+__u64 test8_result = 0;
+SEC("fexit/bpf_fentry_test8")
+int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
+{
+       if (arg->a == 0)
+               test8_result = 1;
+       return 0;
+}
--

2.24.1

#12 lore raw

Re: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

Quoted 58 lines · Andrii Nakryiko
Quoted 38 lines · Yonghong Song

Add two tests for PTR_TO_BTF_ID vs. null ptr comparison, one for PTR_TO_BTF_ID in the ctx structure and the other for PTR_TO_BTF_ID after one level pointer chasing. In both cases, the test ensures condition is not removed.

For example, for this test

  struct bpf_fentry_test_t {
      struct bpf_fentry_test_t *a;
  };
  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
  {
      if (arg == 0)
          test7_result = 1;
      return 0;
  }
Before the previous verifier change, we have xlated codes:
   int test7(long long unsigned int * ctx):
   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
      0: (79) r1 = *(u64 *)(r1 +0)
   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
      1: (b4) w0 = 0
      2: (95) exit
After the previous verifier change, we have:
   int test7(long long unsigned int * ctx):
   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
      0: (79) r1 = *(u64 *)(r1 +0)
   ; if (arg == 0)
      1: (55) if r1 != 0x0 goto pc+4
   ; test7_result = 1;
      2: (18) r1 = map[id:6][0]+48
      4: (b7) r2 = 1
      5: (7b) *(u64 *)(r1 +0) = r2
   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
      6: (b4) w0 = 0
      7: (95) exit
Quoted 5 lines
Cc Andrii Nakryiko <[email protected]>
Cc John Fastabend <[email protected]>
Cc Wenbo Zhang <[email protected]>

---

LGTM, two nits below.

Quoted 6 lines
  net/bpf/test_run.c                            | 19 +++++++++++++++-
  .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
  .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
  .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
  4 files changed, 63 insertions(+), 2 deletions(-)

[...]

Quoted 14 lines

tools/testing/selftests/bpf/progs/fentry_test.c int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f) · line 61

Quoted 12 lines
tools/testing/selftests/bpf/progs/fentry_test.c +4 -0
index 9365b686f84b..5f645fdaba6f 100644
@@ -55,3 +55,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f)
                 e == (void *)20 && f == 21;
         return 0;
  }
+
+struct bpf_fentry_test_t {
+       struct bpf_fentry_test_t *a;
+};

nit: __attribute__((preserve_access_index)) ?

Yes. Why not. Will send a followup once the patch circulates back to bpf-next.

Quoted 11 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/fentry_test.c +10 -0
+
+__u64 test7_result = 0;
+SEC("fentry/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+       if (arg == 0)
+               test7_result = 1;
+       return 0;
+}
+

[...]