6 ms·

eBPF Can't Count?

154 points by jgrahamc 8y ago

adontz 8y ago
Looks like there are no unit tests in place? Sad.
- lixtra 8y ago
  Depending on the numbers in the test case it wouldn’t have triggered. Depending on the user, it wouldn’t have triggered. The other problem is that eBPF is a far way from KISS. But then that’s what’s needed for power and performance. EDIT after RTFA: and security against spectre and friends.
  - adontz 8y ago
    I am pretty sure that if you rewrite code, you should test rewritten version for equivalence. GCC has about 300K tests for a reason. I would not say kernel is less important.
    - lixtra 8y ago
      Testing for equivalence? Don’t you need to solve the halting problem for that? EDIT: I’m curious if a down voter can provide a piece of code that tests whether two compilates are equivalent. The root cause of the bug in the article was introduced by a patch to automatically modify an arbitrary program to harden against spectre.
      - adontz 8y ago
        If we are talking about arithmetic operations, then I believe no.
      - adontz 8y ago
        Also, I'm not talking about theoretical proof of equivalence, I'm talking about simple test like assert func(params) == rewrite(func)(params) for some reasonable set of func and params. Totally enough to catch problems like this. I'd say [unit-]testing that subtraction operator works is not that hard.
        lixtra 8y ago
        Except, that in this case params is a string containing an arbitrary program. It would help the discussion if you read the TFA (edit: more carefully). Rewrite() in this case modified the params program to harden it against Spectre.
        Quekid5 8y ago
        I think the poster is talking about something along the lines of bisimulation[1]. No need to solve the halting problem for that. [1] https://en.wikipedia.org/wiki/Bisimulation https://en.wikipedia.org/wiki/Bisimulation
        marcinzm 8y ago
        That argument applies to pretty much every single unit test ever written. A function running on a single long can take 2^64 possible values. Impossible to test by your logic. Yet they're tested without issues constantly. What you do is put together a long list of sample functions and sample arguments that covers the expected edge cases and then test those for equivalence. Hardly impossible. Just takes time. Not bulletproof but better than nothing.
      - rndgermandude 8y ago
        We're talking about eBPF programs here. Those halt by design as you cannot loop (jump backwards) and have a limited number of instructions you can use per program. So the halting problem isn't really and issue here in this particular case. You can just run the original and rewritten code in an eBPF VM with mock inputs and compare.
- majke 8y ago
  Ha! Thanks for asking. We have a number of tests in place to test this eBPF. We are proud of them since, well testing eBPF is hard. Sadly, the tests aren't really worth much here - the bug was in the _kernel_ not the eBPF code! Once again - we'd need to run our tests on the affected kernels to see the problem. We're not there yet, our automatic testing infra runs on another set of kernels than production. Oops on our side. But the fact is - testing new eBPF features is hard. You need to run a rich eBPF bytecode, on a modern kernel. I think the proper approach is to run usermode linux, and run tests _inside_ of it. Not sure how hard would that be to pull it off though. Approach similar to this project: https://source.android.com/devices/architecture/kernel/network_tests https://source.android.com/devices/architecture/kernel/netwo...
- jkbs 8y ago
  If you have the Linux kernel eBPF verifier in mind, it actually has a quite comprehensive test suite: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/testing/selftests/bpf/verifier?h=v5.1-rc7 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... Tests for the corner case that has caused the problem have been added shortly after it was fixed: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?h=v5.1-rc7&id=87dab7c3d54ce0f1ff6b54840bf7279d0944bc6a https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
justinclift 8y ago
There's a part which seems strange, where clang is used with "-O2" to generate code: $ clang -O2 -target bpf -Xclang -target-feature -Xclang +alu32 -c sub64.c -o - | llvm-objdump -S - > Apparently the compiler decided it was better to operate on 64-bit registers and discard the upper 32 bits. The workaround was to use the `volatile` keyword. The problem kind of sounds like one of the LLVM optimisation passes made the change. http://releases.llvm.org/8.0.0/docs/Passes.html#transform-passes http://releases.llvm.org/8.0.0/docs/Passes.html#transform-pa... Wonder if disabling optimisations ("-O0") would have also worked?
- praseodym 8y ago
  Looks like it: $ clang -O2 -target bpf -Xclang -target-feature -Xclang +alu32 -c sub32.c $ llvm-objdump -S -no-show-raw-insn sub32.o sub32.o: file format ELF64-BPF Disassembly of section .text: 0000000000000000 sub32: 0: w0 = w1 1: w0 -= w2 2: exit $ clang -O0 -target bpf -Xclang -target-feature -Xclang +alu32 -c sub32.c $ llvm-objdump -S -no-show-raw-insn sub32.o sub32.o: file format ELF64-BPF Disassembly of section .text: 0000000000000000 sub32: 0: w3 = w2 1: w4 = w1 2: *(u32 *)(r10 - 4) = r1 3: *(u32 *)(r10 - 8) = r2 4: r1 = *(u32 *)(r10 - 4) 5: r2 = *(u32 *)(r10 - 8) 6: w1 -= w2 7: w0 = w1 8: *(u32 *)(r10 - 12) = r3 9: *(u32 *)(r10 - 16) = r4 10: exit
