Re: [PATCH bpf-next v2 28/43] bpf: compute scalar evolution expressions for loops

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Critical] bpf: SCEV analysis overwrites initial state, bypassing bounds checks on early exits
- [High] bpf: NULL pointer dereference in compute_insn_scevs for irreducible nested loops
- [Medium] bpf: log_scevs incorrectly rejects valid programs with nested latches under BPF_LOG_LEVEL2
--

commit 2d2f1f9c2cfacacbaf91e31cf373b1ae40a400ea
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: compute scalar evolution expressions for loops

This commit assigns algebraic expressions to loop variables to describe how
their values evolve across iterations without unrolling the loops. The analysis
proceeds in two phases, analyzing innermost loops first and treating nested
loops as opaque operations.

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> new file mode 100644
> index 0000000000000..9ef28e0d8d481
> --- /dev/null
> +++ b/kernel/bpf/scev.c
[ ... ]
> +static struct env *get_loop_env(struct scev *scev, int loop_header, int insn_idx)
> +{
[ ... ]
> +	e->empty = true;
> +	tmp->entries[cnt].loop_header = loop_header;
> +	tmp->entries[cnt].env = e;
> +	tmp->cnt = cnt + 1;
> +	scev->envs[insn_idx] = tmp;
> +	return e;
> +}
[ ... ]
> +static int setup_initial_loop_env(struct bpf_verifier_env *env, struct env *e, int insn_idx)
> +{
> +	struct scev *scev = env->scev;
> +	int i, err;
> +
> +	for (i = 0; i < REGS_NUM; i++) {
> +		err = replace_reg(scev, e, i, expr1(scev, REG, i));
> +		if (err)
> +			return err;
> +	}
> +	return 0;
> +}

[Severity: Critical]
Could this leave the loop environment marked as empty even after it has been
populated with the initial register state?

When get_loop_env() initializes the environment, it sets e->empty to true.
Since setup_initial_loop_env() does not set e->empty to false after filling
the registers, a subsequent call to join() on the backedge might completely
overwrite this initial state:

	if (acc->empty) {
		memcpy(acc, cur, sizeof(*acc));
		acc->empty = false;
		return 0;
	}

If the loop exits on the first iteration, could the verifier mistakenly
assume a constant from the backedge instead of the actual entry value,
potentially bypassing bounds checks?

[ ... ]
> +static int compute_scev_for_loop(struct bpf_verifier_env *env, int cur_header)
> +{
[ ... ]
> +	/*
> +	 * For irreducible loops, and for loops nesting a loop with a truncated
> +	 * exit list, just assume that everything is clobbered for now.
> +	 */
> +	if (!can_compute_loop_scev(cur_loop)) {
> +		header_env = get_loop_env(scev, cur_header, cur_header);
> +		if (!header_env)
> +			return -ENOMEM;
> +		/* The freshly allocated environment has all expressions unknown. */
> +		header_env->empty = false;
> +		return 0;
> +	}
[ ... ]
> +static int compute_insn_scevs(struct bpf_verifier_env *env, struct env *eheader, struct env *einsn)
> +{
> +	struct scev *scev = env->scev;
> +	int id, reg;
> +
> +	for (reg = 0; reg < REGS_NUM; reg++) {
> +		id = einsn->reg2expr[reg];

[Severity: High]
Is it possible for einsn to be NULL here?

If a reducible outer loop has an exit instruction that is physically located
inside a nested irreducible loop, compute_scev_for_loop() will skip
allocating body environments for the inner loop.

When bpf_compute_scev() iterates over instructions and calls find_loop_env()
for this instruction, it might return NULL. This would result in passing a
NULL pointer into compute_insn_scevs(), leading to a dereference here.

> +		id = transform_expr_once(scev, 0, id, eheader->reg2scev, instantiate_header_scevs);
> +		if (id < 0)
> +			return id;
[ ... ]
> +static int log_scevs(struct bpf_verifier_env *env)
> +{
[ ... ]
> +		if (!can_compute_loop_scev(loop))
> +			continue;
> +		for (j = 0; j < loop->backedges_cnt; j++) {
> +			latch = loop->backedges[j].latch;
> +			if (latch < 0)
> +				continue;
> +			bpf_log(log, " scev at latch %d:\n", latch);
> +			latch_env = find_loop_env(scev, i, latch);
> +			if (verifier_bug_if(!latch_env, env, "i=%d, latch=%d", i, latch))
> +				return -EFAULT;

[Severity: Medium]
Could this trigger a verifier bug for valid programs when log level 2 is
enabled?

If an outer loop's latch is located inside a nested loop, its environment
might not be allocated since the nested loop's body is skipped during
evaluation. If so, find_loop_env() will return NULL, causing this check to
fail and abort verification for otherwise valid code.

> +			print_env(env, latch_env, latch, PRINT_SCEV);
> +		}
> +	}
> +	return 0;
> +}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261004-scev-minimal-rebase-v2-0-f6254e29fdf2@gmail.com?part=28