| Message ID | 151632010687.21271.12004432287640499992.stgit@dwillia2-desk3.amr.corp.intel.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Fri, Jan 19, 2018 at 1:01 AM, Dan Williams <dan.j.williams@intel.com> wrote: > 'array_ptr' is proposed as a generic mechanism to mitigate against > Spectre-variant-1 attacks, i.e. an attack that bypasses boundary checks > via speculative execution). The 'array_ptr' implementation is expected > to be safe for current generation cpus across multiple architectures > (ARM, x86). > > Based on an original implementation by Linus Torvalds, tweaked to remove > speculative flows by Alexei Starovoitov, and tweaked again by Linus to > introduce an x86 assembly implementation for the mask generation. [...] > +/* > + * If idx is negative or if idx > size then bit 63 is set in the mask, > + * and the value of ~(-1L) is zero. When the mask is zero, bounds check > + * failed, array_ptr will return NULL. > + */ > +#ifndef array_ptr_mask > +static inline unsigned long array_ptr_mask(unsigned long idx, unsigned long sz) > +{ > + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); > +} > +#endif Nit: Maybe add a comment saying that this is equivalent to "return ((long)idx >= 0 && idx < sz) ? ULONG_MAX : 0"? > +/** > + * array_ptr - Generate a pointer to an array element, ensuring > + * the pointer is bounded under speculation to NULL. > + * > + * @base: the base of the array > + * @idx: the index of the element, must be less than LONG_MAX > + * @sz: the number of elements in the array, must be less than LONG_MAX > + * > + * If @idx falls in the interval [0, @sz), returns the pointer to > + * @arr[@idx], otherwise returns NULL. > + */ > +#define array_ptr(base, idx, sz) \ > +({ \ > + union { typeof(*(base)) *_ptr; unsigned long _bit; } __u; \ > + typeof(*(base)) *_arr = (base); \ > + unsigned long _i = (idx); \ > + unsigned long _mask = array_ptr_mask(_i, (sz)); \ > + \ > + __u._ptr = _arr + (_i & _mask); \ > + __u._bit &= _mask; \ AFAICS, if `idx` is out of bounds, you first zero out the index (`_i & _mask`) and then immediately afterwards zero out the whole pointer (`_u._bit &= _mask`). Is there a reason for the `_i & _mask`, and if so, can you add a comment explaining that?
Jann Horn <jannh@google.com> writes: >> +/* >> + * If idx is negative or if idx > size then bit 63 is set in the mask, >> + * and the value of ~(-1L) is zero. When the mask is zero, bounds check >> + * failed, array_ptr will return NULL. >> + */ >> +#ifndef array_ptr_mask >> +static inline unsigned long array_ptr_mask(unsigned long idx, >> unsigned long sz) >> +{ >> + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); >> +} >> +#endif > > Nit: Maybe add a comment saying that this is equivalent to > "return ((long)idx >= 0 && idx < sz) ? ULONG_MAX : 0"? That's only true when sz < LONG_MAX, which is documented below but not here; it's also different from the asm version, which doesn't do the idx <= LONG_MAX check. So making the constraint explicit would be a good idea. From a bit of experimentation, when the top bit of sz is set, this expression, the C version and the assembler version all have different behaviour. For example, with 32-bit unsigned long: index=00000000 size=80000001: expr=ffffffff c=00000000 asm=ffffffff index=80000000 size=80000001: expr=00000000 c=00000000 asm=ffffffff index=00000000 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff index=00000001 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff index=fffffffe size=ffffffff: expr=00000000 c=00000000 asm=ffffffff It may be worth noting that: return 0 - ((long) (idx < sz)); causes GCC, on ia32 and amd64, to generate exactly the same cmp/sbb sequence as in Linus's asm. Are there architectures where this form would allow speculation? Thanks,
[ adding Alexei back to the cc ] On Fri, Jan 19, 2018 at 9:48 AM, Adam Sampson <ats@offog.org> wrote: > Jann Horn <jannh@google.com> writes: > >>> +/* >>> + * If idx is negative or if idx > size then bit 63 is set in the mask, >>> + * and the value of ~(-1L) is zero. When the mask is zero, bounds check >>> + * failed, array_ptr will return NULL. >>> + */ >>> +#ifndef array_ptr_mask >>> +static inline unsigned long array_ptr_mask(unsigned long idx, >>> unsigned long sz) >>> +{ >>> + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); >>> +} >>> +#endif >> >> Nit: Maybe add a comment saying that this is equivalent to >> "return ((long)idx >= 0 && idx < sz) ? ULONG_MAX : 0"? > > That's only true when sz < LONG_MAX, which is documented below but not > here; it's also different from the asm version, which doesn't do the idx > <= LONG_MAX check. So making the constraint explicit would be a good idea. > > From a bit of experimentation, when the top bit of sz is set, this > expression, the C version and the assembler version all have different > behaviour. For example, with 32-bit unsigned long: > > index=00000000 size=80000001: expr=ffffffff c=00000000 asm=ffffffff > index=80000000 size=80000001: expr=00000000 c=00000000 asm=ffffffff > index=00000000 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff > index=00000001 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff > index=fffffffe size=ffffffff: expr=00000000 c=00000000 asm=ffffffff > > It may be worth noting that: > > return 0 - ((long) (idx < sz)); > > causes GCC, on ia32 and amd64, to generate exactly the same cmp/sbb > sequence as in Linus's asm. Are there architectures where this form > would allow speculation? We're operating on the assumption that compilers will not try to introduce branches where they don't exist in the code, so if this is producing identical assembly I think we should go with it and drop the x86 array_ptr_mask.
On Fri, Jan 19, 2018 at 10:12:47AM -0800, Dan Williams wrote: > [ adding Alexei back to the cc ] > > On Fri, Jan 19, 2018 at 9:48 AM, Adam Sampson <ats@offog.org> wrote: > > Jann Horn <jannh@google.com> writes: > > > >>> +/* > >>> + * If idx is negative or if idx > size then bit 63 is set in the mask, > >>> + * and the value of ~(-1L) is zero. When the mask is zero, bounds check > >>> + * failed, array_ptr will return NULL. > >>> + */ > >>> +#ifndef array_ptr_mask > >>> +static inline unsigned long array_ptr_mask(unsigned long idx, > >>> unsigned long sz) > >>> +{ > >>> + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); > >>> +} > >>> +#endif > >> > >> Nit: Maybe add a comment saying that this is equivalent to > >> "return ((long)idx >= 0 && idx < sz) ? ULONG_MAX : 0"? > > > > That's only true when sz < LONG_MAX, which is documented below but not > > here; it's also different from the asm version, which doesn't do the idx > > <= LONG_MAX check. So making the constraint explicit would be a good idea. > > > > From a bit of experimentation, when the top bit of sz is set, this > > expression, the C version and the assembler version all have different > > behaviour. For example, with 32-bit unsigned long: > > > > index=00000000 size=80000001: expr=ffffffff c=00000000 asm=ffffffff > > index=80000000 size=80000001: expr=00000000 c=00000000 asm=ffffffff > > index=00000000 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff > > index=00000001 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff > > index=fffffffe size=ffffffff: expr=00000000 c=00000000 asm=ffffffff > > > > It may be worth noting that: > > > > return 0 - ((long) (idx < sz)); > > > > causes GCC, on ia32 and amd64, to generate exactly the same cmp/sbb > > sequence as in Linus's asm. Are there architectures where this form > > would allow speculation? > > We're operating on the assumption that compilers will not try to > introduce branches where they don't exist in the code, so if this is > producing identical assembly I think we should go with it and drop the > x86 array_ptr_mask. Branches, perhaps, but this could easily be compiled to a conditional select (CSEL) instruction on arm64 and that wouldn't be safe without a CSDB. Of course, we can do our own thing in assembly to prevent that, but it would mean that the generic C implementation would not be robust for us. Will
On Fri, Jan 19, 2018 at 2:20 AM, Jann Horn <jannh@google.com> wrote: >> + \ >> + __u._ptr = _arr + (_i & _mask); \ >> + __u._bit &= _mask; \ > > AFAICS, if `idx` is out of bounds, you first zero out the index > (`_i & _mask`) and then immediately afterwards zero out > the whole pointer (`_u._bit &= _mask`). > Is there a reason for the `_i & _mask`, and if so, can you > add a comment explaining that? I think that's just leftovers from my original (untested) thing that also did the access itself. So that __u._bit masking wasn't masking the pointer, it was masking the value that was *read* from the pointer, so that you could know that an invalid access returned 0/NULL, not just the first value in the array. Linus
On Fri, Jan 19, 2018 at 10:18 AM, Will Deacon <will.deacon@arm.com> wrote: > > On Fri, Jan 19, 2018 at 10:12:47AM -0800, Dan Williams wrote: > > [ adding Alexei back to the cc ] > > > > On Fri, Jan 19, 2018 at 9:48 AM, Adam Sampson <ats@offog.org> wrote: > > > Jann Horn <jannh@google.com> writes: > > > > > >>> +/* > > >>> + * If idx is negative or if idx > size then bit 63 is set in the mask, > > >>> + * and the value of ~(-1L) is zero. When the mask is zero, bounds check > > >>> + * failed, array_ptr will return NULL. > > >>> + */ > > >>> +#ifndef array_ptr_mask > > >>> +static inline unsigned long array_ptr_mask(unsigned long idx, > > >>> unsigned long sz) > > >>> +{ > > >>> + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); > > >>> +} > > >>> +#endif > > >> > > >> Nit: Maybe add a comment saying that this is equivalent to > > >> "return ((long)idx >= 0 && idx < sz) ? ULONG_MAX : 0"? > > > > > > That's only true when sz < LONG_MAX, which is documented below but not > > > here; it's also different from the asm version, which doesn't do the idx > > > <= LONG_MAX check. So making the constraint explicit would be a good idea. > > > > > > From a bit of experimentation, when the top bit of sz is set, this > > > expression, the C version and the assembler version all have different > > > behaviour. For example, with 32-bit unsigned long: > > > > > > index=00000000 size=80000001: expr=ffffffff c=00000000 asm=ffffffff > > > index=80000000 size=80000001: expr=00000000 c=00000000 asm=ffffffff > > > index=00000000 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff > > > index=00000001 size=a0000000: expr=ffffffff c=00000000 asm=ffffffff > > > index=fffffffe size=ffffffff: expr=00000000 c=00000000 asm=ffffffff > > > > > > It may be worth noting that: > > > > > > return 0 - ((long) (idx < sz)); > > > > > > causes GCC, on ia32 and amd64, to generate exactly the same cmp/sbb > > > sequence as in Linus's asm. Are there architectures where this form > > > would allow speculation? > > > > We're operating on the assumption that compilers will not try to > > introduce branches where they don't exist in the code, so if this is > > producing identical assembly I think we should go with it and drop the > > x86 array_ptr_mask. > > Branches, perhaps, but this could easily be compiled to a conditional > select (CSEL) instruction on arm64 and that wouldn't be safe without a > CSDB. Of course, we can do our own thing in assembly to prevent that, but > it would mean that the generic C implementation would not be robust for us. > Ah, ok good to know. Likely if the current version doesn't produce a conditional instruction on ARM perhaps it also won't do that on other architectures, so it is safer.
On Fri, Jan 19, 2018 at 10:18 AM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Fri, Jan 19, 2018 at 2:20 AM, Jann Horn <jannh@google.com> wrote: >>> + \ >>> + __u._ptr = _arr + (_i & _mask); \ >>> + __u._bit &= _mask; \ >> >> AFAICS, if `idx` is out of bounds, you first zero out the index >> (`_i & _mask`) and then immediately afterwards zero out >> the whole pointer (`_u._bit &= _mask`). >> Is there a reason for the `_i & _mask`, and if so, can you >> add a comment explaining that? > > I think that's just leftovers from my original (untested) thing that > also did the access itself. So that __u._bit masking wasn't masking > the pointer, it was masking the value that was *read* from the > pointer, so that you could know that an invalid access returned > 0/NULL, not just the first value in the array. Yes, the index masking can be dropped since we're returning a sanitized array element pointer now.
On 1/18/2018 4:01 PM, Dan Williams wrote: > 'array_ptr' is proposed as a generic mechanism to mitigate against > Spectre-variant-1 attacks, i.e. an attack that bypasses boundary checks > via speculative execution). The 'array_ptr' implementation is expected > to be safe for current generation cpus across multiple architectures > (ARM, x86). I'm an outside reviewer, not subscribed to the list, so forgive me if I do something not according to protocol. I have the following comments on this change: After discarding the speculation barrier variant, is array_ptr() needed at all? You could have a simpler sanitizing macro, say #define array_sanitize_idx(idx, sz) ((idx) & array_ptr_mask((idx), (sz))) (adjusted to not evaluate idx twice). And use it as follows: if (idx < array_size) { idx = array_sanitize_idx(idx, array_size); do_something(array[idx]); } If I understand the speculation stuff correctly, unlike array_ptr(), this "leaks" array[0] rather than nothing (*NULL) when executed speculatively. However, it's still much better than leaking an arbitrary location in memory. The attacker can likely get array[0] "leaked" by passing 0 as idx anyway. > +/* > + * If idx is negative or if idx > size then bit 63 is set in the mask, > + * and the value of ~(-1L) is zero. When the mask is zero, bounds check > + * failed, array_ptr will return NULL. > + */ > +#ifndef array_ptr_mask > +static inline unsigned long array_ptr_mask(unsigned long idx, unsigned long sz) > +{ > + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); > +} > +#endif Why does this have to resort to the undefined behavior of shifting a negative number to the right? You can do without it: return ((idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1)) - 1; Of course, you could argue that subtracting 1 from 0 to get all ones is also an undefined behavior, but it's still much better than the shift, isn't it? > +#define array_ptr(base, idx, sz) \ > +({ \ > + union { typeof(*(base)) *_ptr; unsigned long _bit; } __u; \ > + typeof(*(base)) *_arr = (base); \ > + unsigned long _i = (idx); \ > + unsigned long _mask = array_ptr_mask(_i, (sz)); \ > + \ > + __u._ptr = _arr + (_i & _mask); \ > + __u._bit &= _mask; \ > + __u._ptr; \ > +}) Call me paranoid, but I think this may actually create an exploitable bug on 32-bit systems due to casting the index to an unsigned long, if the index as it comes from userland is a 64-bit value. You have *replaced* the "if (idx < array_size)" check with checking if array_ptr() returns NULL. Well, it doesn't return NULL if the low 32 bits of the index are in-bounds, but the high 32 bits are not zero. Apart from the return value pointing to the wrong place, the subsequent code may then assume that the 64-bit idx is actually valid and trip on it badly. -- Cyril
On Wed, Jan 24, 2018 at 11:09 PM, Cyril Novikov <cnovikov@lynx.com> wrote: > On 1/18/2018 4:01 PM, Dan Williams wrote: >> >> 'array_ptr' is proposed as a generic mechanism to mitigate against >> Spectre-variant-1 attacks, i.e. an attack that bypasses boundary checks >> via speculative execution). The 'array_ptr' implementation is expected >> to be safe for current generation cpus across multiple architectures >> (ARM, x86). > > > I'm an outside reviewer, not subscribed to the list, so forgive me if I do > something not according to protocol. I have the following comments on this > change: > > After discarding the speculation barrier variant, is array_ptr() needed at > all? You could have a simpler sanitizing macro, say > > #define array_sanitize_idx(idx, sz) ((idx) & array_ptr_mask((idx), (sz))) > > (adjusted to not evaluate idx twice). And use it as follows: > > if (idx < array_size) { > idx = array_sanitize_idx(idx, array_size); > do_something(array[idx]); > } > > If I understand the speculation stuff correctly, unlike array_ptr(), this > "leaks" array[0] rather than nothing (*NULL) when executed speculatively. > However, it's still much better than leaking an arbitrary location in > memory. The attacker can likely get array[0] "leaked" by passing 0 as idx > anyway. True, we could simplify it to just sanitize the index with the expectation that speculating with index 0 is safe. Although we'd want to document it just case there is some odd code paths where the valid portion of the array is offset from 0. I like this approach better because it handles cases where the bounds check is far away from the array de-reference. I.e. instead of having array_ptr() and array_idx() for different cases, just sanitize the index. > >> +/* >> + * If idx is negative or if idx > size then bit 63 is set in the mask, >> + * and the value of ~(-1L) is zero. When the mask is zero, bounds check >> + * failed, array_ptr will return NULL. >> + */ >> +#ifndef array_ptr_mask >> +static inline unsigned long array_ptr_mask(unsigned long idx, unsigned >> long sz) >> +{ >> + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); >> +} >> +#endif > > > Why does this have to resort to the undefined behavior of shifting a > negative number to the right? You can do without it: > > return ((idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1)) - 1; > > Of course, you could argue that subtracting 1 from 0 to get all ones is also > an undefined behavior, but it's still much better than the shift, isn't it? The goal is to prevent the compiler from emitting conditional instructions. For example, the simplest form of this sanitize operation from Adam: return 0 - ((long) (idx < sz)); ...produces the desired "cmp, sbb" sequence on x86, but leads to a "csel" instruction being emitted for arm64. Stepping back and realizing that all this churn is around the un-optimized form of the comparison vs the inline asm that an arch can provide, and we're effectively handling the carry bit in software, we can have a WARN_ON_ONCE(idx < 0 || sz < 0) to catch places where the expectations of the macro are violated. Archs can remove the overhead of that extra branch with an instruction sequence to handle the carry bit in hardware, otherwise we get runtime coverage of places where array_idx() gets used incorrectly. > >> +#define array_ptr(base, idx, sz) \ >> +({ \ >> + union { typeof(*(base)) *_ptr; unsigned long _bit; } __u; \ >> + typeof(*(base)) *_arr = (base); \ >> + unsigned long _i = (idx); \ >> + unsigned long _mask = array_ptr_mask(_i, (sz)); \ >> + \ >> + __u._ptr = _arr + (_i & _mask); \ >> + __u._bit &= _mask; \ >> + __u._ptr; \ >> +}) > > > Call me paranoid, but I think this may actually create an exploitable bug on > 32-bit systems due to casting the index to an unsigned long, if the index as > it comes from userland is a 64-bit value. You have *replaced* the "if (idx < > array_size)" check with checking if array_ptr() returns NULL. Well, it > doesn't return NULL if the low 32 bits of the index are in-bounds, but the > high 32 bits are not zero. Apart from the return value pointing to the wrong > place, the subsequent code may then assume that the 64-bit idx is actually > valid and trip on it badly. Yes, I'll add some BUILD_BUG_ON safety for cases where sizeof(idx) > sizeof(long). Thanks for taking a look.
diff --git a/include/linux/nospec.h b/include/linux/nospec.h new file mode 100644 index 000000000000..f841c11f3f1f --- /dev/null +++ b/include/linux/nospec.h @@ -0,0 +1,44 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright(c) 2018 Intel Corporation. All rights reserved. + +#ifndef __NOSPEC_H__ +#define __NOSPEC_H__ + +#include <linux/jump_label.h> +#include <asm/barrier.h> + +/* + * If idx is negative or if idx > size then bit 63 is set in the mask, + * and the value of ~(-1L) is zero. When the mask is zero, bounds check + * failed, array_ptr will return NULL. + */ +#ifndef array_ptr_mask +static inline unsigned long array_ptr_mask(unsigned long idx, unsigned long sz) +{ + return ~(long)(idx | (sz - 1 - idx)) >> (BITS_PER_LONG - 1); +} +#endif + +/** + * array_ptr - Generate a pointer to an array element, ensuring + * the pointer is bounded under speculation to NULL. + * + * @base: the base of the array + * @idx: the index of the element, must be less than LONG_MAX + * @sz: the number of elements in the array, must be less than LONG_MAX + * + * If @idx falls in the interval [0, @sz), returns the pointer to + * @arr[@idx], otherwise returns NULL. + */ +#define array_ptr(base, idx, sz) \ +({ \ + union { typeof(*(base)) *_ptr; unsigned long _bit; } __u; \ + typeof(*(base)) *_arr = (base); \ + unsigned long _i = (idx); \ + unsigned long _mask = array_ptr_mask(_i, (sz)); \ + \ + __u._ptr = _arr + (_i & _mask); \ + __u._bit &= _mask; \ + __u._ptr; \ +}) +#endif /* __NOSPEC_H__ */
'array_ptr' is proposed as a generic mechanism to mitigate against Spectre-variant-1 attacks, i.e. an attack that bypasses boundary checks via speculative execution). The 'array_ptr' implementation is expected to be safe for current generation cpus across multiple architectures (ARM, x86). Based on an original implementation by Linus Torvalds, tweaked to remove speculative flows by Alexei Starovoitov, and tweaked again by Linus to introduce an x86 assembly implementation for the mask generation. Co-developed-by: Linus Torvalds <torvalds@linux-foundation.org> Co-developed-by: Alexei Starovoitov <ast@kernel.org> Co-developed-by: Peter Zijlstra <peterz@infradead.org> Cc: Russell King <linux@armlinux.org.uk> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Will Deacon <will.deacon@arm.com> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Ingo Molnar <mingo@redhat.com> Cc: "H. Peter Anvin" <hpa@zytor.com> Cc: x86@kernel.org Signed-off-by: Dan Williams <dan.j.williams@intel.com> --- include/linux/nospec.h | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 include/linux/nospec.h