Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > linux.kernel > #1283713 > unrolled thread

bpf: undefined shift in __bpf_prog_run

Started byDmitry Vyukov <dvyukov@google.com>
First post2015-12-04 12:20 +0100
Last post2015-12-09 19:40 +0100
Articles 12 — 6 participants

Back to article view | Back to linux.kernel


Contents

  bpf: undefined shift in __bpf_prog_run Dmitry Vyukov <dvyukov@google.com> - 2015-12-04 12:20 +0100
    Re: bpf: undefined shift in __bpf_prog_run Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2015-12-04 19:50 +0100
      Re: bpf: undefined shift in __bpf_prog_run Dmitry Vyukov <dvyukov@google.com> - 2015-12-04 20:10 +0100
        Re: bpf: undefined shift in __bpf_prog_run Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2015-12-04 20:20 +0100
          Re: bpf: undefined shift in __bpf_prog_run David Miller <davem@davemloft.net> - 2015-12-04 20:30 +0100
            Re: bpf: undefined shift in __bpf_prog_run Dmitry Vyukov <dvyukov@google.com> - 2015-12-04 20:50 +0100
              Re: bpf: undefined shift in __bpf_prog_run Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2015-12-04 21:40 +0100
                Re: bpf: undefined shift in __bpf_prog_run Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2015-12-04 22:00 +0100
                Re: bpf: undefined shift in __bpf_prog_run David Miller <davem@davemloft.net> - 2015-12-04 22:40 +0100
              Re: bpf: undefined shift in __bpf_prog_run Hannes Frederic Sowa <hannes@stressinduktion.org> - 2015-12-04 22:30 +0100
              RE: bpf: undefined shift in __bpf_prog_run David Laight <David.Laight@ACULAB.COM> - 2015-12-07 12:20 +0100
          Re: bpf: undefined shift in __bpf_prog_run Daniel Borkmann <daniel@iogearbox.net> - 2015-12-09 19:40 +0100

#1283713 — bpf: undefined shift in __bpf_prog_run

FromDmitry Vyukov <dvyukov@google.com>
Date2015-12-04 12:20 +0100
Subjectbpf: undefined shift in __bpf_prog_run
Message-ID<qBWz7-1WS-1@gated-at.bofh.it>
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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]


#1284155

FromAlexei Starovoitov <alexei.starovoitov@gmail.com>
Date2015-12-04 19:50 +0100
Message-ID<qC3AC-6ol-27@gated-at.bofh.it>
In reply to#1283713
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.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284163

FromDmitry Vyukov <dvyukov@google.com>
Date2015-12-04 20:10 +0100
Message-ID<qC3TX-6LX-3@gated-at.bofh.it>
In reply to#1284155
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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284168

FromAlexei Starovoitov <alexei.starovoitov@gmail.com>
Date2015-12-04 20:20 +0100
Message-ID<qC43D-6Pk-5@gated-at.bofh.it>
In reply to#1284163
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.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284173

FromDavid Miller <davem@davemloft.net>
Date2015-12-04 20:30 +0100
Message-ID<qC4dk-6SH-17@gated-at.bofh.it>
In reply to#1284168
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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284179

FromDmitry Vyukov <dvyukov@google.com>
Date2015-12-04 20:50 +0100
Message-ID<qC4wF-6ZX-3@gated-at.bofh.it>
In reply to#1284173
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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284215

FromAlexei Starovoitov <alexei.starovoitov@gmail.com>
Date2015-12-04 21:40 +0100
Message-ID<qC5j4-7wJ-21@gated-at.bofh.it>
In reply to#1284179
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.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284223

FromAlexei Starovoitov <alexei.starovoitov@gmail.com>
Date2015-12-04 22:00 +0100
Message-ID<qC5Cq-7E0-3@gated-at.bofh.it>
In reply to#1284215
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.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284247

FromDavid Miller <davem@davemloft.net>
Date2015-12-04 22:40 +0100
Message-ID<qC6f8-88D-5@gated-at.bofh.it>
In reply to#1284215
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1284239

