* [PATCH bpf v2 0/2] bpf: fix accesses to uninit stack slots
@ 2023-11-26 1:50 Andrei Matei
2023-11-26 1:50 ` [PATCH bpf v2 1/2] " Andrei Matei
2023-11-26 1:50 ` [PATCH bpf v2 2/2] bpf: new verifier tests for stack access Andrei Matei
0 siblings, 2 replies; 14+ messages in thread
From: Andrei Matei @ 2023-11-26 1:50 UTC (permalink / raw
To: bpf, andrii.nakryiko; +Cc: sunhao.th, eddyz87, kernel-team, Andrei Matei
Fix two related issues issues around verifying stack accesses:
1. accesses to uninitialized stack memory was allowed inconsistently
2. the maximum stack depth needed for a program was not always
maintained correctly
The two issues are fixed together in one commit because the code for one
affects the other.
The second patch is tests only. It was split for review purposes; it can
be squashed when merging if it looks good.
Andrei Matei (2):
bpf: fix accesses to uninit stack slots
bpf: new verifier tests for stack access
include/linux/bpf_verifier.h | 4 ++
kernel/bpf/verifier.c | 70 ++++++++-----------
.../selftests/bpf/progs/test_global_func16.c | 2 +-
.../bpf/progs/verifier_basic_stack.c | 6 +-
.../selftests/bpf/progs/verifier_int_ptr.c | 2 +-
.../selftests/bpf/progs/verifier_raw_stack.c | 2 +-
.../selftests/bpf/progs/verifier_var_off.c | 4 +-
tools/testing/selftests/bpf/test_verifier.c | 24 +++++++
.../selftests/bpf/verifier/atomic_cmpxchg.c | 11 ---
tools/testing/selftests/bpf/verifier/calls.c | 2 +-
tools/testing/selftests/bpf/verifier/stack.c | 40 +++++++++++
11 files changed, 106 insertions(+), 61 deletions(-)
create mode 100644 tools/testing/selftests/bpf/verifier/stack.c
--
2.40.1
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-26 1:50 [PATCH bpf v2 0/2] bpf: fix accesses to uninit stack slots Andrei Matei
@ 2023-11-26 1:50 ` Andrei Matei
2023-11-28 1:33 ` Eduard Zingerman
2023-11-29 6:05 ` Andrii Nakryiko
2023-11-26 1:50 ` [PATCH bpf v2 2/2] bpf: new verifier tests for stack access Andrei Matei
1 sibling, 2 replies; 14+ messages in thread
From: Andrei Matei @ 2023-11-26 1:50 UTC (permalink / raw
To: bpf, andrii.nakryiko; +Cc: sunhao.th, eddyz87, kernel-team, Andrei Matei
Privileged programs are supposed to be able to read uninitialized stack
memory (ever since 6715df8d5) but, before this patch, these accesses
were permitted inconsistently. In particular, accesses were permitted
above state->allocated_stack, but not below it. In other words, if the
stack was already "large enough", the access was permitted, but
otherwise the access was rejected instead of being allowed to "grow the
stack". This undesired rejection was happening in two places:
- in check_stack_slot_within_bounds()
- in check_stack_range_initialized()
This patch arranges for these accesses to be permitted.
This patch also fixes the tracking of the stack size for variable-offset
reads. This second fix is bundled in the same commit as the first one
because they're inter-related. Before this patch, writes to the stack
using registers containing a variable offset (as opposed to registers
with fixed, known values) were not properly contributing to the
function's needed stack size. As a result, it was possible for a program
to verify, but then to attempt to read out-of-bounds data at runtime
because a too small stack had been allocated for it.
Each function tracks the size of the stack it needs in
bpf_subprog_info.stack_depth, which is maintained by
update_stack_depth(). For regular memory accesses, check_mem_access()
was calling update_state_depth() but it was passing in only the fixed
part of the offset register, ignoring the variable offset. This was
incorrect; the minimum possible value of that register should be used
instead.
This tracking is now fixed by centralizing the tracking of stack size in
grow_stack_state(), and by lifting the calls to grow_stack_state() to
check_stack_access_within_bounds() as suggested by Andrii. The code is
now simpler and more convincingly tracks the correct maximum stack size.
check_stack_range_initialized() can now rely on enough stack having been
allocated for the access; this helps with the fix for the first issue.
Reported-by: Hao Sun <sunhao.th@gmail.com>
Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
Closes: https://lore.kernel.org/bpf/CABWLsev9g8UP_c3a=1qbuZUi20tGoUXoU07FPf-5FLvhOKOY+Q@mail.gmail.com/
Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
include/linux/bpf_verifier.h | 4 ++
kernel/bpf/verifier.c | 70 ++++++++-----------
.../selftests/bpf/progs/test_global_func16.c | 2 +-
.../bpf/progs/verifier_basic_stack.c | 6 +-
.../selftests/bpf/progs/verifier_int_ptr.c | 2 +-
.../selftests/bpf/progs/verifier_raw_stack.c | 2 +-
.../selftests/bpf/progs/verifier_var_off.c | 4 +-
.../selftests/bpf/verifier/atomic_cmpxchg.c | 11 ---
tools/testing/selftests/bpf/verifier/calls.c | 2 +-
9 files changed, 42 insertions(+), 61 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index aa4d19d0bc94..5fc389e8be35 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -630,6 +630,10 @@ struct bpf_verifier_env {
int exception_callback_subprog;
bool explore_alu_limits;
bool allow_ptr_leaks;
+ /* Allow access to uninitialized stack memory. Writes with fixed offset are
+ * always allowed, so this refers to reads (with fixed or variable offset),
+ * to writes with variable offset and to indirect (helper) accesses.
+ */
bool allow_uninit_stack;
bool bpf_capable;
bool bypass_spec_v1;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index af2819d5c8ee..f9546dd73f3c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1685,10 +1685,12 @@ static int resize_reference_state(struct bpf_func_state *state, size_t n)
return 0;
}
-static int grow_stack_state(struct bpf_func_state *state, int size)
+/* Possibly update state->allocated_stack to be at least size bytes. Also
+ * possibly update the function's high-water mark in its bpf_subprog_info.
+ */
+static int grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size)
{
size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE;
-
if (old_n >= n)
return 0;
@@ -1697,6 +1699,12 @@ static int grow_stack_state(struct bpf_func_state *state, int size)
return -ENOMEM;
state->allocated_stack = size;
+
+ /* update known max for given subprogram */
+ u16 stack = env->subprog_info[state->subprogno].stack_depth;
+ if (stack < size)
+ env->subprog_info[state->subprogno].stack_depth = size;
+
return 0;
}
@@ -4669,9 +4677,6 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
struct bpf_reg_state *reg = NULL;
u32 dst_reg = insn->dst_reg;
- err = grow_stack_state(state, round_up(slot + 1, BPF_REG_SIZE));
- if (err)
- return err;
/* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
* so it's aligned access and [off, off + size) are within stack limits
*/
@@ -4827,10 +4832,6 @@ static int check_stack_write_var_off(struct bpf_verifier_env *env,
(!value_reg && is_bpf_st_mem(insn) && insn->imm == 0))
writing_zero = true;
- err = grow_stack_state(state, round_up(-min_off, BPF_REG_SIZE));
- if (err)
- return err;
-
for (i = min_off; i < max_off; i++) {
int spi;
@@ -5959,20 +5960,6 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,
strict);
}
-static int update_stack_depth(struct bpf_verifier_env *env,
- const struct bpf_func_state *func,
- int off)
-{
- u16 stack = env->subprog_info[func->subprogno].stack_depth;
-
- if (stack >= -off)
- return 0;
-
- /* update known max for given subprogram */
- env->subprog_info[func->subprogno].stack_depth = -off;
- return 0;
-}
-
/* starting from main bpf function walk all instructions of the function
* and recursively walk all callees that given function can call.
* Ignore jump and exit insns.
@@ -6761,13 +6748,15 @@ static int check_ptr_to_map_access(struct bpf_verifier_env *env,
* The minimum valid offset is -MAX_BPF_STACK for writes, and
* -state->allocated_stack for reads.
*/
-static int check_stack_slot_within_bounds(int off,
- struct bpf_func_state *state,
- enum bpf_access_type t)
+static int check_stack_slot_within_bounds(
+ struct bpf_verifier_env *env,
+ int off,
+ struct bpf_func_state *state,
+ enum bpf_access_type t)
{
int min_valid_off;
- if (t == BPF_WRITE)
+ if (t == BPF_WRITE || env->allow_uninit_stack)
min_valid_off = -MAX_BPF_STACK;
else
min_valid_off = -state->allocated_stack;
@@ -6822,9 +6811,9 @@ static int check_stack_access_within_bounds(
max_off = min_off;
}
- err = check_stack_slot_within_bounds(min_off, state, type);
+ err = check_stack_slot_within_bounds(env, min_off, state, type);
if (!err)
- err = check_stack_slot_within_bounds(max_off, state, type);
+ err = check_stack_slot_within_bounds(env, max_off, state, type);
if (err) {
if (tnum_is_const(reg->var_off)) {
@@ -6837,8 +6826,10 @@ static int check_stack_access_within_bounds(
verbose(env, "invalid variable-offset%s stack R%d var_off=%s size=%d\n",
err_extra, regno, tn_buf, access_size);
}
+ return err;
}
- return err;
+
+ return grow_stack_state(env, state, round_up(-min_off, BPF_REG_SIZE));
}
/* check whether memory at (regno + off) is accessible for t = (read | write)
@@ -6853,7 +6844,6 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
{
struct bpf_reg_state *regs = cur_regs(env);
struct bpf_reg_state *reg = regs + regno;
- struct bpf_func_state *state;
int size, err = 0;
size = bpf_size_to_bytes(bpf_size);
@@ -6996,11 +6986,6 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
if (err)
return err;
- state = func(env, reg);
- err = update_stack_depth(env, state, off);
- if (err)
- return err;
-
if (t == BPF_READ)
err = check_stack_read(env, regno, off, size,
value_regno);
@@ -7195,7 +7180,8 @@ static int check_atomic(struct bpf_verifier_env *env, int insn_idx, struct bpf_i
/* When register 'regno' is used to read the stack (either directly or through
* a helper function) make sure that it's within stack boundary and, depending
- * on the access type, that all elements of the stack are initialized.
+ * on the access type and privileges, that all elements of the stack are
+ * initialized.
*
* 'off' includes 'regno->off', but not its dynamic part (if any).
*
@@ -7303,8 +7289,11 @@ static int check_stack_range_initialized(
slot = -i - 1;
spi = slot / BPF_REG_SIZE;
- if (state->allocated_stack <= slot)
- goto err;
+ if (state->allocated_stack <= slot) {
+ verbose(env, "verifier bug: allocated_stack too small");
+ return -EFAULT;
+ }
+
stype = &state->stack[spi].slot_type[slot % BPF_REG_SIZE];
if (*stype == STACK_MISC)
goto mark;
@@ -7328,7 +7317,6 @@ static int check_stack_range_initialized(
goto mark;
}
-err:
if (tnum_is_const(reg->var_off)) {
verbose(env, "invalid%s read from stack R%d off %d+%d size %d\n",
err_extra, regno, min_off, i - min_off, access_size);
@@ -7353,7 +7341,7 @@ static int check_stack_range_initialized(
* helper may write to the entire memory range.
*/
}
- return update_stack_depth(env, state, min_off);
+ return 0;
}
static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
diff --git a/tools/testing/selftests/bpf/progs/test_global_func16.c b/tools/testing/selftests/bpf/progs/test_global_func16.c
index e7206304632e..e3e64bc472cd 100644
--- a/tools/testing/selftests/bpf/progs/test_global_func16.c
+++ b/tools/testing/selftests/bpf/progs/test_global_func16.c
@@ -13,7 +13,7 @@ __noinline int foo(int (*arr)[10])
}
SEC("cgroup_skb/ingress")
-__failure __msg("invalid indirect read from stack")
+__success
int global_func16(struct __sk_buff *skb)
{
int array[10];
diff --git a/tools/testing/selftests/bpf/progs/verifier_basic_stack.c b/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
index 359df865a8f3..069c3f91705c 100644
--- a/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
@@ -27,8 +27,8 @@ __naked void stack_out_of_bounds(void)
SEC("socket")
__description("uninitialized stack1")
-__failure __msg("invalid indirect read from stack")
-__failure_unpriv
+__success
+__failure_unpriv __msg_unpriv("invalid indirect read from stack")
__naked void uninitialized_stack1(void)
{
asm volatile (" \
@@ -45,7 +45,7 @@ __naked void uninitialized_stack1(void)
SEC("socket")
__description("uninitialized stack2")
-__failure __msg("invalid read from stack")
+__success
__failure_unpriv
__naked void uninitialized_stack2(void)
{
diff --git a/tools/testing/selftests/bpf/progs/verifier_int_ptr.c b/tools/testing/selftests/bpf/progs/verifier_int_ptr.c
index b054f9c48143..b5cedc0d23c1 100644
--- a/tools/testing/selftests/bpf/progs/verifier_int_ptr.c
+++ b/tools/testing/selftests/bpf/progs/verifier_int_ptr.c
@@ -7,7 +7,7 @@
SEC("cgroup/sysctl")
__description("ARG_PTR_TO_LONG uninitialized")
-__failure __msg("invalid indirect read from stack R4 off -16+0 size 8")
+__success
__naked void arg_ptr_to_long_uninitialized(void)
{
asm volatile (" \
diff --git a/tools/testing/selftests/bpf/progs/verifier_raw_stack.c b/tools/testing/selftests/bpf/progs/verifier_raw_stack.c
index efbfc3a4ad6a..5468c5302495 100644
--- a/tools/testing/selftests/bpf/progs/verifier_raw_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_raw_stack.c
@@ -7,7 +7,7 @@
SEC("tc")
__description("raw_stack: no skb_load_bytes")
-__failure __msg("invalid read from stack R6 off=-8 size=8")
+__success
__naked void stack_no_skb_load_bytes(void)
{
asm volatile (" \
diff --git a/tools/testing/selftests/bpf/progs/verifier_var_off.c b/tools/testing/selftests/bpf/progs/verifier_var_off.c
index 83a90afba785..bbf3628c625a 100644
--- a/tools/testing/selftests/bpf/progs/verifier_var_off.c
+++ b/tools/testing/selftests/bpf/progs/verifier_var_off.c
@@ -61,7 +61,7 @@ __naked void stack_read_priv_vs_unpriv(void)
SEC("lwt_in")
__description("variable-offset stack read, uninitialized")
-__failure __msg("invalid variable-offset read from stack R2")
+__success
__naked void variable_offset_stack_read_uninitialized(void)
{
asm volatile (" \
@@ -255,7 +255,7 @@ __naked void access_min_out_of_bound(void)
SEC("lwt_in")
__description("indirect variable-offset stack access, min_off < min_initialized")
-__failure __msg("invalid indirect read from stack R2 var_off")
+__success
__naked void access_min_off_min_initialized(void)
{
asm volatile (" \
diff --git a/tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c b/tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c
index 319337bdcfc8..9a7b1106fda8 100644
--- a/tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c
+++ b/tools/testing/selftests/bpf/verifier/atomic_cmpxchg.c
@@ -83,17 +83,6 @@
.result = REJECT,
.errstr = "!read_ok",
},
-{
- "Can't use cmpxchg on uninit memory",
- .insns = {
- BPF_MOV64_IMM(BPF_REG_0, 3),
- BPF_MOV64_IMM(BPF_REG_2, 4),
- BPF_ATOMIC_OP(BPF_DW, BPF_CMPXCHG, BPF_REG_10, BPF_REG_2, -8),
- BPF_EXIT_INSN(),
- },
- .result = REJECT,
- .errstr = "invalid read from stack",
-},
{
"BPF_W cmpxchg should zero top 32 bits",
.insns = {
diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index 3d5cd51071f0..89b79997c1b4 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -1505,7 +1505,7 @@
.prog_type = BPF_PROG_TYPE_XDP,
.fixup_map_hash_8b = { 23 },
.result = REJECT,
- .errstr = "invalid read from stack R7 off=-16 size=8",
+ .errstr = "R0 invalid mem access 'scalar'",
},
{
"calls: two calls that receive map_value via arg=ptr_stack_of_caller. test1",
--
2.40.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH bpf v2 2/2] bpf: new verifier tests for stack access
2023-11-26 1:50 [PATCH bpf v2 0/2] bpf: fix accesses to uninit stack slots Andrei Matei
2023-11-26 1:50 ` [PATCH bpf v2 1/2] " Andrei Matei
@ 2023-11-26 1:50 ` Andrei Matei
2023-11-28 1:23 ` Eduard Zingerman
1 sibling, 1 reply; 14+ messages in thread
From: Andrei Matei @ 2023-11-26 1:50 UTC (permalink / raw
To: bpf, andrii.nakryiko; +Cc: sunhao.th, eddyz87, kernel-team, Andrei Matei
This patch adds tests for the previous patch, checking the tracking of
the maximum stack size and checking that accesses to uninit stack memory
are allowed.
They are a separate patch for review purposes; whoever merges them can
consider squashing.
Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
tools/testing/selftests/bpf/test_verifier.c | 24 ++++++++++++
tools/testing/selftests/bpf/verifier/stack.c | 40 ++++++++++++++++++++
2 files changed, 64 insertions(+)
create mode 100644 tools/testing/selftests/bpf/verifier/stack.c
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 98107e0452d3..a62610585ee4 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -135,6 +135,10 @@ struct bpf_test {
const char *errstr;
const char *errstr_unpriv;
uint32_t insn_processed;
+ /* Expected maximum stack depth for the main subprogram. Not checked if 0.
+ * Only checked if the program is accepted.
+ */
+ uint16_t max_stack_depth;
int prog_len;
enum {
UNDEF,
@@ -1703,6 +1707,26 @@ static void do_test_single(struct bpf_test *test, bool unpriv,
}
}
+ /* Check the stack size if the test configured an expecation and the program
+ * was loaded successfully.
+ */
+ if (test->max_stack_depth && fd_prog >= 0) {
+ uint32_t max_stack;
+ char *s;
+
+ s = strstr(bpf_vlog, "stack depth ");
+ if (s == NULL) {
+ printf("FAIL\nstack depth result not found in verifier output\n");
+ goto fail_log;
+ }
+ max_stack = atoi(s + 12);
+ if (test->max_stack_depth != max_stack) {
+ printf("FAIL\nUnexpected max stack %u vs %u\n",
+ max_stack, test->max_stack_depth);
+ goto fail_log;
+ }
+ }
+
if (verbose)
printf(", verifier log:\n%s", bpf_vlog);
diff --git a/tools/testing/selftests/bpf/verifier/stack.c b/tools/testing/selftests/bpf/verifier/stack.c
new file mode 100644
index 000000000000..ac571783c05e
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/stack.c
@@ -0,0 +1,40 @@
+{
+ /* Check that reading unitialized stack memory is allowed only in privileged
+ * mode. Also check that such reads maintain the max stack depth.
+ */
+ "read uninit stack",
+ .insns = {
+ BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_10, -504),
+ /* exit(0); */
+ BPF_MOV32_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
+ .result = ACCEPT,
+ .result_unpriv = REJECT,
+ .errstr_unpriv = "invalid read from stack",
+ .max_stack_depth = 504,
+},
+{
+ /* Check that indirect accesses to stack maintain the max stack depth. */
+ "read (indirect) uninit stack",
+ .insns = {
+ /* We'll use probe_read_user as an arbitrary helper that can access the
+ * stack. We're going to read into *(fp-104).
+ */
+ BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -104),
+ BPF_MOV32_IMM(BPF_REG_2, 8),
+ /* read from a random address */
+ BPF_MOV32_IMM(BPF_REG_3, 0x4242),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_probe_read_user),
+ BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+ BPF_EXIT_INSN(),
+ /* exit(0); */
+ BPF_MOV32_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
+ .result = ACCEPT,
+ .result_unpriv = REJECT,
+ .errstr_unpriv = "",
+ .max_stack_depth = 104,
+},
\ No newline at end of file
--
2.40.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 2/2] bpf: new verifier tests for stack access
2023-11-26 1:50 ` [PATCH bpf v2 2/2] bpf: new verifier tests for stack access Andrei Matei
@ 2023-11-28 1:23 ` Eduard Zingerman
2023-11-28 3:15 ` Andrei Matei
0 siblings, 1 reply; 14+ messages in thread
From: Eduard Zingerman @ 2023-11-28 1:23 UTC (permalink / raw
To: Andrei Matei, bpf, andrii.nakryiko; +Cc: sunhao.th, kernel-team
On Sat, 2023-11-25 at 20:50 -0500, Andrei Matei wrote:
> This patch adds tests for the previous patch, checking the tracking of
> the maximum stack size and checking that accesses to uninit stack memory
> are allowed.
>
> They are a separate patch for review purposes; whoever merges them can
> consider squashing.
>
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---
I think the strategy now is to add new tests using inline assembly,
e.g. as a part of verifier_* tests in test_progs.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-26 1:50 ` [PATCH bpf v2 1/2] " Andrei Matei
@ 2023-11-28 1:33 ` Eduard Zingerman
2023-11-28 1:43 ` Eduard Zingerman
2023-11-28 14:14 ` Eduard Zingerman
2023-11-29 6:05 ` Andrii Nakryiko
1 sibling, 2 replies; 14+ messages in thread
From: Eduard Zingerman @ 2023-11-28 1:33 UTC (permalink / raw
To: Andrei Matei, bpf, andrii.nakryiko; +Cc: sunhao.th, kernel-team
On Sat, 2023-11-25 at 20:50 -0500, Andrei Matei wrote:
> Privileged programs are supposed to be able to read uninitialized stack
> memory (ever since 6715df8d5) but, before this patch, these accesses
> were permitted inconsistently. In particular, accesses were permitted
> above state->allocated_stack, but not below it. In other words, if the
> stack was already "large enough", the access was permitted, but
> otherwise the access was rejected instead of being allowed to "grow the
> stack". This undesired rejection was happening in two places:
> - in check_stack_slot_within_bounds()
> - in check_stack_range_initialized()
> This patch arranges for these accesses to be permitted.
>
> This patch also fixes the tracking of the stack size for variable-offset
> reads. This second fix is bundled in the same commit as the first one
> because they're inter-related. Before this patch, writes to the stack
> using registers containing a variable offset (as opposed to registers
> with fixed, known values) were not properly contributing to the
> function's needed stack size. As a result, it was possible for a program
> to verify, but then to attempt to read out-of-bounds data at runtime
> because a too small stack had been allocated for it.
>
> Each function tracks the size of the stack it needs in
> bpf_subprog_info.stack_depth, which is maintained by
> update_stack_depth(). For regular memory accesses, check_mem_access()
> was calling update_state_depth() but it was passing in only the fixed
> part of the offset register, ignoring the variable offset. This was
> incorrect; the minimum possible value of that register should be used
> instead.
>
> This tracking is now fixed by centralizing the tracking of stack size in
> grow_stack_state(), and by lifting the calls to grow_stack_state() to
> check_stack_access_within_bounds() as suggested by Andrii. The code is
> now simpler and more convincingly tracks the correct maximum stack size.
> check_stack_range_initialized() can now rely on enough stack having been
> allocated for the access; this helps with the fix for the first issue.
>
> Reported-by: Hao Sun <sunhao.th@gmail.com>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CABWLsev9g8UP_c3a=1qbuZUi20tGoUXoU07FPf-5FLvhOKOY+Q@mail.gmail.com/
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---
I think these changes make sense.
Question: would it be possible to recover some of the tests (those
converted from failure to success) by changing execution mode from
priv to unpriv?
Also, I think there are some tests that do oob stack read in branches
that should be proven unreachable, with expectation that if certain
verifier logic does not work as expected stack access would serve as a
canary. Have no idea how to identify these tests, though.
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
[...]
> @@ -1697,6 +1699,12 @@ static int grow_stack_state(struct bpf_func_state *state, int size)
> return -ENOMEM;
>
> state->allocated_stack = size;
> +
> + /* update known max for given subprogram */
> + u16 stack = env->subprog_info[state->subprogno].stack_depth;
Nit: 'u16 stack;' should be at the top of the function.
> + if (stack < size)
> + env->subprog_info[state->subprogno].stack_depth = size;
> +
> return 0;
> }
[...]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-28 1:33 ` Eduard Zingerman
@ 2023-11-28 1:43 ` Eduard Zingerman
2023-11-28 14:14 ` Eduard Zingerman
1 sibling, 0 replies; 14+ messages in thread
From: Eduard Zingerman @ 2023-11-28 1:43 UTC (permalink / raw
To: Andrei Matei, bpf, andrii.nakryiko; +Cc: sunhao.th, kernel-team
On Tue, 2023-11-28 at 03:33 +0200, Eduard Zingerman wrote:
> I think these changes make sense.
(Under assumption that access to uninitialized stack should be allowed,
although I implemented the patch-set that made such behavior legal
I still don't really like this idea).
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 2/2] bpf: new verifier tests for stack access
2023-11-28 1:23 ` Eduard Zingerman
@ 2023-11-28 3:15 ` Andrei Matei
2023-11-28 12:55 ` Eduard Zingerman
0 siblings, 1 reply; 14+ messages in thread
From: Andrei Matei @ 2023-11-28 3:15 UTC (permalink / raw
To: Eduard Zingerman; +Cc: bpf, andrii.nakryiko, sunhao.th, kernel-team
On Mon, Nov 27, 2023 at 8:23 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sat, 2023-11-25 at 20:50 -0500, Andrei Matei wrote:
> > This patch adds tests for the previous patch, checking the tracking of
> > the maximum stack size and checking that accesses to uninit stack memory
> > are allowed.
> >
> > They are a separate patch for review purposes; whoever merges them can
> > consider squashing.
> >
> > Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> > ---
>
> I think the strategy now is to add new tests using inline assembly,
> e.g. as a part of verifier_* tests in test_progs.
Thanks, I'll try that. I see in some of the verifier tests that you
have converted to test_progs hints that they were converted
"automatically". I'm curious what tool you've used, if any.
Do you have any thoughts on how a test could assert the maximum stack
depth? test_verifier has access to the verifier verifier log and
parses it out of there; do you know how I could achieve the same in
test_progs?
For the curiosity of someone who doesn't know much about this code
base - how come we moved from test_verifier, which seems a bit more
unit-test-y, do the higher level test_progs? Is it because of the
nicer assembly syntax?
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 2/2] bpf: new verifier tests for stack access
2023-11-28 3:15 ` Andrei Matei
@ 2023-11-28 12:55 ` Eduard Zingerman
2023-11-29 6:12 ` Andrii Nakryiko
0 siblings, 1 reply; 14+ messages in thread
From: Eduard Zingerman @ 2023-11-28 12:55 UTC (permalink / raw
To: Andrei Matei; +Cc: bpf, andrii.nakryiko, sunhao.th, kernel-team
On Mon, 2023-11-27 at 22:15 -0500, Andrei Matei wrote:
> On Mon, Nov 27, 2023 at 8:23 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Sat, 2023-11-25 at 20:50 -0500, Andrei Matei wrote:
> > > This patch adds tests for the previous patch, checking the tracking of
> > > the maximum stack size and checking that accesses to uninit stack memory
> > > are allowed.
> > >
> > > They are a separate patch for review purposes; whoever merges them can
> > > consider squashing.
> > >
> > > Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> > > ---
> >
> > I think the strategy now is to add new tests using inline assembly,
> > e.g. as a part of verifier_* tests in test_progs.
>
> Thanks, I'll try that. I see in some of the verifier tests that you
> have converted to test_progs hints that they were converted
> "automatically". I'm curious what tool you've used, if any.
I wrote a small tree-sitter based tool for this:
https://github.com/eddyz87/verifier-tests-migrator
> Do you have any thoughts on how a test could assert the maximum stack
> depth? test_verifier has access to the verifier verifier log and
> parses it out of there; do you know how I could achieve the same in
> test_progs?
Could be done like in the patch below (set log level so that stack
depth is printed, match stack depth message):
diff --git a/tools/testing/selftests/bpf/progs/verifier_basic_stack.c b/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
index 069c3f91705c..e85ac95c8dd3 100644
--- a/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
@@ -27,7 +27,7 @@ __naked void stack_out_of_bounds(void)
SEC("socket")
__description("uninitialized stack1")
-__success
+__success __log_level(4) __msg("stack depth 8")
__failure_unpriv __msg_unpriv("invalid indirect read from stack")
__naked void uninitialized_stack1(void)
{
> For the curiosity of someone who doesn't know much about this code
> base - how come we moved from test_verifier, which seems a bit more
> unit-test-y, do the higher level test_progs? Is it because of the
> nicer assembly syntax?
Yes, ability to use assembly syntax is the main (sole?) driver.
In fact, tests that use annotations from bpf_misc.h and are registered
in tools/testing/selftests/bpf/prog_tests/verifier.c provide almost
the same functionality as test_verifier:
- interface:
- select test to run using filter, e.g.:
./test_progs -a 'verifier_basic_stack/uninitialized stack1'
./test_progs -a 'verifier_basic_stack/uninitialized stack1 @unpriv'
- see verifier log for the test, e.g.:
./test_progs -vvv -a 'verifier_basic_stack/uninitialized stack1'
- test expectations:
- use __success / __failure to mark expected test outcome;
- use __msg to search for expected messages in the log;
- use __log_level to specify log level when program is loaded;
- use __flags to enable additional knobs, e.g. BPF_F_TEST_STATE_FREQ;
- use __retval if test program has to be executed;
- use _unpriv suffix to specify any of the above for when test is
executed in unprivileged mode.
See comments in tools/testing/selftests/bpf/progs/bpf_misc.h for details.
- plus clang generates BTF and CO-RE relocations for us,
with test_verifier one has to write these things "by hand"
(which is only truly needed in tests for CO-RE/BTF).
The only drawback is compilation time, because all test_progs/*.c
files depend on all *.bpf.o files. Locally I mitigate this by using
ccache: make CC='ccache clang' LLVM=1 -j14 test_progs .
I probably need to look at what could be done in the makefile one day.
Unfortunately neither test_verifier nor test_progs are true unit tests.
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-28 1:33 ` Eduard Zingerman
2023-11-28 1:43 ` Eduard Zingerman
@ 2023-11-28 14:14 ` Eduard Zingerman
1 sibling, 0 replies; 14+ messages in thread
From: Eduard Zingerman @ 2023-11-28 14:14 UTC (permalink / raw
To: Andrei Matei, bpf, andrii.nakryiko; +Cc: sunhao.th, kernel-team
On Tue, 2023-11-28 at 03:33 +0200, Eduard Zingerman wrote:
[...]
> Also, I think there are some tests that do oob stack read in branches
> that should be proven unreachable, with expectation that if certain
> verifier logic does not work as expected stack access would serve as a
> canary. Have no idea how to identify these tests, though.
I looked through all test cases I ever added (not so many) and it
seems that only one test case should be updated:
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index b2181f850d3e..3aca3dc145b5 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -846,7 +846,7 @@ __naked int delayed_precision_mark(void)
"call %[bpf_iter_num_next];"
"if r0 == 0 goto 2f;"
"if r6 != 42 goto 3f;"
- "r7 = -32;"
+ "r7 = -33;"
"call %[bpf_get_prandom_u32];"
"r6 = r0;"
"goto 1b;\n"
Here oob access is replaced by unaligned, this does not affect error
message, but should be future proof in case if widening logic would
get smarter.
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-26 1:50 ` [PATCH bpf v2 1/2] " Andrei Matei
2023-11-28 1:33 ` Eduard Zingerman
@ 2023-11-29 6:05 ` Andrii Nakryiko
2023-11-29 16:48 ` Andrei Matei
1 sibling, 1 reply; 14+ messages in thread
From: Andrii Nakryiko @ 2023-11-29 6:05 UTC (permalink / raw
To: Andrei Matei; +Cc: bpf, sunhao.th, eddyz87, kernel-team
On Sat, Nov 25, 2023 at 5:53 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> Privileged programs are supposed to be able to read uninitialized stack
> memory (ever since 6715df8d5) but, before this patch, these accesses
> were permitted inconsistently. In particular, accesses were permitted
> above state->allocated_stack, but not below it. In other words, if the
> stack was already "large enough", the access was permitted, but
> otherwise the access was rejected instead of being allowed to "grow the
> stack". This undesired rejection was happening in two places:
> - in check_stack_slot_within_bounds()
> - in check_stack_range_initialized()
> This patch arranges for these accesses to be permitted.
>
> This patch also fixes the tracking of the stack size for variable-offset
> reads. This second fix is bundled in the same commit as the first one
> because they're inter-related. Before this patch, writes to the stack
> using registers containing a variable offset (as opposed to registers
> with fixed, known values) were not properly contributing to the
> function's needed stack size. As a result, it was possible for a program
> to verify, but then to attempt to read out-of-bounds data at runtime
> because a too small stack had been allocated for it.
>
> Each function tracks the size of the stack it needs in
> bpf_subprog_info.stack_depth, which is maintained by
> update_stack_depth(). For regular memory accesses, check_mem_access()
> was calling update_state_depth() but it was passing in only the fixed
> part of the offset register, ignoring the variable offset. This was
> incorrect; the minimum possible value of that register should be used
> instead.
>
> This tracking is now fixed by centralizing the tracking of stack size in
> grow_stack_state(), and by lifting the calls to grow_stack_state() to
> check_stack_access_within_bounds() as suggested by Andrii. The code is
> now simpler and more convincingly tracks the correct maximum stack size.
> check_stack_range_initialized() can now rely on enough stack having been
> allocated for the access; this helps with the fix for the first issue.
>
> Reported-by: Hao Sun <sunhao.th@gmail.com>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CABWLsev9g8UP_c3a=1qbuZUi20tGoUXoU07FPf-5FLvhOKOY+Q@mail.gmail.com/
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---
> include/linux/bpf_verifier.h | 4 ++
> kernel/bpf/verifier.c | 70 ++++++++-----------
> .../selftests/bpf/progs/test_global_func16.c | 2 +-
> .../bpf/progs/verifier_basic_stack.c | 6 +-
> .../selftests/bpf/progs/verifier_int_ptr.c | 2 +-
> .../selftests/bpf/progs/verifier_raw_stack.c | 2 +-
> .../selftests/bpf/progs/verifier_var_off.c | 4 +-
> .../selftests/bpf/verifier/atomic_cmpxchg.c | 11 ---
> tools/testing/selftests/bpf/verifier/calls.c | 2 +-
> 9 files changed, 42 insertions(+), 61 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index aa4d19d0bc94..5fc389e8be35 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -630,6 +630,10 @@ struct bpf_verifier_env {
> int exception_callback_subprog;
> bool explore_alu_limits;
> bool allow_ptr_leaks;
> + /* Allow access to uninitialized stack memory. Writes with fixed offset are
> + * always allowed, so this refers to reads (with fixed or variable offset),
> + * to writes with variable offset and to indirect (helper) accesses.
> + */
> bool allow_uninit_stack;
> bool bpf_capable;
> bool bypass_spec_v1;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index af2819d5c8ee..f9546dd73f3c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1685,10 +1685,12 @@ static int resize_reference_state(struct bpf_func_state *state, size_t n)
> return 0;
> }
>
> -static int grow_stack_state(struct bpf_func_state *state, int size)
> +/* Possibly update state->allocated_stack to be at least size bytes. Also
> + * possibly update the function's high-water mark in its bpf_subprog_info.
> + */
> +static int grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size)
> {
> size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE;
shouldn't this be rounding up? (size + BPF_REG_SIZE - 1) / BPF_REG_SIZE?
> -
According to kernel code style, there should be an empty line between
variable declaration and other statements. Please keep this empty
line.
> if (old_n >= n)
> return 0;
>
[...]
> @@ -6761,13 +6748,15 @@ static int check_ptr_to_map_access(struct bpf_verifier_env *env,
> * The minimum valid offset is -MAX_BPF_STACK for writes, and
> * -state->allocated_stack for reads.
> */
> -static int check_stack_slot_within_bounds(int off,
> - struct bpf_func_state *state,
> - enum bpf_access_type t)
> +static int check_stack_slot_within_bounds(
> + struct bpf_verifier_env *env,
> + int off,
> + struct bpf_func_state *state,
> + enum bpf_access_type t)
nit: please keep code style, first argument is normally on the same
line as opening parenthesis
> {
> int min_valid_off;
>
> - if (t == BPF_WRITE)
> + if (t == BPF_WRITE || env->allow_uninit_stack)
> min_valid_off = -MAX_BPF_STACK;
> else
> min_valid_off = -state->allocated_stack;
[...]
> diff --git a/tools/testing/selftests/bpf/progs/verifier_var_off.c b/tools/testing/selftests/bpf/progs/verifier_var_off.c
> index 83a90afba785..bbf3628c625a 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_var_off.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_var_off.c
> @@ -61,7 +61,7 @@ __naked void stack_read_priv_vs_unpriv(void)
>
> SEC("lwt_in")
> __description("variable-offset stack read, uninitialized")
> -__failure __msg("invalid variable-offset read from stack R2")
> +__success
> __naked void variable_offset_stack_read_uninitialized(void)
> {
> asm volatile (" \
> @@ -255,7 +255,7 @@ __naked void access_min_out_of_bound(void)
>
> SEC("lwt_in")
> __description("indirect variable-offset stack access, min_off < min_initialized")
> -__failure __msg("invalid indirect read from stack R2 var_off")
> +__success
as Eduard mentioned, can you please try updating program type to
something that is allowed in unprivileged mode, e.g., SEC("socket")
and make sure that it still fails in unpriv mode
> __naked void access_min_off_min_initialized(void)
> {
> asm volatile (" \
[...]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 2/2] bpf: new verifier tests for stack access
2023-11-28 12:55 ` Eduard Zingerman
@ 2023-11-29 6:12 ` Andrii Nakryiko
0 siblings, 0 replies; 14+ messages in thread
From: Andrii Nakryiko @ 2023-11-29 6:12 UTC (permalink / raw
To: Eduard Zingerman; +Cc: Andrei Matei, bpf, sunhao.th, kernel-team
On Tue, Nov 28, 2023 at 4:55 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2023-11-27 at 22:15 -0500, Andrei Matei wrote:
> > On Mon, Nov 27, 2023 at 8:23 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Sat, 2023-11-25 at 20:50 -0500, Andrei Matei wrote:
> > > > This patch adds tests for the previous patch, checking the tracking of
> > > > the maximum stack size and checking that accesses to uninit stack memory
> > > > are allowed.
> > > >
> > > > They are a separate patch for review purposes; whoever merges them can
> > > > consider squashing.
> > > >
> > > > Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> > > > ---
> > >
> > > I think the strategy now is to add new tests using inline assembly,
> > > e.g. as a part of verifier_* tests in test_progs.
> >
> > Thanks, I'll try that. I see in some of the verifier tests that you
> > have converted to test_progs hints that they were converted
> > "automatically". I'm curious what tool you've used, if any.
>
> I wrote a small tree-sitter based tool for this:
> https://github.com/eddyz87/verifier-tests-migrator
>
> > Do you have any thoughts on how a test could assert the maximum stack
> > depth? test_verifier has access to the verifier verifier log and
> > parses it out of there; do you know how I could achieve the same in
> > test_progs?
>
> Could be done like in the patch below (set log level so that stack
> depth is printed, match stack depth message):
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_basic_stack.c b/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
> index 069c3f91705c..e85ac95c8dd3 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_basic_stack.c
> @@ -27,7 +27,7 @@ __naked void stack_out_of_bounds(void)
>
> SEC("socket")
> __description("uninitialized stack1")
> -__success
> +__success __log_level(4) __msg("stack depth 8")
> __failure_unpriv __msg_unpriv("invalid indirect read from stack")
> __naked void uninitialized_stack1(void)
> {
>
> > For the curiosity of someone who doesn't know much about this code
> > base - how come we moved from test_verifier, which seems a bit more
> > unit-test-y, do the higher level test_progs? Is it because of the
> > nicer assembly syntax?
>
> Yes, ability to use assembly syntax is the main (sole?) driver.
Not just that, test_progs by itself is a much nicer test runner for
debugging tests. It's easier to get log_level 2 logs, for example.
It's much easier to select a subset of tests to run. Plus by having
these BPF programs compiled as stand-alone .bpf.o objects, we can use
veristat to test them, bypassing test_progs altogether.
> In fact, tests that use annotations from bpf_misc.h and are registered
> in tools/testing/selftests/bpf/prog_tests/verifier.c provide almost
> the same functionality as test_verifier:
> - interface:
> - select test to run using filter, e.g.:
> ./test_progs -a 'verifier_basic_stack/uninitialized stack1'
> ./test_progs -a 'verifier_basic_stack/uninitialized stack1 @unpriv'
> - see verifier log for the test, e.g.:
> ./test_progs -vvv -a 'verifier_basic_stack/uninitialized stack1'
> - test expectations:
> - use __success / __failure to mark expected test outcome;
> - use __msg to search for expected messages in the log;
> - use __log_level to specify log level when program is loaded;
> - use __flags to enable additional knobs, e.g. BPF_F_TEST_STATE_FREQ;
> - use __retval if test program has to be executed;
> - use _unpriv suffix to specify any of the above for when test is
> executed in unprivileged mode.
> See comments in tools/testing/selftests/bpf/progs/bpf_misc.h for details.
> - plus clang generates BTF and CO-RE relocations for us,
> with test_verifier one has to write these things "by hand"
> (which is only truly needed in tests for CO-RE/BTF).
>
> The only drawback is compilation time, because all test_progs/*.c
> files depend on all *.bpf.o files. Locally I mitigate this by using
> ccache: make CC='ccache clang' LLVM=1 -j14 test_progs .
> I probably need to look at what could be done in the makefile one day.
I think if we make a push to use BPF skeletons in all tests, we should
be able to get proper dependencies between prog_tests/xxx.c and its
corresponding progs/yyy.bpf.o file(s). And at which point we should be
able to teach Makefile to only recompile relevant test files.
>
> Unfortunately neither test_verifier nor test_progs are true unit tests.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-29 6:05 ` Andrii Nakryiko
@ 2023-11-29 16:48 ` Andrei Matei
2023-11-29 23:54 ` Andrii Nakryiko
0 siblings, 1 reply; 14+ messages in thread
From: Andrei Matei @ 2023-11-29 16:48 UTC (permalink / raw
To: Andrii Nakryiko; +Cc: bpf, sunhao.th, eddyz87, kernel-team
[...]
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index af2819d5c8ee..f9546dd73f3c 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -1685,10 +1685,12 @@ static int resize_reference_state(struct bpf_func_state *state, size_t n)
> > return 0;
> > }
> >
> > -static int grow_stack_state(struct bpf_func_state *state, int size)
> > +/* Possibly update state->allocated_stack to be at least size bytes. Also
> > + * possibly update the function's high-water mark in its bpf_subprog_info.
> > + */
> > +static int grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size)
> > {
> > size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE;
>
> shouldn't this be rounding up? (size + BPF_REG_SIZE - 1) / BPF_REG_SIZE?
You're saying this was always broken, regardless of the current patch, right? I
think you're right, but that seems like a bug that should have been
caught somehow; I'm surprised no programs crashed the verifier. Perhaps in
practice all stack accesses are 8-byte aligned, so the rounding doesn't matter?
I'll spend a bit of time reading code and come back.
[...]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-29 16:48 ` Andrei Matei
@ 2023-11-29 23:54 ` Andrii Nakryiko
2023-12-02 22:41 ` Andrei Matei
0 siblings, 1 reply; 14+ messages in thread
From: Andrii Nakryiko @ 2023-11-29 23:54 UTC (permalink / raw
To: Andrei Matei; +Cc: bpf, sunhao.th, eddyz87, kernel-team
On Wed, Nov 29, 2023 at 8:48 AM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> [...]
>
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index af2819d5c8ee..f9546dd73f3c 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -1685,10 +1685,12 @@ static int resize_reference_state(struct bpf_func_state *state, size_t n)
> > > return 0;
> > > }
> > >
> > > -static int grow_stack_state(struct bpf_func_state *state, int size)
> > > +/* Possibly update state->allocated_stack to be at least size bytes. Also
> > > + * possibly update the function's high-water mark in its bpf_subprog_info.
> > > + */
> > > +static int grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size)
> > > {
> > > size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE;
> >
> > shouldn't this be rounding up? (size + BPF_REG_SIZE - 1) / BPF_REG_SIZE?
>
> You're saying this was always broken, regardless of the current patch, right? I
I think so, yes...
> think you're right, but that seems like a bug that should have been
> caught somehow; I'm surprised no programs crashed the verifier. Perhaps in
> practice all stack accesses are 8-byte aligned, so the rounding doesn't matter?
>
> I'll spend a bit of time reading code and come back.
Thanks!
>
> [...]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: fix accesses to uninit stack slots
2023-11-29 23:54 ` Andrii Nakryiko
@ 2023-12-02 22:41 ` Andrei Matei
0 siblings, 0 replies; 14+ messages in thread
From: Andrei Matei @ 2023-12-02 22:41 UTC (permalink / raw
To: Andrii Nakryiko; +Cc: bpf, sunhao.th, eddyz87, kernel-team
On Wed, Nov 29, 2023 at 6:55 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Nov 29, 2023 at 8:48 AM Andrei Matei <andreimatei1@gmail.com> wrote:
> >
> > [...]
> >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index af2819d5c8ee..f9546dd73f3c 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -1685,10 +1685,12 @@ static int resize_reference_state(struct bpf_func_state *state, size_t n)
> > > > return 0;
> > > > }
> > > >
> > > > -static int grow_stack_state(struct bpf_func_state *state, int size)
> > > > +/* Possibly update state->allocated_stack to be at least size bytes. Also
> > > > + * possibly update the function's high-water mark in its bpf_subprog_info.
> > > > + */
> > > > +static int grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size)
> > > > {
> > > > size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE;
> > >
> > > shouldn't this be rounding up? (size + BPF_REG_SIZE - 1) / BPF_REG_SIZE?
> >
> > You're saying this was always broken, regardless of the current patch, right? I
>
> I think so, yes...
I believe that this code was OK after all because all the callers to
grow_stack_state() do the rounding. This seems fragile though; I'll include a
patch to push the rounding inside grow_stack_state() if it's OK to you.
While reading the code around how the stack is accessed, something else caught
my eye. I'm not sure if there's a problem or not; perhaps you could take a
look. Around here in check_stack_write_fixed_off() [1], the code that deals
with register spills has a couple of cases, including:
[1] https://github.com/torvalds/linux/blob/815fb87b753055df2d9e50f6cd80eb10235fe3e9/kernel/bpf/verifier.c#L4733-L4744
} else if (reg && is_spillable_regtype(reg->type)) {
/* register containing pointer is being spilled into stack */
if (size != BPF_REG_SIZE) {
verbose_linfo(env, insn_idx, "; ");
verbose(env, "invalid size of register spill\n");
return -EACCES;
}
if (state != cur && reg->type == PTR_TO_STACK) {
verbose(env, "cannot spill pointers to stack into stack frame of
the caller\n");
return -EINVAL;
}
save_register_state(state, spi, reg, size);
}
This branch, as opposed to all the others, calls save_register_state() without
checking that `!(off % BPF_REG_SIZE)`. I believe save_register_spill()
implicitly assumes that the access is aligned, so it'd be bad if `off` was not
aligned. Is it possible for the offset to not be aligned? I'm not sure... The
higher-level check_mem_access() starts with a check_ptr_alignment(), which I
think does the required check at least on the code paths that I've tried. But
then why do all the other branches in check_stack_write_fixed_off() check for
the alignment explicitly? FWIW, the branch in question also has a
is_spillable_regtype() check which is perhaps relevant.
Would an assertion that off is indeed aligned in the branch I'm talking about
(or elsewhere around) be welcomed?
Apologies if I'm paranoid for no reason.
>
> > think you're right, but that seems like a bug that should have been
> > caught somehow; I'm surprised no programs crashed the verifier. Perhaps in
> > practice all stack accesses are 8-byte aligned, so the rounding doesn't matter?
> >
> > I'll spend a bit of time reading code and come back.
>
> Thanks!
>
> >
> > [...]
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2023-12-02 22:41 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-11-26 1:50 [PATCH bpf v2 0/2] bpf: fix accesses to uninit stack slots Andrei Matei
2023-11-26 1:50 ` [PATCH bpf v2 1/2] " Andrei Matei
2023-11-28 1:33 ` Eduard Zingerman
2023-11-28 1:43 ` Eduard Zingerman
2023-11-28 14:14 ` Eduard Zingerman
2023-11-29 6:05 ` Andrii Nakryiko
2023-11-29 16:48 ` Andrei Matei
2023-11-29 23:54 ` Andrii Nakryiko
2023-12-02 22:41 ` Andrei Matei
2023-11-26 1:50 ` [PATCH bpf v2 2/2] bpf: new verifier tests for stack access Andrei Matei
2023-11-28 1:23 ` Eduard Zingerman
2023-11-28 3:15 ` Andrei Matei
2023-11-28 12:55 ` Eduard Zingerman
2023-11-29 6:12 ` Andrii Nakryiko
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.