Summary

A bug in the verifier’s register limit tracking was found by using https://github.com/google/buzzer that allows an attacker to trick the eBPF verifier into thinking a register has a value different from the one it takes when executing the program.
Using this bug, an LPE exploit was written allowing the attacker to gain an arbitrary kernel memory R/W primitive that can then be used to gain a full system compromise.

Severity

Moderate -

Proof of Concept

This is a complex operation that involves following the possible branches a bpf program can take and calculate all the possible states a register can take for all given possible branches a program can take.
To do this, the verifier has a bpf_reg_state structure. Particularly, the verifier keeps track of the possible minimum and maximum values a register can take when it is interpreted as an uint64_t, int64_t, uint32_t, int32_t.
Additionally, the verifier keeps track of all the bits that are known to be set on a register, this is tracked in the var_off field of bpf_reg_state . Var_off works by keeping a u64 value that acts as a mask, for any given bit that is known to the verifier, the mask will take the value of 0 at that bit’s position and the bit’s value will be tracked in the value member of the var_off.
To better illustrate this, here are a few examples from the verifier’s perspective of the limits of a register for a few given operations. For simplicity we will only illustrate the limits for when the register gets interpreted as a signed 32 bit value. U64, S64 and U32 values would follow a similar idea:

REG INVARIANTS VIOLATION (true_reg1): range bounds violation u64=[0xffffffff, 0xfffffffe] s64=[0xffffffff, 0xfffffffe] u32=[0xffffffff, 0xfffffffe] s32=[0xffffffff, 0xfffffffe] var_off=(0xffffffff, 0x0)
REG INVARIANTS VIOLATION (true_reg2): range bounds violation u64=[0xffffffffffffffff, 0xfffffffffffffffe] s64=[0xffffffffffffffff, 0xfffffffffffffffe] u32=[0xffffffff, 0xfffffffe] s32=[0xffffffff, 0xfffffffe] var_off=(0xffffffffffffffff, 0x0)
REG INVARIANTS VIOLATION (false_reg2): const tnum out of sync with range bounds u64=[0x0, 0xffffffffffffffff] s64=[0x8000000000000000, 0x7fffffffffffffff] u32=[0x0, 0xffffffff] s32=[0x80000000, 0x7fffffff] var_off=(0xffffffffffffffff, 0x0)

R1 = read_from_map() // The verifier knows nothing about R1
R1 |= 2 // The verifier knows that bit 2 is set but knows nothing about the rest
if R1 != 0x7ffffffd goto b1:
Exit // False branch
b1:
R0 = 0 // True branch
Exit