To mitigate Spectre v4, 2039f26f3aca ("bpf: Fix leakage due to
insufficient speculative store bypass mitigation") inserts lfence
instructions after 1) initializing a stack slot and 2) spilling a
pointer to the stack.
However, this does not cover cases where a stack slot is first
initialized with a pointer (subject to sanitization) but then
overwritten with a scalar (not subject to sanitization because the slot
was already initialized). In this case, the second write may be subject
to speculative store bypass (SSB) creating a speculative
pointer-as-scalar type confusion. This allows the program to
subsequently leak the numerical pointer value using, for example, a
branch-based cache side channel.
To fix this, also sanitize scalars if they write a stack slot that
previously contained a pointer. Assuming that pointer-spills are only
generated by LLVM on register-pressure, the performance impact on most
real-world BPF programs should be small.
The following unprivileged BPF bytecode drafts a minimal exploit and the
mitigation:
[...]
// r6 = 0 or 1 (skalar, unknown user input)
// r7 = accessible ptr for side channel
// r10 = frame pointer (fp), to be leaked
//
r9 = r10 # fp alias to encourage ssb
*(u64 *)(r9 - 8) = r10 // fp[-8] = ptr, to be leaked
// lfence added here because of pointer spill to stack.
//
// Ommitted: Dummy bpf_ringbuf_output() here to train alias predictor
// for no r9-r10 dependency.
//
*(u64 *)(r10 - 8) = r6 // fp[-8] = scalar, overwrites ptr
// 2039f26f3aca: no lfence added because stack slot was not STACK_INVALID,
// store may be subject to SSB
//
// fix: also add an lfence when the slot contained a ptr
//
r8 = *(u64 *)(r9 - 8)
// r8 = architecturally a scalar, speculatively a ptr
//
// leak ptr using branch-based cache side channel:
r8 &= 1 // choose bit to leak
if r8 == 0 goto SLOW // no mispredict
// architecturally dead code if input r6 is 0,
// only executes speculatively iff ptr bit is 1
r8 = *(u64 *)(r7 + 0) # encode bit in cache (0: slow, 1: fast)
SLOW:
[...]
After running this, the program can time the access to *(r7 + 0) to
determine whether the chosen pointer bit was 0 or 1. Repeat this 64
times to recover the whole address on amd64.
In summary, sanitization can only be skipped if one scalar is
overwritten with another scalar. Scalar-confusion due to speculative
store bypass can not lead to invalid accesses because the pointer bounds
deducted during verification are enforced using branchless logic. See
979d63d50c0c ("bpf: prevent out of bounds speculation on pointer
arithmetic") for details.
Do not make the mitigation depend on
!env->allow_{uninit_stack,ptr_leaks} because speculative leaks are
likely unexpected if these were enabled. For example, leaking the
address to a protected log file may be acceptable while disabling the
mitigation might unintentionally leak the address into the cached-state
of a map that is accessible to unprivileged processes.
Fixes: 2039f26f3aca ("bpf: Fix leakage due to insufficient speculative store bypass mitigation")
Signed-off-by: Luis Gerhorst <[email protected]>
Acked-by: Henriette Hofmeier <[email protected]>
---
kernel/bpf/verifier.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a5255a0dcbb6..5e3aa4a75bd6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3287,7 +3287,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
bool sanitize = reg && is_spillable_regtype(reg->type);
for (i = 0; i < size; i++) {
- if (state->stack[spi].slot_type[i] == STACK_INVALID) {
+ u8 type = state->stack[spi].slot_type[i];
+ if (type != STACK_MISC && type != STACK_ZERO) {
sanitize = true;
break;
}
--
2.34.1
On Mon, Jan 9, 2023 at 7:07 AM Luis Gerhorst <[email protected]> wrote:
>
> To mitigate Spectre v4, 2039f26f3aca ("bpf: Fix leakage due to
> insufficient speculative store bypass mitigation") inserts lfence
> instructions after 1) initializing a stack slot and 2) spilling a
> pointer to the stack.
>
> However, this does not cover cases where a stack slot is first
> initialized with a pointer (subject to sanitization) but then
> overwritten with a scalar (not subject to sanitization because the slot
> was already initialized). In this case, the second write may be subject
> to speculative store bypass (SSB) creating a speculative
> pointer-as-scalar type confusion. This allows the program to
> subsequently leak the numerical pointer value using, for example, a
> branch-based cache side channel.
>
> To fix this, also sanitize scalars if they write a stack slot that
> previously contained a pointer. Assuming that pointer-spills are only
> generated by LLVM on register-pressure, the performance impact on most
> real-world BPF programs should be small.
>
> The following unprivileged BPF bytecode drafts a minimal exploit and the
> mitigation:
>
> [...]
> // r6 = 0 or 1 (skalar, unknown user input)
> // r7 = accessible ptr for side channel
> // r10 = frame pointer (fp), to be leaked
> //
> r9 = r10 # fp alias to encourage ssb
> *(u64 *)(r9 - 8) = r10 // fp[-8] = ptr, to be leaked
> // lfence added here because of pointer spill to stack.
> //
> // Ommitted: Dummy bpf_ringbuf_output() here to train alias predictor
> // for no r9-r10 dependency.
> //
> *(u64 *)(r10 - 8) = r6 // fp[-8] = scalar, overwrites ptr
> // 2039f26f3aca: no lfence added because stack slot was not STACK_INVALID,
> // store may be subject to SSB
> //
> // fix: also add an lfence when the slot contained a ptr
> //
> r8 = *(u64 *)(r9 - 8)
> // r8 = architecturally a scalar, speculatively a ptr
> //
> // leak ptr using branch-based cache side channel:
> r8 &= 1 // choose bit to leak
> if r8 == 0 goto SLOW // no mispredict
> // architecturally dead code if input r6 is 0,
> // only executes speculatively iff ptr bit is 1
> r8 = *(u64 *)(r7 + 0) # encode bit in cache (0: slow, 1: fast)
> SLOW:
> [...]
>
> After running this, the program can time the access to *(r7 + 0) to
> determine whether the chosen pointer bit was 0 or 1. Repeat this 64
> times to recover the whole address on amd64.
>
> In summary, sanitization can only be skipped if one scalar is
> overwritten with another scalar. Scalar-confusion due to speculative
> store bypass can not lead to invalid accesses because the pointer bounds
> deducted during verification are enforced using branchless logic. See
> 979d63d50c0c ("bpf: prevent out of bounds speculation on pointer
> arithmetic") for details.
>
> Do not make the mitigation depend on
> !env->allow_{uninit_stack,ptr_leaks} because speculative leaks are
> likely unexpected if these were enabled. For example, leaking the
> address to a protected log file may be acceptable while disabling the
> mitigation might unintentionally leak the address into the cached-state
> of a map that is accessible to unprivileged processes.
>
> Fixes: 2039f26f3aca ("bpf: Fix leakage due to insufficient speculative store bypass mitigation")
All makes sense to me.
Daniel,
please take a look.
> Signed-off-by: Luis Gerhorst <[email protected]>
> Acked-by: Henriette Hofmeier <[email protected]>
> ---
> kernel/bpf/verifier.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a5255a0dcbb6..5e3aa4a75bd6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3287,7 +3287,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> bool sanitize = reg && is_spillable_regtype(reg->type);
>
> for (i = 0; i < size; i++) {
> - if (state->stack[spi].slot_type[i] == STACK_INVALID) {
> + u8 type = state->stack[spi].slot_type[i];
> + if (type != STACK_MISC && type != STACK_ZERO) {
> sanitize = true;
> break;
> }
> --
> 2.34.1
>
On 1/9/23 4:05 PM, Luis Gerhorst wrote:
> To mitigate Spectre v4, 2039f26f3aca ("bpf: Fix leakage due to
> insufficient speculative store bypass mitigation") inserts lfence
> instructions after 1) initializing a stack slot and 2) spilling a
> pointer to the stack.
>
> However, this does not cover cases where a stack slot is first
> initialized with a pointer (subject to sanitization) but then
> overwritten with a scalar (not subject to sanitization because the slot
> was already initialized). In this case, the second write may be subject
> to speculative store bypass (SSB) creating a speculative
> pointer-as-scalar type confusion. This allows the program to
> subsequently leak the numerical pointer value using, for example, a
> branch-based cache side channel.
>
> To fix this, also sanitize scalars if they write a stack slot that
> previously contained a pointer. Assuming that pointer-spills are only
> generated by LLVM on register-pressure, the performance impact on most
> real-world BPF programs should be small.
>
> The following unprivileged BPF bytecode drafts a minimal exploit and the
> mitigation:
>
> [...]
> // r6 = 0 or 1 (skalar, unknown user input)
> // r7 = accessible ptr for side channel
> // r10 = frame pointer (fp), to be leaked
> //
> r9 = r10 # fp alias to encourage ssb
> *(u64 *)(r9 - 8) = r10 // fp[-8] = ptr, to be leaked
> // lfence added here because of pointer spill to stack.
> //
> // Ommitted: Dummy bpf_ringbuf_output() here to train alias predictor
> // for no r9-r10 dependency.
> //
> *(u64 *)(r10 - 8) = r6 // fp[-8] = scalar, overwrites ptr
> // 2039f26f3aca: no lfence added because stack slot was not STACK_INVALID,
> // store may be subject to SSB
> //
> // fix: also add an lfence when the slot contained a ptr
> //
> r8 = *(u64 *)(r9 - 8)
> // r8 = architecturally a scalar, speculatively a ptr
> //
> // leak ptr using branch-based cache side channel:
> r8 &= 1 // choose bit to leak
> if r8 == 0 goto SLOW // no mispredict
> // architecturally dead code if input r6 is 0,
> // only executes speculatively iff ptr bit is 1
> r8 = *(u64 *)(r7 + 0) # encode bit in cache (0: slow, 1: fast)
> SLOW:
> [...]
>
> After running this, the program can time the access to *(r7 + 0) to
> determine whether the chosen pointer bit was 0 or 1. Repeat this 64
> times to recover the whole address on amd64.
>
> In summary, sanitization can only be skipped if one scalar is
> overwritten with another scalar. Scalar-confusion due to speculative
> store bypass can not lead to invalid accesses because the pointer bounds
> deducted during verification are enforced using branchless logic. See
> 979d63d50c0c ("bpf: prevent out of bounds speculation on pointer
> arithmetic") for details.
>
> Do not make the mitigation depend on
> !env->allow_{uninit_stack,ptr_leaks} because speculative leaks are
> likely unexpected if these were enabled. For example, leaking the
> address to a protected log file may be acceptable while disabling the
> mitigation might unintentionally leak the address into the cached-state
> of a map that is accessible to unprivileged processes.
>
> Fixes: 2039f26f3aca ("bpf: Fix leakage due to insufficient speculative store bypass mitigation")
> Signed-off-by: Luis Gerhorst <[email protected]>
> Acked-by: Henriette Hofmeier <[email protected]>
This looks good to me, thank you for the research on this topic! Applied
to bpf tree. (I've also added a link tag to your other mail.)
https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf.git/commit/?id=e4f4db47794c9f474b184ee1418f42e6a07412b6
Thanks,
Daniel