* [bpf-next PATCH v2 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ
2020-05-21 20:07 [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic John Fastabend
@ 2020-05-21 20:07 ` John Fastabend
2020-05-21 20:07 ` [bpf-next PATCH v2 2/4] bpf: selftests, verifier case for non null pointer check branch taken John Fastabend
` (3 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: John Fastabend @ 2020-05-21 20:07 UTC (permalink / raw)
To: yhs, andrii.nakryiko, ast, daniel; +Cc: netdev, bpf, john.fastabend
Currently, when considering the branches that may be taken for a jump
instruction if the register being compared is a pointer the verifier
assumes both branches may be taken. But, if the jump instruction
is comparing if a pointer is NULL we have this information in the
verifier encoded in the reg->type so we can do better in these cases.
Specifically, these two common cases can be handled.
* If the instruction is BPF_JEQ and we are comparing against a
zero value. This test is 'if ptr == 0 goto +X' then using the
type information in reg->type we can decide if the ptr is not
null. This allows us to avoid pushing both branches onto the
stack and instead only use the != 0 case. For example
PTR_TO_SOCK and PTR_TO_SOCK_OR_NULL encode the null pointer.
Note if the type is PTR_TO_SOCK_OR_NULL we can not learn anything.
And also if the value is non-zero we learn nothing because it
could be any arbitrary value a different pointer for example
* If the instruction is BPF_JNE and ware comparing against a zero
value then a similar analysis as above can be done. The test in
asm looks like 'if ptr != 0 goto +X'. Again using the type
information if the non null type is set (from above PTR_TO_SOCK)
we know the jump is 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 C code like the following.
See progs/test_sk_lookup_kern.c in selftests.
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;
In the above the bpf_printk() will resolve the pointer from
PTR_TO_SOCK_OR_NULL to PTR_TO_SOCK. Then the second test guarding
the release will cause the verifier to walk both paths resulting
in the an unreleased sock reference. See verifier/ref_tracking.c
in selftests for an assembly version of the above.
After the above additional logic is added the C code above passes
as expected.
Suggested-by: Alexei Starovoitov <ast@kernel.org>
Reported-by: Andrey Ignatov <rdna@fb.com>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
kernel/bpf/verifier.c | 36 +++++++++++++++++++++++++++++++++---
1 file changed, 33 insertions(+), 3 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9c7d67d..4e0dc44 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -393,6 +393,15 @@ 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 ||
+ type == PTR_TO_BTF_ID;
+}
+
static bool reg_type_may_be_null(enum bpf_reg_type type)
{
return type == PTR_TO_MAP_VALUE_OR_NULL ||
@@ -6308,8 +6317,25 @@ 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.
+ */
+ if (val != 0)
+ return -1;
+
+ switch (opcode) {
+ case BPF_JEQ:
+ return 0;
+ case BPF_JNE:
+ return 1;
+ default:
+ return -1;
+ }
+ }
if (is_jmp32)
return is_branch32_taken(reg, val, opcode);
@@ -6808,7 +6834,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
}
if (pred >= 0) {
- err = mark_chain_precision(env, insn->dst_reg);
+ /* If we get here with a dst_reg pointer type it is because
+ * above is_branch_taken() special cased the 0 comparison.
+ */
+ if (!__is_pointer_value(false, dst_reg))
+ err = mark_chain_precision(env, insn->dst_reg);
if (BPF_SRC(insn->code) == BPF_X && !err)
err = mark_chain_precision(env, insn->src_reg);
if (err)
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [bpf-next PATCH v2 2/4] bpf: selftests, verifier case for non null pointer check branch taken
2020-05-21 20:07 [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic John Fastabend
2020-05-21 20:07 ` [bpf-next PATCH v2 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ John Fastabend
@ 2020-05-21 20:07 ` John Fastabend
2020-05-21 20:08 ` [bpf-next PATCH v2 3/4] bpf: selftests, verifier case for non null pointer map value branch John Fastabend
` (2 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: John Fastabend @ 2020-05-21 20:07 UTC (permalink / raw)
To: yhs, andrii.nakryiko, ast, daniel; +Cc: netdev, bpf, john.fastabend
When we have pointer type that is known to be non-null and comparing
against zero we only follow the non-null branch. This adds tests to
cover this case for reference tracking. Also add the other case when
comparison against a non-zero value and ensure we still fail with
unreleased reference.
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
.../testing/selftests/bpf/verifier/ref_tracking.c | 33 ++++++++++++++++++++
1 file changed, 33 insertions(+)
diff --git a/tools/testing/selftests/bpf/verifier/ref_tracking.c b/tools/testing/selftests/bpf/verifier/ref_tracking.c
index 604b461..056e027 100644
--- a/tools/testing/selftests/bpf/verifier/ref_tracking.c
+++ b/tools/testing/selftests/bpf/verifier/ref_tracking.c
@@ -821,3 +821,36 @@
.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,
+},
+{
+ "reference tracking: branch tracking valid pointer value 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_JEQ, BPF_REG_6, 0, 4),
+ BPF_MOV64_IMM(BPF_REG_3, 0),
+ BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 1234, 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,
+ .errstr = "Unreleased reference",
+ .result = REJECT,
+},
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [bpf-next PATCH v2 3/4] bpf: selftests, verifier case for non null pointer map value branch
2020-05-21 20:07 [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic John Fastabend
2020-05-21 20:07 ` [bpf-next PATCH v2 1/4] bpf: verifier track null pointer branch_taken with JNE and JEQ John Fastabend
2020-05-21 20:07 ` [bpf-next PATCH v2 2/4] bpf: selftests, verifier case for non null pointer check branch taken John Fastabend
@ 2020-05-21 20:08 ` John Fastabend
2020-05-21 20:08 ` [bpf-next PATCH v2 4/4] bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check John Fastabend
2020-05-21 22:21 ` [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic Andrii Nakryiko
4 siblings, 0 replies; 7+ messages in thread
From: John Fastabend @ 2020-05-21 20:08 UTC (permalink / raw)
To: yhs, andrii.nakryiko, ast, daniel; +Cc: netdev, bpf, 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.
Acked-by: Andrii Nakryiko <andriin@fb.com>
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,
+},
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [bpf-next PATCH v2 4/4] bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check
2020-05-21 20:07 [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic John Fastabend
` (2 preceding siblings ...)
2020-05-21 20:08 ` [bpf-next PATCH v2 3/4] bpf: selftests, verifier case for non null pointer map value branch John Fastabend
@ 2020-05-21 20:08 ` John Fastabend
2020-05-21 22:21 ` [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic Andrii Nakryiko
4 siblings, 0 replies; 7+ messages in thread
From: John Fastabend @ 2020-05-21 20:08 UTC (permalink / raw)
To: yhs, andrii.nakryiko, ast, daniel; +Cc: netdev, bpf, 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.
Acked-by: Andrii Nakryiko <andriin@fb.com>
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;
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic
2020-05-21 20:07 [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic John Fastabend
` (3 preceding siblings ...)
2020-05-21 20:08 ` [bpf-next PATCH v2 4/4] bpf: selftests, add printk to test_sk_lookup_kern to encode null ptr check John Fastabend
@ 2020-05-21 22:21 ` Andrii Nakryiko
2020-05-22 0:49 ` Alexei Starovoitov
4 siblings, 1 reply; 7+ messages in thread
From: Andrii Nakryiko @ 2020-05-21 22:21 UTC (permalink / raw)
To: John Fastabend
Cc: Yonghong Song, Alexei Starovoitov, Daniel Borkmann, Networking, bpf
On Thu, May 21, 2020 at 1:07 PM John Fastabend <john.fastabend@gmail.com> wrote:
>
> This series adds logic to the verifier to handle the case where a
> pointer is known to be non-null but then the verifier encountesr a
> instruction, such as 'if ptr == 0 goto X' or 'if ptr != 0 goto X',
> where the pointer is compared against 0. Because the verifier tracks
> if a pointer may be null in many cases we can improve the branch
> tracking by following the case known to be true.
>
> The first patch adds the verifier logic and patches 2-4 add the
> test cases.
>
> v1->v2: fix verifier logic to return -1 indicating both paths must
> still be walked if value is not zero. Move mark_precision skip for
> this case into caller of mark_precision to ensure mark_precision can
> still catch other misuses. And add PTR_TYPE_BTF_ID to our list of
> supported types. Finally add one more test to catch the value not
> equal zero case. Thanks to Andrii for original review.
>
> Also fixed up commit messages hopefully its better now.
>
Yeah, much better, thanks! Few typos don't count ;)
For the series:
Acked-by: Andrii Nakryiko <andriin@fb.com>
> ---
>
> 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
>
>
> kernel/bpf/verifier.c | 36 ++++++++++++++++++--
> .../selftests/bpf/progs/test_sk_lookup_kern.c | 1 +
> .../testing/selftests/bpf/verifier/ref_tracking.c | 33 ++++++++++++++++++
> .../testing/selftests/bpf/verifier/value_or_null.c | 19 +++++++++++
> 4 files changed, 86 insertions(+), 3 deletions(-)
>
> --
> Signature
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic
2020-05-21 22:21 ` [bpf-next PATCH v2 0/4] ] verifier, improve ptr is_branch_taken logic Andrii Nakryiko
@ 2020-05-22 0:49 ` Alexei Starovoitov
0 siblings, 0 replies; 7+ messages in thread
From: Alexei Starovoitov @ 2020-05-22 0:49 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: John Fastabend, Yonghong Song, Alexei Starovoitov,
Daniel Borkmann, Networking, bpf
On Thu, May 21, 2020 at 3:21 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, May 21, 2020 at 1:07 PM John Fastabend <john.fastabend@gmail.com> wrote:
> >
> > This series adds logic to the verifier to handle the case where a
> > pointer is known to be non-null but then the verifier encountesr a
> > instruction, such as 'if ptr == 0 goto X' or 'if ptr != 0 goto X',
> > where the pointer is compared against 0. Because the verifier tracks
> > if a pointer may be null in many cases we can improve the branch
> > tracking by following the case known to be true.
> >
> > The first patch adds the verifier logic and patches 2-4 add the
> > test cases.
> >
> > v1->v2: fix verifier logic to return -1 indicating both paths must
> > still be walked if value is not zero. Move mark_precision skip for
> > this case into caller of mark_precision to ensure mark_precision can
> > still catch other misuses. And add PTR_TYPE_BTF_ID to our list of
> > supported types. Finally add one more test to catch the value not
> > equal zero case. Thanks to Andrii for original review.
> >
> > Also fixed up commit messages hopefully its better now.
> >
>
> Yeah, much better, thanks! Few typos don't count ;)
>
> For the series:
>
> Acked-by: Andrii Nakryiko <andriin@fb.com>
Applied. Thanks a lot everyone.
^ permalink raw reply [flat|nested] 7+ messages in thread