This patch set adds a big set of manual and auto-generated test cases validating BPF verifier's register bounds tracking and deduction logic. See details in the last patch. We start with building a tester that validates existing <range> vs <scalar> verifier logic for range bounds. To make all this work, BPF verifier's logic needed a bunch of improvements to handle some cases that previously were not covered. This had no implications as to correctness of verifier logic, but it was incomplete enough to cause significant disagreements with alternative implementation of register bounds logic that tests in this patch set implement. So we need BPF verifier logic improvements to make all the tests pass. This is what we do in patches #3 through #9. Patch #10 implements tester. We guard millions of generated tests behind SLOW_TESTS=1 envvar requirement, but also have a relatively small number of tricky cases that came up during development and debugging of this work. Those will be executed as part of a normal test_progs run. The end goal of this work, though, is to extend BPF verifier range state tracking such as to allow to derive new range bounds when comparing non-const registers. There is some more investigative work required to investigate and fix existing potential issues with range tracking as part of ALU/ALU64 operations, so <range> x <range> part of v5 patch set ([0]) is dropped until these issues are sorted out. For now, we include preparatory refactorings and clean ups, that set up BPF verifier code base to extend the logic to <range> vs <range> logic in subsequent patch set. Patches #11-#17 perform preliminary refactorings without functionally changing anything. But they do clean up check_cond_jmp_op() logic and generalize a bunch of other pieces in is_branch_taken() logic. [0] https://patchwork.kernel.org/project/netdevbpf/list/?series=797178&state=* v5->v6: - dropped <range> vs <range> patches (original patches #18 through #23) to add more register range sanity checks and fix preexisting issues; - comments improvements, addressing other feedback on first 17 patches (Eduard, Alexei); v4->v5: - added entirety of verifier reg bounds tracking changes, now handling <range> vs <range> cases (Alexei); - added way more comments trying to explain why deductions added are correct, hopefully they are useful and clarify things a bit (Daniel, Shung-Hsi); - added two preliminary selftests fixes necessary for RELEASE=1 build to work again, it keeps breaking. v3->v4: - improvements to reg_bounds tester (progress report, split 32-bit and 64-bit ranges, fix various verbosity output issues, etc); v2->v3: - fix a subtle little-endianness assumption inside parge_reg_state() (CI); v1->v2: - fix compilation when building selftests with llvm-16 toolchain (CI). Andrii Nakryiko (17): selftests/bpf: fix RELEASE=1 build for tc_opts selftests/bpf: satisfy compiler by having explicit return in btf test bpf: derive smin/smax from umin/max bounds bpf: derive smin32/smax32 from umin32/umax32 bounds bpf: derive subreg bounds from full bounds when upper 32 bits are constant bpf: add special smin32/smax32 derivation from 64-bit bounds bpf: improve deduction of 64-bit bounds from 32-bit bounds bpf: try harder to deduce register bounds from different numeric domains bpf: drop knowledge-losing __reg_combine_{32,64}_into_{64,32} logic selftests/bpf: BPF register range bounds tester bpf: rename is_branch_taken reg arguments to prepare for the second one bpf: generalize is_branch_taken() to work with two registers bpf: move is_branch_taken() down bpf: generalize is_branch_taken to handle all conditional jumps in one place bpf: unify 32-bit and 64-bit is_branch_taken logic bpf: prepare reg_set_min_max for second set of registers bpf: generalize reg_set_min_max() to handle two sets of two registers kernel/bpf/verifier.c | 744 ++++--- tools/testing/selftests/bpf/prog_tests/btf.c | 1 + .../selftests/bpf/prog_tests/reg_bounds.c | 1841 +++++++++++++++++ .../selftests/bpf/prog_tests/tc_opts.c | 6 +- 4 files changed, 2242 insertions(+), 350 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/reg_bounds.c -- 2.34.1
