[PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[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.

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(-)

-- 
2.17.1

[PATCH bpf-next 1/2] bpf: Support variable offset stack access from helpers

[Andrey Ignatov]

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 <rdna@fb.com>
---
 kernel/bpf/verifier.c | 75 +++++++++++++++++++++++++++++++------------
 1 file changed, 54 insertions(+), 21 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7c88099c4547..b7a7a9caa82f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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,
-- 
2.17.1

[PATCH bpf-next 2/2] selftests/bpf: Test variable offset stack access

[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 <rdna@fb.com>
---
 .../testing/selftests/bpf/verifier/var_off.c  | 79 ++++++++++++++++++-
 1 file changed, 77 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/verifier/var_off.c b/tools/testing/selftests/bpf/verifier/var_off.c
index 1e536ff121a5..c4ebd0bb0781 100644
--- a/tools/testing/selftests/bpf/verifier/var_off.c
+++ b/tools/testing/selftests/bpf/verifier/var_off.c
@@ -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,
+},
-- 
2.17.1

Re: [PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[Alexei Starovoitov]

On Thu, Mar 28, 2019 at 6:02 PM Andrey Ignatov <rdna@fb.com> wrote:
>
> 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

Re: [PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[Daniel Borkmann]

On 03/29/2019 08:10 PM, Alexei Starovoitov wrote:
> On Thu, Mar 28, 2019 at 6:02 PM Andrey Ignatov <rdna@fb.com> wrote:
>>
>> 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.

Re: [PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[Alexei Starovoitov]

On 4/1/19 9:09 AM, Daniel Borkmann wrote:
> On 03/29/2019 08:10 PM, Alexei Starovoitov wrote:
>> On Thu, Mar 28, 2019 at 6:02 PM Andrey Ignatov <rdna@fb.com> wrote:
>>>
>>> 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.

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

Re: [PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[Daniel Borkmann]

On 04/01/2019 07:23 PM, Alexei Starovoitov wrote:
> On 4/1/19 9:09 AM, Daniel Borkmann wrote:
>> On 03/29/2019 08:10 PM, Alexei Starovoitov wrote:
>>> On Thu, Mar 28, 2019 at 6:02 PM Andrey Ignatov <rdna@fb.com> wrote:
>>>>
>>>> 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.
> 
> 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

Re: [PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[Andrey Ignatov]

Daniel Borkmann <daniel@iogearbox.net> [Mon, 2019-04-01 11:58 -0700]:
> On 04/01/2019 07:23 PM, Alexei Starovoitov wrote:
> > On 4/1/19 9:09 AM, Daniel Borkmann wrote:
> >> On 03/29/2019 08:10 PM, Alexei Starovoitov wrote:
> >>> On Thu, Mar 28, 2019 at 6:02 PM Andrey Ignatov <rdna@fb.com> wrote:
> >>>>
> >>>> 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.
> > 
> > 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.

> 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!


-- 
Andrey Ignatov

Re: [PATCH bpf-next 0/2] bpf: Support variable offset stack access from helpers

[Daniel Borkmann]

On 04/02/2019 04:45 AM, Andrey Ignatov wrote:
> Daniel Borkmann <daniel@iogearbox.net> [Mon, 2019-04-01 11:58 -0700]:
>> On 04/01/2019 07:23 PM, Alexei Starovoitov wrote:
>>> On 4/1/19 9:09 AM, Daniel Borkmann wrote:
>>>> On 03/29/2019 08:10 PM, Alexei Starovoitov wrote:
>>>>> On Thu, Mar 28, 2019 at 6:02 PM Andrey Ignatov <rdna@fb.com> wrote:
>>>>>>
>>>>>> 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.
>>>
>>> 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.

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

>> 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.

+1

> Thank you!
> 
>