bpf: undefined shift in __bpf_prog_run

bpf: undefined shift in __bpf_prog_run

[Dmitry Vyukov]

Hello,

UBSAN reports the following undefined behavior:

UBSAN: Undefined behaviour in kernel/bpf/core.c:336:2
shift exponent 2835 is to large for 32-bit type 'unsigned int'
CPU: 1 PID: 14227 Comm: syzkaller_execu Not tainted 4.4.0-rc3+ #142
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
 0000000000000001 ffff88003892f898 ffffffff82c747b8 0000000041b58ab3
 ffffffff878cbc05 ffffffff82c74706 ffff88003892f860 ffff88003892f9a0
 0000000000000000 0000000000000b13 ffffffff88178de2 0000000000000020
Call Trace:
 [<ffffffff82d684f0>] __ubsan_handle_shift_out_of_bounds+0x294/0x2e5
lib/ubsan.c:417
 [<ffffffff8160a408>] __bpf_prog_run+0x8f48/0x9ac0 kernel/bpf/core.c:336
 [<     inline     >] seccomp_run_filters kernel/seccomp.c:198
 [<     inline     >] __seccomp_phase1_filter kernel/seccomp.c:588
 [<ffffffff8156ddfb>] seccomp_phase1+0x1cb/0x990 kernel/seccomp.c:667
 [<ffffffff8100651f>] syscall_trace_enter_phase1+0x28f/0x4e0
arch/x86/entry/common.c:132
 [<ffffffff8691b939>] tracesys+0xd/0x44 arch/x86/entry/entry_64.S:240

On commit 31ade3b83e1821da5fbb2f11b5b3d4ab2ec39db8.

Such shifts have undefined behavior according to C standard and behave
differently on different archs. I guess we don't want to rely on any
kind of undefined behavior in bpf/seccomp. And generally want to
completely define results of all operations in bpf.

Re: bpf: undefined shift in __bpf_prog_run

[Alexei Starovoitov]

On Fri, Dec 04, 2015 at 12:17:08PM +0100, Dmitry Vyukov wrote:
> Hello,
> 
> UBSAN reports the following undefined behavior:
> 
> UBSAN: Undefined behaviour in kernel/bpf/core.c:336:2
> shift exponent 2835 is to large for 32-bit type 'unsigned int'
> CPU: 1 PID: 14227 Comm: syzkaller_execu Not tainted 4.4.0-rc3+ #142
> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
>  0000000000000001 ffff88003892f898 ffffffff82c747b8 0000000041b58ab3
>  ffffffff878cbc05 ffffffff82c74706 ffff88003892f860 ffff88003892f9a0
>  0000000000000000 0000000000000b13 ffffffff88178de2 0000000000000020
> Call Trace:
>  [<ffffffff82d684f0>] __ubsan_handle_shift_out_of_bounds+0x294/0x2e5
> lib/ubsan.c:417
>  [<ffffffff8160a408>] __bpf_prog_run+0x8f48/0x9ac0 kernel/bpf/core.c:336
>  [<     inline     >] seccomp_run_filters kernel/seccomp.c:198
>  [<     inline     >] __seccomp_phase1_filter kernel/seccomp.c:588
>  [<ffffffff8156ddfb>] seccomp_phase1+0x1cb/0x990 kernel/seccomp.c:667
>  [<ffffffff8100651f>] syscall_trace_enter_phase1+0x28f/0x4e0
> arch/x86/entry/common.c:132
>  [<ffffffff8691b939>] tracesys+0xd/0x44 arch/x86/entry/entry_64.S:240

is it with some random seccomp program?
If normal libseccomp generates such programs than it needs to be fixed.

> Such shifts have undefined behavior according to C standard and behave
> differently on different archs. I guess we don't want to rely on any
> kind of undefined behavior in bpf/seccomp. And generally want to
> completely define results of all operations in bpf.

