[PATCH bpf-next 0/5] bpf: Fix indirect var_off stack access support

[PATCH bpf-next 0/5] bpf: Fix indirect var_off stack access support

[Andrey Ignatov]

This patch set is a follow-up for discussion [1].

It fixes variable offset stack access handling for raw and unprivileged
mode, rejecting both of them.

Patch 1 handles raw (uninitialized) mode.
Patch 2 adds test for raw mode.
Patch 3 handles unprivileged mode.
Patch 4 adds test for unprivileged mode.
Patch 5 is a minor fix in verbose log.

Unprivileged mode is an interesting case since one (and only?) way to come up
with variable offset is to use pointer arithmetics. Though pointer arithmetics
is already prohibited for unprivileged mode. I'm not sure if it's enough though
and it seems like a good idea to still reject variable offset for unpriv in
check_stack_boundary(). Please see patches 3 and 4 for more details on this.

[1] https://marc.info/?l=linux-netdev&m=155419526427742&w=2

Andrey Ignatov (5):
  bpf: Reject indirect var_off stack access in raw mode
  selftests/bpf: Test indirect var_off stack access in raw mode
  bpf: Reject indirect var_off stack access in unpriv mode
  selftests/bpf: Test indirect var_off stack access in unpriv mode
  bpf: Add missed newline in verifier verbose log

 kernel/bpf/verifier.c                         | 43 ++++++++++++---
 .../testing/selftests/bpf/verifier/var_off.c  | 54 +++++++++++++++++++
 2 files changed, 90 insertions(+), 7 deletions(-)

-- 
2.17.1

[PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Andrey Ignatov]

It's hard to guarantee that whole memory is marked as initialized on
helper return if uninitialized stack is accessed with variable offset
since specific bounds are unknown to verifier. This may cause
uninitialized stack leaking.

Reject such an access in check_stack_boundary to prevent possible
leaking.

There are no known use-cases for indirect uninitialized stack access
with variable offset so it shouldn't break anything.

Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
Reported-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Andrey Ignatov <rdna@fb.com>
---
 kernel/bpf/verifier.c | 25 +++++++++++++++++++------
 1 file changed, 19 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b7a7a9caa82f..12b84307ffa8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 					     zero_size_allowed);
 		if (err)
 			return err;
+		if (meta && meta->raw_mode) {
+			meta->access_size = access_size;
+			meta->regno = regno;
+			return 0;
+		}
 	} else {
+		/* Only initialized buffer on stack is allowed to be accessed
+		 * with variable offset. With uninitialized buffer it's hard to
+		 * guarantee that whole memory is marked as initialized on
+		 * helper return since specific bounds are unknown what may
+		 * cause uninitialized stack leaking.
+		 */
+		if (meta && meta->raw_mode) {
+			char tn_buf[48];
+
+			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
+				regno, tn_buf);
+			return -EACCES;
+		}
 		min_off = reg->smin_value + reg->off;
 		max_off = reg->umax_value + reg->off;
 		err = __check_stack_boundary(env, regno, min_off, access_size,
@@ -2225,12 +2244,6 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 			return err;
 	}
 
-	if (meta && meta->raw_mode) {
-		meta->access_size = access_size;
-		meta->regno = regno;
-		return 0;
-	}
-
 	for (i = min_off; i < max_off + access_size; i++) {
 		u8 *stype;
 
-- 
2.17.1

[PATCH bpf-next 2/5] selftests/bpf: Test indirect var_off stack access in raw mode

[Andrey Ignatov]

Test that verifier rejects indirect access to uninitialized stack with
variable offset.

Example of output:
  # ./test_verifier
  ...
  #859/p indirect variable-offset stack access, uninitialized OK

Signed-off-by: Andrey Ignatov <rdna@fb.com>
---
 .../testing/selftests/bpf/verifier/var_off.c  | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/var_off.c b/tools/testing/selftests/bpf/verifier/var_off.c
index c4ebd0bb0781..7d095bd04636 100644
--- a/tools/testing/selftests/bpf/verifier/var_off.c
+++ b/tools/testing/selftests/bpf/verifier/var_off.c
@@ -114,6 +114,33 @@
 	.result = REJECT,
 	.prog_type = BPF_PROG_TYPE_LWT_IN,
 },
