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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAADnVQ+2eLKh-s34ciNue-Jt5yL1MrS=LL8Zjfo0gkUkk8dDug@mail.gmail.com>
Date:   Thu, 28 May 2020 09:00:39 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Alexander Potapenko <glider@...gle.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 Thu, May 28, 2020 at 2:54 AM Alexander Potapenko <glider@...gle.com> wrote:
>
> 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?

xoring of two identical values is undefined in standard?
If that's really true such standard worth nothing.

> 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.

of course. compile can use different cpu regs.

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

"unexpected" meaning that xor has different regs?

> 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.

The tool needs to do data flow analysis to realize that the source
data in different regs is the same, hence xoring them will produce zero.
That could be super hard to achieve in practice and will take years
of work to implement KMSAN, but that's what you have to do.