bpf is an engine and we're not going to slow down each shift operation
by extra run-time checks or masks.
In other words bpf shift instruction == shift in C. Both undefined
with for large operands.
If seccomp is relying on undefined behavior, it should be fixed.

Re: bpf: undefined shift in __bpf_prog_run

[Dmitry Vyukov]

On Fri, Dec 4, 2015 at 7:43 PM, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Fri, Dec 04, 2015 at 12:17:08PM +0100, Dmitry Vyukov wrote:
>> Hello,
>>
>> UBSAN reports the following undefined behavior:
>>
>> UBSAN: Undefined behaviour in kernel/bpf/core.c:336:2
>> shift exponent 2835 is to large for 32-bit type 'unsigned int'
>> CPU: 1 PID: 14227 Comm: syzkaller_execu Not tainted 4.4.0-rc3+ #142
>> Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
>>  0000000000000001 ffff88003892f898 ffffffff82c747b8 0000000041b58ab3
>>  ffffffff878cbc05 ffffffff82c74706 ffff88003892f860 ffff88003892f9a0
>>  0000000000000000 0000000000000b13 ffffffff88178de2 0000000000000020
>> Call Trace:
>>  [<ffffffff82d684f0>] __ubsan_handle_shift_out_of_bounds+0x294/0x2e5
>> lib/ubsan.c:417
>>  [<ffffffff8160a408>] __bpf_prog_run+0x8f48/0x9ac0 kernel/bpf/core.c:336
>>  [<     inline     >] seccomp_run_filters kernel/seccomp.c:198
>>  [<     inline     >] __seccomp_phase1_filter kernel/seccomp.c:588
>>  [<ffffffff8156ddfb>] seccomp_phase1+0x1cb/0x990 kernel/seccomp.c:667
>>  [<ffffffff8100651f>] syscall_trace_enter_phase1+0x28f/0x4e0
>> arch/x86/entry/common.c:132
>>  [<ffffffff8691b939>] tracesys+0xd/0x44 arch/x86/entry/entry_64.S:240
>
> is it with some random seccomp program?
> If normal libseccomp generates such programs than it needs to be fixed.

Yes, it is with completely random seccomp program.

>> Such shifts have undefined behavior according to C standard and behave
>> differently on different archs. I guess we don't want to rely on any
>> kind of undefined behavior in bpf/seccomp. And generally want to
>> completely define results of all operations in bpf.
>
> bpf is an engine and we're not going to slow down each shift operation
> by extra run-time checks or masks.
> In other words bpf shift instruction == shift in C. Both undefined
> with for large operands.
> If seccomp is relying on undefined behavior, it should be fixed.

But note that it is not that result of such operation is undefined, it
is overall kernel behavior that becomes undefined.

Re: bpf: undefined shift in __bpf_prog_run

[Alexei Starovoitov]

On Fri, Dec 04, 2015 at 08:03:47PM +0100, Dmitry Vyukov wrote:
> > is it with some random seccomp program?
> > If normal libseccomp generates such programs than it needs to be fixed.
> 
> Yes, it is with completely random seccomp program.
> 
> >> Such shifts have undefined behavior according to C standard and behave
> >> differently on different archs. I guess we don't want to rely on any
> >> kind of undefined behavior in bpf/seccomp. And generally want to
> >> completely define results of all operations in bpf.
> >
> > bpf is an engine and we're not going to slow down each shift operation
> > by extra run-time checks or masks.
> > In other words bpf shift instruction == shift in C. Both undefined
> > with for large operands.
> > If seccomp is relying on undefined behavior, it should be fixed.
> 
> But note that it is not that result of such operation is undefined, it
> is overall kernel behavior that becomes undefined.

not true.
just don't generate random bpf programs with such shifts.
kernel is fine.

Re: bpf: undefined shift in __bpf_prog_run

[David Miller]

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date: Fri, 4 Dec 2015 11:10:15 -0800

> just don't generate random bpf programs with such shifts.

