netdev - Re: [PATCH/RFC v2 bpf-next 05/19] bpf: split read liveness into REG_LIVE_READ64 and REG_LIVE

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 10 Apr 2019 19:52:18 -0700
From:   Jakub Kicinski <jakub.kicinski@...ronome.com>
To:     Jiong Wang <jiong.wang@...ronome.com>
Cc:     alexei.starovoitov@...il.com, daniel@...earbox.net,
        bpf@...r.kernel.org, netdev@...r.kernel.org,
        oss-drivers@...ronome.com
Subject: Re: [PATCH/RFC v2 bpf-next 05/19] bpf: split read liveness into
 REG_LIVE_READ64 and REG_LIVE_READ32

On Wed, 10 Apr 2019 20:50:19 +0100, Jiong Wang wrote:
> Register liveness infrastructure doesn't track register read width at the
> moment, while the width information will be needed for the later 32-bit
> safety analysis pass.
> 
> This patch take the first step to split read liveness into REG_LIVE_READ64
> and REG_LIVE_READ32.
> 
> Liveness propagation code are updated accordingly. They are taught to
> understand how to propagate REG_LIVE_READ64 and REG_LIVE_READ32 at the same
> propagation iteration. For example, "mark_reg_read" now propagate "flags"
> which could be multiple read bits instead of the single REG_LIVE_READ64.
> 
> A write still screen off all width of reads.
> 
> Signed-off-by: Jiong Wang <jiong.wang@...ronome.com>
> ---
>  include/linux/bpf_verifier.h |   8 +--
>  kernel/bpf/verifier.c        | 119 +++++++++++++++++++++++++++++++++++++++----
>  2 files changed, 113 insertions(+), 14 deletions(-)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index b3ab61f..fba0ebb 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -36,9 +36,11 @@
>   */
>  enum bpf_reg_liveness {
>  	REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
> -	REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
> -	REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
> -	REG_LIVE_DONE = 4, /* liveness won't be updating this register anymore */
> +	REG_LIVE_READ32 = 0x1, /* reg was read, so we're sensitive to initial value */
> +	REG_LIVE_READ64 = 0x2, /* likewise, but full 64-bit content matters */
> +	REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
> +	REG_LIVE_WRITTEN = 0x4, /* reg was written first, screening off later reads */
> +	REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */
>  };
>  
>  struct bpf_reg_state {
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index bd30a65..44e4278 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1135,7 +1135,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
>   */
>  static int mark_reg_read(struct bpf_verifier_env *env,
>  			 const struct bpf_reg_state *state,
> -			 struct bpf_reg_state *parent)
> +			 struct bpf_reg_state *parent, u8 flags)
>  {
>  	bool writes = parent == state->parent; /* Observe write marks */
>  	int cnt = 0;
> @@ -1150,17 +1150,17 @@ static int mark_reg_read(struct bpf_verifier_env *env,
>  				parent->var_off.value, parent->off);
>  			return -EFAULT;
>  		}
> -		if (parent->live & REG_LIVE_READ)
> +		if ((parent->live & REG_LIVE_READ) == flags)
>  			/* The parentage chain never changes and
> -			 * this parent was already marked as LIVE_READ.
> +			 * this parent was already marked with all read bits.

Do we have to propagate all read bits?  Read64 is strictly stronger
than read32, as long as read64 is set on the parent we should be good?

>  			 * There is no need to keep walking the chain again and
> -			 * keep re-marking all parents as LIVE_READ.
> +			 * keep re-marking all parents with reads bits in flags.
>  			 * This case happens when the same register is read
>  			 * multiple times without writes into it in-between.
>  			 */
>  			break;
>  		/* ... then we depend on parent's value */
> -		parent->live |= REG_LIVE_READ;
> +		parent->live |= flags;
>  		state = parent;
>  		parent = state->parent;
>  		writes = true;

> @@ -6196,12 +6286,19 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env,
>  				  struct bpf_reg_state *reg,
>  				  struct bpf_reg_state *parent_reg)
>  {
> +	u8 parent_bits = parent_reg->live & REG_LIVE_READ;
> +	u8 bits = reg->live & REG_LIVE_READ;
> +	u8 bits_diff = parent_bits ^ bits;
> +	u8 bits_prop = bits_diff & bits;
>  	int err;
>  
> -	if (parent_reg->live & REG_LIVE_READ || !(reg->live & REG_LIVE_READ))
> +	/* "reg" and "parent_reg" has the same read bits, or the bit doesn't
> +	 * belong to "reg".
> +	 */
> +	if (!bits_diff || !bits_prop)

bits_prop is a subset of bits_diff, no?  !bits_prop is always true
if !bits_diff is true, no need to check both.

>  		return 0;
> 
> -	err = mark_reg_read(env, reg, parent_reg);
> +	err = mark_reg_read(env, reg, parent_reg, bits_prop);
>  	if (err)
>  		return err;
>