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  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Thu, 28 May 2020 11:54:16 +0200
From:   Alexander Potapenko <glider@...gle.com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc:     Daniel Borkmann <daniel@...earbox.net>,
        Michal Kubecek <mkubecek@...e.cz>,
        Alexei Starovoitov <ast@...nel.org>,
        Dmitriy Vyukov <dvyukov@...gle.com>,
        Networking <netdev@...r.kernel.org>
Subject: Re: Self-XORing BPF registers is undefined behavior

On Wed, May 27, 2020 at 7:15 PM Alexei Starovoitov
<alexei.starovoitov@...il.com> wrote:
>
> On Wed, May 27, 2020 at 10:12 AM Alexander Potapenko <glider@...gle.com> wrote:
> >
> > On Wed, May 27, 2020 at 6:58 PM Alexei Starovoitov
> > <alexei.starovoitov@...il.com> wrote:
> > >
> > > On Wed, May 27, 2020 at 8:52 AM Alexander Potapenko <glider@...gle.com> wrote:
> > > >
> > > > This basically means that BPF's output register was uninitialized when
> > > > ___bpf_prog_run() returned.
> > > >
> > > > When I replace the lines initializing registers A and X in net/core/filter.c:
> > > >
> > > > -               *new_insn++ = BPF_ALU32_REG(BPF_XOR, BPF_REG_A, BPF_REG_A);
> > > > -               *new_insn++ = BPF_ALU32_REG(BPF_XOR, BPF_REG_X, BPF_REG_X);
> > > >
> > > > with
> > > >
> > > > +               *new_insn++ = BPF_MOV32_IMM(BPF_REG_A, 0);
> > > > +               *new_insn++ = BPF_MOV32_IMM(BPF_REG_X, 0);
> > > >
> > > > , the bug goes away, therefore I think it's being caused by XORing the
> > > > initially uninitialized registers with themselves.
> > > >
> > > > kernel/bpf/core.c:1408, where the uninitialized value was stored to
> > > > memory, points to the "ALU(ADD,  +)" macro in ___bpf_prog_run().
> > > > But the debug info seems to be incorrect here: if I comment this line
> > > > out and unroll the macro manually, KMSAN points to "ALU(SUB,  -)".
> > > > Most certainly it's actually one of the XOR instruction declarations.
> > > >
> > > > Do you think it makes sense to use the UB-proof BPF_MOV32_IMM
> > > > instructions to initialize the registers?
> > >
> > > I think it's better for UBsan to get smarter about xor-ing.
> >
> > Could you please elaborate on this? How exactly should KMSAN handle
> > this situation?
> > Note that despite the source says "BPF_ALU32_REG(BPF_XOR, BPF_REG_A,
> > BPF_REG_A);", it doesn't necessarily boil down to an expression like A
> > = A ^ A. It's more likely that temporary values will be involved,
> > making it quite hard to figure out whether the two operands are really
> > the same.
>
> I really don't know who to make it smarter. It's your area of expertise.

The point I am trying to make is that BPF is relying on undefined
behavior (see the quotations from C89 standard) here for no apparent
reason.
This code might be working with the current set of
compilers/optimizations, but will it pay off to debug it when
something breaks?

The C implementation for BPF_XOR in kernel/bpf/core.c is translated to:
  regs[insn->dst_reg] = regs[insn->dst_reg] ^ regs[insn->src_reg];
, at which point the compiler already can't tell whether dst_reg and
src_reg are the same.

In fact Clang may already generate unexpected code for such cases: see
the assembly for foo3() in https://godbolt.org/z/VoMHaC.

I therefore think it's better to fix the buggy code unless there are
strong reasons not to do so, rather than teach the tool how to work
around this particular bug.

-- 
Alexander Potapenko
Software Engineer

Google Germany GmbH
Erika-Mann-Straße, 33
80636 München

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg

Powered by blists - more mailing lists