netdev - Re: Self-XORing BPF registers is undefined behavior

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAG_fn=Uvp2HmqHUZqEHtAWj8dG4j5ifqbGFQ2A3Jzv10bf-b9Q@mail.gmail.com>
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