Skip to contentSkip to conversation

bpf: implement __reg_deduce_bounds() using wrapped intervals

RFC PATCH In review Eduard Zingerman 3 participants 12 messages Mar 18 – Apr 14

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover bpf: implement __reg_deduce_bounds() using wrapped intervals

Use wrapped intervals representation [1] to express range-based deductions. Such representation allows to express these deductions in a more mathematically rigorous way:
- {32,64}-bit signed -> unsigned, unsigned -> signed deduction infers improved bounds from an intersection of signed and unsigned arcs.
- 32-bit -> 64-bit and 32-bit -> 64 bit deduction infer improved bounds from projections of 32-bit arcs onto 64-bit space and vice-versa.

Reformulating 32-bit -> 64-bit deduction in such terms allowed to find two cases currently not handled by deduce_bounds_64_from_32(). See patch #3 for details.

This RFC argues that wrapped interval based implementation for __reg_deduce_bounds() is easier to understand and maintain. An alternative to this RFC would be to update deduce_bounds_64_from_32() in a same way patch #3 modifies reg_bounds.c selftest, in order to handle newly identified cases.

[1] https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf

---
Eduard Zingerman (4):

      bpf: representation and basic operations on circular numbers
      bpf: cnum for 32->32, 64->64, 64->32 deductions in reg_bounds_sync
      bpf: cnum 32->64 deductions in reg_bounds_sync
      selftests/bpf: new cases handled by 32->64 range refinements
 include/linux/cnum.h                               |  60 ++++
 kernel/bpf/Makefile                                |   2 +-
 kernel/bpf/cnum.c                                  | 115 +++++++
 kernel/bpf/cnum_defs.h                             | 176 ++++++++++
 kernel/bpf/verifier.c                              | 373 ++++-----------------
 .../testing/selftests/bpf/prog_tests/reg_bounds.c  |  82 +++--
 .../testing/selftests/bpf/progs/verifier_bounds.c  |  80 +++++
 7 files changed, 556 insertions(+), 332 deletions(-)

---
base-commit: 77378dabb50f593c756d393d8eacb0b91b758863
change-id: 20260318-cnum-sync-bounds-8b6732710fd7

author maintainer
#1 lore raw

RFC PATCH 1/4 bpf: representation and basic operations on circular numbers

This commit adds basic definitions for cnum32/cnum64.
This is a unified numeric range representation for signed and unsigned domains. Inspired by an old post from Shung-Hsi Yu [1] and paper [2]. Operations correctness is verified using cbmc model checker, tests source code can be found in a separate repo [3].

[1] https://lore.kernel.org/all/ZTZxoDJJbX9mrQ9w@u94a/
[2] https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf
[3] https://github.com/eddyz87/cnum-verif/tree/master

---
 include/linux/cnum.h   |  60 +++++++++++++++++
 kernel/bpf/Makefile    |   2 +-
 kernel/bpf/cnum.c      | 115 ++++++++++++++++++++++++++++++++
 kernel/bpf/cnum_defs.h | 176 +++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 352 insertions(+), 1 deletion(-)
include/linux/cnum.h new file +60 -0
new file mode 100644
index 0000000000000000000000000000000000000000..c38142d3cee11185018e34e669800f1d72865e57
@@ -0,0 +1,60 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
+
+#ifndef _LINUX_CNUM_H
+#define _LINUX_CNUM_H
+
+#include <linux/types.h>
+
+/*
+ * cnum32: a circular number.
+ * A unified representation for signed and unsigned ranges.
+ *
+ * Assume that a 32-bit range is a circle, with 0 being in the 12 o'clock
+ * position, numbers placed sequentially in clockwise order and U32_MAX
+ * in the 11 o'clock position. Signed values map onto the same circle:
+ * S32_MAX sits at 5 o'clock, S32_MIN sits at 6 o'clock (opposite 0),
+ * negative values occupy the left half and positive values the right half.
+ *
+ * @cnum32 represents an arc on this circle drawn clockwise.
+ * @base corresponds to the first value of the range.
+ * @size corresponds to the number of integers in the range excluding @base.
+ * (The @base is excluded to avoid integer overflow when representing the full
+ *  0..U32_MAX range, which corresponds to 2^32, which can't be stored in u32).
+ *
+ * For example: {U32_MAX, 1} corresponds to signed range [-1, 0],
+ *              {S32_MAX, 1} corresponds to unsigned range [S32_MAX, S32_MIN].
+ */
+struct cnum32 {
+	u32 base;
+	u32 size;
+};
+
+struct cnum32 cnum32_from_urange(u32 min, u32 max);
+struct cnum32 cnum32_from_srange(s32 min, s32 max);
+u32 cnum32_umin(struct cnum32 cnum);
+u32 cnum32_umax(struct cnum32 cnum);
+s32 cnum32_smin(struct cnum32 cnum);
+s32 cnum32_smax(struct cnum32 cnum);
+bool cnum32_intersect(struct cnum32 a, struct cnum32 b, struct cnum32 *out);
+bool cnum32_contains(struct cnum32 cnum, u32 v);
+
+/* Same as cnum32 but for 64-bit ranges */
+struct cnum64 {
+	u64 base;
+	u64 size;
+};
+
+struct cnum64 cnum64_from_urange(u64 min, u64 max);
+struct cnum64 cnum64_from_srange(s64 min, s64 max);
+u64 cnum64_umin(struct cnum64 cnum);
+u64 cnum64_umax(struct cnum64 cnum);
+s64 cnum64_smin(struct cnum64 cnum);
+s64 cnum64_smax(struct cnum64 cnum);
+bool cnum64_intersect(struct cnum64 a, struct cnum64 b, struct cnum64 *out);
+bool cnum64_contains(struct cnum64 cnum, u64 v);
+
+struct cnum32 cnum32_from_cnum64(struct cnum64 cnum);
+bool cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b, struct cnum64 *out);
+
+#endif /* _LINUX_CNUM_H */
kernel/bpf/Makefile +1 -1
index 79cf22860a99ba31a9daf08a29de0f3a162ba89f..b6647a3cca8b5db2283c01d155c82190824701c0 100644
@@ -6,7 +6,7 @@ cflags-nogcse-$(CONFIG_X86)$(CONFIG_CC_IS_GCC) := -fno-gcse
 endif
 CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy)
 
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o liveness.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o liveness.o cnum.o
 obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
 obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o bpf_insn_array.o
