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: <ce1c307e-b7ae-2590-7b2e-43cbe963bc4d@intel.com>
Date:   Mon, 24 Apr 2023 15:46:30 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.10.0
Subject: Re: [PATCH RFC] Randomized slab caches for kmalloc()
Content-Language: en-US
To:     Gong Ruiqi <gongruiqi1@huawei.com>
CC:     Hyeonggon Yoo <42.hyeyoo@gmail.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>
 <36019eb3-4b71-26c4-21ad-b0e0eabd0ca5@intel.com>
 <f5b23bbc-6fb5-84d3-fcad-6253b346328a@huawei.com>
From:   Alexander Lobakin <aleksander.lobakin@intel.com>
In-Reply-To: <f5b23bbc-6fb5-84d3-fcad-6253b346328a@huawei.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?cDZOMGFneFZQVjFHZnd2SHdBeUpSUFl3OGtrV3gwV3ZqaG9KdnlwRVBGOEdq?=
 =?utf-8?B?SzRsbEdXaTd0WlZyVDRseHp3SEx3MHdTV2dURXM1anBHV1hNRUdMYUVCTDl2?=
 =?utf-8?B?am52WjNyMURPU2xYanYyZ0ZCNm42Yi9BWXNDbFlSNzdEbEgzZysvSjE4OFQz?=
 =?utf-8?B?T25qMGlFUUlUTkdxT0hBWmFvaUxEMk5SaGV4dG1DUGFudGdXQ24wWHhua0l0?=
 =?utf-8?B?MSttb1JYOEQ1YXk4ZGYraWgvb09zUTFRQ0h6NWNvK3ZXRkpBTzc2VnZJSU1S?=
 =?utf-8?B?MWE2MEhyYm04LzNsWDRyVy9hZDlpVXhsTFNMczJ5bDd2Wkh6VGtDamZCMWh2?=
 =?utf-8?B?VC82WEx3Z0RKM09hQVlGODFHSUZKcmNRTVFpTnFzenBDdGUyNnZ0YmdVd2Jk?=
 =?utf-8?B?Y1NQTmZETGN2bnlJU0RnZFhRMjlqZ3ovVHNUVDlkcDFUUjRIYU5DK1Y4RGhJ?=
 =?utf-8?B?RDFNN1hhOVVuWm5ZVWZtaXY0Ujg4QnFGVlAzYk53bnJWUjZKOEwrOFkreHlF?=
 =?utf-8?B?TG5INjI2V3pJelp4YVhOMkMzN2l1VUYvdllQa0hmY0UzMVBDNE9ubVBicFd6?=
 =?utf-8?B?ZU5PRE1hbjUvVlRNTytneXoyRTg3b2tjaW90U2lhdGZwNnZibnh1VmRqbS9C?=
 =?utf-8?B?cHN2VCtqcGVybVpYUlhPenI4RjBrclhXZy9PbVlWL05IZ1gyS2dqcmFqaTFx?=
 =?utf-8?B?RjE4ZFVwdnliUDlDeldNbnp0RVh4Q29TNHRmNk50M1VqYU5lY1dqM3FURTlD?=
 =?utf-8?B?TmwyYVNzYjhKZkpRVDMzWFdwM1FmWU5Rak0va3VjM2JGVWZzeldOV3oxNTRi?=
 =?utf-8?B?RkIyRHV4RE9pQU5pdFN6VGxocVVUZmlycHdnRWFrM1VBYVB5Sm1tRmU5bUpY?=
 =?utf-8?B?KzhPbG5vZWtUeUFqVXpKenY2U21saWNXbXNFWHF4aVNoSGJFWkpkR2lvWFRV?=
 =?utf-8?B?MktlQStCQlcwOFFaSFdnL0VxSkZteXZLVUMvNnJCSG5lc2tFcjgrVU1kQm44?=
 =?utf-8?B?V1pBWW9oSHhiMG5TbGYxWTFFYWtHM3hEeVZQSm5XMDUyTnZ2dnNtVm9vRHg3?=
 =?utf-8?B?TFY1UGtkYWF1d1RpOUJZWTcwN0Q0enN3T1VqWFNDRlBDODk3MmZ2cVpjMWti?=
 =?utf-8?B?c3VmTEZERlA0em12b3phRTBhcmZyVEUwQ2dkS2xPR2pBbEZQR1llWWI1Vk55?=
 =?utf-8?B?QUJJYXlaZVZUYm1UWGhWOEduaXBpMTRMSEdWdncyTEloaHF3c2JZRWdRTGt2?=
 =?utf-8?B?OU5BbjNBbmtvbHhISXZSdFIzNjlBbDBOc3hvYzNtblhQaUoyVTBjMGpkMEM0?=
 =?utf-8?B?UG1NcXBmV0hIaWdLYUxPYXc0RmxPb1I5OUp3WXZEYjhWUHdDVHkzRWZINFl1?=
 =?utf-8?B?cGZsZnZIQm15dTVvcGNVQlNGaXgrNHJuRmQwcXNkS1lyYXNMR2xWUkUzYmo1?=
 =?utf-8?B?TVZkbDVqaU5qeEQ3YndmZjlKc0RGMkNQdmUyZTZ1N3BjblV1SHdLUWQ0Nktu?=
 =?utf-8?B?Vit1VWJSTm9SeUhUSzZUd0FzVVdiMWFaMjRHY3V5Ryt0SkJySFc3YmhBQ2Jw?=
 =?utf-8?B?alhRYTNJeFVZb0JLYmd3UFVTcjF3NFZoSWpIM3FvUUVMTWNoU0RrSXg4bjJL?=
 =?utf-8?B?MVc3NmxaaEJCd1JRaUlPTUVjbVpZZmxoRXBsOXYwMEpCektod1RtQytHU1l2?=
 =?utf-8?B?OUk1SHhRSHMwbHpCSTZZZU1XQ0t0dU4yclFXSzZyVk5GalBpc3lDb3RJNlJ3?=
 =?utf-8?B?b21udjNwNnd3bUsvQ3g5UlRwZ292ajFxWHZwUXdQbzVyVlFkek1aQ2VUTFdy?=
 =?utf-8?B?YzcyMWRiU1JmVjV1YXhpN2xwYjY5Mk9hUm9naWxGU2NaQXJUamZNUWJJZk5M?=
 =?utf-8?B?ak81OFdCblVxbmZTMzQ0RTB4VGpEVlA0bncxL25ic3VwUFhsM2YxL2Q3SURw?=
 =?utf-8?B?WFhQQktMeUZxUXVWSW1JcFdkSnJqME1BeTFnakNqcStSOHU4TnNja0U3dFlh?=
 =?utf-8?B?QW9Cd3BxeVFLNDJYT3pzMDRRVzVjaEhxWk1JZzNoSkx0bmwwcHRjLzI4Rjcw?=
 =?utf-8?B?R2NmYm1MdWlVUklDZ3FFVW94MzFDUnovWk9PaGFhOUlUQmgxRVRTVUcwVlFy?=
 =?utf-8?B?bERGdkVNTUlkUVkxTUdoOEFYdEl4aUtUSTRHdFBSSk80MFI3NGVBajQwYWc0?=
 =?utf-8?B?d2c9PQ==?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 69454748-e253-4595-5765-08db44ca8f41
