Message-ID: <e15dea4b-f6a5-a37d-1660-406bca5a0026@cs.fau.de>
Date:   Mon, 18 Sep 2023 13:52:29 +0200
From:   Luis Gerhorst <gerhorst@...fau.de>
To:     Yafang Shao <laoar.shao@...il.com>
Cc:     alexei.starovoitov@...il.com, andrii@...nel.org, ast@...nel.org,
        bpf@...r.kernel.org, daniel@...earbox.net, haoluo@...gle.com,
        john.fastabend@...il.com, jolsa@...nel.org, kpsingh@...nel.org,
        martin.lau@...ux.dev, sdf@...gle.com, song@...nel.org,
        yonghong.song@...ux.dev, mykolal@...com, shuah@...nel.org,
        gerhorst@...zon.de, iii@...ux.ibm.com,
        linux-kselftest@...r.kernel.org, linux-kernel@...r.kernel.org,
        Hagar Gamal Halim Hemdan <hagarhem@...zon.de>,
        Puranjay Mohan <puranjay12@...il.com>
Subject: Re: [PATCH 2/3] Revert "bpf: Fix issue in verifying allow_ptr_leaks"

On 15/09/2023 04:26, Yafang Shao wrote:
> On Wed, Sep 13, 2023 at 8:30 PM Luis Gerhorst <gerhorst@...zon.de> wrote:
>>
>> This reverts commit d75e30dddf73449bc2d10bb8e2f1a2c446bc67a2.
>>
>> To mitigate Spectre v1, the verifier relies on static analysis to deduct
>> constant pointer bounds, which can then be enforced by rewriting pointer
>> arithmetic [1] or index masking [2]. This relies on the fact that every
>> memory region to be accessed has a static upper bound and every date
>> below that bound is accessible. The verifier can only rewrite pointer
>> arithmetic or insert masking instructions to mitigate Spectre v1 if a
>> static upper bound, below of which every access is valid, can be given.
>>
>> When allowing packet pointer comparisons, this introduces a way for the
>> program to effectively construct an accessible pointer for which no
>> static upper bound is known. Intuitively, this is obvious as a packet
>> might be of any size and therefore 0 is the only statically known upper
>> bound below of which every date is always accessible (i.e., none).
>>
>> To clarify, the problem is not that comparing two pointers can be used
>> for pointer leaks in the same way in that comparing a pointer to a known
>> scalar can be used for pointer leaks. That is because the "secret"
>> components of the addresses cancel each other out if the pointers are
>> into the same region.
>>
>> With [3] applied, the following malicious BPF program can be loaded into
>> the kernel without CAP_PERFMON:
>>
>> r2 = *(u32 *)(r1 + 76) // data
>> r3 = *(u32 *)(r1 + 80) // data_end
>> r4 = r2
>> r4 += 1
>> if r4 > r3 goto exit
>> r5 = *(u8 *)(r2 + 0) // speculatively read secret
>> r5 &= 1 // choose bit to leak
>> // ... side channel to leak secret bit
>> exit:
>> // ...
>>
>> This is jited to the following amd64 code which still contains the
>> gadget:
>>
>>     0:   endbr64
>>     4:   nopl   0x0(%rax,%rax,1)
>>     9:   xchg   %ax,%ax
>>     b:   push   %rbp
>>     c:   mov    %rsp,%rbp
>>     f:   endbr64
>>    13:   push   %rbx
>>    14:   mov    0xc8(%rdi),%rsi // data
>>    1b:   mov    0x50(%rdi),%rdx // data_end
>>    1f:   mov    %rsi,%rcx
>>    22:   add    $0x1,%rcx
>>    26:   cmp    %rdx,%rcx
>>    29:   ja     0x000000000000003f // branch to mispredict
>>    2b:   movzbq 0x0(%rsi),%r8 // speculative load of secret
>>    30:   and    $0x1,%r8 // choose bit to leak
>>    34:   xor    %ebx,%ebx
>>    36:   cmp    %rbx,%r8
>>    39:   je     0x000000000000003f // branch based on secret
>>    3b:   imul   $0x61,%r8,%r8 // leak using port contention side channel
>>    3f:   xor    %eax,%eax
>>    41:   pop    %rbx
>>    42:   leaveq
>>    43:   retq
>>
>> Here I'm using a port contention side channel because storing the secret
>> to the stack causes the verifier to insert an lfence for unrelated
>> reasons (SSB mitigation) which would terminate the speculation.
>>
>> As Daniel already pointed out to me, data_end is even attacker
>> controlled as one could send many packets of sufficient length to train
>> the branch prediction into assuming data_end >= data will never be true.
>> When the attacker then sends a packet with insufficient data, the
>> Spectre v1 gadget leaks the chosen bit of some value that lies behind
>> data_end.
>>
>> To make it clear that the problem is not the pointer comparison but the
>> missing masking instruction, it can be useful to transform the code
>> above into the following equivalent pseudocode:
>>
>> r2 = data
>> r3 = data_end
>> r6 = ... // index to access, constant does not help
>> r7 = data_end - data // only known at runtime, could be [0,PKT_MAX)
>> if !(r6 < r7) goto exit
>> // no masking of index in r6 happens
>> r2 += r6 // addr. to access
>> r5 = *(u8 *)(r2 + 0) // speculatively read secret
>> // ... leak secret as above
>>
>> One idea to resolve this while still allowing for unprivileged packet
>> access would be to always allocate a power of 2 for the packet data and
>> then also pass the respective index mask in the skb structure. The
>> verifier would then have to check that this index mask is always applied
>> to the offset before a packet pointer is dereferenced. This patch does
>> not implement this extension, but only reverts [3].
> 
> Hi Luis,
> 
> The skb pointer comparison is a reasonable operation in a networking bpf prog.
> If we just prohibit a reasonable operation to prevent a possible
> spectre v1 attack, it looks a little weird, right ?
> Should we figure out a real fix to prevent it ?
> 

I see your point, but this has been the case since Spectre v1 was 
mitigated for BPF. I actually did a few statistics on that in [1] and 
 >50 out of ~350 programs are rejected because of the Spectre v1 
mitigations. However, to repeat: The operation is not completely 
prohibited, only prohibited without CAP_PERFMON.

Maybe it would be possible to expose the allow_ptr_leaks/bpf_spec_vX 
flags in sysfs? It would be helpful for debugging, and you could set it 
to 1 permanently for your purposes. However, I'm not sure if the others 
would like that...

Another solution I have been working on in [2] is to change the 
mitigations to insert an lfence instead of rejecting the program 
entirely. That would have bad performance, but would still be better 
than completely rejecting the program. However, these patches are far 
from going upstream currently.

A detail: The patches in [2] currently do not support the case we are 
discussing here, they only insert fences when the speculative paths fail 
to verify.

[1] 
https://sys.cs.fau.de/extern/person/gerhorst/23-03_fgbs-spring-2023-presentation.pdf 
- Slide 9
[2] 
https://gitlab.cs.fau.de/un65esoq/linux/-/commits/v6.5-rc6-bpf-spectre-nospec/

-- 
Luis

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

Powered by blists - more mailing lists