[RFC] adding KASAN support to JIT compiler(s)

["Alexis Lothoré" <alexis.lothore@bootlin.com>]

Hi everyone,

I am starting to work on adding KASAN support for loaded programs in the
kernel (in the context of the sponsorship granted to the eBPF Foundation
by the Alpha-Omega project, see [0]). I have done a bit of
research/experiments, but before actually writing and sending things
upstream, I'm sharing here what I understood on the requirement overall,
and how I am currently considering to implement it. Please feel free to
correct or enrich any part below!

# Brief

Once a program has passed the verifier (and have been JIted into native
code), we have strong guarantees that its _behavior_ will not trigger
bugs like infinite loops, invalid access on input context, NULL pointer
dereference, and so on. However, eBPF programs can still generate
invalid memory accesses in some scenarios:
- programs validated behavior relies on the hypothesis
that the tools (helpers, kfuncs) and data (eg kernel data) provided to
eBPF programs are sane: eg if a pointer returned by the kernel to a
program is somehow bogus (used after free, triggering out of bounds
accesses, etc), a bpf program that has been validated by the verifier
will happily use this pointer.
- there could be a bug in the verifier and/or the JIT compiler, letting
  invalid accesses slip through

To help detect those issues, Address Sanitizing can be implemented for
loaded programs.

Similarly to the KASAN tooling implemented for kernel code ([1]), the
goal will be to instrument any load/store performed by loaded eBPF
programs.  This means detecting those load/store in eBPF bytecode (when
being processed by the JIT compiler), and insert calls to the
corresponding __asan_loadX/__asan_storeX before those accesses,
similarly to what compilers do for KASAN. The major difference here is
that this instrumentation will not be inserted at program build time: it
will be inserted dynamically by the JIT compiler, while it is turning
the eBPF bytecode into native machine code (and so, this work will focus
on jit-enabled systems). I am considering this general process:

# Basic instrumentation

- start in do_jit(), in arch/<$ARCH>/net/bpf_jit_comp.c
  - note from Alexei: let's focus on x86 instead of all architectures.
- in the main loop going over all instructions, for all load/store
  instructions
  - note from Alexei: let's focus on LDX/STX for now instead of _any_
    load/store instruction to keep JIT complexity reasonable
- identify the size (b, h, w, dw) and type (read/write) of the access.
  Depending on those two, define the __asan_XXX function to call (those
  functions are defined in mm/kasan/generic.c, and are basically
  wrappers around check_region_inline)
  - I did some tests, emitting explicit calls to the __asan_load/store
    checkers implemented in the kernel directly into the jitted code,
    and it seems to be fine to call those from bpf execution context
- similarly to what ASAN is doing ([2]), possibly implement a fast path/slow
  path, mechanism:
  - fast path: emit instructions to first check the whole corresponding
    shadow byte, it it's 0, access is legitimate, jump back to the
    actual memory access
  - slow path: if the shadow byte is not 0, emit a call to the relevant
    __asan_load/storeXXX to validate or report the access. 

# Memory tracking

For this instrumentation to behave correctly, the monitored memory must
be tracked accordingly. The method used by KASAN is to allocate some
"shadow memory", which allows monitoring 8 bytes of memory with 1 byte
of shadow memory. Legit memory must have its corresponding shadow area
"unpoisoned", and must be poisoned/quarantined again once accesses are not
legitimate anymore. There are different memory types, with some of them
already covered/monitored:
- data passed to programs: KASAN on kernel side is already taking care
  of {un}poisoning this memory, so we can check directly the
  corresponding shadow memory.
- bpf global variables: global variables in bpf programs are turned into
  maps. Those maps, when created by the kernel, are then already
  monitored (ie: poisoned/unpoisoned) when the corresponding memory is
  allocated/deallocated. I did not check all maps, but looking at a few
  of those, they are vmalloc'ed, so the proper monitoring will depend
  directly on CONFIG_KASAN_VMALLOC
- bpf stack: when a program allocate some memory on its own stack, it is
  not tracked by KASAN. To be able to track stack memory misusage, JIT
  compiler must insert some red zones around the variables on the stack.
  This point looks more complex than the previous ones, as we need to:
  - identify variables that live on bpf program stack instead of
    registers
  - insert asan left/right red zones, and possibly inter-variables red zones
  - and so account for this "stack overhead", eg in the verifier
  I then propose to put this "stack monitoring" as a next step, to be
  implemented once we have a basic kasan monitoring integrated in x86
  JIT compiler.

# Integration

- KASAN monitoring for eBPF programs can be set under a new
  CONFIG_KASAN_EBPF kconfig
  - will likely depend on a few other Kconfigs, eg CONFIG_BPF_JIT, and
    possibly a CONFIG_HAVE_KASAN_EBPF, that would be set for x86 only
    for now
- I am also thinking about adding a sysctl (present and enabled by
  default if CONFIG_KASAN_EBPF=1), to allow temporarily disabling KASAN
  for ebpf programs. When set to 0, JIT compiler would stop inserting
  checking instructions in new programs being loaded.

# Testing

This new KASAN feature must obviously come with some tests. I'd like to
find a way to trigger KASAN reports in ebpf programs without having to
alter the verifier specifically for testing. I am thinking about
creating dedicated _faulty_ kfuncs in
tools/testing/selftests/bpf/bpf_testmod.c, and a corresponding bpf
program:
- those kfuncs would return kernel data to be used by the test program,
  but they would trigger a variety of issues, eg:
  - returned data has already been freed
  - returned data is not pointing to the beginning of an allocated
    buffer but at an arbitrary offset in this buffer, making the caller
    potentially perform OoB accesses
  - etc
- ebpf programs would trigger kasan reports when trying to access the
  corresponding data, the test would be about making sure that the
  report is indeed triggered

Alexei also made me aware that Emil Tsalapatis is working on adding ASAN
for bpf arenas ([3]). The main difference is that Emil's sanitizing will
be directly included in the bpf bytecode, while this RFC proposes to
inject ASAN checks in the JITed code. Also, Emil's series seems to need
dedicated KASAN support as it aims to sanitize accesses on memory
returned by the custom allocators brought by this same series (on top of
bpf arenas).

This plan is based from some small tests and quite a lot of code
reading, I hope not to miss any major feature and/or technical
constraint, hence this RFC. Once again, feel free to correct me and/or
challenge this plan.

Alexis

[0] https://alpha-omega.dev/grants/grantrecipients/
[1] https://www.kernel.org/doc/html/latest/dev-tools/kasan.html
[2] https://github.com/google/sanitizers/wiki/AddressSanitizerAlgorithm#mapping
[3] https://lore.kernel.org/bpf/20260127181610.86376-1-emil@etsalapatis.com/

-- 
Alexis Lothoré, Bootlin
Embedded Linux and Kernel engineering
https://bootlin.com