mbox series

[v2,bpf-next,00/13] BPF register bounds range vs range support

Message ID 20231112010609.848406-1-andrii@kernel.org (mailing list archive)
Headers show
Series BPF register bounds range vs range support | expand

Message

Andrii Nakryiko Nov. 12, 2023, 1:05 a.m. UTC
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

Comments

patchwork-bot+netdevbpf@kernel.org Nov. 15, 2023, 8:30 p.m. UTC | #1
Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Sat, 11 Nov 2023 17:05:56 -0800 you wrote:
> 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.
> 
> [...]

Here is the summary with links:
  - [v2,bpf-next,01/13] bpf: generalize reg_set_min_max() to handle non-const register comparisons
    https://git.kernel.org/bpf/bpf-next/c/67420501e868
  - [v2,bpf-next,02/13] bpf: generalize is_scalar_branch_taken() logic
    https://git.kernel.org/bpf/bpf-next/c/96381879a370
  - [v2,bpf-next,03/13] bpf: enhance BPF_JEQ/BPF_JNE is_branch_taken logic
    https://git.kernel.org/bpf/bpf-next/c/be41a203bb9e
  - [v2,bpf-next,04/13] bpf: add register bounds sanity checks and sanitization
    https://git.kernel.org/bpf/bpf-next/c/5f99f312bd3b
  - [v2,bpf-next,05/13] bpf: remove redundant s{32,64} -> u{32,64} deduction logic
    https://git.kernel.org/bpf/bpf-next/c/3cf98cf594ea
  - [v2,bpf-next,06/13] bpf: make __reg{32,64}_deduce_bounds logic more robust
    https://git.kernel.org/bpf/bpf-next/c/cf5fe3c71c5a
  - [v2,bpf-next,07/13] selftests/bpf: BPF register range bounds tester
    https://git.kernel.org/bpf/bpf-next/c/8863238993e2
  - [v2,bpf-next,08/13] selftests/bpf: adjust OP_EQ/OP_NE handling to use subranges for branch taken
    https://git.kernel.org/bpf/bpf-next/c/774f94c5e74d
  - [v2,bpf-next,09/13] selftests/bpf: add range x range test to reg_bounds
    https://git.kernel.org/bpf/bpf-next/c/2b0d204e368b
  - [v2,bpf-next,10/13] selftests/bpf: add randomized reg_bounds tests
    https://git.kernel.org/bpf/bpf-next/c/dab16659c50e
  - [v2,bpf-next,11/13] selftests/bpf: set BPF_F_TEST_SANITY_SCRIPT by default
    https://git.kernel.org/bpf/bpf-next/c/8c5677f8b31e
  - [v2,bpf-next,12/13] veristat: add ability to set BPF_F_TEST_SANITY_STRICT flag with -r flag
    https://git.kernel.org/bpf/bpf-next/c/a5c57f81eb2b
  - [v2,bpf-next,13/13] selftests/bpf: add iter test requiring range x range logic
    https://git.kernel.org/bpf/bpf-next/c/882e3d873c2d

You are awesome, thank you!