Date:   Fri, 29 May 2020 08:14:42 +0200
From:   Dmitry Vyukov <dvyukov@...gle.com>
To:     Edward Cree <ecree@...arflare.com>
Cc:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Alexander Potapenko <glider@...gle.com>,
        Daniel Borkmann <daniel@...earbox.net>,
        Michal Kubecek <mkubecek@...e.cz>,
        Alexei Starovoitov <ast@...nel.org>,
        Networking <netdev@...r.kernel.org>
Subject: Re: Self-XORing BPF registers is undefined behavior

On Fri, May 29, 2020 at 2:17 AM Edward Cree <ecree@...arflare.com> wrote:
>
> On 28/05/2020 17:00, Alexei Starovoitov wrote:
> > xoring of two identical values is undefined in standard?
> I believe it is in this case, yes; even without the complication
>  of array references that happen to alias, Alexander's foo1() is
>  undefined behaviour under C89 (and also C99 which handles the
>  case differently).
>
> From the definitions section (1.6) of the C89 draft [1]:
> > * Undefined behavior --- behavior, upon use of a nonportable or
> > erroneous program construct, of erroneous data, or of
> > indeterminately-valued objects, for which the Standard imposes
> > no requirements.
> And from 3.5.7 'Initialization':
> > If an object that has automatic storage duration is not
> > initialized explicitly, its value is indeterminate.
> Since the standard doesn't say anything about self-XORing that
>  could make it 'special' in this regard, the compiler isn't
>  required to notice that it's a self-XOR, and (in the tradition
>  of compiler-writers the world over) is entitled to optimise the
>  program based on the assumption that the programmer has not
>  committed UB, so in the foo1() example would be strictly within
>  its rights to generate a binary that contained no XOR
>  instruction at all.  UB, as you surely know, isn't guaranteed to
>  do something 'sensible'.
> And in the BPF example, if the compiler at some point manages to
>  statically figure out that regs[insn->dst_reg] is uninitialised,
>  it might say "hey, I can just grab any old free register and
>  declare that that's now regs[insn->dst_reg] without filling it.
>  And then it can do the same for regs[insn->src_reg], or heck,
>  even choose to fill that one (this is now legal even though the
>  pointers alias, because you already committed UB), and do a xor
>  with different regs and produce garbage results.
>
> (In C99 it gets subtler because an 'indeterminate value' is
>  defined to be 'either a valid value or a trap representation',
>  so arguably the compiler can only do this stuff if it _has_
>  trap representations for the type in question.)

Interesting. Are you sure that's the meaning of 'indeterminate value'?
My latest copy of the standard says:

3.19.2
1 indeterminate value
either an unspecified value or a trap representation

My reading of this would be that this only prevents things from
exploding in all possible random ways (like formatting drive). The
effects are only reduced to either getting a random value, or a trap
on access to the value. Both of these do not seem to be acceptable for
a bpf program.


> > If that's really true such standard worth nothing.
> You may be right, but plenty of compiler writers will take that
>  as a reason to ignore you, and if (say) a gcc upgrade breaks
>  filter.c, they will merrily close any bugs you file as NOTABUG
>  or INVALID or GOAWAYWEDONTCARE.
> Is this annoying?  Extremely; the XOR-clearing _would_ be fine
>  if the standard had chosen to define things differently (e.g.
>  it's fine under a hypothetical 'C99 but uninitialised auto
>  variables have unspecified rather than indeterminate values').
> I can't see a way to work around it that doesn't have a possible
>  performance cost (alternatives to Alexander's MOV_IMM 0 include
>  initialising regs[BPF_REG_A] and regs[BPF_REG_X] in PROG_NAME
>  and PROG_NAME_ARGS), although there is the question of whether
>  anyone who cares about performance (or security) will be using
>  BPF without the JIT anyway.
> But I don't think "Alexandar has to do the data-flow analysis in
>  KMSAN" is the right answer; KMSAN's diagnostic here is _correct_
>  in that ___bpf_prog_run() invokes UB on this XOR.
> Now, since it would be rather difficult and pointless for the
>  compiler to statically prove that the reg is uninitialised (it
>  would need to generate a special code-path just for this one
>  case), maybe the best thing to do is to get GCC folks to bless
>  this usage (perhaps defining uninitialised variables to have
>  what C99 would call an unspecified value), at which point it
>  becomes defined under the "gnu89" pseudo-standard which is what
>  we compile the kernel with.  At which point KMSAN can be taught
>  that this is OK, and can figure out "hey, you're self-XORing an
>  unspecified value, the result is determinate" and clear the
>  shadow bits appropriately.
>
> -ed
>
> [1]: https://port70.net/~nsz/c/c89/c89-draft.html

Powered by blists - more mailing lists