Skip to contentSkip to conversation

inetpeer: harden tree sizing and address side-channel eviction

PATCH In review Eric Dumazet 1 participant 5 messages Aug 12 – Aug 14

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover inetpeer: harden tree sizing and address side-channel eviction

This series addresses a vulnerability in the inetpeer subsystem where an off-path adversary can manipulate garbage collection to bypass IP-keyed ICMP rate limits, and hardens inetpeer memory usage under pressure.

The inetpeer rate limiting system stores peer entries in an RB-tree keyed deterministically by remote IP address. Because tree lookups walk the tree using lexicographical comparison (inetpeer_addr_cmp), an off-path attacker can predict the tree topology and the exact sequence of nodes traversed during lookups (the gc_stack candidate list). By combining predictable traversal with aggressive garbage collection triggered when the tree size exceeds inet_peer_threshold, an attacker can selectively force the eviction of targeted inet_peer nodes. When an evicted node is recreated on the next packet, its rate-limiting token bucket is reset to full capacity, creating a side-channel to bypass ICMP rate limits and probe for open UDP ports.

- Patch 1 enforces a hard limit on inet_peer allocations at 2x inet_peer_threshold to prevent unbounded slab memory growth if GC cannot free entries, and ensures inet_peer_xrlim_allow() fails closed (returns false) if peer allocation fails and returns NULL.

- Patch 2 randomizes RB-tree node ordering using SipHash with a secret boot-time key (inetpeer_hash_key), making tree layout and GC eviction paths unpredictable to off-path attackers.

Eric Dumazet (2):
inetpeer: enforce hard limit on tree size and fix NULL peer rate limit
inetpeer: randomize RB-tree node comparison using SipHash

 include/net/inetpeer.h |  4 ++++
 net/ipv4/inetpeer.c    | 43 +++++++++++++++++++++++++++++++++++++-----
 2 files changed, 42 insertions(+), 5 deletions(-)
Signature · 1 line
2.55.0.691.gc56d675ccc-goog
#1 lore raw

PATCH 1/2 inetpeer: enforce hard limit on tree size and fix NULL peer rate limit

Currently, inet_peer_threshold is used to trigger aggressive garbage collection when tree size reaches the threshold. However, if garbage collection is unable to reclaim candidate entries (e.g. due to held references or active fragment queues), base->total can grow without any upper bound, consuming excessive slab memory.

Fix this by enforcing a hard limit on inet_peer allocations when (u64)base->total reaches 2ULL * READ_ONCE(inet_peer_threshold). Casting to 64-bit unsigned avoids signed integer overflow if inet_peer_threshold is configured to large values via sysctl.

Additionally, when peer allocation fails and returns NULL, inet_peer_xrlim_allow() previously returned true, allowing packets without rate limiting. Fix this to return false when peer is NULL, ensuring rate limiting fails closed under memory pressure.

Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")
---
 net/ipv4/inetpeer.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
