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

Groups > linux.kernel > #1628642 > unrolled thread

[PATCH] x86/refcount: Implement fast refcount_t handling

Back to article view | Back to linux.kernel

Contents

  [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-22 00:10 +0200
    Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-24 10:40 +0200
      Re: [kernel-hardening] Re: [PATCH] x86/refcount: Implement fast  refcount_t handling Jann Horn <jannh@google.com> - 2017-04-24 11:00 +0200
        Re: [kernel-hardening] Re: [PATCH] x86/refcount: Implement fast  refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-24 11:30 +0200
      Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-24 13:10 +0200
        Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-24 13:20 +0200
          Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-24 15:20 +0200
            Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-24 15:40 +0200
              Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-24 17:20 +0200
                Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-24 22:50 +0200
                  Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-25 00:10 +0200
                    Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-25 00:40 +0200
                      Re: [kernel-hardening] Re: [PATCH] x86/refcount: Implement fast  refcount_t handling Rik van Riel <riel@redhat.com> - 2017-04-25 03:20 +0200
                      Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-25 11:10 +0200
                    Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-25 13:30 +0200
                      Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-25 18:40 +0200
        Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-24 22:40 +0200
          Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-25 13:30 +0200
            Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-25 18:50 +0200
              Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-26 04:20 +0200
                Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-26 06:50 +0200
      Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-24 22:20 +0200
    Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-24 12:50 +0200
      Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-24 22:20 +0200
    Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-24 13:00 +0200
      Re: [PATCH] x86/refcount: Implement fast refcount_t handling Kees Cook <keescook@chromium.org> - 2017-04-24 22:30 +0200
    Re: [PATCH] x86/refcount: Implement fast refcount_t handling Peter Zijlstra <peterz@infradead.org> - 2017-04-25 12:30 +0200
      Re: [PATCH] x86/refcount: Implement fast refcount_t handling "PaX Team" <pageexec@freemail.hu> - 2017-04-25 13:30 +0200

Page 2 of 2 — ← Prev page 1 [2]

#1631141

On Tue, Apr 25, 2017 at 7:14 PM, PaX Team <pageexec@freemail.hu> wrote:
> On 25 Apr 2017 at 9:39, Kees Cook wrote:
>
>> On Tue, Apr 25, 2017 at 4:26 AM, PaX Team <pageexec@freemail.hu> wrote:
>> > INT_MAX threads would be needed when the leaking path is locked so
>> > that it can only be exercised once and you'll need to get normal
>> > (balanced) paths preempted just after the increment. if the leaking
>> > path is lockless (can be exercised in parallel without bounds) then
>> > 2 threads are enough where the one triggering the signed overflow
>> > would have to be preempted while the other one does INT_MAX increments
>> > and trigger the UAF. this is where the other mechanisms i talked about
>> > in the past become relevant: preemption or interrupts can be disabled
>> > or negative refcount values can be detected and acted upon (your blind
>> > copy-pasting effort passed upon this latter opportunity by not
>> > specializing the 'jo' into 'js' for the refcount case).
>>
>> Well, it's not "blind" -- I'm trying to bring the code as-is to
>> upstream for discussion/examination with as little functional
>> differences as possible so it's easier to compare apples to apples.
>
> you copied code from a version which is at least 2 major kernel revisions
> behind (so much for those apples)

Hmm, this was from your 4.9 port. Linus hasn't quite released 4.11
yet, so that's actually "at most 2 major kernel revisions behind". :)
Regardless, I'd be happy to refresh the port. Will you share a URL to
your latest rebase against upstream?

> you chose the one version which had a
> bug that you didn't spot nor fix properly, you didn't realize the opportunity
> that a special refcount type represents, you claimed refcount underflows
> aren't exploitable but copied code that would detect signed underflow, you
> didn't understand the limits and edge cases i explained above... need i go

As I said, I was trying to minimize changes to your implementation,
which included the bug and the other issues. The point of this was to
share it with others, and work collaboratively on it. I think this
clearly succeeded with benefits to both upstream and PaX: Jann spotted
the fix for the bug causing weird crashes I saw when doing initial
testing, you pointed out the benefit of using js over jo, I've
reorganized the RMWcc macros for more easily adding trailing
instructions, Peter is thinking about ways around the protection, etc.

> on? doesn't leave one with great confidence in your ability to understand
> and maintain this code...

Well, that's your opinion. I think the patch and its discussion helped
several people, including myself, understand this code. Since many
people will share its maintenance, I think this is the right way to
handle upstreaming these kinds of things. I don't claim to be
omniscient, just persistent. Getting this protection into upstream
means every Linux user will benefit from what you created, which I
think is awesome; this whole class of refcount flaws goes away. Thank
you for writing it, sharing it, and discussing it!

-Kees

-- 
Kees Cook
Pixel Security

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

#1629961

On Mon, Apr 24, 2017 at 1:32 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Apr 21, 2017 at 03:09:39PM -0700, Kees Cook wrote:
>> This patch ports the x86-specific atomic overflow handling from PaX's
>> PAX_REFCOUNT to the upstream refcount_t API. This is an updated version
>> from PaX that eliminates the saturation race condition by resetting the
>> atomic counter back to the INT_MAX saturation value on both overflow and
>> underflow. To win a race, a system would have to have INT_MAX threads
>> simultaneously overflow before the saturation handler runs.
>
> And is this impossible? Highly unlikely I'll grant you, but absolutely
> impossible?

I'll adjust the language. "Highly unlikely" is still better than
"trivially doable with a single thread". :)

