bpf: Support variable offset stack access from helpers

PATCH Applied Andrey Ignatov 4 participants 9 messages Mar 29, 2019 – Apr 2, 2019

Subsystems (6)

Networking Network drivers Kselftest BPF +2 more subsystems

lore

Share & tools

lore

Andrey Ignatov

author

2019-03-29 01:02 UTC #0 lore raw

cover bpf: Support variable offset stack access from helpers

The patch set adds support for stack access with variable offset from helpers.

Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.

Andrey Ignatov (2):
bpf: Support variable offset stack access from helpers selftests/bpf: Test variable offset stack access

 kernel/bpf/verifier.c                         | 75 +++++++++++++-----
 .../testing/selftests/bpf/verifier/var_off.c  | 79 ++++++++++++++++++-
 2 files changed, 131 insertions(+), 23 deletions(-)

Signature · 1 line

2.17.1

Andrey Ignatov

author

2019-03-29 01:02 UTC #1 lore raw

PATCH 1/2 bpf: Support variable offset stack access from helpers

Currently there is a difference in how verifier checks memory access for helper arguments for PTR_TO_MAP_VALUE and PTR_TO_STACK with regard to variable part of offset.

check_map_access, that is used for PTR_TO_MAP_VALUE, can handle variable offsets just fine, so that BPF program can call a helper like this:

  some_helper(map_value_ptr + off, size);

, where offset is unknown at load time, but is checked by program to be in a safe rage (off >= 0 && off + size < map_value_size).

But it's not the case for check_stack_boundary, that is used for PTR_TO_STACK, and same code with pointer to stack is rejected by verifier:

  some_helper(stack_value_ptr + off, size);

For example:
0: (7a) *(u64 *)(r10 -16) = 0
1: (7a) *(u64 *)(r10 -8) = 0
2: (61) r2 = *(u32 *)(r1 +0)
3: (57) r2 &= 4
4: (17) r2 -= 16
5: (0f) r2 += r10
6: (18) r1 = 0xffff888111343a80
8: (85) call bpf_map_lookup_elem#1
invalid variable stack read R2 var_off=(0xfffffffffffffff0; 0x4)

Add support for variable offset access to check_stack_boundary so that if offset is checked by program to be in a safe range it's accepted by verifier.

Signed-off-by Andrey Ignatov <[email protected]>

---
 kernel/bpf/verifier.c | 75 +++++++++++++++++++++++++++++++------------
 1 file changed, 54 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +54 ~~-21~~

index 7c88099c4547..b7a7a9caa82f 100644
@@ -2157,6 +2157,29 @@ static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_ins
 				BPF_SIZE(insn->code), BPF_WRITE, -1, true);
 }
 
+static int __check_stack_boundary(struct bpf_verifier_env *env, u32 regno,
+				  int off, int access_size,
+				  bool zero_size_allowed)
+{
+	struct bpf_reg_state *reg = reg_state(env, regno);
+
+	if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
+	    access_size < 0 || (access_size == 0 && !zero_size_allowed)) {
+		if (tnum_is_const(reg->var_off)) {
+			verbose(env, "invalid stack type R%d off=%d access_size=%d\n",
+				regno, off, access_size);
+		} else {
+			char tn_buf[48];
+
+			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+			verbose(env, "invalid stack type R%d var_off=%s access_size=%d\n",
+				regno, tn_buf, access_size);
+		}
+		return -EACCES;
+	}
+	return 0;
+}
+
 /* when register 'regno' is passed into function that will read 'access_size'
  * bytes from that pointer, make sure that it's within stack boundary
  * and all elements of stack are initialized.

@@ -2169,7 +2192,7 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 {
 	struct bpf_reg_state *reg = reg_state(env, regno);
 	struct bpf_func_state *state = func(env, reg);
-	int off, i, slot, spi;
+	int err, min_off, max_off, i, slot, spi;
 
 	if (reg->type != PTR_TO_STACK) {
 		/* Allow zero-byte read from NULL, regardless of pointer type */

@@ -2183,21 +2206,23 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 		return -EACCES;
 	}
 
