Skip to contentSkip to conversation

Fix bpf_dynptr_slice_rdwr stack state

RFC PATCH In review Kumar Kartikeya Dwivedi 4 participants 18 messages Feb 19, 2025 – Feb 21, 2025

Subsystems (4)
lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

cover Fix bpf_dynptr_slice_rdwr stack state

Fix verifier state tracking in case of stack pointer passed to bpf_dynptr_slice_rdwr. Add an associated selftest to verify the fix. Details in the commit log.

Kumar Kartikeya Dwivedi (2):
bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr selftests/bpf: Add selftest for bpf_dynptr_slice_rdwr r0 handling

 kernel/bpf/verifier.c                         | 51 +++++++++++++++++++
 .../testing/selftests/bpf/progs/dynptr_fail.c | 45 ++++++++++++++++
 2 files changed, 96 insertions(+)

base-commit: 654765b5c6d62efad270ec5f8a57802dc253d128
prerequisite-patch-id: c5126a1279e394882a332d246dbb726b224ba690

Signature · 1 line
2.43.5
author maintainer
#1 lore raw

RFC PATCH 1/2 bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

A complication arises when the passed in buffer is a stack pointer. The returned pointer may be used to perform writes (unlike bpf_dynptr_slice), but the verifier will be unaware of which stack slots such writes may end up overwriting. As such, a program may end up overwriting stack data (such as spilled pointers) through such return values by accident, which may cause undefined behavior.

Fix this by exploring an additional path whenever the passed in argument is a PTR_TO_STACK, and explore a path where the returned buffer is the same as this stack pointer. This allows us to ensure that the program doesn't introduce unsafe behavior when this condition is triggered at runtime.

The push_stack() call is performed after kfunc processing is over, simply fixing up the return type to PTR_TO_STACK with proper frameno, off, and var_off.

Fixes 66e3a13e7c2c ("bpf: Add bpf_dynptr_slice and bpf_dynptr_slice_rdwr")
---
 kernel/bpf/verifier.c | 51 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)
