Skip to contentSkip to conversation

Patch "bpf, verifier: add additional patterns to evaluate_reg_imm_alu" has been added to the 4.9-stable tree

PATCH [email protected] 1 participant 1 message Aug 25, 2017

Subsystems (3)
Stable branch BPF BPF core
lore
Share & tools
lore

[email protected]

author maintainer Applied
#0 lore raw

This is a note to let you know that I've just added the patch titled

bpf, verifier: add additional patterns to evaluate_reg_imm_alu

to the 4.9-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
bpf-verifier-add-additional-patterns-to-evaluate_reg_imm_alu.patch
and it can be found in the queue-4.9 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

Quoted 1 line

From foo@baz Thu Aug 24 17:44:02 PDT 2017

From: John Fastabend <[email protected]>
Date: Sun, 2 Jul 2017 02:13:30 +0200
Subject: bpf, verifier: add additional patterns to evaluate_reg_imm_alu

From: John Fastabend <[email protected]>

[ Upstream commit 43188702b3d98d2792969a3377a30957f05695e6 ]

Currently the verifier does not track imm across alu operations when the source register is of unknown type. This adds additional pattern matching to catch this and track imm. We've seen LLVM generating this pattern while working on cilium.

Signed-off-by John Fastabend <[email protected]>
Acked-by Daniel Borkmann <[email protected]>
Acked-by Alexei Starovoitov <[email protected]>
Signed-off-by David S. Miller <[email protected]>
Signed-off-by Greg Kroah-Hartman <[email protected]>
---
 kernel/bpf/verifier.c |   62 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)
kernel/bpf/verifier.c +62 -0
@@ -1467,6 +1467,65 @@ static int evaluate_reg_alu(struct bpf_v
 	return 0;
 }
 
+static int evaluate_reg_imm_alu_unknown(struct bpf_verifier_env *env,
+					struct bpf_insn *insn)
+{
+	struct bpf_reg_state *regs = env->cur_state.regs;
+	struct bpf_reg_state *dst_reg = &regs[insn->dst_reg];
+	struct bpf_reg_state *src_reg = &regs[insn->src_reg];
+	u8 opcode = BPF_OP(insn->code);
+	s64 imm_log2 = __ilog2_u64((long long)dst_reg->imm);
+
+	/* BPF_X code with src_reg->type UNKNOWN_VALUE here. */
+	if (src_reg->imm > 0 && dst_reg->imm) {
+		switch (opcode) {
+		case BPF_ADD:
+			/* dreg += sreg
+			 * where both have zero upper bits. Adding them
+			 * can only result making one more bit non-zero
+			 * in the larger value.
+			 * Ex. 0xffff (imm=48) + 1 (imm=63) = 0x10000 (imm=47)
+			 *     0xffff (imm=48) + 0xffff = 0x1fffe (imm=47)
+			 */
+			dst_reg->imm = min(src_reg->imm, 63 - imm_log2);
+			dst_reg->imm--;
+			break;
+		case BPF_AND:
+			/* dreg &= sreg
+			 * AND can not extend zero bits only shrink
+			 * Ex.  0x00..00ffffff
+			 *    & 0x0f..ffffffff
+			 *     ----------------
+			 *      0x00..00ffffff
+			 */
+			dst_reg->imm = max(src_reg->imm, 63 - imm_log2);
+			break;
+		case BPF_OR:
+			/* dreg |= sreg
+			 * OR can only extend zero bits
+			 * Ex.  0x00..00ffffff
+			 *    | 0x0f..ffffffff
+			 *     ----------------
+			 *      0x0f..00ffffff
+			 */
+			dst_reg->imm = min(src_reg->imm, 63 - imm_log2);
+			break;
+		case BPF_SUB:
+		case BPF_MUL:
+		case BPF_RSH:
+		case BPF_LSH:
+			/* These may be flushed out later */
+		default:
+			mark_reg_unknown_value(regs, insn->dst_reg);
+		}
+	} else {
+		mark_reg_unknown_value(regs, insn->dst_reg);
+	}
+
+	dst_reg->type = UNKNOWN_VALUE;
+	return 0;
+}
+
 static int evaluate_reg_imm_alu(struct bpf_verifier_env *env,
 				struct bpf_insn *insn)
 {

@@ -1475,6 +1534,9 @@ static int evaluate_reg_imm_alu(struct b
 	struct bpf_reg_state *src_reg = &regs[insn->src_reg];
 	u8 opcode = BPF_OP(insn->code);
 
+	if (BPF_SRC(insn->code) == BPF_X && src_reg->type == UNKNOWN_VALUE)
+		return evaluate_reg_imm_alu_unknown(env, insn);
+
 	/* dst_reg->type == CONST_IMM here, simulate execution of 'add' insn.
 	 * Don't care about overflow or negative values, just add them
 	 */

Patches currently in stable-queue which might be from [email protected] are

queue-4.9/bpf-verifier-add-additional-patterns-to-evaluate_reg_imm_alu.patch