-	/* Only allow fixed-offset stack reads */
-	if (!tnum_is_const(reg->var_off)) {
-		char tn_buf[48];
-
-		tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
-		verbose(env, "invalid variable stack read R%d var_off=%s\n",
-			regno, tn_buf);
-		return -EACCES;
-	}
-	off = reg->off + reg->var_off.value;
-	if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
-	    access_size < 0 || (access_size == 0 && !zero_size_allowed)) {
-		verbose(env, "invalid stack type R%d off=%d access_size=%d\n",
-			regno, off, access_size);
-		return -EACCES;
+	if (tnum_is_const(reg->var_off)) {
+		min_off = max_off = reg->var_off.value + reg->off;
+		err = __check_stack_boundary(env, regno, min_off, access_size,
+					     zero_size_allowed);
+		if (err)
+			return err;
+	} else {
+		min_off = reg->smin_value + reg->off;
+		max_off = reg->umax_value + reg->off;
+		err = __check_stack_boundary(env, regno, min_off, access_size,
+					     zero_size_allowed);
+		if (err)
+			return err;
+		err = __check_stack_boundary(env, regno, max_off, access_size,
+					     zero_size_allowed);
+		if (err)
+			return err;
 	}
 
 	if (meta && meta->raw_mode) {

@@ -2206,10 +2231,10 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 		return 0;
 	}
 
-	for (i = 0; i < access_size; i++) {
+	for (i = min_off; i < max_off + access_size; i++) {
 		u8 *stype;
 
-		slot = -(off + i) - 1;
+		slot = -i - 1;
 		spi = slot / BPF_REG_SIZE;
 		if (state->allocated_stack <= slot)
 			goto err;

@@ -2222,8 +2247,16 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 			goto mark;
 		}
 err:
-		verbose(env, "invalid indirect read from stack off %d+%d size %d\n",
-			off, i, access_size);
+		if (tnum_is_const(reg->var_off)) {
+			verbose(env, "invalid indirect read from stack off %d+%d size %d\n",
+				min_off, i - min_off, access_size);
+		} else {
+			char tn_buf[48];
+
+			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+			verbose(env, "invalid indirect read from stack var_off %s+%d size %d\n",
+				tn_buf, i - min_off, access_size);
+		}
 		return -EACCES;
 mark:
 		/* reading any byte out of 8-byte 'spill_slot' will cause

@@ -2232,7 +2265,7 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 		mark_reg_read(env, &state->stack[spi].spilled_ptr,
 			      state->stack[spi].spilled_ptr.parent);
 	}
-	return update_stack_depth(env, state, off);
+	return update_stack_depth(env, state, min_off);
 }
 
 static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,

Signature · 1 line

2.17.1

Andrey Ignatov

author

2019-03-29 01:02 UTC #2 lore raw

PATCH 2/2 selftests/bpf: Test variable offset stack access

In reply to Andrey Ignatov

Test different scenarios of indirect variable-offset stack access: out of bound access (>0), min_off below initialized part of the stack, max_off+size above initialized part of the stack, initialized stack.

Example of output:
...
#856/p indirect variable-offset stack access, out of bound OK #857/p indirect variable-offset stack access, max_off+size > max_initialized OK #858/p indirect variable-offset stack access, min_off < min_initialized OK #859/p indirect variable-offset stack access, ok OK
...

Signed-off-by Andrey Ignatov <[email protected]>

---
 .../testing/selftests/bpf/verifier/var_off.c  | 79 ++++++++++++++++++-
 1 file changed, 77 insertions(+), 2 deletions(-)

tools/testing/selftests/bpf/verifier/var_off.c +77 -2

index 1e536ff121a5..c4ebd0bb0781 100644
@@ -40,7 +40,7 @@
 	.prog_type = BPF_PROG_TYPE_LWT_IN,
 },
 {
-	"indirect variable-offset stack access",
+	"indirect variable-offset stack access, out of bound",
 	.insns = {
 	/* Fill the top 8 bytes of the stack */
 	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),

@@ -60,7 +60,82 @@
 	BPF_EXIT_INSN(),
 	},
 	.fixup_map_hash_8b = { 5 },
-	.errstr = "variable stack read R2",
+	.errstr = "invalid stack type R2 var_off",
 	.result = REJECT,
 	.prog_type = BPF_PROG_TYPE_LWT_IN,
 },
+{
+	"indirect variable-offset stack access, max_off+size > max_initialized",
+	.insns = {
+	/* Fill only the second from top 8 bytes of the stack. */
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -16, 0),
+	/* Get an unknown value. */
+	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
+	/* Make it small and 4-byte aligned. */
+	BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 4),
+	BPF_ALU64_IMM(BPF_SUB, BPF_REG_2, 16),
+	/* Add it to fp.  We now have either fp-12 or fp-16, but we don't know
+	 * which. fp-12 size 8 is partially uninitialized stack.
+	 */
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_10),
+	/* Dereference it indirectly. */
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 5 },
+	.errstr = "invalid indirect read from stack var_off",
+	.result = REJECT,
+	.prog_type = BPF_PROG_TYPE_LWT_IN,
+},
+{
+	"indirect variable-offset stack access, min_off < min_initialized",
+	.insns = {
+	/* Fill only the top 8 bytes of the stack. */
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	/* Get an unknown value */
+	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
+	/* Make it small and 4-byte aligned. */
+	BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 4),
+	BPF_ALU64_IMM(BPF_SUB, BPF_REG_2, 16),
+	/* Add it to fp.  We now have either fp-12 or fp-16, but we don't know
+	 * which. fp-16 size 8 is partially uninitialized stack.
+	 */
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_10),
+	/* Dereference it indirectly. */
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 5 },
+	.errstr = "invalid indirect read from stack var_off",
+	.result = REJECT,
+	.prog_type = BPF_PROG_TYPE_LWT_IN,
+},
+{
+	"indirect variable-offset stack access, ok",
+	.insns = {
+	/* Fill the top 16 bytes of the stack. */
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -16, 0),
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	/* Get an unknown value. */
+	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
+	/* Make it small and 4-byte aligned. */
+	BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 4),
+	BPF_ALU64_IMM(BPF_SUB, BPF_REG_2, 16),
+	/* Add it to fp.  We now have either fp-12 or fp-16, we don't know
+	 * which, but either way it points to initialized stack.
+	 */
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_10),
+	/* Dereference it indirectly. */
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 6 },
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_LWT_IN,
+},

Signature · 1 line

2.17.1

Alexei Starovoitov

Applied

2019-03-29 19:10 UTC #3 lore raw

In reply to Andrey Ignatov

Quoted 5 lines · Andrey Ignatov

The patch set adds support for stack access with variable offset from helpers.
Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.

Applied. Thanks

Daniel Borkmann

maintainer

2019-04-01 16:09 UTC #4 lore raw

Quoted 8 lines · Alexei Starovoitov

Quoted 5 lines · Andrey Ignatov
The patch set adds support for stack access with variable offset from helpers.
Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.
Applied. Thanks

Hmm, I think this series needs more work unfortunately. The selftests are only checking root-only programs, which is way to little. For !root we do the spectre masking for map and stack ALU, and that hasn't been adapted here, so it will generate a wrong masking for runtime since it doesn't take variable part into account. Andrey, please take a look.

Alexei Starovoitov

2019-04-01 17:55 UTC #5 lore raw

Quoted 8 lines · Daniel Borkmann

Quoted 7 lines · Alexei Starovoitov
Quoted 5 lines · Andrey Ignatov
The patch set adds support for stack access with variable offset from helpers.
Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.

Quoted 7 lines

Quoted 1 line
Applied. Thanks
Hmm, I think this series needs more work unfortunately. The selftests are only checking root-only programs, which is way to little. For !root we do the spectre masking for map and stack ALU, and that hasn't been adapted here, so it will generate a wrong masking for runtime since it doesn't take variable part into account. Andrey, please take a look.

right. may be we should allow this for root only then?

Daniel Borkmann

maintainer

2019-04-01 18:58 UTC #6 lore raw

Quoted 11 lines · Alexei Starovoitov

Quoted 10 lines · Daniel Borkmann
Quoted 8 lines · Alexei Starovoitov
Quoted 5 lines · Andrey Ignatov
The patch set adds support for stack access with variable offset from helpers.
Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.
Applied. Thanks

Quoted 7 lines

Quoted 5 lines
Hmm, I think this series needs more work unfortunately. The selftests are only checking root-only programs, which is way to little. For !root we do the spectre masking for map and stack ALU, and that hasn't been adapted here, so it will generate a wrong masking for runtime since it doesn't take variable part into account. Andrey, please take a look.
right. may be we should allow this for root only then?

Probably yeah, though thinking more about it, what about the case where we pass in raw (uninitialized) buffers from stack into a helper? Our assumption has been thus far that given the size is const, we can mark them in verifier as initialized after the call (as helpers memset it on error). With variable access it could be within a given range from verification side, but at runtime it's concrete value, meaning, upon function return we could leak uninitialized stack where verifier thinks it has been initialized by the helper. I think the set doesn't address this either, unfortunately. (So would need to be restricted to helpers where we pass always initialized buffers into it.)

Thanks,
Daniel

Andrey Ignatov

