Losing the magic [LWN.net]

Losing the magic

Posted Dec 13, 2022 12:11 UTC (Tue) by mathstuf (subscriber, #69389)
In reply to: Losing the magic by tytso
Parent article: Losing the magic

I run my userspace under `MALLOC_CHECK_=3` and `MALLOC_PERTURB_=…` (updated occasionally by a user timer unit) to catch things like this. Is some kind of "memset-on-kfree" mechanism not suitable for debugging the entire kernel for use-after-free while also being far less heavy than KMSAN?

I ask because some day, a very smart compiler might see that dead write of `fs->magic = 0;` given the immediate free afterwards and optimize it out as UB to observe. Additionally, while it's also against UAF in ext2 code, non-ext2 code that gets its hands on the pointer that somehow that doesn't have the magic-checking logic is just as dead too (I have no gauge on how "likely" this is in the design's use of pointers).

to post comments

Losing the magic

Posted Dec 13, 2022 13:08 UTC (Tue) by excors (subscriber, #95769) [Link] (8 responses)

> I ask because some day, a very smart compiler might see that dead write of `fs->magic = 0;` given the immediate free afterwards and optimize it out as UB to observe.

That day was at least 8 years ago. GCC 4.9 with -O1 will optimise away the writes, defeating this attempt at memory protection, because ext2fs_free_mem is an inline function so the compiler knows the object is passed to free() and can no longer be observed. See e.g. https://godbolt.org/z/nWYEa34a6

I guess the cheapest way to prevent that is to insert a compiler barrier (`asm volatile ("" ::: "memory")`) just after writing to fs->magic, to prevent the compiler making assumptions about observability of memory.

Losing the magic

Posted Dec 13, 2022 14:47 UTC (Tue) by adobriyan (guest, #30858) [Link] (7 responses)

This is the usecase for "volatile": *(volatile int *)&fs->magic = 0;

Losing the magic

Posted Dec 14, 2022 2:46 UTC (Wed) by nybble41 (subscriber, #55106) [Link] (6 responses)

Even then, couldn't the compiler just set it back after the volatile write, but before the memory is freed? Seeing as how it's unobservable and all. Perhaps it decides to use that "dead" memory as scratch space for some other operation.

Losing the magic

Posted Dec 14, 2022 16:47 UTC (Wed) by adobriyan (guest, #30858) [Link] (4 responses)

I don't think so. "volatile" means "load/store instruction must be somewhere in the instruction stream" which is what needed.

Losing the magic

Posted Dec 14, 2022 17:10 UTC (Wed) by mathstuf (subscriber, #69389) [Link] (3 responses)

It means that the value being represented is not trackable in the C abstract machine and therefore no assumptions can be made about it. Because no assumptions can be made, optimizers are hard-pressed to do much of anything about it because the "as-if" rule is likely impossible to track accurately.

However, given that this is trivially detectable as about-to-be-freed memory, I don't know what kind of rules exist around "volatile values living in C-maintained memory" might allow even this to still be seen as a dead store and unobservable via UAF == UB.

Losing the magic

Posted Dec 14, 2022 19:31 UTC (Wed) by farnz (subscriber, #17727) [Link] (2 responses)

If I'm reading the standard correctly, the compiler has to output the stores, because it is possible that the program has shared that memory with an external entity using mechanisms outside the scope of the standard. What the implementation does after the memory is freed is not specified (although the implementation is allowed to assume that the memory is no longer shared with an external entity at this point), and in theory a sufficiently malicious implementation could undo those final stores after you called free, but before the memory is reused.

In practice, I don't think this is a significant concern for tricks intended to help with debugging. It is for security-oriented code, but that's not the case here.

Losing the magic

Posted Dec 14, 2022 23:25 UTC (Wed) by mathstuf (subscriber, #69389) [Link] (1 responses)

Can the C abstract machine really say that memory it obtains through `malloc` has some other magical property? Wouldn't that require you to get "lucky" with what `malloc` gives you in the first place to have that address space "mean something" to some other part of the system?

Maybe the kernel gets away with it by "hiding" behind non-standard allocation APIs…

Losing the magic

Posted Dec 15, 2022 10:47 UTC (Thu) by farnz (subscriber, #17727) [Link]

It's more that you can have an external observer outside the abstract machine, but able to understand abstract machine pointers; I can, in theory, store a pointer from malloc in a way that allows the external observer to reach into the abstract machine and read the malloc'd block. I can also have the external observer be looking not at the addresses, but at the pattern of data written into the block (just as in hardware, it's not unknown to have chips only connected to the address bus, and to rely on the pattern of address accesses to determine what to do).

The compiler is not allowed to make assumptions about what the external environment can, or cannot, see, and thus has to assume that any write to a volatile is visible in an interesting fashion.

Losing the magic

Posted Dec 14, 2022 18:33 UTC (Wed) by excors (subscriber, #95769) [Link]

> Even then, couldn't the compiler just set it back after the volatile write, but before the memory is freed? Seeing as how it's unobservable and all. Perhaps it decides to use that "dead" memory as scratch space for some other operation.

It probably could, but I don't think it's particularly fruitful to consider what the compiler 'could' do, because the goal of the magic numbers here is to detect use-after-free bugs, i.e. we're interested in the practical behaviour of a situation that the standard says is undefined behaviour. We're outside the scope of the standard, so all we can do is look at what GCC/Clang actually will do.

If there is no barrier or volatile, and some optimisations are turned on, they demonstrably will delete the write-before-free. With barrier or volatile, it appears (in my basic testing) they don't delete it, so the code will behave as intended - that doesn't prove they'll never delete it, but I can't immediately find any examples where that trick fails, and intuitively I think it'd be very surprising if it didn't work, so I'd be happy to make that assumption until shown a counterexample.

(The same issue comes up when trying to zero a sensitive buffer before releasing it, to reduce the risk of leaking its data when some other code has a memory-safety bug - you need to be very careful that the compiler doesn't remove all the zeroing code, and you can't look to the C standard for an answer.)