Re: [PATCH bpf-next v2 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:
- [Critical] Incomplete bounds check in `bpf_strpbrk` allows pointer wraparound and out-of-bounds reads.
- [High] Unoptimized O(N*M) nested loop in `bpf_strpbrk` causes CPU exhaustion and Denial of Service.

Pre-existing issues:
- [Critical] Incomplete bounds checks in pre-existing string kfuncs allow pointer wraparound and arbitrary memory reads.
- [High] Pre-existing string kfuncs (`bpf_strcspn`, `bpf_strspn`, `bpf_strnstr`, etc.) contain O(N*M) nested loops vulnerable to CPU exhaustion.
--

commit eccea6a6a708ac6a6e30a1e094434ed92118f8f0
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 if no
match is found.

> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c

[ ... ]

> +__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)) {

[Severity: Critical]
Since the __ign suffix allows arbitrary scalar values as pointers, could
checking only the first byte allow a pointer near ULONG_MAX
(e.g. ULONG_MAX - 5) to pass this validation?

Because the loop below increments the pointer up to XATTR_SIZE_MAX times,
it appears the pointer could wrap around to user space (0). Since
__get_kernel_nofault() uses __get_user(), could this allow reading
arbitrary user-space memory, bypassing security boundaries?

[Severity: Critical]
This is a pre-existing issue, but other string functions like bpf_strcspn()
and __bpf_strnstr() use this same 1-byte validation pattern.

In __bpf_strnstr(), accessing s1 + i + j can reach up to 131,070 bytes past
the start pointer, bypassing mmap_min_addr and allowing direct user space
memory reads from within BPF. Could this be updated across all string kfuncs
to validate the entire memory range being accessed?

> +		return -ERANGE;
> +	}
> +
> +	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++) {

[Severity: High]
Does this nested loop introduce a potential CPU stall or soft lockup?

If a BPF program passes 64KB strings for both s__ign and accept__ign where
no characters match and the null terminator is placed near the end of
accept__ign, the outer loop could execute 65,536 times with the inner loop
executing ~65,535 times per iteration.

With page faults disabled via guard(pagefault)(), could this lead to
~4.29 billion memory accesses, potentially causing a Denial of Service?

[Severity: High]
This is a pre-existing issue, but other kfuncs like bpf_strcspn() and
bpf_strspn() also contain these XATTR_SIZE_MAX nested loops.

Could crafted strings force those inner loops to run fully for every
iteration of the outer loop, causing the same CPU exhaustion? Is there a
way to optimize these searches or limit the execution time?

> +			__get_kernel_nofault(&ca, accept__ign + j, char, err_out);
> +			if (ca == '\0')
> +				break;
> +			if (cs == ca)
> +				return i;
> +		}

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