FromHannes Frederic Sowa <hannes@stressinduktion.org>
Date2015-12-04 22:30 +0100
Message-ID<qC65r-851-1@gated-at.bofh.it>
In reply to#1284179
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1285217

FromDavid Laight <David.Laight@ACULAB.COM>
Date2015-12-07 12:20 +0100
Message-ID<qD1ZM-3Ks-1@gated-at.bofh.it>
In reply to#1284179
RnJvbTogRG1pdHJ5IFZ5dWtvdg0KPiBTZW50OiAwNCBEZWNlbWJlciAyMDE1IDE5OjQ5DQouLi4N
Cj4gMy40LjMNCj4gdW5kZWZpbmVkIGJlaGF2aW9yDQo+IDEgYmVoYXZpb3IsIHVwb24gdXNlIG9m
IGEgbm9ucG9ydGFibGUgb3IgZXJyb25lb3VzIHByb2dyYW0gY29uc3RydWN0DQo+IG9yIG9mIGVy
cm9uZW91cyBkYXRhLCBmb3Igd2hpY2ggdGhpcyBJbnRlcm5hdGlvbmFsIFN0YW5kYXJkIGltcG9z
ZXMgbm8NCj4gcmVxdWlyZW1lbnRzDQo+IDIgTk9URSBQb3NzaWJsZSB1bmRlZmluZWQgYmVoYXZp
b3IgcmFuZ2VzIGZyb20gaWdub3JpbmcgdGhlIHNpdHVhdGlvbg0KPiBjb21wbGV0ZWx5IHdpdGgg
dW5wcmVkaWN0YWJsZSByZXN1bHRzLCB0byBiZWhhdmluZyBkdXJpbmcgdHJhbnNsYXRpb24NCj4g
b3IgcHJvZ3JhbSBleGVjdXRpb24gaW4gYSBkb2N1bWVudGVkIG1hbm5lciBjaGFyYWN0ZXJpc3Rp
YyBvZiB0aGUNCj4gZW52aXJvbm1lbnQgKHdpdGggb3Igd2l0aG91dCB0aGUgaXNzdWFuY2Ugb2Yg
YSBkaWFnbm9zdGljIG1lc3NhZ2UpLCB0bw0KPiB0ZXJtaW5hdGluZyBhIHRyYW5zbGF0aW9uIG9y
IGV4ZWN1dGlvbg0KDQpXaGlsZSAndW5kZWZpbmVkIGJlaGF2aW91cicgaXMgYWxsb3dlZCB0byBp
bmNsdWRlICdmaXJpbmcgYW4gSUNCTSBhdA0KdGhlIGN1cnJlbnQgbG9jYXRpb24gb2YgdGhlIHBl
cnNvbiB3aG8gd3JvdGUgdGhlIGNvZGUnIGl0IGlzIHZlcnkNCnVubGlrZWx5IHRvIHJlc3VsdCBp
biBhbnl0aGluZyBvdGhlciB0aGFuIGFuIHVuZXhwZWN0ZWQgdmFsdWUNCmFuZCB0aGUgY29tcGls
ZXIgbWFraW5nIGZhbHNlIGFzc3VtcHRpb25zIGFib3V0IHRoZSB2YWx1ZS4NCg0KZWcgdGhlIGNv
bXBpbGVyIGNhbiBhc3N1bWUgdGhpcyBpcyBhbiBpbmZpbml0ZSBsb29wOg0KCWludCBpOw0KCWZv
ciAoaSA9IDA7IGkgPj0gMDsgaSsrKQ0KCQkuLi4NCg0KCURhdmlkDQo=
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]


#1287731

FromDaniel Borkmann <daniel@iogearbox.net>
Date2015-12-09 19:40 +0100
Message-ID<qDROG-3xr-21@gated-at.bofh.it>
In reply to#1284168
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]


Back to top | Article view | linux.kernel


csiph-web