kernel/bpf/verifier.c +51 -0
index e57b7c949860..ad57144f044c 100644
@@ -329,6 +329,12 @@ struct bpf_kfunc_call_arg_meta {
 	struct {
 		struct btf_field *field;
 	} arg_rbtree_root;
+	struct {
+		u32 frameno;
+		s32 off;
+		struct tnum var_off;
+		bool found;
+	} arg_stack;
 	struct {
 		enum bpf_dynptr_type type;
 		u32 id;
@@ -7287,6 +7293,7 @@ static int check_stack_access_within_bounds(
 		min_off = (s64)reg->var_off.value + off;
 		max_off = min_off + access_size;
 	} else {
+
 		if (reg->smax_value >= BPF_MAX_VAR_OFF ||
 		    reg->smin_value <= -BPF_MAX_VAR_OFF) {
 			verbose(env, "invalid unbounded variable-offset%s stack R%d\n",
@@ -13017,6 +13024,22 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 				meta->arg_constant.value = size_reg->var_off.value;
 			}
 
+			/* We need to simulate a path where return value is the
+			 * stack buffer passed into the kfunc, therefore store
+			 * its metadata here.
+			 */
+			if (buff_reg->type == PTR_TO_STACK &&
+			    meta->func_id == special_kfunc_list[KF_bpf_dynptr_slice_rdwr]) {
+				if (meta->arg_stack.found) {
+					verbose(env, "verifier internal error: only one stack argument permitted\n");
+					return -EFAULT;
+				}
+				meta->arg_stack.found = true;
+				meta->arg_stack.frameno = buff_reg->frameno;
+				meta->arg_stack.off = buff_reg->off;
+				meta->arg_stack.var_off = buff_reg->var_off;
+			}
+
 			/* Skip next '__sz' or '__szk' argument */
 			i++;
 			break;
@@ -13598,6 +13621,34 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			return err;
 	}
 
+	/* Push a state for exploration where the returned buffer is pointing to
+	 * the stack buffer passed into bpf_dynptr_slice_rdwr, otherwise we
+	 * cannot see writes to the stack solely through marking it as
+	 * PTR_TO_MEM. We don't do the same for bpf_dynptr_slice, because the
+	 * returned pointer is MEM_RDONLY, hence cannot be used to write to the
+	 * stack.
+	 */
+	if (!insn->off && meta.arg_stack.found &&
+	    insn->imm == special_kfunc_list[KF_bpf_dynptr_slice_rdwr]) {
+		struct bpf_verifier_state *branch;
+		struct bpf_reg_state *regs, *r0;
+
+		branch = push_stack(env, env->insn_idx + 1, env->insn_idx, false);
+		if (!branch) {
+			verbose(env, "failed to push state to explore stack buffer in r0\n");
+			return -ENOMEM;
+		}
+
+		regs = branch->frame[branch->curframe]->regs;
+		r0 = &regs[BPF_REG_0];
+
+		r0->type = PTR_TO_STACK;
+		mark_reg_known_zero(env, regs, BPF_REG_0);
+		r0->frameno = meta.arg_stack.frameno;
+		r0->off = meta.arg_stack.off;
+		r0->var_off = meta.arg_stack.var_off;
+	}
+
 	return 0;
 }
 
Signature · 1 line
2.43.5
author maintainer
#2 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 21 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

A complication arises when the passed in buffer is a stack pointer. The returned pointer may be used to perform writes (unlike bpf_dynptr_slice), but the verifier will be unaware of which stack slots such writes may end up overwriting. As such, a program may end up overwriting stack data (such as spilled pointers) through such return values by accident, which may cause undefined behavior.

Fix this by exploring an additional path whenever the passed in argument is a PTR_TO_STACK, and explore a path where the returned buffer is the same as this stack pointer. This allows us to ensure that the program doesn't introduce unsafe behavior when this condition is triggered at runtime.

Quoted 3 lines

The push_stack() call is performed after kfunc processing is over, simply fixing up the return type to PTR_TO_STACK with proper frameno, off, and var_off.

I just sent this out to have discussion with code and context (in selftest).

The current approach has two problems:
It fails xdp_dynptr selftest with misaligned stack access (-72+30 =
42) size 4 error.
This was happening before as well, but is surfaced because we see writes to the stack.

It also leads to veristat regression (+80-100% in states) in two selftests.

We probably want to avoid doing push_stack due to the states increase, and instead mark the stack slot instead whenever the returned PTR_TO_MEM is used for writing, but we'll have to keep remarking whenever writes happen, so it requires stashing some stack slot state in the register.
The other option is invalidating the returned PTR_TO_MEM when the buffer on the stack is written to (i.e. the stack location gets reused).

maintainer
#3 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

On Wed, 2025-02-19 at 13:56 +0100, Kumar Kartikeya Dwivedi wrote:

[...]

Quoted 10 lines

It also leads to veristat regression (+80-100% in states) in two selftests.

We probably want to avoid doing push_stack due to the states increase, and instead mark the stack slot instead whenever the returned PTR_TO_MEM is used for writing, but we'll have to keep remarking whenever writes happen, so it requires stashing some stack slot state in the register.
The other option is invalidating the returned PTR_TO_MEM when the buffer on the stack is written to (i.e. the stack location gets reused).

Would it be wrong, to always consider r0 to be a pointer to stack if buffer is provided? It's like modelling the PTR_TO_MEM with some additional precision.

Otherwise, I think push_stack() is fine, as it keeps implementation simple.

#4 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 16 lines · Eduard Zingerman

On Wed, 2025-02-19 at 13:56 +0100, Kumar Kartikeya Dwivedi wrote:

[...]

Quoted 10 lines

It also leads to veristat regression (+80-100% in states) in two selftests.

We probably want to avoid doing push_stack due to the states increase, and instead mark the stack slot instead whenever the returned PTR_TO_MEM is used for writing, but we'll have to keep remarking whenever writes happen, so it requires stashing some stack slot state in the register.
The other option is invalidating the returned PTR_TO_MEM when the buffer on the stack is written to (i.e. the stack location gets reused).

Quoted 5 lines

Would it be wrong, to always consider r0 to be a pointer to stack if buffer is provided? It's like modelling the PTR_TO_MEM with some additional precision.

Otherwise, I think push_stack() is fine, as it keeps implementation simple.

Discussed plenty of options offline with Kumar.
The next step is to experiment returning PTR_TO_STACK with mem_size.

author maintainer
#5 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

In reply to Kumar Kartikeya Dwivedi
Quoted 43 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

A complication arises when the passed in buffer is a stack pointer. The returned pointer may be used to perform writes (unlike bpf_dynptr_slice), but the verifier will be unaware of which stack slots such writes may end up overwriting. As such, a program may end up overwriting stack data (such as spilled pointers) through such return values by accident, which may cause undefined behavior.

Fix this by exploring an additional path whenever the passed in argument is a PTR_TO_STACK, and explore a path where the returned buffer is the same as this stack pointer. This allows us to ensure that the program doesn't introduce unsafe behavior when this condition is triggered at runtime.

The push_stack() call is performed after kfunc processing is over, simply fixing up the return type to PTR_TO_STACK with proper frameno, off, and var_off.

Fixes 66e3a13e7c2c ("bpf: Add bpf_dynptr_slice and bpf_dynptr_slice_rdwr")

---
[...]

        }
kernel/bpf/verifier.c +12 -0
+       /* Push a state for exploration where the returned buffer is pointing to
+        * the stack buffer passed into bpf_dynptr_slice_rdwr, otherwise we
+        * cannot see writes to the stack solely through marking it as
+        * PTR_TO_MEM. We don't do the same for bpf_dynptr_slice, because the
+        * returned pointer is MEM_RDONLY, hence cannot be used to write to the
+        * stack.
+        */
+       if (!insn->off && meta.arg_stack.found &&
+           insn->imm == special_kfunc_list[KF_bpf_dynptr_slice_rdwr]) {
+               struct bpf_verifier_state *branch;
+               struct bpf_reg_state *regs, *r0;
+

kernel/bpf/verifier.c static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, · line 13645

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+               branch = push_stack(env, env->insn_idx + 1, env->insn_idx, false);
+               if (!branch) {
+                       verbose(env, "failed to push state to explore stack buffer in r0\n");
+                       return -ENOMEM;
+               }
+
+               regs = branch->frame[branch->curframe]->regs;
+               r0 = &regs[BPF_REG_0];
+
+               r0->type = PTR_TO_STACK;

I forgot to fold in a hunk.
This needs to be marked PTR_MAYBE_NULL (preserve the set reg->id).

Quoted 2 lines

[...]

#6 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

In reply to Kumar Kartikeya Dwivedi
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

author maintainer
#7 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

I don't recall if there was a hardware/JIT specific reason to care about stack access alignment or not (on some architectures), but otherwise we can over approximately mark at 8-byte granularity for any slot(s) that overlap with the buffer to cover such a case. The second problem is slightly trickier, which makes me lean towards invalidating returned PTR_TO_MEM when stack slot is overwritten or frame is destroyed.

#8 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Quoted 8 lines

I don't recall if there was a hardware/JIT specific reason to care about stack access alignment or not (on some architectures), but otherwise we can over approximately mark at 8-byte granularity for any slot(s) that overlap with the buffer to cover such a case. The second problem is slightly trickier, which makes me lean towards invalidating returned PTR_TO_MEM when stack slot is overwritten or frame is destroyed.

author maintainer
#9 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 67 lines · Andrii Nakryiko
Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Quoted 9 lines

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Invalidation is certainly one option. The one Alexei mentioned was where we discussed bounding how much data can be read through the PTR_TO_STACK (similar to PTR_TO_MEM), and mark r0 as PTR_TO_STACK. This ends up combining the constraints of both types of pointers (it may as well be called PTR_TO_STACK_OR_MEM) without forking paths.

The benefit over the push_stack approach is that we avoid the states regression for cls_redirect and balancer_ingress.
For the selftest failure, I plan to just silence the error by changing it.

Quoted 8 lines
Quoted 8 lines

I don't recall if there was a hardware/JIT specific reason to care about stack access alignment or not (on some architectures), but otherwise we can over approximately mark at 8-byte granularity for any slot(s) that overlap with the buffer to cover such a case. The second problem is slightly trickier, which makes me lean towards invalidating returned PTR_TO_MEM when stack slot is overwritten or frame is destroyed.

#10 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 67 lines · Andrii Nakryiko
Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Quoted 9 lines

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Quoted 5 lines

Invalidation is certainly one option. The one Alexei mentioned was where we discussed bounding how much data can be read through the PTR_TO_STACK (similar to PTR_TO_MEM), and mark r0 as PTR_TO_STACK. This ends up combining the constraints of both types of pointers (it may as well be called PTR_TO_STACK_OR_MEM) without forking paths.

Yeah, PTR_TO_STACK_OR_MEM would be more precise. But how does that help with this problem? Not sure I follow the idea of the solution (but I can wait for patches to be posted).

Quoted 3 lines

The benefit over the push_stack approach is that we avoid the states regression for cls_redirect and balancer_ingress.

yeah, of course, I don't particularly like the push_stack approach.

Quoted 10 lines

For the selftest failure, I plan to just silence the error by changing it.

Quoted 8 lines
Quoted 8 lines

I don't recall if there was a hardware/JIT specific reason to care about stack access alignment or not (on some architectures), but otherwise we can over approximately mark at 8-byte granularity for any slot(s) that overlap with the buffer to cover such a case. The second problem is slightly trickier, which makes me lean towards invalidating returned PTR_TO_MEM when stack slot is overwritten or frame is destroyed.

author maintainer
#11 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 88 lines · Andrii Nakryiko
Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 67 lines · Andrii Nakryiko
Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Quoted 9 lines

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Quoted 5 lines

Invalidation is certainly one option. The one Alexei mentioned was where we discussed bounding how much data can be read through the PTR_TO_STACK (similar to PTR_TO_MEM), and mark r0 as PTR_TO_STACK. This ends up combining the constraints of both types of pointers (it may as well be called PTR_TO_STACK_OR_MEM) without forking paths.

Quoted 3 lines

Yeah, PTR_TO_STACK_OR_MEM would be more precise. But how does that help with this problem? Not sure I follow the idea of the solution (but I can wait for patches to be posted).

The reason for push_stack was to ensure writes through the returned pointer take effect on stack state.
By keeping it PTR_TO_STACK, we get that behavior.
However, in the other path of this patch, the verifier would verify the pointer as PTR_TO_MEM, with a bounded mem_size.
Thus it would not allow writing beyond a certain size.
If we simply set r0 to PTR_TO_STACK now, it would possibly allow going beyond the size that was passed to kfunc.
E.g. say buffer was fp-24 and size was 8, we can also modify fp-8 through it and not just fp-16.
Adding an additional mem_size field and checking it (when set) for PTR_TO_STACK allows us to ensure we cannot write beyond 8 bytes through r0=fp-24.

I hope this is clearer.

Quoted 3 lines
Quoted 2 lines

[...]

#12 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 94 lines · Kumar Kartikeya Dwivedi
Quoted 88 lines · Andrii Nakryiko
Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 67 lines · Andrii Nakryiko
Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Quoted 9 lines

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Quoted 5 lines

Invalidation is certainly one option. The one Alexei mentioned was where we discussed bounding how much data can be read through the PTR_TO_STACK (similar to PTR_TO_MEM), and mark r0 as PTR_TO_STACK. This ends up combining the constraints of both types of pointers (it may as well be called PTR_TO_STACK_OR_MEM) without forking paths.

Quoted 3 lines

Yeah, PTR_TO_STACK_OR_MEM would be more precise. But how does that help with this problem? Not sure I follow the idea of the solution (but I can wait for patches to be posted).

Quoted 13 lines

The reason for push_stack was to ensure writes through the returned pointer take effect on stack state.
By keeping it PTR_TO_STACK, we get that behavior.
However, in the other path of this patch, the verifier would verify the pointer as PTR_TO_MEM, with a bounded mem_size.
Thus it would not allow writing beyond a certain size.
If we simply set r0 to PTR_TO_STACK now, it would possibly allow going beyond the size that was passed to kfunc.
E.g. say buffer was fp-24 and size was 8, we can also modify fp-8 through it and not just fp-16.
Adding an additional mem_size field and checking it (when set) for PTR_TO_STACK allows us to ensure we cannot write beyond 8 bytes through r0=fp-24.

yeah, this part is clear, of course, but I was actually more worried about handling the following situation:

struct bpf_dynptr dptr;
void *slice;

union {
    char buf[32];
    void *map_value;
} blah;

bpf_dynptr_from_skb(..., &dptr);

slice = bpf_dynptr_slice_rdwr(&dptr, 0, &blah.buf, sizeof(blah.buf)); if (!slice) return 0; /* whatever */

/* now slice points to blah.{buf,map_value}, right? */

map_value = bpf_map_lookup_elem(&some_map, ...);
if (!map_value) return 0;

/* we shouldn't allow working with slice at this point */ *(u64 *)slice = 0xdeadbeef; /* overwrite map_value */

*(u64 *)map_value = 123; /* BOOM */

Would this PTR_TO_STACK_OR_MEM approach handle this? If so, can you briefly walk me through how? Thanks!

Quoted 6 lines

I hope this is clearer.

Quoted 3 lines
Quoted 2 lines

[...]

author maintainer
#13 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 111 lines · Andrii Nakryiko
Quoted 94 lines · Kumar Kartikeya Dwivedi
Quoted 88 lines · Andrii Nakryiko
Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 67 lines · Andrii Nakryiko
Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Quoted 9 lines

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Quoted 5 lines

Invalidation is certainly one option. The one Alexei mentioned was where we discussed bounding how much data can be read through the PTR_TO_STACK (similar to PTR_TO_MEM), and mark r0 as PTR_TO_STACK. This ends up combining the constraints of both types of pointers (it may as well be called PTR_TO_STACK_OR_MEM) without forking paths.

Quoted 3 lines

Yeah, PTR_TO_STACK_OR_MEM would be more precise. But how does that help with this problem? Not sure I follow the idea of the solution (but I can wait for patches to be posted).

Quoted 13 lines

The reason for push_stack was to ensure writes through the returned pointer take effect on stack state.
By keeping it PTR_TO_STACK, we get that behavior.
However, in the other path of this patch, the verifier would verify the pointer as PTR_TO_MEM, with a bounded mem_size.
Thus it would not allow writing beyond a certain size.
If we simply set r0 to PTR_TO_STACK now, it would possibly allow going beyond the size that was passed to kfunc.
E.g. say buffer was fp-24 and size was 8, we can also modify fp-8 through it and not just fp-16.
Adding an additional mem_size field and checking it (when set) for PTR_TO_STACK allows us to ensure we cannot write beyond 8 bytes through r0=fp-24.

Quoted 3 lines

yeah, this part is clear, of course, but I was actually more worried about handling the following situation:

For simplicity, let's just forget about stack_or_mem, and assume stack pointer with this extra mem_size.
I haven't written the code yet but the idea would be to limit writing to [fp-N, fp-N+mem_size) through it.
A screening check before we pass through to the normal stack access handling code.

Quoted 9 lines

struct bpf_dynptr dptr;
void *slice;

union {
    char buf[32];
    void *map_value;
} blah;

bpf_dynptr_from_skb(..., &dptr);

At this point we mark dptr.

Quoted 4 lines

slice = bpf_dynptr_slice_rdwr(&dptr, 0, &blah.buf, sizeof(blah.buf)); if (!slice) return 0; /* whatever */

slice is PTR_TO_STACK w/ mem_size = 32.

We mark the bytes for buf as STACK_MISC at this point.

Quoted 4 lines

/* now slice points to blah.{buf,map_value}, right? */

map_value = bpf_map_lookup_elem(&some_map, ...);
if (!map_value) return 0;

The 8-byte slot for map_value in these 32-bytes becomes map_value. Rest remains misc.

Quoted 3 lines

/* we shouldn't allow working with slice at this point */ *(u64 *)slice = 0xdeadbeef; /* overwrite map_value */

And because slice is PTR_TO_STACK, we will notice the overwrite of map value with scalar.

Quoted 3 lines

*(u64 *)map_value = 123; /* BOOM */

So this would fail as deref of scalar.

Let me know if I missed something you were trying to point out.

#14 lore raw

Re: [RFC PATCH bpf-next v1 1/2] bpf: Explore PTR_TO_STACK as R0 for bpf_dynptr_slice_rdwr

Quoted 161 lines · Kumar Kartikeya Dwivedi
Quoted 111 lines · Andrii Nakryiko
Quoted 94 lines · Kumar Kartikeya Dwivedi
Quoted 88 lines · Andrii Nakryiko
Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 67 lines · Andrii Nakryiko
Quoted 59 lines · Kumar Kartikeya Dwivedi
Quoted 22 lines · Alexei Starovoitov
Quoted 7 lines · Kumar Kartikeya Dwivedi

For the bpf_dynptr_slice_rdwr kfunc, the verifier may return a pointer to the underlying packet (if the requested slice is linear), or copy out the data to the buffer passed into the kfunc. The verifier performs symbolic execution assuming the returned value is a PTR_TO_MEM of a certain size (passed into the kfunc), and ensures reads and writes are within bounds.

sounds like
check_kfunc_mem_size_reg() -> check_mem_size_reg() -> check_helper_mem_access()
case PTR_TO_STACK:

      check_stack_range_initialized()
         clobber = true
             if (clobber) {
                  __mark_reg_unknown(env, &state->stack[spi].spilled_ptr);

is somehow broken?

Quoted 7 lines

ohh. It might be:
|| !is_kfunc_arg_optional(meta->btf, buff_arg)

This bit is wrong then.
When arg is not-null check_kfunc_mem_size_reg() should be called. The PTR_TO_STACK abuse is a small subset of issues
if check_kfunc_mem_size_reg() is indeed not called.

The condition looks ok to me.

The condition to do check_mem_size_reg is !null || !opt.
So when it's null, and it's opt, it will be skipped.
When it's null, and it's not opt, the check will happen.
When arg is not-null, the said function is called, opt does not matter then. So the stack slots are marked misc.

In our case we're not passing a NULL pointer in the selftest.

The problem occurs once we spill to that slot _after_ the call, and then do a write through returned mem pointer.

The final few lines from the selftest do the dirty thing, where r0 is aliasing fp-8, and r1 = 0.

+ *(u64 *)(r10 - 8) = r8; \
+ *(u64 *)(r0 + 0) = r1; \
+ r8 = *(u64 *)(r10 - 8); \
+ r0 = *(u64 *)(r8 + 0); \

The write through r0 must re-mark the stack, but the verifier doesn't know it's pointing to the stack.
push_stack was the conceptually cleaner/simpler fix, but it apparently isn't good enough.

Quoted 4 lines

Remarking the stack on write to PTR_TO_MEM, or invalidating PTR_TO_MEM when r8 is spilled to fp-8 first time after the call are two options. Both have some concerns (first, the misaligned stack access is not caught, second PTR_TO_MEM may outlive stack frame).

Quoted 9 lines

Reading the description of the problem my first instinct was to have stack slots with associated obj_ref_id for such cases and when something writes into that stack slot, invalidate everything with that obj_ref_id. So that's probably what you mean by invalidating PTR_TO_MEM, right?

Not sure I understand what "PTR_TO_STACK with mem_size" (that Alexei mentioned in another email) means, though, so hard to compare.

Quoted 5 lines

Invalidation is certainly one option. The one Alexei mentioned was where we discussed bounding how much data can be read through the PTR_TO_STACK (similar to PTR_TO_MEM), and mark r0 as PTR_TO_STACK. This ends up combining the constraints of both types of pointers (it may as well be called PTR_TO_STACK_OR_MEM) without forking paths.

Quoted 3 lines

Yeah, PTR_TO_STACK_OR_MEM would be more precise. But how does that help with this problem? Not sure I follow the idea of the solution (but I can wait for patches to be posted).

Quoted 13 lines

The reason for push_stack was to ensure writes through the returned pointer take effect on stack state.
By keeping it PTR_TO_STACK, we get that behavior.
However, in the other path of this patch, the verifier would verify the pointer as PTR_TO_MEM, with a bounded mem_size.
Thus it would not allow writing beyond a certain size.
If we simply set r0 to PTR_TO_STACK now, it would possibly allow going beyond the size that was passed to kfunc.
E.g. say buffer was fp-24 and size was 8, we can also modify fp-8 through it and not just fp-16.
Adding an additional mem_size field and checking it (when set) for PTR_TO_STACK allows us to ensure we cannot write beyond 8 bytes through r0=fp-24.

Quoted 3 lines

yeah, this part is clear, of course, but I was actually more worried about handling the following situation:

For simplicity, let's just forget about stack_or_mem, and assume stack pointer with this extra mem_size.
I haven't written the code yet but the idea would be to limit writing to [fp-N, fp-N+mem_size) through it.
A screening check before we pass through to the normal stack access handling code.

Quoted 9 lines

struct bpf_dynptr dptr;
void *slice;

union {
    char buf[32];
    void *map_value;
} blah;

bpf_dynptr_from_skb(..., &dptr);

At this point we mark dptr.

Quoted 4 lines

slice = bpf_dynptr_slice_rdwr(&dptr, 0, &blah.buf, sizeof(blah.buf)); if (!slice) return 0; /* whatever */

slice is PTR_TO_STACK w/ mem_size = 32.

We mark the bytes for buf as STACK_MISC at this point.

Quoted 4 lines

/* now slice points to blah.{buf,map_value}, right? */

map_value = bpf_map_lookup_elem(&some_map, ...);
if (!map_value) return 0;

The 8-byte slot for map_value in these 32-bytes becomes map_value. Rest remains misc.

Quoted 3 lines

/* we shouldn't allow working with slice at this point */ *(u64 *)slice = 0xdeadbeef; /* overwrite map_value */

And because slice is PTR_TO_STACK, we will notice the overwrite of map value with scalar.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

*(u64 *)map_value = 123; /* BOOM */

So this would fail as deref of scalar.

Let me know if I missed something you were trying to point out.

Thanks for elaborating, I got the idea now. But I'm still unsure why we need to invent this new mechanism instead of building upon the existing one we already have. Note that when someone is overwriting dynptr slots on the stack, we automatically invalidate all the pointers derived from that dynptr. And also note that by itself it's not even an invalid thing to use. Once code is done using dynptr, it's ok to reuse that stack for something else.

So I was thinking the same thing here. That buffer on the stack passed to bpf_dynptr_slice would be marked as DYNPTR_BUF or something like that, and whenever some instruction overwrites any part of those stack slots, we just invalidate those pointers.

This new PTR_TO_STACK aliasing for bpf_dynptr_slice() approach seems a bit more error-prone, IMO (especially that returned pointer in reality might not, and most often will not, point to the stack memory actually; so it's a bit of mental exercise to keep this discrepancy in one's head). Plus it might regress states convergence, because any write through that pointer is now tracking some state on the stack, even though we just read/write raw unknown bytes "somewhere in memory".

Anyways, probably nothing broken here, but just a new concept that feels unnecessary.

author maintainer
#15 lore raw

RFC PATCH 2/2 selftests/bpf: Add selftest for bpf_dynptr_slice_rdwr r0 handling

In reply to Kumar Kartikeya Dwivedi

Ensure that once we get the return value and write to a stack slot it may potentially alias, we don't get confused about the state of the stack. Without the fix in the previous patch, we will assume the load from r8 into r0 before will always be from a map value, but in the case where the returned value is the passed in buffer, we're writing to fp-8 and will overwrite the map value stored there.

---
 .../testing/selftests/bpf/progs/dynptr_fail.c | 45 +++++++++++++++++++
 1 file changed, 45 insertions(+)
tools/testing/selftests/bpf/progs/dynptr_fail.c +45 -0
index bd8f15229f5c..4584bf53c5f8 100644
@@ -1735,3 +1735,48 @@ int test_dynptr_reg_type(void *ctx)
 	global_call_bpf_dynptr((const struct bpf_dynptr *)current);
 	return 0;
 }
+
+SEC("?tc")
+__failure __msg("R8 invalid mem access 'scalar'") __log_level(2)
+int dynptr_slice_rdwr_overwrite(struct __sk_buff *ctx)
+{
+	asm volatile (
+		"r6 = %[array_map4] ll;			\
+		 r9 = r1;				\
+		 r1 = r6;				\
+		 r2 = r10;				\
+		 r2 += -8;				\
+		 call %[bpf_map_lookup_elem];		\
+		 if r0 == 0 goto rjmp1;			\
+		 *(u64 *)(r10 - 8) = r0;		\
+		 r8 = r0;				\
+		 r1 = r9;				\
+		 r2 = 0;				\
+		 r3 = r10;				\
+		 r3 += -24;				\
+		 call %[bpf_dynptr_from_skb];		\
+		 r1 = r10;				\
+		 r1 += -24;				\
+		 r2 = 0;				\
+		 r3 = r10;				\
+		 r3 += -8;				\
+		 r4 = 8;				\
+		 call %[bpf_dynptr_slice_rdwr];		\
+		 if r0 == 0 goto rjmp1;			\
+		 r1 = 0;				\
+		 *(u64 *)(r10 - 8) = r8;		\
+		 *(u64 *)(r0 + 0) = r1;			\
+		 r8 = *(u64 *)(r10 - 8);		\
+		 r0 = *(u64 *)(r8 + 0);			\
+	rjmp1:						\
+		 r0 = 0;				\
+		 "
+		:
+		: __imm(bpf_map_lookup_elem),
+		  __imm(bpf_dynptr_from_skb),
+		  __imm(bpf_dynptr_slice_rdwr),
+		  __imm_addr(array_map4)
+		: __clobber_all
+	);
+	return 0;
+}
Signature · 1 line
2.43.5
maintainer
#16 lore raw

Re: [RFC PATCH bpf-next v1 2/2] selftests/bpf: Add selftest for bpf_dynptr_slice_rdwr r0 handling

Quoted 17 lines · Kumar Kartikeya Dwivedi

Ensure that once we get the return value and write to a stack slot it may potentially alias, we don't get confused about the state of the stack. Without the fix in the previous patch, we will assume the load from r8 into r0 before will always be from a map value, but in the case where the returned value is the passed in buffer, we're writing to fp-8 and will overwrite the map value stored there.

---
 .../testing/selftests/bpf/progs/dynptr_fail.c | 45 +++++++++++++++++++
 1 file changed, 45 insertions(+)
tools/testing/selftests/bpf/progs/dynptr_fail.c +0 -0
index bd8f15229f5c..4584bf53c5f8 100644

tools/testing/selftests/bpf/progs/dynptr_fail.c int test_dynptr_reg_type(void *ctx) · line 1743

Quoted 9 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +6 -0
@@ -1735,3 +1735,48 @@ int test_dynptr_reg_type(void *ctx)
 	global_call_bpf_dynptr((const struct bpf_dynptr *)current);
 	return 0;
 }
+
+SEC("?tc")
+__failure __msg("R8 invalid mem access 'scalar'") __log_level(2)
+int dynptr_slice_rdwr_overwrite(struct __sk_buff *ctx)
+{
+	asm volatile (

Nit: having a few comments with equivalent C code would help
understand this test case.

Quoted 18 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +18 -0
+		"r6 = %[array_map4] ll;			\
+		 r9 = r1;				\
+		 r1 = r6;				\
+		 r2 = r10;				\
+		 r2 += -8;				\
+		 call %[bpf_map_lookup_elem];		\
+		 if r0 == 0 goto rjmp1;			\
+		 *(u64 *)(r10 - 8) = r0;		\
+		 r8 = r0;				\
+		 r1 = r9;				\
+		 r2 = 0;				\
+		 r3 = r10;				\
+		 r3 += -24;				\
+		 call %[bpf_dynptr_from_skb];		\
+		 r1 = r10;				\
+		 r1 += -24;				\
+		 r2 = 0;				\
+		 r3 = r10;				\

tools/testing/selftests/bpf/progs/dynptr_fail.c int test_dynptr_reg_type(void *ctx) · line 1771

Quoted 10 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +10 -0
+		 r3 += -8;				\
+		 r4 = 8;				\
+		 call %[bpf_dynptr_slice_rdwr];		\
+		 if r0 == 0 goto rjmp1;			\
+		 r1 = 0;				\
+		 *(u64 *)(r10 - 8) = r8;		\
+		 *(u64 *)(r0 + 0) = r1;			\
+		 r8 = *(u64 *)(r10 - 8);		\
+		 r0 = *(u64 *)(r8 + 0);			\
+	rjmp1:						\

Note: 'rjmp1' would be a global label.
An alternative would be to either use 'goto 1f' and label '1:',
or use the '%=' counter: 'goto rjmp1_%=', 'rjmp_%=:'.
These would make label names unique for this inline assembly block. See https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Special-format-strings , And https://sourceware.org/binutils/docs/as/Symbol-Names.html .

Quoted 11 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +11 -0
+		 r0 = 0;				\
+		 "
+		:
+		: __imm(bpf_map_lookup_elem),
+		  __imm(bpf_dynptr_from_skb),
+		  __imm(bpf_dynptr_slice_rdwr),
+		  __imm_addr(array_map4)
+		: __clobber_all
+	);
+	return 0;
+}
author maintainer
#17 lore raw

Re: [RFC PATCH bpf-next v1 2/2] selftests/bpf: Add selftest for bpf_dynptr_slice_rdwr r0 handling

Quoted 23 lines · Eduard Zingerman
Quoted 21 lines · Kumar Kartikeya Dwivedi

Ensure that once we get the return value and write to a stack slot it may potentially alias, we don't get confused about the state of the stack. Without the fix in the previous patch, we will assume the load from r8 into r0 before will always be from a map value, but in the case where the returned value is the passed in buffer, we're writing to fp-8 and will overwrite the map value stored there.

---
 .../testing/selftests/bpf/progs/dynptr_fail.c | 45 +++++++++++++++++++
 1 file changed, 45 insertions(+)
tools/testing/selftests/bpf/progs/dynptr_fail.c +1 -0
index bd8f15229f5c..4584bf53c5f8 100644
@@ -1735,3 +1735,48 @@ int test_dynptr_reg_type(void *ctx)
      global_call_bpf_dynptr((const struct bpf_dynptr *)current);
      return 0;
 }
+
Quoted 8 lines

tools/testing/selftests/bpf/progs/dynptr_fail.c int test_dynptr_reg_type(void *ctx) · line 1743

Quoted 5 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +5 -0
+SEC("?tc")
+__failure __msg("R8 invalid mem access 'scalar'") __log_level(2)
+int dynptr_slice_rdwr_overwrite(struct __sk_buff *ctx)
+{
+     asm volatile (

Nit: having a few comments with equivalent C code would help
understand this test case.

Ack.

Quoted 30 lines
Quoted 19 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +18 -0
+             "r6 = %[array_map4] ll;                 \
+              r9 = r1;                               \
+              r1 = r6;                               \
+              r2 = r10;                              \
+              r2 += -8;                              \
+              call %[bpf_map_lookup_elem];           \
+              if r0 == 0 goto rjmp1;                 \
+              *(u64 *)(r10 - 8) = r0;                \
+              r8 = r0;                               \
+              r1 = r9;                               \
+              r2 = 0;                                \
+              r3 = r10;                              \
+              r3 += -24;                             \
+              call %[bpf_dynptr_from_skb];           \
+              r1 = r10;                              \
+              r1 += -24;                             \
+              r2 = 0;                                \
+              r3 = r10;                              \

tools/testing/selftests/bpf/progs/dynptr_fail.c int test_dynptr_reg_type(void *ctx) · line 1771

Quoted 10 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +10 -0
+              r3 += -8;                              \
+              r4 = 8;                                \
+              call %[bpf_dynptr_slice_rdwr];         \
+              if r0 == 0 goto rjmp1;                 \
+              r1 = 0;                                \
+              *(u64 *)(r10 - 8) = r8;                \
+              *(u64 *)(r0 + 0) = r1;                 \
+              r8 = *(u64 *)(r10 - 8);                \
+              r0 = *(u64 *)(r8 + 0);                 \
+     rjmp1:                                          \
Quoted 7 lines

Note: 'rjmp1' would be a global label.
An alternative would be to either use 'goto 1f' and label '1:',
or use the '%=' counter: 'goto rjmp1_%=', 'rjmp_%=:'.
These would make label names unique for this inline assembly block. See https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Special-format-strings , And https://sourceware.org/binutils/docs/as/Symbol-Names.html .

Thanks for the tip, will fix.

Quoted 13 lines
Quoted 11 lines
tools/testing/selftests/bpf/progs/dynptr_fail.c +11 -0
+              r0 = 0;                                \
+              "
+             :
+             : __imm(bpf_map_lookup_elem),
+               __imm(bpf_dynptr_from_skb),
+               __imm(bpf_dynptr_slice_rdwr),
+               __imm_addr(array_map4)
+             : __clobber_all
+     );
+     return 0;
+}