Re: [PATCH bpf-next v2 5/5] selftests/bpf: add tests for bpf_strpbrk

[sashiko-bot@kernel.org]

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

Pre-existing issues:
- [High] The string search kfuncs (bpf_strpbrk, bpf_strspn, bpf_strcspn) have an O(N*M) algorithmic complexity that can trigger up to 4.29 billion memory reads in the kernel, stalling the CPU. The newly added tests explicitly mask this vulnerability.
--

commit 8efd73628e6ad8d84061c17ed578ece973a232c2
Author: Longjun Tang <tanglongjun@kylinos.cn>

selftests/bpf: add tests for bpf_strpbrk
    
Add functional tests for first-match, multiple-match, not-found, and
empty-accept cases. Add negative tests for NULL, user-space, and
invalid kernel pointer arguments.

> diff --git a/tools/testing/selftests/bpf/progs/string_kfuncs_failure2.c b/tools/testing/selftests/bpf/progs/string_kfuncs_failure2.c
> index 412c53b87b182..d3b978e453bd7 100644
> --- a/tools/testing/selftests/bpf/progs/string_kfuncs_failure2.c
> +++ b/tools/testing/selftests/bpf/progs/string_kfuncs_failure2.c
> @@ -19,6 +19,8 @@ SEC("syscall") int test_strspn_str_too_long(void *ctx) { return bpf_strspn(long_
>  SEC("syscall") int test_strspn_accept_too_long(void *ctx) { return bpf_strspn("b", long_str); }
>  SEC("syscall") int test_strcspn_str_too_long(void *ctx) { return bpf_strcspn(long_str, "b"); }
>  SEC("syscall") int test_strcspn_reject_too_long(void *ctx) { return bpf_strcspn("b", long_str); }
> +SEC("syscall") int test_strpbrk_str_too_long(void *ctx) { return bpf_strpbrk(long_str, "z"); }
> +SEC("syscall") int test_strpbrk_accept_too_long(void *ctx) { return bpf_strpbrk("b", long_str); }

[Severity: High]
This is a pre-existing issue, but by only testing a single large string
against a 1-byte string, do these tests mask an O(N*M) algorithmic
complexity in the underlying implementation?

Looking at the nested loops in bpf_strpbrk():

kernel/bpf/helpers.c:bpf_strpbrk() {
	...
	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);
	...
}

Since XATTR_SIZE_MAX is 65536, if a BPF program passes two 64KB buffers
constructed to avoid early loop termination (e.g., no matching characters
and a null-terminator only at the very end of the inner string), couldn't
the function perform up to 4.29 billion calls to __get_kernel_nofault()?

Could this stall the CPU for several seconds, bypassing BPF execution time
limits and potentially triggering a watchdog soft-lockup?

Would it be worth adding a test case that passes long_str for both arguments
to expose how the kernel handles this worst-case scenario?

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