Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1653584 > unrolled thread

[PATCH v5 0/3] Implement fast refcount overflow protection

Back to article view | Back to linux.kernel

Contents

  [PATCH v5 0/3] Implement fast refcount overflow protection Kees Cook <keescook@chromium.org> - 2017-05-30 23:50 +0200
    [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc() Kees Cook <keescook@chromium.org> - 2017-05-30 23:50 +0200
      Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc() Peter Zijlstra <peterz@infradead.org> - 2017-05-31 13:20 +0200
        Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc() Kees Cook <keescook@chromium.org> - 2017-05-31 15:20 +0200
          Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc() Peter Zijlstra <peterz@infradead.org> - 2017-05-31 16:10 +0200
            Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc() Kees Cook <keescook@chromium.org> - 2017-05-31 18:10 +0200
    Re: [PATCH v5 0/3] Implement fast refcount overflow protection Davidlohr Bueso <dave@stgolabs.net> - 2017-05-31 14:30 +0200
      Re: [PATCH v5 0/3] Implement fast refcount overflow protection Kees Cook <keescook@chromium.org> - 2017-05-31 15:30 +0200

#1653584 — [PATCH v5 0/3] Implement fast refcount overflow protection

A new patch has been added at the start of this series to make the default
refcount_t implementation just use an unchecked atomic_t implementation,
since many kernel subsystems want to be able to opt out of the full
validation, since it includes a small performance overhead. When enabling
CONFIG_REFCOUNT_FULL, the full validation is used.

The other two patches provide overflow protection on x86 without incurring
a performance penalty. The changelog for patch 3 is reproduced here for
details:

This protection is a modified version of the x86 PAX_REFCOUNT defense
from PaX/grsecurity. This speeds up the refcount_t API by duplicating
the existing atomic_t implementation with a single instruction added to
detect if the refcount has wrapped past INT_MAX (or below 0) resulting
in a negative value, where the handler then restores the refcount_t to
INT_MAX or saturates to INT_MIN / 2. With this overflow protection, the
use-after-free following a refcount_t wrap is blocked from happening,
avoiding the vulnerability entirely.

While this defense only perfectly protects the overflow case, as that
can be detected and stopped before the reference is freed and left to be
abused by an attacker, it also notices some of the "inc from 0" and "below
0" cases. However, these only indicate that a use-after-free has already
happened. Such notifications are likely avoidable by an attacker that has
already exploited a use-after-free vulnerability, but it's better to have
them than allow such conditions to remain universally silent.

On overflow detection (actually "negative value" detection), the refcount
value is reset to INT_MAX, the offending process is killed, and a report
and stack trace are generated. This allows the system to attempt to
keep operating. In the case of a below-zero decrement or other negative
value results, the refcount is saturated to INT_MIN / 2 to keep it from
reaching zero again. (For the INT_MAX reset, another option would be to
choose (INT_MAX - N) with some small N to provide some headroom for
legitimate users of the reference counter.)

On the matter of races, since the entire range beyond INT_MAX but before 0
is negative, every inc will trap, leaving no overflow-only race condition.

As for performance, this implementation adds a single "js" instruction to
the regular execution flow of a copy of the regular atomic_t operations.
Since this is a forward jump, it is by default the non-predicted path,
which will be reinforced by dynamic branch prediction. The result is
this protection having no measurable change in performance over standard
atomic_t operations. The error path, located in .text.unlikely, saves
the refcount location and then uses UD0 to fire a refcount exception
handler, which resets the refcount, reports the error, marks the process
to be killed, and returns to regular execution. This keeps the changes to
.text size minimal, avoiding return jumps and open-coded calls to the
error reporting routine.
    
Assembly comparison:
    
atomic_inc
.text:
ffffffff81546149:       f0 ff 45 f4             lock incl -0xc(%rbp)
    
refcount_inc
.text:
ffffffff81546149:       f0 ff 45 f4             lock incl -0xc(%rbp)
ffffffff8154614d:       0f 88 80 d5 17 00       js     ffffffff816c36d3
...
.text.unlikely:
ffffffff816c36d3:       48 8d 4d f4             lea    -0xc(%rbp),%rcx
ffffffff816c36d7:       0f ff                   (bad)

Thanks to PaX Team for various suggestions for improvement.


-Kees

v5:
- add unchecked atomic_t implementation when !CONFIG_REFCOUNT_FULL
- use "leal" again, as in v3 for more flexible reset handling
- provide better underflow detection, with saturation

v4:
- switch to js from jns to gain static branch prediction benefits
- use .text.unlikely for js target, effectively making handler __cold
- use UD0 with refcount exception handler instead of int 0x81
- Kconfig defaults on when arch has support

v3:
- drop named text sections until we need to distinguish sizes/directions
- reset value immediately instead of passing back to handler
- drop needless export; josh

v2:
- fix instruction pointer decrement bug; thejh
- switch to js; pax-team
- improve commit log
- extract rmwcc macro helpers for better readability
- implemented checks in inc_not_zero interface
- adjusted reset values

[toc] | [next] | [standalone]

#1653587 — [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc()

The coming x86 refcount protection needs to be able to add trailing
instructions to the GEN_*_RMWcc() operations. This extracts the
difference between the goto/non-goto cases so the helper macros
can be defined outside the #ifdef cases. Additionally adds argument
naming to the resulting asm for referencing from suffixed
instructions, and adds clobbers for "cc", and "cx" to let suffixes
use _ASM_CX, and retain any set flags.

Signed-off-by: Kees Cook <keescook@chromium.org>
---
 arch/x86/include/asm/rmwcc.h | 37 ++++++++++++++++++++++++-------------
 1 file changed, 24 insertions(+), 13 deletions(-)

diff --git a/arch/x86/include/asm/rmwcc.h b/arch/x86/include/asm/rmwcc.h
index 661dd305694a..045f99211a99 100644
--- a/arch/x86/include/asm/rmwcc.h
+++ b/arch/x86/include/asm/rmwcc.h
@@ -1,45 +1,56 @@
 #ifndef _ASM_X86_RMWcc
 #define _ASM_X86_RMWcc
 
+#define __CLOBBERS_MEM		"memory"
+#define __CLOBBERS_MEM_CC_CX	"memory", "cc", "cx"
+
 #if !defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(CC_HAVE_ASM_GOTO)
 
 /* Use asm goto */
 
-#define __GEN_RMWcc(fullop, var, cc, ...)				\
+#define __GEN_RMWcc(fullop, var, cc, clobbers, ...)			\
 do {									\
 	asm_volatile_goto (fullop "; j" #cc " %l[cc_label]"		\
-			: : "m" (var), ## __VA_ARGS__ 			\
-			: "memory" : cc_label);				\
+			: : [counter] "m" (var), ## __VA_ARGS__		\
+			: clobbers : cc_label);				\
 	return 0;							\
 cc_label:								\
 	return 1;							\
 } while (0)
 
