Paper | HotBPF: Kill Exploitable Design Pattern

1. Basic Information

This paper is the last chapter of Dr. Yueqi’s dissertation titled Investigating Exploitable Design Patterns for More Advanced Protection Design. The paper has never been published elsewhere, while there was a keynote on HotBPF given by Yueqi and Zhenpeng on Linux Security Summit Europe 2022.

Dr. Yueqi’s dissertation is composed of five chapters: FUZE, ELOISE (reading note), SLAKE (reading note), KEPLER and HotBPF, which aims to study exploitable design patterns in a systematic approach, including investigating exploitable design patterns and constructing advanced protection design.

The HotBPF implementation has been open-sourced on GitHub, while another researcher and I haven’t succeeded in reproduce it yet because of some version issues. As this technique is very instructive, I will try to reproduce it. If I make it, I will update this post by adding a new reproduction section. Currently, this post just serves as a reading note to summarize the original paper.

UPDATE 2023-04-26: @sun-ruijiang finds it hard to do the reproduction (issue #3).

2. Introduction

The idea of HotBPF is to isolate corruption to protect the Linux kernel from attacks that start from memory corruption and take advantage of a variety of exploitable design patterns, which have been discussed in SLAKE and ELOISE papers.

Before HotBPF, researchers have designed some isolation-based defenses, such as xMP and AutoSlab. However, the existing defenses have some limitations:

1. They provide proactive protection after the sensitive objects have been corrupted in the wild.
2. Recompilation and Rebooting are needed to enable these protections.
3. Most of them cannot prevent cross-cache exploitation.
4. They either introduce non-negligible overhead or rely on special hardware features or hypervisor.

Unlike the existing mechanisms, HotBPF aims to isolate the memory corruption, instead of the sensitive data or object, which is composed of two components:

1. The first component takes a vulnerability report as input and conducts static analysis to identify the vulnerable object where memory corruption happens. After that, it calculates all kernel sites where the vulnerable object is allocated and feeds these sites to the second component.
2. The second component leverages eBPF to intercept all allocation sites of interest on-the-fly and divert the allocation of vulnerable object to vmalloc region.

As the authors say, HotBPF has four advantages:

1. It provides protection immediately after a severe vulnerability is reported.
2. The protection can be enabled on-the-fly without recompilation or rebooting.
3. It can also prevent cross-cache exploitation.
4. The defense is independent of hardware features and hypervisor.

According to this paper, the overhead introduced by HotBPF is about 2% to 3%.

3. Background

Two elements of heap-based exploitation are overlapping and sensitive data. The attackers need to overlap the corruption caused by the vulnerability to overwrite or overread sensitive data. In UAF and DF, the corruption range is the freed object referenced by the dangling pointer. In heap-based OOB write/read, the corruption range is where overflow happens.

The best way to deal with the spatial overlap is strict isolation; the best way to deal with the temporal overlap is one-time allocation (OTA), which never reclaims freed memory.

Few existing defense mechanisms puts efforts on spatially isolating corruption, due to three challenges:

1. The corruption source varies vulnerability by vulnerability, making it hard to automatize the process of identifying corruption source.
2. The corruption can happen to any kernel variables, so the isolation needs to be enforced dynamically.
3. It is hard to reduce the impact and overhead of the on-the-fly isolation.

There is no OTA solution for OS kernel as well, which might exhaust memory.

4. Design Overview

As the diagram below shows, the first component is the agent in the userspace, which takes a vulnerability report generated by Syzkaller or syzbot as input. By analyzing the report and kernel source code, the agent identifies the type of vulnerable object (e.g., struct napi_struct). Then the agent pinpoint the allocation sites of vulnerable objects, calculate the binary address of these sites in the kernel image, and pass these addresses to the second component of HotBPF, the eBPF program, within the kernel space through BPF maps.

The eBPF program will intercept these allocation sites in the running kernel image. When allocation happens, the eBPF program will divert the allocation to the vmalloc region, so as to separate the vulnerable object from other kernel objects, making it much harder or even impossible for the attacker to manipulate the heap layout.

There is a special case when the vulnerable object and the spray object are in the same type. To prevent attackers from spraying in this case, HotBPF implements one-time allocation (OTA) using BPF maps. Once a vulnerable object is freed, the relative memory region will not be reclaimed for future allocation, which would defeat the overlapping.

Up to now, for the OTA solution, I have two questions:

1. How can HotBPF know whether the vulnerable object is in the same type as the spray object? One potential way is to leverage the results from the ELOISE and SLAKE papers.
2. How can HotBPF avoid the memory exhaustion, if it doesn’t release the memory for the freed object?

5. Technical Details

HotBPF is implemented based on LLVM and eBPF.

5.1 Vulnerable Object Identification

Based on LLVM, HotBPF utilizes backward taint analysis to identify vulnerable structures, which is composed of three stages:

1. Report Analysis & Taint Source Identification

From the vulnerability report, we can get the debug information, which are generated by kernel debug checking. For explicit checking, HotBPF traces from the condition that triggers the execution of the logging statement and extracts the corresponding variable in the condition as the taint source. For implicit checking, HotBPF pinpoints the specific instruction that captures the kernel error and treats the memory access associated with the error-catching instruction as the taint source.

2. Taint Propagation & Sink Identification

After identifying the taint source, HotBPF extracts the call trace from the bug report, constructs the CFG and propagates taint source backward on CFG. Aliases of the tainted variable are also covered. The backward taint process will be terminated until one of the conditions holds:

1. The backward propagation reaches out to the definition of a tainted variable.
2. The backward propagation reaches out to a system call’s entry, an interrupt handler or the entry of the function that starts the scheduler of work queue.

3. Allocation Sites Pinpointing

After identifying the candidate vulnerable objects, this paper performs a use-def analysis to pinpoint the allocation sites, which is similar to that used in the ELOISE and SLAKE papers.

5.2 eBPF-based Isolation

Researchers extend eBPF mechanism to enforce the isolation of vulnerable object identified in the foregoing stages.

As the figure below shows, the eBPF program includes three parts: a kmalloc handler, a kfree handler and a BPF map structure. When the eBPF program is installed, the call instruction of the identified allocation and free sites will be overwritten with int 3, which will trap the kernel into interrupt handlers where kmalloc and kfree handlers are registered.

If the vulnerable object is to be allocated, kmalloc handler will be triggered, which firstly gets the execution context and then invokes the eBPF helper function bpf_vmalloc implemented by the authors in bpf_trace.c to allocate and return (by invoking the bpf_override_return helper) the demanded memory in vmalloc region. The memory address will be recorded in the BPF maps as well.

The situation of kfree is similar. When kfree handler is triggered, it queries the BPF map to determine whether the freed address is associated with a vulnerable object in the vmalloc region. If so, it will directly return without releasing the memory. If not, it will call the kfree function to do the normal work.

6. Evaluation & Discussion

The authors select kernel bugs from Syzkaller reports as test cases. As the diagram below shows, for all the 30 cases, HotBPF has no FN, while some FPs for 24 out of 30, on the effectiveness of static analysis.

The performance overhead is shown as below (tested with LMbench):

According to the authors, HotBPF doesn’t work for DMA-based objects, which require physically continuous memory.

7. Summary

This paper proposes a new on-the-fly defense mechanism against Linux kernel exploitation.

To be honest, I am not sure whether HotBPF can work in real-world industrial environment, as it requires that each kernel to be protected must be generated from source code, and IR must be generated along the compilation process. Actually, many companies would like to directly use official Linux distributions like Ubuntu and CentOS, without modifying and recompiling the kernel, even if they can download the target source code.

BTW, the paper doesn’t answer the second question I present before: how can HotBPF avoid the memory exhaustion, if it doesn’t release the memory for the freed object? Or, can the attacker utilizes HotBPF to conduct memory exhaustion attack?

But, anyway, HotBPF is an instructive idea for kernel hardening.