net/ipv4/inetpeer.c +3 -2
index 5b957a831e7c39f2e9b224469f0eba4703833475..1e2bd1c522326c9ba14c3ceeb8e934f703b827a5 100644
@@ -192,7 +192,8 @@ struct inet_peer *inet_getpeer(struct inet_peer_base *base,
 	gc_cnt = 0;
 	p = lookup(daddr, base, seq, gc_stack, &gc_cnt, &parent, &pp);
 	if (!p) {
-		p = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);
+		if ((u64)base->total < 2ULL * READ_ONCE(inet_peer_threshold))
+			p = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);
 		if (p) {
 			p->daddr = *daddr;
 			p->dtime = (__u32)jiffies;
@@ -248,7 +249,7 @@ bool inet_peer_xrlim_allow(struct inet_peer *peer, int timeout)
 	bool rc = false;
 
 	if (!peer)
-		return true;
+		return false;
 
 	token = otoken = READ_ONCE(peer->rate_tokens);
 	now = jiffies;
Signature · 1 line
2.55.0.691.gc56d675ccc-goog
#2 lore raw

Re: [PATCH net 1/2] inetpeer: enforce hard limit on tree size and fix NULL peer rate limit

Quoted 17 lines · Eric Dumazet

Currently, inet_peer_threshold is used to trigger aggressive garbage collection when tree size reaches the threshold. However, if garbage collection is unable to reclaim candidate entries (e.g. due to held references or active fragment queues), base->total can grow without any upper bound, consuming excessive slab memory.

Fix this by enforcing a hard limit on inet_peer allocations when (u64)base->total reaches 2ULL * READ_ONCE(inet_peer_threshold). Casting to 64-bit unsigned avoids signed integer overflow if inet_peer_threshold is configured to large values via sysctl.

Additionally, when peer allocation fails and returns NULL, inet_peer_xrlim_allow() previously returned true, allowing packets without rate limiting. Fix this to return false when peer is NULL, ensuring rate limiting fails closed under memory pressure.

Quoted 4 lines
Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")

---

I will drop this patch, sashiko is not happy and I do not really care.

pw-bot: cr

#3 lore raw

PATCH 2/2 inetpeer: randomize RB-tree node comparison using SipHash

In reply to Eric Dumazet

The inetpeer rate limiting system stores peer entries in a Red-Black tree keyed deterministically on the remote IP address. Because tree lookups walk the RB-tree using standard lexicographical comparisons (inetpeer_addr_cmp), an off-path adversary can predict the exact topology of the tree and the sequence of nodes traversed during lookups (the gc_stack candidate list).

By combining deterministic tree traversal with aggressive garbage collection (triggered when tree size exceeds inet_peer_threshold), an attacker can selectively force the eviction of targeted inet_peer nodes. When an evicted node is subsequently re-created upon receiving a new packet, its rate-limiting token bucket (rate_tokens, rate_last) is reset to full capacity. This creates a side-channel primitive allowing off-path attackers to bypass IP-keyed ICMP rate limits and infer open UDP ports (similar to SAD DNS style attacks).

Mitigate this by randomizing the RB-tree node comparison logic using SipHash with a secret boot-time key (inetpeer_hash_key). Nodes are ordered in the tree by SipHash(addr, key) rather than raw IP addresses. Because the secret key is unknown to external entities, the tree layout and lookup traversal paths are unpredictable to off-path adversaries, breaking the deterministic eviction gadget.

Cache the computed 64-bit SipHash (hash) in struct inet_peer and compute the target hash (dhash) once at the beginning of inet_getpeer() to avoid recomputing SipHash at every step of the RB-tree walk.

Fixes b145425f269a ("inetpeer: remove AVL implementation in favor of RB tree")
---
 include/net/inetpeer.h |  4 ++++
 net/ipv4/inetpeer.c    | 38 +++++++++++++++++++++++++++++++++++---
 2 files changed, 39 insertions(+), 3 deletions(-)
include/net/inetpeer.h +4 -0
index f475757daafba998a10c815d0178c98d2bf1ae43..414e9adf4c51145f14313993f04d1f47c0aaa07d 100644
@@ -35,6 +35,7 @@ struct inetpeer_addr {
 
 struct inet_peer {
 	struct rb_node		rb_node;
+	u64			hash;
 	struct inetpeer_addr	daddr;
 
 	u32			metrics[RTAX_MAX];
@@ -125,6 +126,9 @@ static inline int inetpeer_addr_cmp(const struct inetpeer_addr *a,
 {
 	int i, n;
 
+	if (a->family != b->family)
+		return a->family < b->family ? -1 : 1;
+
 	if (a->family == AF_INET)
 		n = sizeof(a->a4) / sizeof(u32);
 	else
net/ipv4/inetpeer.c +35 -3
index 1e2bd1c522326c9ba14c3ceeb8e934f703b827a5..96871f52010f330e2ce7f60ad375178e8eac290c 100644
@@ -21,6 +21,7 @@
 #include <net/ip.h>
 #include <net/inetpeer.h>
 #include <net/secure_seq.h>
+#include <linux/siphash.h>
 
 /*
  *  Theory of operations.
@@ -52,6 +53,32 @@
  */
 
 static struct kmem_cache *peer_cachep __ro_after_init;
+static siphash_aligned_key_t inetpeer_hash_key __read_mostly;
+
+static u64 inetpeer_addr_hash(const struct inetpeer_addr *a)
+{
+	if (a->family == AF_INET)
+		return siphash_2u32((__force u32)a->a4.addr, a->a4.vif,
+				    &inetpeer_hash_key);
+
+	return siphash_4u32((__force u32)a->a6.s6_addr32[0],
+			    (__force u32)a->a6.s6_addr32[1],
+			    (__force u32)a->a6.s6_addr32[2],
+			    (__force u32)a->a6.s6_addr32[3],
+			    &inetpeer_hash_key);
+}
+
+static int inetpeer_entry_cmp(u64 dhash,
+			      const struct inetpeer_addr *daddr,
+			      const struct inet_peer *p)
+{
+	if (dhash < p->hash)
+		return -1;
+	if (dhash > p->hash)
+		return 1;
+
+	return inetpeer_addr_cmp(daddr, &p->daddr);
+}
 
 void inet_peer_base_init(struct inet_peer_base *bp)
 {
@@ -73,6 +100,8 @@ void __init inet_initpeers(void)
 {
 	u64 nr_entries;
 
+	get_random_bytes(&inetpeer_hash_key, sizeof(inetpeer_hash_key));
+
 	 /* 1% of physical memory */
 	nr_entries = div64_ul((u64)totalram_pages() << PAGE_SHIFT,
 			      100 * L1_CACHE_ALIGN(sizeof(struct inet_peer)));
@@ -84,6 +113,7 @@ void __init inet_initpeers(void)
 
 /* Called with rcu_read_lock() or base->lock held */
 static struct inet_peer *lookup(const struct inetpeer_addr *daddr,
+				u64 dhash,
 				struct inet_peer_base *base,
 				unsigned int seq,
 				struct inet_peer *gc_stack[],
@@ -105,7 +135,7 @@ static struct inet_peer *lookup(const struct inetpeer_addr *daddr,
 			break;
 		parent = next;
 		p = rb_entry(parent, struct inet_peer, rb_node);
-		cmp = inetpeer_addr_cmp(daddr, &p->daddr);
+		cmp = inetpeer_entry_cmp(dhash, daddr, p);
 		if (cmp == 0) {
 			now = jiffies;
 			if (READ_ONCE(p->dtime) != now)
@@ -170,6 +200,7 @@ struct inet_peer *inet_getpeer(struct inet_peer_base *base,
 			       const struct inetpeer_addr *daddr)
 {
 	struct inet_peer *p, *gc_stack[PEER_MAX_GC];
+	u64 dhash = inetpeer_addr_hash(daddr);
 	struct rb_node **pp, *parent;
 	unsigned int gc_cnt, seq;
 
@@ -177,7 +208,7 @@ struct inet_peer *inet_getpeer(struct inet_peer_base *base,
 	 * Because of a concurrent writer, we might not find an existing entry.
 	 */
 	seq = read_seqbegin(&base->lock);
-	p = lookup(daddr, base, seq, NULL, &gc_cnt, &parent, &pp);
+	p = lookup(daddr, dhash, base, seq, NULL, &gc_cnt, &parent, &pp);
 
 	/* Make sure tree was not modified during our lookup. */
 	if (p && !read_seqretry(&base->lock, seq))
@@ -190,12 +221,13 @@ struct inet_peer *inet_getpeer(struct inet_peer_base *base,
 	write_seqlock_bh(&base->lock);
 
 	gc_cnt = 0;
-	p = lookup(daddr, base, seq, gc_stack, &gc_cnt, &parent, &pp);
+	p = lookup(daddr, dhash, base, seq, gc_stack, &gc_cnt, &parent, &pp);
 	if (!p) {
 		if ((u64)base->total < 2ULL * READ_ONCE(inet_peer_threshold))
 			p = kmem_cache_alloc(peer_cachep, GFP_ATOMIC);
 		if (p) {
 			p->daddr = *daddr;
+			p->hash = dhash;
 			p->dtime = (__u32)jiffies;
 			refcount_set(&p->refcnt, 1);
 			atomic_set(&p->rid, 0);
Signature · 1 line
2.55.0.691.gc56d675ccc-goog
#4 lore raw

Re: [PATCH net 2/2] inetpeer: randomize RB-tree node comparison using SipHash

Quoted 26 lines · Eric Dumazet

The inetpeer rate limiting system stores peer entries in a Red-Black tree keyed deterministically on the remote IP address. Because tree lookups walk the RB-tree using standard lexicographical comparisons (inetpeer_addr_cmp), an off-path adversary can predict the exact topology of the tree and the sequence of nodes traversed during lookups (the gc_stack candidate list).

By combining deterministic tree traversal with aggressive garbage collection (triggered when tree size exceeds inet_peer_threshold), an attacker can selectively force the eviction of targeted inet_peer nodes. When an evicted node is subsequently re-created upon receiving a new packet, its rate-limiting token bucket (rate_tokens, rate_last) is reset to full capacity. This creates a side-channel primitive allowing off-path attackers to bypass IP-keyed ICMP rate limits and infer open UDP ports (similar to SAD DNS style attacks).

Mitigate this by randomizing the RB-tree node comparison logic using SipHash with a secret boot-time key (inetpeer_hash_key). Nodes are ordered in the tree by SipHash(addr, key) rather than raw IP addresses. Because the secret key is unknown to external entities, the tree layout and lookup traversal paths are unpredictable to off-path adversaries, breaking the deterministic eviction gadget.

Cache the computed 64-bit SipHash (hash) in struct inet_peer and compute the target hash (dhash) once at the beginning of inet_getpeer() to avoid recomputing SipHash at every step of the RB-tree walk.

Quoted 5 lines
Fixes b145425f269a ("inetpeer: remove AVL implementation in favor of RB tree")

---

I will send a V2 to address sashiko's feedback (
https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260812205946.356185-1-edumazet%40google.com
)

pw-bot: cr