-#define GEN_UNARY_RMWcc(op, var, arg0, cc) 				\
-	__GEN_RMWcc(op " " arg0, var, cc)
+#define __BINARY_RMWcc_ARG	" %1, "
 
-#define GEN_BINARY_RMWcc(op, var, vcon, val, arg0, cc)			\
-	__GEN_RMWcc(op " %1, " arg0, var, cc, vcon (val))
 
 #else /* defined(__GCC_ASM_FLAG_OUTPUTS__) || !defined(CC_HAVE_ASM_GOTO) */
 
 /* Use flags output or a set instruction */
 
-#define __GEN_RMWcc(fullop, var, cc, ...)				\
+#define __GEN_RMWcc(fullop, var, cc, clobbers, ...)			\
 do {									\
 	bool c;								\
 	asm volatile (fullop ";" CC_SET(cc)				\
-			: "+m" (var), CC_OUT(cc) (c)			\
-			: __VA_ARGS__ : "memory");			\
+			: [counter] "+m" (var), CC_OUT(cc) (c)		\
+			: __VA_ARGS__ : clobbers);			\
 	return c;							\
 } while (0)
 
+#define __BINARY_RMWcc_ARG	" %2, "
+
+#endif /* defined(__GCC_ASM_FLAG_OUTPUTS__) || !defined(CC_HAVE_ASM_GOTO) */
+
 #define GEN_UNARY_RMWcc(op, var, arg0, cc)				\
