Message-ID: <CAG_fn=W_BCW5OvP2tayQLcrTuiXCXDBYDYSJ7U6xHftDFyLu3A@mail.gmail.com>
Date:   Wed, 27 May 2020 17:52:20 +0200
From:   Alexander Potapenko <glider@...gle.com>
To:     daniel@...earbox.net
Cc:     mkubecek@...e.cz, ast@...nel.org,
        Dmitriy Vyukov <dvyukov@...gle.com>,
        Networking <netdev@...r.kernel.org>
Subject: Re: Self-XORing BPF registers is undefined behavior

On Tue, Dec 18, 2018 at 3:36 PM Alexander Potapenko <glider@...gle.com> wrote:
>
> On Thu, Dec 13, 2018 at 3:54 PM Daniel Borkmann <daniel@...earbox.net> wrote:
> >
> > On 12/13/2018 02:18 PM, Daniel Borkmann wrote:
> > > On 12/13/2018 01:24 PM, Alexander Potapenko wrote:
> > >> On Thu, Dec 13, 2018 at 1:20 PM Michal Kubecek <mkubecek@...e.cz> wrote:
> > >>> On Thu, Dec 13, 2018 at 12:59:36PM +0100, Michal Kubecek wrote:
> > >>>> On Thu, Dec 13, 2018 at 12:00:59PM +0100, Alexander Potapenko wrote:
> > >>>>> Hi BPF maintainers,
> > >>>>>
> > >>>>> some time ago KMSAN found an issue in BPF code which we decided to
> > >>>>> suppress at that point, but now I'd like to bring it to your
> > >>>>> attention.
> > >>>>> Namely, some BPF programs may contain instructions that XOR a register
> > >>>>> with itself.
> > >>>>> This effectively results in the following C code:
> > >>>>>   regs[BPF_REG_A] = regs[BPF_REG_A] ^ regs[BPF_REG_A];
> > >>>>> or
> > >>>>>   regs[BPF_REG_X] = regs[BPF_REG_X] ^ regs[BPF_REG_X];
> > >>>>> being executed.
> > >>>>>
> > >>>>> According to the C11 standard this is undefined behavior, so KMSAN
> > >>>>> reports an error in this case.
> > >
> > > Can you elaborate / quote the exact bit from C11 that KMSAN is referring
> > > to? (The below that Michal was quoting or something else?)
> > >
> > > Does that only refer to C11 standard? Note that kernel's Makefile +430
> > > explicitly states 'std=gnu89' and not 'std=c11' [0].
> > >
> > >   [0] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=51b97e354ba9fce1890cf38ecc754aa49677fc89
> > >
> > >>>> Can you quote the part of the standard saying this is undefined
> > >>>> behavior? I couldn't find anything else than
> > >>>>
> > >>>>   If the value being stored in an object is read from another object
> > >>>>   that overlaps in any way the storage of the first object, then the
> > >>>>   overlap shall be exact and the two objects shall have qualified or
> > >>>>   unqualified versions of a compatible type; otherwise, the behavior
> > >>>>   is undefined.
> > >>>>
> > >>>> (but I only have a draft for obvious reasons). I'm not sure what exactly
> > >>>> they mean by "exact overlap" and the standard doesn't seem to define
> > >>>> the term but if the two objects are actually the same, they certainly
> > >>>> have compatible types.
> > >
> > > Here is an example for the overlap quoted above; I don't think this
> > > applies to our case since it would be "exact". Quote [1]:
> > >
> > >   struct S { int x; int y; };
> > >   struct T { int z; struct S s; };
> > >   union U { struct S f ; struct T g; } u;
> > >
> > >   main(){
> > >     u.f = u.g.s;
> > >     return 0;
> > >   }
> > >
> > >   [1] https://bts.frama-c.com/print_bug_page.php?bug_id=945
> > >
> > >>> I think I understand now. You didn't want to say that the statement
> > >>>
> > >>>   regs[BPF_REG_A] = regs[BPF_REG_A] ^ regs[BPF_REG_A];
> > >>>
> > >>> as such is undefined behavior but that it's UB when regs[BPF_REG_A] is
> > >>> uninitialized. Right?
> > >> Yes. Sorry for being unclear.
> > >> By default regs[] is uninitialized, so we need to initialize it before
> > >> using the register values.
> > >> I am also wondering if it's possible to simply copy the uninitialized
> > >> register values from regs[] to the userspace via maps.
> >
> > Nope, not possible. And to elaborate on cBPF / eBPF cases:
> If you mean that it's not possible to generate a eBPF program that
> XORs an uninitialized register with itself, you may be actually right.
> I've reverted https://github.com/google/kmsan/commit/813c0f3d45ebfa321d70b4b06cc054518dd1d90d,
> and syzkaller couldn't find a program triggering this behavior so far.
> Perhaps something had changed in eBPF code since I encountered this error.
> I'll be watching the dashboard and will let you know if I have a
> reliable reproducer for the aforementioned problem.
> Thanks for checking!

Hi again,

similar bugs have started showing up recently.
When I run the attached program (note it uses
SO_SECURITY_AUTHENTICATION, which as far as I understand is a no-op)
on the KMSAN-enabled kernel (currently using v5.7-rc4) I see the
following errors:

=====================================================
BUG: KMSAN: uninit-value in packet_rcv_fanout+0x242b/0x25a0
net/packet/af_packet.c:1463
 __msan_warning+0x58/0xa0 mm/kmsan/kmsan_instr.c:215
 packet_rcv_fanout+0x242b/0x25a0 net/packet/af_packet.c:1463
 deliver_skb net/core/dev.c:2168
 __netif_receive_skb_core+0x1434/0x5860 net/core/dev.c:5052
 __netif_receive_skb_list_core+0x315/0x1380 net/core/dev.c:5264
 __netif_receive_skb_list net/core/dev.c:5331
 netif_receive_skb_list_internal+0xf54/0x1600 net/core/dev.c:5426
 gro_normal_list net/core/dev.c:5537
 napi_complete_done+0x2ef/0xb40 net/core/dev.c:6258
 e1000_clean+0x1bc8/0x5d80 drivers/net/ethernet/intel/e1000/e1000_main.c:3802
 napi_poll net/core/dev.c:6572
...
Uninit was stored to memory at:
 kmsan_save_stack_with_flags mm/kmsan/kmsan.c:144
 kmsan_internal_chain_origin+0xad/0x130 mm/kmsan/kmsan.c:310
 __msan_chain_origin+0x50/0x90 mm/kmsan/kmsan_instr.c:165
 ___bpf_prog_run+0x68fa/0x9300 kernel/bpf/core.c:1408
 __bpf_prog_run32+0x101/0x170 kernel/bpf/core.c:1681
 bpf_dispatcher_nop_func ./include/linux/bpf.h:545
 bpf_prog_run_pin_on_cpu ./include/linux/filter.h:599
 bpf_prog_run_clear_cb ./include/linux/filter.h:721
 fanout_demux_bpf net/packet/af_packet.c:1404
 packet_rcv_fanout+0x517/0x25a0 net/packet/af_packet.c:1456
 deliver_skb net/core/dev.c:2168
...
Local variable ----regs@...pf_prog_run32 created at:
 __bpf_prog_run32+0x87/0x170 kernel/bpf/core.c:1681
 __bpf_prog_run32+0x87/0x170 kernel/bpf/core.c:1681
=====================================================

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?

View attachment "bpf2.c" of type "text/x-csrc" (596 bytes)

Powered by blists - more mailing lists