Re: [PATCH v2 bpf-next 4/6] bpf: Simulate branches to prune based on range violations

Eduard Zingerman
2026-03-23T19:05:16Z

On Fri, 2026-03-20 at 17:49 +0100, Paul Chaignon wrote:

[...]

> @@ -16717,11 +16717,48 @@ static void find_good_pkt_pointers(struct bpf_verifier_state *vstate,
> }));
> }
>
> +static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
> + u8 opcode, bool is_jmp32);
> +static u8 rev_opcode(u8 opcode);
> +
> +/* Learn more information about live branches by simulating both branches being
> + * taken using regs_refine_cond_op. Because regs_refine_cond_op is sound when
> + * the branch is taken, if it produces ill-formed register bounds, it must mean
> + * that the branch is dead.
> + */
> +static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode, bool is_jmp32)
> +{
> + /* Fallthrough (FALSE) branch */
> + regs_refine_cond_op(&env->false_reg1, &env->false_reg2, rev_opcode(opcode), is_jmp32);
> + reg_bounds_sync(&env->false_reg1);
> + reg_bounds_sync(&env->false_reg2);
> + /* If there is a range bounds violation in *any* of the abstract values in
> + * either reg_states in the FALSE branch (i.e. reg1, reg2), the
> + * FALSE branch must be dead. Only TRUE branch will be taken.
> + */
> + if (range_bounds_violation(&env->false_reg1) || range_bounds_violation(&env->false_reg2))
> + return 1;
> +
> + /* Jump (TRUE) branch */
> + regs_refine_cond_op(&env->true_reg1, &env->true_reg2, opcode, is_jmp32);
> + reg_bounds_sync(&env->true_reg1);
> + reg_bounds_sync(&env->true_reg2);
> + /* If there is a range bounds violation in *any* of the abstract values in
> + * either reg_states in the TRUE branch (i.e. true_reg1, true_reg2), the
> + * TRUE branch must be dead. Only FALSE branch will be taken.
> + */
> + if (range_bounds_violation(&env->true_reg1) || range_bounds_violation(&env->true_reg2))
> + return 0;

Why did you chose to limit these checks to range_bounds_violation(),
excluding const_{subreg_,}tnum_out_of_sync_with_range_bounds()?

Also, it appears that tnum bounds checking functions are unnecessarily
restricted and should be implemented as follows:

static bool const_tnum_out_of_sync_with_range_bounds(struct bpf_reg_state *reg)
{

u64 tnum_umin = reg->var_off.value;
u64 tnum_umax = reg->var_off.value | reg->var_off.mask;
s64 tnum_smin = (s64)tnum_umin;
s64 tnum_smax = (s64)tnum_smax;

// check that [tnum_umin, tnum_umax] and [reg->umin_value, reg->umax_value] intersect
// check that [tnum_smin, tnum_smax] and [reg->smin_value, reg->smax_value] intersect
return ...;
}

Wdyt?

> +
> + /* Both branches are possible, we can't determine which one will be taken. */
> + return -1;
> +}
> +
> /*
> * <reg1> <op> <reg2>, currently assuming reg2 is a constant
> */
> -static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_state *reg2,
> - u8 opcode, bool is_jmp32)
> +static int is_scalar_branch_taken(struct bpf_verifier_env *env, struct bpf_reg_state *reg1,
> + struct bpf_reg_state *reg2, u8 opcode, bool is_jmp32)
> {
> struct tnum t1 = is_jmp32 ? tnum_subreg(reg1->var_off) : reg1->var_off;
> struct tnum t2 = is_jmp32 ? tnum_subreg(reg2->var_off) : reg2->var_off; …