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: Tue, 18 Dec 2018 15:36:39 +0100 From: Alexander Potapenko <glider@...gle.com> To: daniel@...earbox.net Cc: mkubecek@...e.cz, ast@...nel.org, Dmitriy Vyukov <dvyukov@...gle.com>, Networking <netdev@...r.kernel.org> Subject: Re: Self-XORing BPF registers is undefined behavior On Thu, Dec 13, 2018 at 3:54 PM Daniel Borkmann <daniel@...earbox.net> wrote: > > 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: If you mean that it's not possible to generate a eBPF program that XORs an uninitialized register with itself, you may be actually right. I've reverted https://github.com/google/kmsan/commit/813c0f3d45ebfa321d70b4b06cc054518dd1d90d, and syzkaller couldn't find a program triggering this behavior so far. Perhaps something had changed in eBPF code since I encountered this error. I'll be watching the dashboard and will let you know if I have a reliable reproducer for the aforementioned problem. Thanks for checking! > # 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.. IIUC some hardware, like IA64, may do these checks at runtime (see https://blogs.msdn.microsoft.com/oldnewthing/20150727-00/?p=90821 for an example) Please note that referring to results of compiling a finite number of programs with UB with a finite number of compilers doesn't prove anything. It won't help much in the case tomorrow e.g. GCC changes its behavior to make use of some new hardware feature. > # 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 -- Alexander Potapenko Software Engineer Google Germany GmbH Erika-Mann-Straße, 33 80636 München Geschäftsführer: Paul Manicle, Halimah DeLaine Prado Registergericht und -nummer: Hamburg, HRB 86891 Sitz der Gesellschaft: Hamburg
Powered by blists - more mailing lists