bpf: fix an incorrect branch elimination by verifier
Subsystems (5)
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
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/
--- kernel/bpf/verifier.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -2
@@ -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
John Fastabend
reviewerQuoted 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_btfand the pointer to compare is aPTR_TO_BTF_ID.The current verifier considers
PTR_TO_BTF_IDalways reprents a non-null pointer, hence allPTR_TO_BTF_IDcompares 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 pointerbranch_takenwith JNE and JEQ"), wherePTR_TO_BTF_IDis considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we havePTR_TO_BTF_ID_OR_NULLin the verifier as well.
Quoted 5 lines
PTR_TO_BTF_ID_OR_NULLis added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assignsPTR_TO_BTF_IDso users does not need to check NULL pointer at every pointer level likea->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
@@ -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
@@ -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_IDasPTR_TO_BTF_ID_OR_NULLas 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_IDfromreg_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]>Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/verifier.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)kernel/bpf/verifier.c +1
-2@@ -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
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_btfand the pointer to compare is aPTR_TO_BTF_ID.The current verifier considers
PTR_TO_BTF_IDalways reprents a non-null pointer, hence allPTR_TO_BTF_IDcompares 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 pointerbranch_takenwith JNE and JEQ"), wherePTR_TO_BTF_IDis considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we havePTR_TO_BTF_ID_OR_NULLin the verifier as well.Quoted 5 lines
PTR_TO_BTF_ID_OR_NULLis added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assignsPTR_TO_BTF_IDso users does not need to check NULL pointer at every pointer level likea->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_IDif 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@@ -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@@ -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_IDasPTR_TO_BTF_ID_OR_NULLas 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_IDfromreg_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]>Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/verifier.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)kernel/bpf/verifier.c +1
-2@@ -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
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_btfand the pointer to compare is aPTR_TO_BTF_ID.The current verifier considers
PTR_TO_BTF_IDalways reprents a non-null pointer, hence allPTR_TO_BTF_IDcompares 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 pointerbranch_takenwith JNE and JEQ"), wherePTR_TO_BTF_IDis considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we havePTR_TO_BTF_ID_OR_NULLin the verifier as well.Quoted 5 lines
PTR_TO_BTF_ID_OR_NULLis added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assignsPTR_TO_BTF_IDso users does not need to check NULL pointer at every pointer level likea->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 anda->b,a->b->c,a->b->care all valid pointers, user may just writea->b->c->d. this happens to some bcc scripts. So non-null pointer is checked.But if user thinks
a->b->cis 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->deven ifa->b->ccould be null.
if the result is 0, it meansa->b->cis 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_IDif 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_IDactually means it may be null but not checking is enforced and pointer tracing is always allowed.PTR_TO_BTF_ID_OR_NULLmeans 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@@ -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@@ -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_IDasPTR_TO_BTF_ID_OR_NULLas 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_IDfromreg_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]>Signed-off-by Yonghong Song <[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@@ -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
Quoted 12 lines · John Fastabend
Quoted 12 lines
Quoted 6 lines
Also, we probably shouldn't name the type
PTR_TO_BTF_IDif 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_IDactually means it may be null but not checking is enforced and pointer tracing is always allowed.PTR_TO_BTF_ID_OR_NULLmeans 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.
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_btfand the pointer to compare is aPTR_TO_BTF_ID.The current verifier considers
PTR_TO_BTF_IDalways reprents a non-null pointer, hence allPTR_TO_BTF_IDcompares 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 pointerbranch_takenwith JNE and JEQ"), wherePTR_TO_BTF_IDis considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we havePTR_TO_BTF_ID_OR_NULLin the verifier as well.Quoted 5 lines
PTR_TO_BTF_ID_OR_NULLis added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assignsPTR_TO_BTF_IDso users does not need to check NULL pointer at every pointer level likea->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_IDif 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 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_btfand the pointer to compare is aPTR_TO_BTF_ID.The current verifier considers
PTR_TO_BTF_IDalways reprents a non-null pointer, hence allPTR_TO_BTF_IDcompares 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 pointerbranch_takenwith JNE and JEQ"), wherePTR_TO_BTF_IDis considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we havePTR_TO_BTF_ID_OR_NULLin the verifier as well.
PTR_TO_BTF_ID_OR_NULLis added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assignsPTR_TO_BTF_IDso users does not need to check NULL pointer at every pointer level likea->b->c->d.We may not want to assign every
PTR_TO_BTF_IDasPTR_TO_BTF_ID_OR_NULLas 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_IDfromreg_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]>Signed-off-by Yonghong Song <[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@@ -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
Daniel Borkmann
maintainerQuoted 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_btfand the pointer to compare is aPTR_TO_BTF_ID.The current verifier considers
PTR_TO_BTF_IDalways reprents a non-null pointer, hence allPTR_TO_BTF_IDcompares 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 pointerbranch_takenwith JNE and JEQ"), wherePTR_TO_BTF_IDis considered to be non-null when evaluting pointer vs. scalar comparison. This may be added considering we havePTR_TO_BTF_ID_OR_NULLin the verifier as well.
PTR_TO_BTF_ID_OR_NULLis added to explicitly requires a non-NULL testing in selective cases. The current generic pointer tracing framework in verifier always assignsPTR_TO_BTF_IDso users does not need to check NULL pointer at every pointer level likea->b->c->d.We may not want to assign every
PTR_TO_BTF_IDasPTR_TO_BTF_ID_OR_NULLas 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_IDfromreg_type_not_null()in verifier, which prevented the above branches from being eliminated.
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]>Signed-off-by Yonghong Song <[email protected]>---
You missed Reported-by: tag, please add.
Agree, fixed up manually (and also pulled in your ACKs, Andrii).
Thanks,
Daniel
PATCH 2/2 bpf: add tests for PTR_TO_BTF_ID vs. null comparison
In reply to Yonghong SongAdd 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--- 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
@@ -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
@@ -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
@@ -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
@@ -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
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_IDvs. null ptr comparison, one forPTR_TO_BTF_IDin the ctx structure and the other forPTR_TO_BTF_IDafter 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:
inttest7(long long unsigned int * ctx):
; intBPF_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]>Signed-off-by Yonghong Song <[email protected]>---
Thanks.
Re: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison
In reply to Yonghong SongQuoted 38 lines · Yonghong Song
Add two tests for
PTR_TO_BTF_IDvs. null ptr comparison, one forPTR_TO_BTF_IDin the ctx structure and the other forPTR_TO_BTF_IDafter 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:
inttest7(long long unsigned int * ctx):
; intBPF_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]>Signed-off-by Yonghong Song <[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@@ -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
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
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_IDvs. null ptr comparison, one forPTR_TO_BTF_IDin the ctx structure and the other forPTR_TO_BTF_IDafter 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) exitQuoted 5 lines
Cc Andrii Nakryiko <[email protected]>Cc John Fastabend <[email protected]>Cc Wenbo Zhang <[email protected]>Signed-off-by Yonghong Song <[email protected]>---
LGTM, two nits below.
Acked-by Andrii Nakryiko <[email protected]>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@@ -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 ; +} +
[...]