diff mbox series

[RFC,bpf-next,v2,3/3] selftests/bpf: add more verifier tests for signed range deduction of BPF_AND

Message ID 20241119114023.397450-4-shung-hsi.yu@suse.com (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series Improve signed ranges reasoning for BPF_AND | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-15 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-16 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-17 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-25 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-32 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-33 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17-O2
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18-O2
bpf/vmtest-bpf-next-VM_Test-34 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-40 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-41 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-PR fail PR summary
bpf/vmtest-bpf-next-VM_Test-38 fail Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-37 fail Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-8 fail Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 fail Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-13 fail Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 fail Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 fail Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 fail Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-7 fail Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-31 fail Logs for x86_64-llvm-17 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-39 fail Logs for x86_64-llvm-18 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-18
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf-next
netdev/ynl success Generated files up to date; no warnings/errors; no diff in generated;
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 3 this patch: 3
netdev/build_tools success Errors and warnings before: 0 (+0) this patch: 0 (+0)
netdev/cc_maintainers warning 10 maintainers not CCed: kpsingh@kernel.org jolsa@kernel.org shuah@kernel.org song@kernel.org haoluo@google.com yonghong.song@linux.dev martin.lau@linux.dev linux-kselftest@vger.kernel.org mykolal@fb.com sdf@fomichev.me
netdev/build_clang success Errors and warnings before: 3 this patch: 3
netdev/verify_signedoff fail author Signed-off-by missing
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 3 this patch: 3
netdev/checkpatch warning WARNING: Avoid line continuations in quoted strings
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0

Commit Message

Shung-Hsi Yu Nov. 19, 2024, 11:40 a.m. UTC 
Add more specific test cases into verifier_and.c to test against signed
range deduction.

WIP, Test failing.
---
The GitHub action is at https://github.com/kernel-patches/bpf/actions/runs/11909088689/

For and_mixed_range_vs_neg_const()

  Error: #432/8 verifier_and/[-1,0] range vs negative constant @unpriv
  ...
  VERIFIER LOG:
  =============
  0: R1=ctx() R10=fp0
  0: (85) call bpf_get_prandom_u32#7    ; R0_w=Pscalar()
  1: (67) r0 <<= 63                     ; R0_w=Pscalar(smax=smax32=umax32=0,umax=0x8000000000000000,smin32=0,var_off=(0x0; 0x8000000000000000))
  2: (c7) r0 s>>= 63                    ; R0_w=Pscalar(smin=smin32=-1,smax=smax32=0)
  3: (b7) r1 = -13                      ; R1_w=P-13
  4: (5f) r0 &= r1                      ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R1_w=P-13
  5: (b7) r2 = 0                        ; R2_w=P0
  6: (6d) if r0 s> r2 goto pc+4         ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R2_w=P0
  7: (b7) r2 = -16                      ; R2=P-16
  8: (cd) if r0 s< r2 goto pc+2 11: R0=Pscalar() R1=P-13 R2=Pscalar() R10=fp0

	Somehow despite the verifier knows that r0's smin=-16 and smax=0,
	and r2's smin=-16 and smax=-16, it does determine that
	[-16, 0] s< -16 is always false.

  11: (61) r1 = *(u32 *)(r1 +0)
  R1 invalid mem access 'scalar'

Felt like this is something obvious, but I just couldn't see where the
problem lies.

---
 .../selftests/bpf/progs/verifier_and.c        | 56 +++++++++++++++++++
 1 file changed, 56 insertions(+)

Comments

Shung-Hsi Yu Nov. 19, 2024, 11:44 a.m. UTC | #1 
On Tue, Nov 19, 2024 at 07:40:21PM GMT, Shung-Hsi Yu wrote:
> Add more specific test cases into verifier_and.c to test against signed
> range deduction.
> 
> WIP, Test failing.
> ---
> The GitHub action is at https://github.com/kernel-patches/bpf/actions/runs/11909088689/
> 
> For and_mixed_range_vs_neg_const()
> 
>   Error: #432/8 verifier_and/[-1,0] range vs negative constant @unpriv
>   ...
>   VERIFIER LOG:
>   =============
>   0: R1=ctx() R10=fp0
>   0: (85) call bpf_get_prandom_u32#7    ; R0_w=Pscalar()
>   1: (67) r0 <<= 63                     ; R0_w=Pscalar(smax=smax32=umax32=0,umax=0x8000000000000000,smin32=0,var_off=(0x0; 0x8000000000000000))
>   2: (c7) r0 s>>= 63                    ; R0_w=Pscalar(smin=smin32=-1,smax=smax32=0)
>   3: (b7) r1 = -13                      ; R1_w=P-13
>   4: (5f) r0 &= r1                      ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R1_w=P-13
>   5: (b7) r2 = 0                        ; R2_w=P0
>   6: (6d) if r0 s> r2 goto pc+4         ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R2_w=P0
>   7: (b7) r2 = -16                      ; R2=P-16
>   8: (cd) if r0 s< r2 goto pc+2 11: R0=Pscalar() R1=P-13 R2=Pscalar() R10=fp0
> 
> 	Somehow despite the verifier knows that r0's smin=-16 and smax=0,
> 	and r2's smin=-16 and smax=-16, it does determine that
                                typo here  ^ 
                                          not
> 	[-16, 0] s< -16 is always false.
> 
>   11: (61) r1 = *(u32 *)(r1 +0)
>   R1 invalid mem access 'scalar'
> 
> Felt like this is something obvious, but I just couldn't see where the
> problem lies.
...
Xu Kuohai Nov. 20, 2024, 12:15 p.m. UTC | #2 
On 11/19/2024 7:40 PM, Shung-Hsi Yu wrote:
> Add more specific test cases into verifier_and.c to test against signed
> range deduction.
> 
> WIP, Test failing.
> ---
> The GitHub action is at https://github.com/kernel-patches/bpf/actions/runs/11909088689/
> 
> For and_mixed_range_vs_neg_const()
> 
>    Error: #432/8 verifier_and/[-1,0] range vs negative constant @unpriv
>    ...
>    VERIFIER LOG:
>    =============
>    0: R1=ctx() R10=fp0
>    0: (85) call bpf_get_prandom_u32#7    ; R0_w=Pscalar()
>    1: (67) r0 <<= 63                     ; R0_w=Pscalar(smax=smax32=umax32=0,umax=0x8000000000000000,smin32=0,var_off=(0x0; 0x8000000000000000))
>    2: (c7) r0 s>>= 63                    ; R0_w=Pscalar(smin=smin32=-1,smax=smax32=0)
>    3: (b7) r1 = -13                      ; R1_w=P-13
>    4: (5f) r0 &= r1                      ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R1_w=P-13
>    5: (b7) r2 = 0                        ; R2_w=P0
>    6: (6d) if r0 s> r2 goto pc+4         ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R2_w=P0
>    7: (b7) r2 = -16                      ; R2=P-16
>    8: (cd) if r0 s< r2 goto pc+2 11: R0=Pscalar() R1=P-13 R2=Pscalar() R10=fp0
> 
> 	Somehow despite the verifier knows that r0's smin=-16 and smax=0,
> 	and r2's smin=-16 and smax=-16, it does determine that
> 	[-16, 0] s< -16 is always false.
> 
>    11: (61) r1 = *(u32 *)(r1 +0)
>    R1 invalid mem access 'scalar'
>

Interesting, CI reported failure in unpriv test, while the priv
test ran well. It seems to be related to some security policy.
I think it is bypass_spec_v1, which makes the verifier to check
the unreachable target instruction.
Alexei Starovoitov Nov. 20, 2024, 7:38 p.m. UTC | #3 
On Wed, Nov 20, 2024 at 4:16 AM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
>
> On 11/19/2024 7:40 PM, Shung-Hsi Yu wrote:
> > Add more specific test cases into verifier_and.c to test against signed
> > range deduction.
> >
> > WIP, Test failing.
> > ---
> > The GitHub action is at https://github.com/kernel-patches/bpf/actions/runs/11909088689/
> >
> > For and_mixed_range_vs_neg_const()
> >
> >    Error: #432/8 verifier_and/[-1,0] range vs negative constant @unpriv
> >    ...
> >    VERIFIER LOG:
> >    =============
> >    0: R1=ctx() R10=fp0
> >    0: (85) call bpf_get_prandom_u32#7    ; R0_w=Pscalar()
> >    1: (67) r0 <<= 63                     ; R0_w=Pscalar(smax=smax32=umax32=0,umax=0x8000000000000000,smin32=0,var_off=(0x0; 0x8000000000000000))
> >    2: (c7) r0 s>>= 63                    ; R0_w=Pscalar(smin=smin32=-1,smax=smax32=0)
> >    3: (b7) r1 = -13                      ; R1_w=P-13
> >    4: (5f) r0 &= r1                      ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R1_w=P-13
> >    5: (b7) r2 = 0                        ; R2_w=P0
> >    6: (6d) if r0 s> r2 goto pc+4         ; R0_w=Pscalar(smin=smin32=-16,smax=smax32=0,umax=0xfffffffffffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) R2_w=P0
> >    7: (b7) r2 = -16                      ; R2=P-16
> >    8: (cd) if r0 s< r2 goto pc+2 11: R0=Pscalar() R1=P-13 R2=Pscalar() R10=fp0
> >
> >       Somehow despite the verifier knows that r0's smin=-16 and smax=0,
> >       and r2's smin=-16 and smax=-16, it does determine that
> >       [-16, 0] s< -16 is always false.
> >
> >    11: (61) r1 = *(u32 *)(r1 +0)
> >    R1 invalid mem access 'scalar'
> >
>
> Interesting, CI reported failure in unpriv test, while the priv
> test ran well. It seems to be related to some security policy.
> I think it is bypass_spec_v1, which makes the verifier to check
> the unreachable target instruction.

Correct. See speculative path in the verifier.

The patch is missing SOB too.

pw-bot: cr
diff mbox series

Patch

diff --git a/tools/testing/selftests/bpf/progs/verifier_and.c b/tools/testing/selftests/bpf/progs/verifier_and.c
index e97e518516b6..56c362f99a21 100644
--- a/tools/testing/selftests/bpf/progs/verifier_and.c
+++ b/tools/testing/selftests/bpf/progs/verifier_and.c
@@ -104,4 +104,60 @@  l0_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("[-1,0] range vs negative constant")
+__success __success_unpriv __retval(0)
+__naked void and_mixed_range_vs_neg_const(void)
+{
+	/* Use ARSH with AND like compiler would */
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r0 <<= 63;					\
+	r0 s>>= 63; /* r0 = [-1, 0] */			\
+	r1 = -13;					\
+	r0 &= r1;					\
+	/* [-1, 0] & -13 give either -13 or 0. So	\
+	 * ideally this should be a tight range of	\
+	 * [-13, 0], but verifier is not advanced enough\
+	 * to deduce that. just knowing result is in	\
+	 * [-16, 0] is good enough.			\
+	 */                                             \
+	r2 = 0;						\
+	if r0 s> r2 goto l0_%=;				\
+	r2 = -16;					\
+	if r0 s< r2 goto l0_%=;				\
+	r0 = 0;						\
+	exit;						\
+l0_%=:  r1 = *(u32*)(r1 + 0);				\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("32-bit [-1,0] range vs negative constant")
+__success __success_unpriv __retval(0)
+__naked void and32_mixed_range_vs_neg_const(void)
+{
+	/* See and_mixed_range_vs_neg_const() */
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	w0 <<= 31;					\
+	w0 s>>= 31;					\
+	w1 = -13;					\
+	w0 &= w1;					\
+	w2 = 0;						\
+	if w0 s> w2 goto l0_%=;				\
+	w2 = -16;					\
+	if w0 s< w2 goto l0_%=;				\
+	r0 = 0;						\
+	exit;						\
+l0_%=:  r1 = *(u32*)(r1 + 0);				\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";