public inbox for bpf@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH bpf-next 00/13] BPF register bounds range vs range support
@ 2023-11-03  0:08 Andrii Nakryiko
  2023-11-03  0:08 ` [PATCH bpf-next 01/13] bpf: generalize reg_set_min_max() to handle non-const register comparisons Andrii Nakryiko
                   ` (12 more replies)
  0 siblings, 13 replies; 39+ messages in thread
From: Andrii Nakryiko @ 2023-11-03  0:08 UTC (permalink / raw)
  To: bpf, ast, daniel, martin.lau; +Cc: andrii, kernel-team

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=*

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                         |  619 ++---
 tools/include/uapi/linux/bpf.h                |    3 +
 .../bpf/prog_tests/bpf_verif_scale.c          |    2 +-
 .../selftests/bpf/prog_tests/reg_bounds.c     | 2091 +++++++++++++++++
 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        |   12 +-
 16 files changed, 2511 insertions(+), 300 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/reg_bounds.c

-- 
2.34.1


^ permalink raw reply	[flat|nested] 39+ messages in thread

end of thread, other threads:[~2023-11-09  9:03 UTC | newest]

Thread overview: 39+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-11-03  0:08 [PATCH bpf-next 00/13] BPF register bounds range vs range support Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 01/13] bpf: generalize reg_set_min_max() to handle non-const register comparisons Andrii Nakryiko
2023-11-03  7:52   ` Shung-Hsi Yu
2023-11-03  8:33     ` Shung-Hsi Yu
2023-11-03 20:39     ` Andrii Nakryiko
2023-11-03 20:48       ` Andrii Nakryiko
2023-11-06  2:22         ` Shung-Hsi Yu
2023-11-03 16:20   ` Eduard Zingerman
2023-11-03 20:39     ` Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 02/13] bpf: generalize is_scalar_branch_taken() logic Andrii Nakryiko
2023-11-03  0:13   ` Andrii Nakryiko
2023-11-03 16:47   ` Eduard Zingerman
2023-11-03 20:59     ` Andrii Nakryiko
2023-11-03 21:02       ` Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 03/13] bpf: enhance BPF_JEQ/BPF_JNE is_branch_taken logic Andrii Nakryiko
2023-11-03 17:28   ` Eduard Zingerman
2023-11-09  8:39   ` Shung-Hsi Yu
2023-11-03  0:08 ` [PATCH bpf-next 04/13] bpf: add register bounds sanity checks and sanitization Andrii Nakryiko
2023-11-03  2:13   ` Andrii Nakryiko
2023-11-03 17:56   ` Eduard Zingerman
2023-11-03 21:11     ` Andrii Nakryiko
2023-11-03 21:39       ` Eduard Zingerman
2023-11-09  8:30   ` Shung-Hsi Yu
2023-11-03  0:08 ` [PATCH bpf-next 05/13] bpf: remove redundant s{32,64} -> u{32,64} deduction logic Andrii Nakryiko
2023-11-03 22:16   ` Eduard Zingerman
2023-11-09  8:43   ` Shung-Hsi Yu
2023-11-03  0:08 ` [PATCH bpf-next 06/13] bpf: make __reg{32,64}_deduce_bounds logic more robust Andrii Nakryiko
2023-11-03 22:27   ` Eduard Zingerman
2023-11-09  9:02   ` Shung-Hsi Yu
2023-11-03  0:08 ` [PATCH bpf-next 07/13] selftests/bpf: BPF register range bounds tester Andrii Nakryiko
2023-11-03 19:19   ` Alexei Starovoitov
2023-11-03 21:12     ` Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 08/13] selftests/bpf: adjust OP_EQ/OP_NE handling to use subranges for branch taken Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 09/13] selftests/bpf: add range x range test to reg_bounds Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 10/13] selftests/bpf: add randomized reg_bounds tests Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 11/13] selftests/bpf: set BPF_F_TEST_SANITY_SCRIPT by default Andrii Nakryiko
2023-11-03 22:35   ` Eduard Zingerman
2023-11-03  0:08 ` [PATCH bpf-next 12/13] veristat: add ability to set BPF_F_TEST_SANITY_STRICT flag with -r flag Andrii Nakryiko
2023-11-03  0:08 ` [PATCH bpf-next 13/13] selftests/bpf: add iter test requiring range x range logic Andrii Nakryiko

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox