[PATCH v2 4.4 1/3] bpf: fix branch pruning logic

[PATCH v2 4.4 1/3] bpf: fix branch pruning logic

[Ben Hutchings]

From: Alexei Starovoitov <ast@fb.com>

commit c131187db2d3fa2f8bf32fdf4e9a4ef805168467 upstream.

when the verifier detects that register contains a runtime constant
and it's compared with another constant it will prune exploration
of the branch that is guaranteed not to be taken at runtime.
This is all correct, but malicious program may be constructed
in such a way that it always has a constant comparison and
the other branch is never taken under any conditions.
In this case such path through the program will not be explored
by the verifier. It won't be taken at run-time either, but since
all instructions are JITed the malicious program may cause JITs
to complain about using reserved fields, etc.
To fix the issue we have to track the instructions explored by
the verifier and sanitize instructions that are dead at run time
with NOPs. We cannot reject such dead code, since llvm generates
it for valid C code, since it doesn't do as much data flow
analysis as the verifier does.

Fixes: 17a5267067f3 ("bpf: verifier (add verifier core)")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
[bwh: Backported to 4.4:
 - s/bpf_verifier_env/verifier_env/
 - Adjust context]
Signed-off-by: Ben Hutchings <ben.hutchings@codethink.co.uk>
---
v2: Restore Alexei as author

 kernel/bpf/verifier.c | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 014c2d759916..a62679711de0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -191,6 +191,7 @@ struct bpf_insn_aux_data {
 		enum bpf_reg_type ptr_type;	/* pointer type for load/store insns */
 		struct bpf_map *map_ptr;	/* pointer for call insn into lookup_elem */
 	};
+	bool seen; /* this insn was processed by the verifier */
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
@@ -1793,6 +1794,7 @@ static int do_check(struct verifier_env *env)
 			print_bpf_insn(env, insn);
 		}
 