> Also, you forgot nr_cpus in your bound. Afaict the worst case here is
> O(nr_tasks + 3*nr_cpus).
>
> Because PaX does it, is not a correctness argument. And this really
> wants one.

Sure, I didn't mean to imply anything other than a demonstration of
what PaX is doing (and that it's better than not having it). If we can
improve it, that's great.

-Kees

-- 
Kees Cook
Pixel Security

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

#1629417

On Fri, Apr 21, 2017 at 03:09:39PM -0700, Kees Cook wrote:
> +static __always_inline __must_check bool refcount_inc_not_zero(refcount_t *r)
> +{
> +	const int a = 1;
> +	const int u = 0;
> +	int c, old;
> +
> +	c = atomic_read(&(r->refs));
> +	for (;;) {
> +		if (unlikely(c == (u)))
> +			break;
> +		old = atomic_cmpxchg(&(r->refs), c, c + (a));

Please use atomic_try_cmpxchg(), that generates saner code.

> +		if (likely(old == c))
> +			break;
> +		c = old;
> +	}
> +	return c != u;
> +}

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

#1629962

On Mon, Apr 24, 2017 at 3:45 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Apr 21, 2017 at 03:09:39PM -0700, Kees Cook wrote:
>> +static __always_inline __must_check bool refcount_inc_not_zero(refcount_t *r)
>> +{
>> +     const int a = 1;
>> +     const int u = 0;
>> +     int c, old;
>> +
>> +     c = atomic_read(&(r->refs));
>> +     for (;;) {
>> +             if (unlikely(c == (u)))
>> +                     break;
>> +             old = atomic_cmpxchg(&(r->refs), c, c + (a));
>
> Please use atomic_try_cmpxchg(), that generates saner code.

Ah-ha, thanks. I actually copied this directly out of the existing
atomic_t function, so we should probably update it there too.

-Kees

>
>> +             if (likely(old == c))
>> +                     break;
>> +             c = old;
>> +     }
>> +     return c != u;
>> +}



-- 
Kees Cook
Pixel Security

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

#1629424

On Fri, Apr 21, 2017 at 03:09:39PM -0700, Kees Cook wrote:
> diff --git a/drivers/misc/lkdtm_bugs.c b/drivers/misc/lkdtm_bugs.c
> index e3f4cd8876b5..1bdafb29b802 100644
> --- a/drivers/misc/lkdtm_bugs.c
> +++ b/drivers/misc/lkdtm_bugs.c
> @@ -135,9 +135,15 @@ void lkdtm_HUNG_TASK(void)
>  	schedule();
>  }
>  
> +#ifdef CONFIG_FAST_REFCOUNT
> +#define REFCOUNT_MAX	INT_MAX
> +#else
> +#define REFCOUNT_MAX	UINT_MAX
> +#endif

