[v5,bpf-next,05/23] bpf: derive subreg bounds from full bounds when upper 32 bits are constant

Commit Message

Andrii Nakryiko Oct. 27, 2023, 6:13 p.m. UTC

Comments in code try to explain the idea behind why this is correct.
Please check the code and comments.

Acked-by: Shung-Hsi Yu <[e-mail]>
Signed-off-by: Andrii Nakryiko <[e-mail]>
---
 kernel/bpf/verifier.c | 45 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

Comments

Eduard Zingerman Oct. 31, 2023, 3:37 p.m. UTC | #1

On Fri, 2023-10-27 at 11:13 -0700, Andrii Nakryiko wrote:
> > Comments in code try to explain the idea behind why this is correct.
> > Please check the code and comments.
> > 
> > Acked-by: Shung-Hsi Yu <[e-mail]>
> > Signed-off-by: Andrii Nakryiko <[e-mail]>

Acked-by: Eduard Zingerman <[e-mail]>

> > ---
> >  kernel/bpf/verifier.c | 45 +++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 45 insertions(+)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 0f66e9092c38..5082ca1ea5dc 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -2324,6 +2324,51 @@ static void __update_reg_bounds(struct bpf_reg_state *reg)
> >  /* Uses signed min/max values to inform unsigned, and vice-versa */
> >  static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
> >  {
> > +	/* If upper 32 bits of u64/s64 range don't change, we can use lower 32
> > +	 * bits to improve our u32/s32 boundaries.
> > +	 *
> > +	 * E.g., the case where we have upper 32 bits as zero ([10, 20] in
> > +	 * u64) is pretty trivial, it's obvious that in u32 we'll also have
> > +	 * [10, 20] range. But this property holds for any 64-bit range as
> > +	 * long as upper 32 bits in that entire range of values stay the same.
> > +	 *
> > +	 * E.g., u64 range [0x10000000A, 0x10000000F] ([4294967306, 4294967311]
> > +	 * in decimal) has the same upper 32 bits throughout all the values in
> > +	 * that range. As such, lower 32 bits form a valid [0xA, 0xF] ([10, 15])
> > +	 * range.
> > +	 *
> > +	 * Note also, that [0xA, 0xF] is a valid range both in u32 and in s32,
> > +	 * following the rules outlined below about u64/s64 correspondence
> > +	 * (which equally applies to u32 vs s32 correspondence). In general it
> > +	 * depends on actual hexadecimal values of 32-bit range. They can form
> > +	 * only valid u32, or only valid s32 ranges in some cases.
> > +	 *
> > +	 * So we use all these insights to derive bounds for subregisters here.
> > +	 */
> > +	if ((reg->umin_value >> 32) == (reg->umax_value >> 32)) {
> > +		/* u64 to u32 casting preserves validity of low 32 bits as
> > +		 * a range, if upper 32 bits are the same
> > +		 */
> > +		reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->umin_value);
> > +		reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->umax_value);
> > +
> > +		if ((s32)reg->umin_value <= (s32)reg->umax_value) {
> > +			reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value);
> > +			reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->umax_value);
> > +		}
> > +	}
> > +	if ((reg->smin_value >> 32) == (reg->smax_value >> 32)) {
> > +		/* low 32 bits should form a proper u32 range */
> > +		if ((u32)reg->smin_value <= (u32)reg->smax_value) {
> > +			reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->smin_value);
> > +			reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->smax_value);
> > +		}
> > +		/* low 32 bits should form a proper s32 range */
> > +		if ((s32)reg->smin_value <= (s32)reg->smax_value) {
> > +			reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value);
> > +			reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value);
> > +		}
> > +	}
> >  	/* if u32 range forms a valid s32 range (due to matching sign bit),
> >  	 * try to learn from that
> >  	 */

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0f66e9092c38..5082ca1ea5dc 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2324,6 +2324,51 @@  static void __update_reg_bounds(struct bpf_reg_state *reg)
 /* Uses signed min/max values to inform unsigned, and vice-versa */
 static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
 {
+	/* If upper 32 bits of u64/s64 range don't change, we can use lower 32
+	 * bits to improve our u32/s32 boundaries.
+	 *
+	 * E.g., the case where we have upper 32 bits as zero ([10, 20] in
+	 * u64) is pretty trivial, it's obvious that in u32 we'll also have
+	 * [10, 20] range. But this property holds for any 64-bit range as
+	 * long as upper 32 bits in that entire range of values stay the same.
+	 *
+	 * E.g., u64 range [0x10000000A, 0x10000000F] ([4294967306, 4294967311]
+	 * in decimal) has the same upper 32 bits throughout all the values in
+	 * that range. As such, lower 32 bits form a valid [0xA, 0xF] ([10, 15])
+	 * range.
+	 *
+	 * Note also, that [0xA, 0xF] is a valid range both in u32 and in s32,
+	 * following the rules outlined below about u64/s64 correspondence
+	 * (which equally applies to u32 vs s32 correspondence). In general it
+	 * depends on actual hexadecimal values of 32-bit range. They can form
+	 * only valid u32, or only valid s32 ranges in some cases.
+	 *
+	 * So we use all these insights to derive bounds for subregisters here.
+	 */
+	if ((reg->umin_value >> 32) == (reg->umax_value >> 32)) {
+		/* u64 to u32 casting preserves validity of low 32 bits as
+		 * a range, if upper 32 bits are the same
+		 */
+		reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->umin_value);
+		reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->umax_value);
+
+		if ((s32)reg->umin_value <= (s32)reg->umax_value) {
+			reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value);
+			reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->umax_value);
+		}
+	}
+	if ((reg->smin_value >> 32) == (reg->smax_value >> 32)) {
+		/* low 32 bits should form a proper u32 range */
+		if ((u32)reg->smin_value <= (u32)reg->smax_value) {
+			reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->smin_value);
+			reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->smax_value);
+		}
+		/* low 32 bits should form a proper s32 range */
+		if ((s32)reg->smin_value <= (s32)reg->smax_value) {
+			reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value);
+			reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value);
+		}
+	}
 	/* if u32 range forms a valid s32 range (due to matching sign bit),
 	 * try to learn from that
 	 */