+		env->insn_aux_data[insn_idx].seen = true;
 		if (class == BPF_ALU || class == BPF_ALU64) {
 			err = check_alu_op(env, insn);
 			if (err)
@@ -1988,6 +1990,7 @@ process_bpf_exit:
 					return err;
 
 				insn_idx++;
+				env->insn_aux_data[insn_idx].seen = true;
 			} else {
 				verbose("invalid BPF_LD mode\n");
 				return -EINVAL;
@@ -2125,6 +2128,7 @@ static int adjust_insn_aux_data(struct verifier_env *env, u32 prog_len,
 				u32 off, u32 cnt)
 {
 	struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data;
+	int i;
 
 	if (cnt == 1)
 		return 0;
@@ -2134,6 +2138,8 @@ static int adjust_insn_aux_data(struct verifier_env *env, u32 prog_len,
 	memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off);
 	memcpy(new_data + off + cnt - 1, old_data + off,
 	       sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
+	for (i = off; i < off + cnt - 1; i++)
+		new_data[i].seen = true;
 	env->insn_aux_data = new_data;
 	vfree(old_data);
 	return 0;
@@ -2152,6 +2158,25 @@ static struct bpf_prog *bpf_patch_insn_data(struct verifier_env *env, u32 off,
 	return new_prog;
 }
 
+/* The verifier does more data flow analysis than llvm and will not explore
+ * branches that are dead at run time. Malicious programs can have dead code
+ * too. Therefore replace all dead at-run-time code with nops.
+ */
+static void sanitize_dead_code(struct verifier_env *env)
+{
+	struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
+	struct bpf_insn nop = BPF_MOV64_REG(BPF_REG_0, BPF_REG_0);
+	struct bpf_insn *insn = env->prog->insnsi;
+	const int insn_cnt = env->prog->len;
+	int i;
+
+	for (i = 0; i < insn_cnt; i++) {
+		if (aux_data[i].seen)
+			continue;
+		memcpy(insn + i, &nop, sizeof(nop));
+	}
+}
+
 /* convert load instructions that access fields of 'struct __sk_buff'
  * into sequence of instructions that access fields of 'struct sk_buff'
  */
@@ -2370,6 +2395,9 @@ skip_full_check:
 	while (pop_stack(env, NULL) >= 0);
 	free_states(env);
 
+	if (ret == 0)
+		sanitize_dead_code(env);
+
 	if (ret == 0)
 		/* program is valid, convert *(u32*)(ctx + off) accesses */
 		ret = convert_ctx_accesses(env);
-- 
2.15.0.rc0

[PATCH v2 4.4 2/3] bpf: arsh is not supported in 32 bit alu thus reject it

[Ben Hutchings]

From: Daniel Borkmann <daniel@iogearbox.net>

commit 7891a87efc7116590eaba57acc3c422487802c6f upstream.

The following snippet was throwing an 'unknown opcode cc' warning
in BPF interpreter:

  0: (18) r0 = 0x0
  2: (7b) *(u64 *)(r10 -16) = r0
  3: (cc) (u32) r0 s>>= (u32) r0
  4: (95) exit

Although a number of JITs do support BPF_ALU | BPF_ARSH | BPF_{K,X}
generation, not all of them do and interpreter does neither. We can
leave existing ones and implement it later in bpf-next for the
remaining ones, but reject this properly in verifier for the time
being.

Fixes: 17a5267067f3 ("bpf: verifier (add verifier core)")
Reported-by: syzbot+93c4904c5c70348a6890@syzkaller.appspotmail.com
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
[bwh: Backported to 4.4:
 - Drop selftest changes
 - verbose() doesn't take an env pointer]
Signed-off-by: Ben Hutchings <ben.hutchings@codethink.co.uk>
---
 kernel/bpf/verifier.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a62679711de0..32af15136bf4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1165,6 +1165,11 @@ static int check_alu_op(struct verifier_env *env, struct bpf_insn *insn)
 			return -EINVAL;
 		}
 
+		if (opcode == BPF_ARSH && BPF_CLASS(insn->code) != BPF_ALU64) {
+			verbose("BPF_ARSH not supported for 32 bit ALU\n");
+			return -EINVAL;
+		}
+
 		if ((opcode == BPF_LSH || opcode == BPF_RSH ||
 		     opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
 			int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
-- 
2.15.0.rc0

[PATCH v2 4.4 3/3] bpf: reject stores into ctx via st and xadd

[Ben Hutchings]

From: Daniel Borkmann <daniel@iogearbox.net>

commit f37a8cb84cce18762e8f86a70bd6a49a66ab964c upstream.

Alexei found that verifier does not reject stores into context
via BPF_ST instead of BPF_STX. And while looking at it, we
also should not allow XADD variant of BPF_STX.

The context rewriter is only assuming either BPF_LDX_MEM- or
BPF_STX_MEM-type operations, thus reject anything other than
that so that assumptions in the rewriter properly hold. Add
test cases as well for BPF selftests.

Fixes: d691f9e8d440 ("bpf: allow programs to write to certain skb fields")
Reported-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
[bwh: Backported to 4.4:
 - Drop selftest changes
 - verbose() doesn't take an env pointer
 - s/bpf_verifier_env/verifier_env/; s/bpf_reg_state/reg_state/
 - Open-code cur_regs()]
Signed-off-by: Ben Hutchings <ben.hutchings@codethink.co.uk>
---
 kernel/bpf/verifier.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 32af15136bf4..bb3e96628228 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -683,6 +683,13 @@ static bool is_pointer_value(struct verifier_env *env, int regno)
 	}
 }
 
+static bool is_ctx_reg(struct verifier_env *env, int regno)
+{
+	const struct reg_state *reg = env->cur_state.regs + regno;
+
+	return reg->type == PTR_TO_CTX;
+}
+
 /* check whether memory at (regno + off) is accessible for t = (read | write)
  * if t==write, value_regno is a register which value is stored into memory
  * if t==read, value_regno is a register which will receive the value from memory
@@ -779,6 +786,12 @@ static int check_xadd(struct verifier_env *env, struct bpf_insn *insn)
 		return -EACCES;
 	}
 
+	if (is_ctx_reg(env, insn->dst_reg)) {
+		verbose("BPF_XADD stores into R%d context is not allowed\n",
+			insn->dst_reg);
+		return -EACCES;
+	}
+
 	/* check whether atomic_add can read the memory */
 	err = check_mem_access(env, insn->dst_reg, insn->off,
 			       BPF_SIZE(insn->code), BPF_READ, -1);
@@ -1909,6 +1922,12 @@ static int do_check(struct verifier_env *env)
 			if (err)
 				return err;
 
+			if (is_ctx_reg(env, insn->dst_reg)) {
+				verbose("BPF_ST stores into R%d context is not allowed\n",
+					insn->dst_reg);
+				return -EACCES;
+			}
+
 			/* check that memory (dst_reg + off) is writeable */
 			err = check_mem_access(env, insn->dst_reg, insn->off,
 					       BPF_SIZE(insn->code), BPF_WRITE,
-- 
2.15.0.rc0

Re: [PATCH v2 4.4 1/3] bpf: fix branch pruning logic

[Daniel Borkmann]

Hi Ben,

On 01/31/2018 07:08 PM, Ben Hutchings wrote:
> From: Alexei Starovoitov <ast@fb.com>
> 
> commit c131187db2d3fa2f8bf32fdf4e9a4ef805168467 upstream.
> 
> when the verifier detects that register contains a runtime constant
> and it's compared with another constant it will prune exploration
> of the branch that is guaranteed not to be taken at runtime.
> This is all correct, but malicious program may be constructed
> in such a way that it always has a constant comparison and
> the other branch is never taken under any conditions.
> In this case such path through the program will not be explored
> by the verifier. It won't be taken at run-time either, but since
> all instructions are JITed the malicious program may cause JITs
> to complain about using reserved fields, etc.
> To fix the issue we have to track the instructions explored by
> the verifier and sanitize instructions that are dead at run time
> with NOPs. We cannot reject such dead code, since llvm generates
> it for valid C code, since it doesn't do as much data flow
> analysis as the verifier does.
> 
> Fixes: 17a5267067f3 ("bpf: verifier (add verifier core)")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> Acked-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> [bwh: Backported to 4.4:
>  - s/bpf_verifier_env/verifier_env/
>  - Adjust context]
> Signed-off-by: Ben Hutchings <ben.hutchings@codethink.co.uk>

Thanks a lot for helping out with 4.4! There are a couple of more
needed for 4.4, see also the series [0] from few days ago. I don't
really mind at all which of those Greg cherry-picks, but it would
be good to have the 9 listed upstream commits in some form in 4.4
kernels.

Thanks & best,
Daniel

  [0] https://www.spinics.net/lists/stable/msg212526.html

Re: [PATCH v2 4.4 1/3] bpf: fix branch pruning logic

[Greg Kroah-Hartman]

On Wed, Jan 31, 2018 at 06:08:10PM +0000, Ben Hutchings wrote:
> From: Alexei Starovoitov <ast@fb.com>
> 
> commit c131187db2d3fa2f8bf32fdf4e9a4ef805168467 upstream.
> 
> when the verifier detects that register contains a runtime constant
> and it's compared with another constant it will prune exploration
> of the branch that is guaranteed not to be taken at runtime.
> This is all correct, but malicious program may be constructed
> in such a way that it always has a constant comparison and
> the other branch is never taken under any conditions.
> In this case such path through the program will not be explored
> by the verifier. It won't be taken at run-time either, but since
> all instructions are JITed the malicious program may cause JITs
> to complain about using reserved fields, etc.
> To fix the issue we have to track the instructions explored by
> the verifier and sanitize instructions that are dead at run time
> with NOPs. We cannot reject such dead code, since llvm generates
> it for valid C code, since it doesn't do as much data flow
> analysis as the verifier does.
> 
> Fixes: 17a5267067f3 ("bpf: verifier (add verifier core)")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> Acked-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> [bwh: Backported to 4.4:
>  - s/bpf_verifier_env/verifier_env/
>  - Adjust context]
> Signed-off-by: Ben Hutchings <ben.hutchings@codethink.co.uk>
> ---
> v2: Restore Alexei as author

All 3 of these are already queued up thanks to backport from Daniel.

greg k-h