+{
+	"indirect variable-offset stack access, uninitialized",
+	.insns = {
+	BPF_MOV64_IMM(BPF_REG_2, 6),
+	BPF_MOV64_IMM(BPF_REG_3, 28),
+	/* 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_4, BPF_REG_1, 0),
+	/* Make it small and 4-byte aligned. */
+	BPF_ALU64_IMM(BPF_AND, BPF_REG_4, 4),
+	BPF_ALU64_IMM(BPF_SUB, BPF_REG_4, 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_4, BPF_REG_10),
+	BPF_MOV64_IMM(BPF_REG_5, 8),
+	/* Dereference it indirectly. */
+	BPF_EMIT_CALL(BPF_FUNC_getsockopt),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.errstr = "R4 invalid indirect access to uninitialized stack var_off=",
+	.result = REJECT,
+	.prog_type = BPF_PROG_TYPE_SOCK_OPS,
+},
 {
 	"indirect variable-offset stack access, ok",
 	.insns = {
-- 
2.17.1

[PATCH bpf-next 3/5] bpf: Reject indirect var_off stack access in unpriv mode

[Andrey Ignatov]

Proper support of indirect stack access with variable offset in
unprivileged mode (!root) requires corresponding support in Spectre
masking for stack ALU in retrieve_ptr_limit().

There are no use-case for variable offset in unprivileged mode though so
make verifier reject such accesses for simplicity.

Pointer arithmetics is one (and only?) way to cause variable offset and
it's already rejected in unpriv mode so that verifier won't even get to
helper function whose argument contains variable offset, e.g.:

  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
  variable stack access var_off=(0xfffffffffffffff0; 0x4) off=-16 size=1R2
  stack pointer arithmetic goes out of range, prohibited for !root

Still it looks like a good idea to reject variable offset indirect stack
access for unprivileged mode in check_stack_boundary() explicitly.

Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
Reported-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Andrey Ignatov <rdna@fb.com>
---
 kernel/bpf/verifier.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 12b84307ffa8..6c8c53db9555 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2218,6 +2218,19 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
 			return 0;
 		}
 	} else {
+		/* Variable offset is prohibited for unprivileged mode for
+		 * simplicity since it requires corresponding support in
+		 * Spectre masking for stack ALU.
+		 * See also retrieve_ptr_limit().
+		 */
+		if (!env->allow_ptr_leaks) {
+			char tn_buf[48];
+
+			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+			verbose(env, "R%d indirect variable offset stack access prohibited for !root, var_off=%s\n",
+				regno, tn_buf);
+			return -EACCES;
+		}
 		/* Only initialized buffer on stack is allowed to be accessed
 		 * with variable offset. With uninitialized buffer it's hard to
 		 * guarantee that whole memory is marked as initialized on
@@ -3359,6 +3372,9 @@ static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,
 
 	switch (ptr_reg->type) {
 	case PTR_TO_STACK:
+		/* Indirect variable offset stack access is prohibited in
+		 * unprivileged mode so it's not handled here.
+		 */
 		off = ptr_reg->off + ptr_reg->var_off.value;
 		if (mask_to_left)
 			*ptr_limit = MAX_BPF_STACK + off;
-- 
2.17.1

[PATCH bpf-next 4/5] selftests/bpf: Test indirect var_off stack access in unpriv mode

[Andrey Ignatov]

Test that verifier rejects indirect stack access with variable offset in
unprivileged mode and accepts same code in privileged mode.

Since pointer arithmetics is prohibited in unprivileged mode verifier
should reject the program even before it gets to helper call that uses
variable offset, at the time when that variable offset is trying to be
constructed.

Example of output:
  # ./test_verifier
  ...
  #859/u indirect variable-offset stack access, priv vs unpriv OK
  #859/p indirect variable-offset stack access, priv vs unpriv OK

Signed-off-by: Andrey Ignatov <rdna@fb.com>
---
 .../testing/selftests/bpf/verifier/var_off.c  | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/var_off.c b/tools/testing/selftests/bpf/verifier/var_off.c
index 7d095bd04636..c83d9942c1bc 100644
--- a/tools/testing/selftests/bpf/verifier/var_off.c
+++ b/tools/testing/selftests/bpf/verifier/var_off.c
@@ -114,6 +114,33 @@
 	.result = REJECT,
 	.prog_type = BPF_PROG_TYPE_LWT_IN,
 },
+{
+	"indirect variable-offset stack access, priv vs unpriv",
+	.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 },
+	.errstr_unpriv = "R2 stack pointer arithmetic goes out of range, prohibited for !root",
+	.result_unpriv = REJECT,
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+},
 {
 	"indirect variable-offset stack access, uninitialized",
 	.insns = {
-- 
2.17.1

[PATCH bpf-next 5/5] bpf: Add missed newline in verifier verbose log

[Andrey Ignatov]

check_stack_access() that prints verbose log is used in
adjust_ptr_min_max_vals() that prints its own verbose log and now they
stick together, e.g.:

  variable stack access var_off=(0xfffffffffffffff0; 0x4) off=-16
  size=1R2 stack pointer arithmetic goes out of range, prohibited for
  !root

Add missing newline so that log is more readable:
  variable stack access var_off=(0xfffffffffffffff0; 0x4) off=-16 size=1
  R2 stack pointer arithmetic goes out of range, prohibited for !root

Fixes: f1174f77b50c ("bpf/verifier: rework value tracking")
Signed-off-by: Andrey Ignatov <rdna@fb.com>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6c8c53db9555..2ed6eeed614d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1413,7 +1413,7 @@ static int check_stack_access(struct bpf_verifier_env *env,
 		char tn_buf[48];
 
 		tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
-		verbose(env, "variable stack access var_off=%s off=%d size=%d",
+		verbose(env, "variable stack access var_off=%s off=%d size=%d\n",
 			tn_buf, off, size);
 		return -EACCES;
 	}
-- 
2.17.1

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Daniel Borkmann]

On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
> It's hard to guarantee that whole memory is marked as initialized on
> helper return if uninitialized stack is accessed with variable offset
> since specific bounds are unknown to verifier. This may cause
> uninitialized stack leaking.
> 
> Reject such an access in check_stack_boundary to prevent possible
> leaking.
> 
> There are no known use-cases for indirect uninitialized stack access
> with variable offset so it shouldn't break anything.
> 
> Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
> Reported-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: Andrey Ignatov <rdna@fb.com>
> ---
>  kernel/bpf/verifier.c | 25 +++++++++++++++++++------
>  1 file changed, 19 insertions(+), 6 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b7a7a9caa82f..12b84307ffa8 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>  					     zero_size_allowed);
>  		if (err)
>  			return err;
> +		if (meta && meta->raw_mode) {
> +			meta->access_size = access_size;
> +			meta->regno = regno;
> +			return 0;
> +		}
>  	} else {
> +		/* Only initialized buffer on stack is allowed to be accessed
> +		 * with variable offset. With uninitialized buffer it's hard to
> +		 * guarantee that whole memory is marked as initialized on
> +		 * helper return since specific bounds are unknown what may
> +		 * cause uninitialized stack leaking.
> +		 */
> +		if (meta && meta->raw_mode) {
> +			char tn_buf[48];
> +
> +			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
> +			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
> +				regno, tn_buf);
> +			return -EACCES;
> +		}

