[PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Yonghong Song]

Daniel Hodges reported a kernel verifier crash when playing with sched-ext.
The crash dump looks like below:

  [   65.874474] BUG: kernel NULL pointer dereference, address: 0000000000000088
  [   65.888406] #PF: supervisor read access in kernel mode
  [   65.898682] #PF: error_code(0x0000) - not-present page
  [   65.908957] PGD 0 P4D 0
  [   65.914020] Oops: 0000 [#1] SMP
  [   65.920300] CPU: 19 PID: 9364 Comm: scx_layered Kdump: loaded Tainted: G S          E      6.9.5-g93cea04637ea-dirty #7
  [   65.941874] Hardware name: Quanta Delta Lake MP 29F0EMA01D0/Delta Lake-Class1, BIOS F0E_3A19 04/27/2023
  [   65.960664] RIP: 0010:states_equal+0x3ee/0x770
  [   65.969559] Code: 33 85 ed 89 e8 41 0f 48 c7 83 e0 f8 89 e9 29 c1 48 63 c1 4c 89 e9 48 c1 e1 07 49 8d 14 08 0f
                 b6 54 10 78 49 03 8a 58 05 00 00 <3a> 54 08 78 0f 85 60 03 00 00 49 c1 e5 07 43 8b 44 28 70 83 e0 03
  [   66.007120] RSP: 0018:ffffc9000ebeb8b8 EFLAGS: 00010202
  [   66.017570] RAX: 0000000000000000 RBX: ffff888149719680 RCX: 0000000000000010
  [   66.031843] RDX: 0000000000000000 RSI: ffff88907f4e0c08 RDI: ffff8881572f0000
  [   66.046115] RBP: 0000000000000000 R08: ffff8883d5014000 R09: ffffffff83065d50
  [   66.060386] R10: ffff8881bf9a1800 R11: 0000000000000002 R12: 0000000000000000
  [   66.074659] R13: 0000000000000000 R14: ffff888149719a40 R15: 0000000000000007
  [   66.088932] FS:  00007f5d5da96800(0000) GS:ffff88907f4c0000(0000) knlGS:0000000000000000
  [   66.105114] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
  [   66.116606] CR2: 0000000000000088 CR3: 0000000388261001 CR4: 00000000007706f0
  [   66.130873] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
  [   66.145145] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
  [   66.159416] PKRU: 55555554
  [   66.164823] Call Trace:
  [   66.169709]  <TASK>
  [   66.173906]  ? __die_body+0x66/0xb0
  [   66.180890]  ? page_fault_oops+0x370/0x3d0
  [   66.189082]  ? console_unlock+0xb5/0x140
  [   66.196926]  ? exc_page_fault+0x4f/0xb0
  [   66.204597]  ? asm_exc_page_fault+0x22/0x30
  [   66.212974]  ? states_equal+0x3ee/0x770
  [   66.220643]  ? states_equal+0x529/0x770
  [   66.228312]  do_check+0x60f/0x5240
  [   66.235114]  do_check_common+0x388/0x840
  [   66.242960]  do_check_subprogs+0x101/0x150
  [   66.251150]  bpf_check+0x5d5/0x4b60
  [   66.258134]  ? __mod_memcg_state+0x79/0x110
  [   66.266506]  ? pcpu_alloc+0x892/0xba0
  [   66.273829]  bpf_prog_load+0x5bb/0x660
  [   66.281324]  ? bpf_prog_bind_map+0x1e1/0x290
  [   66.289862]  __sys_bpf+0x29d/0x3a0
  [   66.296664]  __x64_sys_bpf+0x18/0x20
  [   66.303811]  do_syscall_64+0x6a/0x140
  [   66.311133]  entry_SYSCALL_64_after_hwframe+0x4b/0x53

Forther investigation shows that the crash is due to invalid memory access in stacksafe().
More specifically, it is the following code:

    if (exact != NOT_EXACT &&
        old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
        cur->stack[spi].slot_type[i % BPF_REG_SIZE])
            return false;

If cur->allocated_stack is 0, cur->stack will be a ZERO_SIZE_PTR. If this happens,
cur->stack[spi].slot_type[i % BPF_REG_SIZE] will crash the kernel as the memory
address is illegal. This is exactly what happened in the above crash dump.
If cur->allocated_stack is not 0, the above code could trigger array out-of-bound
access.

The patch added a condition 'i < cur->allocated_stack' to ensure
cur->stack[spi].slot_type[i % BPF_REG_SIZE] memory access always legal.

Fixes: 2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks")
Cc: Eduard Zingerman <eddyz87@gmail.com>
Reported-by: Daniel Hodges <hodgesd@meta.com>
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4cb5441ad75f..1e3d7794bf13 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16883,7 +16883,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
 
 		spi = i / BPF_REG_SIZE;
 
-		if (exact != NOT_EXACT &&
+		if (exact != NOT_EXACT && i < cur->allocated_stack &&
 		    old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
 		    cur->stack[spi].slot_type[i % BPF_REG_SIZE])
 			return false;
-- 
2.43.5

[PATCH bpf 2/2] selftests/bpf: Add a test to verify previous stacksafe() fix

[Yonghong Song]

A selftest is added such that without the previous patch,
a crash can happen. With the previous patch, the test can
run successfully. The new test is written in a way which
mimics original crash case:
  main_prog
    static_prog_1
      static_prog_2
where static_prog_1 has different paths to static_prog_2
and some path has stack allocated and some other path
does not. A stacksafe() checking in static_prog_2()
triggered the crash.

Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 tools/testing/selftests/bpf/progs/iters.c | 54 +++++++++++++++++++++++
 1 file changed, 54 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 16bdc3e25591..8d3b75147617 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -1432,4 +1432,58 @@ int iter_arr_with_actual_elem_count(const void *ctx)
 	return sum;
 }
 
+__u32 upper, select_n, result;
+__u64 global;
+
+static __noinline bool nest_2(char *str, int len)
+{
+	/* some insns (including branch insns) to ensure stacksafe() is triggered
+	 * in nest_2(). This way, stacksafe() can compare frame associated with nest_1().
+	 */
+	if (str[0] == 't')
+		return true;
+	if (str[1] == 'e')
+		return true;
+	if (str[2] == 's')
+		return true;
+	if (str[3] == 't')
+		return true;
+	return false;
+}
+
+static __noinline bool nest_1(int n)
+{
+	/* case 0: allocate stack, case 1: no allocate stack */
+	switch (n) {
+	case 0: {
+		char comm[16];
+
+		if (bpf_get_current_comm(comm, 16))
+			return false;
+		return nest_2(comm, 16);
+	}
+	case 1:
+		return nest_2((char *)&global, sizeof(global));
+	default:
+		return false;
+	}
+}
+
+SEC("raw_tp")
+__success
+int iter_subprog_check_stacksafe(const void *ctx)
+{
+	long i;
+
+	bpf_for(i, 0, upper) {
+		if (!nest_1(select_n)) {
+			result = 1;
+			return 0;
+		}
+	}
+
+	result = 2;
+	return 0;
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.5

Re: [PATCH bpf 2/2] selftests/bpf: Add a test to verify previous stacksafe() fix

[Yonghong Song]

On 8/11/24 10:21 PM, Yonghong Song wrote:
> A selftest is added such that without the previous patch,
> a crash can happen. With the previous patch, the test can
> run successfully. The new test is written in a way which
> mimics original crash case:
>    main_prog
>      static_prog_1
>        static_prog_2
> where static_prog_1 has different paths to static_prog_2
> and some path has stack allocated and some other path
> does not. A stacksafe() checking in static_prog_2()
> triggered the crash.
>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---
>   tools/testing/selftests/bpf/progs/iters.c | 54 +++++++++++++++++++++++
>   1 file changed, 54 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
> index 16bdc3e25591..8d3b75147617 100644
> --- a/tools/testing/selftests/bpf/progs/iters.c
> +++ b/tools/testing/selftests/bpf/progs/iters.c
> @@ -1432,4 +1432,58 @@ int iter_arr_with_actual_elem_count(const void *ctx)
>   	return sum;
>   }
>   
> +__u32 upper, select_n, result;
> +__u64 global;
> +
> +static __noinline bool nest_2(char *str, int len)

Argument 'len' is not needed here. I can make the change after some
additional comments.

> +{
> +	/* some insns (including branch insns) to ensure stacksafe() is triggered
> +	 * in nest_2(). This way, stacksafe() can compare frame associated with nest_1().
> +	 */
> +	if (str[0] == 't')
> +		return true;
> +	if (str[1] == 'e')
> +		return true;
> +	if (str[2] == 's')
> +		return true;
> +	if (str[3] == 't')
> +		return true;
> +	return false;
> +}
> +
> +static __noinline bool nest_1(int n)
> +{
> +	/* case 0: allocate stack, case 1: no allocate stack */
> +	switch (n) {
> +	case 0: {
> +		char comm[16];
> +
> +		if (bpf_get_current_comm(comm, 16))
> +			return false;
> +		return nest_2(comm, 16);
> +	}
> +	case 1:
> +		return nest_2((char *)&global, sizeof(global));
> +	default:
> +		return false;
> +	}

To triger the failure, we rely on 'case 0' is explored by the verifier first
and 'case 1' is explored later. This seems the case for llvm18 and llvm20.

> +}
> +
> +SEC("raw_tp")
> +__success
> +int iter_subprog_check_stacksafe(const void *ctx)
> +{
> +	long i;
> +
> +	bpf_for(i, 0, upper) {
> +		if (!nest_1(select_n)) {
> +			result = 1;
> +			return 0;
> +		}
> +	}
> +
> +	result = 2;
> +	return 0;
> +}
> +
>   char _license[] SEC("license") = "GPL";

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Eduard Zingerman]

