Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753345AbdF0MyE (ORCPT ); Tue, 27 Jun 2017 08:54:04 -0400 Received: from dispatch1-us1.ppe-hosted.com ([67.231.154.164]:34644 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753007AbdF0Mxu (ORCPT ); Tue, 27 Jun 2017 08:53:50 -0400 From: Edward Cree Subject: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier To: , Alexei Starovoitov , Alexei Starovoitov , Daniel Borkmann CC: , , iovisor-dev Message-ID: Date: Tue, 27 Jun 2017 13:53:18 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.1.0 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-Originating-IP: [10.17.20.45] X-ClientProxiedBy: ocex03.SolarFlarecom.com (10.20.40.36) To ukex01.SolarFlarecom.com (10.17.10.4) X-TM-AS-Product-Ver: SMEX-11.0.0.1191-8.100.1062-23160.002 X-TM-AS-Result: No--7.154800-0.000000-31 X-TM-AS-User-Approved-Sender: Yes X-TM-AS-User-Blocked-Sender: No X-MDID: 1498568019-9ihqYt5ik8ZZ Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3091 Lines: 57 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