netdev - [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]

Message-ID: <158983215367.6512.2773569595786906135.stgit@john-Precision-5820-Tower>
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);