From patchwork Sat Jun 25 01:13:12 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jann Horn X-Patchwork-Id: 9198321 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 3B43A6077D for ; Sat, 25 Jun 2016 01:13:48 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2595E284E2 for ; Sat, 25 Jun 2016 01:13:48 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1A2AD284ED; Sat, 25 Jun 2016 01:13:48 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, RCVD_IN_DNSWL_MED, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from mother.openwall.net (mother.openwall.net [195.42.179.200]) by mail.wl.linuxfoundation.org (Postfix) with SMTP id 1BBC7284E2 for ; Sat, 25 Jun 2016 01:13:45 +0000 (UTC) Received: (qmail 32504 invoked by uid 550); 25 Jun 2016 01:13:44 -0000 Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: kernel-hardening@lists.openwall.com Delivered-To: mailing list kernel-hardening@lists.openwall.com Received: (qmail 32034 invoked from network); 25 Jun 2016 01:13:33 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=EjIlB5+0rH/Qjyq20kmu5GPRElDZEmv5SoroOoaZpKs=; b=X1p7KpKiqZbw53LaebwmhiBbRldDgVKwckJr3zg5zYznpkxub1VbDr+G5O1driq1ca jBF/He2paCa/62j1VYdIwGHqynatgbSaPOglijc4w6k7YWdt7+cOfyNhombL62piQuYE b+aahjpfdZ/siMUAjVeHxdHgSUEvxvYAsRY1egYzDjrjNC+1tVWynmPUeztlEzHglpZd TEg26KQiA6202MSOy2K36eQJKNN5ojopWDzJZw5bHYlGJVCmB+RT9sF5JvajJvfu6QyH mpzUflg2oVVxEJP44MSjp2n8INk9f2twyehKHocML74G+XrcO8cYuUKybAJntAF2jCS8 yhuA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=EjIlB5+0rH/Qjyq20kmu5GPRElDZEmv5SoroOoaZpKs=; b=JAlPZgtO/kkNqqxy8JFUvi3IVBIhZZOmv4UXz3l2+weFuQQqhBACddIZMIZ8yMkK/w FNWsQ7yz6W5b7L/OueD3vSsBHaATWASLazHAjwTOKWv02JtcNVBAhtVY7dX+kjEgt3g0 LHACw05gV42XsO5IMGwrqo3U+UBx5g29X5K9Qs0gaYYLBSahpLp2pv2aOjIHGYVFd3of S+MUN0ZotBWbg6hRiLw6fMBz3IQuLtwXS6XUDwkJpi9r/TG1wAKYnvHHo7WmbwYSzbFP QH+HZgsPgjAWZ4EbhnYLOB65h3+jr4KGlXvMWiyWWjog+pAa/2x/79GKxHuwuCVjzUM3 BEIA== X-Gm-Message-State: ALyK8tIYQHindJBWPH/YQWlXpGRBk1TvtReLp3E84WTkGyEic7BFgEaAH6FL7VJHWcbK5Oz+ X-Received: by 10.28.132.15 with SMTP id g15mr691246wmd.67.1466817201622; Fri, 24 Jun 2016 18:13:21 -0700 (PDT) From: Jann Horn To: linux-kernel@vger.kernel.org, kernel-hardening@lists.openwall.com Cc: pageexec@freemail.hu, Kees Cook , jann@thejh.net, Jann Horn Date: Sat, 25 Jun 2016 03:13:12 +0200 Message-Id: <1466817192-9586-2-git-send-email-jannh@google.com> X-Mailer: git-send-email 2.8.0.rc3.226.g39d4020 In-Reply-To: <1466817192-9586-1-git-send-email-jannh@google.com> References: <1466817192-9586-1-git-send-email-jannh@google.com> Subject: [kernel-hardening] [RFC] kref: pin objects with dangerously high reference count X-Virus-Scanned: ClamAV using ClamSMTP Reference counting is a frequent source of (security) trouble in the kernel. Here are the three main things that can, as far as I know, go wrong with it, together with examples of specific bugs: - reference count overdecrement: If something (e.g. a normally-unused error path) decrements a reference counter more than it was previously incremented, this can cause the reference counter to end up lower than it was before. This will cause the object to be freed before the last reference to the object is gone. This bug class is hard to mitigate - it isn't very different from a generic use-after-free. Vulnerability examples: commit 8358b02bf67d ("bpf: fix double-fdput [...]") Bug examples where I haven't looked at impact: commit 75f0b68b75da ("debugfs: [...]: avoid double fops release") commit 121323ae668e ("drivers/perf: [...]: Fix reference count[...]") - reference count overincrement: If an error path omits a necessary reference count decrement, this can cause the reference counter to end up higher than it was before even though no new reference to the object was created. If such a bug is triggered around 2^32 times, the (32 bits wide) reference counter overflows to a small value. After dropping a few references so that exactly 2^32 references remain, the object will be freed prematurely. This kind of bug can easily occur when mistakes are made while writing error handling code. Vulnerability examples: commit 23567fd052a9 ("KEYS: Fix keyring ref leak [...]") Bug examples where I haven't looked at impact: commit b10e3e90485e ("debugfs: [...]: free proxy on ->open() failure") commit 3ea411c56ef5 ("android: fix reference leak in [...]") commit 8ed9e0e1b602 ("Input: turbografx - fix reference counting") - simple reference count overflow: If there are over 2^32 legitimate references to an object, a 32-bit reference counter can overflow. Since this can't happen on 32-bit architectures and normal references require at least a pointer, the minimum amount of physical memory required to hit this bug class is sizeof(void*) * 2^32 = 32 GiB ~= 34.36 GB. One example of a reference count overflow that could be triggered in some uncommon configurations on systems with 40GB of RAM is commit 92117d8443bc ("bpf: fix refcnt overflow"). The nasty thing about this bug class is that it doesn't require a "real" reference counting bug, and with increasing amounts of physical memory, the number of reachable instances of this issue increases. (Probably not at 64GB or so; but it might get dangerous around 1TB or so.) This patch is a first step towards addressing overincrements and simple overflows, but not overdecrements. My concerns when choosing an appropriate fix implementation are: - memory usage: An easy fix would be to increase the size of refcounts to 64 bits. However, that would both increase memory usage and mess with data structures that have been designed carefully to e.g. fit into a single cacheline. (Note: Because file descriptor tables can contain lots of struct file pointers and are relatively dense, struct file already has a 64-bit refcount.) - CPU usage: Refcounting is a central, relatively hot piece of kernel code, so a fix must not use a lot of CPU time. In particular, additional or less deterministic atomic operations should be avoided. - complexity: A fix shouldn't involve significant changes in arch-specific code. - crashiness: While these kinds of bugs currently cause (potentially exploitable) crashes and oopsing would be a big improvement over that, ideally the system should just keep going without killing anything. - impact on non-refcounting code: atomic_t is a generic atomic type, and while a lot of code uses it for reference counting, it also has other users for whom reference count hardening might mess up things. Since 2009 or so, PaX had reference count overflow mitigation code. My main reasons for reinventing the wheel are: - PaX adds arch-specific code, both in the atomic_t operations and in exception handlers. I'd like to keep the code as architecture-independent as possible, especially without adding complexity to assembler code, to make it more maintainable and auditable. - The refcounting hardening from PaX does not handle the "simple reference count overflow" case when just the refcounting hardening code is used as a standalone patch. (On a system with the full PaX patch, the active response code would probably prevent exploitation of this case.) I think that the biggest disadvantages of my code are: - It increases the size of the inline code for kref_get_unless_zero() and, if CONFIG_HARDEN_KREF_BIGMEM is enabled, of kref_sub(). (Also of kref_put_mutex(), but that method isn't used often.) - If CONFIG_HARDEN_KREF_BIGMEM is enabled, its kref_sub() implementation always has to do an additional READ_ONCE() on the reference count, which might cause slowdowns. The inline code in PaX is likely much smaller. To avoid impact on non-refcounting code, this patch only adds a mitigation to struct kref, not to atomic_t. The downside of that is that this patch alone does *not* mitigate issues in most reference counting code in the current kernel - that will require separate patches that change the various subsystems to use struct kref instead of atomic_t for reference counting. The basic way my patch works with REFCOUNT_HARDEN_BIGMEM enabled is that when a reference counter becomes too big (KREF_MAX_DECREMENTABLE or above), it is pinned, meaning that all further reference count increments and decrements on the object have no effect anymore. When REFCOUNT_HARDEN_BIGMEM is disabled, the code assumes that reference counts can't legitimately reach KREF_MAX_DECREMENTABLE and only half-pins the reference counter: It can't be incremented anymore, but it can still be decremented. If the attacker reached the high reference counter by exploiting an overincrement / missing decrement, he won't be able to undo the overincrements, meaning that it's safe to simply limit the reference counter like this. The straightforward way to implement reference count hardening would be to e.g. replace the atomic_inc_return() in kref_get() with an "increment and return unless equal" operation. However, on x86, atomic "unless equal" operations are implemented with cmpxchg loops, and I'd like to avoid replacing normal atomic operations with operations that have somewhat unpredictable performance. (Also, even in the fast case where the first cmpxchg succeeds, an extra atomic_read() has to be performed, and the inline code is a bit big.) Instead, with REFCOUNT_HARDEN_BIGMEM, my patch divides the positive reference counter values into three ranges: - In the first range, from 0 to 0x70000000, refcounters work normally. - In the second range, from 0x70000001 to 0x78000000, increments work normally, but decrements are blocked. The code is intentionally racy so that, if a reference counter goes above 0x70000000 while several kref_put() calls are in the middle of execution, it can go back down below 0x70000001. However, it shouldn't be possible to still get back into the first range from a refcounter near 0x78000000 - doing so would require having about 0x8000000 tasks, each of which would have to be preempted for quite a while in the middle of kref_dec(). Currently, the kernel has a hardcoded limit of 4 million PIDs that can be allocated, so even theoretically, this should be safe. Because in this range, only decrements are blocked, going into this range and back down into the first range can't cause the reference count to become too low, it can only cause it to become too high (causing a memory leak, harmless compared to a crash). - In the third range, from 0x78000001 to 0x7fffffff, both increments and decrements are blocked. This means that the reference counter can become lower than the number of references to the object, so the counter must not be allowed to go back into the "normal refcounting" range ever again. Again, the code is racy, but it shouldn't be possible to get to the end of the third range or back to the start of the second range because the range of movement of the reference counter is limited by the number of running tasks. Without REFCOUNT_HARDEN_BIGMEM, the first and second range behave identically, and in the third range, only increments are blocked under the assumption that the reference counter must be above the number of legitimate references, so ignoring increments just reduces the gap between the number of legitimate references and the reference counter state. If this patch lands, the next steps will be: - Go through the kernel and mechanically replace instances of atomic_t that are used for reference counting with struct kref. This will have to land in the form of big, ugly patches that touch many subsystems at once. - Add a checkpatch warning for newly-added atomic_t structure members. Notes regarding performance and similar stuff: This is the assembly diff (modulo changed addresses) of kobject_get(), which calls kref_get(), when compiling with CONFIG_64BIT and CONFIG_BUG on x86-64: + 48 8d 7b 38 lea rdi,[rbx+0x38] b8 01 00 00 00 mov eax,0x1 0f c1 43 38 xadd DWORD PTR [rbx+0x38],eax - ff c0 inc eax + 8d 70 01 lea esi,[rax+0x1] ff c8 dec eax - 7f 21 jg ffffffff8108947c - 80 3d 27 17 3a 00 00 cmp BYTE PTR [rip+0x3a1727],0x0 #<__warned.8073> - 75 18 jne ffffffff8108947c - be 2e 00 00 00 mov esi,0x2e - 48 c7 c7 fe d4 20 81 mov rdi,0xffffffff8120d4fe - c6 05 12 17 3a 00 01 mov BYTE PTR [rip+0x3a1712],0x1 #<__warned.8073> - e8 49 4e f9 ff call ffffffff8101e2c5 + 3d fe ff ff 77 cmp eax,0x77fffffe + 76 05 jbe ffffffff81089477 + e8 c6 3b fa ff call ffffffff8102d03d As you can see, the compiler optimizes the code so that basically only a "cmp" and some arithmetic are added, not even an extra conditional branch or so. For this reason, I believe that putting this part of the hardening behind a config flag would be more trouble than it's worth. For kref_put(), if CONFIG_REFCOUNT_HARDEN_BIGMEM is turned on, it's different (here in kobject_put()) - there are a new read from the counter, a comparison and a conditional branch: e8 72 4d f9 ff call ffffffff8101e223 + 8b 43 38 mov eax,DWORD PTR [rbx+0x38] + 3d 00 00 00 70 cmp eax,0x70000000 + 7f 0e jg ffffffff810894c9 83 6b 38 01 sub DWORD PTR [rbx+0x38],0x1 To be fair: Here I compared the new kref code against the old kref code - when code is ported from raw atomic_t to kref later, there will be an additional cost for the change from raw atomic_inc() to kref_get(). Thanks to pipacs for talking to me about refcount hardening. Thanks to kees for looking at a first version of this patch. Signed-off-by: Jann Horn --- include/linux/kref.h | 39 +++++++++++++++++++++++++++++++++------ init/Kconfig | 16 ++++++++++++++++ kernel/Makefile | 2 +- kernel/kref.c | 17 +++++++++++++++++ 4 files changed, 67 insertions(+), 7 deletions(-) create mode 100644 kernel/kref.c diff --git a/include/linux/kref.h b/include/linux/kref.h index e15828f..6c44a0d 100644 --- a/include/linux/kref.h +++ b/include/linux/kref.h @@ -20,10 +20,19 @@ #include #include +/* + * Strictly speaking, atomic_t is signed. Avoid undefined behavior by keeping + * the reference count below 0x80000000. + */ +#define KREF_MAX_DECREMENTABLE 0x70000000 +#define KREF_MAX_INCREMENTABLE 0x78000000 + struct kref { atomic_t refcount; }; +void kref_get_slowpath(struct kref *kref, unsigned int new_refcount); + /** * kref_init - initialize object. * @kref: object in question. @@ -39,11 +48,11 @@ static inline void kref_init(struct kref *kref) */ static inline void kref_get(struct kref *kref) { - /* If refcount was 0 before incrementing then we have a race - * condition when this kref is freeing by some other thread right now. - * In this case one should use kref_get_unless_zero() - */ - WARN_ON_ONCE(atomic_inc_return(&kref->refcount) < 2); + unsigned int new_refcount = atomic_inc_return(&kref->refcount); + + if (unlikely(new_refcount < 2 || + new_refcount > KREF_MAX_INCREMENTABLE)) + kref_get_slowpath(kref, new_refcount); } /** @@ -69,6 +78,12 @@ static inline int kref_sub(struct kref *kref, unsigned int count, { WARN_ON(release == NULL); +#ifdef CONFIG_HARDEN_KREF_BIGMEM + /* If the object has been pinned, leak the reference. */ + if (unlikely(atomic_read(&kref->refcount) > KREF_MAX_DECREMENTABLE)) + return 0; +#endif + if (atomic_sub_and_test((int) count, &kref->refcount)) { release(kref); return 1; @@ -103,6 +118,13 @@ static inline int kref_put_mutex(struct kref *kref, struct mutex *lock) { WARN_ON(release == NULL); + +#ifdef CONFIG_HARDEN_KREF_BIGMEM + /* If the object has been pinned, leak the reference. */ + if (unlikely(atomic_read(&kref->refcount) > KREF_MAX_DECREMENTABLE)) + return 0; +#endif + if (unlikely(!atomic_add_unless(&kref->refcount, -1, 1))) { mutex_lock(lock); if (unlikely(!atomic_dec_and_test(&kref->refcount))) { @@ -133,6 +155,11 @@ static inline int kref_put_mutex(struct kref *kref, */ static inline int __must_check kref_get_unless_zero(struct kref *kref) { - return atomic_add_unless(&kref->refcount, 1, 0); + int old_value = __atomic_add_unless(&kref->refcount, 1, 0); + + if (unlikely(old_value > KREF_MAX_INCREMENTABLE)) + atomic_dec(&kref->refcount); + + return old_value != 0; } #endif /* _KREF_H_ */ diff --git a/init/Kconfig b/init/Kconfig index f755a60..8618353 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1855,6 +1855,22 @@ config PROFILING config TRACEPOINTS bool +config HARDEN_KREF_BIGMEM + bool "Harden kref against too many references" + depends on 64BIT + default n + help + Prevent memory corruption caused by temporarily having more + references to a kref-managed object than the reference counter can + represent. + This increases security for systems with over 16GB of RAM (swap + doesn't count); if your kernel will only run on systems with <=16GB + of RAM, you can safely leave this disabled to reduce kernel code + size and increase performance. Even on systems with 64GB or so of + RAM, this only protects against worst-case kernel code that probably + doesn't exist; but if your kernel might run on a system with a + terabyte of RAM or so, you'll probably want to enable this. + source "arch/Kconfig" endmenu # General setup diff --git a/kernel/Makefile b/kernel/Makefile index e2ec54e..e2dcf8d 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -9,7 +9,7 @@ obj-y = fork.o exec_domain.o panic.o \ extable.o params.o \ kthread.o sys_ni.o nsproxy.o \ notifier.o ksysfs.o cred.o reboot.o \ - async.o range.o smpboot.o + async.o range.o smpboot.o kref.o obj-$(CONFIG_MULTIUSER) += groups.o diff --git a/kernel/kref.c b/kernel/kref.c new file mode 100644 index 0000000..2f277cc --- /dev/null +++ b/kernel/kref.c @@ -0,0 +1,17 @@ +#include +#include +#include +#include +#include + +void kref_get_slowpath(struct kref *kref, unsigned int new_refcount) +{ + /* If refcount was 0 before incrementing then we have a race + * condition when this kref is freeing by some other thread right now. + * In this case one should use kref_get_unless_zero() + */ + WARN_ON_ONCE(new_refcount < 2); + + if (new_refcount > KREF_MAX_INCREMENTABLE) + atomic_dec(&kref->refcount); +}