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
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <CACkBjsbvk7rNfV0uS8uvrw497ybB1uLvUFvZWPx_SBzSRn2Raw@mail.gmail.com>
Date:   Thu, 2 Nov 2023 15:17:11 +0100
From:   Hao Sun <sunhao.th@...il.com>
To:     Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc:     Eduard Zingerman <eddyz87@...il.com>,
        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 <yonghong.song@...ux.dev>,
        KP Singh <kpsingh@...nel.org>,
        Stanislav Fomichev <sdf@...gle.com>,
        Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>,
        bpf <bpf@...r.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: bpf: shift-out-of-bounds in tnum_rshift()

On Wed, Nov 1, 2023 at 11:45 PM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Wed, Nov 1, 2023 at 2:53 AM Hao Sun <sunhao.th@...il.com> wrote:
> >
> > On Fri, Oct 27, 2023 at 7:51 PM Andrii Nakryiko
> > <andrii.nakryiko@...il.com> wrote:
> > >
> > > On Wed, Oct 25, 2023 at 10:34 AM Eduard Zingerman <eddyz87@...il.com> wrote:
> > > >
> > > > On Tue, 2023-10-24 at 14:40 +0200, Hao Sun wrote:
> > > > > Hi,
> > > > >
> > > > > The following program can trigger a shift-out-of-bounds in
> > > > > tnum_rshift(), called by scalar32_min_max_rsh():
> > > > >
> > > > > 0: (bc) w0 = w1
> > > > > 1: (bf) r2 = r0
> > > > > 2: (18) r3 = 0xd
> > > > > 4: (bc) w4 = w0
> > > > > 5: (bf) r5 = r0
> > > > > 6: (bf) r7 = r3
> > > > > 7: (bf) r8 = r4
> > > > > 8: (2f) r8 *= r5
> > > > > 9: (cf) r5 s>>= r5
> > > > > 10: (a6) if w8 < 0xfffffffb goto pc+10
> > > > > 11: (1f) r7 -= r5
> > > > > 12: (71) r6 = *(u8 *)(r1 +17)
> > > > > 13: (5f) r3 &= r8
> > > > > 14: (74) w2 >>= 30
> > > > > 15: (1f) r7 -= r5
> > > > > 16: (5d) if r8 != r6 goto pc+4
> > > > > 17: (c7) r8 s>>= 5
> > > > > 18: (cf) r0 s>>= r0
> > > > > 19: (7f) r0 >>= r0
> > > > > 20: (7c) w5 >>= w8         # shift-out-bounds here
> > > > > 21: exit
> > > >
> > > > Here is a simplified example:
> > > >
> > > > SEC("?tp")
> > > > __success __retval(0)
> > > > __naked void large_shifts(void)
> > > > {
> > > >         asm volatile ("                 \
> > > >         call %[bpf_get_prandom_u32];    \n\
> > > >         r8 = r0;                        \n\
> > > >         r6 = r0;                        \n\
> > > >         r6 &= 0xf;                      \n\
> > > >         if w8 < 0xffffffff goto +2;     \n\
> > > >         if r8 != r6 goto +1;            \n\
> > > >         w0 >>= w8;       /* shift-out-bounds here */    \n\
> > > >         exit;                           \n\
> > > > "       :
> > > >         : __imm(bpf_get_prandom_u32)
> > > >         : __clobber_all);
> > > > }
> > > >
> > >
> > > With my changes the verifier does correctly derive that r8 != r6 will
> > > always happen, and thus skips w0 >>= w8. But the test itself with
> >
> > A similar issue can be triggered after your patch for JNE/JEQ.
> >
> > For the following case, the verifier would shift out of bound:
> >      //  0: r0 = -2
> >       BPF_MOV64_IMM(BPF_REG_0, -2),
> >       // 1: r0 /= 1
> >       BPF_ALU64_IMM(BPF_DIV, BPF_REG_0, 1),
> >       // 2: r8 = r0
> >       BPF_MOV64_REG(BPF_REG_8, BPF_REG_0),
> >       // 3: if w8 != 0xfffffffe goto+4
> >       BPF_JMP32_IMM(BPF_JNE, BPF_REG_8, 0xfffffffe, 4),
> >       // 4: if r8 s> 0xd goto+3
> >       BPF_JMP_IMM(BPF_JSGT, BPF_REG_8, 0xd, 3),
> >       // 5: r4 = 0x2
> >       BPF_MOV64_IMM(BPF_REG_4, 0x2),
> >       // 6: if r8 s<= r4 goto+1
> >       BPF_JMP_REG(BPF_JSLE, BPF_REG_8, BPF_REG_4, 1),
> >       // 7: w8 s>>= w0 # shift out of bound here
> >       BPF_ALU32_REG(BPF_ARSH, BPF_REG_8, BPF_REG_0),
> >       // 8: exit
> >       BPF_EXIT_INSN(),
> >
> >  -------- Verifier Log --------
> >  func#0 @0
> >  0: R1=ctx(off=0,imm=0) R10=fp0
> >  0: (b7) r0 = -2                       ; R0_w=-2
> >  1: (37) r0 /= 1                       ; R0_w=scalar()
> >  2: (bf) r8 = r0                       ; R0_w=scalar(id=1) R8_w=scalar(id=1)
> >  3: (56) if w8 != 0xfffffffe goto pc+4         ;
> > R8_w=scalar(id=1,smin=-9223372032559808514,smax=9223372036854775806,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,
> > umax32=4294967294,var_off=(0xfffffffe; 0xffffffff00000000))
> >  4: (65) if r8 s> 0xd goto pc+3        ;
> > R8_w=scalar(id=1,smin=-9223372032559808514,smax=13,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294,
> > var_off=(0xfffffffe; 0xffffffff00000000))
> >  5: (b7) r4 = 2                        ; R4_w=2
> >  6: (dd) if r8 s<= r4 goto pc+1        ; R4_w=2 R8_w=4294967294
> >  7: (cc) w8 s>>= w0                    ; R0=4294967294 R8=4294967295
> >  8: (95) exit
> >
> > Here, after #6, reg range is incorrect, seems to be an issue in JSLE case
> > in is_branch_taken(). Is this issue fixed in your patch series?
>
> I don't know, but you can easily check by applying my patches on top
> of bpf-next and then trying your change.
>

