Two approaches to reference count hardening

With reference counts, the most common bugs are failure to decrement a counter and decrementing the counter when a reference is not held. Both often happen in error paths and can go undetected for a long time, since those paths are lightly tested at best and rarely executed. An error situation might lead a function to return without performing a necessary decrement, or it may decrement a count that, in fact, had not yet been incremented. But these bugs can pop up in non-error paths as well; they often go unnoticed, since they rarely result in obvious explosions.

Excessive decrements will cause an object to be freed before the last real reference has been released, leading to a classic use-after-free situation. Such errors are often exploitable; see CVE-2016-4557 (and the associated fix) for a recent example. Excessive increments, if they can be provoked by an attacker, lead to a similar scenario: first the counter is overflowed, then decremented back to zero, leading to a premature freeing of the object. CVE-2016-0728 (fixed with this commit) is an example of the trouble that can ensue. Needless to say, it would be nice to catch this type of error before it gets to the point of being exploitable by an attacker.

As is so often the case, the oldest work in this area seems to have been done in the PaX project. This work starts with the kernel's atomic_t type, which is often used to implement reference counts. The kernel provides a set of helper functions for performing operations (increments and decrements, for example) on atomic_t variables, so it makes sense to add overflow checks to those functions. That must be done carefully, though, since operations on atomic_t variables are often in hot paths in the kernel; changes that increase the size of the atomic_t type are also unlikely to be accepted.

In the PaX case, the relevant operations, most of which are already implemented in assembly, are enhanced to perform overflow checks. Often that is just a matter of checking the condition-code flags set by the processor as a result of the increment or decrement operation. Should an overflow be detected, the response is architecture-dependent, but results in some sort of kernel trap. The overflow is undone, the process that overflowed the counter is killed, and a message is logged.

This checking catches attempts to exploit the overflow (excessive increment) bugs handily; that class of bugs is rendered unexploitable. Excessive decrements are harder to catch, since decrementing a reference count to zero is a part of normal operation. If such a bug exists, though, it will almost certainly show itself by decrementing the counter below zero occasionally, even in normal operations. With checking in place, somebody should notice the problem and it should be fixed.

There is one catch that makes this patch more invasive than one might expect, though: not all uses of atomic_t are reference counts. Other uses, which might legitimately wrap or go below zero, should not have this type of checking enabled. To get to that point, PaX adds atomic_unchecked_t type and converts a large set of in-kernel users; that leads to a fair amount of code churn.

Back in December, David Windsor posted a version of the PaX reference-count hardening patch set for review. A certain amount of discussion followed, and some problems were pointed out, but there was little opposition to the idea in general. Unfortunately, David vanished shortly thereafter and never followed up with a new version of the patches, so they remain outside of the mainline. Nobody else has stepped up to carry this work forward.

More recently, Jann Horn has posted a different approach to the refcount problem. Rather than change the atomic_t type, this patch set changes the kref mechanism, which exists explicitly for the implementation of reference counts. This choice means that far fewer locations in the kernel will be protected, but it makes the patch set far less invasive and allows testing of the underlying ideas.

Jann's patch set eschews assembly tweaks in favor of entirely architecture-independent checking, a choice which, he later conceded, might not be the most efficient in the end. With this patch in place, special things happen once a reference count reaches a maximum value (0x70000000): after that point, increments and decrements are no longer allowed. In essence, a reference count that large is deemed to have already overflowed, so it is "pinned" at a high number to prevent premature object freeing. No warnings are emitted, and no processes are killed.

While he had no objection to the patch as it was, Kees Cook said that he would rather see the checking done at the atomic_t level, since so much reference counting is done that way. Greg Kroah-Hartman agreed, noting that the process of auditing atomic_t users would turn up a lot of places where kref should be used instead. Adding overflow checking to atomic_t would protect kref automatically (since krefs are implemented as a wrapper around atomic_t), so it really does seem that, despite the large number of changes required, this protection should be done at the lower level.

Of course, there is already a working patch set for the detection of atomic_t overflows: the PaX code. The work to separate it out and turn it into a standalone kernel patch has even been done. The flag-day nature of the change (all non-reference-count uses of atomic_t have to change when the semantics of atomic_t do) is will make the process of upstreaming this patch a bit harder, but such changes can be made when they are justified. Closing off a class of errors that has demonstrably led to exploitable kernel vulnerabilities would seem like a reasonably strong justification.