[bpf-next,0/4] reduce BPF_ID_MAP_SIZE to fit only valid programs

Message

Eduard Zingerman Dec. 17, 2022, 2:17 a.m. UTC

This is a follow-up for threads [1] and [2]:
 - The size of the bpf_verifier_state->idmap_scratch array is reduced but
   remains sufficient for any valid BPF program.
 - selftests/bpf test_loader is updated to allow specifying that program
   requires BPF_F_TEST_STATE_FREQ flag.
 - Test case for the verifier.c:check_ids() update uses test_loader and is
   meant as an example of using it for test_verifier-kind tests.

The combination of test_loader and naked functions (see [3]) with inline
assembly allows to write verifier tests easier than it is done currently
with BPF_RAW_INSN-series macros.

One can follow the steps below to add new tests of such kind:
 - add a topic file under bpf/progs/ directory;
 - define test programs using naked functions and inline assembly:

	#include <linux/bpf.h>
	#include "bpf_misc.h"
	
	SEC(...)
	__naked int foo_test(void)
	{
		asm volatile(
			"r0 = 0;"
			"exit;"
			::: __clobber_all);
	}
	
 - add skeleton and runner functions in prog_tests/verifier.c:
 
	#include "topic.skel.h"
	TEST_SET(topic)

After these steps the test_progs binary would include the topic tests.
Topic tests could be selectively executed using the following command:

$ ./test_progs -vvv -a topic

These changes are suggested by Andrii Nakryiko.

[1] https://lore.kernel.org/bpf/[e-mail]/
[2] https://lore.kernel.org/bpf/CAEf4BzYPsDWdRgx+ND1wiKAB62P=[e-mail]/
[3] https://gcc.gnu.org/onlinedocs/gcc/Basic-Asm.html#Basic-Asm

Eduard Zingerman (4):
  selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
  selftests/bpf: convenience macro for use with 'asm volatile' blocks
  bpf: reduce BPF_ID_MAP_SIZE to fit only valid programs
  selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids

 include/linux/bpf_verifier.h                  |  4 +-
 kernel/bpf/verifier.c                         |  6 +-
 .../selftests/bpf/prog_tests/verifier.c       | 12 +++
 tools/testing/selftests/bpf/progs/bpf_misc.h  |  7 ++
 .../selftests/bpf/progs/check_ids_limits.c    | 77 +++++++++++++++++++
 tools/testing/selftests/bpf/test_loader.c     | 10 +++
 6 files changed, 112 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c
 create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c

Comments

Andrii Nakryiko Dec. 20, 2022, 9:21 p.m. UTC | #1

On Fri, Dec 16, 2022 at 6:17 PM Eduard Zingerman <[e-mail]> wrote:
>
> This is a follow-up for threads [1] and [2]:
>  - The size of the bpf_verifier_state->idmap_scratch array is reduced but
>    remains sufficient for any valid BPF program.
>  - selftests/bpf test_loader is updated to allow specifying that program
>    requires BPF_F_TEST_STATE_FREQ flag.
>  - Test case for the verifier.c:check_ids() update uses test_loader and is
>    meant as an example of using it for test_verifier-kind tests.
>
> The combination of test_loader and naked functions (see [3]) with inline
> assembly allows to write verifier tests easier than it is done currently
> with BPF_RAW_INSN-series macros.
>
> One can follow the steps below to add new tests of such kind:
>  - add a topic file under bpf/progs/ directory;
>  - define test programs using naked functions and inline assembly:

it's better, you don't *have* to use __naked functions, you can mix
and match. E.g., I have local tests that rely on the C compiler to do
stack allocation for local variables (%[dynptr]) and global variables
(%[zero]) and pass an address (fp-X) register to asm parts to work
with it.

+int zero;
+
+SEC("?raw_tp")
+__failure
+__flags(BPF_F_TEST_STATE_FREQ)
+__msg("invalid size of register fill")
+int stacksafe_should_not_conflate_stack_spill_and_dynptr(void *ctx)
+{
+       struct bpf_dynptr dynptr;
+
+       asm volatile (
+               /* Create a fork in logic, with general setup as follows:
+                *   - fallthrough (first) path is valid;
+                *   - branch (second) path is invalid.
+                * Then depending on what we do in fallthrough vs branch path,
+                * we try to detect bugs in func_states_equal(), regsafe(),
+                * refsafe(), stack_safe(), and similar by tricking verifier
+                * into believing that branch state is a valid subset of
+                * a fallthrough state. Verifier should reject overall
+                * validation, unless there is a bug somewhere in verifier
+                * logic.
+                */
+               "call %[bpf_get_prandom_u32];"
+               "r6 = r0;"
+               "call %[bpf_get_prandom_u32];"
+               "r7 = r0;"
+               "if r6 > r7 goto bad;" /* fork */
+
+               /* spill r6 into stack slot of bpf_dynptr var */
+               "*(u64 *)(%[dynptr] + 0) = r6;"
+               "*(u64 *)(%[dynptr] + 8) = r6;"
+
+               "goto skip_bad;"
+       "bad:"
+               /* create dynptr in the same stack slot */
+               "r1 = %[zero];"
+               "r2 = 4;"
+               "r3 = 0;"
+               "r4 = %[dynptr];"
+               "call %[bpf_dynptr_from_mem];"
+
+               /* here, if stacksafe() doesn't distinguish STACK_DYNPTR from
+                * STACK_MISC, verifier will assume safety at checkpoint below
+                */
+       "skip_bad:"
+               "goto +0;" /* force checkpoint */
+
+               /* leak dynptr state */
+               "r0 = *(u64 *)(%[dynptr] + 8);"
+               "if r0 > 0 goto +1;"
+               "exit;"
+               :
+               : __asm_ptr(dynptr), __asm_ptr(zero),
+                 __asm_imm(bpf_get_prandom_u32),
+                 __asm_imm(bpf_dynptr_from_mem)
+               : __asm_common_clobbers, "r6", "r7"
+       );
+
+       return 0;
+}



>
>         #include <linux/bpf.h>
>         #include "bpf_misc.h"
>
>         SEC(...)
>         __naked int foo_test(void)
>         {
>                 asm volatile(
>                         "r0 = 0;"
>                         "exit;"
>                         ::: __clobber_all);
>         }
>
>  - add skeleton and runner functions in prog_tests/verifier.c:
>
>         #include "topic.skel.h"
>         TEST_SET(topic)
>
> After these steps the test_progs binary would include the topic tests.
> Topic tests could be selectively executed using the following command:
>
> $ ./test_progs -vvv -a topic
>
> These changes are suggested by Andrii Nakryiko.
>
> [1] https://lore.kernel.org/bpf/[e-mail]/
> [2] https://lore.kernel.org/bpf/CAEf4BzYPsDWdRgx+ND1wiKAB62P=[e-mail]/
> [3] https://gcc.gnu.org/onlinedocs/gcc/Basic-Asm.html#Basic-Asm
>
> Eduard Zingerman (4):
>   selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
>   selftests/bpf: convenience macro for use with 'asm volatile' blocks
>   bpf: reduce BPF_ID_MAP_SIZE to fit only valid programs
>   selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids
>
>  include/linux/bpf_verifier.h                  |  4 +-
>  kernel/bpf/verifier.c                         |  6 +-
>  .../selftests/bpf/prog_tests/verifier.c       | 12 +++
>  tools/testing/selftests/bpf/progs/bpf_misc.h  |  7 ++
>  .../selftests/bpf/progs/check_ids_limits.c    | 77 +++++++++++++++++++
>  tools/testing/selftests/bpf/test_loader.c     | 10 +++
>  6 files changed, 112 insertions(+), 4 deletions(-)
>  create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c
>  create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c
>
> --
> 2.38.2
>