After applying your change, the verifier does not shift out of bound,
but the range
is still not correct. See this verifier log:

-------- Verifier Log --------
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = -2                       ; R0_w=-2
1: (37) r0 /= 1                       ; R0_w=scalar()
2: (bf) r8 = r0                       ; R0_w=scalar(id=1) R8_w=scalar(id=1)
3: (56) if w8 != 0xfffffffe goto pc+4         ;
R8_w=scalar(id=1,smin=-9223372032559808514,smax=9223372036854775806,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294,var_off=(0xfffffffe;
0xffffffff00000000))
4: (65) if r8 s> 0xd goto pc+3        ;
R8_w=scalar(id=1,smin=-9223372032559808514,smax=13,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294,var_off=(0xfffffffe;
0xffffffff00000000))
5: (b7) r4 = 2                        ; R4_w=2
6: (dd) if r8 s<= r4 goto pc+1        ; R4_w=2 R8_w=4294967294
7: (cc) w8 s>>= w0                    ; R0=4294967294 R8=scalar()
8: (77) r0 >>= 32                     ; R0_w=0
9: (57) r0 &= 1                       ; R0_w=0
10: (95) exit

from 6 to 8: safe

from 4 to 8: safe

from 3 to 8: safe
processed 14 insns (limit 1000000) max_states_per_insn 0 total_states
1 peak_states 1 mark_read 1

-------- Test Run Log --------
RetVal: 1

At #9, the verifier thinks the value of R0 is 0, but it's 1, because
r0 is -2 all the time before
#8. The test run also shows return value is 1.

This program can reproduce the above: https://pastebin.com/raw/a0WuXaKh

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