Message-ID: <sjownmnyf4ygi5rtbedan6oauzvyk2d7xcummo5rykiryrpcrt@kasomz5imkkm>
Date: Thu, 13 Feb 2025 17:20:22 +0100
From: Maciej Wieczor-Retman <maciej.wieczor-retman@...el.com>
To: Andrey Konovalov <andreyknvl@...il.com>
CC: Samuel Holland <samuel.holland@...ive.com>, Palmer Dabbelt
	<palmer@...belt.com>, <linux-riscv@...ts.infradead.org>, Andrey Ryabinin
	<ryabinin.a.a@...il.com>, Alexander Potapenko <glider@...gle.com>, "Dmitry
 Vyukov" <dvyukov@...gle.com>, Vincenzo Frascino <vincenzo.frascino@....com>,
	<kasan-dev@...glegroups.com>, <llvm@...ts.linux.dev>, Catalin Marinas
	<catalin.marinas@....com>, <linux-kernel@...r.kernel.org>,
	<linux-mm@...ck.org>, Alexandre Ghiti <alexghiti@...osinc.com>, Will Deacon
	<will@...nel.org>, Evgenii Stepanov <eugenis@...gle.com>, Andrew Morton
	<akpm@...ux-foundation.org>, <linux-arm-kernel@...ts.infradead.org>
Subject: Re: [PATCH v2 1/9] kasan: sw_tags: Use arithmetic shift for shadow
 computation

On 2025-02-13 at 02:28:08 +0100, Andrey Konovalov wrote:
>On Thu, Feb 13, 2025 at 2:21 AM Andrey Konovalov <andreyknvl@...il.com> wrote:
>>
>> On Tue, Feb 11, 2025 at 7:07 PM Maciej Wieczor-Retman
>> <maciej.wieczor-retman@...el.com> wrote:
>> >
>> > I did some experiments with multiple addresses passed through
>> > kasan_mem_to_shadow(). And it seems like we can get almost any address out when
>> > we consider any random bogus pointers.
>> >
>> > I used the KASAN_SHADOW_OFFSET from your example above. Userspace addresses seem
>> > to map to the range [KASAN_SHADOW_OFFSET - 0xffff8fffffffffff]. Then going
>> > through non-canonical addresses until 0x0007ffffffffffff we reach the end of
>> > kernel LA and we loop around. Then the addresses seem to go from 0 until we
>> > again start reaching the kernel space and then it maps into the proper shadow
>> > memory.
>> >
>> > It gave me the same results when using the previous version of
>> > kasan_mem_to_shadow() so I'm wondering whether I'm doing this experiment
>> > incorrectly or if there aren't any addresses we can rule out here?
>>
>> By the definition of the shadow mapping, if we apply that mapping to
>> the whole 64-bit address space, the result will only contain 1/8th
>> (1/16th for SW/HW_TAGS) of that space.
>>
>> For example, with the current upstream value of KASAN_SHADOW_OFFSET on
>> x86 and arm64, the value of the top 3 bits (4 for SW/HW_TAGS) of any
>> shadow address are always the same: KASAN_SHADOW_OFFSET's value is
>> such that the shadow address calculation never overflows. Addresses
>> that have a different value for those top 3 bits are the once we can
>> rule out.
>
>Eh, scratch that, the 3rd bit from the top changes, as
>KASAN_SHADOW_OFFSET is not a that-well-aligned value, the overall size
>of the mapping holds.
>
>> The KASAN_SHADOW_OFFSET value from my example does rely on the
>> overflow (arguably, this makes things more confusing [1]). But still,
>> the possible values of shadow addresses should only cover 1/16th of
>> the address space.
>>
>> So whether the address belongs to that 1/8th (1/16th) of the address
>> space is what we want to check in kasan_non_canonical_hook().
>>

Right, I somehow forgot that obviously the whole LA has to map to 1/16th of the
address space and it shold stay contiguous.

After rethinking how the mapping worked before and will work after making stuff
signed I thought this patch could make use of the overflow?

>From what I noticed, all the Kconfig values for KASAN_SHADOW_OFFSET should make
it so there will be overflow when inputing more and more positive addresses.

So maybe we should first find what the most negative and most positive (signed)
addresses map to in shadow memory address space. And then when looking for
invalid values that aren't the product of kasan_mem_to_shadow() we should check

	if (addr > kasan_mem_to_shadow(biggest_positive_address) &&
	    addr < kasan_mem_to_shadow(smallest_negative_address))
		return;

Is this correct?

I think this works with TBI because valid kernel addresses depending on the top
bit value will go both up and down from the KASAN_SHADOW_OFFSET. And the same
will work for x86 where the (negative) kernel addresses are mapped down of
KASAN_SHADOW_OFFSET and positive user addresses are mapped above and also
overflow (in tag-based mode).

>> The current upstream version of kasan_non_canonical_hook() actually
>> does a simplified check by only checking for the lower bound (e.g. for
>> x86, there's also an upper bound: KASAN_SHADOW_OFFSET +
>> (0xffffffffffffffff >> 3) == 0xfffffbffffffffff), so we could improve
>> it.

Right, Samuel's check for generic KASAN seems to cover that case.

>>
>> [1] https://bugzilla.kernel.org/show_bug.cgi?id=218043
>
>_______________________________________________
>linux-riscv mailing list
>linux-riscv@...ts.infradead.org
>http://lists.infradead.org/mailman/listinfo/linux-riscv

-- 
Kind regards
Maciej Wieczór-Retman

Powered by blists - more mailing lists