-	__GEN_RMWcc(op " " arg0, var, cc)
+	__GEN_RMWcc(op " " arg0, var, cc, __CLOBBERS_MEM)
+
+#define GEN_UNARY_SUFFIXED_RMWcc(op, suffix, var, arg0, cc)		\
+	__GEN_RMWcc(op " " arg0 "\n\t" suffix, var, cc,			\
+		    __CLOBBERS_MEM_CC_CX)
 
 #define GEN_BINARY_RMWcc(op, var, vcon, val, arg0, cc)			\
-	__GEN_RMWcc(op " %2, " arg0, var, cc, vcon (val))
+	__GEN_RMWcc(op __BINARY_RMWcc_ARG arg0, var, cc,		\
+		    __CLOBBERS_MEM, vcon (val))
 
-#endif /* defined(__GCC_ASM_FLAG_OUTPUTS__) || !defined(CC_HAVE_ASM_GOTO) */
+#define GEN_BINARY_SUFFIXED_RMWcc(op, suffix, var, vcon, val, arg0, cc)	\
+	__GEN_RMWcc(op __BINARY_RMWcc_ARG arg0 "\n\t" suffix, var, cc,	\
+		    __CLOBBERS_MEM_CC_CX, vcon (val))
 
 #endif /* _ASM_X86_RMWcc */
-- 
2.7.4

[toc] | [prev] | [next] | [standalone]

#1654134 — Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc()

On Tue, May 30, 2017 at 02:39:51PM -0700, Kees Cook wrote:
> The coming x86 refcount protection needs to be able to add trailing
> instructions to the GEN_*_RMWcc() operations. This extracts the
> difference between the goto/non-goto cases so the helper macros
> can be defined outside the #ifdef cases. Additionally adds argument
> naming to the resulting asm for referencing from suffixed
> instructions, and adds clobbers for "cc", and "cx" to let suffixes
> use _ASM_CX, and retain any set flags.

Another option is to simply require __GCC_ASM_FLAG_OUTPUT__ for the fast
refcount stuff. That would result in simpler and more readable code.

[toc] | [prev] | [next] | [standalone]

#1654223 — Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc()

On Wed, May 31, 2017 at 4:13 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, May 30, 2017 at 02:39:51PM -0700, Kees Cook wrote:
>> The coming x86 refcount protection needs to be able to add trailing
>> instructions to the GEN_*_RMWcc() operations. This extracts the
>> difference between the goto/non-goto cases so the helper macros
>> can be defined outside the #ifdef cases. Additionally adds argument
>> naming to the resulting asm for referencing from suffixed
>> instructions, and adds clobbers for "cc", and "cx" to let suffixes
>> use _ASM_CX, and retain any set flags.
>
> Another option is to simply require __GCC_ASM_FLAG_OUTPUT__ for the fast
> refcount stuff. That would result in simpler and more readable code.

What versions of GCC support that?

-Kees

-- 
Kees Cook
Pixel Security

[toc] | [prev] | [next] | [standalone]

#1654275 — Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc()

