All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
@ 2017-06-27 12:53 ` Edward Cree via iovisor-dev
  0 siblings, 0 replies; 83+ messages in thread
From: Edward Cree @ 2017-06-27 12:53 UTC (permalink / raw)
  To: davem, Alexei Starovoitov, Alexei Starovoitov, Daniel Borkmann
  Cc: netdev, linux-kernel, iovisor-dev

This series simplifies alignment tracking, generalises bounds tracking and
 fixes some bounds-tracking bugs in the BPF verifier.  Pointer arithmetic on
 packet pointers, stack pointers, map value pointers and context pointers has
 been unified, and bounds on these pointers are only checked when the pointer
 is dereferenced.
Operations on pointers which destroy all relation to the original pointer
 (such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks,
 otherwise they convert the pointer to an unknown scalar and feed it to the
 normal scalar arithmetic handling.
Pointer types have been unified with the corresponding adjusted-pointer types
 where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs
 PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into
 SCALAR_VALUE.
Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and
 PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and
 a 'variable offset'; the former is used when e.g. adding an immediate or a
 known-constant register, as long as it does not overflow.  Otherwise the
 latter is used, and any operation creating a new variable offset creates a
 new 'id' (and, for PTR_TO_PACKET, clears the 'range').
SCALAR_VALUEs use the 'variable offset' fields to track the range of possible
 values; the 'fixed offset' should never be set on a scalar.

As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier
 and tools/testing/selftests/bpf/test_align pass.

v3: added a few more tests; removed RFC tags.

v2: fixed nfp build, made test_align pass again and extended it with a few
 new tests (though still need to add more).

Edward Cree (12):
  selftests/bpf: add test for mixed signed and unsigned bounds checks
  bpf/verifier: rework value tracking
  nfp: change bpf verifier hooks to match new verifier data structures
  bpf/verifier: track signed and unsigned min/max values
  bpf/verifier: more concise register state logs for constant var_off
  selftests/bpf: change test_verifier expectations
  selftests/bpf: rewrite test_align
  selftests/bpf: add a test to test_align
  selftests/bpf: add test for bogus operations on pointers
  selftests/bpf: don't try to access past MAX_PACKET_OFF in
    test_verifier
  selftests/bpf: add tests for subtraction & negative numbers
  selftests/bpf: variable offset negative tests

 drivers/net/ethernet/netronome/nfp/bpf/verifier.c |   24 +-
 include/linux/bpf.h                               |   34 +-
 include/linux/bpf_verifier.h                      |   56 +-
 include/linux/tnum.h                              |   81 +
 kernel/bpf/Makefile                               |    2 +-
 kernel/bpf/tnum.c                                 |  180 ++
 kernel/bpf/verifier.c                             | 1943 ++++++++++++---------
 tools/testing/selftests/bpf/test_align.c          |  462 ++++-
 tools/testing/selftests/bpf/test_verifier.c       |  293 ++--
 9 files changed, 2034 insertions(+), 1041 deletions(-)
 create mode 100644 include/linux/tnum.h
 create mode 100644 kernel/bpf/tnum.c

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

end of thread, other threads:[~2017-07-17 17:02 UTC | newest]

Thread overview: 83+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-06-27 12:53 [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree
2017-06-27 12:53 ` Edward Cree via iovisor-dev
2017-06-27 12:56 ` [PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks Edward Cree
2017-06-27 12:56   ` Edward Cree via iovisor-dev
2017-06-28 13:51   ` Daniel Borkmann
2017-06-28 13:51     ` Daniel Borkmann via iovisor-dev
2017-06-27 12:56 ` [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Edward Cree
2017-06-27 12:56   ` Edward Cree via iovisor-dev
2017-06-28 15:15   ` Daniel Borkmann
2017-06-28 16:07     ` Edward Cree
2017-06-28 16:07       ` Edward Cree via iovisor-dev
2017-06-28 19:44       ` Daniel Borkmann
2017-06-28 19:44         ` Daniel Borkmann via iovisor-dev
2017-06-28 17:09   ` Daniel Borkmann
2017-06-28 17:09     ` Daniel Borkmann via iovisor-dev
2017-06-28 18:28     ` Edward Cree
2017-06-28 18:28       ` Edward Cree via iovisor-dev
2017-06-29  7:48   ` kbuild test robot
     [not found]   ` <2244b48b-f415-3239-6912-cb09f0abc546-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-07-06 20:26     ` Nadav Amit via iovisor-dev