Hmm, I think we should probably handle this in similar way like we do
in case of variable stack access when it comes to stack size:

               if (!tnum_is_const(reg->var_off))
                        /* For unprivileged variable accesses, disable raw
                         * mode so that the program is required to
                         * initialize all the memory that the helper could
                         * just partially fill up.
                         */
                        meta = NULL;

So we error out naturally on the loop later where we also mark for
liveness, and also allow for more flexibility if we know stack must
already be initialized in this range.

>  		min_off = reg->smin_value + reg->off;
>  		max_off = reg->umax_value + reg->off;
>  		err = __check_stack_boundary(env, regno, min_off, access_size,
> @@ -2225,12 +2244,6 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>  			return err;
>  	}
>  
> -	if (meta && meta->raw_mode) {
> -		meta->access_size = access_size;
> -		meta->regno = regno;
> -		return 0;
> -	}

This can then also stay as-is.

>  	for (i = min_off; i < max_off + access_size; i++) {
>  		u8 *stype;
>  
> 

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Daniel Borkmann]

On 04/03/2019 06:21 PM, Daniel Borkmann wrote:
> On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
>> It's hard to guarantee that whole memory is marked as initialized on
>> helper return if uninitialized stack is accessed with variable offset
>> since specific bounds are unknown to verifier. This may cause
>> uninitialized stack leaking.
>>
>> Reject such an access in check_stack_boundary to prevent possible
>> leaking.
>>
>> There are no known use-cases for indirect uninitialized stack access
>> with variable offset so it shouldn't break anything.
>>
>> Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
>> Reported-by: Daniel Borkmann <daniel@iogearbox.net>
>> Signed-off-by: Andrey Ignatov <rdna@fb.com>
>> ---
>>  kernel/bpf/verifier.c | 25 +++++++++++++++++++------
>>  1 file changed, 19 insertions(+), 6 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index b7a7a9caa82f..12b84307ffa8 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>>  					     zero_size_allowed);
>>  		if (err)
>>  			return err;
>> +		if (meta && meta->raw_mode) {
>> +			meta->access_size = access_size;
>> +			meta->regno = regno;
>> +			return 0;
>> +		}
>>  	} else {
>> +		/* Only initialized buffer on stack is allowed to be accessed
>> +		 * with variable offset. With uninitialized buffer it's hard to
>> +		 * guarantee that whole memory is marked as initialized on
>> +		 * helper return since specific bounds are unknown what may
>> +		 * cause uninitialized stack leaking.
>> +		 */
>> +		if (meta && meta->raw_mode) {
>> +			char tn_buf[48];
>> +
>> +			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
>> +			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
>> +				regno, tn_buf);
>> +			return -EACCES;
>> +		}
> 
> Hmm, I think we should probably handle this in similar way like we do
> in case of variable stack access when it comes to stack size:
> 
>                if (!tnum_is_const(reg->var_off))
>                         /* For unprivileged variable accesses, disable raw
>                          * mode so that the program is required to
>                          * initialize all the memory that the helper could
>                          * just partially fill up.
>                          */
>                         meta = NULL;
> 
> So we error out naturally on the loop later where we also mark for
> liveness, and also allow for more flexibility if we know stack must
> already be initialized in this range.
> 
>>  		min_off = reg->smin_value + reg->off;
>>  		max_off = reg->umax_value + reg->off;
>>  		err = __check_stack_boundary(env, regno, min_off, access_size,

Btw, shouldn't above two additions be sanity checked for wrap-around
resp. truncation?

>> @@ -2225,12 +2244,6 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>>  			return err;
>>  	}
>>  
>> -	if (meta && meta->raw_mode) {
>> -		meta->access_size = access_size;
>> -		meta->regno = regno;
>> -		return 0;
>> -	}
> 
> This can then also stay as-is.
> 
>>  	for (i = min_off; i < max_off + access_size; i++) {
>>  		u8 *stype;
>>  
>>
> 

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Andrey Ignatov]