On Sun, 2024-08-11 at 22:21 -0700, Yonghong Song wrote:
> Daniel Hodges reported a kernel verifier crash when playing with sched-ext.
> The crash dump looks like below:
> 
>   [   65.874474] BUG: kernel NULL pointer dereference, address: 0000000000000088
>   [   65.888406] #PF: supervisor read access in kernel mode
>   [   65.898682] #PF: error_code(0x0000) - not-present page
>   [   65.908957] PGD 0 P4D 0
>   [   65.914020] Oops: 0000 [#1] SMP
>   [   65.920300] CPU: 19 PID: 9364 Comm: scx_layered Kdump: loaded Tainted: G S          E      6.9.5-g93cea04637ea-dirty #7
>   [   65.941874] Hardware name: Quanta Delta Lake MP 29F0EMA01D0/Delta Lake-Class1, BIOS F0E_3A19 04/27/2023
>   [   65.960664] RIP: 0010:states_equal+0x3ee/0x770
>   [   65.969559] Code: 33 85 ed 89 e8 41 0f 48 c7 83 e0 f8 89 e9 29 c1 48 63 c1 4c 89 e9 48 c1 e1 07 49 8d 14 08 0f
>                  b6 54 10 78 49 03 8a 58 05 00 00 <3a> 54 08 78 0f 85 60 03 00 00 49 c1 e5 07 43 8b 44 28 70 83 e0 03
>   [   66.007120] RSP: 0018:ffffc9000ebeb8b8 EFLAGS: 00010202
>   [   66.017570] RAX: 0000000000000000 RBX: ffff888149719680 RCX: 0000000000000010
>   [   66.031843] RDX: 0000000000000000 RSI: ffff88907f4e0c08 RDI: ffff8881572f0000
>   [   66.046115] RBP: 0000000000000000 R08: ffff8883d5014000 R09: ffffffff83065d50
>   [   66.060386] R10: ffff8881bf9a1800 R11: 0000000000000002 R12: 0000000000000000
>   [   66.074659] R13: 0000000000000000 R14: ffff888149719a40 R15: 0000000000000007
>   [   66.088932] FS:  00007f5d5da96800(0000) GS:ffff88907f4c0000(0000) knlGS:0000000000000000
>   [   66.105114] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
>   [   66.116606] CR2: 0000000000000088 CR3: 0000000388261001 CR4: 00000000007706f0
>   [   66.130873] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
>   [   66.145145] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
>   [   66.159416] PKRU: 55555554
>   [   66.164823] Call Trace:
>   [   66.169709]  <TASK>
>   [   66.173906]  ? __die_body+0x66/0xb0
>   [   66.180890]  ? page_fault_oops+0x370/0x3d0
>   [   66.189082]  ? console_unlock+0xb5/0x140
>   [   66.196926]  ? exc_page_fault+0x4f/0xb0
>   [   66.204597]  ? asm_exc_page_fault+0x22/0x30
>   [   66.212974]  ? states_equal+0x3ee/0x770
>   [   66.220643]  ? states_equal+0x529/0x770
>   [   66.228312]  do_check+0x60f/0x5240
>   [   66.235114]  do_check_common+0x388/0x840
>   [   66.242960]  do_check_subprogs+0x101/0x150
>   [   66.251150]  bpf_check+0x5d5/0x4b60
>   [   66.258134]  ? __mod_memcg_state+0x79/0x110
>   [   66.266506]  ? pcpu_alloc+0x892/0xba0
>   [   66.273829]  bpf_prog_load+0x5bb/0x660
>   [   66.281324]  ? bpf_prog_bind_map+0x1e1/0x290
>   [   66.289862]  __sys_bpf+0x29d/0x3a0
>   [   66.296664]  __x64_sys_bpf+0x18/0x20
>   [   66.303811]  do_syscall_64+0x6a/0x140
>   [   66.311133]  entry_SYSCALL_64_after_hwframe+0x4b/0x53
> 
> Forther investigation shows that the crash is due to invalid memory access in stacksafe().
> More specifically, it is the following code:
> 
>     if (exact != NOT_EXACT &&
>         old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>         cur->stack[spi].slot_type[i % BPF_REG_SIZE])
>             return false;
> 
> If cur->allocated_stack is 0, cur->stack will be a ZERO_SIZE_PTR. If this happens,
> cur->stack[spi].slot_type[i % BPF_REG_SIZE] will crash the kernel as the memory
> address is illegal. This is exactly what happened in the above crash dump.
> If cur->allocated_stack is not 0, the above code could trigger array out-of-bound
> access.
> 
> The patch added a condition 'i < cur->allocated_stack' to ensure
> cur->stack[spi].slot_type[i % BPF_REG_SIZE] memory access always legal.
> 
> Fixes: 2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks")
> Cc: Eduard Zingerman <eddyz87@gmail.com>
> Reported-by: Daniel Hodges <hodgesd@meta.com>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---

My bad, for some reason I thought that 'if (i >= cur->allocated_stack) return false;'
check below would be sufficient. (Which is obviously not true, sigh...).

Acked-by: Eduard Zingerman <eddyz87@gmail.com>


[...]

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Alexei Starovoitov]