2017-07-06 21:21   ` [iovisor-dev] " Nadav Amit
2017-07-06 21:21     ` Nadav Amit via iovisor-dev
2017-07-07 13:48     ` [iovisor-dev] " Edward Cree
2017-07-07 13:48       ` Edward Cree via iovisor-dev
2017-07-07 17:45       ` [iovisor-dev] " Nadav Amit
2017-07-07 17:45         ` Nadav Amit via iovisor-dev
2017-07-08  0:54         ` [iovisor-dev] " Nadav Amit
2017-07-08  0:54           ` Nadav Amit via iovisor-dev
2017-07-12 19:13         ` [iovisor-dev] " Edward Cree
2017-07-12 19:13           ` Edward Cree via iovisor-dev
2017-07-12 22:07           ` [iovisor-dev] " Nadav Amit
2017-07-12 22:07             ` Nadav Amit via iovisor-dev
2017-07-17 17:02             ` [iovisor-dev] " Edward Cree
2017-07-17 17:02               ` Edward Cree via iovisor-dev
2017-06-27 12:57 ` [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Edward Cree
2017-06-27 12:57   ` Edward Cree via iovisor-dev
2017-06-28 20:47   ` Daniel Borkmann
2017-06-28 20:47     ` Daniel Borkmann via iovisor-dev
2017-06-29  3:47   ` Jakub Kicinski
2017-06-29  3:47     ` Jakub Kicinski via iovisor-dev
2017-06-27 12:57 ` [PATCH v3 net-next 04/12] bpf/verifier: track signed and unsigned min/max values Edward Cree
2017-06-27 12:57   ` Edward Cree via iovisor-dev
2017-06-27 12:58 ` [PATCH v3 net-next 05/12] bpf/verifier: more concise register state logs for constant var_off Edward Cree
2017-06-27 12:58   ` Edward Cree via iovisor-dev
2017-06-27 12:58 ` [PATCH v3 net-next 06/12] selftests/bpf: change test_verifier expectations Edward Cree
2017-06-27 12:58   ` Edward Cree via iovisor-dev
2017-06-27 12:59 ` [PATCH v3 net-next 07/12] selftests/bpf: rewrite test_align Edward Cree
2017-06-27 12:59   ` Edward Cree via iovisor-dev
2017-06-27 12:59 ` [PATCH v3 net-next 08/12] selftests/bpf: add a test to test_align Edward Cree
2017-06-27 12:59   ` Edward Cree via iovisor-dev
2017-06-27 12:59 ` [PATCH v3 net-next 09/12] selftests/bpf: add test for bogus operations on pointers Edward Cree
2017-06-27 12:59   ` Edward Cree via iovisor-dev
2017-06-27 12:59 ` [PATCH v3 net-next 10/12] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier Edward Cree
2017-06-27 12:59   ` Edward Cree via iovisor-dev
2017-06-27 13:00 ` [PATCH v3 net-next 11/12] selftests/bpf: add tests for subtraction & negative numbers Edward Cree
2017-06-27 13:00   ` Edward Cree via iovisor-dev
2017-06-27 13:00 ` [PATCH v3 net-next 12/12] selftests/bpf: variable offset negative tests Edward Cree
2017-06-27 13:00   ` Edward Cree via iovisor-dev
2017-06-28 13:50 ` [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann
2017-06-28 14:11   ` Edward Cree
2017-06-28 14:11     ` Edward Cree via iovisor-dev
2017-06-28 20:38     ` Daniel Borkmann
2017-06-28 20:38       ` Daniel Borkmann via iovisor-dev
2017-06-28 21:37       ` Alexei Starovoitov
2017-06-28 21:37         ` Alexei Starovoitov via iovisor-dev
2017-06-30 16:44         ` Edward Cree
2017-06-30 16:44           ` Edward Cree via iovisor-dev
2017-06-30 17:34           ` [TEST PATCH] bpf/verifier: roll back ptr&const handling, and fix signed bounds Edward Cree
2017-06-30 17:34             ` Edward Cree via iovisor-dev
2017-06-30 18:15           ` [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Alexei Starovoitov
2017-06-30 18:15             ` Alexei Starovoitov via iovisor-dev
2017-07-04 19:22             ` Edward Cree
2017-07-04 19:22               ` Edward Cree via iovisor-dev
2017-07-04 22:28               ` Daniel Borkmann
2017-07-04 22:28                 ` Daniel Borkmann via iovisor-dev
2017-07-06 18:27                 ` Edward Cree
2017-07-07  9:14                   ` Daniel Borkmann
2017-07-07  9:14                     ` Daniel Borkmann via iovisor-dev
2017-07-07 12:50                     ` Edward Cree
2017-07-07 12:50                       ` Edward Cree via iovisor-dev
2017-07-07 13:05                       ` Daniel Borkmann
2017-07-06 14:07               ` Edward Cree
2017-07-06 14:07                 ` Edward Cree via iovisor-dev
2017-07-14 20:03 ` [iovisor-dev] " Y Song

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.