Daniel Borkmann <daniel@iogearbox.net> [Wed, 2019-04-03 09:22 -0700]:
> On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
> > It's hard to guarantee that whole memory is marked as initialized on
> > helper return if uninitialized stack is accessed with variable offset
> > since specific bounds are unknown to verifier. This may cause
> > uninitialized stack leaking.
> > 
> > Reject such an access in check_stack_boundary to prevent possible
> > leaking.
> > 
> > There are no known use-cases for indirect uninitialized stack access
> > with variable offset so it shouldn't break anything.
> > 
> > Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
> > Reported-by: Daniel Borkmann <daniel@iogearbox.net>
> > Signed-off-by: Andrey Ignatov <rdna@fb.com>
> > ---
> >  kernel/bpf/verifier.c | 25 +++++++++++++++++++------
> >  1 file changed, 19 insertions(+), 6 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index b7a7a9caa82f..12b84307ffa8 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
> >  					     zero_size_allowed);
> >  		if (err)
> >  			return err;
> > +		if (meta && meta->raw_mode) {
> > +			meta->access_size = access_size;
> > +			meta->regno = regno;
> > +			return 0;
> > +		}
> >  	} else {
> > +		/* Only initialized buffer on stack is allowed to be accessed
> > +		 * with variable offset. With uninitialized buffer it's hard to
> > +		 * guarantee that whole memory is marked as initialized on
> > +		 * helper return since specific bounds are unknown what may
> > +		 * cause uninitialized stack leaking.
> > +		 */
> > +		if (meta && meta->raw_mode) {
> > +			char tn_buf[48];
> > +
> > +			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
> > +			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
> > +				regno, tn_buf);
> > +			return -EACCES;
> > +		}
> 
> Hmm, I think we should probably handle this in similar way like we do
> in case of variable stack access when it comes to stack size:
> 
>                if (!tnum_is_const(reg->var_off))
>                         /* For unprivileged variable accesses, disable raw
>                          * mode so that the program is required to
>                          * initialize all the memory that the helper could
>                          * just partially fill up.
>                          */
>                         meta = NULL;
> 
> So we error out naturally on the loop later where we also mark for
> liveness, and also allow for more flexibility if we know stack must
> already be initialized in this range.