- majke 8y ago
  Compiling to eBPF is hard! The compiler must: - avoid loops (backwards jumps) - unroll everything - inline everything - no function calls Basically, it's impossible to use clang to generate eBPF without -O2. Sorry.
  - justinclift 8y ago
    >Basically, it's impossible to use clang to generate eBPF without -O2. Sorry. That's a bit confusing, as the comment by praseodym shows the output from doing just that. ???
    - 8y ago
yoodenvranx 8y ago
I love stories like this, thx for posting!
setheron 8y ago
Great post. Detailed enough to keep it informative but light enough to read along. I've been doing some eBPF work at the moment but the CloudFlare guys are at another level. I'd love to take it up a notch like them. eBPF is very exciting and I'm hoping to remain in the space.
antpls 8y ago
If you made it works, does it mean the Spectre mitigation is basically useless, as it can be bypassed ?
- andreareina 8y ago
  The verifier rewrites pointer arithmetic to be safe. There's a bug where it misclassifies 64-bit integer arithmetic to be pointer arithmetic, AIUI the bug doesn't affect 32-bit arithmetic (i.e. it should still detect and rewrite 32-bit pointer arithmetic, so the Spectre mitigation isn't being bypassed)
zeusk 8y ago
The reason why volatile variables aren't extended to 64 bit is because in embedded and systems programming, it is often used to access memory mapped IO registers - so any sign extension or truncation might lead to a wrong value being sent over the bus. GCC also has a keyword (register) to make sure that the variable is sized exactly right and fits in a register (iirc, there was a way to even ask the compiler for a specific register to be used for the variable in case of inline assembly being used).
- jkbs 8y ago
  The MMIO restrictions make sense. Thanks for the explanation!

eBPF Can't Count?

154 points by jgrahamc 8y ago

adontz 8y ago

Looks like there are no unit tests in place? Sad.

lixtra 8y ago
Depending on the numbers in the test case it wouldn’t have triggered. Depending on the user, it wouldn’t have triggered. The other problem is that eBPF is a far way from KISS. But then that’s what’s needed for power and performance. EDIT after RTFA: and security against spectre and friends.
- adontz 8y ago
  I am pretty sure that if you rewrite code, you should test rewritten version for equivalence. GCC has about 300K tests for a reason. I would not say kernel is less important.
  - lixtra 8y ago
    Testing for equivalence? Don’t you need to solve the halting problem for that? EDIT: I’m curious if a down voter can provide a piece of code that tests whether two compilates are equivalent. The root cause of the bug in the article was introduced by a patch to automatically modify an arbitrary program to harden against spectre.
    - adontz 8y ago
      If we are talking about arithmetic operations, then I believe no.
    - adontz 8y ago
      Also, I'm not talking about theoretical proof of equivalence, I'm talking about simple test like assert func(params) == rewrite(func)(params) for some reasonable set of func and params. Totally enough to catch problems like this. I'd say [unit-]testing that subtraction operator works is not that hard.
      - lixtra 8y ago
        Except, that in this case params is a string containing an arbitrary program. It would help the discussion if you read the TFA (edit: more carefully). Rewrite() in this case modified the params program to harden it against Spectre.
        Quekid5 8y ago
        I think the poster is talking about something along the lines of bisimulation[1]. No need to solve the halting problem for that. [1] https://en.wikipedia.org/wiki/Bisimulation https://en.wikipedia.org/wiki/Bisimulation
        marcinzm 8y ago
        That argument applies to pretty much every single unit test ever written. A function running on a single long can take 2^64 possible values. Impossible to test by your logic. Yet they're tested without issues constantly. What you do is put together a long list of sample functions and sample arguments that covers the expected edge cases and then test those for equivalence. Hardly impossible. Just takes time. Not bulletproof but better than nothing.
    - rndgermandude 8y ago
      We're talking about eBPF programs here. Those halt by design as you cannot loop (jump backwards) and have a limited number of instructions you can use per program. So the halting problem isn't really and issue here in this particular case. You can just run the original and rewritten code in an eBPF VM with mock inputs and compare.
majke 8y ago
Ha! Thanks for asking. We have a number of tests in place to test this eBPF. We are proud of them since, well testing eBPF is hard. Sadly, the tests aren't really worth much here - the bug was in the _kernel_ not the eBPF code! Once again - we'd need to run our tests on the affected kernels to see the problem. We're not there yet, our automatic testing infra runs on another set of kernels than production. Oops on our side. But the fact is - testing new eBPF features is hard. You need to run a rich eBPF bytecode, on a modern kernel. I think the proper approach is to run usermode linux, and run tests _inside_ of it. Not sure how hard would that be to pull it off though. Approach similar to this project: https://source.android.com/devices/architecture/kernel/network_tests https://source.android.com/devices/architecture/kernel/netwo...
jkbs 8y ago
If you have the Linux kernel eBPF verifier in mind, it actually has a quite comprehensive test suite: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/testing/selftests/bpf/verifier?h=v5.1-rc7 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... Tests for the corner case that has caused the problem have been added shortly after it was fixed: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?h=v5.1-rc7&id=87dab7c3d54ce0f1ff6b54840bf7279d0944bc6a https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

justinclift 8y ago

There's a part which seems strange, where clang is used with "-O2" to generate code: $ clang -O2 -target bpf -Xclang -target-feature -Xclang +alu32 -c sub64.c -o - | llvm-objdump -S - > Apparently the compiler decided it was better to operate on 64-bit registers and discard the upper 32 bits. The workaround was to use the `volatile` keyword. The problem kind of sounds like one of the LLVM optimisation passes made the change. http://releases.llvm.org/8.0.0/docs/Passes.html#transform-passes http://releases.llvm.org/8.0.0/docs/Passes.html#transform-pa... Wonder if disabling optimisations ("-O0") would have also worked?

praseodym 8y ago
Looks like it: $ clang -O2 -target bpf -Xclang -target-feature -Xclang +alu32 -c sub32.c $ llvm-objdump -S -no-show-raw-insn sub32.o sub32.o: file format ELF64-BPF Disassembly of section .text: 0000000000000000 sub32: 0: w0 = w1 1: w0 -= w2 2: exit $ clang -O0 -target bpf -Xclang -target-feature -Xclang +alu32 -c sub32.c $ llvm-objdump -S -no-show-raw-insn sub32.o sub32.o: file format ELF64-BPF Disassembly of section .text: 0000000000000000 sub32: 0: w3 = w2 1: w4 = w1 2: *(u32 *)(r10 - 4) = r1 3: *(u32 *)(r10 - 8) = r2 4: r1 = *(u32 *)(r10 - 4) 5: r2 = *(u32 *)(r10 - 8) 6: w1 -= w2 7: w0 = w1 8: *(u32 *)(r10 - 12) = r3 9: *(u32 *)(r10 - 16) = r4 10: exit
majke 8y ago
Compiling to eBPF is hard! The compiler must: - avoid loops (backwards jumps) - unroll everything - inline everything - no function calls Basically, it's impossible to use clang to generate eBPF without -O2. Sorry.
- justinclift 8y ago
  >Basically, it's impossible to use clang to generate eBPF without -O2. Sorry. That's a bit confusing, as the comment by praseodym shows the output from doing just that. ???
  - 8y ago

yoodenvranx 8y ago

I love stories like this, thx for posting!

setheron 8y ago

Great post. Detailed enough to keep it informative but light enough to read along. I've been doing some eBPF work at the moment but the CloudFlare guys are at another level. I'd love to take it up a notch like them. eBPF is very exciting and I'm hoping to remain in the space.

antpls 8y ago

If you made it works, does it mean the Spectre mitigation is basically useless, as it can be bypassed ?

andreareina 8y ago
The verifier rewrites pointer arithmetic to be safe. There's a bug where it misclassifies 64-bit integer arithmetic to be pointer arithmetic, AIUI the bug doesn't affect 32-bit arithmetic (i.e. it should still detect and rewrite 32-bit pointer arithmetic, so the Spectre mitigation isn't being bypassed)

zeusk 8y ago

The reason why volatile variables aren't extended to 64 bit is because in embedded and systems programming, it is often used to access memory mapped IO registers - so any sign extension or truncation might lead to a wrong value being sent over the bus. GCC also has a keyword (register) to make sure that the variable is sized exactly right and fits in a register (iirc, there was a way to even ask the compiler for a specific register to be used for the variable in case of inline assembly being used).

jkbs 8y ago
The MMIO restrictions make sense. Thanks for the explanation!