LWN: Comments on "Software-tag-based KASAN"

Software-tag-based KASAN

mcortese — Tue, 23 Oct 2018 20:17:38 +0000

Right. However you shouldn't worry about two unrelated pointers sharing the same tag. You should wonder what's the probability of one pointer gone rogue pointing out of its original bounds into the range of another pointer, and *those* two pointers sharing the same tag.

Software-tag-based KASAN

Wol — Thu, 04 Oct 2018 22:22:29 +0000

> I'm pretty certain that the kernel can have more then 256 live allocations at any given time, hence, tag collisions are guaranteed to happen even when regarding "about 4 collisions in 1000 allocations" as "small probability" (doesn't seem small to me).

If you've only got 256 possible tag values, then I would think that the probability of a collision is more than 50% with just 25 live allocations. Think birthday paradox.

You only need 30 people, chosen at random, for the chances of two of them sharing a birthday to go over 50%. That's 30 people, 365 days, and a collision. Extrapolating (yes I know that's very dangerous with statistics), I would guess that once a hash table is over 10% full, the chances of a collision go over 50%.

Cheers,
Wol

Software-tag-based KASAN

mtaht — Tue, 02 Oct 2018 11:07:21 +0000

One of the stumbling blocks on the Mill cpu's compiler (which has tagged pointers also), was that llvm considered long ints and pointers to be equivalent in various stages of the optimizer. Is this fixed now in llvm 7?

Software-tag-based KASAN

cmarinas — Mon, 01 Oct 2018 13:00:38 +0000

That's x86, on arm64 we can still build the kernel without asm goto (albeit a small performance degradation).

Software-tag-based KASAN

rweikusat2 — Sun, 30 Sep 2018 15:42:46 +0000

I'm pretty certain that the kernel can have more then 256 live allocations at any given time, hence, tag collisions are guaranteed to happen even when regarding "about 4 collisions in 1000 allocations" as "small probability" (doesn't seem small to me). And there's of course Knuth's classic statement that a arbitrarily long sequence of twos is a perfectly random sequence. This means if this mechanism considers an access valid, there's absolutely no way to determine that it's actually valid short of examining the code for correct pointer usages. And if this was such an easy thing to do, surely, there shouldn't be any incorrect pointer uses.

Software-tag-based KASAN

NHO — Thu, 27 Sep 2018 17:26:47 +0000

I thought ASM goto caused kernel to stop building with Clang. It's restored with Clang 7?

Software-tag-based KASAN

stonedown — Thu, 27 Sep 2018 17:16:33 +0000

I really appreciate articles like this, which are helpful for those of us debugging embedded systems.

Software-tag-based KASAN

Cyberax — Thu, 27 Sep 2018 00:01:08 +0000

> rather larger than is actually needed on current systems, even if a web browser is running.
LOL