Skip to contentSkip to conversation

bpf: Fix register equivalence tracking.

PATCH Applied Alexei Starovoitov 5 participants 10 messages Oct 14, 2020 – Oct 15, 2020

Subsystems (6)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: Fix register equivalence tracking.

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly. Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register should preserve its ID to recognize:
r1 = r2
if (r1 == 20) {
#1 here both r1 and r2 == 20
} else if (r2 < 20) {
#2 here both r1 and r2 < 20
}

The patch is addressing #1 case. The #2 was working correctly already.

Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
---
 kernel/bpf/verifier.c                         | 38 ++++++++++++-------
 .../testing/selftests/bpf/verifier/regalloc.c | 26 +++++++++++++
 2 files changed, 51 insertions(+), 13 deletions(-)
kernel/bpf/verifier.c +25 -13
index c43a5e8f0818..39d7f44e7c92 100644
@@ -1010,14 +1010,9 @@ static const int caller_saved[CALLER_SAVED_REGS] = {
 static void __mark_reg_not_init(const struct bpf_verifier_env *env,
 				struct bpf_reg_state *reg);
 
-/* Mark the unknown part of a register (variable offset or scalar value) as
- * known to have the value @imm.
- */
-static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
+/* This helper doesn't clear reg->id */
+static void ___mark_reg_known(struct bpf_reg_state *reg, u64 imm)
 {
-	/* Clear id, off, and union(map_ptr, range) */
-	memset(((u8 *)reg) + sizeof(reg->type), 0,
-	       offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
 	reg->var_off = tnum_const(imm);
 	reg->smin_value = (s64)imm;
 	reg->smax_value = (s64)imm;
@@ -1030,6 +1025,17 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
 	reg->u32_max_value = (u32)imm;
 }
 
+/* Mark the unknown part of a register (variable offset or scalar value) as
+ * known to have the value @imm.
+ */
+static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
+{
+	/* Clear id, off, and union(map_ptr, range) */
+	memset(((u8 *)reg) + sizeof(reg->type), 0,
+	       offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
+	___mark_reg_known(reg, imm);
+}
+
 static void __mark_reg32_known(struct bpf_reg_state *reg, u64 imm)
 {
 	reg->var_off = tnum_const_subreg(reg->var_off, imm);
@@ -7001,14 +7007,18 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
 		struct bpf_reg_state *reg =
 			opcode == BPF_JEQ ? true_reg : false_reg;
 
-		/* For BPF_JEQ, if this is false we know nothing Jon Snow, but
-		 * if it is true we know the value for sure. Likewise for
-		 * BPF_JNE.
+		/* JEQ/JNE comparison doesn't change the register equivalence.
+		 * r1 = r2;
+		 * if (r1 == 42) goto label;
+		 * ...
+		 * label: // here both r1 and r2 are known to be 42.
+		 *
+		 * Hence when marking register as known preserve it's ID.
 		 */
 		if (is_jmp32)
 			__mark_reg32_known(reg, val32);
 		else
-			__mark_reg_known(reg, val);
+			___mark_reg_known(reg, val);
 		break;
 	}
 	case BPF_JSET:
@@ -7551,7 +7561,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 				reg_combine_min_max(&other_branch_regs[insn->src_reg],
 						    &other_branch_regs[insn->dst_reg],
 						    src_reg, dst_reg, opcode);
-			if (src_reg->id) {
+			if (src_reg->id &&
+			    !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
 				find_equal_scalars(this_branch, src_reg);
 				find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
 			}
@@ -7563,7 +7574,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 					opcode, is_jmp32);
 	}
 
-	if (dst_reg->type == SCALAR_VALUE && dst_reg->id) {
+	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
+	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
 		find_equal_scalars(this_branch, dst_reg);
 		find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
 	}
tools/testing/selftests/bpf/verifier/regalloc.c +26 -0
index ac71b824f97a..4ad7e05de706 100644
@@ -241,3 +241,29 @@
 	.result = ACCEPT,
 	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
 },
+{
+	"regalloc, spill, JEQ",
+	.insns = {
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8), /* spill r0 */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0),
+	/* The verifier will walk the rest twice with r0 == 0 and r0 == map_value */
+	BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_2, 20, 0),
+	/* The verifier will walk the rest two more times with r0 == 20 and r0 == unknown */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_10, -8), /* fill r3 with map_value */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_3, 0, 1), /* skip ldx if map_value == NULL */
+	/* Buggy verifier will think that r3 == 20 here */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_3, 0), /* read from map_value */
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_48b = { 4 },
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
+},
Signature · 1 line
2.23.0
Acked-by on v1 1/1
#1 lore raw
Quoted 18 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly. Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register should preserve its ID to recognize:
r1 = r2
if (r1 == 20) {
#1 here both r1 and r2 == 20
} else if (r2 < 20) {
#2 here both r1 and r2 < 20
}

Quoted 5 lines

The patch is addressing #1 case. The #2 was working correctly already.

Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")

---

Number of underscores is a bit subtle a difference, but this fixes the bug, so:

Quoted 4 lines
 kernel/bpf/verifier.c                         | 38 ++++++++++++-------
 .../testing/selftests/bpf/verifier/regalloc.c | 26 +++++++++++++
 2 files changed, 51 insertions(+), 13 deletions(-)

[...]

reviewer Acked-by
#2 lore raw
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly.

One thought. It seems we should never have reg->id=0 in find_equal_scalars() would it be worthwhile to add an additional check here? Something like,

if (known_reg->id == 0)
return

Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking about.

Quoted 12 lines
Quoted 12 lines

Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register should preserve its ID to recognize:
r1 = r2
if (r1 == 20) {
#1 here both r1 and r2 == 20
} else if (r2 < 20) {
#2 here both r1 and r2 < 20
}

The patch is addressing #1 case. The #2 was working correctly already.

Quoted 8 lines
Quoted 3 lines
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")

---

Number of underscores is a bit subtle a difference, but this fixes the bug, so:

Nice catch,

Quoted 7 lines
Quoted 5 lines
 kernel/bpf/verifier.c                         | 38 ++++++++++++-------
 .../testing/selftests/bpf/verifier/regalloc.c | 26 +++++++++++++
 2 files changed, 51 insertions(+), 13 deletions(-)

[...]

#3 lore raw
Quoted 12 lines · John Fastabend
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly.

Quoted 8 lines

One thought. It seems we should never have reg->id=0 in find_equal_scalars() would it be worthwhile to add an additional check here? Something like,

if (known_reg->id == 0)
return

Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking about.

That cannot happen anymore due to
if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) check in the caller.
I prefer not to repeat the same check twice. Also I really don't like defensive programming. if (known_reg->id == 0)

       return;

is exactly that.
If we had that already, as Andrii argued in the original thread, we would have never noticed this issue. <, >, <= ops would have worked, but == would be sort-of working. It would mark one branch instead of both, and sometimes neither of the branches. I'd rather have bugs like this one hurting and caught quickly instead of warm feeling of being safe and sailing into unknown.

#4 lore raw
Quoted 27 lines · Alexei Starovoitov
Quoted 12 lines · John Fastabend
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly.

Quoted 8 lines

One thought. It seems we should never have reg->id=0 in find_equal_scalars() would it be worthwhile to add an additional check here? Something like,

if (known_reg->id == 0)
return

Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking about.

That cannot happen anymore due to
if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) check in the caller.
I prefer not to repeat the same check twice. Also I really don't like defensive programming. if (known_reg->id == 0)

Quoted 7 lines
       return;

is exactly that.
If we had that already, as Andrii argued in the original thread, we would have never noticed this issue. <, >, <= ops would have worked, but == would be sort-of working. It would mark one branch instead of both, and sometimes neither of the branches. I'd rather have bugs like this one hurting and caught quickly instead of warm feeling of being safe and sailing into unknown.

Agree. Although a WARN_ON_ONCE would have also been caught.

#5 lore raw
Quoted 36 lines · John Fastabend
Quoted 27 lines · Alexei Starovoitov
Quoted 12 lines · John Fastabend
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly.

Quoted 8 lines

One thought. It seems we should never have reg->id=0 in find_equal_scalars() would it be worthwhile to add an additional check here? Something like,

if (known_reg->id == 0)
return

Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking about.

That cannot happen anymore due to
if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) check in the caller.
I prefer not to repeat the same check twice. Also I really don't like defensive programming. if (known_reg->id == 0)

