diff mbox series

[bpf-next,1/2] bpf: update 32-bit bounds when the lower 32-bit value is not wrapping

Message ID 20230307220449.2933650-2-xukuohai@huaweicloud.com (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series update 32-bit bounds when the lower 32-bit value is not wrapping | expand

Checks

Context Check Description
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf-next
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: 29 this patch: 29
netdev/cc_maintainers success CCed 12 of 12 maintainers
netdev/build_clang success Errors and warnings before: 20 this patch: 20
netdev/verify_signedoff success Signed-off-by tag matches author and committer
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: 29 this patch: 29
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 37 lines checked
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-7 success Logs for llvm-toolchain
bpf/vmtest-bpf-next-VM_Test-8 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-5 success Logs for build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-2 success Logs for build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-3 success Logs for build for aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-4 success Logs for build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-37 success Logs for test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for test_maps on aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-12 success Logs for test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-13 success Logs for test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-14 success Logs for test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for test_progs on aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-17 success Logs for test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-19 success Logs for test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for test_progs_no_alu32 on aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-22 success Logs for test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for test_progs_no_alu32 on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-24 success Logs for test_progs_no_alu32_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-25 success Logs for test_progs_no_alu32_parallel on aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-27 success Logs for test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for test_progs_no_alu32_parallel on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-29 success Logs for test_progs_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 success Logs for test_progs_parallel on aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-32 success Logs for test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-33 success Logs for test_progs_parallel on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-34 success Logs for test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-35 success Logs for test_verifier on aarch64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-38 success Logs for test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-26 success Logs for test_progs_no_alu32_parallel on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-36 success Logs for test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-16 success Logs for test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-31 success Logs for test_progs_parallel on s390x with gcc
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-11 success Logs for test_maps on s390x with gcc

Commit Message

Xu Kuohai March 7, 2023, 10:04 p.m. UTC 
The following XDP prog is accepted by verifier.

0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
2: (bf) r1 = r2
3: (07) r1 += 1
4: (2d) if r1 > r3 goto pc+6
5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
6: (b4) w0 = 0x7fffff10
7: (0c) w1 += w0                      ; R1_w=scalar(umin=0x7fffff10,umax=0x8000000f,var_off=(0x0; 0xffffffff))
8: (b4) w0 = 0x80000000
9: (04) w0 += 1
10: (ae) if w0 < w1 goto pc-2
11: (b7) r0 = 0
12: (95) exit

while the following 64-bit version is rejected.

0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
2: (bf) r1 = r2
3: (07) r1 += 1
4: (2d) if r1 > r3 goto pc+8
5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
6: (18) r0 = 0x7fffffffffffff10
8: (0f) r1 += r0                      ; R1_w=scalar(umin=0x7fffffffffffff10,umax=0x800000000000000f)
9: (18) r0 = 0x8000000000000000
11: (07) r0 += 1
12: (ad) if r0 < r1 goto pc-2
13: (b7) r0 = 0
14: (95) exit

The verifier log says:

[...]

from 12 to 11: R0_w=-9223372036854775794 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
11: (07) r0 += 1                      ; R0_w=-9223372036854775793
12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
13: safe

from 12 to 11: R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
11: (07) r0 += 1                      ; R0_w=-9223372036854775792
12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775792 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
13: safe

[...]

The loop crosses termination condition r0 == r1.umax, and does not stop.

The reason is that when the verifier enumerates to r1.umin == r1.umax, the value
0x800000000000000f of r1.umin is greater than U32_MAX, so __reg_combine_64_into_32
sets the u32 range of r1 to [0, U32_MAX] instead of marking r1 as a constant,
making is_branch_taken() in check_cond_jmp_op() be skipped.

To fix it, update 32-bit bounds when the lower 32-bit value is not wrapping,
even if the 64-bit value is beyond the range of [0, U32_MAX] or [S32_MIN, S32_MAX].

Signed-off-by: Xu Kuohai <xukuohai@huaweicloud.com>
---
 kernel/bpf/verifier.c | 27 +++++++++++----------------
 1 file changed, 11 insertions(+), 16 deletions(-)

Comments

Xu Kuohai March 7, 2023, 9:21 a.m. UTC | #1 
On 3/8/2023 6:04 AM, Xu Kuohai wrote:
> The following XDP prog is accepted by verifier.
> 
> 0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
> 1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
> 2: (bf) r1 = r2
> 3: (07) r1 += 1
> 4: (2d) if r1 > r3 goto pc+6
> 5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
> 6: (b4) w0 = 0x7fffff10
> 7: (0c) w1 += w0                      ; R1_w=scalar(umin=0x7fffff10,umax=0x8000000f,var_off=(0x0; 0xffffffff))
> 8: (b4) w0 = 0x80000000
> 9: (04) w0 += 1
> 10: (ae) if w0 < w1 goto pc-2
> 11: (b7) r0 = 0
> 12: (95) exit
> 
> while the following 64-bit version is rejected.
> 
> 0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
> 1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
> 2: (bf) r1 = r2
> 3: (07) r1 += 1
> 4: (2d) if r1 > r3 goto pc+8
> 5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
> 6: (18) r0 = 0x7fffffffffffff10
> 8: (0f) r1 += r0                      ; R1_w=scalar(umin=0x7fffffffffffff10,umax=0x800000000000000f)
> 9: (18) r0 = 0x8000000000000000
> 11: (07) r0 += 1
> 12: (ad) if r0 < r1 goto pc-2
> 13: (b7) r0 = 0
> 14: (95) exit
> 
> The verifier log says:
> 
> [...]
> 
> from 12 to 11: R0_w=-9223372036854775794 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 11: (07) r0 += 1                      ; R0_w=-9223372036854775793
> 12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 13: safe
> 
> from 12 to 11: R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 11: (07) r0 += 1                      ; R0_w=-9223372036854775792
> 12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775792 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 13: safe
> 
> [...]
> 
> The loop crosses termination condition r0 == r1.umax, and does not stop.
> 
> The reason is that when the verifier enumerates to r1.umin == r1.umax, the value
> 0x800000000000000f of r1.umin is greater than U32_MAX, so __reg_combine_64_into_32
> sets the u32 range of r1 to [0, U32_MAX] instead of marking r1 as a constant,
> making is_branch_taken() in check_cond_jmp_op() be skipped.
> 
> To fix it, update 32-bit bounds when the lower 32-bit value is not wrapping,
> even if the 64-bit value is beyond the range of [0, U32_MAX] or [S32_MIN, S32_MAX].
> 
> Signed-off-by: Xu Kuohai <xukuohai@huaweicloud.com>

Oops, missing fixes tag, will resend

> ---
>   kernel/bpf/verifier.c | 27 +++++++++++----------------
>   1 file changed, 11 insertions(+), 16 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b2116ca78d9a..64c9ee3857ec 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2013,26 +2013,21 @@ static void __reg_combine_32_into_64(struct bpf_reg_state *reg)
>   	reg_bounds_sync(reg);
>   }
>   
> -static bool __reg64_bound_s32(s64 a)
> -{
> -	return a >= S32_MIN && a <= S32_MAX;
> -}
> -
> -static bool __reg64_bound_u32(u64 a)
> -{
> -	return a >= U32_MIN && a <= U32_MAX;
> -}
> -
>   static void __reg_combine_64_into_32(struct bpf_reg_state *reg)
>   {
> +	s64 smin = reg->smin_value;
> +	s64 smax = reg->smax_value;
> +	u64 umin = reg->umin_value;
> +	u64 umax = reg->umax_value;
> +
>   	__mark_reg32_unbounded(reg);
> -	if (__reg64_bound_s32(reg->smin_value) && __reg64_bound_s32(reg->smax_value)) {
> -		reg->s32_min_value = (s32)reg->smin_value;
> -		reg->s32_max_value = (s32)reg->smax_value;
> +	if ((u64)(smax - smin) <= (u64)U32_MAX && (s32)smin <= (s32)smax) {
> +		reg->s32_min_value = (s32)smin;
> +		reg->s32_max_value = (s32)smax;
>   	}
> -	if (__reg64_bound_u32(reg->umin_value) && __reg64_bound_u32(reg->umax_value)) {
> -		reg->u32_min_value = (u32)reg->umin_value;
> -		reg->u32_max_value = (u32)reg->umax_value;
> +	if (umax - umin <= U32_MAX && (u32)umin <= (u32)umax) {
> +		reg->u32_min_value = (u32)umin;
> +		reg->u32_max_value = (u32)umax;
>   	}
>   	reg_bounds_sync(reg);
>   }
Alexei Starovoitov March 7, 2023, 5:22 p.m. UTC | #2 
On Tue, Mar 7, 2023 at 1:05 AM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
>
> The following XDP prog is accepted by verifier.
>
> 0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
> 1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
> 2: (bf) r1 = r2
> 3: (07) r1 += 1
> 4: (2d) if r1 > r3 goto pc+6
> 5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
> 6: (b4) w0 = 0x7fffff10
> 7: (0c) w1 += w0                      ; R1_w=scalar(umin=0x7fffff10,umax=0x8000000f,var_off=(0x0; 0xffffffff))
> 8: (b4) w0 = 0x80000000
> 9: (04) w0 += 1
> 10: (ae) if w0 < w1 goto pc-2
> 11: (b7) r0 = 0
> 12: (95) exit
>
> while the following 64-bit version is rejected.
>
> 0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
> 1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
> 2: (bf) r1 = r2
> 3: (07) r1 += 1
> 4: (2d) if r1 > r3 goto pc+8
> 5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
> 6: (18) r0 = 0x7fffffffffffff10
> 8: (0f) r1 += r0                      ; R1_w=scalar(umin=0x7fffffffffffff10,umax=0x800000000000000f)
> 9: (18) r0 = 0x8000000000000000
> 11: (07) r0 += 1
> 12: (ad) if r0 < r1 goto pc-2
> 13: (b7) r0 = 0
> 14: (95) exit

These two programs are not equivalent.
Not clear how apples to oranges comparison explains anything.

> The verifier log says:
>
> [...]
>
> from 12 to 11: R0_w=-9223372036854775794 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 11: (07) r0 += 1                      ; R0_w=-9223372036854775793
> 12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 13: safe
>
> from 12 to 11: R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))

