Hi Pablo,
Sorry, the description was too terse. Answering both mails here.
There is no memory safety issue, and I should have said so explicitly.
It is a correctness problem: after GC the set no longer holds what was
committed, and the packet path matches keys that were never added.
Exact sequence, raw nfnetlink. The set has NFT_SET_INTERVAL |
NFT_SET_TIMEOUT, an ipv4_addr key, no default timeout, and
NFTA_SET_GC_INTERVAL = 3600000, so the commit-time scan does not run and
only the insertion path is involved.
Batch 1 (NEWSETELEM): start 10 with a 50ms timeout, end 20 with no
timeout, start 30 and end 40 with no timeout. Only start 10 expires;
[30,40) is permanent.
Wait 200ms.
Batch 2: DELSETELEM of end 20 only, then NEWSETELEM of [12,13). This is
not something nft(8) generates, but the kernel accepts it. Inserting 12
runs nft_rbtree_gc_elem() on the expired start 10. The walk skips end
20 because it is being deleted in this transaction, passes start 30 and
takes end 40 as the end of 10. 10 and 40 are removed, and start 30 is
left without an end.
At commit, nft_rbtree_commit() turns 30 into an interval with ->from =
30 and ->to = NULL, and nft_array_lookup_cmp() treats ->to == NULL as
open-ended. So nft_rbtree_lookup() matches every key >= 30, while
userspace believes the set holds only [30,40). Reading back with
GETSETELEM, which uses the same array: without the patch 45 is found,
end 40 is gone and deleting [30,40) fails with ENOENT; with the patch
45 is not found, 40 is present and the delete succeeds.
To be fair about the limits: the only trigger I have is crafted
nfnetlink from whoever already owns the ruleset (CAP_NET_ADMIN in that
netns), so it does not cross a privilege boundary, and I have not found
an nft(8) command sequence that reaches the insertion-path case. The
commit-path case (nft_rbtree_gc_scan() not clearing rbe_end) uses a
different sequence without the lone end delete; I can send it in the
same detail if useful.
If you consider sets built from such batches unsupported, I think the
better fix is to reject deleting a lone interval end element, and I can
send that instead; or drop this if it is not worth the churn.
Thanks,
Joas
Em sáb., 31 de out. de 2026 às 14:50, Pablo Neira Ayuso
[off-list ref] escreveu:
On Sat, Oct 31, 2026 at 06:44:43PM +0100, Pablo Neira Ayuso wrote:
quoted
On Sat, Oct 31, 2026 at 03:54:05PM +0000, Joas Antonio dos Santos via B4 Relay wrote:
quoted
From: Joas Antonio dos Santos <redacted>
Garbage collection of an expired interval start element also removes its
end element. Both the insertion path, nft_rbtree_gc_elem(), and the
commit path, nft_rbtree_gc_scan(), find that end element by its position
in the tree, and both can pick the end element of a different, live
interval:
- nft_rbtree_gc_elem() walks towards higher keys and skips end elements
that are not active in both generations. If the end element of the
expired interval is being deleted in the same transaction, the walk
skips it, passes the start element of the next interval and takes that
interval's end element instead.
- nft_rbtree_gc_scan() remembers the last end element it visited in
rbe_end, but does not clear it when it visits a live start element. An
expired start element without an end element (a start-only element, or
an interval whose end element was already removed) then takes the end
element of the live interval above it.
In both cases the live interval [S, E) loses E: the set no longer holds
the interval that userspace added, and deleting [S, E) later fails with
ENOENT.
In the insertion path, stop the walk at the first element that is active
in the current generation. Elements added by this transaction are still
skipped, as intended by commit 60c0c230c6f0 ("netfilter: nft_set_rbtree:
skip end interval element from gc"). If that element is a start element,
the expired interval has no end element. If it is an end element that
this transaction is removing, leave it to the transaction. In the commit
path, clear rbe_end when a live start element is visited.
Reproduced on current mainline under QEMU (arm64, KASAN), from an
unprivileged user in a new user and network namespace:
- insertion path: add [10,20) with a 50ms timeout and [30,40), wait,
then in one batch delete the end element 20 and add [12,13).
I don't follow.
You add [10,20) with 50ms...
and [30,40) with... what timeout?
you wait how long?
You follow up with another batch an you only delete 20?
quoted
Before: a GET for 45 finds an element, the end element 40 is gone and
deleting [30,40) fails with ENOENT. After: 45 is not found, 40 is
present and the delete succeeds.
- commit path: add [30,40) and a start-only element 10 with a 50ms
timeout to a set with a 100ms gc interval, wait, then add [200,201),
whose insertion walk stops at the highest element, so only the
commit-time scan reaches 10. Before: the end element 40 is gone and
deleting [30,40) fails with ENOENT. After: both work.
Normal expiry, and a new interval whose end element shares the key of an
expired start element (the case handled by 60c0c230c6f0), behave the same
before and after. About 39000 random batches on interval sets with
timeouts, with and without slab/page allocation fault injection, showed
no KASAN, lockdep or WARN reports with the patch applied.
Hm, no KASAN, no splat, what's the issue, really?
quoted
quoted
The insertion path issue was found with a small nfnetlink fuzzer. Both
paths had been pointed out earlier by the netdev AI review of commit
86b6471e690c ("netfilter: nft_set_rbtree: skip transaction elements
during GC"), see the Link below.
Fixes: f718863aca46 ("netfilter: nft_set_rbtree: fix overlap expiration walk")
Fixes: 8d8540c4f5e0 ("netfilter: nft_set_rbtree: add timeout support")
Link: https://lore.kernel.org/all/179063970372.3145.17414936987144600093@kernel.org/ (local)
Signed-off-by: Joas Antonio dos Santos <redacted>
---
Tool-use note: the fuzzer, the directed tests and the analysis were
prepared with help from an LLM-based assistant; I reviewed the change
and built and ran all tests myself. Test harness available on request.
This is a resend through the kernel.org web endpoint: my earlier
submission of this patch was blocked by my mail provider and never
reached the lists.
---
net/netfilter/nft_set_rbtree.c | 23 +++++++++++++++++++----
1 file changed, 19 insertions(+), 4 deletions(-)
diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index fbe1750f1..086823067 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -215,17 +215,25 @@ nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv,
struct nft_set *set = (struct nft_set *)__set;
struct rb_node *prev = rb_prev(&rbe->node);
struct net *net = read_pnet(&set->net);
+ u8 cur_genmask = nft_genmask_cur(net);
struct nft_rbtree_elem *rbe_prev;
/* search for end interval coming before this element.
* end intervals don't carry a timeout extension, they
* are coupled with the interval start element.
+ *
+ * Skip elements added in this transaction. The first element
+ * that is active in the current generation is either the end
+ * element of this interval or the start element of another
+ * interval, in which case this interval has no end element.
*/
while (prev) {
rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node);
- if (nft_rbtree_interval_end(rbe_prev) &&
- nft_set_elem_active(&rbe_prev->ext, NFT_GENMASK_ANY))
+ if (nft_set_elem_active(&rbe_prev->ext, cur_genmask)) {
+ if (!nft_rbtree_interval_end(rbe_prev))
+ prev = NULL;
break;
+ }
prev = rb_prev(prev);
}@@ -233,7 +241,11 @@ nft_rbtree_gc_elem(const struct nft_set *__set, struct nft_rbtree *priv,
rbe_prev = NULL;
if (prev) {
rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node);
- nft_rbtree_gc_elem_move(net, set, priv, rbe_prev);
+ /* end element is being removed by this transaction */
+ if (nft_set_elem_active(&rbe_prev->ext, NFT_GENMASK_ANY))
+ nft_rbtree_gc_elem_move(net, set, priv, rbe_prev);
+ else
+ rbe_prev = NULL;
}
nft_rbtree_gc_elem_move(net, set, priv, rbe);@@ -911,8 +923,11 @@ static void nft_rbtree_gc_scan(struct nft_set *set)
rbe_end = rbe;
continue;
}
- if (!__nft_set_elem_expired(&rbe->ext, tstamp))
+ if (!__nft_set_elem_expired(&rbe->ext, tstamp)) {
+ /* rbe_end belongs to this live interval */
+ rbe_end = NULL;
continue;
+ }
/* end element needs to be removed first, it has
* no timeout extension.
---
base-commit: c339f4010dea8b0d754f84ace70cd1b089878ef8
change-id: 20261031-b4-nft-rbtree-gc-1d9c72dba2bd
Best regards,
--
Joas Antonio dos Santos [off-list ref]
--
Joas Antonio dos Santos
Cyber Security Specialist and Ethical Hacker
joasantonio108@gmail.com
LinkedIn