| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAADnVQLDmP0A7Pr7628nH8YSo3-xTjzAr5-x-0YCZvuS8xu09A@mail.gmail.com>
Date: Tue, 7 Mar 2023 09:22:08 -0800
From: Alexei Starovoitov <alexei.starovoitov@...il.com>
To: Xu Kuohai <xukuohai@...weicloud.com>
Cc: bpf <bpf@...r.kernel.org>,
"open list:KERNEL SELFTEST FRAMEWORK"
<linux-kselftest@...r.kernel.org>,
LKML <linux-kernel@...r.kernel.org>,
Alexei Starovoitov <ast@...nel.org>,
Daniel Borkmann <daniel@...earbox.net>,
John Fastabend <john.fastabend@...il.com>,
Andrii Nakryiko <andrii@...nel.org>,
Martin KaFai Lau <martin.lau@...ux.dev>,
Song Liu <song@...nel.org>, Yonghong Song <yhs@...com>,
KP Singh <kpsingh@...nel.org>,
Stanislav Fomichev <sdf@...gle.com>,
Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>,
Mykola Lysenko <mykolal@...com>, Shuah Khan <shuah@...nel.org>
Subject: Re: [PATCH bpf-next 1/2] bpf: update 32-bit bounds when the lower
32-bit value is not wrapping
On Tue, Mar 7, 2023 at 1:05 AM Xu Kuohai <xukuohai@...weicloud.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@...weicloud.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
>
Powered by blists - more mailing lists