netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC PATCH net-next 0/5] bpf: rewrite value tracking in verifier
@ 2017-06-07 14:55 Edward Cree via iovisor-dev
       [not found] ` <92db9689-af6a-e172-ba57-195e588f9cc0-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
                   ` (2 more replies)
  0 siblings, 3 replies; 25+ messages in thread
From: Edward Cree via iovisor-dev @ 2017-06-07 14:55 UTC (permalink / raw)
  To: davem-fT/PcQaiUtIeIZ0/mPfg9Q, Alexei Starovoitov,
	Alexei Starovoitov, Daniel Borkmann
  Cc: netdev-u79uwXL29TY76Z2rM5mHXA, iovisor-dev, LKML

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.

Patch 2/5 is rather on the big side, but since it changes the contents and
 semantics of a fairly central data structure, I'm not really sure how to go
 about splitting it up further without producing broken intermediate states.

With the changes in patch 5/5, all tools/testing/selftests/bpf/test_verifier
 tests pass.

Edward Cree (5):
  selftests/bpf: add test for mixed signed and unsigned bounds checks
  bpf/verifier: rework value tracking
  bpf/verifier: feed pointer-to-unknown-scalar casts into scalar ALU
    path
  bpf/verifier: track signed and unsigned min/max values
  selftests/bpf: change test_verifier expectations

 include/linux/bpf.h                         |   34 +-
 include/linux/bpf_verifier.h                |   56 +-
 include/linux/tnum.h                        |   58 +
 kernel/bpf/Makefile                         |    2 +-
 kernel/bpf/tnum.c                           |  163 +++
 kernel/bpf/verifier.c                       | 1852 ++++++++++++++++-----------
 tools/testing/selftests/bpf/test_verifier.c |  248 ++--
 7 files changed, 1482 insertions(+), 931 deletions(-)
 create mode 100644 include/linux/tnum.h
 create mode 100644 kernel/bpf/tnum.c

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

end of thread, other threads:[~2017-06-09 13:25 UTC | newest]

Thread overview: 25+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-06-07 14:55 [RFC PATCH net-next 0/5] bpf: rewrite value tracking in verifier Edward Cree via iovisor-dev
     [not found] ` <92db9689-af6a-e172-ba57-195e588f9cc0-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-07 14:58   ` [RFC PATCH net-next 1/5] selftests/bpf: add test for mixed signed and unsigned bounds checks Edward Cree via iovisor-dev
2017-06-07 14:58   ` [RFC PATCH net-next 2/5] bpf/verifier: rework value tracking Edward Cree via iovisor-dev
     [not found]     ` <cef78266-62ec-8ef7-a512-cc111ba9c22a-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08  2:32       ` Alexei Starovoitov via iovisor-dev
2017-06-08 14:53         ` Edward Cree via iovisor-dev
     [not found]           ` <81a661cc-a37c-336b-c10f-1fd4b301ca54-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08 16:45             ` Alexei Starovoitov via iovisor-dev
     [not found]               ` <20170608164553.y2jvdbmsqqdc7cqt-+o4/htvd0TCa6kscz5V53/3mLCh9rsb+VpNB7YpNyf8@public.gmane.org>
2017-06-08 19:38                 ` Edward Cree via iovisor-dev
     [not found]                   ` <9b7aaa39-aacf-6f41-6adf-fc9317c447aa-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08 21:20                     ` Alexei Starovoitov via iovisor-dev
2017-06-09 13:25               ` Daniel Borkmann
2017-06-07 14:58   ` [RFC PATCH net-next 3/5] bpf/verifier: feed pointer-to-unknown-scalar casts into scalar ALU path Edward Cree via iovisor-dev
     [not found]     ` <47ecf6ca-ae89-7fc3-3cd5-a47009b6ede9-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08  2:35       ` Alexei Starovoitov via iovisor-dev
2017-06-08 15:25         ` Edward Cree via iovisor-dev
2017-06-08 16:50           ` Alexei Starovoitov
     [not found]             ` <20170608165004.n5jc33pocxlytuvf-+o4/htvd0TCa6kscz5V53/3mLCh9rsb+VpNB7YpNyf8@public.gmane.org>
2017-06-08 17:12               ` Edward Cree via iovisor-dev
     [not found]                 ` <3cca425f-5794-dddd-18a8-af5e36bb3597-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08 18:41                   ` Alexei Starovoitov via iovisor-dev
     [not found]                     ` <20170608184108.52tlp5apo44jte2t-+o4/htvd0TCa6kscz5V53/3mLCh9rsb+VpNB7YpNyf8@public.gmane.org>
2017-06-08 19:07                       ` Edward Cree via iovisor-dev
     [not found]                         ` <05371ef3-f10a-21b0-def0-1cbdfe458171-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08 21:17                           ` Alexei Starovoitov via iovisor-dev
2017-06-07 15:00   ` [RFC PATCH net-next 5/5] selftests/bpf: change test_verifier expectations Edward Cree via iovisor-dev
     [not found]     ` <b04aa1a3-2b6c-2d3d-f26f-17eaaa549539-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08  2:43       ` Alexei Starovoitov via iovisor-dev
2017-06-08 15:27         ` Edward Cree via iovisor-dev
2017-06-07 14:59 ` [RFC PATCH net-next 4/5] bpf/verifier: track signed and unsigned min/max values Edward Cree
     [not found]   ` <56b924eb-e2d5-b2ee-484a-d073a3b13d79-s/n/eUQHGBpZroRs9YW3xA@public.gmane.org>
2017-06-08  2:40     ` Alexei Starovoitov via iovisor-dev
2017-06-08 15:23       ` Edward Cree via iovisor-dev
2017-06-08 16:47         ` Alexei Starovoitov
2017-06-08 20:18 ` [RFC PATCH net-next 0/5] bpf: rewrite value tracking in verifier David Miller

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).