From: John Fastabend <john.fastabend@gmail.com> To: ecree@solarflare.com, yhs@fb.com, alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: netdev@vger.kernel.org, bpf@vger.kernel.org, john.fastabend@gmail.com Subject: [bpf-next PATCH v2 0/7] ALU32 bounds tracking support Date: Mon, 30 Mar 2020 14:35:59 -0700 Message-ID: <158560409224.10843.3588655801186916301.stgit@john-Precision-5820-Tower> (raw) This series adds ALU32 signed and unsigned min/max bounds. The origins of this work is to fix do_refine_retval_range() which before this series clamps the return value bounds to [0, max]. However, this is not correct because its possible these functions may return negative errors so the correct bound is [*MIN, max]. Where *MIN is the signed and unsigned min values U64_MIN and S64_MIN. And 'max' here is the max positive value returned by this routine. Patch 1 changes the do_refine_retval_range() to return the correct bounds but this breaks existing programs that were depending on the old incorrect bound. To repair these old programs we add ALU32 bounds to properly track the return values from these helpers. The ALU32 bounds are needed because clang realizes these helepers return 'int' type and will use jmp32 ops with the return value. With current state of things this does little to help 64bit bounds and with patch 1 applied will cause many programs to fail verifier pass. See patch 5 for trace details on how this happens. Patch 2 does the ALU32 addition it adds the new bounds and populates them through the verifier. Design note, initially a var32 was added but as pointed out by Alexei and Edward it is not strictly needed so it was removed here. This worked out nicely. Patch 3 notes that the refine return value can now also bound the 32-bit subregister allowing better bouinds tracking in these cases. Patches 4 adds a C test case to test_progs which will cause the verifier to fail if new 32bit and do_refine_retval_range() is incorrect. Patches 5 and 6 fix test cases that broke after refining the return values from helpers. I attempted to be explicit about each failure and why we need the change. See patches for details. Patch 7 adds some bounds check tests to ensure bounds checking when mixing alu32, alu64 and jmp32 ops together. Thanks to Alexei, Edward, and Daniel for initial feedback it helped clean this up a lot. v2: - rebased to bpf-next - fixed tnum equals optimization for combining 32->64bits - updated patch to fix verifier test correctly - updated refine_retval_range to set both s32_*_value and s*_value we need both to get better bounds tracking --- John Fastabend (7): bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly bpf: verifier, do explicit ALU32 bounds tracking bpf: verifier, refine 32bit bound in do_refine_retval_range bpf: test_progs, add test to catch retval refine error handling bpf: test_verifier, bpf_get_stack return value add <0 bpf: test_verifier, #65 error message updates for trunc of boundary-cross bpf: test_verifier, add alu32 bounds tracking tests include/linux/bpf_verifier.h | 4 include/linux/limits.h | 1 include/linux/tnum.h | 12 kernel/bpf/tnum.c | 15 kernel/bpf/verifier.c | 1138 +++++++++++++++----- .../selftests/bpf/prog_tests/get_stack_raw_tp.c | 5 .../selftests/bpf/progs/test_get_stack_rawtp_err.c | 26 tools/testing/selftests/bpf/verifier/bounds.c | 51 + .../testing/selftests/bpf/verifier/bpf_get_stack.c | 8 9 files changed, 959 insertions(+), 301 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/test_get_stack_rawtp_err.c -- Signature
next reply index Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top 2020-03-30 21:35 John Fastabend [this message] 2020-03-30 21:36 ` [bpf-next PATCH v2 1/7] bpf: verifier, do_refine_retval_range may clamp umin to 0 incorrectly John Fastabend 2020-03-30 21:36 ` [bpf-next PATCH v2 2/7] bpf: verifier, do explicit ALU32 bounds tracking John Fastabend 2020-03-30 22:23 ` Alexei Starovoitov 2020-03-30 21:36 ` [bpf-next PATCH v2 3/7] bpf: verifier, refine 32bit bound in do_refine_retval_range John Fastabend 2020-03-30 21:37 ` [bpf-next PATCH v2 4/7] bpf: test_progs, add test to catch retval refine error handling John Fastabend 2020-03-30 21:37 ` [bpf-next PATCH v2 5/7] bpf: test_verifier, bpf_get_stack return value add <0 John Fastabend 2020-03-30 21:38 ` [bpf-next PATCH v2 6/7] bpf: test_verifier, #65 error message updates for trunc of boundary-cross John Fastabend 2020-03-30 21:38 ` [bpf-next PATCH v2 7/7] bpf: test_verifier, add alu32 bounds tracking tests John Fastabend
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=158560409224.10843.3588655801186916301.stgit@john-Precision-5820-Tower \ --to=john.fastabend@gmail.com \ --cc=alexei.starovoitov@gmail.com \ --cc=bpf@vger.kernel.org \ --cc=daniel@iogearbox.net \ --cc=ecree@solarflare.com \ --cc=netdev@vger.kernel.org \ --cc=yhs@fb.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
BPF Archive on lore.kernel.org Archives are clonable: git clone --mirror https://lore.kernel.org/bpf/0 bpf/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 bpf bpf/ https://lore.kernel.org/bpf \ bpf@vger.kernel.org public-inbox-index bpf Example config snippet for mirrors Newsgroup available over NNTP: nntp://nntp.lore.kernel.org/org.kernel.vger.bpf AGPL code for this site: git clone https://public-inbox.org/public-inbox.git