author

2019-04-02 02:45 UTC #7 lore raw

Daniel Borkmann <[email protected]> [Mon, 2019-04-01 11:58 -0700]:

Quoted 12 lines · Alexei Starovoitov

Quoted 11 lines · Daniel Borkmann
Quoted 10 lines · Alexei Starovoitov
Quoted 8 lines · Andrey Ignatov
Quoted 5 lines
The patch set adds support for stack access with variable offset from helpers.
Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.
Applied. Thanks

Quoted 7 lines

Quoted 7 lines
Quoted 5 lines
Hmm, I think this series needs more work unfortunately. The selftests are only checking root-only programs, which is way to little. For !root we do the spectre masking for map and stack ALU, and that hasn't been adapted here, so it will generate a wrong masking for runtime since it doesn't take variable part into account. Andrey, please take a look.
right. may be we should allow this for root only then?

Thanks Daniel! I missed this spectre masking for stack ALU.

I read the code and see that, yeah, retrieve_ptr_limit, that is called from sanitize_ptr_alu, doesn't take variable offset into account.

Though since sanitation happens only for unpriv mode I agree with Alexei that we can just deny variable offsets for unpriv. That's probably the simplest option and it should be fine for use-case I have for variable offset (bpf_strto{l,ul}).

I'll send follow-up with this change.

Quoted 9 lines

Probably yeah, though thinking more about it, what about the case where we pass in raw (uninitialized) buffers from stack into a helper? Our assumption has been thus far that given the size is const, we can mark them in verifier as initialized after the call (as helpers memset it on error). With variable access it could be within a given range from verification side, but at runtime it's concrete value, meaning, upon function return we could leak uninitialized stack where verifier thinks it has been initialized by the helper. I think the set doesn't address this either, unfortunately. (So would need to be restricted to helpers where we pass always initialized buffers into it.)

Thanks again for another great catch! I'll change it so that if (meta && meta->raw_mode) (i.e. buffer wasn't initialized), variable offset will be rejected.

I'll also add more tests for both scenarios and send follow-up with all these changes.

Thank you!

Signature · 1 line

Andrey Ignatov

Daniel Borkmann

maintainer

2019-04-02 08:54 UTC #8 lore raw

Quoted 26 lines · Andrey Ignatov

Daniel Borkmann <[email protected]> [Mon, 2019-04-01 11:58 -0700]:
Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Daniel Borkmann
Quoted 10 lines · Alexei Starovoitov
Quoted 8 lines · Andrey Ignatov
Quoted 5 lines
The patch set adds support for stack access with variable offset from helpers.
Patch 1 is the main patch in the set and provides more details. Patch 2 adds selftests for new functionality.
Applied. Thanks
Quoted 7 lines
Quoted 7 lines
Quoted 5 lines
Hmm, I think this series needs more work unfortunately. The selftests are only checking root-only programs, which is way to little. For !root we do the spectre masking for map and stack ALU, and that hasn't been adapted here, so it will generate a wrong masking for runtime since it doesn't take variable part into account. Andrey, please take a look.
right. may be we should allow this for root only then?
Thanks Daniel! I missed this spectre masking for stack ALU.
I read the code and see that, yeah, retrieve_ptr_limit, that is called from sanitize_ptr_alu, doesn't take variable offset into account.

Quoted 6 lines

Though since sanitation happens only for unpriv mode I agree with Alexei that we can just deny variable offsets for unpriv. That's probably the simplest option and it should be fine for use-case I have for variable offset (bpf_strto{l,ul}).
I'll send follow-up with this change.

Ok, please make sure to also add a comment into retrieve_ptr_limit() on why we don't handle var offset.

Quoted 10 lines

Quoted 9 lines
Probably yeah, though thinking more about it, what about the case where we pass in raw (uninitialized) buffers from stack into a helper? Our assumption has been thus far that given the size is const, we can mark them in verifier as initialized after the call (as helpers memset it on error). With variable access it could be within a given range from verification side, but at runtime it's concrete value, meaning, upon function return we could leak uninitialized stack where verifier thinks it has been initialized by the helper. I think the set doesn't address this either, unfortunately. (So would need to be restricted to helpers where we pass always initialized buffers into it.)

Quoted 6 lines

Thanks again for another great catch! I'll change it so that if (meta && meta->raw_mode) (i.e. buffer wasn't initialized), variable offset will be rejected.
I'll also add more tests for both scenarios and send follow-up with all these changes.

Quoted 3 lines

Thank you!