kernel/bpf/cnum.c new file +115 -0

115 lines not on this page · raw message

kernel/bpf/cnum_defs.h new file +176 -0

176 lines not on this page · raw message

Signature · 1 line
2.51.1
#2 lore raw

Re: [PATCH RFC bpf-next v1 1/4] bpf: representation and basic operations on circular numbers

Should (u32)a be (u32)v here? As written, the condition (u32)a does not depend on v, which makes the quantifier trivial. The function computes the tightest range t containing all v in a whose low 32…
Quoted 5 lines
kernel/bpf/cnum.c new file +0 -0
new file mode 100644
index 000000000000..da50a40e79ac

[ ... ]

Quoted 12 lines

+/*
+ * Suppose 'a' and 'b' are laid out as follows:
+ *
+ * 64-bit number axis --->
+ *
+ * N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32

+ * ||------|---|=====|-------||----------|=====|-------||----------|=====|----|--||
+ *         |   |< b >|                   |< b >|                   |< b >|    |
+ *         |   |                                                         |    |
+ *         |<--+--------------------------- a ---------------------------+--->|
+ *             |                                                         |
+ *             |<-------------------------- t -------------------------->|
Quoted 4 lines

+ *
+ * In such a case it is possible to infer a more tight representation t
+ * such that ∀ v ∈ a, (u32)a ∈ b: v ∈ t.
+ */

Should (u32)a be (u32)v here? As written, the condition (u32)a does not depend on v, which makes the quantifier trivial. The function computes the tightest range t containing all v in a whose low 32 bits fall in b, so the specification should read:

such that ∀ v ∈ a, (u32)v ∈ b: v ∈ t.

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/23256340287

author maintainer
#3 lore raw

Re: [PATCH RFC bpf-next v1 1/4] bpf: representation and basic operations on circular numbers

Quoted 25 lines · On Wed, 2026-03-18 at 17:11 +0000, [email protected] wrote:
Quoted 5 lines
kernel/bpf/cnum.c new file +0 -0
new file mode 100644
index 000000000000..da50a40e79ac

[ ... ]

Quoted 10 lines

+/*
+ * Suppose 'a' and 'b' are laid out as follows:
+ *
+ *                                                          64-bit number axis --->
+ *
+ * N*2^32                   (N+1)*2^32                (N+2)*2^32                (N+3)*2^32
+ * ||------|---|=====|-------||----------|=====|-------||----------|=====|----|--||

+ *         |   |< b >|                   |< b >|                   |< b >|    |
+ *         |   |                                                         |    |
+ *         |<--+--------------------------- a ---------------------------+--->|
Quoted 6 lines

+ *             |                                                         |
+ *             |<-------------------------- t -------------------------->|
+ *
+ * In such a case it is possible to infer a more tight representation t
+ * such that ∀ v ∈ a, (u32)a ∈ b: v ∈ t.
+ */

Quoted 6 lines

Should (u32)a be (u32)v here?  As written, the condition (u32)a does not depend on v, which makes the quantifier trivial.  The function computes the tightest range t containing all v in a whose low 32 bits fall in b, so the specification should read:

  such that ∀ v ∈ a, (u32)v ∈ b: v ∈ t.

Yes, it should have been (u32)v ∈ b and that's what cbmc test is checking.

#4 lore raw

Re: [PATCH RFC bpf-next v1 1/4] bpf: representation and basic operations on circular numbers

In reply to Eduard Zingerman

On Wed, Mar 18, 2026 at 09:28:58AM -0700, Eduard Zingerman wrote:
...

Quoted 18 lines

