bpf: Introduce verifier test oracle
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest8 patches 0 repliesNew
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/8 | bpf: Save pruning point states in oracleinclude/ kernel/ kernel/ +1 more | +103 | 0 replies | |
| 2/8 | bpf: Patch bytecode with oracle check instructionsinclude/ include/ kernel/ +4 more | +71 | 0 replies | |
| 3/8 | bpf: Create inner oracle mapsinclude/ include/ kernel/ +2 more | +76 | 0 replies | |
| 4/8 | bpf: Populate inner oracle mapskernel/ | +31 | 0 replies | |
| 5/8 | bpf: Create and populate oracle mapinclude/ include/ kernel/ +2 more | +143 | 0 replies | |
| 6/8 | bpf: Check oracle in interpreterinclude/ include/ kernel/ +2 more | +84 | 0 replies | |
| 7/8 | bpf: Introduce CONFIG_BPF_ORACLEkernel/ kernel/ kernel/ +1 more | +24 | 0 replies | |
| 8/8 | bpftool: Dump oracle mapstools/ tools/ tools/ +1 more | +167 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [PATCH bpf-next 0/8] bpf: Introduce verifier test oracle
This patchset introduces a test oracle for the BPF verifier, to help fuzzers detect false negatives.
At the moment, although several fuzzers cover BPF and its verifier, they report very few soundness issues. These issues can lead to false negatives and are typically silent. This patchset aims to make such bugs noisy, by emitting a kernel warning when they happen.
The idea is relatively simple: when the test oracle is enabled, the verifier will save some information on variables (registers and stack slots) at regular points throughout the program. This information can then be compared at runtime with the concrete values to ensure that the verifier's information is correct.
This patchset implements this idea for registers and saves their ranges into array maps at pruning points. The interpreter then compares the runtime values of registers with their expected ranges. The idea can be extended to stack slots and JIT compiles in the future.
I'm sending this as an RFC to have a concrete base for discussion at Linux Plumbers [1] even if some of the patches still need some work/cleanup. The end of this cover letter lists different limitations and aspects that may require discussion.
[1] https://lpc.events/event/19/contributions/2164/
Example
=======
The test oracle can be easily tested by reverting commit 811c363645b3 ("bpf: Fix check_stack_write_fixed_off() to correctly spill imm") and loading the following program:
0: r2 = r10; 1: *(u64*)(r2 -40) = -44; 2: r6 = *(u64*)(r2 - 40); 3: call 7; 4: r0 = 0; 5: exit;
As shown below, without the fix, the verifier will lose the sign information when spilling -44 to the stack. It thus expects R6 to be equal to 0xffffffd4.
0: R1=ctx() R10=fp0
0: (bf) r2 = r10 ; R2=fp0 R10=fp0 1: (7a) *(u64 *)(r2 -40) = -44 ; R2=fp0 fp-40=0xffffffd4 2: (79) r6 = *(u64 *)(r2 -40) ; R2=fp0 R6=0xffffffd4 fp-40=0xffffffd4 3: (85) call bpf_get_prandom_u32#7 ; R0=scalar() 4: (b7) r0 = 0 ; R0=0
5: (95) exit
processed 6 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
The call at instruction 3 simply provides us with a pruning point. At the moment, it is required to trigger the test oracle (but not to reproduce the bug).
When running this program with JIT disabled and the test oracle enabled, it will throw the following kernel warning:
[ 29.845786] ------------[ cut here ]------------ [ 29.846696] oracle caught invalid states in oracle_map[id:22]: r6=0xffffffffffffffd4 [ 29.847857] WARNING: kernel/bpf/oracle.c:368 at 0x0, CPU#1: minimal/544
The "bpftool oracle" command introduced at the end of this patchset shows the information saved on registers:
# bpftool oracle dump id 22 State 0: R0=scalar(u64=[0; 18446744073709551615], s64=[-9223372036854775808; 9223372036854775807], u32=[0; 4294967295], s32=[-2147483648; 2147483647], var_off=(0; 0xffffffffffffffff) R6=scalar(u64=[4294967252; 4294967252], s64=[4294967252; 4294967252], u32=[4294967252; 4294967252], s32=[-44; -44], var_off=(0xffffffd4; 0)
Found 1 state
Our small example contains a single path and a single state at the pruning point, but the oracle isn't limited to that. If there are several saved states, it will compare concrete runtime values with each state and warn only if none of them match the concrete values.
Limitations and other considerations
====================================
- The current version uses a special LDIMM64 instruction to encode the map addresses in the bytecode for lookups from the interpreter. This is very hackish, so I'd like to replace it with something else. One option is to use a new instruction closer to BPF_ST_NOSPEC. Another option is to avoid adding any instruction and lookup the maps from the hashmap of maps. We however need the instruction index for that, so it would mean keeping a count of instruction indexes in the interpreter.
- The oracle test is enabled via a new kernel config. This feels like the easiest option for fuzzers as they can enable it once and for all in their test VM images. Other, runtime options may require a bit more work as we'd potentially need to remember which programs have been loaded with the oracle enabled.
- The current version doesn't support subprogs. I'm not seeing any blocker, except that we don't have the callchain at runtime. We would therefore need to save states for different calls under the same key (the instruction index) and would likely lose some precision.
- As shown in the example above, we currently need pruning points to detect bugs. There's a tradeoff here between saving information too often (high memory usage) vs. not often enough (lower precision). Pruning points felt like a good middle ground, but we can also choose a different heuristic (ex., jump targets + exits).
Paul Chaignon (8):
bpf: Save pruning point states in oracle
bpf: Patch bytecode with oracle check instructions
bpf: Create inner oracle maps
bpf: Populate inner oracle maps
bpf: Create and populate oracle map
bpf: Check oracle in interpreter
bpf: Introduce CONFIG_BPF_ORACLE
bpftool: Dump oracle maps
include/linux/bpf.h | 6 + include/linux/bpf_verifier.h | 45 ++++ include/linux/tnum.h | 3 + include/uapi/linux/bpf.h | 10 + kernel/bpf/Kconfig | 14 ++ kernel/bpf/Makefile | 1 + kernel/bpf/core.c | 14 +- kernel/bpf/disasm.c | 3 +- kernel/bpf/hashtab.c | 6 +- kernel/bpf/oracle.c | 387 ++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 12 +- kernel/bpf/tnum.c | 5 + kernel/bpf/verifier.c | 40 ++- tools/bpf/bpftool/main.c | 3 +- tools/bpf/bpftool/main.h | 1 + tools/bpf/bpftool/oracle.c | 154 ++++++++++++ tools/bpf/bpftool/xlated_dumper.c | 3 + tools/include/uapi/linux/bpf.h | 10 + 18 files changed, 695 insertions(+), 22 deletions(-) create mode 100644 kernel/bpf/oracle.c create mode 100644 tools/bpf/bpftool/oracle.c
Signature · 1 line
2.43.0