This patch set is a continuation of work started in [0]. It adds a big set of manual, auto-generated, and now also random test cases validating BPF verifier's register bounds tracking and deduction logic. First few patches generalize verifier's logic to handle conditional jumps and corresponding range adjustments in case when two non-const registers are compared to each other. Patch #1 generalizes reg_set_min_max() portion, while patch #2 does the same for is_branch_taken() part of the overall solution. Patch #3 improves equality and inequality for cases when BPF program code mixes 64-bit and 32-bit uses of the same register. Depending on specific sequence, it's possible to get to the point where u64/s64 bounds will be very generic (e.g., after signed 32-bit comparison), while we still keep pretty tight u32/s32 bounds. If in such state we proceed with 32-bit equality or inequality comparison, reg_set_min_max() might have to deal with adjusting s32 bounds for two registers that don't overlap, which breaks reg_set_min_max(). This doesn't manifest in <range> vs <const> cases, because if that happens reg_set_min_max() in effect will force s32 bounds to be a new "impossible" constant (from original smin32/smax32 bounds point of view). Things get tricky when we have <range> vs <range> adjustments, so instead of trying to somehow make sense out of such situations, it's best to detect such impossible situations and prune the branch that can't be taken in is_branch_taken() logic. This equality/inequality was the only such category of situations with auto-generated tests added later in the patch set. But when we start mixing arithmetic operations in different numeric domains and conditionals, things get even hairier. So, patch #4 adds sanity checking logic after all ALU/ALU64, JMP/JMP32, and LDX operations. By default, instead of failing verification, we conservatively reset range bounds to unknown values, reporting violation in verifier log (if verbose logs are requested). But to aid development, detection, and debugging, we also introduce a new test flag, BPF_F_TEST_SANITY_STRICT, which triggers verification failure on range sanity violation. Patch #11 sets BPF_F_TEST_SANITY_STRICT by default for test_progs and test_verifier. Patch #12 adds support for controlling this in veristat for testing with production BPF object files. Getting back to BPF verifier, patches #5 and #6 complete verifier's range tracking logic clean up. See respective patches for details. With kernel-side taken care of, we move to testing. We start with building a tester that validates existing <range> vs <scalar> verifier logic for range bounds. Patch #7 implements an initial version of such a 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. Patch #8 simulates more nuanced JEQ/JNE logic we added to verifier in patch #3. Patch #9 adds <range> vs <range> "slow tests". Patch #10 is a completely new one, it adds a bunch of randomly generated cases to be run normally, without SLOW_TESTS=1 guard. This should help to get a bunch of cover, and hopefully find some remaining latent problems if verifier proactively as part of normal BPF CI runs. Finally, a tiny test which was, amazingly, an initial motivation for this whole work, is added in lucky patch #13, demonstrating how verifier is now smart enough to track actual number of elements in the array and won't require additional checks on loop iteration variable inside the bpf_for() open-coded iterator loop. [0] https://patchwork.kernel.org/project/netdevbpf/list/?series=798308&state=* v1->v2: - use x < y => y > x property to minimize reg_set_min_max (Eduard); - fix for JEQ/JNE logic in reg_bounds.c (Eduard); - split BPF_JSET and !BPF_JSET cases handling (Shung-Hsi); - adjustments to reg_bounds.c to make it easier to follow (Alexei); - added acks (Eduard, Shung-Hsi). Andrii Nakryiko (13): bpf: generalize reg_set_min_max() to handle non-const register comparisons bpf: generalize is_scalar_branch_taken() logic bpf: enhance BPF_JEQ/BPF_JNE is_branch_taken logic bpf: add register bounds sanity checks and sanitization bpf: remove redundant s{32,64} -> u{32,64} deduction logic bpf: make __reg{32,64}_deduce_bounds logic more robust selftests/bpf: BPF register range bounds tester selftests/bpf: adjust OP_EQ/OP_NE handling to use subranges for branch taken selftests/bpf: add range x range test to reg_bounds selftests/bpf: add randomized reg_bounds tests selftests/bpf: set BPF_F_TEST_SANITY_SCRIPT by default veristat: add ability to set BPF_F_TEST_SANITY_STRICT flag with -r flag selftests/bpf: add iter test requiring range x range logic include/linux/bpf_verifier.h | 1 + include/linux/tnum.h | 4 + include/uapi/linux/bpf.h | 3 + kernel/bpf/syscall.c | 3 +- kernel/bpf/tnum.c | 7 +- kernel/bpf/verifier.c | 601 ++--- tools/include/uapi/linux/bpf.h | 3 + .../bpf/prog_tests/bpf_verif_scale.c | 2 +- .../selftests/bpf/prog_tests/reg_bounds.c | 2099 +++++++++++++++++ tools/testing/selftests/bpf/progs/iters.c | 22 + .../selftests/bpf/progs/verifier_bounds.c | 2 + tools/testing/selftests/bpf/test_loader.c | 35 +- tools/testing/selftests/bpf/test_sock_addr.c | 1 + tools/testing/selftests/bpf/test_verifier.c | 2 +- tools/testing/selftests/bpf/testing_helpers.c | 4 +- tools/testing/selftests/bpf/veristat.c | 13 +- 16 files changed, 2495 insertions(+), 307 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/reg_bounds.c -- 2.34.1
