Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1660673 > unrolled thread

Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2017-06-08 04:40 +0200
    Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Edward Cree <ecree@solarflare.com> - 2017-06-08 17:00 +0200
      Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2017-06-08 18:50 +0200
        Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Edward Cree <ecree@solarflare.com> - 2017-06-08 21:40 +0200
          Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2017-06-08 23:30 +0200
        Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-09 15:30 +0200

#1660673 — Re: [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking

On Wed, Jun 07, 2017 at 03:58:31PM +0100, Edward Cree wrote:
> Tracks value alignment by means of tracking known & unknown bits.
> Tightens some min/max value checks and fixes a couple of bugs therein.
> 
> Signed-off-by: Edward Cree <ecree@solarflare.com>
> ---
>  include/linux/bpf.h          |   34 +-
>  include/linux/bpf_verifier.h |   40 +-
>  include/linux/tnum.h         |   58 ++
>  kernel/bpf/Makefile          |    2 +-
>  kernel/bpf/tnum.c            |  163 +++++
>  kernel/bpf/verifier.c        | 1641 +++++++++++++++++++++++-------------------
>  6 files changed, 1170 insertions(+), 768 deletions(-)

yeah! That's cool. Overall I like the direction.
I don't understand it completely yet, so ony few nits so far:

> +/* Arithmetic and logical ops */
> +/* Shift a tnum left (by a fixed shift) */
> +struct tnum tn_sl(struct tnum a, u8 shift);
> +/* Shift a tnum right (by a fixed shift) */
> +struct tnum tn_sr(struct tnum a, u8 shift);

I think in few month we will forget what these abbreviations mean.
Can you change it to tnum_rshift, tnum_lshift, tnum_add ?

> +/* half-multiply add: acc += (unknown * mask * value) */
> +static struct tnum hma(struct tnum acc, u64 value, u64 mask)

hma? is it a standard abbreviation?

> -static void init_reg_state(struct bpf_reg_state *regs)
> +static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno)
>  {
> -	int i;
> -
> -	for (i = 0; i < MAX_BPF_REG; i++)
> -		mark_reg_not_init(regs, i);
> -
> -	/* frame pointer */
> -	regs[BPF_REG_FP].type = FRAME_PTR;
> -
> -	/* 1st arg to a function */
> -	regs[BPF_REG_1].type = PTR_TO_CTX;
> +	BUG_ON(regno >= MAX_BPF_REG);
> +	__mark_reg_known_zero(regs + regno);

I know we have BUG_ONs in the code and it was never hit,
but since you're rewriting it please change it to WARN_ON and
set all regs into NOT_INIT in such case.
This way if we really have a bug, it hopefully won't crash.

> -/* check read/write into an adjusted map element */
> -static int check_map_access_adj(struct bpf_verifier_env *env, u32 regno,
> +/* check read/write into a map element with possible variable offset */
> +static int check_map_access(struct bpf_verifier_env *env, u32 regno,
>  				int off, int size)
>  {
>  	struct bpf_verifier_state *state = &env->cur_state;
>  	struct bpf_reg_state *reg = &state->regs[regno];
>  	int err;
>  
> -	/* We adjusted the register to this map value, so we
> -	 * need to change off and size to min_value and max_value
> -	 * respectively to make sure our theoretical access will be
> -	 * safe.
> +	/* We may have adjusted the register to this map value, so we
> +	 * need to try adding each of min_value and max_value to off
> +	 * to make sure our theoretical access will be safe.
>  	 */
>  	if (log_level)
>  		print_verifier_state(state);
> -	env->varlen_map_value_access = true;
> +	/* If the offset is variable, we will need to be stricter in state
> +	 * pruning from now on.
> +	 */
> +	if (reg->align.mask)
> +		env->varlen_map_value_access = true;

i think this align.mask access was used in few places.
May be worth to do static inline helper with clear name?

>  	switch (reg->type) {
>  	case PTR_TO_PACKET:
> +		/* special case, because of NET_IP_ALIGN */
>  		return check_pkt_ptr_alignment(reg, off, size, strict);
> -	case PTR_TO_MAP_VALUE_ADJ:
> -		return check_val_ptr_alignment(reg, size, strict);
> +	case PTR_TO_MAP_VALUE:
> +		pointer_desc = "value ";
> +		break;
> +	case PTR_TO_CTX:
> +		pointer_desc = "context ";
> +		break;
> +	case PTR_TO_STACK:
> +		pointer_desc = "stack ";
> +		break;

thank you for making errors more human readable.

> +			char tn_buf[48];
> +
> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
> +			verbose("variable ctx access align=%s off=%d size=%d",
> +				tn_buf, off, size);
> +			return -EACCES;
> +		}
> +		off += reg->align.value;

I think 'align' is an odd name for this field.
May be rename off/align fields into
s32 fixed_off;
struct tnum var_off;

>  
> -	} else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
> +	} else if (reg->type == PTR_TO_STACK) {
> +		/* stack accesses must be at a fixed offset, so that we can
> +		 * determine what type of data were returned.
> +		 */
> +		if (reg->align.mask) {
> +			char tn_buf[48];
> +
> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
> +			verbose("variable stack access align=%s off=%d size=%d",
> +				tn_buf, off, size);
> +			return -EACCES;

hmm. why this restriction?
I thought one of key points of the diff that ptr+var tracking logic
will now apply not only to map_value, but to stack_ptr as well?

>  	}
>  
> -	if (!err && size <= 2 && value_regno >= 0 && env->allow_ptr_leaks &&
> -	    state->regs[value_regno].type == UNKNOWN_VALUE) {
> -		/* 1 or 2 byte load zero-extends, determine the number of
> -		 * zero upper bits. Not doing it fo 4 byte load, since
> -		 * such values cannot be added to ptr_to_packet anyway.
> -		 */
> -		state->regs[value_regno].imm = 64 - size * 8;
> +	if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
> +	    state->regs[value_regno].type == SCALAR_VALUE) {
> +		/* b/h/w load zero-extends, mark upper bits as known 0 */
> +		state->regs[value_regno].align.value &= (1ULL << (size * 8)) - 1;
> +		state->regs[value_regno].align.mask &= (1ULL << (size * 8)) - 1;

probably another helper from tnum.h is needed.

> +		/* sign bit is known zero, so we can bound the value */
> +		state->regs[value_regno].min_value = 0;
> +		state->regs[value_regno].max_value = min_t(u64,
> +					state->regs[value_regno].align.mask,
> +					BPF_REGISTER_MAX_RANGE);

min_t with mask? should it be align.value?

>  	}
>  	return err;
>  }
> @@ -1000,9 +1068,18 @@ static int check_xadd(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  				BPF_SIZE(insn->code), BPF_WRITE, -1);
>  }
>  
> +/* Does this register contain a constant zero? */
> +static bool register_is_null(struct bpf_reg_state reg)
> +{
> +	return reg.type == SCALAR_VALUE && reg.align.mask == 0 &&
> +	       reg.align.value == 0;

align.mask == 0 && align.value==0 into helper in tnum.h ?

> @@ -1024,7 +1101,15 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>  		return -EACCES;
>  	}
>  
> -	off = regs[regno].imm;
> +	/* Only allow fixed-offset stack reads */
> +	if (regs[regno].align.mask) {
> +		char tn_buf[48];
> +
> +		tn_strn(tn_buf, sizeof(tn_buf), regs[regno].align);
> +		verbose("invalid variable stack read R%d align=%s\n",
> +			regno, tn_buf);
> +	}

same question as before. can it be relaxed?
The support for char arr[32]; accee arr[n] was requested several times
and folks used map_value[n] as a workaround.
Seems with this var stack logic it's one step away, no?

> -		if (src_reg->imm < 48) {
> -			verbose("cannot add integer value with %lld upper zero bits to ptr_to_packet\n",
> -				src_reg->imm);
> -			return -EACCES;
> -		}
> -
> -		had_id = (dst_reg->id != 0);
> -
> -		/* dst_reg stays as pkt_ptr type and since some positive
> -		 * integer value was added to the pointer, increment its 'id'
> -		 */
> -		dst_reg->id = ++env->id_gen;

great to see it's being generalized.

> +	if (ptr_reg->type == PTR_TO_MAP_VALUE_OR_NULL) {
> +		if (!env->allow_ptr_leaks) {
> +			verbose("R%d pointer arithmetic on PTR_TO_MAP_VALUE_OR_NULL prohibited, null-check it first\n",
> +				dst);
> +			return -EACCES;
> +		}

i guess mark_map_reg() logic will cover good cases and
actual math on ptr_to_map_or_null will happen only in broken programs.
just feels a bit fragile, since it probably depends on order we will
evaluate the branches? it's not an issue with this patch. we have
the same situation today. just thinking out loud.

> +	/* Got here implies adding two SCALAR_VALUEs */
> +	if (WARN_ON_ONCE(ptr_reg)) {
> +		verbose("verifier internal error\n");
> +		return -EINVAL;
...
> +	if (WARN_ON(!src_reg)) {
> +		verbose("verifier internal error\n");
> +		return -EINVAL;
>  	}

i'm lost with these bits.
Can you add a comment in what circumstances this can be hit
and what would be the consequences?

> +/* Returns true if (rold safe implies rcur safe) */
> +static bool regsafe(struct bpf_reg_state *rold,
> +		    struct bpf_reg_state *rcur,
> +		    bool varlen_map_access)
> +{
> +	if (memcmp(rold, rcur, sizeof(*rold)) == 0)
>  		return true;
> +	if (rold->type == NOT_INIT)
> +		/* explored state can't have used this */
>  		return true;
> +	if (rcur->type == NOT_INIT)
> +		return false;
> +	switch (rold->type) {
> +	case SCALAR_VALUE:
> +		if (rcur->type == SCALAR_VALUE) {
> +			/* new val must satisfy old val knowledge */
> +			return range_within(rold, rcur) &&
> +			       tn_in(rold->align, rcur->align);
> +		} else {
> +			/* if we knew anything about the old value, we're not
> +			 * equal, because we can't know anything about the
> +			 * scalar value of the pointer in the new value.
> +			 */
> +			return rold->min_value == BPF_REGISTER_MIN_RANGE &&
> +			       rold->max_value == BPF_REGISTER_MAX_RANGE &&
> +			       !~rold->align.mask;
> +		}
> +	case PTR_TO_MAP_VALUE:
> +		if (varlen_map_access) {
> +			/* If the new min/max/align satisfy the old ones and
> +			 * everything else matches, we are OK.
> +			 * We don't care about the 'id' value, because nothing
> +			 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
> +			 */
> +			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
> +			       range_within(rold, rcur) &&
> +			       tn_in(rold->align, rcur->align);
> +		} else {
> +			/* If the ranges/align were not the same, but
> +			 * everything else was and we didn't do a variable
> +			 * access into a map then we are a-ok.
> +			 */
> +			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0;
> +		}
> +	case PTR_TO_MAP_VALUE_OR_NULL:

does this new state comparison logic helps?
Do you have any numbers before/after in the number of insns it had to process
for the tests in selftests ?

[toc] | [next] | [standalone]

#1661356

On 08/06/17 03:32, Alexei Starovoitov wrote:
> On Wed, Jun 07, 2017 at 03:58:31PM +0100, Edward Cree wrote:
>> +/* Arithmetic and logical ops */
>> +/* Shift a tnum left (by a fixed shift) */
>> +struct tnum tn_sl(struct tnum a, u8 shift);
>> +/* Shift a tnum right (by a fixed shift) */
>> +struct tnum tn_sr(struct tnum a, u8 shift);
> I think in few month we will forget what these abbreviations mean.
> Can you change it to tnum_rshift, tnum_lshift, tnum_add ?
Sure, will do.
>> +/* half-multiply add: acc += (unknown * mask * value) */
>> +static struct tnum hma(struct tnum acc, u64 value, u64 mask)
> hma? is it a standard abbreviation?
No, just a weird operation that appears in my multiply algorithm.  Since
 it's static I didn't worry too much about naming it well.
(The abbreviation was inspired by floating point 'fma', fused multiply-add.)
>> -static void init_reg_state(struct bpf_reg_state *regs)
>> +static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno)
>>  {
>> -	int i;
>> -
>> -	for (i = 0; i < MAX_BPF_REG; i++)
>> -		mark_reg_not_init(regs, i);
>> -
>> -	/* frame pointer */
>> -	regs[BPF_REG_FP].type = FRAME_PTR;
>> -
>> -	/* 1st arg to a function */
>> -	regs[BPF_REG_1].type = PTR_TO_CTX;
>> +	BUG_ON(regno >= MAX_BPF_REG);
>> +	__mark_reg_known_zero(regs + regno);
> I know we have BUG_ONs in the code and it was never hit,
> but since you're rewriting it please change it to WARN_ON and
> set all regs into NOT_INIT in such case.
> This way if we really have a bug, it hopefully won't crash.
Sure, will do.
>> -/* check read/write into an adjusted map element */
>> -static int check_map_access_adj(struct bpf_verifier_env *env, u32 regno,
>> +/* check read/write into a map element with possible variable offset */
>> +static int check_map_access(struct bpf_verifier_env *env, u32 regno,
>>  				int off, int size)
>>  {
>>  	struct bpf_verifier_state *state = &env->cur_state;
>>  	struct bpf_reg_state *reg = &state->regs[regno];
>>  	int err;
>>  
>> -	/* We adjusted the register to this map value, so we
>> -	 * need to change off and size to min_value and max_value
>> -	 * respectively to make sure our theoretical access will be
>> -	 * safe.
>> +	/* We may have adjusted the register to this map value, so we
>> +	 * need to try adding each of min_value and max_value to off
>> +	 * to make sure our theoretical access will be safe.
>>  	 */
>>  	if (log_level)
>>  		print_verifier_state(state);
>> -	env->varlen_map_value_access = true;
>> +	/* If the offset is variable, we will need to be stricter in state
>> +	 * pruning from now on.
>> +	 */
>> +	if (reg->align.mask)
>> +		env->varlen_map_value_access = true;
> i think this align.mask access was used in few places.
> May be worth to do static inline helper with clear name?
Sure, seems reasonable.
>> +			char tn_buf[48];
>> +
>> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
>> +			verbose("variable ctx access align=%s off=%d size=%d",
>> +				tn_buf, off, size);
>> +			return -EACCES;
>> +		}
>> +		off += reg->align.value;
> I think 'align' is an odd name for this field.
> May be rename off/align fields into
> s32 fixed_off;
> struct tnum var_off;
Yeah, it got that name for 'historical' reasons i.e. this patch series
 started out as just a rewrite of the alignment tracking, then grew...
I'll do the rename in the next version.
>>  
>> -	} else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
>> +	} else if (reg->type == PTR_TO_STACK) {
>> +		/* stack accesses must be at a fixed offset, so that we can
>> +		 * determine what type of data were returned.
>> +		 */
>> +		if (reg->align.mask) {
>> +			char tn_buf[48];
>> +
>> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
>> +			verbose("variable stack access align=%s off=%d size=%d",
>> +				tn_buf, off, size);
>> +			return -EACCES;
> hmm. why this restriction?
> I thought one of key points of the diff that ptr+var tracking logic
> will now apply not only to map_value, but to stack_ptr as well?
As the comment above it says, we need to determine what was returned:
 was it STACK_MISC or STACK_SPILL, and if the latter, what kind of pointer
 was spilled there?  See check_stack_read(), which I should probably
 mention in the comment.
>>  	}
>>  
>> -	if (!err && size <= 2 && value_regno >= 0 && env->allow_ptr_leaks &&
>> -	    state->regs[value_regno].type == UNKNOWN_VALUE) {
>> -		/* 1 or 2 byte load zero-extends, determine the number of
>> -		 * zero upper bits. Not doing it fo 4 byte load, since
>> -		 * such values cannot be added to ptr_to_packet anyway.
>> -		 */
>> -		state->regs[value_regno].imm = 64 - size * 8;
>> +	if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
>> +	    state->regs[value_regno].type == SCALAR_VALUE) {
>> +		/* b/h/w load zero-extends, mark upper bits as known 0 */
>> +		state->regs[value_regno].align.value &= (1ULL << (size * 8)) - 1;
>> +		state->regs[value_regno].align.mask &= (1ULL << (size * 8)) - 1;
> probably another helper from tnum.h is needed.
I could rewrite as
 reg->align = tn_and(reg->align, tn_const((1ULL << (size * 8)) - 1))
 or do you mean a helper that takes 'size' as an argument?
>> +		/* sign bit is known zero, so we can bound the value */
>> +		state->regs[value_regno].min_value = 0;
>> +		state->regs[value_regno].max_value = min_t(u64,
>> +					state->regs[value_regno].align.mask,
>> +					BPF_REGISTER_MAX_RANGE);
> min_t with mask? should it be align.value?
Hmm, I think actually it should be (mask | value), because this is the
 max (we're taking the min of two maxes to see which is tighter).
>>  	}
>>  	return err;
>>  }
>> @@ -1000,9 +1068,18 @@ static int check_xadd(struct bpf_verifier_env *env, struct bpf_insn *insn)
>>  				BPF_SIZE(insn->code), BPF_WRITE, -1);
>>  }
>>  
>> +/* Does this register contain a constant zero? */
>> +static bool register_is_null(struct bpf_reg_state reg)
>> +{
>> +	return reg.type == SCALAR_VALUE && reg.align.mask == 0 &&
>> +	       reg.align.value == 0;
> align.mask == 0 && align.value==0 into helper in tnum.h ?
Could do, but it seems unnecessary; I don't think anything but this
 function would use it.
>> +	/* Got here implies adding two SCALAR_VALUEs */
>> +	if (WARN_ON_ONCE(ptr_reg)) {
>> +		verbose("verifier internal error\n");
>> +		return -EINVAL;
> ...
>> +	if (WARN_ON(!src_reg)) {
>> +		verbose("verifier internal error\n");
>> +		return -EINVAL;
>>  	}
> i'm lost with these bits.
> Can you add a comment in what circumstances this can be hit
> and what would be the consequences?
It should be impossible to hit either of these cases.  If we let the
 first through, we'd probably do invalid pointer arithmetic (e.g. we
 could multiply a pointer by two and think we'd just multiplied the
 variable offset).  As for the latter, we access through that pointer
 so if it were NULL we would promptly oops.
>> +/* Returns true if (rold safe implies rcur safe) */
>> +static bool regsafe(struct bpf_reg_state *rold,
>> +		    struct bpf_reg_state *rcur,
>> +		    bool varlen_map_access)
>> +{
>> +	if (memcmp(rold, rcur, sizeof(*rold)) == 0)
>>  		return true;
>> +	if (rold->type == NOT_INIT)
>> +		/* explored state can't have used this */
>>  		return true;
>> +	if (rcur->type == NOT_INIT)
>> +		return false;
>> +	switch (rold->type) {
>> +	case SCALAR_VALUE:
>> +		if (rcur->type == SCALAR_VALUE) {
>> +			/* new val must satisfy old val knowledge */
>> +			return range_within(rold, rcur) &&
>> +			       tn_in(rold->align, rcur->align);
>> +		} else {
>> +			/* if we knew anything about the old value, we're not
>> +			 * equal, because we can't know anything about the
>> +			 * scalar value of the pointer in the new value.
>> +			 */
>> +			return rold->min_value == BPF_REGISTER_MIN_RANGE &&
>> +			       rold->max_value == BPF_REGISTER_MAX_RANGE &&
>> +			       !~rold->align.mask;
>> +		}
>> +	case PTR_TO_MAP_VALUE:
>> +		if (varlen_map_access) {
>> +			/* If the new min/max/align satisfy the old ones and
>> +			 * everything else matches, we are OK.
>> +			 * We don't care about the 'id' value, because nothing
>> +			 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
>> +			 */
>> +			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
>> +			       range_within(rold, rcur) &&
>> +			       tn_in(rold->align, rcur->align);
>> +		} else {
>> +			/* If the ranges/align were not the same, but
>> +			 * everything else was and we didn't do a variable
>> +			 * access into a map then we are a-ok.
>> +			 */
>> +			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0;
>> +		}
>> +	case PTR_TO_MAP_VALUE_OR_NULL:
> does this new state comparison logic helps? Do you have any numbers before/after in the number of insns it had to process for the tests in selftests ?
I don't have the numbers, no (I'll try to collect them).  This rewrite was
 more because the data structures had changed so the old code needed changing
 to match.  It's mainly just a refactor and reimplementation of the existing
 logic, I think, extended to cover the new 'align' member as well.

-Ed

[toc] | [prev] | [next] | [standalone]

#1661480

On Thu, Jun 08, 2017 at 03:53:36PM +0100, Edward Cree wrote:
> >>  
> >> -	} else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
> >> +	} else if (reg->type == PTR_TO_STACK) {
> >> +		/* stack accesses must be at a fixed offset, so that we can
> >> +		 * determine what type of data were returned.
> >> +		 */
> >> +		if (reg->align.mask) {
> >> +			char tn_buf[48];
> >> +
> >> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
> >> +			verbose("variable stack access align=%s off=%d size=%d",
> >> +				tn_buf, off, size);
> >> +			return -EACCES;
> > hmm. why this restriction?
> > I thought one of key points of the diff that ptr+var tracking logic
> > will now apply not only to map_value, but to stack_ptr as well?
> As the comment above it says, we need to determine what was returned:
>  was it STACK_MISC or STACK_SPILL, and if the latter, what kind of pointer
>  was spilled there?  See check_stack_read(), which I should probably
>  mention in the comment.

this piece of code is not only spill/fill, but normal ldx/stx stack access.
Consider the frequent pattern that many folks tried to do:
bpf_prog()
{
  char buf[64];
  int len;

  bpf_probe_read(&len, sizeof(len), kernel_ptr_to_filename_len);
  bpf_probe_read(buf, sizeof(buf), kernel_ptr_to_filename);
  buf[len & (sizeof(buf) - 1)] = 0;
...

currently above is not supported, but when 'buf' is a pointer to map value
it works fine. Allocating extra bpf map just to do such workaround
isn't nice and since this patch generalized map_value_adj with ptr_to_stack
we can support above code too.
We can check that all bytes of stack for this variable access were
initialized already.
In the example above it will happen by bpf_probe_read (in the verifier code):
        for (i = 0; i < meta.access_size; i++) {
                err = check_mem_access(env, meta.regno, i, BPF_B, BPF_WRITE, -1);
so at the time of
  buf[len & ..] = 0
we can check that 'stx' is within the range of inited stack and allow it.

> >> +	if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
> >> +	    state->regs[value_regno].type == SCALAR_VALUE) {
> >> +		/* b/h/w load zero-extends, mark upper bits as known 0 */
> >> +		state->regs[value_regno].align.value &= (1ULL << (size * 8)) - 1;
> >> +		state->regs[value_regno].align.mask &= (1ULL << (size * 8)) - 1;
> > probably another helper from tnum.h is needed.
> I could rewrite as
>  reg->align = tn_and(reg->align, tn_const((1ULL << (size * 8)) - 1))

yep. that's perfect.

> >> +	/* Got here implies adding two SCALAR_VALUEs */
> >> +	if (WARN_ON_ONCE(ptr_reg)) {
> >> +		verbose("verifier internal error\n");
> >> +		return -EINVAL;
> > ...
> >> +	if (WARN_ON(!src_reg)) {
> >> +		verbose("verifier internal error\n");
> >> +		return -EINVAL;
> >>  	}
> > i'm lost with these bits.
> > Can you add a comment in what circumstances this can be hit
> > and what would be the consequences?
> It should be impossible to hit either of these cases.  If we let the
>  first through, we'd probably do invalid pointer arithmetic (e.g. we
>  could multiply a pointer by two and think we'd just multiplied the
>  variable offset).  As for the latter, we access through that pointer
>  so if it were NULL we would promptly oops.

I see. May be print verifier state in such warn_ons and make error
more human readable?

> >> +	case PTR_TO_MAP_VALUE_OR_NULL:
> > does this new state comparison logic helps? Do you have any numbers before/after in the number of insns it had to process for the tests in selftests ?
> I don't have the numbers, no (I'll try to collect them).  This rewrite was

Thanks. The main concern is that right now some complex programs
that cilium is using are close to the verifier complexity limit and these
big changes to amount of info recognized by the verifier can cause pruning
to be ineffective, so we need to test on big programs.
I think Daniel will be happy to test your next rev of the patches.
I'll test them as well.
At least 'insn_processed' from C code in tools/testing/selftests/bpf/
is a good estimate of how these changes affect pruning.

btw, I'm working on bpf_call support and also refactoring verifier
quite a bit, but my stuff is far from ready and I'll wait for
your rewrite to land first.
One of the things I'm working on is trying to get rid of state pruning
heuristics and use register+stack liveness information instead.
It's all experimental so far.

[toc] | [prev] | [next] | [standalone]

#1661618

On 08/06/17 17:45, Alexei Starovoitov wrote:
> On Thu, Jun 08, 2017 at 03:53:36PM +0100, Edward Cree wrote:
>>>>  
>>>> -	} else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
>>>> +	} else if (reg->type == PTR_TO_STACK) {
>>>> +		/* stack accesses must be at a fixed offset, so that we can
>>>> +		 * determine what type of data were returned.
>>>> +		 */
>>>> +		if (reg->align.mask) {
>>>> +			char tn_buf[48];
>>>> +
>>>> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
>>>> +			verbose("variable stack access align=%s off=%d size=%d",
>>>> +				tn_buf, off, size);
>>>> +			return -EACCES;
>>> hmm. why this restriction?
>>> I thought one of key points of the diff that ptr+var tracking logic
>>> will now apply not only to map_value, but to stack_ptr as well?
>> As the comment above it says, we need to determine what was returned:
>>  was it STACK_MISC or STACK_SPILL, and if the latter, what kind of pointer
>>  was spilled there?  See check_stack_read(), which I should probably
>>  mention in the comment.
> this piece of code is not only spill/fill, but normal ldx/stx stack access.
> Consider the frequent pattern that many folks tried to do:
> bpf_prog()
> {
>   char buf[64];
>   int len;
>
>   bpf_probe_read(&len, sizeof(len), kernel_ptr_to_filename_len);
>   bpf_probe_read(buf, sizeof(buf), kernel_ptr_to_filename);
>   buf[len & (sizeof(buf) - 1)] = 0;
> ...
>
> currently above is not supported, but when 'buf' is a pointer to map value
> it works fine. Allocating extra bpf map just to do such workaround
> isn't nice and since this patch generalized map_value_adj with ptr_to_stack
> we can support above code too.
> We can check that all bytes of stack for this variable access were
> initialized already.
> In the example above it will happen by bpf_probe_read (in the verifier code):
>         for (i = 0; i < meta.access_size; i++) {
>                 err = check_mem_access(env, meta.regno, i, BPF_B, BPF_WRITE, -1);
> so at the time of
>   buf[len & ..] = 0
> we can check that 'stx' is within the range of inited stack and allow it.
Yes, we could check every byte of the stack within the range [buf, buf+63]
 is a STACK_MISC and if so allow it.  But since this is not supported by the
 existing code (so it's not a regression), I'd prefer to leave that for a
 future patch - this one is quite big enough already ;-)
>>>> +	if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
>>>> +	    state->regs[value_regno].type == SCALAR_VALUE) {
>>>> +		/* b/h/w load zero-extends, mark upper bits as known 0 */
>>>> +		state->regs[value_regno].align.value &= (1ULL << (size * 8)) - 1;
>>>> +		state->regs[value_regno].align.mask &= (1ULL << (size * 8)) - 1;
>>> probably another helper from tnum.h is needed.
>> I could rewrite as
>>  reg->align = tn_and(reg->align, tn_const((1ULL << (size * 8)) - 1))
> yep. that's perfect.
In the end I settled on adding a helper
    struct tnum tnum_cast(struct tnum a, u8 size);
 since I have a bunch of other places that cast things to 32 bits.
> I see. May be print verifier state in such warn_ons and make error
> more human readable?
Good idea, I'll do that.
>>>> +	case PTR_TO_MAP_VALUE_OR_NULL:
>>> does this new state comparison logic helps? Do you have any numbers before/after in the number of insns it had to process for the tests in selftests ?
>> I don't have the numbers, no (I'll try to collect them).  This rewrite was
> Thanks. The main concern is that right now some complex programs
> that cilium is using are close to the verifier complexity limit and these
> big changes to amount of info recognized by the verifier can cause pruning
> to be ineffective, so we need to test on big programs.
> I think Daniel will be happy to test your next rev of the patches.
> I'll test them as well.
> At least 'insn_processed' from C code in tools/testing/selftests/bpf/
> is a good estimate of how these changes affect pruning.
It looks like the only place this gets recorded is as "processed %d insns"
 in the log_buf.  Is there a convenient way to get at this, or am I going
 to have to make bpf_verify_program grovel through the log sscanf()ing for
 a matching line?

-Ed

[toc] | [prev] | [next] | [standalone]

#1661707

On Thu, Jun 08, 2017 at 08:38:29PM +0100, Edward Cree wrote:
> On 08/06/17 17:45, Alexei Starovoitov wrote:
> > On Thu, Jun 08, 2017 at 03:53:36PM +0100, Edward Cree wrote:
> >>>>  
> >>>> -	} else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
> >>>> +	} else if (reg->type == PTR_TO_STACK) {
> >>>> +		/* stack accesses must be at a fixed offset, so that we can
> >>>> +		 * determine what type of data were returned.
> >>>> +		 */
> >>>> +		if (reg->align.mask) {
> >>>> +			char tn_buf[48];
> >>>> +
> >>>> +			tn_strn(tn_buf, sizeof(tn_buf), reg->align);
> >>>> +			verbose("variable stack access align=%s off=%d size=%d",
> >>>> +				tn_buf, off, size);
> >>>> +			return -EACCES;
> >>> hmm. why this restriction?
> >>> I thought one of key points of the diff that ptr+var tracking logic
> >>> will now apply not only to map_value, but to stack_ptr as well?
> >> As the comment above it says, we need to determine what was returned:
> >>  was it STACK_MISC or STACK_SPILL, and if the latter, what kind of pointer
> >>  was spilled there?  See check_stack_read(), which I should probably
> >>  mention in the comment.
> > this piece of code is not only spill/fill, but normal ldx/stx stack access.
> > Consider the frequent pattern that many folks tried to do:
> > bpf_prog()
> > {
> >   char buf[64];
> >   int len;
> >
> >   bpf_probe_read(&len, sizeof(len), kernel_ptr_to_filename_len);
> >   bpf_probe_read(buf, sizeof(buf), kernel_ptr_to_filename);
> >   buf[len & (sizeof(buf) - 1)] = 0;
> > ...
> >
> > currently above is not supported, but when 'buf' is a pointer to map value
> > it works fine. Allocating extra bpf map just to do such workaround
> > isn't nice and since this patch generalized map_value_adj with ptr_to_stack
> > we can support above code too.
> > We can check that all bytes of stack for this variable access were
> > initialized already.
> > In the example above it will happen by bpf_probe_read (in the verifier code):
> >         for (i = 0; i < meta.access_size; i++) {
> >                 err = check_mem_access(env, meta.regno, i, BPF_B, BPF_WRITE, -1);
> > so at the time of
> >   buf[len & ..] = 0
> > we can check that 'stx' is within the range of inited stack and allow it.
> Yes, we could check every byte of the stack within the range [buf, buf+63]
>  is a STACK_MISC and if so allow it.  But since this is not supported by the
>  existing code (so it's not a regression), I'd prefer to leave that for a
>  future patch - this one is quite big enough already ;-)

of course! just exploring.

> >>>> +	if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
> >>>> +	    state->regs[value_regno].type == SCALAR_VALUE) {
> >>>> +		/* b/h/w load zero-extends, mark upper bits as known 0 */
> >>>> +		state->regs[value_regno].align.value &= (1ULL << (size * 8)) - 1;
> >>>> +		state->regs[value_regno].align.mask &= (1ULL << (size * 8)) - 1;
> >>> probably another helper from tnum.h is needed.
> >> I could rewrite as
> >>  reg->align = tn_and(reg->align, tn_const((1ULL << (size * 8)) - 1))
> > yep. that's perfect.
> In the end I settled on adding a helper
>     struct tnum tnum_cast(struct tnum a, u8 size);
>  since I have a bunch of other places that cast things to 32 bits.

sounds good to me

> > I see. May be print verifier state in such warn_ons and make error
> > more human readable?
> Good idea, I'll do that.
> >>>> +	case PTR_TO_MAP_VALUE_OR_NULL:
> >>> does this new state comparison logic helps? Do you have any numbers before/after in the number of insns it had to process for the tests in selftests ?
> >> I don't have the numbers, no (I'll try to collect them).  This rewrite was
> > Thanks. The main concern is that right now some complex programs
> > that cilium is using are close to the verifier complexity limit and these
> > big changes to amount of info recognized by the verifier can cause pruning
> > to be ineffective, so we need to test on big programs.
> > I think Daniel will be happy to test your next rev of the patches.
> > I'll test them as well.
> > At least 'insn_processed' from C code in tools/testing/selftests/bpf/
> > is a good estimate of how these changes affect pruning.
> It looks like the only place this gets recorded is as "processed %d insns"
>  in the log_buf.  Is there a convenient way to get at this, or am I going
>  to have to make bpf_verify_program grovel through the log sscanf()ing for
>  a matching line?

typically we just run the tests with hacked log_level and grep.
similar stuff Dave did in test_align.c

[toc] | [prev] | [next] | [standalone]

#1662410

On 06/08/2017 06:45 PM, Alexei Starovoitov wrote:
[...]
> I think Daniel will be happy to test your next rev of the patches.
> I'll test them as well.
> At least 'insn_processed' from C code in tools/testing/selftests/bpf/
> is a good estimate of how these changes affect pruning.

Without having looked more deeply (yet), I ran couple of tests with
the cilium test suite to track complexity. Overall programs load
with the set applied, worst case increase I've seen for some of the
current progs was by ~80% from ~33k to ~60k insns. Will still go over
the code for an initial review either today or tomorrow.

> btw, I'm working on bpf_call support and also refactoring verifier
> quite a bit, but my stuff is far from ready and I'll wait for
> your rewrite to land first.
> One of the things I'm working on is trying to get rid of state pruning
> heuristics and use register+stack liveness information instead.
> It's all experimental so far.

Thanks,
Daniel

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web