From: Eric W. Biederman <hidden> Date: 2018-01-09 03:12:48
Dan Williams [off-list ref] writes:
Static analysis reports that 'index' may be a user controlled value that
is used as a data dependency reading 'rt' from the 'platform_label'
array. In order to avoid potential leaks of kernel memory values, block
speculative execution of the instruction stream that could issue further
reads based on an invalid 'rt' value.
In detail.
a) This code is fast path packet forwarding code. Introducing an
unconditional pipeline stall is not ok.
AKA either there is no speculation and so this is invulnerable
or there is speculation and you are creating an unconditional
pipeline stall here.
My back of the napkin caluculations say that a pipeline stall
is about 20 cycles. Which is about the same length of time
as a modern cache miss.
On a good day this code will perform with 0 cache misses. On a less
good day 1 cache miss. Which means you are quite possibly doubling
the runtime of mpls_forward.
b) The array is dynamically allocated which should provide some
protection, as it will be more difficult to predict the address
of the array which is needed to craft an malicious userspace value.
c) The code can be trivially modified to say:
static struct mpls_route *mpls_route_input_rcu(struct net *net, unsigned index)
{
struct mpls_route *rt = NULL;
if (index < net->mpls.platform_labels) {
struct mpls_route __rcu **platform_label =
rcu_dereference(net->mpls.platform_label);
rt = rcu_dereference(platform_label[index & ((1 << 20) - 1)]);
}
return rt;
}
AKA a static mask will ensure that there is not a primitive that can be
used to access all of memory. That is max a 1 cycle slowdown in the
code, which is a much better trade off.
d) If we care more it is straight forward to modify
resize_platform_label_table() to ensure that the size of the array
is always a power of 2.
e) The fact that a pointer is returned from the array and it is treated
like a pointer would seem to provide a defense against the
exfiltration technique of using the value read as an index into
a small array, that user space code can probe aliased cached
lines of, to see which value was dereferenced.
So to this patch in particular.
Nacked-by: "Eric W. Biederman" [off-list ref]
This code path will be difficult to exploit. This change messes with
performance. There are ways to make this code path useless while
preserving the performance of the code.
Eric
quoted hunk
Based on an original patch by Elena Reshetova.
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Eric W. Biederman <redacted>
Cc: netdev@vger.kernel.org
Signed-off-by: Elena Reshetova <elena.reshetova@intel.com>
Signed-off-by: Dan Williams <redacted>
---
net/mpls/af_mpls.c | 12 +++++++-----
1 file changed, 7 insertions(+), 5 deletions(-)
From: Dan Williams <hidden> Date: 2018-01-09 03:42:33
On Mon, Jan 8, 2018 at 7:11 PM, Eric W. Biederman [off-list ref] wrote:
Dan Williams [off-list ref] writes:
quoted
Static analysis reports that 'index' may be a user controlled value that
is used as a data dependency reading 'rt' from the 'platform_label'
array. In order to avoid potential leaks of kernel memory values, block
speculative execution of the instruction stream that could issue further
reads based on an invalid 'rt' value.
In detail.
a) This code is fast path packet forwarding code. Introducing an
unconditional pipeline stall is not ok.
AKA either there is no speculation and so this is invulnerable
or there is speculation and you are creating an unconditional
pipeline stall here.
My back of the napkin caluculations say that a pipeline stall
is about 20 cycles. Which is about the same length of time
as a modern cache miss.
On a good day this code will perform with 0 cache misses. On a less
good day 1 cache miss. Which means you are quite possibly doubling
the runtime of mpls_forward.
b) The array is dynamically allocated which should provide some
protection, as it will be more difficult to predict the address
of the array which is needed to craft an malicious userspace value.
c) The code can be trivially modified to say:
static struct mpls_route *mpls_route_input_rcu(struct net *net, unsigned index)
{
struct mpls_route *rt = NULL;
if (index < net->mpls.platform_labels) {
struct mpls_route __rcu **platform_label =
rcu_dereference(net->mpls.platform_label);
rt = rcu_dereference(platform_label[index & ((1 << 20) - 1)]);
}
return rt;
}
AKA a static mask will ensure that there is not a primitive that can be
used to access all of memory. That is max a 1 cycle slowdown in the
code, which is a much better trade off.
d) If we care more it is straight forward to modify
resize_platform_label_table() to ensure that the size of the array
is always a power of 2.
e) The fact that a pointer is returned from the array and it is treated
like a pointer would seem to provide a defense against the
exfiltration technique of using the value read as an index into
a small array, that user space code can probe aliased cached
lines of, to see which value was dereferenced.
So to this patch in particular.
Nacked-by: "Eric W. Biederman" [off-list ref]
This code path will be difficult to exploit. This change messes with
performance. There are ways to make this code path useless while
preserving the performance of the code.
Thanks, Eric understood. The discussion over the weekend came to the
conclusion that using a mask will be the default approach. The
nospec_array_ptr() will be defined to something similar to the
following, originally from Linus and tweaked by Alexei and I:
#define __nospec_array_ptr(base, idx, sz) \
({ \
union { typeof(&base[0]) _ptr; unsigned long _bit; } __u; \
unsigned long _i = (idx); \
unsigned long _m = (max); \
unsigned long _mask = ~(long)(_m - 1 - _i) >> BITS_PER_LONG - 1;\
OPTIMIZER_HIDE_VAR(_mask); \
__u._ptr = &base[_i & _mask]; \
__u._bit &= _mask; \
__u._ptr; \
})
Does that address your performance concerns?
Why?
Because "(long)(_m-1-_i)" is not negative just because "i >= m". It
can still be positive.
Think "m = 100", "i=bignum". The subtraction will overflow and become
positive again, the shift will shift to zero, and then the mask will
become ~0.
Now, you can fix it, but you need to be a tiny bit more clever. In
particular, just make sure that you retain the high bit of "_i",
basically making the rule be that a negative index is not ever valid.
And then instead of "(_m - 1 - _i)", you use "(_i | (_m - 1 - _i))".
Now the sign bit is set if _i had it set, _or_ if the subtraction
turned negative, and you don't have to worry about the overflow
situation.
But it does require that extra step to be trustworthy. Still purely
cheap arithmetic operations, although there is possibly some
additional register pressure there.
Somebody might be able to come up with something even more minimal (or
find a fault in my fix of your tweak).
Obviously, with architecture-specific code, you may well be able to do
better, using the carry flag of the subtraction.
For example, on x86, I think you could do it with just two instructions:
# carry will be clear if idx >= max
cmpq %idx,%max
# mask will be clear if carry was clear, ~0 otherwise
sbbq %mask,%mask
to generate mask directly. I might have screwed that up. Worth perhaps trying?
Linus
On Mon, Jan 8, 2018 at 8:13 PM, Linus Torvalds
[off-list ref] wrote:
# carry will be clear if idx >= max
cmpq %idx,%max
Bah. Other way around.
cmpq %max,%idx
I'm a moron.
# mask will be clear if carry was clear, ~0 otherwise
sbbq %mask,%mask
to generate mask directly. I might have screwed that up. Worth perhaps trying?
More importantly, worth _testing_ and fixing my hand-waving "asm like
this" crap.
But I do think that simple two-instruction cmpq/sbbq sequence could
get it right in just two trivial ALU instructions.
Linus
Why?
Because "(long)(_m-1-_i)" is not negative just because "i >= m". It
can still be positive.
Think "m = 100", "i=bignum". The subtraction will overflow and become
positive again, the shift will shift to zero, and then the mask will
become ~0.
Now, you can fix it, but you need to be a tiny bit more clever. In
particular, just make sure that you retain the high bit of "_i",
basically making the rule be that a negative index is not ever valid.
And then instead of "(_m - 1 - _i)", you use "(_i | (_m - 1 - _i))".
Now the sign bit is set if _i had it set, _or_ if the subtraction
turned negative, and you don't have to worry about the overflow
situation.
But it does require that extra step to be trustworthy. Still purely
cheap arithmetic operations, although there is possibly some
additional register pressure there.
Somebody might be able to come up with something even more minimal (or
find a fault in my fix of your tweak).
I looks like there is another problem, or I'm misreading the
cleverness. We want the mask to be ~0 in the ok case and 0 in the
out-of-bounds case. As far as I can see we end up with ~0 in the ok
case, and ~1 in the bad case. Don't we need to do something like the
following, at which point are we getting out of the realm of "cheap
ALU instructions"?
#define __nospec_array_ptr(base, idx, sz) \
({ \
union { typeof(&base[0]) _ptr; unsigned long _bit; } __u; \
unsigned long _i = (idx); \
unsigned long _s = (sz); \
unsigned long _v = (long)(_i | _s - 1 - _i) \
>> BITS_PER_LONG - 1; \
unsigned long _mask = _v * ~0UL; \
OPTIMIZER_HIDE_VAR(_mask); \
__u._ptr = &base[_i & _mask]; \
__u._bit &= _mask; \
__u._ptr; \
})
elem = nospec_array_ptr(array, idx, 3);
106: b8 02 00 00 00 mov $0x2,%eax
10b: 48 63 ff movslq %edi,%rdi
10e: 48 29 f8 sub %rdi,%rax
111: 48 09 f8 or %rdi,%rax
114: 48 c1 e8 3f shr $0x3f,%rax
118: 48 21 c7 and %rax,%rdi
11b: 48 8d 54 bc 04 lea 0x4(%rsp,%rdi,4),%rdx
120: 48 21 d0 and %rdx,%rax
Why?
Because "(long)(_m-1-_i)" is not negative just because "i >= m". It
can still be positive.
Think "m = 100", "i=bignum". The subtraction will overflow and become
positive again, the shift will shift to zero, and then the mask will
become ~0.
Now, you can fix it, but you need to be a tiny bit more clever. In
particular, just make sure that you retain the high bit of "_i",
basically making the rule be that a negative index is not ever valid.
And then instead of "(_m - 1 - _i)", you use "(_i | (_m - 1 - _i))".
Now the sign bit is set if _i had it set, _or_ if the subtraction
turned negative, and you don't have to worry about the overflow
situation.
But it does require that extra step to be trustworthy. Still purely
cheap arithmetic operations, although there is possibly some
additional register pressure there.
Somebody might be able to come up with something even more minimal (or
find a fault in my fix of your tweak).
I looks like there is another problem, or I'm misreading the
cleverness. We want the mask to be ~0 in the ok case and 0 in the
out-of-bounds case. As far as I can see we end up with ~0 in the ok
case, and ~1 in the bad case. Don't we need to do something like the
following, at which point are we getting out of the realm of "cheap
ALU instructions"?
#define __nospec_array_ptr(base, idx, sz) \
({ \
union { typeof(&base[0]) _ptr; unsigned long _bit; } __u; \
unsigned long _i = (idx); \
unsigned long _s = (sz); \
unsigned long _v = (long)(_i | _s - 1 - _i) \
>> BITS_PER_LONG - 1; \
unsigned long _mask = _v * ~0UL; \
OPTIMIZER_HIDE_VAR(_mask); \
__u._ptr = &base[_i & _mask]; \
__u._bit &= _mask; \
__u._ptr; \
})
_v * ~0UL doesn't seem right and non intuitive.
What's wrong with:
unsigned long _mask = ~(long)(_i | _s - 1 - _i) >> BITS_PER_LONG - 1;
and why OPTIMIZER_HIDE_VAR ?
Could you remove '&' ?
since in doesn't work for:
struct {
int fd[4];
...
} *fdt;
it cannot be used as array_acces(fdt->fd, ...);
Could you please drop nospec_ prefix since it is misleading ?
This macro doesn't prevent speculation.
I think array_access() was the best name so far.
_v * ~0UL doesn't seem right and non intuitive.
What's wrong with:
unsigned long _mask = ~(long)(_i | _s - 1 - _i) >> BITS_PER_LONG - 1;
Yeah, I noticed it was ok immediately after I sent that.
and why OPTIMIZER_HIDE_VAR ?
It was in Linus' original. but that was when it had the ternary
conditional, I'll drop it. It does not change the generated assembly.
Could you remove '&' ?
Yes, that should be __u.ptr = base + (i & _mask)
since in doesn't work for:
struct {
int fd[4];
...
} *fdt;
it cannot be used as array_acces(fdt->fd, ...);
Could you please drop nospec_ prefix since it is misleading ?
When you came up with that tweak you noted:
"The following:
[..]
is generic and no speculative flows."
This macro doesn't prevent speculation.
It masks dangerous speculation. At least, I read nospec as "No
Spectre" and it is a prefix used in the Spectre-v2 patches.
I also want to include the option, with a static branch, to switch it
to the hard "no speculation" version with an ifence if worse comes to
worse and we find a compiler / cpu where it doesn't work. The default
will be the fast and practical implementation.
I think array_access() was the best name so far.
For other usages I need the pointer to the array element, also
array_access() by itself is unsuitable for __fcheck_files because we
still need rcu_dereference_raw() on the element de-reference. So, I
think it's better to get a sanitized array element pointer which can
be used with rcu, READ_ONCE(), etc... directly rather than try to do
the access in the same macro.
On Tue, Jan 09, 2018 at 06:22:09PM -0800, Dan Williams wrote:
When you came up with that tweak you noted:
"The following:
[..]
is generic and no speculative flows."
I meant 'no speculative control flow'
load speculation still happens.
quoted
This macro doesn't prevent speculation.
It masks dangerous speculation. At least, I read nospec as "No
Spectre" and it is a prefix used in the Spectre-v2 patches.
ahh. I thought 'nospec' means 'no speculation'.
I think it's too much of an honor to use bug name for the macro
that will be used in many places in the kernel.
quoted
I think array_access() was the best name so far.
For other usages I need the pointer to the array element, also
array_access() by itself is unsuitable for __fcheck_files because we
still need rcu_dereference_raw() on the element de-reference. So, I
think it's better to get a sanitized array element pointer which can
be used with rcu, READ_ONCE(), etc... directly rather than try to do
the access in the same macro.
makes sense, then array_ptr() should fit ?
I'm hearing rumors that the first cpu with variant 2 and 3 fixed
will be appearing in early 2019. Which is amazing considering cpu
release cycles, but it also means that variant 1 will stay with us
for long time and we better pick clean interface and name for it.
On Tue, Jan 9, 2018 at 4:48 PM, Dan Williams [off-list ref] wrote:
I looks like there is another problem, or I'm misreading the
cleverness.
I think you were misreading it.
I was basically saying that this:
unsigned long _mask = ~(long)(_m - 1 - _i) >> BITS_PER_LONG - 1;\
doesn't work, and that the "_m -1 - _i" needs to be replaced by "_i |
_m -1 -_i".
So you have
unsigned long _mask = ~(long)(_i (_m - 1 - _i)) >> BITS_PER_LONG - 1;\
which should give the right result. No?
But as mentioned, I think you can do it with two instructions if you
do an architecture-specific inline asm:
unsigned long mask;
asm("cmpq %1,%2; sbbq %0,%0"
:"=r" (mask)
:"g" (max),"r" (idx));
which is likely much faster, and has much better register usage ("max"
can be a constant or loaded directly from memory, and "mask" could be
assigned the same register as idx).
But once again, I didn't really test it.
Note that the "cmpq/sbbq" version works regardless of max/idx values,
since it literally does the math in BITS_ION_LONG+1 bits.
In contrast, the "binary or with idx" version only works if the high
bit set in idx cannot be valid (put another way: 'max' must not be
bigger than MAXLONG+1).
Linus