Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Mark Rutland]

Hi Alexei,

On Thu, Jan 04, 2018 at 08:28:11PM -0800, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Under speculation, CPUs may mis-predict branches in bounds checks. Thus,
> memory accesses under a bounds check may be speculated even if the
> bounds check fails, providing a primitive for building a side channel.
> 
> To avoid leaking kernel data round up array-based maps and mask the index
> after bounds check, so speculated load with out of bounds index will load
> either valid value from the array or zero from the padded area.

This is on my radar, and I'll try to review / test this next week.

Thanks,
Mark.

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Mark Rutland]

Hi Alexei,

On Thu, Jan 04, 2018 at 08:28:11PM -0800, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> Under speculation, CPUs may mis-predict branches in bounds checks. Thus,
> memory accesses under a bounds check may be speculated even if the
> bounds check fails, providing a primitive for building a side channel.
> 
> To avoid leaking kernel data round up array-based maps and mask the index
> after bounds check, so speculated load with out of bounds index will load
> either valid value from the array or zero from the padded area.

Thanks for putting this together, this certainly looks neat.

I'm a little worried that in the presence of some CPU/compiler
optimisations, the masking may effectively be skipped under speculation.
So I'm not sure how robust this is going to be.

More on that below.

> To avoid duplicating map_lookup functions for root/unpriv always generate
> a sequence of bpf instructions equivalent to map_lookup function for
> array and array_of_maps map types when map was created by unpriv user.
> And unconditionally mask index for percpu_array, since it's fast enough,
> even when max_entries are not rounded to power of 2 for root user,
> since percpu_array doesn't have map_gen_lookup callback yet.

Is there a noticeable slowdown from the masking? Can't we always have
that in place?

> @@ -157,7 +175,7 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key)
>  	if (unlikely(index >= array->map.max_entries))
>  		return NULL;
>  
> -	return this_cpu_ptr(array->pptrs[index]);
> +	return this_cpu_ptr(array->pptrs[index & array->index_mask]);

As above, I think this isn't necessarily robust, as CPU/compiler
optimisations can break the dependency on the index_mask, allowing
speculation without a mask.

e.g. a compiler could re-write this as:

	if (array->index_mask != 0xffffffff)
		index &= array->index_mask;
	return this_cpu_ptr(array->pptrs[index]);

... which would allow an unmasked index to be used in speculated paths.

Similar cases could occur with some CPU implementations. For example, HW
value-prediction could result in the use of an all-ones mask under
speculation.

I think that we may need to be able to provide an arch-specific
pointer sanitization sequence (though we could certainly have masking as
the default).

I have a rough idea as to how that could be plumbed into the JIT. First
I need to verify the sequence I have in mind for arm/arm64 is
sufficient.

Thanks,
Mark.

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Linus Torvalds]

On Mon, Jan 8, 2018 at 9:05 AM, Mark Rutland <mark.rutland@arm.com> wrote:
>
> I'm a little worried that in the presence of some CPU/compiler
> optimisations, the masking may effectively be skipped under speculation.
> So I'm not sure how robust this is going to be.

Honestly, I think the masking is a hell of a lot more robust than any
of the "official" fixes.

More generic data speculation (as opposed to control speculation) is

 (a) mainly academic masturbation

 (b) hasn't even been shown to be a good idea even in _theory_ yet
(except for the "completely unreal hardware" kind of theory where
people assume some data oracle)

 (c) isn't actually done in any real CPU's today that I'm aware of
(unless you want to call the return stack data speculation).

and the thing is, we should really not then worry about "... but maybe
future CPU's will be more aggressive", which is the traditional worry
in these kinds of cases.

Why? Because quite honestly, any future CPU's that are more aggressive
about speculating things like this are broken shit that we should call
out as such, and tell people not to use.

Seriously.

In this particular case, we should be very much aware of future CPU's
being more _constrained_, because CPU vendors had better start taking
this thing into account.

So the masking approach is FUNDAMENTALLY SAFER than the "let's try to
limit control speculation".