On Mon, Aug 12, 2024 at 10:38 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sun, 2024-08-11 at 22:21 -0700, Yonghong Song wrote:
> > Daniel Hodges reported a kernel verifier crash when playing with sched-ext.
> > The crash dump looks like below:
> >
> >   [   65.874474] BUG: kernel NULL pointer dereference, address: 0000000000000088
> >   [   65.888406] #PF: supervisor read access in kernel mode
> >   [   65.898682] #PF: error_code(0x0000) - not-present page
> >   [   65.908957] PGD 0 P4D 0
> >   [   65.914020] Oops: 0000 [#1] SMP
> >   [   65.920300] CPU: 19 PID: 9364 Comm: scx_layered Kdump: loaded Tainted: G S          E      6.9.5-g93cea04637ea-dirty #7
> >   [   65.941874] Hardware name: Quanta Delta Lake MP 29F0EMA01D0/Delta Lake-Class1, BIOS F0E_3A19 04/27/2023
> >   [   65.960664] RIP: 0010:states_equal+0x3ee/0x770
> >   [   65.969559] Code: 33 85 ed 89 e8 41 0f 48 c7 83 e0 f8 89 e9 29 c1 48 63 c1 4c 89 e9 48 c1 e1 07 49 8d 14 08 0f
> >                  b6 54 10 78 49 03 8a 58 05 00 00 <3a> 54 08 78 0f 85 60 03 00 00 49 c1 e5 07 43 8b 44 28 70 83 e0 03
> >   [   66.007120] RSP: 0018:ffffc9000ebeb8b8 EFLAGS: 00010202
> >   [   66.017570] RAX: 0000000000000000 RBX: ffff888149719680 RCX: 0000000000000010
> >   [   66.031843] RDX: 0000000000000000 RSI: ffff88907f4e0c08 RDI: ffff8881572f0000
> >   [   66.046115] RBP: 0000000000000000 R08: ffff8883d5014000 R09: ffffffff83065d50
> >   [   66.060386] R10: ffff8881bf9a1800 R11: 0000000000000002 R12: 0000000000000000
> >   [   66.074659] R13: 0000000000000000 R14: ffff888149719a40 R15: 0000000000000007
> >   [   66.088932] FS:  00007f5d5da96800(0000) GS:ffff88907f4c0000(0000) knlGS:0000000000000000
> >   [   66.105114] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
> >   [   66.116606] CR2: 0000000000000088 CR3: 0000000388261001 CR4: 00000000007706f0
> >   [   66.130873] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
> >   [   66.145145] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
> >   [   66.159416] PKRU: 55555554
> >   [   66.164823] Call Trace:
> >   [   66.169709]  <TASK>
> >   [   66.173906]  ? __die_body+0x66/0xb0
> >   [   66.180890]  ? page_fault_oops+0x370/0x3d0
> >   [   66.189082]  ? console_unlock+0xb5/0x140
> >   [   66.196926]  ? exc_page_fault+0x4f/0xb0
> >   [   66.204597]  ? asm_exc_page_fault+0x22/0x30
> >   [   66.212974]  ? states_equal+0x3ee/0x770
> >   [   66.220643]  ? states_equal+0x529/0x770
> >   [   66.228312]  do_check+0x60f/0x5240
> >   [   66.235114]  do_check_common+0x388/0x840
> >   [   66.242960]  do_check_subprogs+0x101/0x150
> >   [   66.251150]  bpf_check+0x5d5/0x4b60
> >   [   66.258134]  ? __mod_memcg_state+0x79/0x110
> >   [   66.266506]  ? pcpu_alloc+0x892/0xba0
> >   [   66.273829]  bpf_prog_load+0x5bb/0x660
> >   [   66.281324]  ? bpf_prog_bind_map+0x1e1/0x290
> >   [   66.289862]  __sys_bpf+0x29d/0x3a0
> >   [   66.296664]  __x64_sys_bpf+0x18/0x20
> >   [   66.303811]  do_syscall_64+0x6a/0x140
> >   [   66.311133]  entry_SYSCALL_64_after_hwframe+0x4b/0x53
> >
> > Forther investigation shows that the crash is due to invalid memory access in stacksafe().
> > More specifically, it is the following code:
> >
> >     if (exact != NOT_EXACT &&
> >         old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
> >         cur->stack[spi].slot_type[i % BPF_REG_SIZE])
> >             return false;
> >
> > If cur->allocated_stack is 0, cur->stack will be a ZERO_SIZE_PTR. If this happens,
> > cur->stack[spi].slot_type[i % BPF_REG_SIZE] will crash the kernel as the memory
> > address is illegal. This is exactly what happened in the above crash dump.
> > If cur->allocated_stack is not 0, the above code could trigger array out-of-bound
> > access.
> >
> > The patch added a condition 'i < cur->allocated_stack' to ensure
> > cur->stack[spi].slot_type[i % BPF_REG_SIZE] memory access always legal.
> >
> > Fixes: 2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks")
> > Cc: Eduard Zingerman <eddyz87@gmail.com>
> > Reported-by: Daniel Hodges <hodgesd@meta.com>
> > Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> > ---
>
> My bad, for some reason I thought that 'if (i >= cur->allocated_stack) return false;'
> check below would be sufficient. (Which is obviously not true, sigh...).
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>

Should we move the check up instead?

if (i >= cur->allocated_stack)
          return false;

Checking it twice looks odd.

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Eduard Zingerman]