X-MS-Exchange-CrossTenant-AuthSource: DM6PR11MB3625.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Apr 2023 13:48:18.5578
 (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: bBEUQjZYgrSsCb4qLNjexKvAOM87Ta/ONZv5b2ppNQXN4EQ58SZeg4U13QyuF5BYlHthQFiBh/9nO2RdIb2vM1y/i8UBgoRucxenxkgvxQ8=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL1PR11MB5447
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-5.8 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,
        DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,
        RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,
        SPF_NONE,T_SCC_BODY_TEXT_LINE autolearn=ham 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: Gong, Ruiqi <gongruiqi1@huawei.com>
Date: Mon, 24 Apr 2023 10:54:33 +0800

> Sorry for the late reply. I just came back from my paternity leave :)
> 
> On 2023/04/05 23:15, Alexander Lobakin wrote:
>> From: Hyeonggon Yoo <42.hyeyoo@gmail.com>
>> Date: Wed, 5 Apr 2023 21:26:47 +0900
>>
>>> ...
>>>
>>> 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)
>>
>> ?
> 
> This makes the cache selection "dynamic", i.e. each kmalloc() will
> randomly pick a different cache at each time it's executed. The problem
> of this approach is that it only reduces the probability of the cache
> being sprayed by the attacker, and the attacker can bypass it by simply
> repeating the attack multiple times in a brute-force manner.
> 
> Our proposal is to make the randomness 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
> code path that the attacker uses would most likely pick a different
> cache than which the targeted subsystem/driver would pick, which means
> in most of cases the heap spraying is unachievable.

Ah, I see now. Thanks for the explanation, made it really clear.

> 
>> 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().
> 
> Yes, `_RET_IP_ % nr` is a bit naive. Currently the patch is more like a
> PoC so I wrote this. Indeed a proper hash function should be used here.
> 
> And yes _RET_IP_ could somehow be manually determined especially for
> kernels without KASLR, and I think adding a per-boot random seed into
> the selection could solve this.

I recall how it is done for kCFI/FineIBT in the x86 code -- it also uses
per-boot random seed (although it gets patched into the code itself each
time, when applying alternatives). So probably should be optimal enough.
The only thing I'm wondering is where to store this per-boot seed :D
It's generic code, so you can't patch it directly. OTOH storing it in
.data/.bss can make it vulnerable to attacks... Can't it?

> 
> I will implement these in v2. Thanks!
> 
>>
>> Thanks,
>> Olek
>>

Thanks,
Olek