x86/refcount: Implement fast refcount_t handling

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.

Quoted 6 lines · Kees Cook

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?

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.

From include/linux/threads.h:

Quoted 8 lines · Peter Zijlstra

Quoted 6 lines · Kees Cook

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.

Quoted 8 lines

And is this impossible? Highly unlikely I'll grant you, but absolutely impossible?

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.

From include/linux/threads.h:

/*
* A maximum of 4 million PIDs should be enough for a while.
* [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.] */
#define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
(sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))

AFAICS that means you can only have up to 2^22 running tasks at a time, since every running task requires a PID in the init pid namespace.

Quoted 6 lines · Kees Cook

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?

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.

Quoted 2 lines · Peter Zijlstra

Also, you forgot nr_cpus in your bound. Afaict the worst case here is O(nr_tasks + 3*nr_cpus).

what does nr_cpus have to do with winning the race?

Quoted 2 lines

Because PaX does it, is not a correctness argument. And this really wants one.

heh, do you want to tell me about how checking for a 0 refcount prevents exploiting a bug?

Quoted 6 lines · PaX Team

Quoted 2 lines · Peter Zijlstra

Also, you forgot nr_cpus in your bound. Afaict the worst case here is O(nr_tasks + 3*nr_cpus).

what does nr_cpus have to do with winning the race?

The CPUs could each run nested softirq/hardirq/nmi context poking at the refcount, irrespective of the (preempted) task context.

Quoted 5 lines

Quoted 2 lines

Because PaX does it, is not a correctness argument. And this really wants one.

heh, do you want to tell me about how checking for a 0 refcount prevents exploiting a bug?

