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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] The newly introduced jump target validation check in `check_indirect_jump` introduces an O(N * M) algorithmic complexity that bypasses verifier complexity limits, allowing a CPU soft lockup or Denial of Service (DoS).
--

commit 618413c7b9b3d9e098467c3629ea05da9fcb47af
Author: Nuoqi Gui <gnq25@mails.tsinghua.edu.cn>

bpf: Fix gotox target validation against CFG

This commit adds validation to ensure that jump targets copied from the
INSN_ARRAY map are present in the CFG jump table built for the gotox
instruction. It rejects programs before pushing verifier states for unmodeled
targets to prevent entering another subprog without a matching call frame.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ed7ba0e6a9ce0..25fa90e731e30 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])) {

[Severity: High]
Could this nested iteration result in a CPU soft lockup?

This loop inside check_indirect_jump() iterates n times, and
is_cfg_indirect_jump_target() performs a linear scan over jt->cnt. 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 an O(N * M) synchronous
iteration sequence that bypasses the verifier's global instruction limits
and could trigger the kernel watchdog panic.

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?

> +			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;
> +		}
> +	}
> +
>  	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],

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260609-f01-02-gotox-bpf-next-v1-0-b441d63a1559@mails.tsinghua.edu.cn?part=1