From: Cupertino Miranda <cupertino.miranda@oracle.com>
To: bpf@vger.kernel.org
Cc: Cupertino Miranda <cupertino.miranda@oracle.com>,
Yonghong Song <yonghong.song@linux.dev>,
Alexei Starovoitov <alexei.starovoitov@gmail.com>,
David Faust <david.faust@oracle.com>,
Jose Marchesi <jose.marchesi@oracle.com>,
Elena Zannoni <elena.zannoni@oracle.com>
Subject: [PATCH bpf-next v3 2/6] bpf/verifier: refactor checks for range computation
Date: Wed, 24 Apr 2024 23:40:49 +0100 [thread overview]
Message-ID: <20240424224053.471771-3-cupertino.miranda@oracle.com> (raw)
In-Reply-To: <20240424224053.471771-1-cupertino.miranda@oracle.com>
Split range computation checks in its own function, isolating pessimitic
range set for dst_reg and failing return to a single point.
Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Cc: Yonghong Song <yonghong.song@linux.dev>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: David Faust <david.faust@oracle.com>
Cc: Jose Marchesi <jose.marchesi@oracle.com>
Cc: Elena Zannoni <elena.zannoni@oracle.com>
---
kernel/bpf/verifier.c | 141 +++++++++++++++++++++++-------------------
1 file changed, 77 insertions(+), 64 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6fe641c8ae33..829a12d263a5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13695,6 +13695,82 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
__update_reg_bounds(dst_reg);
}
+static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
+ bool *valid)
+{
+ s64 smin_val = reg.smin_value;
+ s64 smax_val = reg.smax_value;
+ u64 umin_val = reg.umin_value;
+ u64 umax_val = reg.umax_value;
+
+ s32 s32_min_val = reg.s32_min_value;
+ s32 s32_max_val = reg.s32_max_value;
+ u32 u32_min_val = reg.u32_min_value;
+ u32 u32_max_val = reg.u32_max_value;
+
+ bool known = alu32 ? tnum_subreg_is_const(reg.var_off) :
+ tnum_is_const(reg.var_off);
+
+ if (alu32) {
+ if ((known &&
+ (s32_min_val != s32_max_val || u32_min_val != u32_max_val)) ||
+ s32_min_val > s32_max_val || u32_min_val > u32_max_val)
+ *valid = false;
+ } else {
+ if ((known &&
+ (smin_val != smax_val || umin_val != umax_val)) ||
+ smin_val > smax_val || umin_val > umax_val)
+ *valid = false;
+ }
+
+ return known;
+}
+
+static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
+ struct bpf_reg_state src_reg)
+{
+ bool src_known;
+ u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
+ bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
+ u8 opcode = BPF_OP(insn->code);
+
+ bool valid_known = true;
+ src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
+
+ /* Taint dst register if offset had invalid bounds
+ * derived from e.g. dead branches.
+ */
+ if (valid_known == false)
+ return false;
+
+ switch (opcode) {
+ case BPF_ADD:
+ case BPF_SUB:
+ case BPF_AND:
+ return true;
+
+ /* Compute range for the following only if the src_reg is known.
+ */
+ case BPF_XOR:
+ case BPF_OR:
+ case BPF_MUL:
+ return src_known;
+
+ /* Shift operators range is only computable if shift dimension operand
+ * is known. Also, shifts greater than 31 or 63 are undefined. This
+ * includes shifts by a negative number.
+ */
+ case BPF_LSH:
+ case BPF_RSH:
+ case BPF_ARSH:
+ return (src_known && src_reg.umax_value < insn_bitness);
+ default:
+ break;
+ }
+
+ return false;
+}
+
/* WARNING: This function does calculations on 64-bit values, but the actual
* execution may occur on 32-bit values. Therefore, things like bitshifts
* need extra checks in the 32-bit case.
@@ -13705,51 +13781,10 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
struct bpf_reg_state src_reg)
{
u8 opcode = BPF_OP(insn->code);
- bool src_known;
- s64 smin_val, smax_val;
- u64 umin_val, umax_val;
- s32 s32_min_val, s32_max_val;
- u32 u32_min_val, u32_max_val;
- u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
int ret;
- smin_val = src_reg.smin_value;
- smax_val = src_reg.smax_value;
- umin_val = src_reg.umin_value;
- umax_val = src_reg.umax_value;
-
- s32_min_val = src_reg.s32_min_value;
- s32_max_val = src_reg.s32_max_value;
- u32_min_val = src_reg.u32_min_value;
- u32_max_val = src_reg.u32_max_value;
-
- if (alu32) {
- src_known = tnum_subreg_is_const(src_reg.var_off);
- if ((src_known &&
- (s32_min_val != s32_max_val || u32_min_val != u32_max_val)) ||
- s32_min_val > s32_max_val || u32_min_val > u32_max_val) {
- /* Taint dst register if offset had invalid bounds
- * derived from e.g. dead branches.
- */
- __mark_reg_unknown(env, dst_reg);
- return 0;
- }
- } else {
- src_known = tnum_is_const(src_reg.var_off);
- if ((src_known &&
- (smin_val != smax_val || umin_val != umax_val)) ||
- smin_val > smax_val || umin_val > umax_val) {
- /* Taint dst register if offset had invalid bounds
- * derived from e.g. dead branches.
- */
- __mark_reg_unknown(env, dst_reg);
- return 0;
- }
- }
-
- if (!src_known &&
- opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
+ if (!is_safe_to_compute_dst_reg_range(insn, src_reg)) {
__mark_reg_unknown(env, dst_reg);
return 0;
}
@@ -13806,46 +13841,24 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
scalar_min_max_xor(dst_reg, &src_reg);
break;
case BPF_LSH:
- if (umax_val >= insn_bitness) {
- /* Shifts greater than 31 or 63 are undefined.
- * This includes shifts by a negative number.
- */
- __mark_reg_unknown(env, dst_reg);
- break;
- }
if (alu32)
scalar32_min_max_lsh(dst_reg, &src_reg);
else
scalar_min_max_lsh(dst_reg, &src_reg);
break;
case BPF_RSH:
- if (umax_val >= insn_bitness) {
- /* Shifts greater than 31 or 63 are undefined.
- * This includes shifts by a negative number.
- */
- __mark_reg_unknown(env, dst_reg);
- break;
- }
if (alu32)
scalar32_min_max_rsh(dst_reg, &src_reg);
else
scalar_min_max_rsh(dst_reg, &src_reg);
break;
case BPF_ARSH:
- if (umax_val >= insn_bitness) {
- /* Shifts greater than 31 or 63 are undefined.
- * This includes shifts by a negative number.
- */
- __mark_reg_unknown(env, dst_reg);
- break;
- }
if (alu32)
scalar32_min_max_arsh(dst_reg, &src_reg);
else
scalar_min_max_arsh(dst_reg, &src_reg);
break;
default:
- __mark_reg_unknown(env, dst_reg);
break;
}
--
2.39.2
next prev parent reply other threads:[~2024-04-24 22:41 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-24 22:40 [PATCH bpf-next v3 0/6] bpf/verifier: range computation improvements Cupertino Miranda
2024-04-24 22:40 ` [PATCH bpf-next v3 1/6] bpf/verifier: replace calls to mark_reg_unknown Cupertino Miranda
2024-04-25 16:56 ` Eduard Zingerman
2024-04-24 22:40 ` Cupertino Miranda [this message]
2024-04-25 18:49 ` [PATCH bpf-next v3 2/6] bpf/verifier: refactor checks for range computation Eduard Zingerman
2024-04-25 23:05 ` Andrii Nakryiko
2024-04-26 10:20 ` Cupertino Miranda
2024-04-26 16:11 ` Andrii Nakryiko
2024-04-26 16:17 ` Alexei Starovoitov
2024-04-27 22:51 ` Cupertino Miranda
2024-04-28 3:22 ` Andrii Nakryiko
2024-04-28 10:56 ` Cupertino Miranda
2024-04-24 22:40 ` [PATCH bpf-next v3 3/6] bpf/verifier: improve XOR and OR " Cupertino Miranda
2024-04-25 18:52 ` Eduard Zingerman
2024-04-24 22:40 ` [PATCH bpf-next v3 4/6] selftests/bpf: XOR and OR range computation tests Cupertino Miranda
2024-04-25 18:59 ` Eduard Zingerman
2024-04-25 23:17 ` Andrii Nakryiko
2024-04-24 22:40 ` [PATCH bpf-next v3 5/6] bpf/verifier: relax MUL range computation check Cupertino Miranda
2024-04-25 19:00 ` Eduard Zingerman
2024-04-25 23:24 ` Andrii Nakryiko
2024-04-24 22:40 ` [PATCH bpf-next v3 6/6] selftests/bpf: MUL range computation tests Cupertino Miranda
2024-04-25 19:02 ` Eduard Zingerman
2024-04-25 23:26 ` Andrii Nakryiko
2024-04-24 22:45 ` [PATCH bpf-next v3 0/6] bpf/verifier: range computation improvements Cupertino Miranda
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=20240424224053.471771-3-cupertino.miranda@oracle.com \
--to=cupertino.miranda@oracle.com \
--cc=alexei.starovoitov@gmail.com \
--cc=bpf@vger.kernel.org \
--cc=david.faust@oracle.com \
--cc=elena.zannoni@oracle.com \
--cc=jose.marchesi@oracle.com \
--cc=yonghong.song@linux.dev \
/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).