[PATCH bpf] bpf: harden bloom filter allocation sizing on 32-bit kernels

[PATCH bpf] bpf: harden bloom filter allocation sizing on 32-bit kernels

[Jérémy Jean]

bloom_map_alloc() can under-allocate bloom filter storage on 32-bit
kernels when the bitset size reaches the U32_MAX fallback case.

BITS_TO_BYTES(U32_MAX) is evaluated with 32-bit arithmetic and wraps to 0,
while bitset_mask remains U32_MAX. As a result, later bloom filter updates
can write beyond the allocated object.

I reached local privilege escalation using only this bug from a binary with
CAP_BPF.

Compute the bitset size from bitset_mask in u64 and check the final
allocation size before calling bpf_map_area_alloc().

Fixes: 9330986c0300 ("bpf: Add bloom filter map implementation")
Cc: bpf@vger.kernel.org
Signed-off-by: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>
---
 kernel/bpf/bloom_filter.c | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)

diff --git a/kernel/bpf/bloom_filter.c b/kernel/bpf/bloom_filter.c
index b73336c976b..8e6532fa418 100644
--- a/kernel/bpf/bloom_filter.c
+++ b/kernel/bpf/bloom_filter.c
@@ -94,9 +94,10 @@ static int bloom_map_alloc_check(union bpf_attr *attr)
 
 static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
 {
-	u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
+	u32 bitset_mask, nr_hash_funcs, nr_bits;
 	int numa_node = bpf_map_attr_numa_node(attr);
 	struct bpf_bloom_filter *bloom;
+	u64 bitset_bytes, alloc_size;
 
 	if (attr->key_size != 0 || attr->value_size == 0 ||
 	    attr->max_entries == 0 ||
@@ -127,23 +128,21 @@ static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
 	if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
 	    check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
 	    nr_bits > (1UL << 31)) {
-		/* The bit array size is 2^32 bits but to avoid overflowing the
-		 * u32, we use U32_MAX, which will round up to the equivalent
-		 * number of bytes
-		 */
-		bitset_bytes = BITS_TO_BYTES(U32_MAX);
 		bitset_mask = U32_MAX;
 	} else {
 		if (nr_bits <= BITS_PER_LONG)
 			nr_bits = BITS_PER_LONG;
 		else
 			nr_bits = roundup_pow_of_two(nr_bits);
-		bitset_bytes = BITS_TO_BYTES(nr_bits);
 		bitset_mask = nr_bits - 1;
 	}
 
+	bitset_bytes = BITS_TO_BYTES((u64)bitset_mask + 1);
 	bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long));
-	bloom = bpf_map_area_alloc(sizeof(*bloom) + bitset_bytes, numa_node);
+	if (check_add_overflow((u64)sizeof(*bloom), bitset_bytes, &alloc_size))
+		return ERR_PTR(-E2BIG);
+
+	bloom = bpf_map_area_alloc(alloc_size, numa_node);
 
 	if (!bloom)
 		return ERR_PTR(-ENOMEM);
-- 
2.47.3

Re: [PATCH bpf] bpf: harden bloom filter allocation sizing on 32-bit kernels

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:

Pre-existing issues:
- [Critical] The patch prevents a 0-byte allocation on 32-bit architectures, but fails to address a critical out-of-bounds access bug caused by negative indexing when `bitset_mask == U32_MAX`.
--

--- Patch [1]: [PATCH bpf] bpf: harden bloom filter allocation sizing on 32-bit kernels ---
commit 02e5a6622a3bf43a5a551fa2588059c5317afd7d
Author: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>

bpf: harden bloom filter allocation sizing on 32-bit kernels

This commit addresses an under-allocation issue for bloom filter maps on
32-bit kernels by computing the required bitset size using u64 arithmetic,
preventing an integer overflow during allocation.

> --- a/kernel/bpf/bloom_filter.c
> +++ b/kernel/bpf/bloom_filter.c
> @@ -127,23 +128,21 @@ static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
>  	if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
>  	    check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
>  	    nr_bits > (1UL << 31)) {
> -		/* The bit array size is 2^32 bits but to avoid overflowing the
> -		 * u32, we use U32_MAX, which will round up to the equivalent
> -		 * number of bytes
> -		 */
> -		bitset_bytes = BITS_TO_BYTES(U32_MAX);
>  		bitset_mask = U32_MAX;

[Severity: Critical]
This is a pre-existing issue, but does setting bitset_mask to U32_MAX leave
the map vulnerable to backward out-of-bounds accesses on 32-bit architectures?

When the map is accessed, the generated u32 hash is masked and passed to
test_bit() and set_bit():

kernel/bpf/bloom_filter.c:bloom_map_peek_elem() {
    ...
    if (!test_bit(h, bloom->bitset))
        return -ENOENT;
    ...
}

kernel/bpf/bloom_filter.c:bloom_map_push_elem() {
    ...
    set_bit(h, bloom->bitset);
    ...
}

On 32-bit systems, test_bit() and set_bit() expect a signed long index.
If the u32 hash value is greater than or equal to 0x80000000, it is
implicitly converted to a negative bit offset.

Because some architectures handle this as a signed offset relative to the
memory base, could this result in reading or writing memory before the
allocated bloom->bitset buffer and corrupting the bpf_bloom_filter struct?

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260731204917.3845309-1-Jeremy.Jean@oss.cyber.gouv.fr?part=1

Re: [PATCH bpf] bpf: harden bloom filter allocation sizing on 32-bit kernels

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 3855 bytes --]