+ * cnum32: a circular number.
+ * A unified representation for signed and unsigned ranges.
+ *
+ * Assume that a 32-bit range is a circle, with 0 being in the 12 o'clock
+ * position, numbers placed sequentially in clockwise order and U32_MAX
+ * in the 11 o'clock position. Signed values map onto the same circle:
+ * S32_MAX sits at 5 o'clock, S32_MIN sits at 6 o'clock (opposite 0),
+ * negative values occupy the left half and positive values the right half.
+ *
+ * @cnum32 represents an arc on this circle drawn clockwise.
+ * @base corresponds to the first value of the range.
+ * @size corresponds to the number of integers in the range excluding @base.
+ * (The @base is excluded to avoid integer overflow when representing the full
+ * 0..U32_MAX range, which corresponds to 2^32, which can't be stored in u32).
+ *
+ * For example: {U32_MAX, 1} corresponds to signed range [-1, 0],
+ * {S32_MAX, 1} corresponds to unsigned range [S32_MAX, S32_MIN].
+ */

include/linux/cnum.h line 31

Quoted 4 lines
include/linux/cnum.h new file +4 -0
+struct cnum32 {
+	u32 base;
+	u32 size;
+};

Minor note, memory are vague, but despite having 'size' available seems to make some calculation easier, I end up finding using 'start' and 'end'[1] more intuitive and feel to me less indirection, as well as being closer to existing implementation. E.g.

...

kernel/bpf/cnum_defs.h line 59

Quoted 4 lines
kernel/bpf/cnum_defs.h new file +4 -0
+/* True if this cnum represents two signed ranges. */
+static inline bool FN(srange_overflow)(struct cnum_t cnum)
+{
+	return FN(contains)(cnum, (ut)ST_MAX) && FN(contains)(cnum, (ut)ST_MIN);

To check overflow in signed ranges, just do (sT)end < (sT)start, which should be more familiar to most.

1: https://lore.kernel.org/bpf/[email protected]/

Quoted 1 line

+}

...

author maintainer
#5 lore raw

Re: [PATCH RFC bpf-next v1 1/4] bpf: representation and basic operations on circular numbers

Quoted 30 lines · Shung-Hsi Yu

On Wed, Mar 18, 2026 at 09:28:58AM -0700, Eduard Zingerman wrote:
...

Quoted 18 lines

+ * cnum32: a circular number.
+ * A unified representation for signed and unsigned ranges.
+ *
+ * Assume that a 32-bit range is a circle, with 0 being in the 12 o'clock
+ * position, numbers placed sequentially in clockwise order and U32_MAX
+ * in the 11 o'clock position. Signed values map onto the same circle:
+ * S32_MAX sits at 5 o'clock, S32_MIN sits at 6 o'clock (opposite 0),
+ * negative values occupy the left half and positive values the right half.
+ *
+ * @cnum32 represents an arc on this circle drawn clockwise.
+ * @base corresponds to the first value of the range.
+ * @size corresponds to the number of integers in the range excluding @base.
+ * (The @base is excluded to avoid integer overflow when representing the full
+ * 0..U32_MAX range, which corresponds to 2^32, which can't be stored in u32).
+ *
+ * For example: {U32_MAX, 1} corresponds to signed range [-1, 0],
+ * {S32_MAX, 1} corresponds to unsigned range [S32_MAX, S32_MIN].
+ */

include/linux/cnum.h line 31

Quoted 4 lines
include/linux/cnum.h new file +4 -0
+struct cnum32 {
+	u32 base;
+	u32 size;
+};

Minor note, memory are vague, but despite having 'size' available seems to make some calculation easier, I end up finding using 'start' and 'end'[1] more intuitive and feel to me less indirection, as well as being closer to existing implementation. E.g.

Quoted 8 lines

...

kernel/bpf/cnum_defs.h line 59

Quoted 4 lines
kernel/bpf/cnum_defs.h new file +4 -0
+/* True if this cnum represents two signed ranges. */
+static inline bool FN(srange_overflow)(struct cnum_t cnum)
+{
+	return FN(contains)(cnum, (ut)ST_MAX) && FN(contains)(cnum, (ut)ST_MIN);

To check overflow in signed ranges, just do (sT)end < (sT)start, which should be more familiar to most.

Yes, start/end is what the paper [2] uses as well. I used 'size' because it was more convenient for intersection implementation. Don't have a strong opinion here.

[2] https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf

Quoted 5 lines

1: https://lore.kernel.org/bpf/[email protected]/

Quoted 1 line

+}

...

author maintainer
#6 lore raw

RFC PATCH 2/4 bpf: cnum for 32->32, 64->64, 64->32 deductions in reg_bounds_sync

In reply to Eduard Zingerman

For deduce_bounds_32_from_32() and deduce_bounds_64_from_64() cnum-based implementation is an intersection of arcs formed by signed and unsigned register ranges:

  if (cnum32_intersect(cnum32_from_ureg(reg),
                       cnum32_from_sreg(reg),
                       cnum))
    cnum_update_reg32_bounds(reg, cnum);

For deduce_bounds_32_from_64() cnum-based implementation is an intersection of arcs formed by signed and unsigned register 64-bit ranges projected to a 32-bit ring.

  if (cnum64_from_reg(reg, &cnum))
    cnum_update_reg32_bounds(reg, cnum32_from_cnum64(cnum));

A non-functional change.

---
 kernel/bpf/verifier.c | 297 ++++++++++----------------------------------------
 1 file changed, 59 insertions(+), 238 deletions(-)
kernel/bpf/verifier.c +59 -238
index 01c18f4268deb3355f3ab03c41ceacc7e9d712c6..45ee8711c50c5ef19d7a24333e55abcded93a8fb 100644
@@ -26,6 +26,7 @@
 #include <linux/poison.h>
 #include <linux/module.h>
 #include <linux/cpumask.h>
+#include <linux/cnum.h>
 #include <linux/bpf_mem_alloc.h>
 #include <net/xdp.h>
 #include <linux/trace_events.h>
@@ -2447,255 +2448,75 @@ static void __update_reg_bounds(struct bpf_reg_state *reg)
 	__update_reg64_bounds(reg);
 }
 
+static struct cnum32 cnum32_from_ureg(struct bpf_reg_state *reg)
+{
+	return cnum32_from_urange(reg->u32_min_value, reg->u32_max_value);
+}
+
+static struct cnum32 cnum32_from_sreg(struct bpf_reg_state *reg)
+{
+	return cnum32_from_srange(reg->s32_min_value, reg->s32_max_value);
+}
+
+static struct cnum64 cnum64_from_ureg(struct bpf_reg_state *reg)
+{
+	return cnum64_from_urange(reg->umin_value, reg->umax_value);
+}
+
+static struct cnum64 cnum64_from_sreg(struct bpf_reg_state *reg)
+{
+	return cnum64_from_srange(reg->smin_value, reg->smax_value);
+}
+
+static bool cnum32_from_reg(struct bpf_reg_state *reg, struct cnum32 *cnum)
+{
+	return cnum32_intersect(cnum32_from_ureg(reg), cnum32_from_sreg(reg), cnum);
+}
+
+static bool cnum64_from_reg(struct bpf_reg_state *reg, struct cnum64 *cnum)
+{
+	return cnum64_intersect(cnum64_from_ureg(reg), cnum64_from_sreg(reg), cnum);
+}
+
+static void cnum_update_reg32_bounds(struct bpf_reg_state *reg, struct cnum32 cnum)
+{
+	reg->u32_min_value = max_t(u32, reg->u32_min_value, cnum32_umin(cnum));
+	reg->u32_max_value = min_t(u32, reg->u32_max_value, cnum32_umax(cnum));
+	reg->s32_min_value = max_t(s32, reg->s32_min_value, cnum32_smin(cnum));
+	reg->s32_max_value = min_t(s32, reg->s32_max_value, cnum32_smax(cnum));
+}
+
+static void cnum_update_reg64_bounds(struct bpf_reg_state *reg, struct cnum64 cnum)
+{
+	reg->umin_value = max_t(u64, reg->umin_value, cnum64_umin(cnum));
+	reg->umax_value = min_t(u64, reg->umax_value, cnum64_umax(cnum));
+	reg->smin_value = max_t(s64, reg->smin_value, cnum64_smin(cnum));
+	reg->smax_value = min_t(s64, reg->smax_value, cnum64_smax(cnum));
+}
+
 /* Uses signed min/max values to inform unsigned, and vice-versa */
 static void deduce_bounds_32_from_64(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);
-		}
-	}
-	/* Special case where upper bits form a small sequence of two
-	 * sequential numbers (in 32-bit unsigned space, so 0xffffffff to
-	 * 0x00000000 is also valid), while lower bits form a proper s32 range
-	 * going from negative numbers to positive numbers. E.g., let's say we
-	 * have s64 range [-1, 1] ([0xffffffffffffffff, 0x0000000000000001]).
-	 * Possible s64 values are {-1, 0, 1} ({0xffffffffffffffff,
-	 * 0x0000000000000000, 0x00000000000001}). Ignoring upper 32 bits,
-	 * we still get a valid s32 range [-1, 1] ([0xffffffff, 0x00000001]).
-	 * Note that it doesn't have to be 0xffffffff going to 0x00000000 in
-	 * upper 32 bits. As a random example, s64 range
-	 * [0xfffffff0fffffff0; 0xfffffff100000010], forms a valid s32 range
-	 * [-16, 16] ([0xfffffff0; 0x00000010]) in its 32 bit subregister.
-	 */
-	if ((u32)(reg->umin_value >> 32) + 1 == (u32)(reg->umax_value >> 32) &&
-	    (s32)reg->umin_value < 0 && (s32)reg->umax_value >= 0) {
-		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 ((u32)(reg->smin_value >> 32) + 1 == (u32)(reg->smax_value >> 32) &&
-	    (s32)reg->smin_value < 0 && (s32)reg->smax_value >= 0) {
-		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);
-	}
+	struct cnum64 cnum;
+
+	if (cnum64_from_reg(reg, &cnum))
+		cnum_update_reg32_bounds(reg, cnum32_from_cnum64(cnum));
 }
 
 static void deduce_bounds_32_from_32(struct bpf_reg_state *reg)
 {
-	/* if u32 range forms a valid s32 range (due to matching sign bit),
-	 * try to learn from that
-	 */
-	if ((s32)reg->u32_min_value <= (s32)reg->u32_max_value) {
-		reg->s32_min_value = max_t(s32, reg->s32_min_value, reg->u32_min_value);
-		reg->s32_max_value = min_t(s32, reg->s32_max_value, reg->u32_max_value);
-	}
-	/* If we cannot cross the sign boundary, then signed and unsigned bounds
-	 * are the same, so combine.  This works even in the negative case, e.g.
-	 * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff.
-	 */
-	if ((u32)reg->s32_min_value <= (u32)reg->s32_max_value) {
-		reg->u32_min_value = max_t(u32, reg->s32_min_value, reg->u32_min_value);
-		reg->u32_max_value = min_t(u32, reg->s32_max_value, reg->u32_max_value);
-	} else {
-		if (reg->u32_max_value < (u32)reg->s32_min_value) {
-			/* See __reg64_deduce_bounds() for detailed explanation.
-			 * Refine ranges in the following situation:
-			 *
-			 * 0                                                   U32_MAX
-			 * |  [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]              |
-			 * |----------------------------|----------------------------|
-			 * |xxxxx s32 range xxxxxxxxx]                       [xxxxxxx|
-			 * 0                     S32_MAX S32_MIN                    -1
-			 */
-			reg->s32_min_value = (s32)reg->u32_min_value;
-			reg->u32_max_value = min_t(u32, reg->u32_max_value, reg->s32_max_value);
-		} else if ((u32)reg->s32_max_value < reg->u32_min_value) {
-			/*
-			 * 0                                                   U32_MAX
-			 * |              [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]  |
-			 * |----------------------------|----------------------------|
-			 * |xxxxxxxxx]                       [xxxxxxxxxxxx s32 range |
-			 * 0                     S32_MAX S32_MIN                    -1
-			 */
-			reg->s32_max_value = (s32)reg->u32_max_value;
-			reg->u32_min_value = max_t(u32, reg->u32_min_value, reg->s32_min_value);
-		}
-	}
+	struct cnum32 cnum;
+
+	if (cnum32_from_reg(reg, &cnum))
+		cnum_update_reg32_bounds(reg, cnum);
 }
 
 static void deduce_bounds_64_from_64(struct bpf_reg_state *reg)
 {
-	/* If u64 range forms a valid s64 range (due to matching sign bit),
-	 * try to learn from that. Let's do a bit of ASCII art to see when
-	 * this is happening. Let's take u64 range first:
-	 *
-	 * 0             0x7fffffffffffffff 0x8000000000000000        U64_MAX
-	 * |-------------------------------|--------------------------------|
-	 *
-	 * Valid u64 range is formed when umin and umax are anywhere in the
-	 * range [0, U64_MAX], and umin <= umax. u64 case is simple and
-	 * straightforward. Let's see how s64 range maps onto the same range
-	 * of values, annotated below the line for comparison:
-	 *
-	 * 0             0x7fffffffffffffff 0x8000000000000000        U64_MAX
-	 * |-------------------------------|--------------------------------|
-	 * 0                        S64_MAX S64_MIN                        -1
-	 *
-	 * So s64 values basically start in the middle and they are logically
-	 * contiguous to the right of it, wrapping around from -1 to 0, and
-	 * then finishing as S64_MAX (0x7fffffffffffffff) right before
-	 * S64_MIN. We can try drawing the continuity of u64 vs s64 values
-	 * more visually as mapped to sign-agnostic range of hex values.
-	 *
-	 *  u64 start                                               u64 end
-	 *  _______________________________________________________________
-	 * /                                                               \
-	 * 0             0x7fffffffffffffff 0x8000000000000000        U64_MAX
-	 * |-------------------------------|--------------------------------|
-	 * 0                        S64_MAX S64_MIN                        -1
-	 *                                / \
-	 * >------------------------------   ------------------------------->
-	 * s64 continues...        s64 end   s64 start          s64 "midpoint"
-	 *
-	 * What this means is that, in general, we can't always derive
-	 * something new about u64 from any random s64 range, and vice versa.
-	 *
-	 * But we can do that in two particular cases. One is when entire
-	 * u64/s64 range is *entirely* contained within left half of the above
-	 * diagram or when it is *entirely* contained in the right half. I.e.:
-	 *
-	 * |-------------------------------|--------------------------------|
-	 *     ^                   ^            ^                 ^
-	 *     A                   B            C                 D
-	 *
-	 * [A, B] and [C, D] are contained entirely in their respective halves
-	 * and form valid contiguous ranges as both u64 and s64 values. [A, B]
-	 * will be non-negative both as u64 and s64 (and in fact it will be
-	 * identical ranges no matter the signedness). [C, D] treated as s64
-	 * will be a range of negative values, while in u64 it will be
-	 * non-negative range of values larger than 0x8000000000000000.
-	 *
-	 * Now, any other range here can't be represented in both u64 and s64
-	 * simultaneously. E.g., [A, C], [A, D], [B, C], [B, D] are valid
-	 * contiguous u64 ranges, but they are discontinuous in s64. [B, C]
-	 * in s64 would be properly presented as [S64_MIN, C] and [B, S64_MAX],
-	 * for example. Similarly, valid s64 range [D, A] (going from negative
-	 * to positive values), would be two separate [D, U64_MAX] and [0, A]
-	 * ranges as u64. Currently reg_state can't represent two segments per
-	 * numeric domain, so in such situations we can only derive maximal
-	 * possible range ([0, U64_MAX] for u64, and [S64_MIN, S64_MAX] for s64).
-	 *
-	 * So we use these facts to derive umin/umax from smin/smax and vice
-	 * versa only if they stay within the same "half". This is equivalent
-	 * to checking sign bit: lower half will have sign bit as zero, upper
-	 * half have sign bit 1. Below in code we simplify this by just
-	 * casting umin/umax as smin/smax and checking if they form valid
-	 * range, and vice versa. Those are equivalent checks.
-	 */
-	if ((s64)reg->umin_value <= (s64)reg->umax_value) {
-		reg->smin_value = max_t(s64, reg->smin_value, reg->umin_value);
-		reg->smax_value = min_t(s64, reg->smax_value, reg->umax_value);
-	}
-	/* If we cannot cross the sign boundary, then signed and unsigned bounds
-	 * are the same, so combine.  This works even in the negative case, e.g.
-	 * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff.
-	 */
-	if ((u64)reg->smin_value <= (u64)reg->smax_value) {
-		reg->umin_value = max_t(u64, reg->smin_value, reg->umin_value);
-		reg->umax_value = min_t(u64, reg->smax_value, reg->umax_value);
-	} else {
-		/* If the s64 range crosses the sign boundary, then it's split
-		 * between the beginning and end of the U64 domain. In that
-		 * case, we can derive new bounds if the u64 range overlaps
-		 * with only one end of the s64 range.
-		 *
-		 * In the following example, the u64 range overlaps only with
-		 * positive portion of the s64 range.
-		 *
-		 * 0                                                   U64_MAX
-		 * |  [xxxxxxxxxxxxxx u64 range xxxxxxxxxxxxxx]              |
-		 * |----------------------------|----------------------------|
-		 * |xxxxx s64 range xxxxxxxxx]                       [xxxxxxx|
-		 * 0                     S64_MAX S64_MIN                    -1
-		 *
-		 * We can thus derive the following new s64 and u64 ranges.
-		 *
-		 * 0                                                   U64_MAX
-		 * |  [xxxxxx u64 range xxxxx]                               |
-		 * |----------------------------|----------------------------|
-		 * |  [xxxxxx s64 range xxxxx]                               |
-		 * 0                     S64_MAX S64_MIN                    -1
-		 *
-		 * If they overlap in two places, we can't derive anything
-		 * because reg_state can't represent two ranges per numeric
-		 * domain.
-		 *
-		 * 0                                                   U64_MAX
-		 * |  [xxxxxxxxxxxxxxxxx u64 range xxxxxxxxxxxxxxxxx]        |
-		 * |----------------------------|----------------------------|
-		 * |xxxxx s64 range xxxxxxxxx]                    [xxxxxxxxxx|
-		 * 0                     S64_MAX S64_MIN                    -1
-		 *
-		 * The first condition below corresponds to the first diagram
-		 * above.
-		 */
-		if (reg->umax_value < (u64)reg->smin_value) {
-			reg->smin_value = (s64)reg->umin_value;
-			reg->umax_value = min_t(u64, reg->umax_value, reg->smax_value);
-		} else if ((u64)reg->smax_value < reg->umin_value) {
-			/* This second condition considers the case where the u64 range
-			 * overlaps with the negative portion of the s64 range:
-			 *
-			 * 0                                                   U64_MAX
-			 * |              [xxxxxxxxxxxxxx u64 range xxxxxxxxxxxxxx]  |
-			 * |----------------------------|----------------------------|
-			 * |xxxxxxxxx]                       [xxxxxxxxxxxx s64 range |
-			 * 0                     S64_MAX S64_MIN                    -1
-			 */
-			reg->smax_value = (s64)reg->umax_value;
-			reg->umin_value = max_t(u64, reg->umin_value, reg->smin_value);
-		}
-	}
+	struct cnum64 cnum;
+
+	if (cnum64_from_reg(reg, &cnum))
+		cnum_update_reg64_bounds(reg, cnum);
 }
 
 static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
