bpf: Allow reads from uninit stack
Subsystems (4)
Eduard Zingerman
maintainerv2 cover bpf: Allow reads from uninit stack
This patch-set modifies BPF verifier to accept programs that read from uninitialized stack locations, but only if executed in privileged mode. This provides significant verification performance gains: 30% to 70% less processed states for big number of test programs.
The reason for performance gains comes from treating STACK_MISC and STACK_INVALID as compatible, when cached state is compared to current state in verifier.c:stacksafe().
The change should not affect safety, because any value read from STACK_MISC location has full binary range (e.g. 0x00-0xff for byte-sized reads).
Details and measurements are provided in the description for the patch #1.
The change was suggested by Andrii Nakryiko, the initial patch was created by Alexei Starovoitov. The discussion could be found at [1].
Changes v1 -> v2 (v1 available at [2]):
- Calls to helper functions now convert STACK_INVALID to STACK_MISC (suggested by Andrii);
- The test case progs/test_global_func10.c is updated to expect new error message. Before recent commit [3] exact content of error messages was not verified for this test.
- Replaced incorrect '//'-style comments in test case asm blocks by '/*...*/'-style comments in order to fix compilation issues;
- Changed the tag from "Suggested-By" to "Co-developed-by" for Alexei on patch #1, please let me know if this is appropriate use of the tag.
[1] https://lore.kernel.org/bpf/CAADnVQKs2i1iuZ5SUGuJtxWVfGYR9kDgYKhq3rNV+kBLQCu7rA@mail.gmail.com/
[2] https://lore.kernel.org/bpf/[email protected]/
[3] 95ebb376176c ("selftests/bpf: Convert test_global_funcs test to test_loader framework")
Eduard Zingerman (2):
bpf: Allow reads from uninit stack selftests/bpf: Tests for uninitialized stack reads
kernel/bpf/verifier.c | 11 +- .../selftests/bpf/prog_tests/uninit_stack.c | 9 ++ .../selftests/bpf/progs/test_global_func10.c | 8 +- .../selftests/bpf/progs/uninit_stack.c | 87 +++++++++++++++ tools/testing/selftests/bpf/verifier/calls.c | 13 ++- .../bpf/verifier/helper_access_var_len.c | 104 ++++++++++++------ .../testing/selftests/bpf/verifier/int_ptr.c | 9 +- .../selftests/bpf/verifier/search_pruning.c | 13 ++- tools/testing/selftests/bpf/verifier/sock.c | 27 ----- .../selftests/bpf/verifier/spill_fill.c | 7 +- .../testing/selftests/bpf/verifier/var_off.c | 52 --------- 11 files changed, 204 insertions(+), 136 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/uninit_stack.c create mode 100644 tools/testing/selftests/bpf/progs/uninit_stack.c
Signature · 1 line
2.39.1
Eduard Zingerman
maintainerPATCH v2 1/2 bpf: Allow reads from uninit stack
This commits updates the following functions to allow reads from uninitialized stack locations when env->allow_uninit_stack option is enabled:
- check_stack_read_fixed_off()
- check_stack_range_initialized(), called from:
- check_stack_read_var_off()
- check_helper_mem_access()
Such change allows to relax logic in stacksafe() to treat STACK_MISC and STACK_INVALID in a same way and make the following stack slot configurations equivalent:
| Cached state | Current state | | stack slot | stack slot | |------------------+------------------| | STACK_INVALID or | STACK_INVALID or | | STACK_MISC | STACK_SPILL or | | | STACK_MISC or | | | STACK_ZERO or | | | STACK_DYNPTR |
This leads to significant verification speed gains (see below).
The idea was suggested by Andrii Nakryiko [1] and initial patch was created by Alexei Starovoitov [2].
Currently the env->allow_uninit_stack is allowed for programs loaded by users with CAP_PERFMON or CAP_SYS_ADMIN capabilities.
A number of test cases from verifier/*.c were expecting uninitialized stack access to be an error. These test cases were updated to execute in unprivileged mode (thus preserving the tests).
The test progs/test_global_func10.c expected "invalid indirect read from stack" error message because of the access to uninitialized memory region. This error is no longer possible in privileged mode. The test is updated to provoke an error "invalid indirect access to stack" because of access to invalid stack address (such error is not verified by progs/test_global_func*.c series of tests).
The following tests had to be removed because these can't be made unprivileged:
- verifier/sock.c:
- "sk_storage_get(map, skb->sk, &stack_value, 1): partially init stack_value"
BPF_PROG_TYPE_SCHED_CLS programs are not executed in unprivileged mode.
- verifier/var_off.c:
- "indirect variable-offset stack access, max_off+size > max_initialized"
- "indirect variable-offset stack access, uninitialized" These tests verify that access to uninitialized stack values is detected when stack offset is not a constant. However, variable stack access is prohibited in unprivileged mode, thus these tests are no longer valid.
* * *
Here is veristat log comparing this patch with current master on a set of selftest binaries listed in tools/testing/selftests/bpf/veristat.cfg and cilium BPF binaries (see [3]):
$ ./veristat -e file,prog,states -C -f 'states_pct<-30' master.log current.log File Program States (A) States (B) States (DIFF) -------------------------- -------------------------- ---------- ---------- ---------------- bpf_host.o tail_handle_ipv6_from_host 349 244 -105 (-30.09%) bpf_host.o tail_handle_nat_fwd_ipv4 1320 895 -425 (-32.20%) bpf_lxc.o tail_handle_nat_fwd_ipv4 1320 895 -425 (-32.20%) bpf_sock.o cil_sock4_connect 70 48 -22 (-31.43%) bpf_sock.o cil_sock4_sendmsg 68 46 -22 (-32.35%) bpf_xdp.o tail_handle_nat_fwd_ipv4 1554 803 -751 (-48.33%) bpf_xdp.o tail_lb_ipv4 6457 2473 -3984 (-61.70%) bpf_xdp.o tail_lb_ipv6 7249 3908 -3341 (-46.09%) pyperf600_bpf_loop.bpf.o on_event 287 145 -142 (-49.48%) strobemeta.bpf.o on_event 15915 4772 -11143 (-70.02%) strobemeta_nounroll2.bpf.o on_event 17087 3820 -13267 (-77.64%) xdp_synproxy_kern.bpf.o syncookie_tc 21271 6635 -14636 (-68.81%) xdp_synproxy_kern.bpf.o syncookie_xdp 23122 6024 -17098 (-73.95%) -------------------------- -------------------------- ---------- ---------- ----------------
Note: I limited selection by states_pct<-30%.
Inspection of differences in pyperf600_bpf_loop behavior shows that the following patch for the test removes almost all differences:
- a/tools/testing/selftests/bpf/progs/pyperf.h
+ b/tools/testing/selftests/bpf/progs/pyperf.h
@ -266,8 +266,8 @ int __on_event(struct bpf_raw_tracepoint_args *ctx)
}
if (event->pthread_match || !pidData->use_tls) {
- void* frame_ptr;
- FrameData frame;
+ void* frame_ptr = 0;
+ FrameData frame = {};
Symbol sym = {};
int cur_cpu = bpf_get_smp_processor_id();
W/o this patch the difference comes from the following pattern (for different variables):
static bool get_frame_data(... FrameData *frame ...)
{
...
bpf_probe_read_user(&frame->f_code, ...);
if (!frame->f_code)
return false;
...
bpf_probe_read_user(&frame->co_name, ...);
if (frame->co_name)
...;
}
int __on_event(struct bpf_raw_tracepoint_args *ctx)
{
FrameData frame;
...
get_frame_data(... &frame ...) // indirectly via a bpf_loop & callback
...
}
SEC("raw_tracepoint/kfree_skb")
int on_event(struct bpf_raw_tracepoint_args* ctx)
{
...
ret |= __on_event(ctx);
ret |= __on_event(ctx);
...
}With regards to value frame->co_name the following is important:
- Because of the conditional if (!frame->f_code) each call to __on_event() produces two states, one with frame->co_name marked as STACK_MISC, another with it as is (and marked STACK_INVALID on a first call).
- The call to bpf_probe_read_user() does not mark stack slots corresponding to &frame->co_name as REG_LIVE_WRITTEN but it marks these slots as BPF_MISC, this happens because of the following loop in the check_helper_call():
for (i = 0; i < meta.access_size; i++) {
err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B,
BPF_WRITE, -1, false);
if (err)
return err;
} Note the size of the write, it is a one byte write for each byte touched by a helper. The BPF_B write does not lead to write marks for the target stack slot.
- Which means that w/o this patch when second __on_event() call is verified if (frame->co_name) will propagate read marks first to a stack slot with STACK_MISC marks and second to a stack slot with STACK_INVALID marks and these states would be considered different.
[1] https://lore.kernel.org/bpf/CAEf4BzY3e+ZuC6HUa8dCiUovQRg2SzEk7M-dSkqNZyn=xEmnPA@mail.gmail.com/
[2] https://lore.kernel.org/bpf/CAADnVQKs2i1iuZ5SUGuJtxWVfGYR9kDgYKhq3rNV+kBLQCu7rA@mail.gmail.com/
[3] [email protected]:anakryiko/cilium.git
--- kernel/bpf/verifier.c | 11 +- .../selftests/bpf/progs/test_global_func10.c | 8 +- tools/testing/selftests/bpf/verifier/calls.c | 13 ++- .../bpf/verifier/helper_access_var_len.c | 104 ++++++++++++------ .../testing/selftests/bpf/verifier/int_ptr.c | 9 +- .../selftests/bpf/verifier/search_pruning.c | 13 ++- tools/testing/selftests/bpf/verifier/sock.c | 27 ----- .../selftests/bpf/verifier/spill_fill.c | 7 +- .../testing/selftests/bpf/verifier/var_off.c | 52 --------- 9 files changed, 108 insertions(+), 136 deletions(-)
kernel/bpf/verifier.c +10 -1
@@ -3826,6 +3826,8 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,continue ;if (type ==STACK_MISC )continue ; +if (type ==STACK_INVALID && env->allow_uninit_stack) +continue ;verbose (env,"invalid read from stack off %d+%d size %d\n" , off, i, size);return -EACCES ;
@@ -3863,6 +3865,8 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,continue ;if (type ==STACK_ZERO )continue ; +if (type ==STACK_INVALID && env->allow_uninit_stack) +continue ;verbose (env,"invalid read from stack off %d+%d size %d\n" , off, i, size);return -EACCES ;
@@ -5754,7 +5758,8 @@ static int check_stack_range_initialized( stype = &state->stack[spi].slot_type[slot %BPF_REG_SIZE ];if (*stype ==STACK_MISC ) goto mark; -if (*stype ==STACK_ZERO ) { +if ((*stype ==STACK_ZERO ) || + (*stype ==STACK_INVALID && env->allow_uninit_stack)) {if (clobber) {/* helper can write anything into the stack */ *stype =STACK_MISC ;
@@ -13936,6 +13941,10 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,if (old->stack[spi].slot_type[i %BPF_REG_SIZE ] ==STACK_INVALID )continue ; +if (env->allow_uninit_stack && + old->stack[spi].slot_type[i %BPF_REG_SIZE ] ==STACK_MISC ) +continue ; +/* explored stack has more populated slots than current stack * and these slots were used */
tools/testing/selftests/bpf/progs/test_global_func10.c +4 -4
@@ -5,12 +5,12 @@#include "bpf_misc.h" struct Small { -int x; +long x; };struct Big { -int x; -int y; +long x; +long y; }; __noinline int foo(const struct Big *big)
@@ -22,7 +22,7 @@ __noinline int foo(const struct Big *big) } SEC("cgroup_skb/ingress") -__failure __msg("invalid indirect read from stack") +__failure __msg("invalid indirect access to stack") int global_func10(struct __sk_buff *skb) {const struct Small small = {.x = skb->len };
tools/testing/selftests/bpf/verifier/calls.c +8 -5
@@ -2221,19 +2221,22 @@* that fp-8 stack slot was unused in the fall-through * branch and will accept the program incorrectly */ -BPF_JMP_IMM (BPF_JGT ,BPF_REG_1 ,2 ,2 ), +BPF_EMIT_CALL (BPF_FUNC_get_prandom_u32), +BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,2 ,2 ),BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ),BPF_JMP_IMM (BPF_JA ,0 ,0 ,0 ),BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ),BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ),BPF_LD_MAP_FD (BPF_REG_1 ,0 ),BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), BPF_EXIT_INSN(), }, - .fixup_map_hash_48b = { 6 }, - .errstr = "invalid indirect read from stack R2 off -8+0 size 8", - .result = REJECT, - .prog_type = BPF_PROG_TYPE_XDP, + .fixup_map_hash_48b = { 7 }, + .errstr_unpriv = "invalid indirect read from stack R2 off -8+0 size 8", + .result_unpriv = REJECT, +/* in privileged mode reads from uninitialized stack locations are permitted */ + .result = ACCEPT, }, { "calls: ctx read at start of subprog",
tools/testing/selftests/bpf/verifier/helper_access_var_len.c +69 -35
137 lines not on this page · raw message
tools/testing/selftests/bpf/verifier/int_ptr.c +5 -4
@@ -54,12 +54,13 @@/* bpf_strtoul() */ BPF_EMIT_CALL (BPF_FUNC_strtoul), -BPF_MOV64_IMM (BPF_REG_0 ,1 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), BPF_EXIT_INSN(), }, - .result =REJECT , - .prog_type = BPF_PROG_TYPE_CGROUP_SYSCTL, - .errstr = "invalid indirect read from stack R4 off -16+4 size 8", + .result_unpriv =REJECT , + .errstr_unpriv = "invalid indirect read from stack R4 off -16+4 size 8", +/* in privileged mode reads from uninitialized stack locations are permitted */ + .result = ACCEPT, }, { "ARG_PTR_TO_LONG misaligned",
tools/testing/selftests/bpf/verifier/search_pruning.c +8 -5
@@ -128,9 +128,10 @@ BPF_EXIT_INSN(), }, .fixup_map_hash_8b = { 3 }, - .errstr = "invalid read from stack off -16+0 size 8", - .result = REJECT, - .prog_type =BPF_PROG_TYPE_TRACEPOINT , + .errstr_unpriv = "invalid read from stack off -16+0 size 8", + .result_unpriv = REJECT, +/* in privileged mode reads from uninitialized stack locations are permitted */ + .result =ACCEPT , }, { "precision tracking for u32 spill/fill",
@@ -258,6 +259,8 @@ BPF_EXIT_INSN(), }, .flags = BPF_F_TEST_STATE_FREQ, - .errstr = "invalid read from stack off -8+1 size 8", - .result = REJECT, + .errstr_unpriv = "invalid read from stack off -8+1 size 8", + .result_unpriv = REJECT, +/* in privileged mode reads from uninitialized stack locations are permitted */ + .result = ACCEPT, },
tools/testing/selftests/bpf/verifier/sock.c +0 -27
@@ -530,33 +530,6 @@ .prog_type = BPF_PROG_TYPE_SCHED_CLS, .result = ACCEPT, }, -{ - "sk_storage_get(map, skb->sk, &stack_value, 1): partially init stack_value", - .insns = { -BPF_MOV64_IMM (BPF_REG_2 ,0 ), -BPF_STX_MEM (BPF_W ,BPF_REG_10 ,BPF_REG_2 ,-8 ), -BPF_LDX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_1 , offsetof(struct __sk_buff , sk)), -BPF_JMP_IMM (BPF_JNE ,BPF_REG_1 ,0 ,2 ), -BPF_MOV64_IMM (BPF_REG_0 ,0 ), -BPF_EXIT_INSN (), -BPF_EMIT_CALL (BPF_FUNC_sk_fullsock), -BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,2 ), -BPF_MOV64_IMM (BPF_REG_0 ,0 ), -BPF_EXIT_INSN (), -BPF_MOV64_IMM (BPF_REG_4 ,1 ), -BPF_MOV64_REG (BPF_REG_3 ,BPF_REG_10 ), -BPF_ALU64_IMM (BPF_ADD ,BPF_REG_3 ,-8 ), -BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_0 ), -BPF_LD_MAP_FD (BPF_REG_1 ,0 ), -BPF_EMIT_CALL (BPF_FUNC_sk_storage_get), -BPF_MOV64_IMM (BPF_REG_0 ,0 ), - BPF_EXIT_INSN(), - }, - .fixup_sk_storage_map = { 14 }, - .prog_type = BPF_PROG_TYPE_SCHED_CLS, - .result = REJECT, - .errstr = "invalid indirect read from stack", -}, { "bpf_map_lookup_elem(smap, &key)", .insns = {
tools/testing/selftests/bpf/verifier/spill_fill.c +4 -3
@@ -171,9 +171,10 @@BPF_MOV64_IMM (BPF_REG_0 ,0 ), BPF_EXIT_INSN(), }, - .result =REJECT , - .errstr = "invalid read from stack off -4+0 size 4", - .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result_unpriv =REJECT , + .errstr_unpriv = "invalid read from stack off -4+0 size 4", +/* in privileged mode reads from uninitialized stack locations are permitted */ + .result = ACCEPT, }, { "Spill a u32 const scalar. Refill as u16. Offset to skb->data",
tools/testing/selftests/bpf/verifier/var_off.c +0 -52
64 lines not on this page · raw message
Signature · 1 line
2.39.1
Eduard Zingerman
maintainerPATCH v2 2/2 selftests/bpf: Tests for uninitialized stack reads
In reply to Eduard ZingermanThree testcases to make sure that stack reads from uninitialized locations are accepted by verifier when executed in privileged mode:
- read from a fixed offset;
- read from a variable offset;
- passing a pointer to stack to a helper converts STACK_INVALID to STACK_MISC.
--- .../selftests/bpf/prog_tests/uninit_stack.c | 9 ++ .../selftests/bpf/progs/uninit_stack.c | 87 +++++++++++++++++++ 2 files changed, 96 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/uninit_stack.c create mode 100644 tools/testing/selftests/bpf/progs/uninit_stack.c
tools/testing/selftests/bpf/prog_tests/uninit_stack.c new file +9 -0
@@ -0,0 +1,9 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <test_progs.h> +#include "uninit_stack.skel.h" + +void test_uninit_stack (void ) +{ +RUN_TESTS (uninit_stack); +}
tools/testing/selftests/bpf/progs/uninit_stack.c new file +87 -0
87 lines not on this page · raw message
Signature · 1 line
2.39.1
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 10 lines · On Sun, 19 Feb 2023 22:04:25 +0200 you wrote:
This patch-set modifies BPF verifier to accept programs that read from uninitialized stack locations, but only if executed in privileged mode. This provides significant verification performance gains: 30% to 70% less processed states for big number of test programs.
The reason for performance gains comes from treating
STACK_MISCandSTACK_INVALIDas compatible, when cached state is compared to current state in verifier.c:stacksafe().[...]
Here is the summary with links:
- [bpf-next,v2,1/2] bpf: Allow reads from uninit stack
https://git.kernel.org/bpf/bpf-next/c/6715df8d5d24 - [bpf-next,v2,2/2] selftests/bpf: Tests for uninitialized stack reads https://git.kernel.org/bpf/bpf-next/c/6338a94d5ab4
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html