[PATCH bpf v2 2/7] bpf: Preserve packet pointer class displacement in regsafe()

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

regsafe() maps packet pointer IDs between states and checks that each
current register range is a subset of the corresponding explored
register range. It does not, however, preserve the displacement between
registers that share a packet pointer ID.

This is unsound because packet range is shared by ID. A bounds check on
one class member updates every member, and a later access can consume the
range through another member. Commit 022ac0750883 ("bpf: use reg->var_off
instead of reg->off for pointers") folded the fixed pointer offset into
r64 and removed the old off equality check, so two individually narrower
registers can prune even when their displacement has changed. The
explored path can then license an out-of-bounds packet access on the
pruned path.

Requiring equal r64 bases would prevent the bug, but would also reject a
safe uniform translation of the whole class. Instead, record the base
translation seen for the first packet pointer in each ID mapping and
require every subsequent member to have the same translation. This keeps
the relative displacement invariant while retaining pruning for uniformly
translated classes. Packet pointers without an ID remain unaffected.

Fixes: 022ac0750883 ("bpf: use reg->var_off instead of reg->off for pointers")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 include/linux/bpf_verifier.h |  2 ++
 kernel/bpf/states.c          | 42 ++++++++++++++++++++++++++++++++++--
 2 files changed, 42 insertions(+), 2 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 36b65797877d..5cf92ce18520 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -854,6 +854,8 @@ struct backtrack_state {
 struct bpf_id_pair {
 	u32 old;
 	u32 cur;
+	s32 pkt_ptr_delta;
+	bool pkt_ptr_delta_set;
 };
 
 struct bpf_idmap {
diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 66fb11b6c6a7..2f8f3fe164b0 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -339,6 +339,7 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
 	if (idmap->cnt < BPF_ID_MAP_SIZE) {
 		map[idmap->cnt].old = old_id;
 		map[idmap->cnt].cur = cur_id;
+		map[idmap->cnt].pkt_ptr_delta_set = false;
 		idmap->cnt++;
 		return true;
 	}
@@ -352,6 +353,43 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
 	return false;
 }
 
+static bool check_pkt_ptr_ids(const struct bpf_reg_state *old,
+			      const struct bpf_reg_state *cur,
+			      struct bpf_idmap *idmap)
+{
+	struct bpf_id_pair *map = idmap->map;
+	s64 delta;
+	unsigned int i;
+
+	if (!check_ids(old->id, cur->id, idmap))
+		return false;
+	if (!old->id)
+		return true;
+
+	/*
+	 * Packet range is shared by all pointers with the same ID. Preserve
+	 * their relative displacement, while allowing the whole class to move.
+	 * Packet pointer offsets are bounded by BPF_MAX_VAR_OFF, so the delta
+	 * between two valid offsets fits in s32.
+	 */
+	delta = (s64)(cur->r64.base - old->r64.base);
+	if (delta < S32_MIN || delta > S32_MAX)
+		return false;
+
+	for (i = 0; i < idmap->cnt; i++) {
+		if (map[i].old != old->id)
+			continue;
+		if (!map[i].pkt_ptr_delta_set) {
+			map[i].pkt_ptr_delta = delta;
+			map[i].pkt_ptr_delta_set = true;
+			return true;
+		}
+		return map[i].pkt_ptr_delta == delta;
+	}
+
+	return false;
+}
+
 /*
  * Compare scalar register IDs for state equivalence.
  *
@@ -632,8 +670,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		} else if (rold->range > rcur->range) {
 			return false;
 		}
-		/* id relations must be preserved */
-		if (!check_ids(rold->id, rcur->id, idmap))
+		/* id relations and intra-class displacement must be preserved */
+		if (!check_pkt_ptr_ids(rold, rcur, idmap))
 			return false;
 		/* new val must satisfy old val knowledge */
 		return range_within(rold, rcur) &&
-- 
2.53.0