If somebody can point to a CPU that actually speculates across an
address masking operation, I will be very surprised. And unless you
can point to that, then stop trying to dismiss the masking approach.

The only thing we need to be really really careful about is to make
sure that the mask generation itself is not in a control speculation
path.

IOW, the mask really has to be a true data dependency, and has to be
generated arithmetically. Because if the mask generation has a control
dependency on it, then obviously that defeats the whole "make sure we
don't have control speculation" approach.

                   Linus

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Will Deacon]

Hi Linus,

On Mon, Jan 08, 2018 at 10:49:01AM -0800, Linus Torvalds wrote:
> On Mon, Jan 8, 2018 at 9:05 AM, Mark Rutland <mark.rutland@arm.com> wrote:
> >
> > I'm a little worried that in the presence of some CPU/compiler
> > optimisations, the masking may effectively be skipped under speculation.
> > So I'm not sure how robust this is going to be.
> 
> Honestly, I think the masking is a hell of a lot more robust than any
> of the "official" fixes.
> 
> More generic data speculation (as opposed to control speculation) is
> 
>  (a) mainly academic masturbation
> 
>  (b) hasn't even been shown to be a good idea even in _theory_ yet
> (except for the "completely unreal hardware" kind of theory where
> people assume some data oracle)
> 
>  (c) isn't actually done in any real CPU's today that I'm aware of
> (unless you want to call the return stack data speculation).
> 
> and the thing is, we should really not then worry about "... but maybe
> future CPU's will be more aggressive", which is the traditional worry
> in these kinds of cases.
> 
> Why? Because quite honestly, any future CPU's that are more aggressive
> about speculating things like this are broken shit that we should call
> out as such, and tell people not to use.
> 
> Seriously.
> 
> In this particular case, we should be very much aware of future CPU's
> being more _constrained_, because CPU vendors had better start taking
> this thing into account.
> 
> So the masking approach is FUNDAMENTALLY SAFER than the "let's try to
> limit control speculation".
> 
> If somebody can point to a CPU that actually speculates across an
> address masking operation, I will be very surprised. And unless you
> can point to that, then stop trying to dismiss the masking approach.

Whilst I agree with your comments about future CPUs, this stuff is further
out of academia than you might think. We're definitely erring on the
belt-and-braces side of things at the moment, so let me go check what's
*actually* been built and I suspect we'll be able to make the masking work.

Stay tuned...

Will

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Will Deacon]

Hi again Linus, Alexei,

On Tue, Jan 09, 2018 at 10:21:29AM +0000, Will Deacon wrote:
> On Mon, Jan 08, 2018 at 10:49:01AM -0800, Linus Torvalds wrote:
> > In this particular case, we should be very much aware of future CPU's
> > being more _constrained_, because CPU vendors had better start taking
> > this thing into account.
> > 
> > So the masking approach is FUNDAMENTALLY SAFER than the "let's try to
> > limit control speculation".
> > 
> > If somebody can point to a CPU that actually speculates across an
> > address masking operation, I will be very surprised. And unless you
> > can point to that, then stop trying to dismiss the masking approach.
> 
> Whilst I agree with your comments about future CPUs, this stuff is further
> out of academia than you might think. We're definitely erring on the
> belt-and-braces side of things at the moment, so let me go check what's
> *actually* been built and I suspect we'll be able to make the masking work.
> 
> Stay tuned...

I can happily confirm that there aren't any (ARM architecture) CPUs where
the masking approach is not sufficient, so there's no need to worry about
value speculation breaking this.

Will

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Alexei Starovoitov]

On 1/10/18 11:47 AM, Will Deacon wrote:
> Hi again Linus, Alexei,
>
> I can happily confirm that there aren't any (ARM architecture) CPUs where
> the masking approach is not sufficient, so there's no need to worry about
> value speculation breaking this.

Awesome! Thank you for confirming.

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Will Deacon]

Hi all,

