1. Instead of having the kernel verify the program about to be installed at installation time, they rely on a trusted compiler and having the kernel perform signature validation. This means that the kernel is relying on a userspace component to enforce kernel-level safety guarantees, adds another level of coupling (via key infrastructure) between the kernel and a particular version of the Rust compiler, and if someone can get the signing key then the kernel will run their signed code no problem.
2. The Rust compiler famously prevents various memory safety correctness bugs, but does not enforce other important parts of eBPF such as termination. The proposed solution is basically just to have a timeout instead. This moves checking for bugs from load time (with the verifier) to runtime, which means you will not know you have a buggy eBPF program until you actually hit the bug and it's terminated. Timeouts are strictly worse than termination checking because they are always either too long or too short.
3. Their major problem is with "escape hatches", kernel code which eBPF programs call out to. They show that various escape hatches can be eliminated or simplified. However they don't have a plan to eliminate all escape hatches, and don't even demonstrate that their technique would eliminate particularly problematic escape hatches.
The escape hatches are unfortunately core to how eBPF in the kernel can work at the moment. It keeps the kernel from having to provide every possible piece of data the program might need as an argument, and provides a lot of assists that otherwise wouldn't be verifiable in general code. Stuff like string operations that would cut into the max 4096 instruction count.
For the most part, the kernel doesn't provide generic string processing helpers. Most helpers are there to form the basis for specific eBPF integration points (the majority are packet and socket handling tools).
The kernel provides quite a few string processing helpers; I'm not sure why they're not documented. Perhaps the purpose of the document is to highlight bpf specific functionality rather than underlying runtime helpers?
And my point in highlighting them in this discussion was to get one to consider how of trap outs to the kernel are sort of fundamental. You get 4096 instructions to execute before you're cut off by the kernel (albeit statically). Given that, say, PATH_MAX is 32768, then you simply don't have enough compute time available to process certain strings you'd expect some bpf filters to be able to handle.
So basically I just wanted to hit home that some raw computation expected of bpf is incompatible with it's current verification model and at the very least extremely deep changes to bpf would need to occur to get rid of helpers.
They are semantically simple string operations whose computational complexity scales with string length.
Near unbound string lengths would exhaust the time (somewhat aproximated by instruction) budget of eBPF applications doing even a single one.
I think the point was not to show "there are a lot of helper functions" but rather to point out "the (undocumented) helper functions that exist are problematic"
Write an eBPF program that actually needs to do any kind of meaningful string manipulation, and you'll quickly get a sense of just how rich the BPF helper inventory is in string processing functions. It'll be sharply obvious, because bounded loop enforcement will keep you from writing even the simplest string functions yourself.
I never said that it's anywhere near a complete set. My point is that they exist as something that must be a helper because they represent a type of raw computation expected of bpf programs, but incompatible with it's verifier model.
The original parent was talking about removing all helpers,
They show that various escape hatches can be eliminated or simplified. However they don't have a plan to eliminate all escape hatches
which simply doesn't make sense. The string helpers are a good example one might not have thought of beyond helpers that expose linux specific functionality.
The specific quantity of "quite a few" was left intentionally vague as it's orthogonal to my core point.
And yes, string ops are difficult if not impossible to write in verified bpf; that's almost a restatement of what I've been saying this whole thread.
I don't think it's super common to do any kind of serious string manipulation in BPF. I happened to have Facebook's `dnswatch` open in my editor, and there are zero calls to strtol or printf. The idiomatic design here is to do that kind of thing in userland, piping raw stuff down a perf or ring buffer to postprocess in a "real" language runtime.
So my rebuttal would be: you could just remove those few string helpers, and not change much about the programming model.
It's common enough in seccomp filters; I've personally used them there. Sometimes you trap into a user space dameon via seccomp_unotify to do relatively unbounded brain surgery on the unprivileged process, but that's pretty expensive to trap out and back to a daemon and it's much better if possible to make the decision in the filter program if you can get away with it.
Edit: Perhaps you'd be happy with another example that isn't a string processing function, but follows the same core idea I'm trying to get across of compute offload from the verified program to create useful verifiable programs: bpf_l3_csum_replace. It's not too hard to hit an mtu where you'd run out of instructions just recomputing the checksum because of the complexity of per byte computation required if it were to happen in regular bpf. This helper is not exposing a specific of the network stack or kernel really (other than who else needs one's complement?), but is instead really a unit of computation not super amenable to bpf verification that's still required of the use cases expected of bpf.
There are others listed in the thread. The specific quantity of 'quite a few' is orthogonal to the core point and was intentionally left vague in what now appears to be a misguided attempt to keep the comment concise and focused.
1. Instead of having the kernel verify the program about to be installed at installation time, they rely on a trusted compiler and having the kernel perform signature validation. This means that the kernel is relying on a userspace component to enforce kernel-level safety guarantees, adds another level of coupling (via key infrastructure) between the kernel and a particular version of the Rust compiler, and if someone can get the signing key then the kernel will run their signed code no problem.
FWIW I'm pretty sure this is how Microsoft does it. Verifier is in userland and signs programs post-verification. This keeps the attack surface unprivileged and is a great idea if you couple your Kernel to your userland and if your operating system has a notion of process protection - Linux doesn't do either.
Driver Verifier? That’s not intended to prove the code under test secure, only to hopefully show that it’s not complete crap in well-known ways. Even a signed driver is still trusted code and requires administrator privileges to install. I guess the closest Linux counterpart would be a distro maintainer running a hardware vendor’s out-of-tree module under KASAN and, if it passes, signing the package with their PGP key.
But none of that is intended or able to check the module (resp. driver) is not gimmeroot.ko (resp. gimmesystem.dll)—that’s left to humans inspecting the source (resp. thoughts and prayers[1]). On the other hand, the eBPF VM absolutely is intended to be able to load anything any unprivileged user throws at it and emerge unscathed.
It’s not precisely essential that a kernel have this capability, but if one is to have it, restricting the allowable code to a predetermined vendor-approved set defeats most of the point. (The authors propose that a userspace compiler running on the user’s computer be allowed to extend it, as I understood them.)
This link is about a proposed new eBPF verifier for the Linux kernel that doesn't use signing. As a research project it is not integrated to the kernel, but their plan does not involve trusting user space (instead they suggest doing the heavy lifting of the verification in user space and provide a proof of safety that the kernel checks, which seems sensible to me).
I believe you meant to link https://github.com/microsoft/ebpf-for-windows/ instead (discussed on HN recently) which is an implementation by Microsoft using the above research project that indeed does not follow the suggestion from the authors of the research project to use validation and does require trusting user space.
FWIW I'm pretty sure this is how Microsoft does it. Verifier is in userland and signs programs post-verification.
Almost. Yes the verifier is in userland, but it doesn't sign things — it's a trusted component of the system, there's no need for a signature on this step. It simply says "OK". But the verifier itself is covered by the usual system integrity mechanisms.
I'm a bit skeptical of this. It will work for some BPF use cases, but for others it might be a nightmare to deploy something in production at scale this way. Essentially on the target machine you're no better than signed kernel modules. If someone gets in possession of the key, they can do whatever they want given there is no verification mechanism anymore. It sounds good for programs of rather static nature, but for more complex application it's rather theory imo.
Your point 1 is the elephant herd in the room. If I were a paranoid person, I would think it’s by design - build in a way to compromise a system retroactively.
You should read Ken Thompson's "Reflections on trusting trust". Outsourcing security to a tool which you have to blindly trust, and can't verify is very, very dangerous.
In re 1, the system operator could configure the kernel to trust their signing key, and build the extensions themselves, which is still highly complex but would minimize the risk of a general compromise.
That said, I agree in general that this approach is mostly going backwards and fails to address the core risks. It’s also important to push back on the Rust-as-security-panacea meme. Rust prevents a certain class of bugs, but it doesn’t ensure reliable operation.
Comments
This is weird.
1. Instead of having the kernel verify the program about to be installed at installation time, they rely on a trusted compiler and having the kernel perform signature validation. This means that the kernel is relying on a userspace component to enforce kernel-level safety guarantees, adds another level of coupling (via key infrastructure) between the kernel and a particular version of the Rust compiler, and if someone can get the signing key then the kernel will run their signed code no problem.
2. The Rust compiler famously prevents various memory safety correctness bugs, but does not enforce other important parts of eBPF such as termination. The proposed solution is basically just to have a timeout instead. This moves checking for bugs from load time (with the verifier) to runtime, which means you will not know you have a buggy eBPF program until you actually hit the bug and it's terminated. Timeouts are strictly worse than termination checking because they are always either too long or too short.
3. Their major problem is with "escape hatches", kernel code which eBPF programs call out to. They show that various escape hatches can be eliminated or simplified. However they don't have a plan to eliminate all escape hatches, and don't even demonstrate that their technique would eliminate particularly problematic escape hatches.
The escape hatches are unfortunately core to how eBPF in the kernel can work at the moment. It keeps the kernel from having to provide every possible piece of data the program might need as an argument, and provides a lot of assists that otherwise wouldn't be verifiable in general code. Stuff like string operations that would cut into the max 4096 instruction count.
For the most part, the kernel doesn't provide generic string processing helpers. Most helpers are there to form the basis for specific eBPF integration points (the majority are packet and socket handling tools).
https://man7.org/linux/man-pages/man7/bpf-helpers.7.html
The kernel provides quite a few string processing helpers; I'm not sure why they're not documented. Perhaps the purpose of the document is to highlight bpf specific functionality rather than underlying runtime helpers?
You can see them listed here: https://elixir.bootlin.com/linux/latest/source/kernel/bpf/he...
And my point in highlighting them in this discussion was to get one to consider how of trap outs to the kernel are sort of fundamental. You get 4096 instructions to execute before you're cut off by the kernel (albeit statically). Given that, say, PATH_MAX is 32768, then you simply don't have enough compute time available to process certain strings you'd expect some bpf filters to be able to handle.
So basically I just wanted to hit home that some raw computation expected of bpf is incompatible with it's current verification model and at the very least extremely deep changes to bpf would need to occur to get rid of helpers.
This a link to string->integer conversion and comparison, and nothing else.
that's what GP said.
They are semantically simple string operations whose computational complexity scales with string length. Near unbound string lengths would exhaust the time (somewhat aproximated by instruction) budget of eBPF applications doing even a single one.
That's all that's there. String-integer conversion and comparison.
I think the point was not to show "there are a lot of helper functions" but rather to point out "the (undocumented) helper functions that exist are problematic"
That's not "quite a few" string helpers.
There are others too, for instance string formatting: https://elixir.bootlin.com/linux/latest/source/kernel/bpf/he...
Write an eBPF program that actually needs to do any kind of meaningful string manipulation, and you'll quickly get a sense of just how rich the BPF helper inventory is in string processing functions. It'll be sharply obvious, because bounded loop enforcement will keep you from writing even the simplest string functions yourself.
I never said that it's anywhere near a complete set. My point is that they exist as something that must be a helper because they represent a type of raw computation expected of bpf programs, but incompatible with it's verifier model.
The original parent was talking about removing all helpers,
which simply doesn't make sense. The string helpers are a good example one might not have thought of beyond helpers that expose linux specific functionality.
The specific quantity of "quite a few" was left intentionally vague as it's orthogonal to my core point.
And yes, string ops are difficult if not impossible to write in verified bpf; that's almost a restatement of what I've been saying this whole thread.
I don't think it's super common to do any kind of serious string manipulation in BPF. I happened to have Facebook's `dnswatch` open in my editor, and there are zero calls to strtol or printf. The idiomatic design here is to do that kind of thing in userland, piping raw stuff down a perf or ring buffer to postprocess in a "real" language runtime.
So my rebuttal would be: you could just remove those few string helpers, and not change much about the programming model.
It's common enough in seccomp filters; I've personally used them there. Sometimes you trap into a user space dameon via seccomp_unotify to do relatively unbounded brain surgery on the unprivileged process, but that's pretty expensive to trap out and back to a daemon and it's much better if possible to make the decision in the filter program if you can get away with it.
Edit: Perhaps you'd be happy with another example that isn't a string processing function, but follows the same core idea I'm trying to get across of compute offload from the verified program to create useful verifiable programs: bpf_l3_csum_replace. It's not too hard to hit an mtu where you'd run out of instructions just recomputing the checksum because of the complexity of per byte computation required if it were to happen in regular bpf. This helper is not exposing a specific of the network stack or kernel really (other than who else needs one's complement?), but is instead really a unit of computation not super amenable to bpf verification that's still required of the use cases expected of bpf.
So "generic string processing helpers" provided by the kernel?
"quite a few" tho
There are others listed in the thread. The specific quantity of 'quite a few' is orthogonal to the core point and was intentionally left vague in what now appears to be a misguided attempt to keep the comment concise and focused.
Rookie mistake! :P
FWIW I'm pretty sure this is how Microsoft does it. Verifier is in userland and signs programs post-verification. This keeps the attack surface unprivileged and is a great idea if you couple your Kernel to your userland and if your operating system has a notion of process protection - Linux doesn't do either.
Driver Verifier? That’s not intended to prove the code under test secure, only to hopefully show that it’s not complete crap in well-known ways. Even a signed driver is still trusted code and requires administrator privileges to install. I guess the closest Linux counterpart would be a distro maintainer running a hardware vendor’s out-of-tree module under KASAN and, if it passes, signing the package with their PGP key.
But none of that is intended or able to check the module (resp. driver) is not gimmeroot.ko (resp. gimmesystem.dll)—that’s left to humans inspecting the source (resp. thoughts and prayers[1]). On the other hand, the eBPF VM absolutely is intended to be able to load anything any unprivileged user throws at it and emerge unscathed.
It’s not precisely essential that a kernel have this capability, but if one is to have it, restricting the allowable code to a predetermined vendor-approved set defeats most of the point. (The authors propose that a userspace compiler running on the user’s computer be allowed to extend it, as I understood them.)
[1] https://www.zdnet.com/article/these-hackers-used-microsoft-s...
No, not driver verifier. https://github.com/vbpf/ebpf-verifier
This link is about a proposed new eBPF verifier for the Linux kernel that doesn't use signing. As a research project it is not integrated to the kernel, but their plan does not involve trusting user space (instead they suggest doing the heavy lifting of the verification in user space and provide a proof of safety that the kernel checks, which seems sensible to me).
I believe you meant to link https://github.com/microsoft/ebpf-for-windows/ instead (discussed on HN recently) which is an implementation by Microsoft using the above research project that indeed does not follow the suggestion from the authors of the research project to use validation and does require trusting user space.
Yeah, I had intended to link to that repo, which also links to the one I provided - unsure what happened there.
Almost. Yes the verifier is in userland, but it doesn't sign things — it's a trusted component of the system, there's no need for a signature on this step. It simply says "OK". But the verifier itself is covered by the usual system integrity mechanisms.
I see, thanks.
I'm a bit skeptical of this. It will work for some BPF use cases, but for others it might be a nightmare to deploy something in production at scale this way. Essentially on the target machine you're no better than signed kernel modules. If someone gets in possession of the key, they can do whatever they want given there is no verification mechanism anymore. It sounds good for programs of rather static nature, but for more complex application it's rather theory imo.
Your point 1 is the elephant herd in the room. If I were a paranoid person, I would think it’s by design - build in a way to compromise a system retroactively.
That makes no sense
You should read Ken Thompson's "Reflections on trusting trust". Outsourcing security to a tool which you have to blindly trust, and can't verify is very, very dangerous.
You've obviously misunderstood the proposal - there's nothing about this that is "blind trust" at all.
Anything based on PKI which at some unknown time in the future can be leaked or otherwise compromised is “blind trust”.
This is why perfect forward secrecy techniques have been developed.
In re 1, the system operator could configure the kernel to trust their signing key, and build the extensions themselves, which is still highly complex but would minimize the risk of a general compromise.
That said, I agree in general that this approach is mostly going backwards and fails to address the core risks. It’s also important to push back on the Rust-as-security-panacea meme. Rust prevents a certain class of bugs, but it doesn’t ensure reliable operation.
Questions about whether it'll work aside, the architecture is not that unusual. The Burroughs machines from the 1960/70s relied on a trusted compiler. Not signed though - just regular OS permissions ensured only the "operator" account could run the compiler :-) https://en.wikipedia.org/wiki/Burroughs_MCP https://seclab.cs.ucdavis.edu/projects/vulnerabilities/doves...