First thing to debug is why umin is higher than umax.

> 11: (07) r0 += 1                      ; R0_w=-9223372036854775792
> 12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775792 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 13: safe
>
> [...]
>
> The loop crosses termination condition r0 == r1.umax, and does not stop.
>
> The reason is that when the verifier enumerates to r1.umin == r1.umax, the value
> 0x800000000000000f of r1.umin is greater than U32_MAX, so __reg_combine_64_into_32
> sets the u32 range of r1 to [0, U32_MAX] instead of marking r1 as a constant,
> making is_branch_taken() in check_cond_jmp_op() be skipped.

And it's fine. The verifier is conservative.

>
> To fix it, update 32-bit bounds when the lower 32-bit value is not wrapping,
> even if the 64-bit value is beyond the range of [0, U32_MAX] or [S32_MIN, S32_MAX].

That's not safe in general.

>
> Signed-off-by: Xu Kuohai <xukuohai@huaweicloud.com>
> ---
>  kernel/bpf/verifier.c | 27 +++++++++++----------------
>  1 file changed, 11 insertions(+), 16 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b2116ca78d9a..64c9ee3857ec 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2013,26 +2013,21 @@ static void __reg_combine_32_into_64(struct bpf_reg_state *reg)
>         reg_bounds_sync(reg);
>  }
>
> -static bool __reg64_bound_s32(s64 a)
> -{
> -       return a >= S32_MIN && a <= S32_MAX;
> -}
> -
> -static bool __reg64_bound_u32(u64 a)
> -{
> -       return a >= U32_MIN && a <= U32_MAX;
> -}
> -
>  static void __reg_combine_64_into_32(struct bpf_reg_state *reg)
>  {
> +       s64 smin = reg->smin_value;
> +       s64 smax = reg->smax_value;
> +       u64 umin = reg->umin_value;
> +       u64 umax = reg->umax_value;
> +
>         __mark_reg32_unbounded(reg);
> -       if (__reg64_bound_s32(reg->smin_value) && __reg64_bound_s32(reg->smax_value)) {
> -               reg->s32_min_value = (s32)reg->smin_value;
> -               reg->s32_max_value = (s32)reg->smax_value;
> +       if ((u64)(smax - smin) <= (u64)U32_MAX && (s32)smin <= (s32)smax) {
> +               reg->s32_min_value = (s32)smin;
> +               reg->s32_max_value = (s32)smax;
>         }
> -       if (__reg64_bound_u32(reg->umin_value) && __reg64_bound_u32(reg->umax_value)) {
> -               reg->u32_min_value = (u32)reg->umin_value;
> -               reg->u32_max_value = (u32)reg->umax_value;
> +       if (umax - umin <= U32_MAX && (u32)umin <= (u32)umax) {
> +               reg->u32_min_value = (u32)umin;
> +               reg->u32_max_value = (u32)umax;

This looks like a workaround for umin > umax issue.
Please debug that instead.

>         }
>         reg_bounds_sync(reg);
>  }
> --
> 2.30.2
>
Xu Kuohai March 8, 2023, 10:05 a.m. UTC | #3 
On 3/8/2023 1:22 AM, Alexei Starovoitov wrote:
> On Tue, Mar 7, 2023 at 1:05 AM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
>>
>> The following XDP prog is accepted by verifier.
>>
>> 0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
>> 1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
>> 2: (bf) r1 = r2
>> 3: (07) r1 += 1
>> 4: (2d) if r1 > r3 goto pc+6
>> 5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
>> 6: (b4) w0 = 0x7fffff10
>> 7: (0c) w1 += w0                      ; R1_w=scalar(umin=0x7fffff10,umax=0x8000000f,var_off=(0x0; 0xffffffff))
>> 8: (b4) w0 = 0x80000000
>> 9: (04) w0 += 1
>> 10: (ae) if w0 < w1 goto pc-2
>> 11: (b7) r0 = 0
>> 12: (95) exit
>>
>> while the following 64-bit version is rejected.
>>
>> 0: (61) r2 = *(u32 *)(r1 +0)          ; R2_w=pkt(off=0,r=0,imm=0)
>> 1: (61) r3 = *(u32 *)(r1 +4)          ; R3_w=pkt_end(off=0,imm=0)
>> 2: (bf) r1 = r2
>> 3: (07) r1 += 1
>> 4: (2d) if r1 > r3 goto pc+8
>> 5: (71) r1 = *(u8 *)(r2 +0)           ; R1_w=scalar(umax=255,var_off=(0x0; 0xff))
>> 6: (18) r0 = 0x7fffffffffffff10
>> 8: (0f) r1 += r0                      ; R1_w=scalar(umin=0x7fffffffffffff10,umax=0x800000000000000f)
>> 9: (18) r0 = 0x8000000000000000
>> 11: (07) r0 += 1
>> 12: (ad) if r0 < r1 goto pc-2
>> 13: (b7) r0 = 0
>> 14: (95) exit
> 
> These two programs are not equivalent.
> Not clear how apples to oranges comparison explains anything.
> 

Yes, they are not equivalent. I assumed the 32-bit prog being accepted
implies it is unreasonable for the 64-bit prog to be rejected. Regardless
of this assumption and the 32-bit prog, the above 64-bit prog is expected
to be accepted, right?

>> The verifier log says:
>>
>> [...]
>>
>> from 12 to 11: R0_w=-9223372036854775794 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
>> 11: (07) r0 += 1                      ; R0_w=-9223372036854775793
>> 12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775823,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
>> 13: safe
>>
>> from 12 to 11: R0_w=-9223372036854775793 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
> 
> First thing to debug is why umin is higher than umax.
> 

Well, it's because the loop does not stop, when r0 increases to -9223372036854775793,
the following code in reg_set_min_max() sets umin_value to 9223372036854775824:

case BPF_JGT:
{
         if (is_jmp32) {
                 [...]
         } else {
                 u64 false_umax = opcode == BPF_JGT ? val    : val - 1;
                 u64 true_umin = opcode == BPF_JGT ? val + 1 : val;

                 false_reg->umax_value = min(false_reg->umax_value, false_umax);
                 true_reg->umin_value = max(true_reg->umin_value, true_umin);
         }
         break;
}

To avoid umin > umax, it could be changed it to:

case BPF_JGT:
{
         if (is_jmp32) {
                 [...]
         } else {
                 u64 false_umax = opcode == BPF_JGT ? val    : val - 1;
                 u64 true_umin = opcode == BPF_JGT ? val + 1 : val;

                 false_reg->umax_value = min(false_reg->umax_value, false_umax);
                 false_reg->umax_value = max(false_reg->umax_value, false_reg->umin_value);

                 true_reg->umin_value = max(true_reg->umin_value, true_umin);
                 true_reg->umin_value = min(true_reg->umax_value, true_reg->umin_value);
         }
         break;
}

The problem is that the loop still does not stop because tnum_is_const(src_reg->var_off)
always returns false and is_branch_taken() is skipped:

         if (BPF_SRC(insn->code) == BPF_K) {
                 [...]
         } else if (src_reg->type == SCALAR_VALUE &&
                    is_jmp32 && tnum_is_const(tnum_subreg(src_reg->var_off))) {
                 [...]
         } else if (src_reg->type == SCALAR_VALUE &&
                    !is_jmp32 && tnum_is_const(src_reg->var_off)) {
                 pred = is_branch_taken(dst_reg,   // could not reach here
                                        src_reg->var_off.value,
                                        opcode,
                                        is_jmp32);
         } else if (reg_is_pkt_pointer_any(dst_reg) &&
                    reg_is_pkt_pointer_any(src_reg) &&
                    !is_jmp32) {
                 [...]
         }

Why tnum_is_const(src_reg->var_off) returns false is because the lower 32-bit
is not constant since the lower 32-bit range is [U32_MIN, U32_MAX].

>> 11: (07) r0 += 1                      ; R0_w=-9223372036854775792
>> 12: (ad) if r0 < r1 goto pc-2         ; R0_w=-9223372036854775792 R1=scalar(umin=9223372036854775824,umax=9223372036854775823,var_off=(0x8000000000000000; 0xffffffff))
>> 13: safe
>>
>> [...]
>>
>> The loop crosses termination condition r0 == r1.umax, and does not stop.
>>
>> The reason is that when the verifier enumerates to r1.umin == r1.umax, the value
>> 0x800000000000000f of r1.umin is greater than U32_MAX, so __reg_combine_64_into_32
>> sets the u32 range of r1 to [0, U32_MAX] instead of marking r1 as a constant,
>> making is_branch_taken() in check_cond_jmp_op() be skipped.
> 
> And it's fine. The verifier is conservative.
> 
>>
>> To fix it, update 32-bit bounds when the lower 32-bit value is not wrapping,
>> even if the 64-bit value is beyond the range of [0, U32_MAX] or [S32_MIN, S32_MAX].
> 
> That's not safe in general.
>
>>
>> Signed-off-by: Xu Kuohai <xukuohai@huaweicloud.com>
>> ---
>>   kernel/bpf/verifier.c | 27 +++++++++++----------------
>>   1 file changed, 11 insertions(+), 16 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index b2116ca78d9a..64c9ee3857ec 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -2013,26 +2013,21 @@ static void __reg_combine_32_into_64(struct bpf_reg_state *reg)
>>          reg_bounds_sync(reg);
>>   }
>>
>> -static bool __reg64_bound_s32(s64 a)
>> -{
>> -       return a >= S32_MIN && a <= S32_MAX;
>> -}
>> -
>> -static bool __reg64_bound_u32(u64 a)
>> -{
>> -       return a >= U32_MIN && a <= U32_MAX;
>> -}
>> -
>>   static void __reg_combine_64_into_32(struct bpf_reg_state *reg)
>>   {
>> +       s64 smin = reg->smin_value;
>> +       s64 smax = reg->smax_value;
>> +       u64 umin = reg->umin_value;
>> +       u64 umax = reg->umax_value;
>> +
>>          __mark_reg32_unbounded(reg);
>> -       if (__reg64_bound_s32(reg->smin_value) && __reg64_bound_s32(reg->smax_value)) {
>> -               reg->s32_min_value = (s32)reg->smin_value;
>> -               reg->s32_max_value = (s32)reg->smax_value;
>> +       if ((u64)(smax - smin) <= (u64)U32_MAX && (s32)smin <= (s32)smax) {
>> +               reg->s32_min_value = (s32)smin;
>> +               reg->s32_max_value = (s32)smax;
>>          }
>> -       if (__reg64_bound_u32(reg->umin_value) && __reg64_bound_u32(reg->umax_value)) {
>> -               reg->u32_min_value = (u32)reg->umin_value;
>> -               reg->u32_max_value = (u32)reg->umax_value;
>> +       if (umax - umin <= U32_MAX && (u32)umin <= (u32)umax) {
>> +               reg->u32_min_value = (u32)umin;
>> +               reg->u32_max_value = (u32)umax;
> 
> This looks like a workaround for umin > umax issue.
> Please debug that instead.
>

"__reg64_bound_u32(umin) && __reg64_bound_u32(max)" is a special case of
"umax - umin <= U32_MAX && (u32)umin <= (u32)umax " when umax <= U32_MAX.

If it's only safe to set lower 32-bit range to [U32_MIN, U32_MAX] when
umax > U32_MAX, could we infer the 64-bit value is a constant from umin == umax?

>>          }
>>          reg_bounds_sync(reg);
>>   }
>> --
>> 2.30.2
>>
> .
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b2116ca78d9a..64c9ee3857ec 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2013,26 +2013,21 @@  static void __reg_combine_32_into_64(struct bpf_reg_state *reg)
 	reg_bounds_sync(reg);
 }
 
-static bool __reg64_bound_s32(s64 a)
-{
-	return a >= S32_MIN && a <= S32_MAX;
-}
-
-static bool __reg64_bound_u32(u64 a)
-{
-	return a >= U32_MIN && a <= U32_MAX;
-}
-
 static void __reg_combine_64_into_32(struct bpf_reg_state *reg)
 {
+	s64 smin = reg->smin_value;
+	s64 smax = reg->smax_value;
+	u64 umin = reg->umin_value;
+	u64 umax = reg->umax_value;
+
 	__mark_reg32_unbounded(reg);
-	if (__reg64_bound_s32(reg->smin_value) && __reg64_bound_s32(reg->smax_value)) {
-		reg->s32_min_value = (s32)reg->smin_value;
-		reg->s32_max_value = (s32)reg->smax_value;
+	if ((u64)(smax - smin) <= (u64)U32_MAX && (s32)smin <= (s32)smax) {
+		reg->s32_min_value = (s32)smin;
+		reg->s32_max_value = (s32)smax;
 	}
-	if (__reg64_bound_u32(reg->umin_value) && __reg64_bound_u32(reg->umax_value)) {
-		reg->u32_min_value = (u32)reg->umin_value;
-		reg->u32_max_value = (u32)reg->umax_value;
+	if (umax - umin <= U32_MAX && (u32)umin <= (u32)umax) {
+		reg->u32_min_value = (u32)umin;
+		reg->u32_max_value = (u32)umax;
 	}
 	reg_bounds_sync(reg);
 }