netdev - RE: [bpf-next PATCH 1/4] bpf: verifier track null pointer branch

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:   Mon, 18 May 2020 13:35:53 -0700
From:   John Fastabend <john.fastabend@...il.com>
To:     John Fastabend <john.fastabend@...il.com>, ast@...nel.org,
        daniel@...earbox.net
Cc:     netdev@...r.kernel.org, bpf@...r.kernel.org,
        john.fastabend@...il.com
Subject: RE: [bpf-next PATCH 1/4] bpf: verifier track null pointer
 branch_taken with JNE and JEQ

John Fastabend wrote:
> Current verifier when considering which branch may be taken on a
> conditional test with pointer returns -1 meaning either branch may
> be taken. But, we track if pointers can be NULL by using dedicated
> types for valid pointers (pointers that can not be NULL). For example,
> we have PTR_TO_SOCK and PTR_TO_SOCK_OR_NULL to indicate a pointer
> that is valid or not, PTR_TO_SOCK being the validated pointer type.

[...]

> Because at 51->53 jmp verifier promoted reg6 from type PTR_TO_SOCK_OR_NULL
> to PTR_TO_SOCK but then at 62 we still test both paths ignoring that we
> already promoted the type. So we incorrectly conclude an unreleased
> reference. To fix this we add logic in is_branch_taken to test the
> OR_NULL portion of the type and if its not possible for a pointer to
> be NULL we can prune the branch taken where 'r6 == 0x0'.
> 
> After the above additional logic is added the C code above passes
> as expected.
> 
> This makes the assumption that all pointer types PTR_TO_* that can be null
> have an equivalent type PTR_TO_*_OR_NULL logic.

I can send a v2 to update the last sentence here it is not true with code
below. Initially I thought to negate reg_type_may_be_null() so that the
guard in the branch_taken on this logic was

 if (__is_pointer_value(false, reg)) {
    if (!reg_type_may_be_null(reg->type))
       return -1;

But this pulls in other pointers which are meaningless in this context.
For example PTR_TO_STACK, PTR_TO_BTF_ID, etc. I think its easier to avoid
thinking about these contexts and also safer to just be explicit and
built a new type filter, reg_type_not_null() below. Better name suggestions
welcome.

> 
> Suggested-by: Alexei Starovoitov <ast@...nel.org>
> Reported-by: Andrey Ignatov <rdna@...com>
> Signed-off-by: John Fastabend <john.fastabend@...il.com>
> ---
>  0 files changed

With the v2 I'll fix this '0 files changed' issue here messed up my
branch mgmt a bit here when moving patches around.

Will wait a bit though to catch any other feedback.

Thanks,
John

> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 180933f..8f576e2 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -393,6 +393,14 @@ static bool type_is_sk_pointer(enum bpf_reg_type type)
>  		type == PTR_TO_XDP_SOCK;
>  }
>  
> +static bool reg_type_not_null(enum bpf_reg_type type)
> +{
k> +	return type == PTR_TO_SOCKET ||
> +		type == PTR_TO_TCP_SOCK ||
> +		type == PTR_TO_MAP_VALUE ||
> +		type == PTR_TO_SOCK_COMMON;
> +}
> +
>  static bool reg_type_may_be_null(enum bpf_reg_type type)
>  {
>  	return type == PTR_TO_MAP_VALUE_OR_NULL ||
> @@ -1970,8 +1978,9 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
>  	if (regno >= 0) {
>  		reg = &func->regs[regno];
>  		if (reg->type != SCALAR_VALUE) {
> -			WARN_ONCE(1, "backtracing misuse");
> -			return -EFAULT;
> +			if (unlikely(!reg_type_not_null(reg->type)))
> +				WARN_ONCE(1, "backtracing misuse");
> +			return 0;
>  		}
>  		if (!reg->precise)
>  			new_marks = true;
> @@ -6306,8 +6315,26 @@ static int is_branch64_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>  static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode,
>  			   bool is_jmp32)
>  {
> -	if (__is_pointer_value(false, reg))
> -		return -1;
> +	if (__is_pointer_value(false, reg)) {
> +		if (!reg_type_not_null(reg->type))
> +			return -1;
> +
> +		/* If pointer is valid tests against zero will fail so we can
> +		 * use this to direct branch taken.
> +		 */
> +		switch (opcode) {
> +		case BPF_JEQ:
> +			if (val == 0)
> +				return 0;
> +			return 1;
> +		case BPF_JNE:
> +			if (val == 0)
> +				return 1;
> +			return 0;
> +		default:
> +			return -1;
> +		}
> +	}
>  
>  	if (is_jmp32)
>  		return is_branch32_taken(reg, val, opcode);
>