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

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

[Paul Chaignon]

In case of a null check on a pointer inside a subprog, we should mark all
registers with this pointer as either safe or unknown, in both the current
and previous frames.  Currently, only spilled registers and registers in
the current frame are marked.  This first patch also marks registers in
previous frames.

A good reproducer looks as follow:

1: ptr = bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3:   return ptr != NULL;
4: }
5: if (ret)
6:   value = *ptr;

With the above, the verifier will complain on line 6 because it sees ptr
as map_value_or_null despite the null check in subprog 1.  The second
patch implements the above as a new test case.

Note that this patch fixes another resulting bug when using
bpf_sk_release():

1: sk = bpf_sk_lookup_tcp(...);
2: subprog(sk) {
3:   if (sk)
4:     bpf_sk_release(sk);
5: }
6: if (!sk)
7:   return 0;
8: return 1;

In the above, mark_ptr_or_null_regs will warn on line 6 because it will
try to free the reference state, even though it was already freed on
line 3.

Changelogs:
  Changes in v2:
    - Fix example codes in commit message.

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

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

-- 
2.17.1

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

[Paul Chaignon]

In case of a null check on a pointer inside a subprog, we should mark all
registers with this pointer as either safe or unknown, in both the current
and previous frames.  Currently, only spilled registers and registers in
the current frame are marked.  This patch also marks registers in previous
frames.

A good reproducer looks as follow:

1: ptr = bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3:   return ptr != NULL;
4: }
5: if (ret)
6:   value = *ptr;

With the above, the verifier will complain on line 6 because it sees ptr
as map_value_or_null despite the null check in subprog 1.

Note that this patch fixes another resulting bug when using
bpf_sk_release():

1: sk = bpf_sk_lookup_tcp(...);
2: subprog(sk) {
3:   if (sk)
4:     bpf_sk_release(sk);
5: }
6: if (!sk)
7:   return 0;
8: return 1;

In the above, mark_ptr_or_null_regs will warn on line 6 because it will
try to free the reference state, even though it was already freed on
line 3.

Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
---
 kernel/bpf/verifier.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index db301e9b5295..777970d8c245 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4876,11 +4876,11 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
 		 */
 		WARN_ON_ONCE(release_reference_state(state, id));
 