Yeah, I think this will work.

This will change the logic a bit though.

E.g. logic in this patch will deny variable offset stack access to
ARG_PTR_TO_UNINIT_MEM no matter if corresponding stack memory is
initialized or not.

But with `meta = NULL` verifier will accept access to
ARG_PTR_TO_UNINIT_MEM on stack if that part of the stack is fully
initialized for all possible offsets.

I think the latter should be fine since if all possible bytes that can
be accessed are already initialized then there should not be problem on
return from the helper.

I'll switch to `meta = NULL` in v3. Though given the difference in the
logic, let me know if you prefer to keep the one in this patch. Thanks.

> >  		min_off = reg->smin_value + reg->off;
> >  		max_off = reg->umax_value + reg->off;
> >  		err = __check_stack_boundary(env, regno, min_off, access_size,
> > @@ -2225,12 +2244,6 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
> >  			return err;
> >  	}
> >  
> > -	if (meta && meta->raw_mode) {
> > -		meta->access_size = access_size;
> > -		meta->regno = regno;
> > -		return 0;
> > -	}
> 
> This can then also stay as-is.
> 
> >  	for (i = min_off; i < max_off + access_size; i++) {
> >  		u8 *stype;
> >  
> > 
> 

-- 
Andrey Ignatov

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Andrey Ignatov]

Daniel Borkmann <daniel@iogearbox.net> [Wed, 2019-04-03 09:46 -0700]:
> On 04/03/2019 06:21 PM, Daniel Borkmann wrote:
> > On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
> >> It's hard to guarantee that whole memory is marked as initialized on
> >> helper return if uninitialized stack is accessed with variable offset
> >> since specific bounds are unknown to verifier. This may cause
> >> uninitialized stack leaking.
> >>
> >> Reject such an access in check_stack_boundary to prevent possible
> >> leaking.
> >>
> >> There are no known use-cases for indirect uninitialized stack access
> >> with variable offset so it shouldn't break anything.
> >>
> >> Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
> >> Reported-by: Daniel Borkmann <daniel@iogearbox.net>
> >> Signed-off-by: Andrey Ignatov <rdna@fb.com>
> >> ---
> >>  kernel/bpf/verifier.c | 25 +++++++++++++++++++------
> >>  1 file changed, 19 insertions(+), 6 deletions(-)
> >>
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index b7a7a9caa82f..12b84307ffa8 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
> >>  					     zero_size_allowed);
> >>  		if (err)
> >>  			return err;
> >> +		if (meta && meta->raw_mode) {
> >> +			meta->access_size = access_size;
> >> +			meta->regno = regno;
> >> +			return 0;
> >> +		}
> >>  	} else {
> >> +		/* Only initialized buffer on stack is allowed to be accessed
> >> +		 * with variable offset. With uninitialized buffer it's hard to
> >> +		 * guarantee that whole memory is marked as initialized on
> >> +		 * helper return since specific bounds are unknown what may
> >> +		 * cause uninitialized stack leaking.
> >> +		 */
> >> +		if (meta && meta->raw_mode) {
> >> +			char tn_buf[48];
> >> +
> >> +			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
> >> +			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
> >> +				regno, tn_buf);
> >> +			return -EACCES;
> >> +		}
> > 
> > Hmm, I think we should probably handle this in similar way like we do
> > in case of variable stack access when it comes to stack size:
> > 
> >                if (!tnum_is_const(reg->var_off))
> >                         /* For unprivileged variable accesses, disable raw
> >                          * mode so that the program is required to
> >                          * initialize all the memory that the helper could
> >                          * just partially fill up.
> >                          */
> >                         meta = NULL;
> > 
> > So we error out naturally on the loop later where we also mark for
> > liveness, and also allow for more flexibility if we know stack must
> > already be initialized in this range.
> > 
> >>  		min_off = reg->smin_value + reg->off;
> >>  		max_off = reg->umax_value + reg->off;
> >>  		err = __check_stack_boundary(env, regno, min_off, access_size,
> 
> Btw, shouldn't above two additions be sanity checked for wrap-around
> resp. truncation?

Good question.

As I can see, both reg->smin_value and reg->off are checked by
check_reg_sane_offset() in adjust_ptr_min_max_vals() that handles
pointer arithmetics. And I don't know how to come up with variable
offset w/o pointer arithmetics, i.e. these both should be in
(-BPF_MAX_VAR_OFF; BPF_MAX_VAR_OFF).

As for reg->umax_value, I see that it's checked in check_func_arg()
before calling to check_helper_mem_access() (that in turn calls to
check_stack_boundary()):

		if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
			verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
                        	regno);
			return -EACCES;
		}

