GSoC 2018 report: Kernel Address Sanitizer, Part 2

Prepared by Siddharth Muralee (@Tr3x__) as a part of GSoC'18

I have been working on porting the Kernel Address Sanitizer(KASAN) for the NetBSD kernel. This summarizes the work done until the second evaluation.

Refer here for the link to the first report.

What is a Kernel Address Sanitizer?

The Kernel Address Sanitizer or KASAN is a fast and efficient memory error detector designed by developers at Google. It is heavily based on compiler optimization and has been very effective in reporting bugs in the Linux Kernel.

The aim of my project is to build the NetBSD kernel with the KASAN and use it to find bugs and improve code quality in the kernel. This Sanitizer will help detect a lot of memory errors that otherwise would be hard to detect.

Porting code from Linux to NetBSD

The design of KASAN in the NetBSD kernel is based on its Linux counterpart. Linux code is GPL licensed hence we intend to rewrite it completely or/and relicense certain code parts. We will be handling this once we have a working prototype ready.

This is in no way an easy task especially when the code we try to port is from multiple areas in the kernel like the Memory management system, Process Management etc.

The total port requires a transfer of around 3000 lines in around 6 files with references in around 20 other locations or more.

Design of KASAN and how it works

Kernel Address Sanitizer works by instrumenting all the memory accesses and having a separate "shadow buffer" to keep track of all the addresses that are legitimate and accessible and complains (Very Descriptively!!) when the kernel reads/writes elsewhere.

The basic idea behind Kernel ASan is to set aside a map/buffer where each byte in the kernel is represented by using a bit. This means the size of the buffer would be 1/8th of the total memory accessible by the kernel. In amd64(also x86_64) this would mean setting aside 16TB of memory to handle a total of 128TB of kernel memory.

Implementation Outline

A bulk of the work is done by the compiler inserted code itself(GCC as of now), but still there are a lot of features we have to implement.

• Checking and reporting Infrastructure
• Allocation and population of the Shadow buffer during boot
• Modification of Allocators to update the Shadow buffer upon allocations and deallocations

Kernel Address Sanitizer is useful in finding bugs/coding errors in the kernel such as :

• Use - after - free
• Stack, heap and global buffer overflows
• Double free
• Use - after - scope

The design makes it faster than other tools such as kmemcheck etc. The average slowdown is expected to be around ~2x times or less.

KASAN Initialisation

KASAN initialization happens in two stages -

• early in the boot stage, we set each page entry of the entire shadow region to zero_page (early_kasan_init)
• after the physical memory has been mapped and the pmap(9) has been bootstrapped during kernel startup, the zero_pages are unmapped and the real pages are allocated and mapped (kasan_init).

Below is a short description of what kasan_init() does in Linux code :

• It loads the kernel boot time page table and clears all the page table entries for the shadow buffer region which had been populated with zero_pages during early_kasan_init.
• It marks shadow buffer offsets of parts of kernel memory; which we don't want to track or are prohibited, by populating them using kasan_populate_zero_shadow which iterates through all the page tables.
• Write-protects the mappings and flushes the TLB.

Allocating the shadow buffer

Instead of iterating through the page table entries as Linux preferred to do, we decided to use our low-level kernel memory allocators to do the job for us. This helped in reducing the code complexity and allowed us to reduce the size of the code by a significant amount.

One may ask then does that allocator need to be sanitized? We propose to add a kasan_inited variable which would help the sanitization to occur after the initialization.

We are still in the process of testing this part.

Shadow translation (Address Sanitizer Algorithm)

The translation from a memory address to the corresponding shadow offset must be done pretty fast since it happens during every memory read/write. This is implemented similar to the below code

shadow_address = KmemToShadow(address);
void * KmemToShadow(void * addr) {
return (addr >> Shadow_scale) + Shadow_buffer_start;
}


The reverse shadow offsets to kernel memory addresses function is also similar to this.

The shadow translation functions have already been implemented and can be found in kasan.h in my Github repository.

Error Detection

Every read/write is instrumented to have a check which would decide if the memory access was legitimate or not. This would be done in the manner shown below.

shadow_address = KmemToShadow(address);
if (IsPoisoned(shadow_address)) {
ReportError(address, Size, IsWrite);
}

The actual implementation of the Error detection is a bit more complex since we have to include the mapping aspect as well.

Each byte of shadow buffer memory maps to a qword(8 bytes) of kernel memory. Because of which poisoned memory(*shadow_address) values have only 3 possibilities :

• The value can be 0 ( Meaning that all 8 bytes are unpoisoned )
• The value can be -ve ( Meaning that all 8 bytes are poisoned )
• The value can have first k bits unpoisoned and the rest (8 - k) poisoned

Therefore we can use the value also to help assist us while doing Error detection.

Basic Bug Report

The information about each bug is stored in struct kasan_access_info which is then used to determine the following information

• The kind of bug
• Whether read/write caused it
• Process ID of the task being executed
• The address which caused the error

We also print the stack backtrace which helps in identifying the function with the bug and also helps in finding the execution flow which caused the bug.

One of the best features is that we will be able to use the address where the error occurred to show the poisoning in the shadow buffer. This diagram will be pretty useful for developers trying to fix the bugs found by KASAN.

Unfortunately, since we haven't finished modifying the allocators to update the shadow buffer on read/write we will not be able to test this as of now.

Summary

I have managed to get a good initial grasp of the internals of NetBSD kernel over the last two months.

I would like to thank my mentor Kamil for his constant support and valuable suggestions. A huge thanks to the NetBSD community who have been supportive throughout.

Most of my work is done on my fork of NetBSD.

Work left to be done

There is a lot of important features that still remains to be implemented. Below is the list of features that I will be working on.

• Solve licensing issues
• sysctl switches to tune options of kern_asan.c (quarantine size, halt_on_error etc)
• Move the KASAN code to src/sys/kernel and the MI part call kern_asan.c (similar to kern_ubsan.c)
• Ability to run concurrently KUBSAN & KASAN
• Refactor kasan_depth and in_ubsan to be shared between sanitizers: probably as a bit in private LWP bitfield
• ATF tests verifying KASAN's detection of bugs
• The first boot to a functional shell of a kernel executing with KASAN
• Finish execution of ATF tests with a kernel running with KASAN
• Quarantine List
• Report generation
• Continue execution
• Allocator hooks and functions
• Memory hotplug
• Kernel module shadowing
• Quarantine for reusable structs like LWP