-	for (i = 0; i < MAX_BPF_REG; i++)
-		mark_ptr_or_null_reg(state, &regs[i], id, is_null);
-
 	for (j = 0; j <= vstate->curframe; j++) {
 		state = vstate->frame[j];
+		for (i = 0; i < MAX_BPF_REG; i++)
+			mark_ptr_or_null_reg(state, &state->regs[i], id,
+					     is_null);
 		bpf_for_each_spilled_reg(i, state, reg) {
 			if (!reg)
 				continue;
-- 
2.17.1

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

[Paul Chaignon]

This test case is equivalent to the following pseudo-code.  It checks that
the verifier does not complain on line 6 and recognizes that ptr isn't
null.

1: ptr = bpf_map_lookup_elem(map, &key);
2: ret = subprog(ptr) {
3:   return ptr != NULL;
4: }
5: if (ret)
6:   value = *ptr;

Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
---
 tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index fb11240b758b..9093a8f64dc6 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -374,6 +374,31 @@
 	.prog_type = BPF_PROG_TYPE_XDP,
 	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
 },
+{
+	"calls: ptr null check in subprog",
+	.insns = {
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 3),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
+	BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_6, 0),
+	BPF_EXIT_INSN(),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 1),
+	BPF_MOV64_IMM(BPF_REG_0, 1),
+	BPF_EXIT_INSN(),
+	},
+	.errstr_unpriv = "function calls to other bpf functions are allowed for root only",
+	.fixup_map_hash_48b = { 3 },
+	.result_unpriv = REJECT,
+	.result = ACCEPT,
+	.retval = 0,
+},
 {
 	"calls: two calls with args",
 	.insns = {
-- 
2.17.1

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

[Yonghong Song]

On 4/22/19 11:34 AM, Paul Chaignon wrote:
> In case of a null check on a pointer inside a subprog, we should mark all
> registers with this pointer as either safe or unknown, in both the current
> and previous frames.  Currently, only spilled registers and registers in
> the current frame are marked.  This first patch also marks registers in
> previous frames.
> 
> A good reproducer looks as follow:
> 
> 1: ptr = bpf_map_lookup_elem(map, &key);
> 2: ret = subprog(ptr) {
> 3:   return ptr != NULL;
> 4: }
> 5: if (ret)
> 6:   value = *ptr;
> 
> With the above, the verifier will complain on line 6 because it sees ptr
> as map_value_or_null despite the null check in subprog 1.  The second
> patch implements the above as a new test case.
> 
> Note that this patch fixes another resulting bug when using
> bpf_sk_release():
> 
> 1: sk = bpf_sk_lookup_tcp(...);
> 2: subprog(sk) {
> 3:   if (sk)
> 4:     bpf_sk_release(sk);
> 5: }
> 6: if (!sk)
> 7:   return 0;
> 8: return 1;
> 
> In the above, mark_ptr_or_null_regs will warn on line 6 because it will
> try to free the reference state, even though it was already freed on
> line 3.
> 
> Changelogs:
>    Changes in v2:
>      - Fix example codes in commit message.
> 
> Paul Chaignon (2):
>    bpf: mark registers as safe or unknown in all frames
>    selftests/bpf: test case for pointer null check in subprog
> 
>   kernel/bpf/verifier.c                        |  6 ++---
>   tools/testing/selftests/bpf/verifier/calls.c | 25 ++++++++++++++++++++
>   2 files changed, 28 insertions(+), 3 deletions(-)

For the series:
   Acked-by: Yonghong Song <yhs@fb.com>

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

[Daniel Borkmann]

On 04/22/2019 08:34 PM, Paul Chaignon wrote:
> In case of a null check on a pointer inside a subprog, we should mark all
> registers with this pointer as either safe or unknown, in both the current
> and previous frames.  Currently, only spilled registers and registers in
> the current frame are marked.  This patch also marks registers in previous
> frames.
> 
> A good reproducer looks as follow:
> 
> 1: ptr = bpf_map_lookup_elem(map, &key);
> 2: ret = subprog(ptr) {
> 3:   return ptr != NULL;
> 4: }
> 5: if (ret)
> 6:   value = *ptr;
> 
> With the above, the verifier will complain on line 6 because it sees ptr
> as map_value_or_null despite the null check in subprog 1.
> 
> Note that this patch fixes another resulting bug when using
> bpf_sk_release():
> 
> 1: sk = bpf_sk_lookup_tcp(...);
> 2: subprog(sk) {
> 3:   if (sk)
> 4:     bpf_sk_release(sk);
> 5: }
> 6: if (!sk)
> 7:   return 0;
> 8: return 1;
> 
> In the above, mark_ptr_or_null_regs will warn on line 6 because it will
> try to free the reference state, even though it was already freed on
> line 3.
> 
> Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
> Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
> ---
>  kernel/bpf/verifier.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index db301e9b5295..777970d8c245 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -4876,11 +4876,11 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
>  		 */
>  		WARN_ON_ONCE(release_reference_state(state, id));
>  
> -	for (i = 0; i < MAX_BPF_REG; i++)
> -		mark_ptr_or_null_reg(state, &regs[i], id, is_null);
> -
>  	for (j = 0; j <= vstate->curframe; j++) {
>  		state = vstate->frame[j];
> +		for (i = 0; i < MAX_BPF_REG; i++)
> +			mark_ptr_or_null_reg(state, &state->regs[i], id,
> +					     is_null);

Small nit: I think it would be good to follow practice from clear_all_pkt_pointers()
and release_reg_references() to move handling of a singe frame into its own function.

>  		bpf_for_each_spilled_reg(i, state, reg) {
>  			if (!reg)
>  				continue;
> 

What about semantics in other, similar functions like find_good_pkt_pointers()?
Should this also consider all frames instead?

Thanks,
Daniel

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

[Paul Chaignon]

On Tue, Apr 23, 2019 01:47AM, Daniel Borkmann wrote:
> On 04/22/2019 08:34 PM, Paul Chaignon wrote:
> > In case of a null check on a pointer inside a subprog, we should mark all
> > registers with this pointer as either safe or unknown, in both the current
> > and previous frames.  Currently, only spilled registers and registers in
> > the current frame are marked.  This patch also marks registers in previous
> > frames.
> > 
> > A good reproducer looks as follow:
> > 
> > 1: ptr = bpf_map_lookup_elem(map, &key);
> > 2: ret = subprog(ptr) {
> > 3:   return ptr != NULL;
> > 4: }
> > 5: if (ret)
> > 6:   value = *ptr;
> > 
> > With the above, the verifier will complain on line 6 because it sees ptr
> > as map_value_or_null despite the null check in subprog 1.
> > 
> > Note that this patch fixes another resulting bug when using
> > bpf_sk_release():
> > 
> > 1: sk = bpf_sk_lookup_tcp(...);
> > 2: subprog(sk) {
> > 3:   if (sk)
> > 4:     bpf_sk_release(sk);
> > 5: }
> > 6: if (!sk)
> > 7:   return 0;
> > 8: return 1;
> > 
> > In the above, mark_ptr_or_null_regs will warn on line 6 because it will
> > try to free the reference state, even though it was already freed on
> > line 3.
> > 
> > Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)")
> > Signed-off-by: Paul Chaignon <paul.chaignon@orange.com>
> > ---
> >  kernel/bpf/verifier.c | 6 +++---
> >  1 file changed, 3 insertions(+), 3 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index db301e9b5295..777970d8c245 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -4876,11 +4876,11 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
> >  		 */
> >  		WARN_ON_ONCE(release_reference_state(state, id));
> >  
> > -	for (i = 0; i < MAX_BPF_REG; i++)
> > -		mark_ptr_or_null_reg(state, &regs[i], id, is_null);
> > -
> >  	for (j = 0; j <= vstate->curframe; j++) {
> >  		state = vstate->frame[j];
> > +		for (i = 0; i < MAX_BPF_REG; i++)
> > +			mark_ptr_or_null_reg(state, &state->regs[i], id,
> > +					     is_null);
> 
> Small nit: I think it would be good to follow practice from clear_all_pkt_pointers()
> and release_reg_references() to move handling of a singe frame into its own function.

Will do.

> 
> >  		bpf_for_each_spilled_reg(i, state, reg) {
> >  			if (!reg)
> >  				continue;
> > 
> 
> What about semantics in other, similar functions like find_good_pkt_pointers()?
> Should this also consider all frames instead?

Looks like the same is needed in find_good_pkt_pointers().  It's the only
similar function I could find though.  Did you have others in mind?

I'll add a second test case for the find_good_pkt_pointers() change in v3.

> 
> Thanks,
> Daniel