[bpf-next,0/2] Allow reads from uninit stack

Message

Eduard Zingerman Feb. 16, 2023, 6:36 p.m. UTC

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].

[1] https://lore.kernel.org/bpf/[e-mail]/

Eduard Zingerman (2):
  bpf: Allow reads from uninit stack
  selftests/bpf: Tests for uninitialized stack reads

 kernel/bpf/verifier.c                         |  10 ++
 .../selftests/bpf/prog_tests/uninit_stack.c   |   9 ++
 .../selftests/bpf/progs/test_global_func10.c  |   6 +-
 .../selftests/bpf/progs/uninit_stack.c        |  55 +++++++++
 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, 171 insertions(+), 134 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/uninit_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/uninit_stack.c

Comments

Daniel Borkmann Feb. 17, 2023, 8:37 p.m. UTC | #1

On 2/16/23 7:36 PM, Eduard Zingerman 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_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].
> 
> [1] https://lore.kernel.org/bpf/[e-mail]/

Ptal, looks like BPF CI is complaining:

https://github.com/kernel-patches/bpf/actions/runs/4205832876/jobs/7298488977

   [...]
     GEN-SKEL [test_progs] bpf_mod_race.skel.h
     GEN-SKEL [test_progs] trace_dummy_st_ops.skel.h
   libbpf: sec 'socket': corrupted program 'read_uninit_stack_fixed_off', offset 0, size 0
   Error: failed to open BPF object file: Invalid argument
     GEN-SKEL [test_progs] test_raw_tp_test_run.skel.h
   make: *** [Makefile:578: /tmp/work/bpf/bpf/tools/testing/selftests/bpf/uninit_stack.skel.h] Error 234
   make: *** Deleting file '/tmp/work/bpf/bpf/tools/testing/selftests/bpf/uninit_stack.skel.h'
   make: *** Waiting for unfinished jobs....
   make: Leaving directory '/tmp/work/bpf/bpf/tools/testing/selftests/bpf'
   Error: Process completed with exit code 2.

Eduard Zingerman Feb. 17, 2023, 8:46 p.m. UTC | #2

On Fri, 2023-02-17 at 21:37 +0100, Daniel Borkmann wrote:
[...]

> Ptal, looks like BPF CI is complaining:
> 
> https://github.com/kernel-patches/bpf/actions/runs/4205832876/jobs/7298488977
>

Yes, I messed up comments in the asm blocks when replaced '\n\' line
endings with '\' before sending the patch w/o re-testing.
Sorry about that.

I'm waiting for answers from Andrii and will resend the patch-set.

---

Here is how the tests should look like:

/* Read an uninitialized value from stack at a fixed offset */
SEC("socket")
__naked int read_uninit_stack_fixed_off(void *ctx)
{
	asm volatile ("					\
		r0 = 0;					\
		/* force stack depth to be 128 */	\
		*(u64*)(r10 - 128) = r1;		\
		r1 = *(u8 *)(r10 - 8 );			\
		r0 += r1;				\
		r1 = *(u8 *)(r10 - 11);			\
		r1 = *(u8 *)(r10 - 13);			\
		r1 = *(u8 *)(r10 - 15);			\
		r1 = *(u16*)(r10 - 16);			\
		r1 = *(u32*)(r10 - 32);			\
		r1 = *(u64*)(r10 - 64);			\
		/* read from a spill of a wrong size, it is a separate	\
		 * branch in check_stack_read_fixed_off()		\
		 */					\
		*(u32*)(r10 - 72) = r1;			\
		r1 = *(u64*)(r10 - 72);			\
		r0 = 0;					\
		exit;					\
"
		      ::: __clobber_all);
}

/* Read an uninitialized value from stack at a variable offset */
SEC("socket")
__naked int read_uninit_stack_var_off(void *ctx)
{
	asm volatile ("					\
		call %[bpf_get_prandom_u32];		\
		/* force stack depth to be 64 */	\
		*(u64*)(r10 - 64) = r0;			\
		r0 = -r0;				\
		/* give r0 a range [-31, -1] */		\
		if r0 s<= -32 goto exit_%=;		\
		if r0 s>= 0 goto exit_%=;		\
		/* access stack using r0 */		\
		r1 = r10;				\
		r1 += r0;				\
		r2 = *(u8*)(r1 + 0);			\
exit_%=:	r0 = 0;					\
		exit;					\
"
		      :
		      : __imm(bpf_get_prandom_u32)
		      : __clobber_all);
}

[...]