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

[sashiko-bot@kernel.org]

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

New issues:
- [Low] The selftests for bpf_strpbrk lack negative tests for the -E2BIG (too long string) error paths, leaving this core logic completely untested.
- [Low] The test `test_strpbrk_found_multiple` does not actually test a multiple-match scenario as claimed in the commit message.

Pre-existing issues:
- [High] O(N*M) algorithmic complexity in string kfuncs (bpf_strpbrk, bpf_strspn, bpf_strcspn) allows a malicious BPF program to stall the CPU and cause a Denial of Service.
--

commit a3423f682404351839c3773b03881a48a31cc20c
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_success.c b/tools/testing/selftests/bpf/progs/string_kfuncs_success.c
> index c2be9edcd2821..e67b80ab3cd2c 100644
> --- a/tools/testing/selftests/bpf/progs/string_kfuncs_success.c
> +++ b/tools/testing/selftests/bpf/progs/string_kfuncs_success.c
[ ... ]
> @@ -63,6 +64,13 @@ __test(-ENOENT) int test_strncasestr_notfound2(void *ctx) { return bpf_strncases
>  __test(-ENOENT) int test_strncasestr_notfound3(void *ctx) { return bpf_strncasestr("", "a", 0); }
>  __test(0) int test_strncasestr_empty(void *ctx) { return bpf_strncasestr(str, "", 1); }
>  
> +/* bpf_strpbrk - functional tests */
> +__test(0) int test_strpbrk_found_first(void *ctx) { return bpf_strpbrk(str, "h"); }
> +__test(4) int test_strpbrk_found_middle(void *ctx) { return bpf_strpbrk(str, "ow"); }
> +__test(6) int test_strpbrk_found_multiple(void *ctx) { return bpf_strpbrk(str, "w"); }

[Severity: Low]
Does this test actually verify a multiple-match scenario?

The target string "hello world" only contains a single 'w', and the accept
string is just "w". Would it be better to test with a character that appears
multiple times, such as "l" or "o"?

> +__test(-ENOENT) int test_strpbrk_notfound(void *ctx) { return bpf_strpbrk(str, "xyz"); }
> +__test(-ENOENT) int test_strpbrk_empty_accept(void *ctx) { return bpf_strpbrk(str, ""); }
> +
>  /* bpf_memcmp - functional tests */

[Severity: Low]
Are we missing negative tests for the -E2BIG (too long string) error paths?

It appears that the test_cases array in prog_tests/string_kfuncs.c was
not updated to include "strpbrk", and string_kfuncs_failure2.c is missing
the corresponding BPF programs for bpf_strpbrk.

Could this leave the bounds-checking logic untested?

[Severity: High]
This is a pre-existing issue, but does the algorithmic complexity in the
underlying string kfuncs allow for a Denial of Service?

Looking at kernel/bpf/helpers.c, functions like bpf_strpbrk(), bpf_strspn(),
and bpf_strcspn() use nested loops bounded by XATTR_SIZE_MAX (64KB):

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);
    ...
}

If a BPF program calls one of these kfuncs with two strings up to 64KB in
length that do not share any characters, the loops will execute O(N*M)
times, resulting in up to 4.29 billion memory reads.

Since the verifier is unaware of this internal kfunc complexity, can this
deliberately stall the CPU for tens of seconds and trigger RCU stalls or
watchdog lockup panics?

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