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

Harishankar Vishwanathan
2026-03-24T23:59:49Z

On Mon, Mar 23, 2026 at 3:05 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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()?

The main reason was because the invariant violations were typically
only detected by
range_bounds_violations().

> 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?

I like the idea! If we do this, we should also rename the function to simply
"tnum_range_mismatch" or something along those lines (as mentioned in
the other thread),
dropping the "const".

Technically, the verifier should maintain the invariant that all domain
pairs always have intersections. There are 10 domain pairs:
u64_s64, u64_tnum, s64_tnum, u32_s32, u32_tnum, s32_tnum,
u64_u32, u64_s32, u32_s64, s64_s32. We can have intersection checks
for each of these pairs, or we can stick to the major ones, i.e. the top 6
in this list.

Checking for intersections was part of the original idea in the RFC
for tnum_step()
I had sent a while back [1], which was about detecting intersection between
tnum and u64.

Generally a simple check will be
if (tmin > umax) || (tmax < umin) // no intersection

The original idea in the RFC was to use tnum_step to make this check
complete. Particularly, for cases like:

t = x0x1 {1, 3, 9, 11}
r = [4, 8] {4, 5, 6, 7, 8}

The above check won't suffice. We can add the following check:

if tnum_step(t, umin) > umax) // no intersection

Since tnum_step() has been upstreamed, maybe it is a good time to
revisit the idea, and have a sound and complete intersection check?
Or do you think that is overkill for this patch?

Also, then, should this patch introduce domain checks for all 10 domain pairs?

[1]: https://lore.kernel.org/bpf/20251107192328.2190680-1-harishankar.vishwanathan@gmail.com/

> > +
> > + /* 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;
>
> …