On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:

[...]

> Should we move the check up instead?
> 
> if (i >= cur->allocated_stack)
>           return false;
> 
> Checking it twice looks odd.

A few checks before that, namely:

		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
		    && exact == NOT_EXACT) {
			i += BPF_REG_SIZE - 1;
			/* explored state didn't use this */
			continue;
		}

		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;

Should be done regardless cur->allocated_stack.

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Alexei Starovoitov]

On Mon, Aug 12, 2024 at 10:47 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
>
> [...]
>
> > Should we move the check up instead?
> >
> > if (i >= cur->allocated_stack)
> >           return false;
> >
> > Checking it twice looks odd.
>
> A few checks before that, namely:
>
>                 if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
>                     && exact == NOT_EXACT) {
>                         i += BPF_REG_SIZE - 1;
>                         /* explored state didn't use this */
>                         continue;
>                 }
>
>                 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;
>
> Should be done regardless cur->allocated_stack.

Right, but then let's sink old->slot_type != cur->slot_type down?

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Eduard Zingerman]

On Mon, 2024-08-12 at 10:50 -0700, Alexei Starovoitov wrote:
> On Mon, Aug 12, 2024 at 10:47 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
> > 
> > [...]
> > 
> > > Should we move the check up instead?
> > > 
> > > if (i >= cur->allocated_stack)
> > >           return false;
> > > 
> > > Checking it twice looks odd.
> > 
> > A few checks before that, namely:
> > 
> >                 if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
> >                     && exact == NOT_EXACT) {
> >                         i += BPF_REG_SIZE - 1;
> >                         /* explored state didn't use this */
> >                         continue;
> >                 }
> > 
> >                 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;
> > 
> > Should be done regardless cur->allocated_stack.
> 
> Right, but then let's sink old->slot_type != cur->slot_type down?

