Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <36019eb3-4b71-26c4-21ad-b0e0eabd0ca5@intel.com>
Date:   Wed, 5 Apr 2023 17:15:44 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.9.0
Subject: Re: [PATCH RFC] Randomized slab caches for kmalloc()
Content-Language: en-US
To:     Hyeonggon Yoo <42.hyeyoo@gmail.com>
CC:     "GONG, Ruiqi" <gongruiqi1@huawei.com>,
        Dennis Zhou <dennis@kernel.org>, Tejun Heo <tj@kernel.org>,
        Christoph Lameter <cl@linux.com>,
        Pekka Enberg <penberg@kernel.org>,
        David Rientjes <rientjes@google.com>,
        Joonsoo Kim <iamjoonsoo.kim@lge.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        Vlastimil Babka <vbabka@suse.cz>,
        Roman Gushchin <roman.gushchin@linux.dev>,
        Alexander Potapenko <glider@google.com>,
        Marco Elver <elver@google.com>,
        Dmitry Vyukov <dvyukov@google.com>, <linux-mm@kvack.org>,
        <linux-kernel@vger.kernel.org>, <kasan-dev@googlegroups.com>,
        Kees Cook <keescook@chromium.org>,
        <linux-hardening@vger.kernel.org>,
        Paul Moore <paul@paul-moore.com>,
        <linux-security-module@vger.kernel.org>,
        James Morris <jmorris@namei.org>,
        Wang Weiyang <wangweiyang2@huawei.com>,
        Xiu Jianfeng <xiujianfeng@huawei.com>
References: <20230315095459.186113-1-gongruiqi1@huawei.com>
 <b7a7c5d7-d3c8-503f-7447-602ec2a18fb0@gmail.com>
From:   Alexander Lobakin <aleksander.lobakin@intel.com>
In-Reply-To: <b7a7c5d7-d3c8-503f-7447-602ec2a18fb0@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?ZE9RTi8vUmxpc0tJTWNueVZVWmxaMTUydjc0Z2thS0Q1cm5pYVlCbVVCVy8z?=
 =?utf-8?B?dzJ6MXlBRlFObGw4YmM2L3JCWFV6UXgxV04yNlZ3ZmU1MFpraWI4Yll4TW1Z?=
 =?utf-8?B?dUJJVi9PMmw0UTAxQmEzbzlYVzdoeGFPVS9BdXFIYk53Mm1iMElrUUZPaG1U?=
 =?utf-8?B?V3orL2M4NVQzWlYwWkM0VHNEZHdteDJKNXRZOU9wTnc2MVJmR2RxUGpqaEFl?=
 =?utf-8?B?YzM3M3hUUVRvVVJjaU5GN0RnSXlBb3FkaVB5MnVPZjdtOVhkT0xQbGMzMHQy?=
 =?utf-8?B?WmFqRXhTakJFMFBMOGxrWGJoenZHOGdSVmhlY3pnOVp6TWdjalg5ajVuTWhZ?=
 =?utf-8?B?RnArQnpvUHhuT0VZckx5QXZpcW9ybHVmVTlNM1ExbEVhdWNpWGh0VlNXZmpK?=
 =?utf-8?B?Y1BoZFAvaStUd2MzemRxZFdIMkFFWGFpZDN2WDlKQTVLWWxvOFVuRVcyT3I2?=
 =?utf-8?B?amtxNEhLMGlMZ0xPYmtVN1VjdjR5K2VsQ21nczR0elNnT3ExeTFhK0xtbHly?=
 =?utf-8?B?WHVTamlQNDEvZm5OcUpYT3ZtdWZvaXgxc1JucDE0WUdFMmtNMG5uSmJma1pD?=
 =?utf-8?B?MHlBSDlYRlV4Qm04dUp2WXg4Y1RtQy9XcGIxYlUyVjdFdkRQODVSNEJCSE5p?=
 =?utf-8?B?K0U0bmEvdDVCUmF6NDhsQzA1VUt2enEyMWNwcFdmd3pqSEg3Y3l4TzJSUXYx?=
 =?utf-8?B?WE81WTVZaEhadEZXMEdKZ3ZhZGZFeGxkMXFpSnNsVVNqamJ3R1RBVk5OSTlu?=
 =?utf-8?B?N2dFMndTZ2pDenpFd3Q3aXB2NlMzN3plUURWMTFOMUFYeDZWbVY2eTkvRjg3?=
 =?utf-8?B?YzRRZ0U2MXJzd0RndkJ3VUtmREk0TzB5cjIxNXBWWHpGMVBVWkh0MXlKelln?=
 =?utf-8?B?bTZNc0RvVXdFdWtDejA4eCszT3VGS01NSlptUUxnVk12bm1ZYnFzOXpid3Vy?=
 =?utf-8?B?bHhKb0cycHNwSG00Q1NqbnUxTnRzQ2x6NTR4UEU0eDdqVUNmZW5IZmx0Qk5o?=
 =?utf-8?B?eUNpeXJJRngrbUUvODJQNnd0bVpQWThNeHdsbDMzUmlEbXZPY1lJWU5uQzJo?=
 =?utf-8?B?eTl2VFJvalhFeDFnUWZ5K0R3VklnOUR5YUxFZUlrVXZ5QW0zcVBYcysvWHh0?=
 =?utf-8?B?QW1DNVRxN2liMlM3anlOaVphblFXdi8wWG9pNHRLSUlDZ00ya1ZwdGkvZnlK?=
 =?utf-8?B?ZURRdE91WFBNdHlzLy8vMk1xdytJSzRHenZDQzBadm1LMWtLQzRNdUlER0o4?=
 =?utf-8?B?YlQ2VENDMWZTZndmMElPVnIvR1E2VTFzVXhPZXUrUW9DdG10VUxzdDluallm?=
 =?utf-8?B?cFArblYwSmQ0d1diRkRFR2FhWGxMWERHYnBic3gvTGlJZ1dwenFRa3VnUnY1?=
 =?utf-8?B?RUlvdW9yeHRBb0I0T2lmczBsdTRvN2M4M2c1VytNd2ZZQ2ZxWjRaeFcxUGZp?=
 =?utf-8?B?YkZvQXRzQzUraVA2dllUUXZDVDRDenlqUTJJblNXeXdSQ3VqZWhDSnk3TG16?=
 =?utf-8?B?bzliWDYvTkNmUmRrUTdOZEhubWhSaDY5MlUrTExhWFg5d25nS0srSjI5WjNC?=
 =?utf-8?B?SkJIRXhsNlJ2VzRzdlJPb0FMdVpLZzNFUU5sN25vUXdCUXUvY2NYQmRJVmNW?=
 =?utf-8?B?ZEJtRjBlKzY2d0paeXRpeVN4L1hwNEZlZmhtVkw1NGIydmwyL3VNUVozcGZt?=
 =?utf-8?B?cWo2NXd3bXFXNmRta1RlSE9PeUhrRGhYVmV4WEZKTG1xaXIraFlKY0d5THRH?=
 =?utf-8?B?eVlydzRpSmFObC90WUYya0xmVzA2MmNvR0JBWG04dUR5YlM1RDVWUk9iZGJr?=
 =?utf-8?B?NmxHdkN6THZlV005WGd5ekF1MktWUmxZSUdPNElncDQxbS9hWXh6UkduM091?=
 =?utf-8?B?amVwU1dzaWs5akdmWDJQM0ZDVlBNME9ndm5Jb3ZyeXVUSS9ReHNLWTQ2Uk1I?=
 =?utf-8?B?cTFNTDVRN1QyVjYyYjZ2bzhSK1FUcFFTMXpUQ0FTTmh1TU9TR1RnL1FGL1BE?=
 =?utf-8?B?cGxYWkRMRUNJV2psL0crVXkzSlcyTE5STG85MXlaamZOM3hVL1paaFZuOE43?=
 =?utf-8?B?U1FlaVZSR3p5S1BIbmM1WEU5WEJTWFhzUXJ3THVYSlUzbHFTNUlFVEV2TzFL?=
 =?utf-8?B?cURRSGl0bXorWlU4ZkI1eStLL0sxYXNteTF3TTR3Q1ZYNlNuZCtEeTlMZmtk?=
 =?utf-8?B?ekE9PQ==?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 65c95da6-7e9b-4247-3f82-08db35e8a4c3
X-MS-Exchange-CrossTenant-AuthSource: DM6PR11MB3625.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Apr 2023 15:15:51.9118
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: B3IC8UCDPKjxeE36/sk+aZBmtzIFbuS/nzrFWpBOwSBRCvUZP2bLWWetEegqRFEOBbW9BhswKVnDgCDqpHw/2Sa7A7vsx/HSY+PUJ9q1oBc=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR11MB4534
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-3.9 required=5.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,RCVD_IN_DNSWL_MED,
        SPF_HELO_NONE,SPF_NONE autolearn=unavailable autolearn_force=no
        version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

From: Hyeonggon Yoo <42.hyeyoo@gmail.com>
Date: Wed, 5 Apr 2023 21:26:47 +0900

> On 3/15/2023 6:54 PM, 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 location 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 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.
>>
>> Signed-off-by: GONG, Ruiqi <gongruiqi1@huawei.com>
>> ---
> 
> I'm not yet sure if this feature is appropriate for mainline kernel.
> 
> I have few questions:
> 
> 1) What is cost of this configuration, in terms of memory overhead, or
> execution time?
> 
> 
> 2) The actual cache depends on caller which is static at build time, not
> runtime.
> 
>     What about using (caller ^ (some subsystem-wide random sequence)),
> 
>     which is static at runtime?

Why can't we just do

	random_get_u32_below(CONFIG_RANDOM_KMALLOC_CACHES_NR)

?
It's fast enough according to Jason... `_RET_IP_ % nr` doesn't sound
"secure" to me. It really is a compile-time constant, which can be
calculated (or not?) manually. Even if it wasn't, `% nr` doesn't sound
good, there should be at least hash_32().

Thanks,
Olek