Signature · 1 line
2.51.1
author maintainer
#7 lore raw

RFC PATCH 3/4 bpf: cnum 32->64 deductions in reg_bounds_sync

In reply to Eduard Zingerman

Replace deduce_bounds_64_from_32() with cnum64_cnum32_intersect() based implementation. Assume:
- a is a 64-bit range
- b is a 32-bit range
- t is a refined 64-bit range, such that ∀ v ∈ a, (u32)a ∈ b: v ∈ t.

New deduce_bounds_64_from_32() makes the following deductions:

(A): 'b' is a sub-range of the first or the last 32-bit
sub-range of 'a':

64-bit number axis --->

N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32

 ||------|---|=====|-------||----------|=====|-------||----------|=====|----|--||
         |   |< b >|                   |< b >|                   |< b >|    |
         |   |                                                         |    |
         |<--+--------------------------- a ---------------------------+--->|
             |                                                         |
             |<-------------------------- t -------------------------->|

(B) 'b' does not intersect with the first of the last 32-bit sub-range of 'a':

N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32

||--|=====|----|----------||--|=====|---------------||--|=====|------------|--||
    |< b >|    |              |< b >|                   |< b >|            |
               |              |                               |            |
               |<-------------+--------- a -------------------|----------->|
                              |                               |
                              |<-------- t ------------------>|

(C) 'b' crosses 0/U32_MAX boundary:

N*2^32 (N+1)*2^32 (N+2)*2^32 (N+3)*2^32

||===|---------|------|===||===|----------------|===||===|---------|------|===||
 |b >|         |      |< b||b >|                |< b||b >|         |      |< b|
               |      |                                  |         |
               |<-----+----------------- a --------------+-------->|
                      |                                  |
                      |<---------------- t ------------->|

Current implementation of deduce_bounds_64_from_32() only handles case (A).

reg_bounds.c is updated with similar logic to keep selftests passing. Instead of using cnums it inspects intersection between 'b' and first / last / next-after-first / previous-before-last sub-ranges of 'a'.

The reg_bounds.c:range64_range32_intersect() function is verified using cbmc model checker, see [1].

[1] https://github.com/eddyz87/cnum-verif

---
 kernel/bpf/verifier.c                              | 76 ++++----------------
 .../testing/selftests/bpf/prog_tests/reg_bounds.c  | 82 ++++++++++++++--------
 2 files changed, 65 insertions(+), 93 deletions(-)
kernel/bpf/verifier.c +13 -63
index 45ee8711c50c5ef19d7a24333e55abcded93a8fb..745aef7d5467f92b0499b480987ef9daf940d52f 100644
@@ -2521,69 +2521,19 @@ static void deduce_bounds_64_from_64(struct bpf_reg_state *reg)
 
 static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
 {
-	/* Try to tighten 64-bit bounds from 32-bit knowledge, using 32-bit
-	 * values on both sides of 64-bit range in hope to have tighter range.
-	 * E.g., if r1 is [0x1'00000000, 0x3'80000000], and we learn from
-	 * 32-bit signed > 0 operation that s32 bounds are now [1; 0x7fffffff].
-	 * With this, we can substitute 1 as low 32-bits of _low_ 64-bit bound
-	 * (0x100000000 -> 0x100000001) and 0x7fffffff as low 32-bits of
-	 * _high_ 64-bit bound (0x380000000 -> 0x37fffffff) and arrive at a
-	 * better overall bounds for r1 as [0x1'000000001; 0x3'7fffffff].
-	 * We just need to make sure that derived bounds we are intersecting
-	 * with are well-formed ranges in respective s64 or u64 domain, just
-	 * like we do with similar kinds of 32-to-64 or 64-to-32 adjustments.
-	 */
-	__u64 new_umin, new_umax;
-	__s64 new_smin, new_smax;
-
-	/* u32 -> u64 tightening, it's always well-formed */
-	new_umin = (reg->umin_value & ~0xffffffffULL) | reg->u32_min_value;
-	new_umax = (reg->umax_value & ~0xffffffffULL) | reg->u32_max_value;
-	reg->umin_value = max_t(u64, reg->umin_value, new_umin);
-	reg->umax_value = min_t(u64, reg->umax_value, new_umax);
-	/* u32 -> s64 tightening, u32 range embedded into s64 preserves range validity */
-	new_smin = (reg->smin_value & ~0xffffffffULL) | reg->u32_min_value;
-	new_smax = (reg->smax_value & ~0xffffffffULL) | reg->u32_max_value;
-	reg->smin_value = max_t(s64, reg->smin_value, new_smin);
-	reg->smax_value = min_t(s64, reg->smax_value, new_smax);
-
-	/* Here we would like to handle a special case after sign extending load,
-	 * when upper bits for a 64-bit range are all 1s or all 0s.
-	 *
-	 * Upper bits are all 1s when register is in a range:
-	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
-	 * Upper bits are all 0s when register is in a range:
-	 *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
-	 * Together this forms are continuous range:
-	 *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
-	 *
-	 * Now, suppose that register range is in fact tighter:
-	 *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
-	 * Also suppose that it's 32-bit range is positive,
-	 * meaning that lower 32-bits of the full 64-bit register
-	 * are in the range:
-	 *   [0x0000_0000, 0x7fff_ffff] (W)
-	 *
-	 * If this happens, then any value in a range:
-	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
-	 * is smaller than a lowest bound of the range (R):
-	 *   0xffff_ffff_8000_0000
-	 * which means that upper bits of the full 64-bit register
-	 * can't be all 1s, when lower bits are in range (W).
-	 *
-	 * Note that:
-	 *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
-	 *  - 0x0000_0000_7fff_ffff == (s64)S32_MAX
-	 * These relations are used in the conditions below.
-	 */
-	if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) {
-		reg->smin_value = reg->s32_min_value;
-		reg->smax_value = reg->s32_max_value;
-		reg->umin_value = reg->s32_min_value;
-		reg->umax_value = reg->s32_max_value;
-		reg->var_off = tnum_intersect(reg->var_off,
-					      tnum_range(reg->smin_value, reg->smax_value));
-	}
+	struct cnum32 s = cnum32_from_sreg(reg);
+	struct cnum32 u = cnum32_from_ureg(reg);
+	struct cnum64 t;
+
+	t = cnum64_from_ureg(reg);
+	if (cnum64_cnum32_intersect(t, s, &t) &&
+	    cnum64_cnum32_intersect(t, u, &t))
+		cnum_update_reg64_bounds(reg, t);
+
+	t = cnum64_from_sreg(reg);
+	if (cnum64_cnum32_intersect(t, s, &t) &&
+	    cnum64_cnum32_intersect(t, u, &t))
+		cnum_update_reg64_bounds(reg, t);
 }
 
 static void __reg_deduce_bounds(struct bpf_reg_state *reg)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +52 -30

98 lines not on this page · raw message

Signature · 1 line
2.51.1
author maintainer
#8 lore raw

RFC PATCH 4/4 selftests/bpf: new cases handled by 32->64 range refinements

In reply to Eduard Zingerman

1. 32-bit range starts before 64-bit range's low bits in each block, causing intersection to skip entire blocks.
2. 32-bit range crosses the U32_MAX/0 boundary, represented as s32 range crossing sign boundary.

---
 .../testing/selftests/bpf/progs/verifier_bounds.c  | 80 ++++++++++++++++++++++
 1 file changed, 80 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +80 -0
index 3724d5e5bcb3623aa54b2eaddb70adc9c7987813..c6980ac049f668799301de33b50bd8c420fd8985 100644
@@ -2070,4 +2070,84 @@ __naked void refinement_32bounds_not_overwriting_64bounds(void *ctx)
 	: __clobber_all);
 }
 
+/*
+ * 32-bit range starts before 64-bit range low bits in each 2^32 block.
+ *
+ * N*2^32                   (N+1)*2^32                (N+2)*2^32                (N+3)*2^32
+ * ||----|=====|--|----------||----|=====|-------------||--|-|=====|-------------||
+ *       |< b >|  |                |< b >|                 | |< b >|
+ *                |                |     |                 |
+ *                |<---------------+- a -+---------------->|
+ *                                 |     |
+ *                                 |< t >| refined r0 range
+ *
+ * a = u64 [0x1'00000008, 0x3'00000001]
+ * b = u32 [2, 5]
+ * t = u64 [0x2'00000002, 0x2'00000005]
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_before_block_start(void *ctx)
+{
+	asm volatile ("							\
+	call %[bpf_get_prandom_u32];					\
+	r1 = 0x100000008 ll;						\
+	if r0 < r1 goto 2f;						\
+	r1 = 0x300000001 ll;						\
+	if r0 > r1 goto 2f;	/* u64: [0x1'00000008, 0x3'00000001] */	\
+	if w0 < 2 goto 2f;						\
+	if w0 > 5 goto 2f;	/* u32: [2, 5] */			\
+	r2 = 0x200000002 ll;						\
+	r3 = 0x200000005 ll;						\
+	if r0 >= r2 goto 1f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+1:	if r0 <= r3 goto 2f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+2:	exit;								\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * 32-bit range crossing U32_MAX / 0 boundary.
+ *
+ * N*2^32                   (N+1)*2^32                (N+2)*2^32                (N+3)*2^32
+ * ||===|---------|------|===||===|----------------|===||===|---------|------|===||
+ *  |b >|         |      |< b||b >|                |< b||b >|         |      |< b|
+ *                |      |                                  |         |
+ *                |<-----+----------------- a --------------+-------->|
+ *                       |                                  |
+ *                       |<---------------- t ------------->| refined r0 range
+ *
+ * a = u64 [0x1'00000006, 0x2'FFFFFFEF]
+ * b = s32 [-16, 5] (u32 wrapping [0xFFFFFFF0, 0x00000005])
+ * t = u64 [0x1'FFFFFFF0, 0x2'00000005]
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_wrapping_32bit(void *ctx)
+{
+	asm volatile ("							\
+	call %[bpf_get_prandom_u32];					\
+	r1 = 0x100000006 ll;						\
+	if r0 < r1 goto 2f;						\
+	r1 = 0x2ffffffef ll;						\
+	if r0 > r1 goto 2f;	/* u64: [0x1'00000006, 0x2'FFFFFFEF] */	\
+	if w0 s< -16 goto 2f;						\
+	if w0 s> 5 goto 2f;	/* s32: [-16, 5] */			\
+	r1 = 0x1fffffff0 ll;						\
+	r2 = 0x200000005 ll;						\
+	if r0 >= r1 goto 1f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+1:	if r0 <= r2 goto 2f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+2:	exit;								\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.51.1
#9 lore raw
In reply to Eduard Zingerman
Quoted 13 lines · Eduard Zingerman

Use wrapped intervals representation [1] to express range-based deductions. Such representation allows to express these deductions in a more mathematically rigorous way:
- {32,64}-bit signed -> unsigned, unsigned -> signed deduction infers improved bounds from an intersection of signed and unsigned arcs.
- 32-bit -> 64-bit and 32-bit -> 64 bit deduction infer improved bounds from projections of 32-bit arcs onto 64-bit space and vice-versa.

Reformulating 32-bit -> 64-bit deduction in such terms allowed to find two cases currently not handled by deduce_bounds_64_from_32(). See patch #3 for details.

Quoted 5 lines

This RFC argues that wrapped interval based implementation for __reg_deduce_bounds() is easier to understand and maintain. An alternative to this RFC would be to update deduce_bounds_64_from_32() in a same way patch #3 modifies reg_bounds.c selftest, in order to handle newly identified cases.

I think introducing wrapper interval for purpose of improving & simplification of __reg_deduce_bounds() alone might not be enough. That said, I still want to push wrapper interval integration forward, but that will be addressed in a separate follow-up email.

If I understand it right, the newly identified case in patch #4 is not something we encounter from compiler-generated BPF program (yet), and thus not something that is needed currently, either this or the alternative to update deduce_bounds_64_from_32() in a same way patch #3.

On the other hand, I do like the much cleaner code as well as better modularity for reuse, and being more mistake-proof.

For a more objective metric, I gauged at the difference in terms of cognitive complexity (which penalize nested conditional more compared to cyclomatic complexity) through clang-tidy, and do find supporting evidence:

Before this patchset, congitive complexity is 88

'deduce_bounds_32_from_64' has cognitive complexity of 42 'deduce_bounds_32_from_32' has cognitive complexity of 20 'deduce_bounds_64_from_64' has cognitive complexity of 20 'deduce_bounds_64_from_32' has cognitive complexity of 6

After this patchset, cognitive complexity is 49

'cnum32_from_cnum64' has cognitive complexity of 2 'cnum64_cnum32_intersect' has cognitive complexity of 13 'cnumT_umin' has cognitive complexity of 1 'cnumT_srange_overflow' has cognitive complexity of 1 'cnumT_intersect' has cognitive complexity of 17 'cnum_update_reg32_bounds' has cognitive complexity of 4 'cnum_update_reg64_bounds' has cognitive complexity of 4 'deduce_bounds_32_from_64' has cognitive complexity of 1 'deduce_bounds_32_from_32' has cognitive complexity of 1 'deduce_bounds_64_from_64' has cognitive complexity of 1 'deduce_bounds_64_from_32' has cognitive complexity of 4

So there is indeed a net reduction of 41 (~46%) in terms of complexity score. Supporting the easier to maintain claim, too.

That said, we do pay some price as cnum is more mind bending and not as straightforward to grasp. Cognitive complexity cannot factor in the background knowledge required.

I do think there are more reason to push cnum/wrapped interval forward beyond using it __reg_deduce_bounds though. Will try to write a follow-up to this email.

Quoted 8 lines

[1] https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf

---
Eduard Zingerman (4):

      bpf: representation and basic operations on circular numbers
      bpf: cnum for 32->32, 64->64, 64->32 deductions in reg_bounds_sync
      bpf: cnum 32->64 deductions in reg_bounds_sync
      selftests/bpf: new cases handled by 32->64 range refinements

...

author maintainer
#10 lore raw
Quoted 62 lines · Shung-Hsi Yu
Quoted 13 lines · Eduard Zingerman

Use wrapped intervals representation [1] to express range-based deductions. Such representation allows to express these deductions in a more mathematically rigorous way:
- {32,64}-bit signed -> unsigned, unsigned -> signed deduction infers improved bounds from an intersection of signed and unsigned arcs.
- 32-bit -> 64-bit and 32-bit -> 64 bit deduction infer improved bounds from projections of 32-bit arcs onto 64-bit space and vice-versa.

Reformulating 32-bit -> 64-bit deduction in such terms allowed to find two cases currently not handled by deduce_bounds_64_from_32(). See patch #3 for details.

Quoted 5 lines

This RFC argues that wrapped interval based implementation for __reg_deduce_bounds() is easier to understand and maintain. An alternative to this RFC would be to update deduce_bounds_64_from_32() in a same way patch #3 modifies reg_bounds.c selftest, in order to handle newly identified cases.

I think introducing wrapper interval for purpose of improving & simplification of __reg_deduce_bounds() alone might not be enough. That said, I still want to push wrapper interval integration forward, but that will be addressed in a separate follow-up email.

If I understand it right, the newly identified case in patch #4 is not something we encounter from compiler-generated BPF program (yet), and thus not something that is needed currently, either this or the alternative to update deduce_bounds_64_from_32() in a same way patch #3.

On the other hand, I do like the much cleaner code as well as better modularity for reuse, and being more mistake-proof.

For a more objective metric, I gauged at the difference in terms of cognitive complexity (which penalize nested conditional more compared to cyclomatic complexity) through clang-tidy, and do find supporting evidence:

Before this patchset, congitive complexity is 88

'deduce_bounds_32_from_64' has cognitive complexity of 42 'deduce_bounds_32_from_32' has cognitive complexity of 20 'deduce_bounds_64_from_64' has cognitive complexity of 20 'deduce_bounds_64_from_32' has cognitive complexity of 6

After this patchset, cognitive complexity is 49

'cnum32_from_cnum64' has cognitive complexity of 2 'cnum64_cnum32_intersect' has cognitive complexity of 13 'cnumT_umin' has cognitive complexity of 1 'cnumT_srange_overflow' has cognitive complexity of 1 'cnumT_intersect' has cognitive complexity of 17 'cnum_update_reg32_bounds' has cognitive complexity of 4 'cnum_update_reg64_bounds' has cognitive complexity of 4 'deduce_bounds_32_from_64' has cognitive complexity of 1 'deduce_bounds_32_from_32' has cognitive complexity of 1 'deduce_bounds_64_from_64' has cognitive complexity of 1 'deduce_bounds_64_from_32' has cognitive complexity of 4

So there is indeed a net reduction of 41 (~46%) in terms of complexity score. Supporting the easier to maintain claim, too.

Quoted 7 lines

That said, we do pay some price as cnum is more mind bending and not as straightforward to grasp. Cognitive complexity cannot factor in the background knowledge required.

I do think there are more reason to push cnum/wrapped interval forward beyond using it __reg_deduce_bounds though. Will try to write a follow-up to this email.

Hi Shung-Hsi,

Thank you for taking a look. I have a work-in-progress branch [1] which implements union and multiplication operators for wrapped intervals domain. I'll plug it into the verifier and share the results in this thread.

Thanks,
Eduard

[1] https://github.com/eddyz87/cnum-verif/tree/arithm-ops

#11 lore raw
Quoted 26 lines · Eduard Zingerman
Quoted 25 lines · Shung-Hsi Yu
Quoted 13 lines · Eduard Zingerman

Use wrapped intervals representation [1] to express range-based deductions. Such representation allows to express these deductions in a more mathematically rigorous way:
- {32,64}-bit signed -> unsigned, unsigned -> signed deduction infers improved bounds from an intersection of signed and unsigned arcs.
- 32-bit -> 64-bit and 32-bit -> 64 bit deduction infer improved bounds from projections of 32-bit arcs onto 64-bit space and vice-versa.

Reformulating 32-bit -> 64-bit deduction in such terms allowed to find two cases currently not handled by deduce_bounds_64_from_32(). See patch #3 for details.

Quoted 5 lines

This RFC argues that wrapped interval based implementation for __reg_deduce_bounds() is easier to understand and maintain. An alternative to this RFC would be to update deduce_bounds_64_from_32() in a same way patch #3 modifies reg_bounds.c selftest, in order to handle newly identified cases.

I think introducing wrapper interval for purpose of improving & simplification of __reg_deduce_bounds() alone might not be enough. That said, I still want to push wrapper interval integration forward, but that will be addressed in a separate follow-up email.

...

Quoted 7 lines
Quoted 7 lines

That said, we do pay some price as cnum is more mind bending and not as straightforward to grasp. Cognitive complexity cannot factor in the background knowledge required.

I do think there are more reason to push cnum/wrapped interval forward beyond using it __reg_deduce_bounds though. Will try to write a follow-up to this email.

Trying to pursue this line of thought further.

Ideally we just have cnum in 'struct bpf_reg_state', and get rid of signed & unsigned tracking, and __reg_deduce_bounds would be the perfect place to start. Though as you have pointed out in [1], it will be less precise for cases where signed & unsigned's overlap in two ranges.

That said, the paper also states that cnum and reduced product of signed and unsigned domains are incomparable, which I take as cnum is not strictly less precise. And given the reg_bounds.c test you ran into is added specifically for ldsx[2], perhaps some special case would be enough.

But I suppose we'll just have to get to the full implementation and see whether Cilium, scx, and Meta's BPF programs pass to now for sure.

If that fails we still have the much less elegant way of dealing with cases of split range with
a. forking verifier state (like "Recognize special arithmetic shift in
the verifier")
b. use two cnum instead of one

Last of all we could keep sign and unsigned ranges, but convert them into cnum for all operations, then converting them back as this patchset does, spread to all operations beyond __reg_deduce_bounds; we should still get some simplification, just not sure if I am trying too hard at this point.

Quoted 5 lines

Hi Shung-Hsi,

Thank you for taking a look. I have a work-in-progress branch [1] which implements union and multiplication operators for wrapped intervals domain. I'll plug it into the verifier and share the results in this thread.

Thanks! Looking forward to the result.

Shung-Hsi

1: https://lore.kernel.org/bpf/[email protected]/
2: https://lore.kernel.org/all/[email protected]/

Quoted 4 lines

Thanks,
Eduard

[1] https://github.com/eddyz87/cnum-verif/tree/arithm-ops