Re: [PATCH bpf-next 06/17] bpf: Add callx calls to the call graph

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: quadratic path explosion in check_max_stack_depth_subprog for callx
--

commit 17c2586ab967c2795c90663c91164f6b6733f760
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Add callx calls to the call graph

This commit introduces call graph tracking for indirect callx calls.
It records caller-to-callee edges in a bitmap during the main verification
pass, which is then used by the recursion check and maximum stack depth checks.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0d32d3921210a..12898d31e244d 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -5486,23 +5539,40 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
>  			return -EINVAL;
>  		}
>  
> -		if (!bpf_pseudo_call(insn + i) && !bpf_pseudo_func(insn + i))
> -			continue;
> -		/* remember insn and function to return to */
> -
> -		/* find the callee */
> -		next_insn = i + insn[i].imm + 1;
> -		sidx = bpf_find_subprog(env, next_insn);
> -		if (verifier_bug_if(sidx < 0, env, "callee not found at insn %d", next_insn))
> -			return -EFAULT;
> -		if (subprog[sidx].is_async_cb) {
> -			/* async callbacks don't increase bpf prog stack size unless called directly */
> -			if (!bpf_pseudo_call(insn + i))
> +		if (bpf_is_callx(insn + i)) {
> +			/*
> +			 * Walk the callees recorded by the main verification
> +			 * pass one by one, returning to this insn after each.
> +			 */
> +			if (dinfo[idx].callx_insn != i) {
> +				dinfo[idx].callx_insn = i;
> +				dinfo[idx].callx_next = 0;
> +			}
> +			sidx = next_callx_callee(env, idx, dinfo[idx].callx_next);

[Severity: High]
Could this lead to a quadratic path explosion and unbounded CPU time in the
verifier?

The callx_edges bitmap appears to aggregate all distinct callees for an
entire caller subprogram. If I am reading this correctly,
check_max_stack_depth_subprog iterates over this entire aggregate bitmap
for every single callx instruction in that subprogram.

If a subprogram has K callx instructions and M distinct callees, would the
verifier evaluate K * M edges here instead of just K edges? Across nested
subprogram calls, it seems like this combinatorial amplification could
evaluate paths exponentially. Since this pass lacks state pruning or
complexity bounds, could this bypass the verifier complexity limits and hang
the kernel thread?

> +			if (sidx < 0)
>  				continue;
> -			if (subprog[sidx].is_exception_cb) {
> -				verbose(env, "insn %d cannot call exception cb directly", i);
> -				return -EINVAL;
> +			dinfo[idx].callx_next = sidx + 1;
> +			dinfo[idx].ret_insn = i;
> +			next_insn = subprog[sidx].start;

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260922011323.1298619-1-alexei.starovoitov@gmail.com?part=6