It does not seem correct to swap the order for these two checks:

		if (exact != NOT_EXACT && i < cur->allocated_stack &&
		    old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
		    cur->stack[spi].slot_type[i % BPF_REG_SIZE])
			return false;

		if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
		    && exact == NOT_EXACT) {
			i += BPF_REG_SIZE - 1;
			/* explored state didn't use this */
			continue;
		}

if we do, 'slot_type' won't be checked for 'cur' when 'old' register is not marked live.

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Yonghong Song]

On 8/12/24 10:50 AM, Alexei Starovoitov wrote:
> On Mon, Aug 12, 2024 at 10:47 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>> On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
>>
>> [...]
>>
>>> Should we move the check up instead?
>>>
>>> if (i >= cur->allocated_stack)
>>>            return false;
>>>
>>> Checking it twice looks odd.
>> A few checks before that, namely:
>>
>>                  if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
>>                      && exact == NOT_EXACT) {
>>                          i += BPF_REG_SIZE - 1;
>>                          /* explored state didn't use this */
>>                          continue;
>>                  }
>>
>>                  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;
>>
>> Should be done regardless cur->allocated_stack.
> Right, but then let's sink old->slot_type != cur->slot_type down?

We could do the following to avoid double comparison: diff --git 
a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 
df3be12096cf..1906798f1a3d 100644 --- a/kernel/bpf/verifier.c +++ 
b/kernel/bpf/verifier.c @@ -17338,10 +17338,13 @@ static bool 
stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, */ 
for (i = 0; i < old->allocated_stack; i++) { struct bpf_reg_state 
*old_reg, *cur_reg; + bool cur_exceed_bound; spi = i / BPF_REG_SIZE; - 
if (exact != NOT_EXACT && + cur_exceed_bound = i >= 
cur->allocated_stack; + + if (exact != NOT_EXACT && !cur_exceed_bound && 
old->stack[spi].slot_type[i % BPF_REG_SIZE] != 
cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; @@ -17363,7 
+17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct 
bpf_func_state *old, /* explored stack has more populated slots than 
current stack * and these slots were used */ - if (i >= 
cur->allocated_stack) + if (cur_exceed_bound) return false; /* 64-bit 
scalar spill vs all slots MISC and vice versa. WDYT?

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Eduard Zingerman]

On Mon, 2024-08-12 at 11:26 -0700, Yonghong Song wrote:

[...]

> 
> We could do the following to avoid double comparison: diff --git 
> a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 
> df3be12096cf..1906798f1a3d 100644 --- a/kernel/bpf/verifier.c +++ 
> b/kernel/bpf/verifier.c @@ -17338,10 +17338,13 @@ static bool 
> stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, */ 
> for (i = 0; i < old->allocated_stack; i++) { struct bpf_reg_state 
> *old_reg, *cur_reg; + bool cur_exceed_bound; spi = i / BPF_REG_SIZE; - 
> if (exact != NOT_EXACT && + cur_exceed_bound = i >= 
> cur->allocated_stack; + + if (exact != NOT_EXACT && !cur_exceed_bound && 
> old->stack[spi].slot_type[i % BPF_REG_SIZE] != 
> cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; @@ -17363,7 
> +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct 
> bpf_func_state *old, /* explored stack has more populated slots than 
> current stack * and these slots were used */ - if (i >= 
> cur->allocated_stack) + if (cur_exceed_bound) return false; /* 64-bit 
> scalar spill vs all slots MISC and vice versa. WDYT?
> 

Yonghong, something went wrong with formatting of the above email,
could you please resend?

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Yonghong Song]

On 8/12/24 11:30 AM, Eduard Zingerman wrote:
> On Mon, 2024-08-12 at 11:26 -0700, Yonghong Song wrote:
>
> [...]
>
>> We could do the following to avoid double comparison: diff --git
>> a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index
>> df3be12096cf..1906798f1a3d 100644 --- a/kernel/bpf/verifier.c +++
>> b/kernel/bpf/verifier.c @@ -17338,10 +17338,13 @@ static bool
>> stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, */
>> for (i = 0; i < old->allocated_stack; i++) { struct bpf_reg_state
>> *old_reg, *cur_reg; + bool cur_exceed_bound; spi = i / BPF_REG_SIZE; -
>> if (exact != NOT_EXACT && + cur_exceed_bound = i >=
>> cur->allocated_stack; + + if (exact != NOT_EXACT && !cur_exceed_bound &&
>> old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>> cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; @@ -17363,7
>> +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct
>> bpf_func_state *old, /* explored stack has more populated slots than
>> current stack * and these slots were used */ - if (i >=
>> cur->allocated_stack) + if (cur_exceed_bound) return false; /* 64-bit
>> scalar spill vs all slots MISC and vice versa. WDYT?
>>
> Yonghong, something went wrong with formatting of the above email,
> could you please resend?

Sorry, I copy-paste from 'git diff' result to my email window. Not sure
why it caused the format issue after I sent out. Anyway, the following
is the patch I suggested:

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index df3be12096cf..1906798f1a3d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
          */
         for (i = 0; i < old->allocated_stack; i++) {
                 struct bpf_reg_state *old_reg, *cur_reg;
+               bool cur_exceed_bound;
  
                 spi = i / BPF_REG_SIZE;
  
-               if (exact != NOT_EXACT &&
+               cur_exceed_bound = i >= cur->allocated_stack;
+
+               if (exact != NOT_EXACT && !cur_exceed_bound &&
                     old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
                     cur->stack[spi].slot_type[i % BPF_REG_SIZE])
                         return false;
@@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
                 /* explored stack has more populated slots than current stack
                  * and these slots were used
                  */
-               if (i >= cur->allocated_stack)
+               if (cur_exceed_bound)
                         return false;
  
                 /* 64-bit scalar spill vs all slots MISC and vice versa.

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Eduard Zingerman]

On Mon, 2024-08-12 at 11:36 -0700, Yonghong Song wrote:

[...]

> Sorry, I copy-paste from 'git diff' result to my email window. Not sure
> why it caused the format issue after I sent out.

Sure, no problem

> Anyway, the following is the patch I suggested:
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index df3be12096cf..1906798f1a3d 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
>           */
>          for (i = 0; i < old->allocated_stack; i++) {
>                  struct bpf_reg_state *old_reg, *cur_reg;
> +               bool cur_exceed_bound;
>   
>                  spi = i / BPF_REG_SIZE;
>   
> -               if (exact != NOT_EXACT &&
> +               cur_exceed_bound = i >= cur->allocated_stack;

idk, I think C compiler would do this anyways,
to me the code is fine both with and without this additional variable.

> +
> +               if (exact != NOT_EXACT && !cur_exceed_bound &&
>                      old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>                      cur->stack[spi].slot_type[i % BPF_REG_SIZE])
>                          return false;
> @@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
>                  /* explored stack has more populated slots than current stack
>                   * and these slots were used
>                   */
> -               if (i >= cur->allocated_stack)
> +               if (cur_exceed_bound)
>                          return false;
>   
>                  /* 64-bit scalar spill vs all slots MISC and vice versa.
> 

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Yonghong Song]

On 8/12/24 11:41 AM, Eduard Zingerman wrote:
> On Mon, 2024-08-12 at 11:36 -0700, Yonghong Song wrote:
>
> [...]
>
>> Sorry, I copy-paste from 'git diff' result to my email window. Not sure
>> why it caused the format issue after I sent out.
> Sure, no problem
>
>> Anyway, the following is the patch I suggested:
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index df3be12096cf..1906798f1a3d 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
>>            */
>>           for (i = 0; i < old->allocated_stack; i++) {
>>                   struct bpf_reg_state *old_reg, *cur_reg;
>> +               bool cur_exceed_bound;
>>    
>>                   spi = i / BPF_REG_SIZE;
>>    
>> -               if (exact != NOT_EXACT &&
>> +               cur_exceed_bound = i >= cur->allocated_stack;
> idk, I think C compiler would do this anyways,
> to me the code is fine both with and without this additional variable.

Okay, I will keep the original (simpler) patch then.

>
>> +
>> +               if (exact != NOT_EXACT && !cur_exceed_bound &&
>>                       old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>>                       cur->stack[spi].slot_type[i % BPF_REG_SIZE])
>>                           return false;
>> @@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
>>                   /* explored stack has more populated slots than current stack
>>                    * and these slots were used
>>                    */
>> -               if (i >= cur->allocated_stack)
>> +               if (cur_exceed_bound)
>>                           return false;
>>    
>>                   /* 64-bit scalar spill vs all slots MISC and vice versa.
>>
>

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Alexei Starovoitov]

On Mon, Aug 12, 2024 at 10:57 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-08-12 at 10:50 -0700, Alexei Starovoitov wrote:
> > On Mon, Aug 12, 2024 at 10:47 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
> > >
> > > [...]
> > >
> > > > Should we move the check up instead?
> > > >
> > > > if (i >= cur->allocated_stack)
> > > >           return false;
> > > >
> > > > Checking it twice looks odd.
> > >
> > > A few checks before that, namely:
> > >
> > >                 if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
> > >                     && exact == NOT_EXACT) {
> > >                         i += BPF_REG_SIZE - 1;
> > >                         /* explored state didn't use this */
> > >                         continue;
> > >                 }
> > >
> > >                 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;
> > >
> > > Should be done regardless cur->allocated_stack.
> >
> > Right, but then let's sink old->slot_type != cur->slot_type down?
>
> It does not seem correct to swap the order for these two checks:
>
>                 if (exact != NOT_EXACT && i < cur->allocated_stack &&
>                     old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>                     cur->stack[spi].slot_type[i % BPF_REG_SIZE])
>                         return false;
>
>                 if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
>                     && exact == NOT_EXACT) {
>                         i += BPF_REG_SIZE - 1;
>                         /* explored state didn't use this */
>                         continue;
>                 }
>
> if we do, 'slot_type' won't be checked for 'cur' when 'old' register is not marked live.

I see. This is to compare states in open coded iter loops when liveness
is not propagated yet, right?

Then when comparing for exact states we should probably do:
if (exact != NOT_EXACT &&
    (i >= cur->allocated_stack ||
     old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
     cur->stack[spi].slot_type[i % BPF_REG_SIZE]))
   return false;

?

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Eduard Zingerman]

On Mon, 2024-08-12 at 12:29 -0700, Alexei Starovoitov wrote:

[...]

> > It does not seem correct to swap the order for these two checks:
> > 
> >                 if (exact != NOT_EXACT && i < cur->allocated_stack &&
> >                     old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
> >                     cur->stack[spi].slot_type[i % BPF_REG_SIZE])
> >                         return false;
> > 
> >                 if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
> >                     && exact == NOT_EXACT) {
> >                         i += BPF_REG_SIZE - 1;
> >                         /* explored state didn't use this */
> >                         continue;
> >                 }
> > 
> > if we do, 'slot_type' won't be checked for 'cur' when 'old' register is not marked live.
> 
> I see. This is to compare states in open coded iter loops when liveness
> is not propagated yet, right?

Yes

> 
> Then when comparing for exact states we should probably do:
> if (exact != NOT_EXACT &&
>     (i >= cur->allocated_stack ||
>      old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>      cur->stack[spi].slot_type[i % BPF_REG_SIZE]))
>    return false;
> 
> ?

Hm, right, otherwise the old slots in the interval
[cur->allocated_stack..old->allocated_stack)
won't be checked using exact rules.

Re: [PATCH bpf 1/2] bpf: Fix a kernel verifier crash in stacksafe()

[Yonghong Song]

On 8/12/24 12:43 PM, Eduard Zingerman wrote:
> On Mon, 2024-08-12 at 12:29 -0700, Alexei Starovoitov wrote:
>
> [...]
>
>>> It does not seem correct to swap the order for these two checks:
>>>
>>>                  if (exact != NOT_EXACT && i < cur->allocated_stack &&
>>>                      old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>>>                      cur->stack[spi].slot_type[i % BPF_REG_SIZE])
>>>                          return false;
>>>
>>>                  if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
>>>                      && exact == NOT_EXACT) {
>>>                          i += BPF_REG_SIZE - 1;
>>>                          /* explored state didn't use this */
>>>                          continue;
>>>                  }
>>>
>>> if we do, 'slot_type' won't be checked for 'cur' when 'old' register is not marked live.
>> I see. This is to compare states in open coded iter loops when liveness
>> is not propagated yet, right?
> Yes
>
>> Then when comparing for exact states we should probably do:
>> if (exact != NOT_EXACT &&
>>      (i >= cur->allocated_stack ||
>>       old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>>       cur->stack[spi].slot_type[i % BPF_REG_SIZE]))
>>     return false;
>>
>> ?
> Hm, right, otherwise the old slots in the interval
> [cur->allocated_stack..old->allocated_stack)
> won't be checked using exact rules.

Okay, for *exact* stack slot_type comparison. Will make the change
and send v2 soon.