> diff --git a/kernel/bpf/bloom_filter.c b/kernel/bpf/bloom_filter.c
> index b73336c976b7..8e6532fa4182 100644
> --- a/kernel/bpf/bloom_filter.c
> +++ b/kernel/bpf/bloom_filter.c
> @@ -94,9 +94,10 @@ static int bloom_map_alloc_check(union bpf_attr *attr)
>
>  static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
>  {
> -	u32 bitset_bytes, bitset_mask, nr_hash_funcs, nr_bits;
> +	u32 bitset_mask, nr_hash_funcs, nr_bits;
>  	int numa_node = bpf_map_attr_numa_node(attr);
>  	struct bpf_bloom_filter *bloom;
> +	u64 bitset_bytes, alloc_size;
>
>  	if (attr->key_size != 0 || attr->value_size == 0 ||
>  	    attr->max_entries == 0 ||
> @@ -127,23 +128,21 @@ static struct bpf_map *bloom_map_alloc(union bpf_attr *attr)
>  	if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) ||
>  	    check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) ||
>  	    nr_bits > (1UL << 31)) {
> -		/* The bit array size is 2^32 bits but to avoid overflowing the
> -		 * u32, we use U32_MAX, which will round up to the equivalent
> -		 * number of bytes
> -		 */
> -		bitset_bytes = BITS_TO_BYTES(U32_MAX);
>  		bitset_mask = U32_MAX;
>  	} else {
>  		if (nr_bits <= BITS_PER_LONG)
>  			nr_bits = BITS_PER_LONG;
>  		else
>  			nr_bits = roundup_pow_of_two(nr_bits);
> -		bitset_bytes = BITS_TO_BYTES(nr_bits);
>  		bitset_mask = nr_bits - 1;
>  	}
>
> +	bitset_bytes = BITS_TO_BYTES((u64)bitset_mask + 1);
>  	bitset_bytes = roundup(bitset_bytes, sizeof(unsigned long));
> +	if (check_add_overflow((u64)sizeof(*bloom), bitset_bytes, &alloc_size))
> +		return ERR_PTR(-E2BIG);
> +

Can this overflow check ever trigger? Once bitset_bytes is computed in
u64, bitset_mask is at most U32_MAX, so:

    bitset_bytes = BITS_TO_BYTES(0x100000000) = 0x20000000

and roundup(0x20000000, sizeof(unsigned long)) is 0x20000000 (already
word-aligned), i.e. 512 MiB. The sizeof(struct bpf_bloom_filter) addend
is a few hundred bytes. The sum is around 2^29 against a u64 range of
2^64-1, leaving roughly 1.8e19 of headroom, so __builtin_add_overflow()
on the two u64 operands cannot report overflow on any path or arch.

The else branch is even smaller: nr_bits is capped at 2^31 by the
`nr_bits > (1UL << 31)` test above, giving at most 0x10000000 bytes.

If the intent is a real size cap, the check needs to compare bitset_bytes
or alloc_size against a concrete limit. If the intent is only to make the
sizing arithmetic overflow-proof, the u64 change already accomplishes that
on its own and the overflow check can be dropped.

In the commit message:

>     bloom_map_alloc() can under-allocate bloom filter storage on 32-bit
>     kernels when the bitset size reaches the U32_MAX fallback case.
>
>     BITS_TO_BYTES(U32_MAX) is evaluated with 32-bit arithmetic and wraps to 0,
>     while bitset_mask remains U32_MAX. As a result, later bloom filter updates
>     can write beyond the allocated object.
>
>     I reached local privilege escalation using only this bug from a binary with
>     CAP_BPF.
>
>     Compute the bitset size from bitset_mask in u64 and check the final
>     allocation size before calling bpf_map_area_alloc().
                                                         ^^^^

Does the second half of this sentence match what the patch does? The
patch checks whether a u64 addition overflows, which cannot happen given
bitset_bytes is bounded at 0x20000000. No bound on alloc_size is
introduced, so nothing new is rejected for being too large.

The first half of the sentence is accurate and is the entire fix:
computing bitset_bytes from bitset_mask in u64 is what removes the ILP32
truncation.


---
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/30666682414