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

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.

We can then use this extra information when we encounter null tests
against pointers. Consider,

  if (sk_ptr == NULL) ... else ...

if the sk_ptr has type PTR_TO_SOCK we know the null check will fail
and the null branch can not be taken.

In this patch we extend is_branch_taken to consider this extra
information and to return only the branch that will be taken. This
resolves a verifier issue reported with this C code,

 sk = bpf_sk_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0);
 bpf_printk("sk=%d\n", sk ? 1 : 0);
 if (sk)
   bpf_sk_release(sk);
 return sk ? TC_ACT_OK : TC_ACT_UNSPEC;

The generated asm then looks like this,

 43: (85) call bpf_sk_lookup_tcp#84
 44: (bf) r6 = r0                    <- do the lookup and put result in r6
 ...                                 <- do some more work
 51: (55) if r6 != 0x0 goto pc+1     <- test sk ptr for printk use
 ...
 56: (85) call bpf_trace_printk#6
 ...
 61: (15) if r6 == 0x0 goto pc+1     <- do the if (sk) test from C code
 62: (b7) r0 = 0                     <- skip release because both branches
                                        are taken in verifier
 63: (95) exit
 Unreleased reference id=3 alloc_insn=43

In the verifier path the flow is,

 51 -> 53 ... 61 -> 62

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.

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

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)
+{
+	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);

Powered by blists - more mailing lists