From: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
To: linux-kernel@vger.kernel.org
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
stable@vger.kernel.org, Jann Horn <jannh@google.com>,
Daniel Borkmann <daniel@iogearbox.net>,
Alexei Starovoitov <ast@kernel.org>,
Sasha Levin <sashal@kernel.org>
Subject: [PATCH 5.4 10/36] bpf: Fix tnum constraints for 32-bit comparisons
Date: Tue, 7 Apr 2020 12:21:43 +0200 [thread overview]
Message-ID: <20200407101455.655552813@linuxfoundation.org> (raw)
In-Reply-To: <20200407101454.281052964@linuxfoundation.org>
From: Jann Horn <jannh@google.com>
[ Upstream commit 604dca5e3af1db98bd123b7bfc02b017af99e3a0 ]
The BPF verifier tried to track values based on 32-bit comparisons by
(ab)using the tnum state via 581738a681b6 ("bpf: Provide better register
bounds after jmp32 instructions"). The idea is that after a check like
this:
if ((u32)r0 > 3)
exit
We can't meaningfully constrain the arithmetic-range-based tracking, but
we can update the tnum state to (value=0,mask=0xffff'ffff'0000'0003).
However, the implementation from 581738a681b6 didn't compute the tnum
constraint based on the fixed operand, but instead derives it from the
arithmetic-range-based tracking. This means that after the following
sequence of operations:
if (r0 >= 0x1'0000'0001)
exit
if ((u32)r0 > 7)
exit
The verifier assumed that the lower half of r0 is in the range (0, 0)
and apply the tnum constraint (value=0,mask=0xffff'ffff'0000'0000) thus
causing the overall tnum to be (value=0,mask=0x1'0000'0000), which was
incorrect. Provide a fixed implementation.
Fixes: 581738a681b6 ("bpf: Provide better register bounds after jmp32 instructions")
Signed-off-by: Jann Horn <jannh@google.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/20200330160324.15259-3-daniel@iogearbox.net
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++--------------
1 file changed, 72 insertions(+), 36 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a0b76b360d6f7..013780ef0bd7d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5325,6 +5325,70 @@ static bool cmp_val_with_extended_s64(s64 sval, struct bpf_reg_state *reg)
reg->smax_value <= 0 && reg->smin_value >= S32_MIN);
}
+/* Constrain the possible values of @reg with unsigned upper bound @bound.
+ * If @is_exclusive, @bound is an exclusive limit, otherwise it is inclusive.
+ * If @is_jmp32, @bound is a 32-bit value that only constrains the low 32 bits
+ * of @reg.
+ */
+static void set_upper_bound(struct bpf_reg_state *reg, u64 bound, bool is_jmp32,
+ bool is_exclusive)
+{
+ if (is_exclusive) {
+ /* There are no values for `reg` that make `reg<0` true. */
+ if (bound == 0)
+ return;
+ bound--;
+ }
+ if (is_jmp32) {
+ /* Constrain the register's value in the tnum representation.
+ * For 64-bit comparisons this happens later in
+ * __reg_bound_offset(), but for 32-bit comparisons, we can be
+ * more precise than what can be derived from the updated
+ * numeric bounds.
+ */
+ struct tnum t = tnum_range(0, bound);
+
+ t.mask |= ~0xffffffffULL; /* upper half is unknown */
+ reg->var_off = tnum_intersect(reg->var_off, t);
+
+ /* Compute the 64-bit bound from the 32-bit bound. */
+ bound += gen_hi_max(reg->var_off);
+ }
+ reg->umax_value = min(reg->umax_value, bound);
+}
+
+/* Constrain the possible values of @reg with unsigned lower bound @bound.
+ * If @is_exclusive, @bound is an exclusive limit, otherwise it is inclusive.
+ * If @is_jmp32, @bound is a 32-bit value that only constrains the low 32 bits
+ * of @reg.
+ */
+static void set_lower_bound(struct bpf_reg_state *reg, u64 bound, bool is_jmp32,
+ bool is_exclusive)
+{
+ if (is_exclusive) {
+ /* There are no values for `reg` that make `reg>MAX` true. */
+ if (bound == (is_jmp32 ? U32_MAX : U64_MAX))
+ return;
+ bound++;
+ }
+ if (is_jmp32) {
+ /* Constrain the register's value in the tnum representation.
+ * For 64-bit comparisons this happens later in
+ * __reg_bound_offset(), but for 32-bit comparisons, we can be
+ * more precise than what can be derived from the updated
+ * numeric bounds.
+ */
+ struct tnum t = tnum_range(bound, U32_MAX);
+
+ t.mask |= ~0xffffffffULL; /* upper half is unknown */
+ reg->var_off = tnum_intersect(reg->var_off, t);
+
+ /* Compute the 64-bit bound from the 32-bit bound. */
+ bound += gen_hi_min(reg->var_off);
+ }
+ reg->umin_value = max(reg->umin_value, bound);
+}
+
/* Adjusts the register min/max values in the case that the dst_reg is the
* variable register that we are working on, and src_reg is a constant or we're
* simply doing a BPF_K check.
@@ -5380,15 +5444,8 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
case BPF_JGE:
case BPF_JGT:
{
- u64 false_umax = opcode == BPF_JGT ? val : val - 1;
- u64 true_umin = opcode == BPF_JGT ? val + 1 : val;
-
- if (is_jmp32) {
- false_umax += gen_hi_max(false_reg->var_off);
- true_umin += gen_hi_min(true_reg->var_off);
- }
- false_reg->umax_value = min(false_reg->umax_value, false_umax);
- true_reg->umin_value = max(true_reg->umin_value, true_umin);
+ set_upper_bound(false_reg, val, is_jmp32, opcode == BPF_JGE);
+ set_lower_bound(true_reg, val, is_jmp32, opcode == BPF_JGT);
break;
}
case BPF_JSGE:
@@ -5409,15 +5466,8 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
case BPF_JLE:
case BPF_JLT:
{
- u64 false_umin = opcode == BPF_JLT ? val : val + 1;
- u64 true_umax = opcode == BPF_JLT ? val - 1 : val;
-
- if (is_jmp32) {
- false_umin += gen_hi_min(false_reg->var_off);
- true_umax += gen_hi_max(true_reg->var_off);
- }
- false_reg->umin_value = max(false_reg->umin_value, false_umin);
- true_reg->umax_value = min(true_reg->umax_value, true_umax);
+ set_lower_bound(false_reg, val, is_jmp32, opcode == BPF_JLE);
+ set_upper_bound(true_reg, val, is_jmp32, opcode == BPF_JLT);
break;
}
case BPF_JSLE:
@@ -5492,15 +5542,8 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
case BPF_JGE:
case BPF_JGT:
{
- u64 false_umin = opcode == BPF_JGT ? val : val + 1;
- u64 true_umax = opcode == BPF_JGT ? val - 1 : val;
-
- if (is_jmp32) {
- false_umin += gen_hi_min(false_reg->var_off);
- true_umax += gen_hi_max(true_reg->var_off);
- }
- false_reg->umin_value = max(false_reg->umin_value, false_umin);
- true_reg->umax_value = min(true_reg->umax_value, true_umax);
+ set_lower_bound(false_reg, val, is_jmp32, opcode == BPF_JGE);
+ set_upper_bound(true_reg, val, is_jmp32, opcode == BPF_JGT);
break;
}
case BPF_JSGE:
@@ -5518,15 +5561,8 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
case BPF_JLE:
case BPF_JLT:
{
- u64 false_umax = opcode == BPF_JLT ? val : val - 1;
- u64 true_umin = opcode == BPF_JLT ? val + 1 : val;
-
- if (is_jmp32) {
- false_umax += gen_hi_max(false_reg->var_off);
- true_umin += gen_hi_min(true_reg->var_off);
- }
- false_reg->umax_value = min(false_reg->umax_value, false_umax);
- true_reg->umin_value = max(true_reg->umin_value, true_umin);
+ set_upper_bound(false_reg, val, is_jmp32, opcode == BPF_JLE);
+ set_lower_bound(true_reg, val, is_jmp32, opcode == BPF_JLT);
break;
}
case BPF_JSLE:
--
2.20.1
next prev parent reply other threads:[~2020-04-07 10:23 UTC|newest]
Thread overview: 40+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-04-07 10:21 [PATCH 5.4 00/36] 5.4.31-rc1 review Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 01/36] nvme-rdma: Avoid double freeing of async event data Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 02/36] kconfig: introduce m32-flag and m64-flag Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 03/36] drm/amd/display: Add link_rate quirk for Apple 15" MBP 2017 Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 04/36] drm/bochs: downgrade pci_request_region failure from error to warning Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 05/36] initramfs: restore default compression behavior Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 06/36] drm/amdgpu: fix typo for vcn1 idle check Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 07/36] tools/power turbostat: Fix gcc build warnings Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 08/36] tools/power turbostat: Fix missing SYS_LPI counter on some Chromebooks Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 09/36] tools/power turbostat: Fix 32-bit capabilities warning Greg Kroah-Hartman
2020-04-07 10:21 ` Greg Kroah-Hartman [this message]
2020-04-07 10:45 ` [PATCH 5.4 10/36] bpf: Fix tnum constraints for 32-bit comparisons Daniel Borkmann
2020-04-07 14:42 ` Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 11/36] net/mlx5e: kTLS, Fix TCP seq off-by-1 issue in TX resync flow Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 12/36] XArray: Fix xa_find_next for large multi-index entries Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 13/36] padata: fix uninitialized return value in padata_replace() Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 14/36] brcmfmac: abort and release host after error Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 15/36] misc: rtsx: set correct pcr_ops for rts522A Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 16/36] misc: pci_endpoint_test: Fix to support > 10 pci-endpoint-test devices Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 17/36] misc: pci_endpoint_test: Avoid using module parameter to determine irqtype Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 18/36] PCI: sysfs: Revert "rescan" file renames Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 19/36] coresight: do not use the BIT() macro in the UAPI header Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 20/36] mei: me: add cedar fork device ids Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 21/36] nvmem: check for NULL reg_read and reg_write before dereferencing Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 22/36] extcon: axp288: Add wakeup support Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 23/36] power: supply: axp288_charger: Add special handling for HP Pavilion x2 10 Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 24/36] Revert "dm: always call blk_queue_split() in dm_process_bio()" Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 25/36] ALSA: hda/ca0132 - Add Recon3Di quirk to handle integrated sound on EVGA X99 Classified motherboard Greg Kroah-Hartman
2020-04-07 10:21 ` [PATCH 5.4 26/36] soc: mediatek: knows_txdone needs to be set in Mediatek CMDQ helper Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 27/36] net/mlx5e: kTLS, Fix wrong value in record tracker enum Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 28/36] iwlwifi: consider HE capability when setting LDPC Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 29/36] iwlwifi: yoyo: dont add TLV offset when reading FIFOs Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 30/36] iwlwifi: dbg: dont abort if sending DBGC_SUSPEND_RESUME fails Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 31/36] rxrpc: Fix sendmsg(MSG_WAITALL) handling Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 32/36] IB/hfi1: Ensure pq is not left on waitlist Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 33/36] tcp: fix TFO SYNACK undo to avoid double-timestamp-undo Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 34/36] i2c: i801: Do not add ICH_RES_IO_SMI for the iTCO_wdt device Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 35/36] net: Fix Tx hash bound checking Greg Kroah-Hartman
2020-04-07 10:22 ` [PATCH 5.4 36/36] padata: always acquire cpu_hotplug_lock before pinst->lock Greg Kroah-Hartman
2020-04-07 12:37 ` [PATCH 5.4 00/36] 5.4.31-rc1 review Jon Hunter
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=20200407101455.655552813@linuxfoundation.org \
--to=gregkh@linuxfoundation.org \
--cc=ast@kernel.org \
--cc=daniel@iogearbox.net \
--cc=jannh@google.com \
--cc=linux-kernel@vger.kernel.org \
--cc=sashal@kernel.org \
--cc=stable@vger.kernel.org \
/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;
as well as URLs for NNTP newsgroup(s).