On Thu, Feb 16, 2023 at 10:36 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> 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 access
> to stack" error message because of the access to uninitialized memory
> region. The test is updated to provoke the same error message by
> accessing stack out of allocated range.
>
> 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@xxxxxxxxxxxxxx/
> [2] https://lore.kernel.org/bpf/CAADnVQKs2i1iuZ5SUGuJtxWVfGYR9kDgYKhq3rNV+kBLQCu7rA@xxxxxxxxxxxxxx/
> [3] git@xxxxxxxxxx:anakryiko/cilium.git
>
> Suggested-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
> Suggested-by: Alexei Starovoitov <ast@xxxxxxxxxx>
> Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
> ---
> kernel/bpf/verifier.c | 10 ++
> .../selftests/bpf/progs/test_global_func10.c | 6 +-
> 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, 107 insertions(+), 134 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 272563a0b770..6fbd0e25ccab 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -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;
> @@ -5761,6 +5765,8 @@ static int check_stack_range_initialized(
> }
> goto mark;
> }
> + if (*stype == STACK_INVALID && env->allow_uninit_stack)
> + goto mark;
should we support clobber and conversion to STACK_MISC like we do for
STACK_ZERO? If yes, probably cleaner to just extend condition to
if ((*stype == STACK_ZERO) || (*stype == STACK_INVALID &&
env->allow_uninit_stack))
?
Other than that, looks good:
Acked-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
>
> if (is_spilled_reg(&state->stack[spi]) &&
> (state->stack[spi].spilled_ptr.type == SCALAR_VALUE ||
> @@ -13936,6 +13942,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
> */
[...]
