Re: [PATCH bpf-next 1/2] bpf: propagate nullness information for reg to reg comparisons

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2022-09-01 at 17:01 +0800, Shung-Hsi Yu wrote:
> On Thu, Sep 01, 2022 at 04:13:22PM +0800, Shung-Hsi Yu wrote:
> > On Tue, Aug 30, 2022 at 01:41:28PM +0300, Eduard Zingerman wrote:
> > > Hi Daniel,
> > > 
> > > Thank you for commenting.
> > > 
> > > > On Mon, 2022-08-29 at 16:23 +0200, Daniel Borkmann wrote:
> > > > [...]
> > > > >   kernel/bpf/verifier.c | 41 +++++++++++++++++++++++++++++++++++++++--
> > > > >   1 file changed, 39 insertions(+), 2 deletions(-)
> > > > > 
> > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > > index 0194a36d0b36..7585288e035b 100644
> > > > > --- a/kernel/bpf/verifier.c
> > > > > +++ b/kernel/bpf/verifier.c
> > > > > @@ -472,6 +472,11 @@ static bool type_may_be_null(u32 type)
> > > > >   	return type & PTR_MAYBE_NULL;
> > > > >   }
> > > > >   
> > > > > +static bool type_is_pointer(enum bpf_reg_type type)
> > > > > +{
> > > > > +	return type != NOT_INIT && type != SCALAR_VALUE;
> > > > > +}
> > > > 
> > > > We also have is_pointer_value(), semantics there are a bit different (and mainly to
> > > > prevent leakage under unpriv), but I wonder if this can be refactored to accommodate
> > > > both. My worry is that if in future we extend one but not the other bugs might slip
> > > > in.
> > > 
> > > John was concerned about this as well, guess I won't not dodging it :)
> > > Suppose I do the following modification:
> > > 
> > >     static bool type_is_pointer(enum bpf_reg_type type)
> > >     {
> > >     	return type != NOT_INIT && type != SCALAR_VALUE;
> > >     }
> > >     
> > >     static bool __is_pointer_value(bool allow_ptr_leaks,
> > >     			       const struct bpf_reg_state *reg)
> > >     {
> > >     	if (allow_ptr_leaks)
> > >     		return false;
> > > 
> > > -    	return reg->type != SCALAR_VALUE;
> > > +    	return type_is_pointer(reg->type);
> > >     }
> >      
> > The verifier is using the wrapped is_pointer_value() to guard against
> > pointer leak.
> > 
> >   static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno,
> >   			    int off, int bpf_size, enum bpf_access_type t,
> >   			    int value_regno, bool strict_alignment_once)
> >   {
> >       ...
> >   	if (reg->type == PTR_TO_MAP_KEY) {
> >   		...
> >   	} else if (reg->type == PTR_TO_MAP_VALUE) {
> >   		struct bpf_map_value_off_desc *kptr_off_desc = NULL;
> >   
> >   		if (t == BPF_WRITE && value_regno >= 0 &&
> >   		    is_pointer_value(env, value_regno)) {
> >   			verbose(env, "R%d leaks addr into map\n", value_regno);
> >   			return -EACCES;
> >           ...
> >   	}
> >       ...
> >   }
> > 
> > In the check_mem_access() case the semantic of is_pointer_value() is check
> > whether or not the value *might* be a pointer, and since NON_INIT can be
> > potentially anything, it should not be excluded.
> 
> I wasn't reading the threads carefully enough, apologies, just realized
> Daniel had already mention the above point further up.
> 
> Also, after going back to the previous RFC thread I saw John mention that
> after making the is_pointer_value() changes to exclude NOT_INIT, the tests
> still passes.
> 
> I guess that comes down to how the verifier rigorously check that the
> registers are not NOT_INIT using check_reg_arg(..., SRC_OP), before moving
> on to more specific checks. So I'm a bit less sure about the split
> {maybe,is}_pointer_value() approach proposed below now.

Hi Shung-Hsi, Daniel,

Sorry for a long delay. I'd like to revive this small change.

Thank you for pointing out the part regarding rigorous checks and
check_reg_arg. I've examined all places where __is_pointer_value(...)
and is_pointer_value(...) are invoked in the verifier code and came to
the conclusion that NOT_INIT can never reach the __is_pointer_value.
I also double checked this by modifying __is_pointer_value as follows:

 static bool __is_pointer_value(bool allow_ptr_leaks,
			       const struct bpf_reg_state *reg)
 {
+	BUG_ON(reg->type == NOT_INIT);
 	...
 }

And running the BPF selftests. None triggered the BUG_ON condition.

The place where I use type_is_pointer in check_cond_jmp_op is after
the check_reg_arg(..., SRC_OP) for both src and dst registers. Thus I
want to delete the type_is_pointer function from the patch and use
__is_pointer_value(false, ...) instead (as NOT_INIT check was
unnecessary from the beginning).

> 
> > Since the use case seems different, perhaps we could split them up, e.g. a
> > maybe_pointer_value() and a is_pointer_value(), or something along that
> > line.
> > 
> > The former is equivalent to type != SCALAR_VALUE, and the latter equivalent
> > to type != NOT_INIT && type != SCALAR_VALUE. The latter can be used here for
> > implementing nullness propogation.
> > 
> > > And check if there are test cases that have to be added because of the
> > > change in the __is_pointer_value behavior (it does not check for
> > > `NOT_INIT` right now). Does this sound like a plan?
> > > 
> > > [...]
> > > > Could we consolidate the logic above with the one below which deals with R == 0 checks?
> > > > There are some similarities, e.g. !is_jmp32, both test for jeq/jne and while one is based
> > > > on K, the other one on X, though we could also add check X == 0 for below. Anyway, just
> > > > a though that it may be nice to consolidate the handling.
> > > 
> > > Ok, I will try to consolidate those.

After some contemplating I don't think that it would be good to
consolidate these two parts.

The part that I want to add merely propagates the nullness
information:

	if (!is_jmp32 && BPF_SRC(insn->code) == BPF_X &&
	    __is_pointer_value(false, src_reg) && __is_pointer_value(false, dst_reg) &&
	    type_may_be_null(src_reg->type) != type_may_be_null(dst_reg->type)) {
            // ... save non-null part for one of the regs ...
        }

However, the part that is already present is actually a pointer leak
check that exempts comparison with zero (and exemption for comparison
with zero is stated as goal of commit 1be7f75d1668 that added
is_pointer_value back in 2015):

	/* detect if R == 0 where R is returned from bpf_map_lookup_elem()...
	 */
	if (!is_jmp32 && BPF_SRC(insn->code) == BPF_K &&
	    insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) &&
	    type_may_be_null(dst_reg->type)) {
		/* Mark all identical registers in each branch as either
		 * safe or unknown depending R == 0 or R != 0 conditional.
		 */
                // ...
	} else if (!try_match_pkt_pointers(insn, dst_reg, &regs[insn->src_reg],
					   this_branch, other_branch) &&
leak check -->	   is_pointer_value(env, insn->dst_reg)) {
		verbose(env, "R%d pointer comparison prohibited\n",
			insn->dst_reg);
		return -EACCES;
	}

Merging these conditionals would be confusing, imo.

If you don't have objections I will post the v2 removing
type_is_pointer from the patch.

Thanks,
Eduard

> > > 
> > > Thanks,
> > > Eduard