Not the point. All I said was that saying somebody else does it (anybody else, doesn't matter it was you) isn't an argument for correctness.

Quoted 8 lines · Peter Zijlstra

Quoted 6 lines · PaX Team

Quoted 2 lines · Peter Zijlstra

Also, you forgot nr_cpus in your bound. Afaict the worst case here is O(nr_tasks + 3*nr_cpus).

what does nr_cpus have to do with winning the race?

Quoted 2 lines

The CPUs could each run nested softirq/hardirq/nmi context poking at the refcount, irrespective of the (preempted) task context.

that's fine but are you also assuming that the code executed in each of those contexts leaks the same refcount? otherwise whatever they do to the refcount is no more relevant than a non-leaking preemptible path that runs to completion in a bounded amount of time (i.e., you get temporary bumps and thus need to win yet another set of races to get their effects at once).

that was exactly my point: all this applies to you as well. so let me ask the 3rd time: what is your "argument for correctness" for a 0 refcount value check? how does it prevent exploitation?

Quoted 10 lines · PaX Team

Quoted 8 lines · Peter Zijlstra

Quoted 6 lines · PaX Team

Quoted 2 lines · Peter Zijlstra

Also, you forgot nr_cpus in your bound. Afaict the worst case here is O(nr_tasks + 3*nr_cpus).

what does nr_cpus have to do with winning the race?

Quoted 8 lines

Quoted 2 lines

The CPUs could each run nested softirq/hardirq/nmi context poking at the refcount, irrespective of the (preempted) task context.

that's fine but are you also assuming that the code executed in each of those contexts leaks the same refcount? otherwise whatever they do to the refcount is no more relevant than a non-leaking preemptible path that runs to completion in a bounded amount of time (i.e., you get temporary bumps and thus need to win yet another set of races to get their effects at once).

For worst case analysis we have to assume it does, unless we can proof it doesn't. And that proof is very very hard, and would need to be redone every time the kernel changes.

Quoted 3 lines

that was exactly my point: all this applies to you as well. so let me ask the 3rd time: what is your "argument for correctness" for a 0 refcount value check? how does it prevent exploitation?

What 0 count check are you talking about, the one that triggers when we want to increment 0 ?

I think I've explained that before; per reference count rules 0 means freed (or about to be freed when we talk RCU).

The whole pattern:

if (dec_and_test(&obj->ref))
kfree(obj);

expresses this etc.. Other reference counts also do this. No references means its getting freed.

Can you agree with this?

If so; any attempt to increase the reference count while its (being) freed() is a use-after-free.

Quoted 8 lines · Peter Zijlstra

Quoted 4 lines · PaX Team

On 24 Apr 2017 at 13:15, Peter Zijlstra wrote:
that was exactly my point: all this applies to you as well. so let me ask the 3rd time: what is your "argument for correctness" for a 0 refcount value check? how does it prevent exploitation?

I think I've explained that before; per reference count rules 0 means freed (or about to be freed when we talk RCU).

you only said the same thing, what 0 means. you (still) didn't explain how checking for it prevents exploitation.

Quoted 9 lines

The whole pattern:

if (dec_and_test(&obj->ref))
kfree(obj);

expresses this etc.. Other reference counts also do this. No references means its getting freed.

Can you agree with this?

sure, so far so good.

Quoted 2 lines

If so; any attempt to increase the reference count while its (being) freed() is a use-after-free.

why would ever be there such an attempt? a freed object with intact memory content is as useful for an attacker as a live one, that is, not at all.

I think we're way off in the weeds here. The "cannot inc from 0" check is about general sanity checks on refcounts.

It should never happen, and if it does, there's a bug.

However, what the refcount hardening protection is trying to do is protect again the exploitable condition: overflow.

Inc-from-0 isn't an exploitable condition since in theory the memory suddenly becomes correctly managed again.

We're just discussing different things.

Quoted 2 lines · Kees Cook

I think we're way off in the weeds here. The "cannot inc from 0" check is about general sanity checks on refcounts.

I disagree, although sanity check are good too.

Quoted 1 line

It should never happen, and if it does, there's a bug.

The very same is true of the overflow thing.

Quoted 2 lines

However, what the refcount hardening protection is trying to do is protect again the exploitable condition: overflow.

Sure..

Quoted 2 lines

Inc-from-0 isn't an exploitable condition since in theory the memory suddenly becomes correctly managed again.

It does not. It just got free'ed. Nothing will stop the free from happening (or already having happened).

Quoted 1 line

We're just discussing different things.

No, both are bugs, neither overflow not inc-from-zero _should_ happen. The whole point is that code is buggy. If it weren't for that, we'd not be doing this.

How is the below not useful fodder for an exploit? It might be a less common bug, and perhaps a bit more fiddly to make work, but afaict its still a full use-after-free and therefore useful.

---

Thread-A Thread-B

if(dec_and_test(&obj->ref)) { // true, ref==0

                                                inc(&obj->ref) // ref: 0->1

        kfree(obj);
}

        ~~~/ Thread-C /~~~

        obj = kmalloc(); // is obj from Thread-A

        obj->ref = 1;
        obj->func = ....


                                                obj->func();

                                                        -- OR --

                                                put(obj);
                                                  if (dec_and_test(&obj->ref))
                                                    kfree(obj); // which was of Thread-C

On Mon, Apr 24, 2017 at 3:01 PM, Peter Zijlstra <[email protected]

Quoted 21 lines

wrote:

Quoted 3 lines · Kees Cook

I think we're way off in the weeds here. The "cannot inc from 0" check
is about general sanity checks on refcounts.

I disagree, although sanity check are good too.

Quoted 1 line

It should never happen, and if it does, there's a bug.

The very same is true of the overflow thing.

Quoted 3 lines

However, what the refcount hardening protection is trying to do is
protect again the exploitable condition: overflow.

Sure..

Quoted 2 lines

Inc-from-0 isn't an exploitable condition since in theory the memory suddenly becomes correctly managed again.

Quoted 2 lines

It does not. It just got free'ed. Nothing will stop the free from happening (or already having happened).

Well, yes, but that's kind of my point. Detecting inc-from-0 is "too late" to offer a protection. It offers notification of a bug, rather than stopping an exploit from happening.

Quoted 2 lines · Peter Zijlstra

It does not. It just got free'ed. Nothing will stop the free from happening (or already having happened).

Well, yes, but that's kind of my point. Detecting inc-from-0 is "too late" to offer a protection. It offers notification of a bug, rather than stopping an exploit from happening.

Quoted 2 lines · Kees Cook

I think we're way off in the weeds here. The "cannot inc from 0" check is about general sanity checks on refcounts.

I disagree, although sanity check are good too.

Quoted 2 lines

However, what the refcount hardening protection is trying to do is protect again the exploitable condition: overflow.

Sure..

Quoted 2 lines

Inc-from-0 isn't an exploitable condition since in theory the memory suddenly becomes correctly managed again.

It does not. It just got free'ed. Nothing will stop the free from happening (or already having happened).

How is the below not useful fodder for an exploit? It might be a less common bug, and perhaps a bit more fiddly to make work, but afaict its still a full use-after-free and therefore useful.

---

Thread-A Thread-B

if(dec_and_test(&obj->ref)) { // true, ref==0

                                                inc(&obj->ref) // ref: 0->1

        kfree(obj);
}

Quoted 6 lines · Peter Zijlstra

How is the below not useful fodder for an exploit? It might be a less common bug, and perhaps a bit more fiddly to make work, but afaict its still a full use-after-free and therefore useful.

---

Quoted 8 lines

Thread-A Thread-B

if(dec_and_test(&obj->ref)) { // true, ref==0

                                                inc(&obj->ref) // ref: 0->1

        kfree(obj);
}

... and tell me why an attacker would let Thread-B do that increment (that you're trying to detect) *before* the underlying memory gets reused and thus the 0 changed to something else? hint: he'll do everything in his power to prevent that, either by winning the race or if there's no race (no refcount users outside his control), he'll win every time. IOW, checking for 0 is pointless and you kinda proved it yourself now.

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Kees Cook

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.

note that the above is wrong (and even contradicting itself and the code).

Quoted 10 lines · PaX Team

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Kees Cook

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.

Quoted 1 line

note that the above is wrong (and even contradicting itself and the code).

True, this changelog could be more accurate (it resets to INT_MAX on overflow and INT_MIN on underflow). I think I'm right in saying that a system would need INT_MAX threads running a refcount_inc() (and a refcount_dec_and_test() at exactly the right moment) before the reset handler got scheduled, though, yes?

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).

Quoted 11 lines · PaX Team

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.

Quoted 13 lines · Kees Cook

Quoted 11 lines · PaX Team

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).

Quoted 3 lines

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)

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

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

Quoted 6 lines · Kees Cook

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?

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.

arch/x86/include/asm/refcount.h new file +6 -0

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

arch/x86/include/asm/refcount.h line 115

Quoted 11 lines · Kees Cook

arch/x86/include/asm/refcount.h new file +11 -0

+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.

Quoted 7 lines

arch/x86/include/asm/refcount.h new file +6 -0

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

Quoted 8 lines · Kees Cook

drivers/misc/lkdtm_bugs.c +0 -0

index e3f4cd8876b5..1bdafb29b802 100644
@@ -135,9 +135,15 @@ void lkdtm_HUNG_TASK(void)
      schedule();
 }
 

drivers/misc/lkdtm_bugs.c void lkdtm_HUNG_TASK(void) · line 142

Quoted 5 lines

drivers/misc/lkdtm_bugs.c +5 -0

+#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.

arch/x86/include/asm/refcount.h new file +28 -0

+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; \
+	}
+

So what avoids this:

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.

	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