| Message ID | 20250501073603.1402960-1-luis.gerhorst@fau.de |
|---|---|
| Headers | show |
| Series | bpf: Mitigate Spectre v1 using barriers | expand |
On Thu, 2025-05-01 at 09:35 +0200, Luis Gerhorst wrote: > Currently, __xlated_unpriv and __jited_unpriv do not work because the > BPF syscall will overwrite info.jited_prog_len and info.xlated_prog_len > with 0 if the process is not bpf_capable(). This bug was not noticed > before, because there is no test that actually uses > __xlated_unpriv/__jited_unpriv. > > To resolve this, simply restore the capabilities earlier (but still > after loading the program). Adding this here unconditionally is fine > because the function first checks that the capabilities were initialized > before attempting to restore them. > > This will be important later when we add tests that check whether a > speculation barrier was inserted in the correct location. > > Signed-off-by: Luis Gerhorst <luis.gerhorst@fau.de> > Fixes: 9c9f73391310 ("selftests/bpf: allow checking xlated programs in verifier_* tests") > Fixes: 7d743e4c759c ("selftests/bpf: __jited test tag to check disassembly after jit") > --- My bad, thank you for fixing this omission. Tested-by: Eduard Zingerman <eddyz87@gmail.com>
On Thu, 1 May 2025 at 09:48, Luis Gerhorst <luis.gerhorst@fau.de> wrote: > > Mark these cases as non-recoverable to later prevent them from being > caught when they occur during speculative path verification. > > Eduard writes [1]: > > The only pace I'm aware of that might act upon specific error code > from verifier syscall is libbpf. Looking through libbpf code, it seems > that this change does not interfere with libbpf. > > [1] https://lore.kernel.org/all/785b4531ce3b44a84059a4feb4ba458c68fce719.camel@gmail.com/ > > Signed-off-by: Luis Gerhorst <luis.gerhorst@fau.de> > Reviewed-by: Eduard Zingerman <eddyz87@gmail.com> > Acked-by: Henriette Herzog <henriette.herzog@rub.de> > Cc: Maximilian Ott <ott@cs.fau.de> > Cc: Milan Stephan <milan.stephan@fau.de> > --- Acked-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
On Thu, 1 May 2025 at 10:00, Luis Gerhorst <luis.gerhorst@fau.de> wrote: > > This implements the core of the series and causes the verifier to fall > back to mitigating Spectre v1 using speculation barriers. The approach > was presented at LPC'24 [1] and RAID'24 [2]. > > If we find any forbidden behavior on a speculative path, we insert a > nospec (e.g., lfence speculation barrier on x86) before the instruction > and stop verifying the path. While verifying a speculative path, we can > furthermore stop verification of that path whenever we encounter a > nospec instruction. > > A minimal example program would look as follows: > > A = true > B = true > if A goto e > f() > if B goto e > unsafe() > e: exit > > There are the following speculative and non-speculative paths > (`cur->speculative` and `speculative` referring to the value of the > push_stack() parameters): > > - A = true > - B = true > - if A goto e > - A && !cur->speculative && !speculative > - exit > - !A && !cur->speculative && speculative > - f() > - if B goto e > - B && cur->speculative && !speculative > - exit > - !B && cur->speculative && speculative > - unsafe() > > If f() contains any unsafe behavior under Spectre v1 and the unsafe > behavior matches `state->speculative && > error_recoverable_with_nospec(err)`, do_check() will now add a nospec > before f() instead of rejecting the program: > > A = true > B = true > if A goto e > nospec > f() > if B goto e > unsafe() > e: exit > > Alternatively, the algorithm also takes advantage of nospec instructions > inserted for other reasons (e.g., Spectre v4). Taking the program above > as an example, speculative path exploration can stop before f() if a > nospec was inserted there because of Spectre v4 sanitization. > > In this example, all instructions after the nospec are dead code (and > with the nospec they are also dead code speculatively). > > On x86_64, this depends on the following property of lfence [3]: > > An LFENCE instruction or a serializing instruction will ensure that no > later instructions execute, even speculatively, until all prior > instructions complete locally. [...] Inserting an LFENCE instruction > after a bounds check prevents later operations from executing before > the bound check completes. > > Regarding the example, this implies that `if B goto e` will not execute > before `if A goto e` completes. Once `if A goto e` completes, the CPU > should find that the speculation was wrong and continue with `exit`. > > If there is any other path that leads to `if B goto e` (and therefore > `unsafe()`) without going through `if A goto e`, then a nospec will > still be needed there. However, this patch assumes this other path will > be explored separately and therefore be discovered by the verifier even > if the exploration discussed here stops at the nospec. > > This patch furthermore has the unfortunate consequence that Spectre v1 > mitigations now only support architectures which implement BPF_NOSPEC. > Before this commit, Spectre v1 mitigations prevented exploits by > rejecting the programs on all architectures. Because some JITs do not > implement BPF_NOSPEC, this patch therefore may regress unpriv BPF's > security to a limited extent: > > * The regression is limited to systems vulnerable to Spectre v1, have > unprivileged BPF enabled, and do NOT emit insns for BPF_NOSPEC. The > latter is not the case for x86 64- and 32-bit, arm64, and powerpc > 64-bit and they are therefore not affected by the regression. > According to commit a6f6a95f2580 ("LoongArch, bpf: Fix jit to skip > speculation barrier opcode"), LoongArch is not vulnerable to Spectre > v1 and therefore also not affected by the regression. > > * To the best of my knowledge this regression may therefore only affect > MIPS. This is deemed acceptable because unpriv BPF is still disabled > there by default. As stated in a previous commit, BPF_NOSPEC could be > implemented for MIPS based on GCC's speculation_barrier > implementation. > > * It is unclear which other architectures (besides x86 64- and 32-bit, > ARM64, PowerPC 64-bit, LoongArch, and MIPS) supported by the kernel > are vulnerable to Spectre v1. Also, it is not clear if barriers are > available on these architectures. Implementing BPF_NOSPEC on these > architectures therefore is non-trivial. Searching GCC and the kernel > for speculation barrier implementations for these architectures > yielded no result. > > * If any of those regressed systems is also vulnerable to Spectre v4, > the system was already vulnerable to Spectre v4 attacks based on > unpriv BPF before this patch and the impact is therefore further > limited. > > As an alternative to regressing security, one could still reject > programs if the architecture does not emit BPF_NOSPEC (e.g., by removing > the empty BPF_NOSPEC-case from all JITs except for LoongArch where it > appears justified). However, this will cause rejections on these archs > that are likely unfounded in the vast majority of cases. > > In the tests, some are now successful where we previously had a > false-positive (i.e., rejection). Change them to reflect where the > nospec should be inserted (using __xlated_unpriv) and modify the error > message if the nospec is able to mitigate a problem that previously > shadowed another problem (in that case __xlated_unpriv does not work, > therefore just add a comment). > > Define SPEC_V1 to avoid duplicating this ifdef whenever we check for > nospec insns using __xlated_unpriv, define it here once. This also > improves readability. PowerPC can probably also be added here. However, > omit it for now because the BPF CI currently does not include a test. > > Briefly went through all the occurrences of EPERM, EINVAL, and EACCESS > in the verifier in order to validate that catching them like this makes > sense. > > [1] https://lpc.events/event/18/contributions/1954/ ("Mitigating > Spectre-PHT using Speculation Barriers in Linux eBPF") > [2] https://arxiv.org/pdf/2405.00078 ("VeriFence: Lightweight and > Precise Spectre Defenses for Untrusted Linux Kernel Extensions") > [3] https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/technical-documentation/runtime-speculative-side-channel-mitigations.html > ("Managed Runtime Speculative Execution Side Channel Mitigations") > > Signed-off-by: Luis Gerhorst <luis.gerhorst@fau.de> > Acked-by: Henriette Herzog <henriette.herzog@rub.de> > Cc: Maximilian Ott <ott@cs.fau.de> > Cc: Milan Stephan <milan.stephan@fau.de> > --- The patches from here on look good in general, I will ack after taking another look later. I had a more high-level question though. Back when all of this surfaced, compiler folks came up with another solution, to rely on Intel's guarantee that conditional moves are not predicted. if (condition) { mask = !condition ? 0UL : ~0UL; // CMOVcc ptr &= mask; x = *ptr; } In case the condition being true in the speculative domain leads to problems, the speculative domain will just read from NULL and not leak sensitive data. The assumption is that cost of instrumentation in speculative domain < completely stalling it until prior instructions are done using lfence. So speculation is still helpful when the branch is not mispredicted. Now I imagine it's not fun to do such analysis in the verifier (I've tried), but theoretically we could break it down into emitting bytecode from the compiler side, and lifting the compiler to do it for us, and ensuring the end result produced is sane (by still following speculative paths) from the verifier. You talk about this in the paper and in the presentation as future work. My question is mainly whether you considered implementing this, if yes, what made you choose a nospec barrier over something like above? Was it the complexity of realizing this during verification? Are there any implications of reading from NULL that would cause problems? Also, did you characterize how much difference it could make? The drop in SCTP throughput seems to suggest so, since CPU-bound computation was moved into the program. Otherwise most programs mostly defer to helpers for heavy lifting. Not that it was as fast as a helper would be, even without nospec, but still. Also a bit sad we don't split the program into BBs already, which could help reduce your mitigation's cost + plus also reduce cost of instruction patching (unrelated). Anyway, all that said, this is valuable stuff, so I was just curious.
Kumar Kartikeya Dwivedi <memxor@gmail.com> writes: > Back when all of this surfaced, compiler folks came up with another > solution, to rely on Intel's guarantee that conditional moves are not > predicted. > > if (condition) { > mask = !condition ? 0UL : ~0UL; // CMOVcc > ptr &= mask; > x = *ptr; > } > > In case the condition being true in the speculative domain leads to > problems, the speculative domain will just read from NULL and not leak > sensitive data. Yes, that is an alternative approach. > The assumption is that cost of instrumentation in speculative domain < > completely stalling it until prior instructions are done using lfence. > So speculation is still helpful when the branch is not mispredicted. > Now I imagine it's not fun to do such analysis in the verifier (I've > tried), but theoretically we could break it down into emitting > bytecode from the compiler side, and lifting the compiler to do it for > us, and ensuring the end result produced is sane (by still following > speculative paths) from the verifier. > You talk about this in the paper and in the presentation as future work. > My question is mainly whether you considered implementing this, if > yes, what made you choose a nospec barrier over something like above? The primary motivation was cerainly that it's the easiest to implement with the current verifier design. I mostly decided not to pursue the "verification-only" approach (and insert the insn in LLVM) because it would require changes to the eBPF instruction set. Other consideration include: * The approach could potentially improve performance (the compiler could for example compute the minimal-cut to reduce the number of fences) and simplify the verifier to some extent (no more inserting of insns). * It could have the downside that non/partially-vulnerable architectures can not benefit from improved performance as easily as it is the case with the current design. * The best choice for the instruction-set extension is not clear to me. For Spectre v1 USLH [1] would suffice and then one only needs a cmov, so that's easy. But this does not cover Spectre v4 (which is currently the main source of overhead). It could be 'nospec_vX rY' to tell the verifier that a certain register must not be used under speculation from a specific variant, or something generic/catch-all like the current 'nospec'. * From a security perspective, LLVM SLH is not as strong as the verifier's Spectre v1 mitigation. This is because it does not harden secret-dependent control flow as shown in [1] while the Linux verifier does (where "secrets" are unreadable/uninitialized registers and kernel pointers). It may be the case the this is not a problem for eBPF by conincidence because the verifier also restricts secret-dependent control flow. Without looking into it in detail I am not sure. If one finds that it is a problem, it may also not be important to fix if we adopt the verification-only approach you mention, or one could change LLVM to extend the mitigation. > Was it the complexity of realizing this during verification? > Are there any implications of reading from NULL that would cause problems? In theory yes, in practice I would assume no and that it works out. I am not aware of any documents from Intel / ARM that state that accessing NULL speculatively acts as a speculation barrier (I remember reading some paper that suggested it practically does, but I can not find it now). If it does not (portably), a downside would be that the verifier will have to analyze a lot more speculative instructions. > Also, did you characterize how much difference it could make? [1] has SPEC2017 benchmarks for LLVM-/U-SLH and a naive lfence-based approach (lfence after every branch), for these USLH is about twice as fast (150%) as the naive fence-based approach (300%). But this is only for Spectre v1 and the Spectre v4 overhead would have to be added. Both number are also very high compared to the programs from the VeriFence paper. There the *combined* overhead for Spectre v1 and v4 was 0% for very small programs and 16%-60% for larger programs. I have since also measured the overhead for Katran and there it is 100%-150%. I am currently working on a prototype to reduce the Spectre v4 (and Spectre v1) overhead and for Katran I was able to lower it to 15%-30% by using more precise analysis of the speculative execution using a fence-based approach. Most remaining fence are now still from Spectre v4 (not v1 which would be adressed by SLH) and I hope to eliminate some more using a SLH-style approach for v4. I will of course also have to check how this carries over to other programs, but it certainly seems possible to eliminate almost all fences because there are rarely any 'real' gadgets in non-malicious programs (only false positive one can not eliminate without reasoning about the cache). > The drop in SCTP throughput seems to suggest so, since CPU-bound > computation was moved into the program. > Otherwise most programs mostly defer to helpers for heavy lifting. > Not that it was as fast as a helper would be, even without nospec, but still. > > Also a bit sad we don't split the program into BBs already, which > could help reduce your mitigation's cost + plus also reduce cost of > instruction patching (unrelated). In the prototype I mention I also tried tackling that. However, at least for Katran it was uncommon to have more than one v1-induced fence per basic block. Therefore it might not be worth it. > Anyway, all that said, this is valuable stuff, so I was just curious. [1] https://www.usenix.org/system/files/usenixsecurity23-zhang-zhiyuan-slh.pdf ("Ultimate SLH: Taking Speculative Load Hardening to the Next Level - Section 5.1: Exploiting Secret-Dependent Control Flow")
On Fri, May 9, 2025 at 11:39 AM <patchwork-bot+netdevbpf@kernel.org> wrote: > > Hello: > > This series was applied to bpf/bpf-next.git (master) > by Alexei Starovoitov <ast@kernel.org>: > > On Thu, 1 May 2025 09:35:51 +0200 you wrote: > > This improves the expressiveness of unprivileged BPF by inserting > > speculation barriers instead of rejecting the programs. > > > > The approach was previously presented at LPC'24 [1] and RAID'24 [2]. > > > > To mitigate the Spectre v1 (PHT) vulnerability, the kernel rejects > > potentially-dangerous unprivileged BPF programs as of > > commit 9183671af6db ("bpf: Fix leakage under speculation on mispredicted > > branches"). In [2], we have analyzed 364 object files from open source > > projects (Linux Samples and Selftests, BCC, Loxilb, Cilium, libbpf > > Examples, Parca, and Prevail) and found that this affects 31% to 54% of > > programs. > > > > [...] > > Here is the summary with links: > - [bpf-next,v3,01/11] selftests/bpf: Fix caps for __xlated/jited_unpriv > https://git.kernel.org/bpf/bpf-next/c/cf15cdc0f0f3 > - [bpf-next,v3,02/11] bpf: Move insn if/else into do_check_insn() > (no matching commit) Applied the first patch only. Waiting for respin of the rest.
This improves the expressiveness of unprivileged BPF by inserting speculation barriers instead of rejecting the programs. The approach was previously presented at LPC'24 [1] and RAID'24 [2]. To mitigate the Spectre v1 (PHT) vulnerability, the kernel rejects potentially-dangerous unprivileged BPF programs as of commit 9183671af6db ("bpf: Fix leakage under speculation on mispredicted branches"). In [2], we have analyzed 364 object files from open source projects (Linux Samples and Selftests, BCC, Loxilb, Cilium, libbpf Examples, Parca, and Prevail) and found that this affects 31% to 54% of programs. To resolve this in the majority of cases this patchset adds a fall-back for mitigating Spectre v1 using speculation barriers. The kernel still optimistically attempts to verify all speculative paths but uses speculation barriers against v1 when unsafe behavior is detected. This allows for more programs to be accepted without disabling the BPF Spectre mitigations (e.g., by setting cpu_mitigations_off()). For this, it relies on the fact that speculation barriers prevent all later instructions if the speculation was not correct: * On x86_64, lfence acts as full speculation barrier, not only as a load fence [3]: An LFENCE instruction or a serializing instruction will ensure that no later instructions execute, even speculatively, until all prior instructions complete locally. [...] Inserting an LFENCE instruction after a bounds check prevents later operations from executing before the bound check completes. This was experimentally confirmed in [4]. * ARM's SB speculation barrier instruction also affects "any instruction that appears later in the program order than the barrier" [5]. In [1] we have measured the overhead of this approach relative to having mitigations off and including the upstream Spectre v4 mitigations. For event tracing and stack-sampling profilers, we found that mitigations increase BPF program execution time by 0% to 62%. For the Loxilb network load balancer, we have measured a 14% slowdown in SCTP performance but no significant slowdown for TCP. This overhead only applies to programs that were previously rejected. I reran the expressiveness-evaluation with v6.14 and made sure the main results still match those from [1] and [2] (which used v6.5). Main design decisions are: * Do not use separate bytecode insns for v1 and v4 barriers (inspired by Daniel Borkmann's question at LPC). This simplifies the verifier significantly and has the only downside that performance on PowerPC is not as high as it could be. * Allow archs to still disable v1/v4 mitigations separately by setting bpf_jit_bypass_spec_v1/v4(). This has the benefit that archs can benefit from improved BPF expressiveness / performance if they are not vulnerable (e.g., ARM64 for v4 in the kernel). * Do not remove the empty BPF_NOSPEC implementation for backends for which it is unknown whether they are vulnerable to Spectre v1. [1] https://lpc.events/event/18/contributions/1954/ ("Mitigating Spectre-PHT using Speculation Barriers in Linux eBPF") [2] https://arxiv.org/pdf/2405.00078 ("VeriFence: Lightweight and Precise Spectre Defenses for Untrusted Linux Kernel Extensions") [3] https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/technical-documentation/runtime-speculative-side-channel-mitigations.html ("Managed Runtime Speculative Execution Side Channel Mitigations") [4] https://dl.acm.org/doi/pdf/10.1145/3359789.3359837 ("Speculator: a tool to analyze speculative execution attacks and mitigations" - Section 4.6 "Stopping Speculative Execution") [5] https://developer.arm.com/documentation/ddi0597/2020-12/Base-Instructions/SB--Speculation-Barrier- ("SB - Speculation Barrier - Arm Armv8-A A32/T32 Instruction Set Architecture (2020-12)") Changes: * v2 -> v3: - Fix https://lore.kernel.org/oe-kbuild-all/202504212030.IF1SLhz6-lkp@intel.com/ and similar by moving the bpf_jit_bypass_spec_v1/v4() prototypes out of the #ifdef CONFIG_BPF_SYSCALL. Decided not to move them to filter.h (where similar bpf_jit_*() prototypes live) as they would still have to be duplicated in bpf.h to be usable to bpf_bypass_spec_v1/v4() (unless including filter.h in bpf.h is an option). - Fix https://lore.kernel.org/oe-kbuild-all/202504220035.SoGveGpj-lkp@intel.com/ by moving the variable declarations out of the switch-case. - Build touched C files with W=2 and bpf config on x86 to check that there are no other warnings introduced. - Found 3 more checkpatch warnings that can be fixed without degrading readability. - Rebase to bpf-next 2025-05-01 - Link to v2: https://lore.kernel.org/bpf/20250421091802.3234859-1-luis.gerhorst@fau.de/ * v1 -> v2: - Drop former commits 9 ("bpf: Return PTR_ERR from push_stack()") and 11 ("bpf: Fall back to nospec for spec path verification") as suggested by Alexei. This series therefore no longer changes push_stack() to return PTR_ERR. - Add detailed explanation of how lfence works internally and how it affects the algorithm. - Add tests checking that nospec instructions are inserted in expected locations using __xlated_unpriv as suggested by Eduard (also, include a fix for __xlated_unpriv) - Add a test for the mitigations from the description of commit 9183671af6db ("bpf: Fix leakage under speculation on mispredicted branches") - Remove unused variables from do_check[_insn]() as suggested by Eduard. - Remove INSN_IDX_MODIFIED to improve readability as suggested by Eduard. This also causes the nospec_result-check to run (and fail) for jumping-ops. Add a warning to assert that this check must never succeed in that case. - Add details on the safety of patch 10 ("bpf: Allow nospec-protected var-offset stack access") based on the feedback on v1. - Rebase to bpf-next-250420 - Link to v1: https://lore.kernel.org/all/20250313172127.1098195-1-luis.gerhorst@fau.de/ * RFC -> v1: - rebase to bpf-next-250313 - tests: mark expected successes/new errors - add bpt_jit_bypass_spec_v1/v4() to avoid #ifdef in bpf_bypass_spec_v1/v4() - ensure that nospec with v1-support is implemented for archs for which GCC supports speculation barriers, except for MIPS - arm64: emit speculation barrier - powerpc: change nospec to include v1 barrier - discuss potential security (archs that do not impl. BPF nospec) and performance (only PowerPC) regressions - Link to RFC: https://lore.kernel.org/bpf/20250224203619.594724-1-luis.gerhorst@fau.de/ Luis Gerhorst (11): selftests/bpf: Fix caps for __xlated/jited_unpriv bpf: Move insn if/else into do_check_insn() bpf: Return -EFAULT on misconfigurations bpf: Return -EFAULT on internal errors bpf, arm64, powerpc: Add bpf_jit_bypass_spec_v1/v4() bpf, arm64, powerpc: Change nospec to include v1 barrier bpf: Rename sanitize_stack_spill to nospec_result bpf: Fall back to nospec for Spectre v1 selftests/bpf: Add test for Spectre v1 mitigation bpf: Allow nospec-protected var-offset stack access bpf: Fall back to nospec for sanitization-failures arch/arm64/net/bpf_jit.h | 5 + arch/arm64/net/bpf_jit_comp.c | 28 +- arch/powerpc/net/bpf_jit_comp64.c | 80 ++- include/linux/bpf.h | 11 +- include/linux/bpf_verifier.h | 3 +- include/linux/filter.h | 2 +- kernel/bpf/core.c | 32 +- kernel/bpf/verifier.c | 653 ++++++++++-------- tools/testing/selftests/bpf/progs/bpf_misc.h | 4 + .../selftests/bpf/progs/verifier_and.c | 8 +- .../selftests/bpf/progs/verifier_bounds.c | 66 +- .../bpf/progs/verifier_bounds_deduction.c | 45 +- .../selftests/bpf/progs/verifier_map_ptr.c | 20 +- .../selftests/bpf/progs/verifier_movsx.c | 16 +- .../selftests/bpf/progs/verifier_unpriv.c | 65 +- .../bpf/progs/verifier_value_ptr_arith.c | 101 ++- tools/testing/selftests/bpf/test_loader.c | 14 +- .../selftests/bpf/verifier/dead_code.c | 3 +- tools/testing/selftests/bpf/verifier/jmp32.c | 33 +- tools/testing/selftests/bpf/verifier/jset.c | 10 +- 20 files changed, 771 insertions(+), 428 deletions(-) base-commit: 358b1c0f56ebb6996fcec7dcdcf6bae5dcbc8b6c