So my understanding is with all these checks that happen beforehand,
there should not be overflow and int is used for offset in both the old
code, that handles constant offset, and this new code for variable
offset.

Let me know if I'm missing something.

> >> @@ -2225,12 +2244,6 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
> >>  			return err;
> >>  	}
> >>  
> >> -	if (meta && meta->raw_mode) {
> >> -		meta->access_size = access_size;
> >> -		meta->regno = regno;
> >> -		return 0;
> >> -	}
> > 
> > This can then also stay as-is.
> > 
> >>  	for (i = min_off; i < max_off + access_size; i++) {
> >>  		u8 *stype;
> >>  
> >>
> > 
> 

-- 
Andrey Ignatov

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Daniel Borkmann]

On 04/03/2019 11:02 PM, Andrey Ignatov wrote:
> Daniel Borkmann <daniel@iogearbox.net> [Wed, 2019-04-03 09:22 -0700]:
>> On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
>>> It's hard to guarantee that whole memory is marked as initialized on
>>> helper return if uninitialized stack is accessed with variable offset
>>> since specific bounds are unknown to verifier. This may cause
>>> uninitialized stack leaking.
>>>
>>> Reject such an access in check_stack_boundary to prevent possible
>>> leaking.
>>>
>>> There are no known use-cases for indirect uninitialized stack access
>>> with variable offset so it shouldn't break anything.
>>>
>>> Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
>>> Reported-by: Daniel Borkmann <daniel@iogearbox.net>
>>> Signed-off-by: Andrey Ignatov <rdna@fb.com>
>>> ---
>>>  kernel/bpf/verifier.c | 25 +++++++++++++++++++------
>>>  1 file changed, 19 insertions(+), 6 deletions(-)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index b7a7a9caa82f..12b84307ffa8 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>>>  					     zero_size_allowed);
>>>  		if (err)
>>>  			return err;
>>> +		if (meta && meta->raw_mode) {
>>> +			meta->access_size = access_size;
>>> +			meta->regno = regno;
>>> +			return 0;
>>> +		}
>>>  	} else {
>>> +		/* Only initialized buffer on stack is allowed to be accessed
>>> +		 * with variable offset. With uninitialized buffer it's hard to
>>> +		 * guarantee that whole memory is marked as initialized on
>>> +		 * helper return since specific bounds are unknown what may
>>> +		 * cause uninitialized stack leaking.
>>> +		 */
>>> +		if (meta && meta->raw_mode) {
>>> +			char tn_buf[48];
>>> +
>>> +			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
>>> +			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
>>> +				regno, tn_buf);
>>> +			return -EACCES;
>>> +		}
>>
>> Hmm, I think we should probably handle this in similar way like we do
>> in case of variable stack access when it comes to stack size:
>>
>>                if (!tnum_is_const(reg->var_off))
>>                         /* For unprivileged variable accesses, disable raw
>>                          * mode so that the program is required to
>>                          * initialize all the memory that the helper could
>>                          * just partially fill up.
>>                          */
>>                         meta = NULL;
>>
>> So we error out naturally on the loop later where we also mark for
>> liveness, and also allow for more flexibility if we know stack must
>> already be initialized in this range.
> 
> Yeah, I think this will work.
> 
> This will change the logic a bit though.
> 
> E.g. logic in this patch will deny variable offset stack access to
> ARG_PTR_TO_UNINIT_MEM no matter if corresponding stack memory is
> initialized or not.
> 
> But with `meta = NULL` verifier will accept access to
> ARG_PTR_TO_UNINIT_MEM on stack if that part of the stack is fully
> initialized for all possible offsets.
> 
> I think the latter should be fine since if all possible bytes that can
> be accessed are already initialized then there should not be problem on
> return from the helper.
> 
> I'll switch to `meta = NULL` in v3. Though given the difference in the
> logic, let me know if you prefer to keep the one in this patch. Thanks.