On Wed, May 31, 2017 at 06:17:16AM -0700, Kees Cook wrote:
> On Wed, May 31, 2017 at 4:13 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Tue, May 30, 2017 at 02:39:51PM -0700, Kees Cook wrote:
> >> The coming x86 refcount protection needs to be able to add trailing
> >> instructions to the GEN_*_RMWcc() operations. This extracts the
> >> difference between the goto/non-goto cases so the helper macros
> >> can be defined outside the #ifdef cases. Additionally adds argument
> >> naming to the resulting asm for referencing from suffixed
> >> instructions, and adds clobbers for "cc", and "cx" to let suffixes
> >> use _ASM_CX, and retain any set flags.
> >
> > Another option is to simply require __GCC_ASM_FLAG_OUTPUT__ for the fast
> > refcount stuff. That would result in simpler and more readable code.
> 
> What versions of GCC support that?

IIRC 6+

[toc] | [prev] | [next] | [standalone]

#1654396 — Re: [PATCH v5 2/3] x86/asm: Add suffix macro for GEN_*_RMWcc()

On Wed, May 31, 2017 at 7:03 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, May 31, 2017 at 06:17:16AM -0700, Kees Cook wrote:
>> On Wed, May 31, 2017 at 4:13 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Tue, May 30, 2017 at 02:39:51PM -0700, Kees Cook wrote:
>> >> The coming x86 refcount protection needs to be able to add trailing
>> >> instructions to the GEN_*_RMWcc() operations. This extracts the
>> >> difference between the goto/non-goto cases so the helper macros
>> >> can be defined outside the #ifdef cases. Additionally adds argument
>> >> naming to the resulting asm for referencing from suffixed
>> >> instructions, and adds clobbers for "cc", and "cx" to let suffixes
>> >> use _ASM_CX, and retain any set flags.
>> >
>> > Another option is to simply require __GCC_ASM_FLAG_OUTPUT__ for the fast
>> > refcount stuff. That would result in simpler and more readable code.
>>
>> What versions of GCC support that?
>
> IIRC 6+

Given how many folks are still using 4.9 (and lower, see the thread
with Arnd[1]), I'd like to just keep this as I have it. It's not much
less readable, IMO (It was already pretty complex). I cleaned it up a
little before making it more ugly, so I think on sum, it's only a
little more weird. I think that's better than making this
compiler-specific or copy/pasting.

-Kees

[1] https://lkml.org/lkml/2017/4/25/66

-- 
Kees Cook
Pixel Security

[toc] | [prev] | [next] | [standalone]

#1654182

On Tue, 30 May 2017, Kees Cook wrote:

>A new patch has been added at the start of this series to make the default
>refcount_t implementation just use an unchecked atomic_t implementation,
>since many kernel subsystems want to be able to opt out of the full
>validation, since it includes a small performance overhead. When enabling
>CONFIG_REFCOUNT_FULL, the full validation is used.
>
>The other two patches provide overflow protection on x86 without incurring
>a performance penalty. The changelog for patch 3 is reproduced here for
>details:

To be sure I'm getting this right, after this all archs with the exception
of x86 will use the regular atomic_t ("unsecure") flavor, right?

Thanks,
Davidlohr

[toc] | [prev] | [next] | [standalone]

#1654227

On Wed, May 31, 2017 at 5:27 AM, Davidlohr Bueso <dave@stgolabs.net> wrote:
> On Tue, 30 May 2017, Kees Cook wrote:
>
>> A new patch has been added at the start of this series to make the default
>> refcount_t implementation just use an unchecked atomic_t implementation,
>> since many kernel subsystems want to be able to opt out of the full
>> validation, since it includes a small performance overhead. When enabling
>> CONFIG_REFCOUNT_FULL, the full validation is used.
>>
>> The other two patches provide overflow protection on x86 without incurring
>> a performance penalty. The changelog for patch 3 is reproduced here for
>> details:
>
>
> To be sure I'm getting this right, after this all archs with the exception
> of x86 will use the regular atomic_t ("unsecure") flavor, right?

If a build does not select CONFIG_REFCOUNT_FULL and lacks
CONFIG_ARCH_HAS_REFCOUNT, refcount_t will be the same at atomic_t
(i.e. no change from the historical behavior where all the ref
counters in the kernel used atomic_t).

-Kees

-- 
Kees Cook
Pixel Security

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web