Quoted 7 lines
       return;

is exactly that.
If we had that already, as Andrii argued in the original thread, we would have never noticed this issue. <, >, <= ops would have worked, but == would be sort-of working. It would mark one branch instead of both, and sometimes neither of the branches. I'd rather have bugs like this one hurting and caught quickly instead of warm feeling of being safe and sailing into unknown.

Quoted 1 line

Agree. Although a WARN_ON_ONCE would have also been caught.

Right. Such WARN_ON_ONCE would definitely have been nice either in the caller or in the callee. If I could have thought that id could be zero somehow here. In retrospect it makes sense that there is possibility that IDs of regs in this_branch and other_branch may diverge.
Hence I'm adding the warn to check for this specific divergence.

#6 lore raw
Quoted 37 lines · Alexei Starovoitov
Quoted 36 lines · John Fastabend
Quoted 34 lines · Alexei Starovoitov
Quoted 12 lines · John Fastabend
Quoted 10 lines · Andrii Nakryiko
Quoted 8 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly.

Quoted 8 lines

One thought. It seems we should never have reg->id=0 in find_equal_scalars() would it be worthwhile to add an additional check here? Something like,

if (known_reg->id == 0)
return

Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking about.

That cannot happen anymore due to
if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) check in the caller.
I prefer not to repeat the same check twice. Also I really don't like defensive programming. if (known_reg->id == 0)

       return;

is exactly that.
If we had that already, as Andrii argued in the original thread, we would have never noticed this issue. <, >, <= ops would have worked, but == would be sort-of working. It would mark one branch instead of both, and sometimes neither of the branches. I'd rather have bugs like this one hurting and caught quickly instead of warm feeling of being safe and sailing into unknown.

Quoted 7 lines
Quoted 1 line

Agree. Although a WARN_ON_ONCE would have also been caught.

Right. Such WARN_ON_ONCE would definitely have been nice either in the caller or in the callee. If I could have thought that id could be zero somehow here. In retrospect it makes sense that there is possibility that IDs of regs in this_branch and other_branch may diverge.
Hence I'm adding the warn to check for this specific divergence.

LGTM thanks.

#7 lore raw
In reply to Alexei Starovoitov
Quoted 14 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly. Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register should preserve its ID to recognize:
r1 = r2

if (r1 == 20) {
   #1 here both r1 and r2 == 20
} else if (r2 < 20) {
Quoted 7 lines

#2 here both r1 and r2 < 20
}

The patch is addressing #1 case. The #2 was working correctly already.

Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")

This fixed an issue appeared in our production system where packets may be incorrectly dropped.

Tested-by
#8 lore raw
Quoted 22 lines · Yonghong Song
Quoted 19 lines · Alexei Starovoitov

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly. Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register should preserve its ID to recognize:
r1 = r2
if (r1 == 20) {
   #1 here both r1 and r2 == 20
} else if (r2 < 20) {
   #2 here both r1 and r2 < 20
}

The patch is addressing #1 case. The #2 was working correctly already.

Quoted 7 lines
Quoted 2 lines
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")

This fixed an issue appeared in our production system where packets may be incorrectly dropped.

Sorry for typo, it should be:

#9 lore raw
In reply to Alexei Starovoitov
This patch was applied to bpf/bpf-next.git (refs/heads/master):

Hello:

This patch was applied to bpf/bpf-next.git (refs/heads/master):

Quoted 17 lines · On Wed, 14 Oct 2020 10:56:08 -0700 you wrote:

From: Alexei Starovoitov <[email protected]>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either true or false branch. In the case 'if (reg->id)' check was done on the other branch the counter part register would have reg->id == 0 when called into find_equal_scalars(). In such case the helper would incorrectly identify other registers with id == 0 as equivalent and propagate the state incorrectly. Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register should preserve its ID to recognize:
r1 = r2
if (r1 == 20) {
#1 here both r1 and r2 == 20
} else if (r2 < 20) {
#2 here both r1 and r2 < 20
}

Quoted 1 line

[...]

Here is the summary with links:
- [bpf-next] bpf: Fix register equivalence tracking.

    https://git.kernel.org/bpf/bpf-next/c/e688c3db7ca6

You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html