Agreed, it is exactly the same as if the compiler emitted real cpu
shift instructions with undefined behavior.

The creator of the BPF code in question is what should be fixed.

Re: bpf: undefined shift in __bpf_prog_run

[Dmitry Vyukov]

On Fri, Dec 4, 2015 at 8:26 PM, David Miller <davem@davemloft.net> wrote:
> From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Date: Fri, 4 Dec 2015 11:10:15 -0800
>
>> just don't generate random bpf programs with such shifts.
>
> Agreed, it is exactly the same as if the compiler emitted real cpu
> shift instructions with undefined behavior.
>
> The creator of the BPF code in question is what should be fixed.


There is another magical gcc flag enabled in kernel that alleviates
this undefined behavior? Or we are just assuming that C compilers are
still dump translators to machine code without analysis and
optimizations?

C standard per-se is pretty clear on this code:

6.5.7/3
The integer promotions are performed on each of the operands. The type
of the result is that of the promoted left operand. If the value of
the right operand is negative or is greater than or equal to the width
of the promoted left operand, the behavior is undefined.

3.4.3
undefined behavior
1 behavior, upon use of a nonportable or erroneous program construct
or of erroneous data, for which this International Standard imposes no
requirements
2 NOTE Possible undefined behavior ranges from ignoring the situation
completely with unpredictable results, to behaving during translation
or program execution in a documented manner characteristic of the
environment (with or without the issuance of a diagnostic message), to
terminating a translation or execution


For example, a compiler can assume that result of left shift is larger
or equal to first operand, which in turn can allow it to elide some
bounds check in code, which in turn can lead to an exploit. I am not
saying that this particular pattern is present in the code, what I
want to say is that such undefined behaviors can lead to very
unpredictable and unexpected consequences.

Re: bpf: undefined shift in __bpf_prog_run

[Alexei Starovoitov]

On Fri, Dec 04, 2015 at 08:48:57PM +0100, Dmitry Vyukov wrote:
> 
> For example, a compiler can assume that result of left shift is larger
> or equal to first operand, which in turn can allow it to elide some
> bounds check in code, which in turn can lead to an exploit. I am not
> saying that this particular pattern is present in the code, what I
> want to say is that such undefined behaviors can lead to very
> unpredictable and unexpected consequences.

Within bpf it cannot.
shift is not used in any memory or bounds operations.
so reg <<= 1234 cannot be exploited.

Re: bpf: undefined shift in __bpf_prog_run

[Alexei Starovoitov]

On Fri, Dec 04, 2015 at 12:44:09PM -0800, Kostya Serebryany wrote:
> On Fri, Dec 4, 2015 at 12:35 PM, Alexei Starovoitov <
> alexei.starovoitov@gmail.com> wrote:
> 
> > On Fri, Dec 04, 2015 at 08:48:57PM +0100, Dmitry Vyukov wrote:
> > >
> > > For example, a compiler can assume that result of left shift is larger
> > > or equal to first operand, which in turn can allow it to elide some
> > > bounds check in code, which in turn can lead to an exploit. I am not
> > > saying that this particular pattern is present in the code, what I
> > > want to say is that such undefined behaviors can lead to very
> > > unpredictable and unexpected consequences.
> >
> > Within bpf it cannot.
> > shift is not used in any memory or bounds operations.
> > so reg <<= 1234 cannot be exploited.
> >
> 
> I afraid this is not that simple.
> In C, undefined behavior applies to the entire program, not just to a
> single instruction.
> My favorite example:
> http://stackoverflow.com/questions/7682477/why-does-integer-overflow-on-x86-with-gcc-cause-an-infinite-loop
> Here an undefined behavior in one instruction causes *other* instructions
> to misbehave.

that's actually not related example. There compiler takes advantage of undefined
behavior which is very typical for compiler to do.
for(int i = 0; i < 100; i++)
and
for(unsigned int i = 0; i < 100; i++)
are very different loops from compiler point of view.