Yes I know, I mentioned it in my email wrt more flexibility, but probably
not communicated clear enough. I think that's totally fine.

>>>  		min_off = reg->smin_value + reg->off;
>>>  		max_off = reg->umax_value + reg->off;
>>>  		err = __check_stack_boundary(env, regno, min_off, access_size,
>>> @@ -2225,12 +2244,6 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>>>  			return err;
>>>  	}
>>>  
>>> -	if (meta && meta->raw_mode) {
>>> -		meta->access_size = access_size;
>>> -		meta->regno = regno;
>>> -		return 0;
>>> -	}
>>
>> This can then also stay as-is.
>>
>>>  	for (i = min_off; i < max_off + access_size; i++) {
>>>  		u8 *stype;
>>>  
>>>
>>
> 

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Daniel Borkmann]

On 04/03/2019 11:57 PM, Andrey Ignatov wrote:
> Daniel Borkmann <daniel@iogearbox.net> [Wed, 2019-04-03 09:46 -0700]:
>> On 04/03/2019 06:21 PM, Daniel Borkmann wrote:
>>> On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
>>>> It's hard to guarantee that whole memory is marked as initialized on
>>>> helper return if uninitialized stack is accessed with variable offset
>>>> since specific bounds are unknown to verifier. This may cause
>>>> uninitialized stack leaking.
>>>>
>>>> Reject such an access in check_stack_boundary to prevent possible
>>>> leaking.
>>>>
>>>> There are no known use-cases for indirect uninitialized stack access
>>>> with variable offset so it shouldn't break anything.
>>>>
>>>> Fixes: 2011fccfb61b ("bpf: Support variable offset stack access from helpers")
>>>> Reported-by: Daniel Borkmann <daniel@iogearbox.net>
>>>> Signed-off-by: Andrey Ignatov <rdna@fb.com>
>>>> ---
>>>>  kernel/bpf/verifier.c | 25 +++++++++++++++++++------
>>>>  1 file changed, 19 insertions(+), 6 deletions(-)
>>>>
>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>> index b7a7a9caa82f..12b84307ffa8 100644
>>>> --- a/kernel/bpf/verifier.c
>>>> +++ b/kernel/bpf/verifier.c
>>>> @@ -2212,7 +2212,26 @@ static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
>>>>  					     zero_size_allowed);
>>>>  		if (err)
>>>>  			return err;
>>>> +		if (meta && meta->raw_mode) {
>>>> +			meta->access_size = access_size;
>>>> +			meta->regno = regno;
>>>> +			return 0;
>>>> +		}
>>>>  	} else {
>>>> +		/* Only initialized buffer on stack is allowed to be accessed
>>>> +		 * with variable offset. With uninitialized buffer it's hard to
>>>> +		 * guarantee that whole memory is marked as initialized on
>>>> +		 * helper return since specific bounds are unknown what may
>>>> +		 * cause uninitialized stack leaking.
>>>> +		 */
>>>> +		if (meta && meta->raw_mode) {
>>>> +			char tn_buf[48];
>>>> +
>>>> +			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
>>>> +			verbose(env, "R%d invalid indirect access to uninitialized stack var_off=%s\n",
>>>> +				regno, tn_buf);
>>>> +			return -EACCES;
>>>> +		}
>>>
>>> Hmm, I think we should probably handle this in similar way like we do
>>> in case of variable stack access when it comes to stack size:
>>>
>>>                if (!tnum_is_const(reg->var_off))
>>>                         /* For unprivileged variable accesses, disable raw
>>>                          * mode so that the program is required to
>>>                          * initialize all the memory that the helper could
>>>                          * just partially fill up.
>>>                          */
>>>                         meta = NULL;
>>>
>>> So we error out naturally on the loop later where we also mark for
>>> liveness, and also allow for more flexibility if we know stack must
>>> already be initialized in this range.
>>>
>>>>  		min_off = reg->smin_value + reg->off;
>>>>  		max_off = reg->umax_value + reg->off;
>>>>  		err = __check_stack_boundary(env, regno, min_off, access_size,
>>
>> Btw, shouldn't above two additions be sanity checked for wrap-around
>> resp. truncation?
> 
> Good question.
> 
> As I can see, both reg->smin_value and reg->off are checked by
> check_reg_sane_offset() in adjust_ptr_min_max_vals() that handles
> pointer arithmetics. And I don't know how to come up with variable
> offset w/o pointer arithmetics, i.e. these both should be in
> (-BPF_MAX_VAR_OFF; BPF_MAX_VAR_OFF).
> 
> As for reg->umax_value, I see that it's checked in check_func_arg()
> before calling to check_helper_mem_access() (that in turn calls to
> check_stack_boundary()):
> 
> 		if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
> 			verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
>                         	regno);
> 			return -EACCES;
> 		}
> 
> So my understanding is with all these checks that happen beforehand,
> there should not be overflow and int is used for offset in both the old
> code, that handles constant offset, and this new code for variable
> offset.

