Re: [PATCH bpf-next 1/2] bpf: Fix gotox target validation against CFG

[bot+bpf-ci@kernel.org]

[-- Attachment #1: Type: text/plain, Size: 2339 bytes --]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ed7ba0e6a9ce..25fa90e731e3 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -17124,6 +17124,23 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
>  	return 0;
>  }
>
> +static bool is_cfg_indirect_jump_target(struct bpf_verifier_env *env,
> +					u32 target)
> +{
> +	struct bpf_iarray *jt = env->insn_aux_data[env->insn_idx].jt;
> +	int i;
> +
> +	if (!jt)
> +		return false;
> +
> +	for (i = 0; i < jt->cnt; i++) {
> +		if (jt->items[i] == target)
> +			return true;
> +	}
> +
> +	return false;
> +}
> +
>  /* gotox *dst_reg */
>  static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  {

[ ... ]

> @@ -17171,6 +17188,15 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in
>  		return -EINVAL;
>  	}
>
> +	for (i = 0; i < n; i++) {
> +		if (!is_cfg_indirect_jump_target(env, env->gotox_tmp_buf->items[i])) {
> +			verbose(env,
> +				"gotox target %u from map id=%d is not in the CFG jump table\n",
> +				env->gotox_tmp_buf->items[i], map->id);
> +			return -EINVAL;
> +		}
> +	}
> +

Could this nested loop create an O(N * M) algorithmic complexity that
bypasses verifier complexity limits?

The outer loop iterates n times, and is_cfg_indirect_jump_target()
performs a linear scan over jt->cnt items. Both n and jt->cnt are bounded
by the map's max_entries, which can be very large.

Since there is no cond_resched() here, this creates a synchronous
iteration sequence that could trigger the kernel watchdog panic or lead to
CPU soft lockup.

Given that both gotox_tmp_buf->items and jt->items are strictly sorted
arrays, could this be optimized to O(N + M) using a two-pointer merge
approach or O(N log M) using binary search?

Raised by sashiko-bot@kernel.org in v1:
https://lore.kernel.org/bpf/20260609151359.3C6F51F00893@smtp.kernel.org/

>  	for (i = 0; i < n - 1; i++) {
>  		mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
>  		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/27216356316