Re: [PATCH bpf-next 4/5] bpf: add bpf_strpbrk kfunc

[sashiko-bot@kernel.org]

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

New issues:
- [High] O(N*M) worst-case time complexity in `bpf_strpbrk` allows for unprivileged CPU soft lockup, bypassing BPF verifier limits.
- [High] The validation of `s__ign` and `accept__ign` only checks the first byte, allowing pointers to wrap around the address space boundary.
- [Low] Duplicate `bpf_memcmp` kernel-doc block mistakenly included before `bpf_strpbrk`.

Pre-existing issues:
- [High] O(N^2) worst-case time complexity in `bpf_strcspn` allows for unprivileged CPU soft lockup.
--

commit 6710699312c85ee398aba5d00ff7694b56ae2a3c
Author: Longjun Tang <tanglongjun@kylinos.cn>

bpf: add bpf_strpbrk kfunc

Add bpf_strpbrk() that returns the index of the first character in a
string matching any character from the accept set, or -ENOENT.
Complements the existing strspn/strcspn kfuncs for string tokenization.
Registered in common_btf_ids.

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index e444c58cad9e9..34b7a9993c0c9 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -4070,6 +4070,67 @@ __bpf_kfunc int bpf_strcspn(const char *s__ign, const char *reject__ign)

[Severity: High]
This is a pre-existing issue, but does bpf_strcspn() have a similar
time complexity issue?

Looking at the existing bpf_strcspn() in kernel/bpf/helpers.c:

__bpf_kfunc int bpf_strcspn(const char *s__ign, const char *reject__ign)
{
	...
	guard(pagefault)();
	for (i = 0; i < XATTR_SIZE_MAX; i++) {
		__get_kernel_nofault(&cs, s__ign, char, err_out);
		...
		for (j = 0; j < XATTR_SIZE_MAX; j++) {
			__get_kernel_nofault(&cr, reject__ign + j, char, err_out);
			...
		}
		...
	}
	...
}

Like the new bpf_strpbrk() function, calling bpf_strcspn() with two long
strings that share no characters could also result in roughly 4 billion memory
reads while page faults are disabled. Could this also cause a multi-second CPU
stall per call?

>  	return -EFAULT;
>  }
>  
> +/**
> + * bpf_memcmp - Compare two memory regions byte by byte
> + * @ptr1__ign: First memory region
> + * @ptr2__ign: Second memory region
> + * @size: Number of bytes to compare
> + *
> + * Compares the first @size bytes of the memory areas @ptr1__ign and
> + * @ptr2__ign. Unlike bpf_strcmp, null bytes do not terminate the comparison.
> + *
> + * Return:
> + * * %0       - The memory regions are equal
> + * * %-1      - @ptr1__ign is less than @ptr2__ign
> + * * %1       - @ptr1__ign is greater than @ptr2__ign
> + * * %-EFAULT - Cannot read one of the memory regions
> + * * %-E2BIG  - @size exceeds the maximum allowed size
> + * * %-ERANGE - One of the memory regions is outside of kernel address space
> + */

[Severity: Low]
This isn't a bug, but it looks like the kernel-doc block for bpf_memcmp() was
accidentally duplicated here instead of providing documentation for the new
bpf_strpbrk() kfunc.

> +/**
> + * bpf_strpbrk - Find the first occurrence of a set of characters in a string
> + * @s__ign: The string to be searched
> + * @accept__ign: The string containing the characters to search for
> + *
> + * Return:
> + * * >=0      - Index of the first character in @s__ign that matches any
> + *              character in @accept__ign
> + * * %-ENOENT - No character of @accept__ign found in @s__ign
> + * * %-EFAULT - Cannot read one of the strings
> + * * %-E2BIG  - One of the strings is too large
> + * * %-ERANGE - One of the strings is outside of kernel address space
> + */
> +__bpf_kfunc int bpf_strpbrk(const char *s__ign, const char *accept__ign)
> +{
> +	char cs, ca;
> +	int i, j;
> +
> +	if (!copy_from_kernel_nofault_allowed(s__ign, 1) ||
> +	    !copy_from_kernel_nofault_allowed(accept__ign, 1)) {
> +		return -ERANGE;
> +	}

[Severity: High]
Does this validation prevent pointers from wrapping around the address space
boundary?

Since only 1 byte is checked here by copy_from_kernel_nofault_allowed(), but
the function reads up to XATTR_SIZE_MAX bytes in the loop below, if a caller
passes a pointer near the end of the address space (such as ULONG_MAX - 10),
could the pointer increment and wrap around to 0x0?

This could allow a BPF program to bypass the kernel memory isolation boundary
and read user-space memory instead of kernel memory.

> +
> +	guard(pagefault)();
> +	for (i = 0; i < XATTR_SIZE_MAX; i++) {
> +		__get_kernel_nofault(&cs, s__ign, char, err_out);
> +		if (cs == '\0')
> +			return -ENOENT;
> +		for (j = 0; j < XATTR_SIZE_MAX; j++) {
> +			__get_kernel_nofault(&ca, accept__ign + j, char, err_out);
> +			if (ca == '\0')
> +				break;
> +			if (cs == ca)
> +				return i;
> +		}
> +		if (j == XATTR_SIZE_MAX)
> +			return -E2BIG;
> +		s__ign++;
> +	}

[Severity: High]
Can this nested loop cause a CPU soft lockup?

Because both loops iterate up to XATTR_SIZE_MAX (65536) times, calling this
with two long strings that don't share any characters could result in over
4 billion memory accesses via __get_kernel_nofault().

Since guard(pagefault)() disables page faults and preemption, could this stall
the CPU for several seconds and bypass the BPF verifier's execution time
limits?

> +	return -E2BIG;
> +err_out:
> +	return -EFAULT;
> +}

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260623030803.44798-1-lange_tang@163.com?part=4