On Wed, Jan 10, 2018 at 07:47:33PM +0000, Will Deacon wrote:
> On Tue, Jan 09, 2018 at 10:21:29AM +0000, Will Deacon wrote:
> > On Mon, Jan 08, 2018 at 10:49:01AM -0800, Linus Torvalds wrote:
> > > In this particular case, we should be very much aware of future CPU's
> > > being more _constrained_, because CPU vendors had better start taking
> > > this thing into account.
> > > 
> > > So the masking approach is FUNDAMENTALLY SAFER than the "let's try to
> > > limit control speculation".
> > > 
> > > If somebody can point to a CPU that actually speculates across an
> > > address masking operation, I will be very surprised. And unless you
> > > can point to that, then stop trying to dismiss the masking approach.
> > 
> > Whilst I agree with your comments about future CPUs, this stuff is further
> > out of academia than you might think. We're definitely erring on the
> > belt-and-braces side of things at the moment, so let me go check what's
> > *actually* been built and I suspect we'll be able to make the masking work.
> > 
> > Stay tuned...
> 
> I can happily confirm that there aren't any (ARM architecture) CPUs where
> the masking approach is not sufficient, so there's no need to worry about
> value speculation breaking this.

Unfortunately, thanks to some internal miscommunication, my previous assertion
that no implementations of the Armv8 architecture utilise data value prediction
has turned out to be incorrect. I received confirmation last week that this has
been deployed in production silicon and has shipped widely in various products,
so the horse really has bolted and this isn't confined to academia as was
suggested previously.

We're still investigating whether this affects the mask-based mitigation used
by eBPF, but we'll definitely be adding a CSDB-based sequence to our nospec
helpers to ensure that array_index_nospec is robust for arm64: the CSDB
instruction follows the generation of the mask (see patches at [1]).

In the meantime, I wanted to correct my previous claim in case anybody else
is using that as a basis to push ahead with the bare masking approach
elsewhere for arm64.

Sorry for the confusion,

Will

[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2018-February/557825.html

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Mark Rutland]

On Mon, Jan 08, 2018 at 10:49:01AM -0800, Linus Torvalds wrote:
> On Mon, Jan 8, 2018 at 9:05 AM, Mark Rutland <mark.rutland@arm.com> wrote:
> >
> > I'm a little worried that in the presence of some CPU/compiler
> > optimisations, the masking may effectively be skipped under speculation.
> > So I'm not sure how robust this is going to be.
> 
> Honestly, I think the masking is a hell of a lot more robust than any
> of the "official" fixes.
> 
> More generic data speculation (as opposed to control speculation) is

>  (c) isn't actually done in any real CPU's today that I'm aware of
> (unless you want to call the return stack data speculation).

Maybe not generally, but the GPZ writeup claims that when a load that
misses in the cache, some CPUs speculate the value (as all-zeroes).

See "Variant 3: Rogue data cache load" in:

  https://googleprojectzero.blogspot.co.uk/2018/01/reading-privileged-memory-with-side.html

If a CPU speculates a load of a mask as all-zeroes, we're fine. If a CPU
can speculate the load of a mask as all-ones, the AND is effectively a
NOP.

I'll wait for Will to find out what's actually been built...

Thanks,
Mark.

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Alan Cox]

>  (c) isn't actually done in any real CPU's today that I'm aware of
> (unless you want to call the return stack data speculation).

There are processors out there today that data speculate.

For Intel family 6 Core, Knights and Atom today all is good.

Alan

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Alexei Starovoitov]

On 1/8/18 9:05 AM, Mark Rutland wrote:
> Hi Alexei,
>
> On Thu, Jan 04, 2018 at 08:28:11PM -0800, Alexei Starovoitov wrote:
>> From: Alexei Starovoitov <ast@kernel.org>
>>
>> Under speculation, CPUs may mis-predict branches in bounds checks. Thus,
>> memory accesses under a bounds check may be speculated even if the
>> bounds check fails, providing a primitive for building a side channel.
>>
>> To avoid leaking kernel data round up array-based maps and mask the index
>> after bounds check, so speculated load with out of bounds index will load
>> either valid value from the array or zero from the padded area.
>
> Thanks for putting this together, this certainly looks neat.
>
> I'm a little worried that in the presence of some CPU/compiler
> optimisations, the masking may effectively be skipped under speculation.
> So I'm not sure how robust this is going to be.
>
> More on that below.
>
>> To avoid duplicating map_lookup functions for root/unpriv always generate
>> a sequence of bpf instructions equivalent to map_lookup function for
>> array and array_of_maps map types when map was created by unpriv user.
>> And unconditionally mask index for percpu_array, since it's fast enough,
>> even when max_entries are not rounded to power of 2 for root user,
>> since percpu_array doesn't have map_gen_lookup callback yet.
>
> Is there a noticeable slowdown from the masking? Can't we always have
> that in place?

right. Please see v3 version:
https://patchwork.ozlabs.org/patch/856645/
Daniel noticed that speculation can happen without program being
loaded and we need to tighten the path via syscall as well.
so v3 is doing masking for all array types unconditionally.
The perf cost is within noise for interpreter and
not seen with JITed root code, since gen_lookup does not
emit AND for root.

>> @@ -157,7 +175,7 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key)
>>  	if (unlikely(index >= array->map.max_entries))
>>  		return NULL;
>>
>> -	return this_cpu_ptr(array->pptrs[index]);
>> +	return this_cpu_ptr(array->pptrs[index & array->index_mask]);
>
> As above, I think this isn't necessarily robust, as CPU/compiler
> optimisations can break the dependency on the index_mask, allowing
> speculation without a mask.
>
> e.g. a compiler could re-write this as:
>
> 	if (array->index_mask != 0xffffffff)
> 		index &= array->index_mask;
> 	return this_cpu_ptr(array->pptrs[index]);
>
> ... which would allow an unmasked index to be used in speculated paths.

prior to kernel I've been working on sun, gcc, llvm compilers
and I've never seen such optimization ever proposed for AND.
It makes no sense.

For heavy ALU like div/mod and calls compiler does indeed try
to predict the value. de-virtualization is an example optimization
for indirect calls. Intel compiler pioneered this approach back in 2000.

Compilers can also optimize "div by X" into
if (x == const)
   unroll div by const into something faster;
else
   div by X

Such optimizations are rarely done without profile feedback,
since branch is costly the compiler will add a branch only if there
is a clear win from introducing it instead of doing the operation.
For and, or, shift, add, sub there is never a case to do so.
Instead compiler is always trying to remove branches instead of
introducing them.

> Similar cases could occur with some CPU implementations. For example, HW
> value-prediction could result in the use of an all-ones mask under
> speculation.

please see the paper that Alan mentioned.
HW value speculation predicts likely valid values. It makes no sense
for HW to continue speculative execution with random value.
Consider array[index & index_mask]
if load index_mask stalls and cpu decides to continue speculation with
random value (both zero and ffff are considered random) it will proceed
through AND and second load will populate the precious cache
with completely irrelevant data.
Such cpu will be slower with speculative execution than without,
since it populates the caches with random data.

> I think that we may need to be able to provide an arch-specific
> pointer sanitization sequence (though we could certainly have masking as
> the default).

I still don't understand where this paranoia is coming from.
Kernel doesn't need to kill speculation. It needs to manage it.

> I have a rough idea as to how that could be plumbed into the JIT. First
> I need to verify the sequence I have in mind for arm/arm64 is
> sufficient.

hmm? the patch provided (both v2 and v3) doesn't need any JIT changes
on either x64, arm, etc.
gen_lookup() emits BPF_AND on index that JIT converts into actual AND
in native instruction set.

Re: [PATCH bpf] bpf: prevent out-of-bounds speculation

[Alan Cox]

> That fixes bpf side of "Variant 1: bounds check bypass (CVE-2017-
> 5753)" on
> all architectures with and without JIT.

For Intel we believe this is true for all family 6 Core, Atom and
Knights processors. If that ceases to be the case in future then Intel
will provide guidance beforehand.

For non x86 you need to check what level of data speculation anyone is
doing. I know some Power did data speculation. Your statement may well
be true but it would be nice to see AMD, ARM, Power, Sparc etc acks on
it.

Alan