Re: Self-XORing BPF registers is undefined behavior

On Thu, May 28, 2020 at 2:54 AM Alexander Potapenko [off-list ref] wrote:

On Wed, May 27, 2020 at 7:15 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Wed, May 27, 2020 at 10:12 AM Alexander Potapenko [off-list ref] wrote:

quoted

On Wed, May 27, 2020 at 6:58 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Wed, May 27, 2020 at 8:52 AM Alexander Potapenko [off-list ref] wrote:

quoted

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.