From: Sasha Levin <sashal@kernel•org>
To: linux-kernel@vger•kernel.org, stable@vger•kernel.org
Cc: Yonghong Song <yhs@fb•com>, Alexei Starovoitov <ast@kernel•org>,
Sasha Levin <sashal@kernel•org>,
netdev@vger•kernel.org, bpf@vger•kernel.org,
clang-built-linux@googlegroups•com
Subject: [PATCH AUTOSEL 5.4 346/350] bpf: Provide better register bounds after jmp32 instructions
Date: Tue, 10 Dec 2019 16:07:31 -0500 [thread overview]
Message-ID: <20191210210735.9077-307-sashal@kernel.org> (raw)
In-Reply-To: <20191210210735.9077-1-sashal@kernel.org>
From: Yonghong Song <yhs@fb•com>
[ Upstream commit 581738a681b6faae5725c2555439189ca81c0f1f ]
With latest llvm (trunk https://github.com/llvm/llvm-project),
test_progs, which has +alu32 enabled, failed for strobemeta.o.
The verifier output looks like below with edit to replace large
decimal numbers with hex ones.
193: (85) call bpf_probe_read_user_str#114
R0=inv(id=0)
194: (26) if w0 > 0x1 goto pc+4
R0_w=inv(id=0,umax_value=0xffffffff00000001)
195: (6b) *(u16 *)(r7 +80) = r0
196: (bc) w6 = w0
R6_w=inv(id=0,umax_value=0xffffffff,var_off=(0x0; 0xffffffff))
197: (67) r6 <<= 32
R6_w=inv(id=0,smax_value=0x7fffffff00000000,umax_value=0xffffffff00000000,
var_off=(0x0; 0xffffffff00000000))
198: (77) r6 >>= 32
R6=inv(id=0,umax_value=0xffffffff,var_off=(0x0; 0xffffffff))
...
201: (79) r8 = *(u64 *)(r10 -416)
R8_w=map_value(id=0,off=40,ks=4,vs=13872,imm=0)
202: (0f) r8 += r6
R8_w=map_value(id=0,off=40,ks=4,vs=13872,umax_value=0xffffffff,var_off=(0x0; 0xffffffff))
203: (07) r8 += 9696
R8_w=map_value(id=0,off=9736,ks=4,vs=13872,umax_value=0xffffffff,var_off=(0x0; 0xffffffff))
...
255: (bf) r1 = r8
R1_w=map_value(id=0,off=9736,ks=4,vs=13872,umax_value=0xffffffff,var_off=(0x0; 0xffffffff))
...
257: (85) call bpf_probe_read_user_str#114
R1 unbounded memory access, make sure to bounds check any array access into a map
The value range for register r6 at insn 198 should be really just 0/1.
The umax_value=0xffffffff caused later verification failure.
After jmp instructions, the current verifier already tried to use just
obtained information to get better register range. The current mechanism is
for 64bit register only. This patch implemented to tighten the range
for 32bit sub-registers after jmp32 instructions.
With the patch, we have the below range ranges for the
above code sequence:
193: (85) call bpf_probe_read_user_str#114
R0=inv(id=0)
194: (26) if w0 > 0x1 goto pc+4
R0_w=inv(id=0,smax_value=0x7fffffff00000001,umax_value=0xffffffff00000001,
var_off=(0x0; 0xffffffff00000001))
195: (6b) *(u16 *)(r7 +80) = r0
196: (bc) w6 = w0
R6_w=inv(id=0,umax_value=0xffffffff,var_off=(0x0; 0x1))
197: (67) r6 <<= 32
R6_w=inv(id=0,umax_value=0x100000000,var_off=(0x0; 0x100000000))
198: (77) r6 >>= 32
R6=inv(id=0,umax_value=1,var_off=(0x0; 0x1))
...
201: (79) r8 = *(u64 *)(r10 -416)
R8_w=map_value(id=0,off=40,ks=4,vs=13872,imm=0)
202: (0f) r8 += r6
R8_w=map_value(id=0,off=40,ks=4,vs=13872,umax_value=1,var_off=(0x0; 0x1))
203: (07) r8 += 9696
R8_w=map_value(id=0,off=9736,ks=4,vs=13872,umax_value=1,var_off=(0x0; 0x1))
...
255: (bf) r1 = r8
R1_w=map_value(id=0,off=9736,ks=4,vs=13872,umax_value=1,var_off=(0x0; 0x1))
...
257: (85) call bpf_probe_read_user_str#114
...
At insn 194, the register R0 has better var_off.mask and smax_value.
Especially, the var_off.mask ensures later lshift and rshift
maintains proper value range.
Suggested-by: Alexei Starovoitov <ast@kernel•org>
Signed-off-by: Yonghong Song <yhs@fb•com>
Signed-off-by: Alexei Starovoitov <ast@kernel•org>
Link: https://lore.kernel.org/bpf/20191121170650.449030-1-yhs@fb.com
Signed-off-by: Sasha Levin <sashal@kernel•org>
---
kernel/bpf/verifier.c | 19 +++++++++++++++++++
1 file changed, 19 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 87181cd5bafd7..df033c5877cbe 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -978,6 +978,17 @@ static void __reg_bound_offset(struct bpf_reg_state *reg)
reg->umax_value));
}
+static void __reg_bound_offset32(struct bpf_reg_state *reg)
+{
+ u64 mask = 0xffffFFFF;
+ struct tnum range = tnum_range(reg->umin_value & mask,
+ reg->umax_value & mask);
+ struct tnum lo32 = tnum_cast(reg->var_off, 4);
+ struct tnum hi32 = tnum_lshift(tnum_rshift(reg->var_off, 32), 32);
+
+ reg->var_off = tnum_or(hi32, tnum_intersect(lo32, range));
+}
+
/* Reset the min/max bounds of a register */
static void __mark_reg_unbounded(struct bpf_reg_state *reg)
{
@@ -5433,6 +5444,10 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
/* We might have learned some bits from the bounds. */
__reg_bound_offset(false_reg);
__reg_bound_offset(true_reg);
+ if (is_jmp32) {
+ __reg_bound_offset32(false_reg);
+ __reg_bound_offset32(true_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.
@@ -5542,6 +5557,10 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
/* We might have learned some bits from the bounds. */
__reg_bound_offset(false_reg);
__reg_bound_offset(true_reg);
+ if (is_jmp32) {
+ __reg_bound_offset32(false_reg);
+ __reg_bound_offset32(true_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.
--
2.20.1
next prev parent reply other threads:[~2019-12-10 21:14 UTC|newest]
Thread overview: 75+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20191210210735.9077-1-sashal@kernel.org>
2019-12-10 21:02 ` [PATCH AUTOSEL 5.4 048/350] ath10k: fix offchannel tx failure when no ath10k_mac_tx_frm_has_freq Sasha Levin
2019-12-10 21:02 ` [PATCH AUTOSEL 5.4 056/350] selftests/bpf: Correct path to include msg + path Sasha Levin
2019-12-10 21:02 ` [PATCH AUTOSEL 5.4 059/350] rtw88: fix NSS of hw_cap Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 077/350] mwifiex: pcie: Fix memory leak in mwifiex_pcie_init_evt_ring Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 079/350] selftests/bpf: Fix btf_dump padding test case Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 080/350] libbpf: Fix struct end padding in btf_dump Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 081/350] libbpf: Fix passing uninitialized bytes to setsockopt Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 082/350] net/smc: increase device refcount for added link group Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 083/350] team: call RCU read lock when walking the port_list Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 106/350] ath10k: Correct error handling of dma_map_single() Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 107/350] rtw88: coex: Set 4 slot mode for A2DP Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 119/350] Bluetooth: missed cpu_to_le16 conversion in hci_init4_req Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 120/350] Bluetooth: Workaround directed advertising bug in Broadcom controllers Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 121/350] Bluetooth: hci_core: fix init for HCI_USER_CHANNEL Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 123/350] bpf/stackmap: Fix deadlock with rq_lock in bpf_get_stack() Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 132/350] selftests/bpf: Make a copy of subtest name Sasha Levin
2019-12-10 21:03 ` [PATCH AUTOSEL 5.4 134/350] net: hns3: log and clear hardware error after reset complete Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 139/350] rtl8xxxu: fix RTL8723BU connection failure issue after warm reboot Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 161/350] i40e: initialize ITRN registers with correct values Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 163/350] i40e: Wrong 'Advertised FEC modes' after set FEC to AUTO Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 164/350] net: phy: dp83867: enable robust auto-mdix Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 178/350] net: dsa: LAN9303: select REGMAP when LAN9303 enable Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 185/350] net: hns3: add struct netdev_queue debug info for TX timeout Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 189/350] net/mlx5e: Verify that rule has at least one fwd/drop action Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 193/350] libbpf: Fix error handling in bpf_map__reuse_fd() Sasha Levin
2019-12-10 21:04 ` [PATCH AUTOSEL 5.4 194/350] Bluetooth: Fix advertising duplicated flags Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 200/350] ixgbe: protect TX timestamping from API misuse Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 211/350] rfkill: allocate static minor Sasha Levin
2019-12-11 7:51 ` Greg Kroah-Hartman
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 212/350] bnx2x: Fix PF-VF communication over multi-cos queues Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 217/350] rtlwifi: fix memory leak in rtl92c_set_fw_rsvdpagepkt() Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 229/350] perf tools: Splice events onto evlist even on error Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 233/350] ice: Check for null pointer dereference when setting rings Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 235/350] perf parse: If pmu configuration fails free terms Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 237/350] net: avoid potential false sharing in neighbor related code Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 242/350] libbpf: Fix negative FD close() in xsk_setup_xdp_prog() Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 243/350] s390/bpf: Use kvcalloc for addrs array Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 248/350] ath10k: fix get invalid tx rate for Mesh metric Sasha Levin
2019-12-10 21:05 ` [PATCH AUTOSEL 5.4 250/350] selftests: net: Fix printf format warnings on arm Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 255/350] ice: delay less Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 267/350] bpf, testing: Workaround a verifier failure for test_progs Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 270/350] net: dsa: sja1105: Disallow management xmit during switch reset Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 271/350] r8169: respect EEE user setting when restarting network Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 274/350] net: ethernet: ti: Add dependency for TI_DAVINCI_EMAC Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 276/350] net: bcmgenet: Add RGMII_RXID support Sasha Levin
2019-12-10 21:49 ` Florian Fainelli
2019-12-19 22:26 ` Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 281/350] qtnfmac: fix debugfs support for multiple cards Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 282/350] qtnfmac: fix invalid channel information output Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 284/350] qtnfmac: fix using skb after free Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 291/350] iwlwifi: mvm: fix unaligned read of rx_pkt_status Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 295/350] tun: fix data-race in gro_normal_list() Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 306/350] selftests, bpf: Fix test_tc_tunnel hanging Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 307/350] selftests, bpf: Workaround an alu32 sub-register spilling issue Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 308/350] bnxt_en: Return proper error code for non-existent NVM variable Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 309/350] net: phy: avoid matching all-ones clause 45 PHY IDs Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 313/350] net-af_xdp: Use correct number of channels from ethtool Sasha Levin
2019-12-10 21:06 ` [PATCH AUTOSEL 5.4 314/350] brcmfmac: remove monitor interface when detaching Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 319/350] bnxt_en: Improve RX buffer error handling Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 320/350] iwlwifi: check kasprintf() return value Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 323/350] net: ethernet: ti: ale: clean ale tbl on init and intf restart Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 324/350] mt76: fix possible out-of-bound access in mt7615_fill_txs/mt7603_fill_txs Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 326/350] bpf: Switch bpf_map ref counter to atomic64_t so bpf_map_inc() never fails Sasha Levin
2019-12-10 21:28 ` [oss-drivers] " Jakub Kicinski
2019-12-12 16:25 ` Daniel Borkmann
2019-12-19 23:25 ` Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 327/350] libbpf: Fix call relocation offset calculation bug Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 332/350] mac80211: consider QoS Null frames for STA_NULLFUNC_ACKED Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 338/350] ice: Only disable VF state when freeing each VF resources Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 339/350] ice: Fix setting coalesce to handle DCB configuration Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 342/350] net: phy: initialise phydev speed and duplex sanely Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 343/350] tools, bpf: Fix build for 'make -s tools/bpf O=<dir>' Sasha Levin
2019-12-10 21:07 ` Sasha Levin [this message]
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 348/350] ibmvnic: Fix completion structure initialization Sasha Levin
2019-12-10 21:07 ` [PATCH AUTOSEL 5.4 349/350] net: wireless: intel: iwlwifi: fix GRO_NORMAL packet stalling Sasha Levin
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=20191210210735.9077-307-sashal@kernel.org \
--to=sashal@kernel$(echo .)org \
--cc=ast@kernel$(echo .)org \
--cc=bpf@vger$(echo .)kernel.org \
--cc=clang-built-linux@googlegroups$(echo .)com \
--cc=linux-kernel@vger$(echo .)kernel.org \
--cc=netdev@vger$(echo .)kernel.org \
--cc=stable@vger$(echo .)kernel.org \
--cc=yhs@fb$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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