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

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(-)

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

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