Finer grained kernel randomization
This project seeks to improve the security of the current Linux kernel address space randomization algorithm (kaslr) by adding an additional level of randomization: function reordering
To see details of our work in progress, please check out out our github project page
Code diversity makes it harder for attackers to find the address of useful routines for their exploits. There has been a lot of academic research over the years on how to add code diversity, but in practice only one method has been widely deployed: base address randomization. This technique has been adopted in both user space and for the kernel, but this project is exclusively focused on improving the kernel aslr algorithm. The techniques used in this project were inspired by the selfrando project. As with the selfrando project, our design objective was to create a practical, deployable method to improve the defenses of the kernel against memory-corruption vulnerabilities.
The kernel text segment is located within a fixed range that is larger than the actual size of the segment. The existing kaslr algorithm chooses a random starting address within this range at boot time that is large enough to hold the segment. The order of code within the segment is unchanged, only the base address is shifted. There are a few shortcomings with this algorithm:
- There are only so many locations that the kernel can fit in. This means that the entropy of this algorithm is fairly low, making it easier to brute force detect the location of the base address.
- Because the order of the rest of the text is unchanged, knowledge of a single address in the kernel can reveal the exact location of every byte of kernel code.
- Infoleaks are common and can make it simple to determine the aslr offset.
gcc has an option to place functions into individual .text sections (-ffunction-sections).
Normally the linker would combine all these .text input sections into a single final output .text segment. If we have access to the information contained in the .text input sections and the relocation information for each of these sections, we can use this information to rearrange the .text segment at load time, thus reordering the functions in memory. There are two very similar ways to do this for the kernel. The first applies to kernel modules, and the second to the kernel text.
Modules are relocatable object files with some extra information in them. This means that each kernel module contains section headers and relocation information in the object so that the kernel module loader can link the module into the kernel at runtime (module load time). If we use the -ffunction-sections flag to build our kernel module, we can modify the module loader to shuffle the .text sections that it finds as part of the current module load process. The code to accomplish this is very straight forward. A work in progress PoC can be found by checking out the reorder-module-functions branch of this linux tree. A talk describing this was presented at the Linux Plumbers Conference in the fall of 2018.
The kernel is an executable, not a relocatable object - but it already supports relocation, and the much of the information needed to apply the same function reordering technique to the rest of the kernel already exists thanks to the current kaslr algorithm. When you apply the gcc function section flag to a portion of the kernel, the kernel build system retains the section header information for the individual function text sections in the final compressed binary. That boundary information can be used during the kernel loading phase to shuffle parts of the text segment in memory. We can leave part of the text segment alone if there are any concerns about randomization.
The relocation information is currently partially available. The existing kaslr algorithm needs to rewrite some of the relocations in the kernel because the kernel has been shifted from the load address that was specified in the linker script. The compressed kernel contains a table of addresses to relocations that need to be adjusted.
Unfortunately, for the purpose of function reordering this list is incomplete as it does not include relative relocations, as that is not needed for the existing algorithm. These needed relocations have been added to support kernel function reordering, along with changing the existing algorithm for updating the relocations to comprehend our shuffled sections.
A talk describing this technique was presented at the 2019 Intel Open Source Technology Summit (slides/video to be posted when available). A PoC for the kernel which also contains the module reordering functionality is available here.
To enable fine grained kaslr in the prototype code, you need to have the following config options set (including all the ones you would use to build normal kaslr)
CONFIG_FG_KASLR=y
There are two areas where function reordering can impact performance: boot time latency, and run time performance.
This implementation of finer grained KASLR impacts the boot time of the kernel in several places. It requires additional parsing of the kernel ELF file to obtain the section headers of the sections to be randomized. It calls the random number generator for each section to be randomized to determine that section's new memory location. It copies the decompressed kernel into a new area of memory to avoid corruption when laying out the newly randomized sections. It increases the number of relocations the kernel has to perform at boot time vs. standard KASLR, and it also requires a lookup on each address that needs to be relocated to see if it was in a randomized section and needs to be adjusted by a new offset.
Booting a test VM on a modern, well appointed system showed an increase in latency of approximately 1 second.
The performance impact at run-time of function reordering varies by workload. Using kcbench, a kernel compilation benchmark, the performance of a kernel build with finer grained KASLR was about 1% slower than a kernel with standard KASLR. Analysis with perf showed slightly higher L1-icache-load-misses vs. L1-icache-loads. Other workloads were examined as well, with varied results. Some workloads performed significantly worse under FGKASLR, while others stayed the same or were mysteriously better. In general, it will depend on the code flow whether or not finer grained KASLR will impact your workload, and how the underlying code was designed. Future work could identify hot areas that may not be randomized and either leave them in the .text section or group them together into a single section that may be randomized.
Adding additional section headers as a result of compiling with -ffunction-sections will increase the size of the vmlinux ELF file. In addition, the vmlinux.bin file generated in arch/x86/boot/compressed by objcopy grows significantly with the current POC implementation. This is because the boot heap size must be dramatically increased to support shuffling the sections and re-sorting kallsyms. With a sample kernel compilation using a stock Fedora config, bzImage grew about 7.5X when CONFIG_FG_KASLR was enabled.
As one can imagine, rearranging the kernel code at load time might break a existing tools which rely on the information in the on-disk kernel binary or build time symbol locations rather than load time symbol locations. Many tools however are easily adjusted as they contain tables that generate relocation sections that allow us to update the addresses after we shuffle our sections. As the PoC matures, the list of affected tools might get larger. Currently only gdb is known to be impacted.
If you would like to learn more about code diversification, here is a very small set of interesting and relevant papers for your reading pleasure.