That doesn't seem like a sensible place for this.

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

#1629989

On Mon, Apr 24, 2017 at 3:48 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Apr 21, 2017 at 03:09:39PM -0700, Kees Cook wrote:
>> diff --git a/drivers/misc/lkdtm_bugs.c b/drivers/misc/lkdtm_bugs.c
>> index e3f4cd8876b5..1bdafb29b802 100644
>> --- a/drivers/misc/lkdtm_bugs.c
>> +++ b/drivers/misc/lkdtm_bugs.c
>> @@ -135,9 +135,15 @@ void lkdtm_HUNG_TASK(void)
>>       schedule();
>>  }
>>
>> +#ifdef CONFIG_FAST_REFCOUNT
>> +#define REFCOUNT_MAX INT_MAX
>> +#else
>> +#define REFCOUNT_MAX UINT_MAX
>> +#endif
>
> That doesn't seem like a sensible place for this.

I'll drop the LKDTM changes from this particular patch. As for the
define, I think it's only interesting to LKDTM since it's the only
part interested in refcount_t internals. (i.e. nothing else would (or
should) use this information.)

-Kees

-- 
Kees Cook
Pixel Security

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

#1630381

On Fri, Apr 21, 2017 at 03:09:39PM -0700, Kees Cook wrote:
> +static __always_inline void refcount_inc(refcount_t *r)
> +{
> +	asm volatile(LOCK_PREFIX "incl %0\n\t"
> +		REFCOUNT_CHECK_OVERFLOW(4)
> +		: [counter] "+m" (r->refs.counter)
> +		: : "cc", "cx");
> +}
> +
> +static __always_inline void refcount_dec(refcount_t *r)
> +{
> +	asm volatile(LOCK_PREFIX "decl %0\n\t"
> +		REFCOUNT_CHECK_UNDERFLOW(4)
> +		: [counter] "+m" (r->refs.counter)
> +		: : "cc", "cx");
> +}

> +dotraplinkage void do_refcount_error(struct pt_regs *regs, long error_code)
> +{
> +	const char *str = NULL;
> +
> +	BUG_ON(!(regs->flags & X86_EFLAGS_OF));
> +
> +#define range_check(size, direction, type, value) \
> +	if ((unsigned long)__##size##_##direction##_start <= regs->ip && \
> +	    regs->ip < (unsigned long)__##size##_##direction##_end) { \
> +		*(type *)regs->cx = value; \
> +		str = #size " " #direction; \
> +	}
> +
> +	range_check(refcount,   overflow,  int, INT_MAX)
> +	range_check(refcount,   underflow, int, INT_MIN)
> +
> +#undef range_check
> +
> +	BUG_ON(!str);
> +	do_error_trap(regs, error_code, (char *)str, X86_REFCOUNT_VECTOR,
> +		      SIGILL);
> +}
> +#endif


So what avoids this:

	CPU0				CPU1


	lock inc %[val]; # 0x7fffffff
	jo  2f
1:	...

					lock dec %[val]; # 0x80000000
					jo  2f
				1:	...




2:	mov $0x7fffffff, %[val]
	jmp 1b

				2:	mov $0x80000000, %[val]
					jmp 1b




	~~~~//~~~~


	lock inc %val; #0x80000000
	....

	lock inc %val; 0xffffffff
	lock inc %val; 0x00000000

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

#1630423

On 25 Apr 2017 at 12:23, Peter Zijlstra wrote:

> So what avoids this:

simple, you noted it yourself in your previous mail:

> Well, your setup (panic_on_warn et al) would have it panic the box. That
> will effectively stop the exploit by virtue of stopping everything.

with that in mind the actual code looks like this:

>	CPU0				CPU1
>
>
>	lock inc %[val]; # 0x7fffffff
>	jo  2f
>1:	...
>
>					lock dec %[val]; # 0x80000000
>					jo  2f
>				1:	...
>
>
>
>
>2:	mov $0x7fffffff, %[val]

	panic()

>	jmp 1b
>
>				2:	mov $0x80000000, %[val]

					panic()

>					jmp 1b
>

... and we never get this far.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web