From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9543FEB64D8 for ; Wed, 21 Jun 2023 18:21:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0EA4F8D0003; Wed, 21 Jun 2023 14:21:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 09AB48D0002; Wed, 21 Jun 2023 14:21:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EA4728D0003; Wed, 21 Jun 2023 14:21:55 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id DD0E28D0002 for ; Wed, 21 Jun 2023 14:21:55 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 7490480864 for ; Wed, 21 Jun 2023 18:21:55 +0000 (UTC) X-FDA: 80927573790.16.EB9A5A0 Received: from mail-pg1-f175.google.com (mail-pg1-f175.google.com [209.85.215.175]) by imf01.hostedemail.com (Postfix) with ESMTP id 2850140025 for ; Wed, 21 Jun 2023 18:21:52 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=HK8K+XVP; spf=pass (imf01.hostedemail.com: domain of keescook@chromium.org designates 209.85.215.175 as permitted sender) smtp.mailfrom=keescook@chromium.org; dmarc=pass (policy=none) header.from=chromium.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1687371713; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=K6Gk7g2e3myD2tH63H8qrLIHXgdsP+ERfyqwv9FmHKA=; b=24Jp84YmdvQqhu7UQYh1zXW0MN0nUpZi989dgalb3VAub2D0MIty3+i0HKrbw0W4I9DuFg JFz1EfLfrqLkubgKVgIuDHr9PkksYB5OEr5Sj3Q322UI8ocH0qd5mwqBKKEJBBxtgGXhYX mDvoE+MTFjTdnHoQf/DANrlZILkbhCs= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1687371713; a=rsa-sha256; cv=none; b=8FODwJ8q4HBBsXNQ/9E6Klv9wkOUviUwA2bsGiUeSF1pmmkQ51nzMuGva0cg7+s9PmHzFP GepRe860pnFF+O6lTOsM0eEuMU1rFveLam8vMDRWiJ+pDBjh8tdcxq6lidO2j2wkDZ87tR tiWx93k2Wuh7bpA4Ai/yz0ghGqu8rO0= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=chromium.org header.s=google header.b=HK8K+XVP; spf=pass (imf01.hostedemail.com: domain of keescook@chromium.org designates 209.85.215.175 as permitted sender) smtp.mailfrom=keescook@chromium.org; dmarc=pass (policy=none) header.from=chromium.org Received: by mail-pg1-f175.google.com with SMTP id 41be03b00d2f7-54fb23ff7d3so3112740a12.0 for ; Wed, 21 Jun 2023 11:21:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; t=1687371712; x=1689963712; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=K6Gk7g2e3myD2tH63H8qrLIHXgdsP+ERfyqwv9FmHKA=; b=HK8K+XVPVpHrQ1TBLWxHjZGw3WZq+6agwyY4s0A5kBhe5WzViWHXCAmvm/2c4NxEEc 5bX6ioGxPIdLfu40Zqo087JGsSjMepJ8zBlsLsKn9h/mBfoDoN038lJ7xFP+/eEXuRlD oI7dse5fvt0FmTSwEGjrcu65EKDRviG72H44w= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687371712; x=1689963712; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=K6Gk7g2e3myD2tH63H8qrLIHXgdsP+ERfyqwv9FmHKA=; b=CJFmp/RViz9mufAkiDn2ierxNt0g6Uw93+9spprgHFMJAzgK+c6ywOqvz/WQDPN2eK UH81tyNWLcSSNRP5MNTWpPt/0bSjQI8EwcG8qFTHKDrsi4mQnaYs4n+It2PC7uoR5/Jh jdtaJKVMdHI9vHvYzUCyfPEfkkN0NvxtVD+fDU4rI7Eawev8yFkw4SNUqN075qaaBPqO GrMqPgvMaMIu5R9or/2V39OMWGw8eG8Q4XjS2NEC6YzSdT/xUFTetZpoO1wTDFws71RQ VfdcRWrpSgbPqXjh2mtsPNpcuYhsc9t7h1Z+10OFMaqAev36fdSzbV8Z7ATS7O7PamjE RH4A== X-Gm-Message-State: AC+VfDxlbFkotS9ca/2hsEQvXgX3+VIWssQ2l6TlpcUU+1zlmUk76k26 jsPLdV48ePQRzKc+1rj3qOnzGg== X-Google-Smtp-Source: ACHHUZ6tDaappzv2ihAfQqvCVZ7H1Q+IK7vT3D+MHa4nEA5bW0z+dgmIb3VIyINlPx/1903qiPnMlQ== X-Received: by 2002:a17:902:e745:b0:1b6:6985:ff5f with SMTP id p5-20020a170902e74500b001b66985ff5fmr7723499plf.36.1687371711957; Wed, 21 Jun 2023 11:21:51 -0700 (PDT) Received: from www.outflux.net (198-0-35-241-static.hfc.comcastbusiness.net. [198.0.35.241]) by smtp.gmail.com with ESMTPSA id iz7-20020a170902ef8700b001b0603829a0sm3801370plb.199.2023.06.21.11.21.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 21 Jun 2023 11:21:51 -0700 (PDT) Date: Wed, 21 Jun 2023 11:21:50 -0700 From: Kees Cook To: "GONG, Ruiqi" , Vlastimil Babka Cc: Andrew Morton , Joonsoo Kim , David Rientjes , Pekka Enberg , Christoph Lameter , Tejun Heo , Dennis Zhou , Alexander Potapenko , Marco Elver , Jann Horn , Roman Gushchin , Hyeonggon Yoo <42.hyeyoo@gmail.com>, Dmitry Vyukov , Alexander Lobakin , Pedro Falcato , Paul Moore , James Morris , "Serge E . Hallyn" , Wang Weiyang , Xiu Jianfeng , linux-mm@kvack.org, linux-hardening@vger.kernel.org, linux-kernel@vger.kernel.org, gongruiqi1@huawei.com Subject: Re: [PATCH v3 1/1] Randomized slab caches for kmalloc() Message-ID: <202306211111.4E70CD6@keescook> References: <20230616111843.3677378-1-gongruiqi@huaweicloud.com> <20230616111843.3677378-2-gongruiqi@huaweicloud.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230616111843.3677378-2-gongruiqi@huaweicloud.com> X-Stat-Signature: ecnaixosqbyr4pri3tzskuod95b36tpx X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 2850140025 X-Rspam-User: X-HE-Tag: 1687371712-871885 X-HE-Meta: U2FsdGVkX19c3ZraqSSHs6BhL3xz6zk0ss80eH9xbL5gvQbj171rZkRbi5PqLf9siZFRkk4YiCryxD/FhLyG8UAW35bSeAVNIE8ljzP8Xk6BR6q+M/DUxAD2pcUfVqNtbIXYLBhYMBUOzFe88P1uKUcLrUds44HZ485XmlENPdyDeDVmoHeMIYB+xYKpLr3eIZO0PNHrQgqQ0sSbCJg46S0e5njDcF5UL0bKg65o3rQlvJMeqsianGSZY99Tf1BmBoxYf9M24R0FTbfCYaJrsHzMCVObtT3Ab3DnoM9jdeLGXZPjH/69DXW9LRlxuj4LSaYAcAAtKmB8NG50yzXAdhAearku405E0N2V4tHoHz8s3ZnZTlhgG2SsDrUY99qnA47FH2SNhaPRvi4pu3a8a2y474FakXXI9dNmOvXszTiPs0B1bSqf8FcdcHTxg0Lc6Vuch+vYfKATcanwpMRMPFcrwSHzOyDMvEOw0ZDnjKxWhFuIGvP9lhPRdFzESzmh0UMys5NMGE29BZ1h8XqzclpMAgv61Stf0TCNqNKwEA5PSRyFNVBrv2Utvg/JjGMPu+xyJfs9820c6d1DrI8oCbtz+bM2HKHyg42whiv+wWV5rkzqI96LFJHC5erlDH1tDQbnAA6avGATvUtyUn9WdIlOf4CJHvFHrgQt4DVV1hbuPV5c0qwllFuRx0ipBP2IAGQdzCcJK4Bbv6al7D+uaRsMjZofztFrh0bHYmGBRcDuE239q6R9VoxFuNfefHcu2xl60vU8k0iHfpf4fGLpWBpgcDgi6Wk0wBH8sap75oToTGzZSfdgV5ghvy/TTWVOrQXLQbLNY6MSsP+Lwx+JZd2KGwS0i0Uu5vXNTJh1Nt12Jz6Z+bJd9prLHObTY+etRL8WD6M8vRgS+1sDvm8WtyrvfkSXnDfoyFAmdAUPX9Gv4TtGatjv+2zn4AWdIYLd5MR3uZd++r6b3JcJbq6 FFgBDisB zP/SxlBIemxjGJ87FBOhNbVKWZ9nuD8bZrIY7cmyscVFqiAKA1P3isJQWmg7HnxWRZzWMoE49IE6YmeY9Lu7hZCKKd84i2wcz5T+nmT0bwfLkL/2qHh9dliNYeHSzfK+bP2uxKl+Y+gvJ7B7rkHqQr8NQTZQClgCQzhiWzxPVhyR39LTL//RuzNwVqReXJxJJqjJEAjfud0TkN67eUXHpXKFCy51+LGIttXkCzEUtK+DDffVj6TCxtZSsAbhvsO7F22Umoqwp0AN8VCnDeM1vhVFNofmph4HJ5EokfiC0exq4TyqtTmQx0b7Wm++yPeC5waAfLrrvCLlGyXgWLGF/bmfBvuNWXHMUaUgLJKRJ6tGkz6J0k/fDrigPu4+qeh/64IqdAza4dOvnhARzU6po7yyvflSBjl7Vf6wy9Q4R9rS68FI5DqjU3J2WorPWxZvSeCccc6lwfrap2vraq2hOBBFkBqlghVSOzigbBHo3PvtdxRHab4Gh5dWgGsDU/nx6ACWKfdHzk4gmLr1h4oJnjcMR2T2OHLiX9UENmlXhz9erblf8UhvNQ03N4OkDT/SodVBxL6doSYJefvzwO48yMEx0aGe6UOy4sjzvjCfqm83qJYc= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Fri, Jun 16, 2023 at 07:18:43PM +0800, GONG, Ruiqi wrote: > When exploiting memory vulnerabilities, "heap spraying" is a common > technique targeting those related to dynamic memory allocation (i.e. the > "heap"), and it plays an important role in a successful exploitation. > Basically, it is to overwrite the memory area of vulnerable object by > triggering allocation in other subsystems or modules and therefore > getting a reference to the targeted memory location. It's usable on > various types of vulnerablity including use after free (UAF), heap out- > of-bound write and etc. > > There are (at least) two reasons why the heap can be sprayed: 1) generic > slab caches are shared among different subsystems and modules, and > 2) dedicated slab caches could be merged with the generic ones. > Currently these two factors cannot be prevented at a low cost: the first > one is a widely used memory allocation mechanism, and shutting down slab > merging completely via `slub_nomerge` would be overkill. > > To efficiently prevent heap spraying, we propose the following approach: > to create multiple copies of generic slab caches that will never be > merged, and random one of them will be used at allocation. The random > selection is based on the address of code that calls `kmalloc()`, which > means it is static at runtime (rather than dynamically determined at > each time of allocation, which could be bypassed by repeatedly spraying > in brute force). In other words, the randomness of cache selection will > be with respect to the code address rather than time, i.e. allocations > in different code paths would most likely pick different caches, > although kmalloc() at each place would use the same cache copy whenever > it is executed. In this way, the vulnerable object and memory allocated > in other subsystems and modules will (most probably) be on different > slab caches, which prevents the object from being sprayed. > > Meanwhile, the static random selection is further enhanced with a > per-boot random seed, which prevents the attacker from finding a usable > kmalloc that happens to pick the same cache with the vulnerable > subsystem/module by analyzing the open source code. > > The overhead of performance has been tested on a 40-core x86 server by > comparing the results of `perf bench all` between the kernels with and > without this patch based on the latest linux-next kernel, which shows > minor difference. A subset of benchmarks are listed below: > > sched/ sched/ syscall/ mem/ mem/ > messaging pipe basic memcpy memset > (sec) (sec) (sec) (GB/sec) (GB/sec) > > control1 0.019 5.459 0.733 15.258789 51.398026 > control2 0.019 5.439 0.730 16.009221 48.828125 > control3 0.019 5.282 0.735 16.009221 48.828125 > control_avg 0.019 5.393 0.733 15.759077 49.684759 > > experiment1 0.019 5.374 0.741 15.500992 46.502976 > experiment2 0.019 5.440 0.746 16.276042 51.398026 > experiment3 0.019 5.242 0.752 15.258789 51.398026 > experiment_avg 0.019 5.352 0.746 15.678608 49.766343 > > The overhead of memory usage was measured by executing `free` after boot > on a QEMU VM with 1GB total memory, and as expected, it's positively > correlated with # of cache copies: > > control 4 copies 8 copies 16 copies > > total 969.8M 968.2M 968.2M 968.2M > used 20.0M 21.9M 24.1M 26.7M > free 936.9M 933.6M 931.4M 928.6M > available 932.2M 928.8M 926.6M 923.9M > > Signed-off-by: GONG, Ruiqi > Co-developed-by: Xiu Jianfeng > Signed-off-by: Xiu Jianfeng I think this looks really good. Thanks for the respin! Some nits/comments/questions below, but I think this can land and get incrementally improved. Please consider it: Reviewed-by: Kees Cook > diff --git a/include/linux/slab.h b/include/linux/slab.h > index 791f7453a04f..b7a5387f0dad 100644 > --- a/include/linux/slab.h > +++ b/include/linux/slab.h > @@ -19,6 +19,9 @@ > #include > #include > > +#ifdef CONFIG_RANDOM_KMALLOC_CACHES > +#include > +#endif I think this can just be included unconditionally, yes? > [...] > +extern unsigned long random_kmalloc_seed; > + > +static __always_inline enum kmalloc_cache_type kmalloc_type(gfp_t flags, unsigned long caller) > { > /* > * The most common case is KMALLOC_NORMAL, so test for it > * with a single branch for all the relevant flags. > */ > if (likely((flags & KMALLOC_NOT_NORMAL_BITS) == 0)) > +#ifdef CONFIG_RANDOM_KMALLOC_CACHES > + return KMALLOC_RANDOM_START + hash_64(caller ^ random_kmalloc_seed, > + CONFIG_RANDOM_KMALLOC_CACHES_BITS); > +#else > return KMALLOC_NORMAL; > +#endif The commit log talks about having no runtime lookup, but that's not entirely true, given this routine. And xor and a hash_64... I wonder how expensive this is compared to some kind of constant expression that could be computed at build time... (the xor should stay, but that's "cheap"). > > /* > * At least one of the flags has to be set. Their priorities in > @@ -577,7 +589,7 @@ static __always_inline __alloc_size(1) void *kmalloc(size_t size, gfp_t flags) > > index = kmalloc_index(size); > return kmalloc_trace( > - kmalloc_caches[kmalloc_type(flags)][index], > + kmalloc_caches[kmalloc_type(flags, _RET_IP_)][index], > flags, size); > } > return __kmalloc(size, flags); > @@ -593,7 +605,7 @@ static __always_inline __alloc_size(1) void *kmalloc_node(size_t size, gfp_t fla > > index = kmalloc_index(size); > return kmalloc_node_trace( > - kmalloc_caches[kmalloc_type(flags)][index], > + kmalloc_caches[kmalloc_type(flags, _RET_IP_)][index], > flags, node, size); > } > return __kmalloc_node(size, flags, node); The use of _RET_IP_ is generally fine here, but I wonder about some of the allocation wrappers (like devm_kmalloc(), etc). I think those aren't being bucketed correctly? Have you checked that? > [...] > @@ -776,12 +781,44 @@ EXPORT_SYMBOL(kmalloc_size_roundup); > #define KMALLOC_RCL_NAME(sz) > #endif > > +#ifdef CONFIG_RANDOM_KMALLOC_CACHES > +#define __KMALLOC_RANDOM_CONCAT(a, b) a ## b > +#define KMALLOC_RANDOM_NAME(N, sz) __KMALLOC_RANDOM_CONCAT(KMA_RAND_, N)(sz) > +#if CONFIG_RANDOM_KMALLOC_CACHES_BITS >= 1 > +#define KMA_RAND_1(sz) .name[KMALLOC_RANDOM_START + 0] = "kmalloc-random-01-" #sz, I wonder if this name is getting too long? Should "random" be "rnd" ? *shrug* > [...] > +#define KMA_RAND_16(sz) KMA_RAND_15(sz) .name[KMALLOC_RANDOM_START + 15] = "kmalloc-random-16-" #sz, And if we wanted to save another character, this could be numbered 0-f, but I defer these aesthetics to Vlastimil. :) -Kees -- Kees Cook