From: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
To: linux-kernel@vger.kernel.org
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
stable@vger.kernel.org, Kuee K1r0a <liulin063@gmail.com>,
Daniel Borkmann <daniel@iogearbox.net>,
Andrii Nakryiko <andrii@kernel.org>,
John Fastabend <john.fastabend@gmail.com>
Subject: [PATCH 5.10 07/55] bpf: Fix insufficient bounds propagation from adjust_scalar_min_max_vals
Date: Mon, 11 Jul 2022 11:06:55 +0200 [thread overview]
Message-ID: <20220711090541.979916069@linuxfoundation.org> (raw)
In-Reply-To: <20220711090541.764895984@linuxfoundation.org>
From: Daniel Borkmann <daniel@iogearbox.net>
commit 3844d153a41adea718202c10ae91dc96b37453b5 upstream.
Kuee reported a corner case where the tnum becomes constant after the call
to __reg_bound_offset(), but the register's bounds are not, that is, its
min bounds are still not equal to the register's max bounds.
This in turn allows to leak pointers through turning a pointer register as
is into an unknown scalar via adjust_ptr_min_max_vals().
Before:
func#0 @0
0: R1=ctx(off=0,imm=0,umax=0,var_off=(0x0; 0x0)) R10=fp(off=0,imm=0,umax=0,var_off=(0x0; 0x0))
0: (b7) r0 = 1 ; R0_w=scalar(imm=1,umin=1,umax=1,var_off=(0x1; 0x0))
1: (b7) r3 = 0 ; R3_w=scalar(imm=0,umax=0,var_off=(0x0; 0x0))
2: (87) r3 = -r3 ; R3_w=scalar()
3: (87) r3 = -r3 ; R3_w=scalar()
4: (47) r3 |= 32767 ; R3_w=scalar(smin=-9223372036854743041,umin=32767,var_off=(0x7fff; 0xffffffffffff8000),s32_min=-2147450881)
5: (75) if r3 s>= 0x0 goto pc+1 ; R3_w=scalar(umin=9223372036854808575,var_off=(0x8000000000007fff; 0x7fffffffffff8000),s32_min=-2147450881,u32_min=32767)
6: (95) exit
from 5 to 7: R0=scalar(imm=1,umin=1,umax=1,var_off=(0x1; 0x0)) R1=ctx(off=0,imm=0,umax=0,var_off=(0x0; 0x0)) R3=scalar(umin=32767,umax=9223372036854775807,var_off=(0x7fff; 0x7fffffffffff8000),s32_min=-2147450881) R10=fp(off=0,imm=0,umax=0,var_off=(0x0; 0x0))
7: (d5) if r3 s<= 0x8000 goto pc+1 ; R3=scalar(umin=32769,umax=9223372036854775807,var_off=(0x7fff; 0x7fffffffffff8000),s32_min=-2147450881,u32_min=32767)
8: (95) exit
from 7 to 9: R0=scalar(imm=1,umin=1,umax=1,var_off=(0x1; 0x0)) R1=ctx(off=0,imm=0,umax=0,var_off=(0x0; 0x0)) R3=scalar(umin=32767,umax=32768,var_off=(0x7fff; 0x8000)) R10=fp(off=0,imm=0,umax=0,var_off=(0x0; 0x0))
9: (07) r3 += -32767 ; R3_w=scalar(imm=0,umax=1,var_off=(0x0; 0x0)) <--- [*]
10: (95) exit
What can be seen here is that R3=scalar(umin=32767,umax=32768,var_off=(0x7fff;
0x8000)) after the operation R3 += -32767 results in a 'malformed' constant, that
is, R3_w=scalar(imm=0,umax=1,var_off=(0x0; 0x0)). Intersecting with var_off has
not been done at that point via __update_reg_bounds(), which would have improved
the umax to be equal to umin.
Refactor the tnum <> min/max bounds information flow into a reg_bounds_sync()
helper and use it consistently everywhere. After the fix, bounds have been
corrected to R3_w=scalar(imm=0,umax=0,var_off=(0x0; 0x0)) and thus the register
is regarded as a 'proper' constant scalar of 0.
After:
func#0 @0
0: R1=ctx(off=0,imm=0,umax=0,var_off=(0x0; 0x0)) R10=fp(off=0,imm=0,umax=0,var_off=(0x0; 0x0))
0: (b7) r0 = 1 ; R0_w=scalar(imm=1,umin=1,umax=1,var_off=(0x1; 0x0))
1: (b7) r3 = 0 ; R3_w=scalar(imm=0,umax=0,var_off=(0x0; 0x0))
2: (87) r3 = -r3 ; R3_w=scalar()
3: (87) r3 = -r3 ; R3_w=scalar()
4: (47) r3 |= 32767 ; R3_w=scalar(smin=-9223372036854743041,umin=32767,var_off=(0x7fff; 0xffffffffffff8000),s32_min=-2147450881)
5: (75) if r3 s>= 0x0 goto pc+1 ; R3_w=scalar(umin=9223372036854808575,var_off=(0x8000000000007fff; 0x7fffffffffff8000),s32_min=-2147450881,u32_min=32767)
6: (95) exit
from 5 to 7: R0=scalar(imm=1,umin=1,umax=1,var_off=(0x1; 0x0)) R1=ctx(off=0,imm=0,umax=0,var_off=(0x0; 0x0)) R3=scalar(umin=32767,umax=9223372036854775807,var_off=(0x7fff; 0x7fffffffffff8000),s32_min=-2147450881) R10=fp(off=0,imm=0,umax=0,var_off=(0x0; 0x0))
7: (d5) if r3 s<= 0x8000 goto pc+1 ; R3=scalar(umin=32769,umax=9223372036854775807,var_off=(0x7fff; 0x7fffffffffff8000),s32_min=-2147450881,u32_min=32767)
8: (95) exit
from 7 to 9: R0=scalar(imm=1,umin=1,umax=1,var_off=(0x1; 0x0)) R1=ctx(off=0,imm=0,umax=0,var_off=(0x0; 0x0)) R3=scalar(umin=32767,umax=32768,var_off=(0x7fff; 0x8000)) R10=fp(off=0,imm=0,umax=0,var_off=(0x0; 0x0))
9: (07) r3 += -32767 ; R3_w=scalar(imm=0,umax=0,var_off=(0x0; 0x0)) <--- [*]
10: (95) exit
Fixes: b03c9f9fdc37 ("bpf/verifier: track signed and unsigned min/max values")
Reported-by: Kuee K1r0a <liulin063@gmail.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
Acked-by: John Fastabend <john.fastabend@gmail.com>
Link: https://lore.kernel.org/bpf/20220701124727.11153-2-daniel@iogearbox.net
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---
kernel/bpf/verifier.c | 72 +++++++++++++++-----------------------------------
1 file changed, 23 insertions(+), 49 deletions(-)
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1249,6 +1249,21 @@ static void __reg_bound_offset(struct bp
reg->var_off = tnum_or(tnum_clear_subreg(var64_off), var32_off);
}
+static void reg_bounds_sync(struct bpf_reg_state *reg)
+{
+ /* We might have learned new bounds from the var_off. */
+ __update_reg_bounds(reg);
+ /* We might have learned something about the sign bit. */
+ __reg_deduce_bounds(reg);
+ /* We might have learned some bits from the bounds. */
+ __reg_bound_offset(reg);
+ /* Intersecting with the old var_off might have improved our bounds
+ * slightly, e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc),
+ * then new var_off is (0; 0x7f...fc) which improves our umax.
+ */
+ __update_reg_bounds(reg);
+}
+
static bool __reg32_bound_s64(s32 a)
{
return a >= 0 && a <= S32_MAX;
@@ -1290,16 +1305,8 @@ static void __reg_combine_32_into_64(str
* so they do not impact tnum bounds calculation.
*/
__mark_reg64_unbounded(reg);
- __update_reg_bounds(reg);
}
-
- /* Intersecting with the old var_off might have improved our bounds
- * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc),
- * then new var_off is (0; 0x7f...fc) which improves our umax.
- */
- __reg_deduce_bounds(reg);
- __reg_bound_offset(reg);
- __update_reg_bounds(reg);
+ reg_bounds_sync(reg);
}
static bool __reg64_bound_s32(s64 a)
@@ -1315,7 +1322,6 @@ static bool __reg64_bound_u32(u64 a)
static void __reg_combine_64_into_32(struct bpf_reg_state *reg)
{
__mark_reg32_unbounded(reg);
-
if (__reg64_bound_s32(reg->smin_value) && __reg64_bound_s32(reg->smax_value)) {
reg->s32_min_value = (s32)reg->smin_value;
reg->s32_max_value = (s32)reg->smax_value;
@@ -1324,14 +1330,7 @@ static void __reg_combine_64_into_32(str
reg->u32_min_value = (u32)reg->umin_value;
reg->u32_max_value = (u32)reg->umax_value;
}
-
- /* Intersecting with the old var_off might have improved our bounds
- * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc),
- * then new var_off is (0; 0x7f...fc) which improves our umax.
- */
- __reg_deduce_bounds(reg);
- __reg_bound_offset(reg);
- __update_reg_bounds(reg);
+ reg_bounds_sync(reg);
}
/* Mark a register as having a completely unknown (scalar) value. */
@@ -5230,9 +5229,7 @@ static void do_refine_retval_range(struc
ret_reg->s32_max_value = meta->msize_max_value;
ret_reg->smin_value = -MAX_ERRNO;
ret_reg->s32_min_value = -MAX_ERRNO;
- __reg_deduce_bounds(ret_reg);
- __reg_bound_offset(ret_reg);
- __update_reg_bounds(ret_reg);
+ reg_bounds_sync(ret_reg);
}
static int
@@ -6197,11 +6194,7 @@ reject:
if (!check_reg_sane_offset(env, dst_reg, ptr_reg->type))
return -EINVAL;
-
- __update_reg_bounds(dst_reg);
- __reg_deduce_bounds(dst_reg);
- __reg_bound_offset(dst_reg);
-
+ reg_bounds_sync(dst_reg);
if (sanitize_check_bounds(env, insn, dst_reg) < 0)
return -EACCES;
if (sanitize_needed(opcode)) {
@@ -6939,10 +6932,7 @@ static int adjust_scalar_min_max_vals(st
/* ALU32 ops are zero extended into 64bit register */
if (alu32)
zext_32_to_64(dst_reg);
-
- __update_reg_bounds(dst_reg);
- __reg_deduce_bounds(dst_reg);
- __reg_bound_offset(dst_reg);
+ reg_bounds_sync(dst_reg);
return 0;
}
@@ -7131,10 +7121,7 @@ static int check_alu_op(struct bpf_verif
insn->dst_reg);
}
zext_32_to_64(dst_reg);
-
- __update_reg_bounds(dst_reg);
- __reg_deduce_bounds(dst_reg);
- __reg_bound_offset(dst_reg);
+ reg_bounds_sync(dst_reg);
}
} else {
/* case: R = imm
@@ -7693,21 +7680,8 @@ static void __reg_combine_min_max(struct
dst_reg->smax_value);
src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off,
dst_reg->var_off);
- /* We might have learned new bounds from the var_off. */
- __update_reg_bounds(src_reg);
- __update_reg_bounds(dst_reg);
- /* We might have learned something about the sign bit. */
- __reg_deduce_bounds(src_reg);
- __reg_deduce_bounds(dst_reg);
- /* We might have learned some bits from the bounds. */
- __reg_bound_offset(src_reg);
- __reg_bound_offset(dst_reg);
- /* Intersecting with the old var_off might have improved our bounds
- * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc),
- * then new var_off is (0; 0x7f...fc) which improves our umax.
- */
- __update_reg_bounds(src_reg);
- __update_reg_bounds(dst_reg);
+ reg_bounds_sync(src_reg);
+ reg_bounds_sync(dst_reg);
}
static void reg_combine_min_max(struct bpf_reg_state *true_src,
next prev parent reply other threads:[~2022-07-11 9:20 UTC|newest]
Thread overview: 62+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-11 9:06 [PATCH 5.10 00/55] 5.10.130-rc1 review Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 01/55] mm/slub: add missing TID updates on slab deactivation Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 02/55] ALSA: hda/realtek: Add quirk for Clevo L140PU Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 03/55] can: bcm: use call_rcu() instead of costly synchronize_rcu() Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 04/55] can: grcan: grcan_probe(): remove extra of_node_get() Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 05/55] can: gs_usb: gs_usb_open/close(): fix memory leak Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 06/55] bpf: Fix incorrect verifier simulation around jmp32s jeq/jne Greg Kroah-Hartman
2022-07-11 9:06 ` Greg Kroah-Hartman [this message]
2022-07-11 9:06 ` [PATCH 5.10 08/55] usbnet: fix memory leak in error case Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 09/55] net: rose: fix UAF bug caused by rose_t0timer_expiry Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 10/55] netfilter: nft_set_pipapo: release elements in clone from abort path Greg Kroah-Hartman
2022-07-11 9:06 ` [PATCH 5.10 11/55] netfilter: nf_tables: stricter validation of element data Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 12/55] iommu/vt-d: Fix PCI bus rescan device hot add Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 13/55] fbdev: fbmem: Fix logo center image dx issue Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 14/55] fbmem: Check virtual screen sizes in fb_set_var() Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 15/55] fbcon: Disallow setting font bigger than screen size Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 16/55] fbcon: Prevent that screen size is smaller than font size Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 17/55] PM: runtime: Redefine pm_runtime_release_supplier() Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 18/55] memregion: Fix memregion_free() fallback definition Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 19/55] video: of_display_timing.h: include errno.h Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 20/55] powerpc/powernv: delay rng platform device creation until later in boot Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 21/55] can: kvaser_usb: replace run-time checks with struct kvaser_usb_driver_info Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 22/55] can: kvaser_usb: kvaser_usb_leaf: fix CAN clock frequency regression Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 23/55] can: kvaser_usb: kvaser_usb_leaf: fix bittiming limits Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 24/55] xfs: remove incorrect ASSERT in xfs_rename Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 25/55] ARM: meson: Fix refcount leak in meson_smp_prepare_cpus Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 26/55] pinctrl: sunxi: a83t: Fix NAND function name for some pins Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 27/55] arm64: dts: qcom: msm8994: Fix CPU6/7 reg values Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 28/55] arm64: dts: imx8mp-evk: correct mmc pad settings Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 29/55] arm64: dts: imx8mp-evk: correct the uart2 pinctl value Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 30/55] arm64: dts: imx8mp-evk: correct gpio-led pad settings Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 31/55] arm64: dts: imx8mp-evk: correct I2C3 " Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 32/55] pinctrl: sunxi: sunxi_pconf_set: use correct offset Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 33/55] arm64: dts: qcom: msm8992-*: Fix vdd_lvs1_2-supply typo Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 34/55] ARM: at91: pm: use proper compatible for sama5d2s rtc Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 35/55] ARM: at91: pm: use proper compatibles for sam9x60s rtc and rtt Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 36/55] ARM: dts: at91: sam9x60ek: fix eeprom compatible and size Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 37/55] ARM: dts: at91: sama5d2_icp: fix eeprom compatibles Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 38/55] xsk: Clear page contiguity bit when unmapping pool Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 39/55] i40e: Fix dropped jumbo frames statistics Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 40/55] ibmvnic: Properly dispose of all skbs during a failover Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 41/55] selftests: forwarding: fix flood_unicast_test when h2 supports IFF_UNICAST_FLT Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 42/55] selftests: forwarding: fix learning_test when h1 " Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 43/55] selftests: forwarding: fix error message in learning_test Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 44/55] r8169: fix accessing unset transport header Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 45/55] i2c: cadence: Unregister the clk notifier in error path Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 46/55] dmaengine: imx-sdma: Allow imx8m for imx7 FW revs Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 47/55] misc: rtsx_usb: fix use of dma mapped buffer for usb bulk transfer Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 48/55] misc: rtsx_usb: use separate command and response buffers Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 49/55] misc: rtsx_usb: set return value in rsp_buf alloc err path Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 50/55] dt-bindings: dma: allwinner,sun50i-a64-dma: Fix min/max typo Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 51/55] ida: dont use BUG_ON() for debugging Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 52/55] dmaengine: pl330: Fix lockdep warning about non-static key Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 53/55] dmaengine: at_xdma: handle errors of at_xdmac_alloc_desc() correctly Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 54/55] dmaengine: ti: Fix refcount leak in ti_dra7_xbar_route_allocate Greg Kroah-Hartman
2022-07-11 9:07 ` [PATCH 5.10 55/55] dmaengine: ti: Add missing put_device " Greg Kroah-Hartman
2022-07-11 11:06 ` [PATCH 5.10 00/55] 5.10.130-rc1 review Pavel Machek
2022-07-11 18:20 ` Florian Fainelli
2022-07-12 1:12 ` Guenter Roeck
2022-07-12 2:39 ` Shuah Khan
2022-07-12 4:00 ` Naresh Kamboju
2022-07-12 14:44 ` Sudip Mukherjee (Codethink)
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=20220711090541.979916069@linuxfoundation.org \
--to=gregkh@linuxfoundation.org \
--cc=andrii@kernel.org \
--cc=daniel@iogearbox.net \
--cc=john.fastabend@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=liulin063@gmail.com \
--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