but that is not applicable in bpf world.
there are no loops in bpf in the first place.

Re: bpf: undefined shift in __bpf_prog_run

[Hannes Frederic Sowa]

Hello,

On Fri, Dec 4, 2015, at 20:48, Dmitry Vyukov wrote:
> On Fri, Dec 4, 2015 at 8:26 PM, David Miller <davem@davemloft.net> wrote:
> > From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> > Date: Fri, 4 Dec 2015 11:10:15 -0800
> >
> >> just don't generate random bpf programs with such shifts.
> >
> > Agreed, it is exactly the same as if the compiler emitted real cpu
> > shift instructions with undefined behavior.
> >
> > The creator of the BPF code in question is what should be fixed.
> 
> 
> There is another magical gcc flag enabled in kernel that alleviates
> this undefined behavior? Or we are just assuming that C compilers are
> still dump translators to machine code without analysis and
> optimizations?
> 
> C standard per-se is pretty clear on this code:
> 
> 6.5.7/3
> The integer promotions are performed on each of the operands. The type
> of the result is that of the promoted left operand. If the value of
> the right operand is negative or is greater than or equal to the width
> of the promoted left operand, the behavior is undefined.
> 
> 3.4.3
> undefined behavior
> 1 behavior, upon use of a nonportable or erroneous program construct
> or of erroneous data, for which this International Standard imposes no
> requirements
> 2 NOTE Possible undefined behavior ranges from ignoring the situation
> completely with unpredictable results, to behaving during translation
> or program execution in a documented manner characteristic of the
> environment (with or without the issuance of a diagnostic message), to
> terminating a translation or execution
> 
> 
> For example, a compiler can assume that result of left shift is larger
> or equal to first operand, which in turn can allow it to elide some
> bounds check in code, which in turn can lead to an exploit. I am not
> saying that this particular pattern is present in the code, what I
> want to say is that such undefined behaviors can lead to very
> unpredictable and unexpected consequences.

I agree with Alexei and David that this should not be an issue. The
paragraphs you quoted define undefined behavior within one compilation
unit. The compiler itself can do undefined behavior within this but it
will not affect the rest of the kernel as the verifier should already
have done enough reasonable checks that you are not able to escape its
sandbox or be able to access random memory.

At the point of execution of the bytecode the interpreter or in case of
jitting, the semantics of the machine code on a particular CPU, are
crucial.

Bye,
Hannes

Re: bpf: undefined shift in __bpf_prog_run

[David Miller]

From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date: Fri, 4 Dec 2015 12:35:23 -0800

> On Fri, Dec 04, 2015 at 08:48:57PM +0100, Dmitry Vyukov wrote:
>> 
>> For example, a compiler can assume that result of left shift is larger
>> or equal to first operand, which in turn can allow it to elide some
>> bounds check in code, which in turn can lead to an exploit. I am not
>> saying that this particular pattern is present in the code, what I
>> want to say is that such undefined behaviors can lead to very
>> unpredictable and unexpected consequences.
> 
> Within bpf it cannot.
> shift is not used in any memory or bounds operations.
> so reg <<= 1234 cannot be exploited.

+1

RE: bpf: undefined shift in __bpf_prog_run

[David Laight]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="utf-8", Size: 1088 bytes --]

From: Dmitry Vyukov
> Sent: 04 December 2015 19:49
...
> 3.4.3
> undefined behavior
> 1 behavior, upon use of a nonportable or erroneous program construct
> or of erroneous data, for which this International Standard imposes no
> requirements
> 2 NOTE Possible undefined behavior ranges from ignoring the situation
> completely with unpredictable results, to behaving during translation
> or program execution in a documented manner characteristic of the
> environment (with or without the issuance of a diagnostic message), to
> terminating a translation or execution

While 'undefined behaviour' is allowed to include 'firing an ICBM at
the current location of the person who wrote the code' it is very
unlikely to result in anything other than an unexpected value
and the compiler making false assumptions about the value.

eg the compiler can assume this is an infinite loop:
	int i;
	for (i = 0; i >= 0; i++)
		...

	David
ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥

RE: bpf: undefined shift in __bpf_prog_run

[David Laight]

From: Dmitry Vyukov
> Sent: 04 December 2015 19:49
...
> 3.4.3
> undefined behavior
> 1 behavior, upon use of a nonportable or erroneous program construct
> or of erroneous data, for which this International Standard imposes no
> requirements
> 2 NOTE Possible undefined behavior ranges from ignoring the situation
> completely with unpredictable results, to behaving during translation
> or program execution in a documented manner characteristic of the
> environment (with or without the issuance of a diagnostic message), to
> terminating a translation or execution

While 'undefined behaviour' is allowed to include 'firing an ICBM at
the current location of the person who wrote the code' it is very
unlikely to result in anything other than an unexpected value
and the compiler making false assumptions about the value.

eg the compiler can assume this is an infinite loop:
	int i;
	for (i = 0; i >= 0; i++)
		...

	David

Re: bpf: undefined shift in __bpf_prog_run

[Daniel Borkmann]

On 12/04/2015 08:10 PM, Alexei Starovoitov wrote:
> On Fri, Dec 04, 2015 at 08:03:47PM +0100, Dmitry Vyukov wrote:
>>> is it with some random seccomp program?
>>> If normal libseccomp generates such programs than it needs to be fixed.
>>
>> Yes, it is with completely random seccomp program.
>>
>>>> Such shifts have undefined behavior according to C standard and behave
>>>> differently on different archs. I guess we don't want to rely on any
>>>> kind of undefined behavior in bpf/seccomp. And generally want to
>>>> completely define results of all operations in bpf.
>>>
>>> bpf is an engine and we're not going to slow down each shift operation
>>> by extra run-time checks or masks.
>>> In other words bpf shift instruction == shift in C. Both undefined
>>> with for large operands.
>>> If seccomp is relying on undefined behavior, it should be fixed.
>>
>> But note that it is not that result of such operation is undefined, it
>> is overall kernel behavior that becomes undefined.
>
> not true.
> just don't generate random bpf programs with such shifts.
> kernel is fine.

Kind of agree, so in case BPF JITs are being used, undefined behavior of the
C standard would not really apply here, imho. Sure, clang is the front end,
but the actual mapping from BPF to the arch opcode happens in kernel in that
case (and pre-checked by the verifier). What matters in that case is the
emission of the opcode itself from the BPF JIT compiler and the underlying
spec of the ISA.

F.e. while on x86 a shift count of > 31 resp. > 63 can be emitted by the
JIT for the related 32/64 bit operations, the count will be masked with 31
resp. 63 eventually by the HW. In other cases like ppc the result would be
different as the mask there is bigger.

In case not JITs but the BPF interpreter is being used (which is compiled
along with the kernel of course), we might need to consider it as "undefined
behavior" in the sense that gcc _could_ do insane things iff it really wanted
to for those cases. Given the interpreter is generic, gcc cannot make any
assumptions at compile time (wrt constants), disassembly on x86 looks similar
to what we do in JIT case. I think bailing out from the interpreter with
'return 0' seems equally bad/unexpected to me. I recall we had a similar
conversation here [1] on rol32() / ror32() and variants.

As this would only concern the interpreter itself, one option could be to reject
large constants (K) through the verifier and binary AND with upper shift limits
the register cases (w/o modifying JITs). That however would give a wrong impression
on the JIT developer (thinking he needs to copy this). Thus, I'd agree with others
iff gcc really decides to go crazy (and perhaps throw an exception or the like),
we need to address the interpreter. Perhaps we should add some test cases to
test_bpf.c on this to track the behavior.

   [1] https://lkml.org/lkml/2014/10/20/186