The latter one is on the reg with size argument, not on the reg with pointer
to stack. check_helper_mem_access() calls 'regno - 1' for the one where the
register holds the pointer to stack value.

Re: [PATCH bpf-next 1/5] bpf: Reject indirect var_off stack access in raw mode

[Andrey Ignatov]

Daniel Borkmann <daniel@iogearbox.net> [Wed, 2019-04-03 16:19 -0700]:
> On 04/03/2019 11:57 PM, Andrey Ignatov wrote:
> > Daniel Borkmann <daniel@iogearbox.net> [Wed, 2019-04-03 09:46 -0700]:
> >> On 04/03/2019 06:21 PM, Daniel Borkmann wrote:
> >>> On 04/02/2019 10:19 PM, Andrey Ignatov wrote:
...
> >>>
> >>>>  		min_off = reg->smin_value + reg->off;
> >>>>  		max_off = reg->umax_value + reg->off;
> >>>>  		err = __check_stack_boundary(env, regno, min_off, access_size,
> >>
> >> Btw, shouldn't above two additions be sanity checked for wrap-around
> >> resp. truncation?
> > 
> > Good question.
> > 
> > As I can see, both reg->smin_value and reg->off are checked by
> > check_reg_sane_offset() in adjust_ptr_min_max_vals() that handles
> > pointer arithmetics. And I don't know how to come up with variable
> > offset w/o pointer arithmetics, i.e. these both should be in
> > (-BPF_MAX_VAR_OFF; BPF_MAX_VAR_OFF).
> > 
> > As for reg->umax_value, I see that it's checked in check_func_arg()
> > before calling to check_helper_mem_access() (that in turn calls to
> > check_stack_boundary()):
> > 
> > 		if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
> > 			verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
> >                         	regno);
> > 			return -EACCES;
> > 		}
> > 
> > So my understanding is with all these checks that happen beforehand,
> > there should not be overflow and int is used for offset in both the old
> > code, that handles constant offset, and this new code for variable
> > offset.
> 
> The latter one is on the reg with size argument, not on the reg with pointer
> to stack. check_helper_mem_access() calls 'regno - 1' for the one where the
> register holds the pointer to stack value.

You're right of course. I saw how size argument is handled and that
'regno - 1', but for some reason missed it while writing previous
answer.

I was able to write a program that exploits max_off overflow, so yeah,
it is a problem. I'll fix it and send v3. Thanks for catching all these
tricky things!


-- 
Andrey Ignatov