* [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation
2024-04-17 12:23 [PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements Cupertino Miranda
@ 2024-04-17 12:23 ` Cupertino Miranda
2024-04-18 22:37 ` Eduard Zingerman
2024-04-17 12:23 ` [PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR " Cupertino Miranda
` (3 subsequent siblings)
4 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-17 12:23 UTC (permalink / raw)
To: bpf
Cc: Cupertino Miranda, Yonghong Song, Alexei Starovoitov,
David Faust, Elena Zannoni
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 | 155 +++++++++++++++++++++++++-----------------
1 file changed, 92 insertions(+), 63 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8e7b6072e3f4..0aa6580af7a2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13395,6 +13395,90 @@ 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;
+}
+
+enum {
+ COMPUTABLE_RANGE = 1,
+ UNCOMPUTABLE_RANGE = 0,
+ UNDEFINED_BEHAVIOUR = -1,
+};
+
+static int 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 UNCOMPUTABLE_RANGE;
+
+ switch (opcode) {
+ case BPF_ADD:
+ case BPF_SUB:
+ case BPF_AND:
+ return COMPUTABLE_RANGE;
+
+ /* Compute range for the following only if the src_reg is known.
+ */
+ case BPF_XOR:
+ case BPF_OR:
+ case BPF_MUL:
+ return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
+
+ /* 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:
+ if (src_reg.umax_value >= insn_bitness)
+ return UNDEFINED_BEHAVIOUR;
+ return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
+ default:
+ break;
+ }
+
+ return UNCOMPUTABLE_RANGE;
+}
+
/* 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.
@@ -13406,53 +13490,19 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
{
struct bpf_reg_state *regs = cur_regs(env);
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) {
+ int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
+ switch (is_safe) {
+ case UNCOMPUTABLE_RANGE:
__mark_reg_unknown(env, dst_reg);
return 0;
+ case UNDEFINED_BEHAVIOUR:
+ mark_reg_unknown(env, regs, insn->dst_reg);
+ return 0;
+ default:
+ break;
}
if (sanitize_needed(opcode)) {
@@ -13507,39 +13557,18 @@ 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, regs, insn->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, regs, insn->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, regs, insn->dst_reg);
- break;
- }
if (alu32)
scalar32_min_max_arsh(dst_reg, &src_reg);
else
--
2.39.2
^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation
2024-04-17 12:23 ` [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation Cupertino Miranda
@ 2024-04-18 22:37 ` Eduard Zingerman
2024-04-19 9:37 ` Cupertino Miranda
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-18 22:37 UTC (permalink / raw)
To: Cupertino Miranda, bpf
Cc: Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
[...]
> @@ -13406,53 +13490,19 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
[...]
> - if (!src_known &&
> - opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> + int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
> + switch (is_safe) {
> + case UNCOMPUTABLE_RANGE:
> __mark_reg_unknown(env, dst_reg);
> return 0;
> + case UNDEFINED_BEHAVIOUR:
> + mark_reg_unknown(env, regs, insn->dst_reg);
> + return 0;
> + default:
> + break;
> }
Nit: I know that the division between __mark_reg_unknown() and
mark_reg_unknown() was asked for directly, but tbh I don't think that
it adds any value here, here is how mark_reg_unknown() is implemented:
static void mark_reg_unknown(struct bpf_verifier_env *env,
struct bpf_reg_state *regs, u32 regno)
{
if (WARN_ON(regno >= MAX_BPF_REG)) {
... mark all regs not init ...
return;
}
__mark_reg_unknown(env, regs + regno);
}
The 'regno >= MAX_BPF_REG' does not apply here, because
adjust_scalar_min_max_vals() is only called from the following stack:
- check_alu_op
- adjust_reg_min_max_vals
- adjust_scalar_min_max_vals
The check_alu_op() does check_reg_arg() which verifies that both src
and dst register numbers are within bounds.
I suggest to replace the enum with as boolean value.
Miranda, Yonhong, what do you think?
[...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation
2024-04-18 22:37 ` Eduard Zingerman
@ 2024-04-19 9:37 ` Cupertino Miranda
2024-04-19 17:38 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-19 9:37 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
Eduard Zingerman writes:
> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
> [...]
>
>> @@ -13406,53 +13490,19 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>
> [...]
>
>> - if (!src_known &&
>> - opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>> + int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
>> + switch (is_safe) {
>> + case UNCOMPUTABLE_RANGE:
>> __mark_reg_unknown(env, dst_reg);
>> return 0;
>> + case UNDEFINED_BEHAVIOUR:
>> + mark_reg_unknown(env, regs, insn->dst_reg);
>> + return 0;
>> + default:
>> + break;
>> }
>
> Nit: I know that the division between __mark_reg_unknown() and
> mark_reg_unknown() was asked for directly, but tbh I don't think that
> it adds any value here, here is how mark_reg_unknown() is implemented:
>
> static void mark_reg_unknown(struct bpf_verifier_env *env,
> struct bpf_reg_state *regs, u32 regno)
> {
> if (WARN_ON(regno >= MAX_BPF_REG)) {
> ... mark all regs not init ...
> return;
> }
> __mark_reg_unknown(env, regs + regno);
> }
>
> The 'regno >= MAX_BPF_REG' does not apply here, because
> adjust_scalar_min_max_vals() is only called from the following stack:
> - check_alu_op
> - adjust_reg_min_max_vals
> - adjust_scalar_min_max_vals
>
> The check_alu_op() does check_reg_arg() which verifies that both src
> and dst register numbers are within bounds.
>
> I suggest to replace the enum with as boolean value.
> Miranda, Yonhong, what do you think?
Thanks for the detailed review.
Well, honestly I could not evaluate if there was any actual difference
between the approaches. Although I can understand range computation in
isolation of an instruction I still did not explore the code in the
global perspective, for example the handling of control-flow.
I was proud of the initial boolean implementation that was very clean
and simple, although like Yonghong said, not truly a refactor.
If everyone agrees that it is Ok, I will be happy to change it back.
>
> [...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation
2024-04-19 9:37 ` Cupertino Miranda
@ 2024-04-19 17:38 ` Eduard Zingerman
2024-04-23 19:28 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-19 17:38 UTC (permalink / raw)
To: Cupertino Miranda
Cc: bpf, Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Fri, 2024-04-19 at 10:37 +0100, Cupertino Miranda wrote:
[...]
> I was proud of the initial boolean implementation that was very clean
> and simple, although like Yonghong said, not truly a refactor.
> If everyone agrees that it is Ok, I will be happy to change it back.
Yes, I liked it more than v2 as well :)
Let's wait and see what Yonghong would say.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation
2024-04-19 17:38 ` Eduard Zingerman
@ 2024-04-23 19:28 ` Eduard Zingerman
2024-04-23 19:36 ` Cupertino Miranda
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-23 19:28 UTC (permalink / raw)
To: Cupertino Miranda
Cc: bpf, Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Fri, 2024-04-19 at 10:37 +0100, Cupertino Miranda wrote:
[...]
> I was proud of the initial boolean implementation that was very clean
> and simple, although like Yonghong said, not truly a refactor.
> If everyone agrees that it is Ok, I will be happy to change it back.
Hi Miranda,
I've talked to Yonghong today, he is ok with removing distinction between
__mark_reg_unknown and mark_reg_unknown, but he asks to first make a patch,
that replaces the use of mark_reg_unknown() by __mark_reg_unknown().
So that the follow-up refactoring patch would not change any behaviour.
What do you think?
Best regards,
Eduard
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation
2024-04-23 19:28 ` Eduard Zingerman
@ 2024-04-23 19:36 ` Cupertino Miranda
2024-04-23 19:37 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-23 19:36 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
Eduard Zingerman writes:
> On Fri, 2024-04-19 at 10:37 +0100, Cupertino Miranda wrote:
>
> [...]
>
>> I was proud of the initial boolean implementation that was very clean
>> and simple, although like Yonghong said, not truly a refactor.
>> If everyone agrees that it is Ok, I will be happy to change it back.
>
> Hi Miranda,
>
> I've talked to Yonghong today, he is ok with removing distinction between
> __mark_reg_unknown and mark_reg_unknown, but he asks to first make a patch,
> that replaces the use of mark_reg_unknown() by __mark_reg_unknown().
> So that the follow-up refactoring patch would not change any behaviour.
> What do you think?
Sure, I will prepare it. I presure the patch should be the first in the
series.
Thanks,
Cupertino
>
> Best regards,
> Eduard
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR range computation
2024-04-17 12:23 [PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements Cupertino Miranda
2024-04-17 12:23 ` [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation Cupertino Miranda
@ 2024-04-17 12:23 ` Cupertino Miranda
2024-04-18 23:57 ` Eduard Zingerman
2024-04-17 12:23 ` [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests Cupertino Miranda
` (2 subsequent siblings)
4 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-17 12:23 UTC (permalink / raw)
To: bpf
Cc: Cupertino Miranda, Yonghong Song, Alexei Starovoitov,
David Faust, Elena Zannoni
Range for XOR and OR operators would not be attempted unless src_reg
would resolve to a single value, i.e. a known constant value.
This condition is unnecessary, and the following XOR/OR operator
handling could compute a possible better range.
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 | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0aa6580af7a2..f410eb027e25 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13453,12 +13453,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
case BPF_ADD:
case BPF_SUB:
case BPF_AND:
+ case BPF_XOR:
+ case BPF_OR:
return COMPUTABLE_RANGE;
/* Compute range for the following only if the src_reg is known.
*/
- case BPF_XOR:
- case BPF_OR:
case BPF_MUL:
return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
--
2.39.2
^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR range computation
2024-04-17 12:23 ` [PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR " Cupertino Miranda
@ 2024-04-18 23:57 ` Eduard Zingerman
0 siblings, 0 replies; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-18 23:57 UTC (permalink / raw)
To: Cupertino Miranda, bpf
Cc: Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
> Range for XOR and OR operators would not be attempted unless src_reg
> would resolve to a single value, i.e. a known constant value.
> This condition is unnecessary, and the following XOR/OR operator
> handling could compute a possible better range.
>
> 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>
> ---
I agree with this reasoning regarding OR/XOR processing.
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.
2024-04-17 12:23 [PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements Cupertino Miranda
2024-04-17 12:23 ` [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation Cupertino Miranda
2024-04-17 12:23 ` [PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR " Cupertino Miranda
@ 2024-04-17 12:23 ` Cupertino Miranda
2024-04-19 1:24 ` Eduard Zingerman
2024-04-23 20:33 ` Yonghong Song
2024-04-17 12:23 ` [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check Cupertino Miranda
2024-04-17 12:23 ` [PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests Cupertino Miranda
4 siblings, 2 replies; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-17 12:23 UTC (permalink / raw)
To: bpf
Cc: Cupertino Miranda, Yonghong Song, Alexei Starovoitov,
David Faust, Elena Zannoni
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>
---
.../selftests/bpf/progs/verifier_bounds.c | 64 +++++++++++++++++++
1 file changed, 64 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index ec430b71730b..e3c867d48664 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -885,6 +885,70 @@ l1_%=: r0 = 0; \
: __clobber_all);
}
+SEC("socket")
+__description("bounds check for reg32 <= 1, 0 xor (0,1)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void t_0_xor_01(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r1 = 0; \
+ *(u64*)(r10 - 8) = r1; \
+ r2 = r10; \
+ r2 += -8; \
+ r1 = %[map_hash_8b] ll; \
+ call %[bpf_map_lookup_elem]; \
+ if r0 != 0 goto l0_%=; \
+ exit; \
+l0_%=: w1 = 0; \
+ r6 >>= 63; \
+ w1 ^= w6; \
+ if w1 <= 1 goto l1_%=; \
+ r0 = *(u64*)(r0 + 8); \
+l1_%=: r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_map_lookup_elem),
+ __imm_addr(map_hash_8b),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 <= 1, 0 or (0,1)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void t_0_or_01(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r1 = 0; \
+ *(u64*)(r10 - 8) = r1; \
+ r2 = r10; \
+ r2 += -8; \
+ r1 = %[map_hash_8b] ll; \
+ call %[bpf_map_lookup_elem]; \
+ if r0 != 0 goto l0_%=; \
+ exit; \
+l0_%=: w1 = 0; \
+ r6 >>= 63; \
+ w1 |= w6; \
+ if w1 <= 1 goto l1_%=; \
+ r0 = *(u64*)(r0 + 8); \
+l1_%=: r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_map_lookup_elem),
+ __imm_addr(map_hash_8b),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
SEC("socket")
__description("bounds checks after 32-bit truncation. test 1")
__success __failure_unpriv __msg_unpriv("R0 leaks addr")
--
2.39.2
^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.
2024-04-17 12:23 ` [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests Cupertino Miranda
@ 2024-04-19 1:24 ` Eduard Zingerman
2024-04-19 9:41 ` Cupertino Miranda
2024-04-23 20:33 ` Yonghong Song
1 sibling, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-19 1:24 UTC (permalink / raw)
To: Cupertino Miranda, bpf
Cc: Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
[...]
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_xor_01(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + r1 = 0; \
> + *(u64*)(r10 - 8) = r1; \
> + r2 = r10; \
> + r2 += -8; \
> + r1 = %[map_hash_8b] ll; \
> + call %[bpf_map_lookup_elem]; \
> + if r0 != 0 goto l0_%=; \
> + exit; \
> +l0_%=: w1 = 0; \
> + r6 >>= 63; \
> + w1 ^= w6; \
> + if w1 <= 1 goto l1_%=; \
> + r0 = *(u64*)(r0 + 8); \
> +l1_%=: r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_map_lookup_elem),
> + __imm_addr(map_hash_8b),
> + __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
> +
I think that this test case (and one below) should be simplified,
e.g. as follows:
SEC("socket")
__success __log_level(2)
__msg("5: (af) r0 ^= r6 ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))")
__naked void non_const_xor_src_dst(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
r6 = r0; \
call %[bpf_get_prandom_u32]; \
r6 &= 0xff; \
r0 &= 0x0f; \
r0 ^= r6; \
exit; \
" :
: __imm(bpf_map_lookup_elem),
__imm_addr(map_hash_8b),
__imm(bpf_get_prandom_u32)
: __clobber_all);
}
Patch #2 allows verifier to compute dst range for xor operation with
non-constant src and dst registers, which is exactly what checked when
verifier log for instruction "r0 ^= r6" is verified.
Manipulations with maps, unpriv behavior and retval are just a distraction.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.
2024-04-19 1:24 ` Eduard Zingerman
@ 2024-04-19 9:41 ` Cupertino Miranda
0 siblings, 0 replies; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-19 9:41 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
Eduard Zingerman writes:
> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>
> [...]
>
>> +SEC("socket")
>> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
>> +__success __failure_unpriv
>> +__msg_unpriv("R0 min value is outside of the allowed memory range")
>> +__retval(0)
>> +__naked void t_0_xor_01(void)
>> +{
>> + asm volatile (" \
>> + call %[bpf_get_prandom_u32]; \
>> + r6 = r0; \
>> + r1 = 0; \
>> + *(u64*)(r10 - 8) = r1; \
>> + r2 = r10; \
>> + r2 += -8; \
>> + r1 = %[map_hash_8b] ll; \
>> + call %[bpf_map_lookup_elem]; \
>> + if r0 != 0 goto l0_%=; \
>> + exit; \
>> +l0_%=: w1 = 0; \
>> + r6 >>= 63; \
>> + w1 ^= w6; \
>> + if w1 <= 1 goto l1_%=; \
>> + r0 = *(u64*)(r0 + 8); \
>> +l1_%=: r0 = 0; \
>> + exit; \
>> +" :
>> + : __imm(bpf_map_lookup_elem),
>> + __imm_addr(map_hash_8b),
>> + __imm(bpf_get_prandom_u32)
>> + : __clobber_all);
>> +}
>> +
>
> I think that this test case (and one below) should be simplified,
> e.g. as follows:
>
> SEC("socket")
> __success __log_level(2)
> __msg("5: (af) r0 ^= r6 ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))")
> __naked void non_const_xor_src_dst(void)
> {
> asm volatile (" \
> call %[bpf_get_prandom_u32]; \
> r6 = r0; \
> call %[bpf_get_prandom_u32]; \
> r6 &= 0xff; \
> r0 &= 0x0f; \
> r0 ^= r6; \
> exit; \
> " :
> : __imm(bpf_map_lookup_elem),
> __imm_addr(map_hash_8b),
> __imm(bpf_get_prandom_u32)
> : __clobber_all);
> }
>
> Patch #2 allows verifier to compute dst range for xor operation with
> non-constant src and dst registers, which is exactly what checked when
> verifier log for instruction "r0 ^= r6" is verified.
> Manipulations with maps, unpriv behavior and retval are just a distraction.
Thanks for the suggestion.
I could not make it fail in the past without that control-flow in the
end of the test. I will try this.
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.
2024-04-17 12:23 ` [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests Cupertino Miranda
2024-04-19 1:24 ` Eduard Zingerman
@ 2024-04-23 20:33 ` Yonghong Song
1 sibling, 0 replies; 21+ messages in thread
From: Yonghong Song @ 2024-04-23 20:33 UTC (permalink / raw)
To: Cupertino Miranda, bpf; +Cc: Alexei Starovoitov, David Faust, Elena Zannoni
On 4/17/24 5:23 AM, Cupertino Miranda wrote:
Please add proper commit message.
> 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>
> ---
> .../selftests/bpf/progs/verifier_bounds.c | 64 +++++++++++++++++++
> 1 file changed, 64 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index ec430b71730b..e3c867d48664 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -885,6 +885,70 @@ l1_%=: r0 = 0; \
> : __clobber_all);
> }
>
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_xor_01(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + r1 = 0; \
> + *(u64*)(r10 - 8) = r1; \
> + r2 = r10; \
> + r2 += -8; \
> + r1 = %[map_hash_8b] ll; \
> + call %[bpf_map_lookup_elem]; \
> + if r0 != 0 goto l0_%=; \
> + exit; \
> +l0_%=: w1 = 0; \
> + r6 >>= 63; \
> + w1 ^= w6; \
> + if w1 <= 1 goto l1_%=; \
> + r0 = *(u64*)(r0 + 8); \
> +l1_%=: r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_map_lookup_elem),
> + __imm_addr(map_hash_8b),
> + __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
> +
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 or (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_or_01(void)
> +{
> + asm volatile (" \
> + call %[bpf_get_prandom_u32]; \
> + r6 = r0; \
> + r1 = 0; \
> + *(u64*)(r10 - 8) = r1; \
> + r2 = r10; \
> + r2 += -8; \
> + r1 = %[map_hash_8b] ll; \
> + call %[bpf_map_lookup_elem]; \
> + if r0 != 0 goto l0_%=; \
> + exit; \
> +l0_%=: w1 = 0; \
> + r6 >>= 63; \
> + w1 |= w6; \
> + if w1 <= 1 goto l1_%=; \
> + r0 = *(u64*)(r0 + 8); \
> +l1_%=: r0 = 0; \
> + exit; \
> +" :
> + : __imm(bpf_map_lookup_elem),
> + __imm_addr(map_hash_8b),
> + __imm(bpf_get_prandom_u32)
> + : __clobber_all);
> +}
> +
> SEC("socket")
> __description("bounds checks after 32-bit truncation. test 1")
> __success __failure_unpriv __msg_unpriv("R0 leaks addr")
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check
2024-04-17 12:23 [PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements Cupertino Miranda
` (2 preceding siblings ...)
2024-04-17 12:23 ` [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests Cupertino Miranda
@ 2024-04-17 12:23 ` Cupertino Miranda
2024-04-19 2:30 ` Eduard Zingerman
2024-04-17 12:23 ` [PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests Cupertino Miranda
4 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-17 12:23 UTC (permalink / raw)
To: bpf
Cc: Cupertino Miranda, Yonghong Song, Alexei Starovoitov,
David Faust, Elena Zannoni
MUL instruction required that src_reg would be a known value (i.e.
src_reg would be a const value). The condition in this case can be
relaxed, since multiplication is a cummutative operator and the range
computation is still valid if at least one of its registers is known.
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 | 19 ++++++++++++-------
1 file changed, 12 insertions(+), 7 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f410eb027e25..185ea7f19a79 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13433,20 +13433,23 @@ enum {
};
static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
+ struct bpf_reg_state dst_reg,
struct bpf_reg_state src_reg)
{
- bool src_known;
+ bool src_known, dst_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);
+ bool valid_known_src = true;
+ bool valid_known_dst = true;
+ src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
+ dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
/* Taint dst register if offset had invalid bounds
* derived from e.g. dead branches.
*/
- if (valid_known == false)
+ if (valid_known_src == false)
return UNCOMPUTABLE_RANGE;
switch (opcode) {
@@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
case BPF_OR:
return COMPUTABLE_RANGE;
- /* Compute range for the following only if the src_reg is known.
+ /* Compute range for MUL if at least one of its registers is known.
*/
case BPF_MUL:
- return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
+ if (src_known || (dst_known && valid_known_dst))
+ return COMPUTABLE_RANGE;
+ break;
/* Shift operators range is only computable if shift dimension operand
* is known. Also, shifts greater than 31 or 63 are undefined. This
@@ -13493,7 +13498,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
int ret;
- int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
+ int is_safe = is_safe_to_compute_dst_reg_range(insn, *dst_reg, src_reg);
switch (is_safe) {
case UNCOMPUTABLE_RANGE:
__mark_reg_unknown(env, dst_reg);
--
2.39.2
^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check
2024-04-17 12:23 ` [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check Cupertino Miranda
@ 2024-04-19 2:30 ` Eduard Zingerman
2024-04-19 9:47 ` Cupertino Miranda
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-19 2:30 UTC (permalink / raw)
To: Cupertino Miranda, bpf
Cc: Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
[...]
> static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
> + struct bpf_reg_state dst_reg,
> struct bpf_reg_state src_reg)
Nit: there is no need to pass {dst,src}_reg by value,
struct bpf_reg_state is 120 bytes in size
(but maybe compiler handles this).
> {
> - bool src_known;
> + bool src_known, dst_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);
> + bool valid_known_src = true;
> + bool valid_known_dst = true;
> + src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
> + dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>
> /* Taint dst register if offset had invalid bounds
> * derived from e.g. dead branches.
> */
> - if (valid_known == false)
> + if (valid_known_src == false)
> return UNCOMPUTABLE_RANGE;
>
> switch (opcode) {
> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
> case BPF_OR:
> return COMPUTABLE_RANGE;
>
> - /* Compute range for the following only if the src_reg is known.
> + /* Compute range for MUL if at least one of its registers is known.
> */
> case BPF_MUL:
> - return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
> + if (src_known || (dst_known && valid_known_dst))
> + return COMPUTABLE_RANGE;
> + break;
Is it even necessary to restrict src or dst to be known?
adjust_scalar_min_max_vals() logic for multiplication looks as follows:
case BPF_MUL:
dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
scalar32_min_max_mul(dst_reg, &src_reg);
scalar_min_max_mul(dst_reg, &src_reg);
break;
Where tnum_mul() refers to a paper, and that paper does not restrict
abstract multiplication algorithm to constant values on either side.
The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
- if both src and dst are positive
- if overflow is not possible
- adjust dst->min *= src->min
- adjust dst->max *= src->max
I think this should work just fine if neither of src or dst is a known constant.
What do you think?
[...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check
2024-04-19 2:30 ` Eduard Zingerman
@ 2024-04-19 9:47 ` Cupertino Miranda
2024-04-23 20:53 ` Yonghong Song
0 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-19 9:47 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
Eduard Zingerman writes:
> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>
> [...]
>
>> static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>> + struct bpf_reg_state dst_reg,
>> struct bpf_reg_state src_reg)
>
> Nit: there is no need to pass {dst,src}_reg by value,
> struct bpf_reg_state is 120 bytes in size
> (but maybe compiler handles this).
>
>> {
>> - bool src_known;
>> + bool src_known, dst_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);
>> + bool valid_known_src = true;
>> + bool valid_known_dst = true;
>> + src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>> + dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>
>> /* Taint dst register if offset had invalid bounds
>> * derived from e.g. dead branches.
>> */
>> - if (valid_known == false)
>> + if (valid_known_src == false)
>> return UNCOMPUTABLE_RANGE;
>>
>> switch (opcode) {
>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>> case BPF_OR:
>> return COMPUTABLE_RANGE;
>>
>> - /* Compute range for the following only if the src_reg is known.
>> + /* Compute range for MUL if at least one of its registers is known.
>> */
>> case BPF_MUL:
>> - return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>> + if (src_known || (dst_known && valid_known_dst))
>> + return COMPUTABLE_RANGE;
>> + break;
>
> Is it even necessary to restrict src or dst to be known?
> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>
> case BPF_MUL:
> dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
> scalar32_min_max_mul(dst_reg, &src_reg);
> scalar_min_max_mul(dst_reg, &src_reg);
> break;
>
> Where tnum_mul() refers to a paper, and that paper does not restrict
> abstract multiplication algorithm to constant values on either side.
> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
> - if both src and dst are positive
> - if overflow is not possible
> - adjust dst->min *= src->min
> - adjust dst->max *= src->max
>
> I think this should work just fine if neither of src or dst is a known constant.
> What do you think?
>
With the refactor this looked like an armless change. Indeed if we agree
that the algorithm covers all scenarios, then why not.
I did not study the paper or the scalar_min_max_mul function nearly
enough to know for sure.
>
> [...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check
2024-04-19 9:47 ` Cupertino Miranda
@ 2024-04-23 20:53 ` Yonghong Song
2024-04-24 14:59 ` Cupertino Miranda
0 siblings, 1 reply; 21+ messages in thread
From: Yonghong Song @ 2024-04-23 20:53 UTC (permalink / raw)
To: Cupertino Miranda, Eduard Zingerman
Cc: bpf, Alexei Starovoitov, David Faust, Elena Zannoni
On 4/19/24 2:47 AM, Cupertino Miranda wrote:
> Eduard Zingerman writes:
>
>> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>>
>> [...]
>>
>>> static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>> + struct bpf_reg_state dst_reg,
>>> struct bpf_reg_state src_reg)
>> Nit: there is no need to pass {dst,src}_reg by value,
>> struct bpf_reg_state is 120 bytes in size
>> (but maybe compiler handles this).
>>
>>> {
>>> - bool src_known;
>>> + bool src_known, dst_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);
>>> + bool valid_known_src = true;
>>> + bool valid_known_dst = true;
>>> + src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>>> + dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>>
>>> /* Taint dst register if offset had invalid bounds
>>> * derived from e.g. dead branches.
>>> */
>>> - if (valid_known == false)
>>> + if (valid_known_src == false)
>>> return UNCOMPUTABLE_RANGE;
>>>
>>> switch (opcode) {
>>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>> case BPF_OR:
>>> return COMPUTABLE_RANGE;
>>>
>>> - /* Compute range for the following only if the src_reg is known.
>>> + /* Compute range for MUL if at least one of its registers is known.
>>> */
>>> case BPF_MUL:
>>> - return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>>> + if (src_known || (dst_known && valid_known_dst))
>>> + return COMPUTABLE_RANGE;
>>> + break;
>> Is it even necessary to restrict src or dst to be known?
>> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>>
>> case BPF_MUL:
>> dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
>> scalar32_min_max_mul(dst_reg, &src_reg);
>> scalar_min_max_mul(dst_reg, &src_reg);
>> break;
>>
>> Where tnum_mul() refers to a paper, and that paper does not restrict
>> abstract multiplication algorithm to constant values on either side.
>> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
>> - if both src and dst are positive
>> - if overflow is not possible
>> - adjust dst->min *= src->min
>> - adjust dst->max *= src->max
>>
>> I think this should work just fine if neither of src or dst is a known constant.
>> What do you think?
>>
> With the refactor this looked like an armless change. Indeed if we agree
> that the algorithm covers all scenarios, then why not.
> I did not study the paper or the scalar_min_max_mul function nearly
> enough to know for sure.
I double checked and I think Eduard is correct. src_known checking
is not necessary for multiplication. It would be great if you can
add this change as well in the patch set.
>> [...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check
2024-04-23 20:53 ` Yonghong Song
@ 2024-04-24 14:59 ` Cupertino Miranda
0 siblings, 0 replies; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-24 14:59 UTC (permalink / raw)
To: Yonghong Song
Cc: Eduard Zingerman, bpf, Alexei Starovoitov, David Faust, Elena Zannoni
Yonghong Song writes:
> On 4/19/24 2:47 AM, Cupertino Miranda wrote:
>> Eduard Zingerman writes:
>>
>>> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>>>
>>> [...]
>>>
>>>> static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>> + struct bpf_reg_state dst_reg,
>>>> struct bpf_reg_state src_reg)
>>> Nit: there is no need to pass {dst,src}_reg by value,
>>> struct bpf_reg_state is 120 bytes in size
>>> (but maybe compiler handles this).
>>>
>>>> {
>>>> - bool src_known;
>>>> + bool src_known, dst_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);
>>>> + bool valid_known_src = true;
>>>> + bool valid_known_dst = true;
>>>> + src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>>>> + dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>>>
>>>> /* Taint dst register if offset had invalid bounds
>>>> * derived from e.g. dead branches.
>>>> */
>>>> - if (valid_known == false)
>>>> + if (valid_known_src == false)
>>>> return UNCOMPUTABLE_RANGE;
>>>>
>>>> switch (opcode) {
>>>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>> case BPF_OR:
>>>> return COMPUTABLE_RANGE;
>>>>
>>>> - /* Compute range for the following only if the src_reg is known.
>>>> + /* Compute range for MUL if at least one of its registers is known.
>>>> */
>>>> case BPF_MUL:
>>>> - return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>>>> + if (src_known || (dst_known && valid_known_dst))
>>>> + return COMPUTABLE_RANGE;
>>>> + break;
>>> Is it even necessary to restrict src or dst to be known?
>>> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>>>
>>> case BPF_MUL:
>>> dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
>>> scalar32_min_max_mul(dst_reg, &src_reg);
>>> scalar_min_max_mul(dst_reg, &src_reg);
>>> break;
>>>
>>> Where tnum_mul() refers to a paper, and that paper does not restrict
>>> abstract multiplication algorithm to constant values on either side.
>>> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
>>> - if both src and dst are positive
>>> - if overflow is not possible
>>> - adjust dst->min *= src->min
>>> - adjust dst->max *= src->max
>>>
>>> I think this should work just fine if neither of src or dst is a known constant.
>>> What do you think?
>>>
>> With the refactor this looked like an armless change. Indeed if we agree
>> that the algorithm covers all scenarios, then why not.
>> I did not study the paper or the scalar_min_max_mul function nearly
>> enough to know for sure.
>
> I double checked and I think Eduard is correct. src_known checking
> is not necessary for multiplication. It would be great if you can
> add this change as well in the patch set.
Sure! Thanks for confirming this.
>
>>> [...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests.
2024-04-17 12:23 [PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements Cupertino Miranda
` (3 preceding siblings ...)
2024-04-17 12:23 ` [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check Cupertino Miranda
@ 2024-04-17 12:23 ` Cupertino Miranda
2024-04-19 2:32 ` Eduard Zingerman
4 siblings, 1 reply; 21+ messages in thread
From: Cupertino Miranda @ 2024-04-17 12:23 UTC (permalink / raw)
To: bpf
Cc: Cupertino Miranda, Yonghong Song, Alexei Starovoitov,
David Faust, Elena Zannoni
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>
---
.../selftests/bpf/progs/verifier_bounds.c | 99 +++++++++++++++++++
1 file changed, 99 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index e3c867d48664..719e247114f5 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -949,6 +949,105 @@ l1_%=: r0 = 0; \
: __clobber_all);
}
+SEC("socket")
+__description("bounds check for reg32 <= 9, 3 mul (0,3)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_3_mul_reg_01(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r1 = 0; \
+ *(u64*)(r10 - 8) = r1; \
+ r2 = r10; \
+ r2 += -8; \
+ r1 = %[map_hash_8b] ll; \
+ call %[bpf_map_lookup_elem]; \
+ if r0 != 0 goto l0_%=; \
+ exit; \
+l0_%=: w1 = 3; \
+ r6 >>= 62; \
+ w1 *= w6; \
+ if w1 <= 9 goto l1_%=; \
+ r0 = *(u64*)(r0 + 8); \
+l1_%=: r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_map_lookup_elem),
+ __imm_addr(map_hash_8b),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 <= 9, (0,3) mul 3")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_13_mul_reg_3(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r1 = 0; \
+ *(u64*)(r10 - 8) = r1; \
+ r2 = r10; \
+ r2 += -8; \
+ r1 = %[map_hash_8b] ll; \
+ call %[bpf_map_lookup_elem]; \
+ if r0 != 0 goto l0_%=; \
+ exit; \
+l0_%=: w1 = 3; \
+ r6 >>= 62; \
+ w6 *= w1; \
+ if w6 <= 9 goto l1_%=; \
+ r0 = *(u64*)(r0 + 8); \
+l1_%=: r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_map_lookup_elem),
+ __imm_addr(map_hash_8b),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 >= 6 && reg32 <= 15, (2,5) mul 3")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_25_mul_reg_3(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; \
+ r1 = 0; \
+ *(u64*)(r10 - 8) = r1; \
+ r2 = r10; \
+ r2 += -8; \
+ r1 = %[map_hash_8b] ll; \
+ call %[bpf_map_lookup_elem]; \
+ if r0 != 0 goto l0_%=; \
+ exit; \
+l0_%=: w1 = 3; \
+ r6 >>= 62; \
+ r6 += 2; \
+ w6 *= w1; \
+ if w6 > 15 goto l1_%=; \
+ if w6 < 6 goto l1_%=; \
+ r0 = 0; \
+ exit; \
+l1_%=: r0 = *(u64*)(r0 + 8); \
+ exit; \
+" :
+ : __imm(bpf_map_lookup_elem),
+ __imm_addr(map_hash_8b),
+ __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
SEC("socket")
__description("bounds checks after 32-bit truncation. test 1")
__success __failure_unpriv __msg_unpriv("R0 leaks addr")
--
2.39.2
^ permalink raw reply related [flat|nested] 21+ messages in thread
* Re: [PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests.
2024-04-17 12:23 ` [PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests Cupertino Miranda
@ 2024-04-19 2:32 ` Eduard Zingerman
0 siblings, 0 replies; 21+ messages in thread
From: Eduard Zingerman @ 2024-04-19 2:32 UTC (permalink / raw)
To: Cupertino Miranda, bpf
Cc: Yonghong Song, Alexei Starovoitov, David Faust, Elena Zannoni
On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
> 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>
> ---
As with or/xor, I suggest to simplify these test cases:
- avoid unnecessary control flow
- avoid map manipulations
- drop __unpriv_* and __retval parts.
^ permalink raw reply [flat|nested] 21+ messages in thread