| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Thu, 13 Dec 2018 15:54:38 +0100
From: Daniel Borkmann <daniel@...earbox.net>
To: Alexander Potapenko <glider@...gle.com>, mkubecek@...e.cz
Cc: ast@...nel.org, Dmitriy Vyukov <dvyukov@...gle.com>,
Networking <netdev@...r.kernel.org>
Subject: Re: Self-XORing BPF registers is undefined behavior
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:
# cat /proc/sys/net/core/bpf_jit_enable
0
For the eBPF case, lets take (test_verifier.c):
{
"xor test",
.insns = {
BPF_ALU64_REG(BPF_XOR, BPF_REG_2, BPF_REG_2),
BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),
},
.result = ACCEPT,
.retval = 0,
},
# ./test_verifier 0
#0/u xor test FAIL
Failed to load prog 'Permission denied'!
0: (af) r2 ^= r2
R2 !read_ok
#0/p xor test FAIL
Failed to load prog 'Permission denied'!
0: (af) r2 ^= r2
R2 !read_ok
Summary: 0 PASSED, 0 SKIPPED, 2 FAILED
And for the initialized case:
{
"xor test",
.insns = {
BPF_MOV64_IMM(BPF_REG_2, 42),
BPF_ALU64_REG(BPF_XOR, BPF_REG_2, BPF_REG_2),
BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
BPF_EXIT_INSN(),
},
.result = ACCEPT,
.retval = 0,
},
# ./test_verifier 0
#0/u xor test OK
#0/p xor test OK
Summary: 2 PASSED, 0 SKIPPED, 0 FAILED
And cBPF (test_bpf.c):
{
"xor test",
.u.insns = {
BPF_STMT(BPF_RET | BPF_A, 0)
},
CLASSIC,
{ },
{ { 0, 0 }, },
},
[...]
[88819.276142] test_bpf: #0 xor test jited:0 PASS
[...]
Given latter two use the same underlying interpreter implementation for
the 'good' and 'bad' case, I don't see how compiler would have any degree
of freedom to judge about the runtime dependent BPF insn input stream
here. If it would assume UB, then also 'good' xor case would be broken
and miscompiled which it is clearly not (even for some very obvious case
below). While KMSAN is analyzing runtime memory access, compiler cannot..
# cat foo.c
#include <stdio.h>
int main(void)
{
int foo = foo ^ foo;
printf("%u\n", foo);
return 0;
}
# clang -Wall -O2 foo.c
foo.c:4:12: warning: variable 'foo' is uninitialized when used within its own initialization [-Wuninitialized]
int foo = foo ^ foo;
~~~ ^~~
# ./a.out
0
disasm:
00000000004004d0 <main>:
4004d0: 50 push %rax
4004d1: bf 74 05 40 00 mov $0x400574,%edi
4004d6: 31 f6 xor %esi,%esi
4004d8: 31 c0 xor %eax,%eax
4004da: e8 f1 fe ff ff callq 4003d0 <printf@plt>
4004df: 31 c0 xor %eax,%eax
4004e1: 59 pop %rcx
4004e2: c3 retq
4004e3: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
4004ea: 00 00 00
4004ed: 0f 1f 00 nopl (%rax)
# gcc -Wall -O2 foo.c (neither complains with using -Wextra)
# ./a.out
0
disasm:
0000000000000560 <main>:
560: 48 8d 35 ad 01 00 00 lea 0x1ad(%rip),%rsi # 714 <_IO_stdin_used+0x4>
567: 48 83 ec 08 sub $0x8,%rsp
56b: 31 d2 xor %edx,%edx
56d: bf 01 00 00 00 mov $0x1,%edi
572: 31 c0 xor %eax,%eax
574: e8 c7 ff ff ff callq 540 <__printf_chk@plt>
579: 31 c0 xor %eax,%eax
57b: 48 83 c4 08 add $0x8,%rsp
57f: c3 retq
Cheers,
Daniel
Powered by blists - more mailing lists