From: Andrii Nakryiko <andrii@kernel.org>
To: <bpf@vger.kernel.org>, <ast@kernel.org>, <daniel@iogearbox.net>,
<martin.lau@kernel.org>
Cc: <andrii@kernel.org>, <kernel-team@meta.com>,
Shung-Hsi Yu <shung-hsi.yu@suse.com>,
Eduard Zingerman <eddyz87@gmail.com>
Subject: [PATCH v2 bpf-next 03/13] bpf: enhance BPF_JEQ/BPF_JNE is_branch_taken logic
Date: Sat, 11 Nov 2023 17:05:59 -0800 [thread overview]
Message-ID: <20231112010609.848406-4-andrii@kernel.org> (raw)
In-Reply-To: <20231112010609.848406-1-andrii@kernel.org>
Use 32-bit subranges to prune some 64-bit BPF_JEQ/BPF_JNE conditions
that otherwise would be "inconclusive" (i.e., is_branch_taken() would
return -1). This can happen, for example, when registers are initialized
as 64-bit u64/s64, then compared for inequality as 32-bit subregisters,
and then followed by 64-bit equality/inequality check. That 32-bit
inequality can establish some pattern for lower 32 bits of a register
(e.g., s< 0 condition determines whether the bit #31 is zero or not),
while overall 64-bit value could be anything (according to a value range
representation).
This is not a fancy quirky special case, but actually a handling that's
necessary to prevent correctness issue with BPF verifier's range
tracking: set_range_min_max() assumes that register ranges are
non-overlapping, and if that condition is not guaranteed by
is_branch_taken() we can end up with invalid ranges, where min > max.
[0] https://lore.kernel.org/bpf/CACkBjsY2q1_fUohD7hRmKGqv1MV=eP2f6XK8kjkYNw7BaiF8iQ@mail.gmail.com/
Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
kernel/bpf/verifier.c | 24 ++++++++++++++++++++++++
1 file changed, 24 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f459ad99256e..65570eedfe88 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14283,6 +14283,18 @@ static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
return 0;
if (smin1 > smax2 || smax1 < smin2)
return 0;
+ if (!is_jmp32) {
+ /* if 64-bit ranges are inconclusive, see if we can
+ * utilize 32-bit subrange knowledge to eliminate
+ * branches that can't be taken a priori
+ */
+ if (reg1->u32_min_value > reg2->u32_max_value ||
+ reg1->u32_max_value < reg2->u32_min_value)
+ return 0;
+ if (reg1->s32_min_value > reg2->s32_max_value ||
+ reg1->s32_max_value < reg2->s32_min_value)
+ return 0;
+ }
break;
case BPF_JNE:
/* constants, umin/umax and smin/smax checks would be
@@ -14295,6 +14307,18 @@ static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
return 1;
if (smin1 > smax2 || smax1 < smin2)
return 1;
+ if (!is_jmp32) {
+ /* if 64-bit ranges are inconclusive, see if we can
+ * utilize 32-bit subrange knowledge to eliminate
+ * branches that can't be taken a priori
+ */
+ if (reg1->u32_min_value > reg2->u32_max_value ||
+ reg1->u32_max_value < reg2->u32_min_value)
+ return 1;
+ if (reg1->s32_min_value > reg2->s32_max_value ||
+ reg1->s32_max_value < reg2->s32_min_value)
+ return 1;
+ }
break;
case BPF_JSET:
if (!is_reg_const(reg2, is_jmp32)) {
--
2.34.1
next prev parent reply other threads:[~2023-11-12 1:06 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-12 1:05 [PATCH v2 bpf-next 00/13] BPF register bounds range vs range support Andrii Nakryiko
2023-11-12 1:05 ` [PATCH v2 bpf-next 01/13] bpf: generalize reg_set_min_max() to handle non-const register comparisons Andrii Nakryiko
2023-11-13 4:35 ` Shung-Hsi Yu
2023-11-12 1:05 ` [PATCH v2 bpf-next 02/13] bpf: generalize is_scalar_branch_taken() logic Andrii Nakryiko
2023-11-13 4:46 ` Shung-Hsi Yu
2023-11-12 1:05 ` Andrii Nakryiko [this message]
2023-11-12 1:06 ` [PATCH v2 bpf-next 04/13] bpf: add register bounds sanity checks and sanitization Andrii Nakryiko
2023-11-13 4:53 ` Shung-Hsi Yu
2023-11-15 20:25 ` Alexei Starovoitov
2023-11-15 22:06 ` Andrii Nakryiko
2023-11-16 19:37 ` Alexei Starovoitov
2023-11-12 1:06 ` [PATCH v2 bpf-next 05/13] bpf: remove redundant s{32,64} -> u{32,64} deduction logic Andrii Nakryiko
2023-11-12 1:06 ` [PATCH v2 bpf-next 06/13] bpf: make __reg{32,64}_deduce_bounds logic more robust Andrii Nakryiko
2023-11-12 1:06 ` [PATCH v2 bpf-next 07/13] selftests/bpf: BPF register range bounds tester Andrii Nakryiko
2023-11-13 4:55 ` Shung-Hsi Yu
2023-11-12 1:06 ` [PATCH v2 bpf-next 08/13] selftests/bpf: adjust OP_EQ/OP_NE handling to use subranges for branch taken Andrii Nakryiko
2023-11-13 23:46 ` Eduard Zingerman
2023-11-12 1:06 ` [PATCH v2 bpf-next 09/13] selftests/bpf: add range x range test to reg_bounds Andrii Nakryiko
2023-11-12 1:06 ` [PATCH v2 bpf-next 10/13] selftests/bpf: add randomized reg_bounds tests Andrii Nakryiko
2023-11-19 19:53 ` Alexei Starovoitov
2023-11-12 1:06 ` [PATCH v2 bpf-next 11/13] selftests/bpf: set BPF_F_TEST_SANITY_SCRIPT by default Andrii Nakryiko
2023-11-12 1:06 ` [PATCH v2 bpf-next 12/13] veristat: add ability to set BPF_F_TEST_SANITY_STRICT flag with -r flag Andrii Nakryiko
2023-11-12 1:06 ` [PATCH v2 bpf-next 13/13] selftests/bpf: add iter test requiring range x range logic Andrii Nakryiko
2023-11-15 20:30 ` [PATCH v2 bpf-next 00/13] BPF register bounds range vs range support patchwork-bot+netdevbpf
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=20231112010609.848406-4-andrii@kernel.org \
--to=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=kernel-team@meta.com \
--cc=martin.lau@kernel.org \
--cc=shung-hsi.yu@suse.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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox