Micro-KASAN : KASAN memory management. ·

uKASAN - This article is part of a series.

Part 5: This Article

Part 6: Micro-KASAN : ARM Thumb Emulator.

Introduction
#

Now that we have a better idea of how the kernel manages memory from a high level point of view, let’s elaborate on how the KASAN will fit in this system.

Metadata
#

The KASAN will have to track the status of each byte of memory in the system.

For this, it will need metadata, that it will store in dedicated memory : each byte of memory managed by the memory system will have attributes, that will describe the status of this byte, or more precisely :

if the byte is accessible (as defined in the region manager section) ?
who can access the byte, either user, allocator or both ?
is the byte writable ?
is the byte initialized ?

This can be achieved by storing 4 bits of attributes per byte of memory.

Attributes location
#

Attributes must be located somewhere in memory. To place them, we will use the same strategy as the Regions allocator.

When registering a memory regions in the region manager, before the region manager allocates all its metadata, the KASAN will split the region in two parts :

kernel-accessible memory : this part will be forwarded to the region manager, that will in turn divide it in two subregions as described in the previous part : pages, and pages metadata.
KASAN attributes : this part will contain 4 bits of attributes for each byte of memory in the kernel-accessible part.

Attributes lifecycle
#

Attributes are the base information that the KASAN will use to verify a memory access. A memory access of N bytes starting at A will cause the KASAN to fetch attributes for the address range [A, A + N[, and verify that they allow the access to occur. If so, the KASAN will let the access happen. Otherwise, it will trigger an error.

In this context, let the access happen means emulate the access, as described in part 3.

Here are some accesses that should cause an error to occur :

reading from an uninitialized byte.
writing to a non-writable byte.
user accessing a byte not accessible to the user.
allocator accessing a byte not accessible to the allocator.
access to a non accessible byte.

The following diagram describes the lifecycle of attributes, and the various events (accesses) that can occur, as well as the errors generated by the KASAN checker if any.

TODO one does not simply find the time to draw diagrams…

CPU state
#

To make our attributes model work, we need an additional per-cpu variable that will report whether the said CPU is running allocator code or user code.

This will be used as a base to verify the accesses :

a CPU running in user mode accessing a memory block accessible to allocator only will trigger a KASAN error (use after free)
a CPU running in allocator mode accessing a memory block accessible to user only will trigger a KASAN error (use after alloc)

Tuning the allocators
#

The access checking relies on the accuracy of the KASAN attributes.

Those attributes are not only modified by a direct access like the ‘initialized’ field.

In particular, any allocation or free in both the region manager or secondary allocators must be reflected in attributes.

This requires the said memory managers to be modified, so that :

when the region manager allocates pages, all the related bytes go from not accessible to accessible to allocator only.
when the region manager frees pages, all the related bytes go from accessible to allocator only to not accessible.
when secondary allocators allocate memory to the user, all the related bytes go from accessible to allocator only to accessible to user only.
when secondary allocators free memory, all the related bytes go from accessible to user only to accessible to allocator only.

When one of those transitions occurs, the KASAN must verify that the related bytes have the expected start state.

As mentioned earlier, the allocators must also be updated to report their entry / exit in the cpu state.

Corner cases
#

The rules stated in the two previous sections are true in the general case. The FSM described is a high level representation of the reality, but there are some corner cases that make the actual implementation look less like an actual FSM.

Allocators data
#

The main corner case is that allocators themselves (the actual allocator structs), so as CPU states, and some other main kernel components must be accessible both in allocator and user state.

That causes us to need a specific attribute state accessible to anyone and dedicated KASAN entrypoints to report that a specified memory block falls into this category.

Global variables
#

Another corner case that we have to handle is the state of global variables.

As much as we would like to avoid them, global variables are a necessary evil. Take the memory system data structure for example : it must be initialized during the early stages of boot, when we have not yet registered any memory region, thus, when dynamic allocation is not available. In any case, memory allocation goes through it, so we literally can’t have it dynamically allocated.

There are a few cases like this one, where we theoretically could avoid using globals, but where there is no real benefit of doing so.

Our kernel executable will have the two regular .data and .bss sections in which globals / static variables are located.

Those variables are initialized as part of the very early bootstrap sequence, by copying the content of the initializer of .data (likely located in flash) directly in .data, and by zeroing-out the content of .bss.

Those sections must be considered initialized by the KASAN, as they indeed are initialized during very early boot.

Though, those sections are located in RAM, and will ultimately be included in a particular memory region.

This will add two tasks to the memory management system when registering a memory region :

the region manager will have to tag all pages in these sections as not allocatable, as those pages are implicitly allocated to the kernel.
the KASAN will have to report any byte in such a section as accessible by anyone, and initialized, as opposed to other bytes whose initial state is accessible by no one.

Attributes management
#

I will not provide a detailed explanation on how to actually handle attributes, as it is very implementation-specific, complex, and I have little time.

Rather, here is a link to my public code repo. Files ksn.h and ksn.c contain the platform-independent KASAN code of my kernel, whose main job is to manage attributes.