linux-kernel - Re: [PATCH] bpf/verifier: optimize precision backtracking by skipping precise bits

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <aa4cc54a3a0796b16d2d5e13142d104fa5a483e1.camel@gmail.com>
Date: Thu, 15 Jan 2026 10:52:54 -0800
From: Eduard Zingerman <eddyz87@...il.com>
To: wujing <realwujing@...il.com>, Alexei Starovoitov <ast@...nel.org>, 
 Daniel Borkmann <daniel@...earbox.net>, Andrii Nakryiko <andrii@...nel.org>
Cc: Martin KaFai Lau <martin.lau@...ux.dev>, Song Liu <song@...nel.org>, 
 Yonghong Song <yonghong.song@...ux.dev>, KP Singh <kpsingh@...nel.org>,
 Stanislav Fomichev <sdf@...ichev.me>,  Hao Luo <haoluo@...gle.com>, Jiri
 Olsa <jolsa@...nel.org>, bpf@...r.kernel.org, 
	linux-kernel@...r.kernel.org, Qiliang Yuan <yuanql9@...natelecom.cn>
Subject: Re: [PATCH] bpf/verifier: optimize precision backtracking by
 skipping precise bits

On Thu, 2026-01-15 at 23:04 +0800, wujing wrote:
> Backtracking is one of the most expensive parts of the verifier. When
> marking precision, currently the verifier always triggers the full
> __mark_chain_precision even if the target register or stack slot is
> already marked as precise.
>
> Since a precise mark in a state implies that all necessary ancestors
> have already been backtracked and marked accordingly, we can safely
> skip the backtracking process if the bit is already set.
>
> This patch implements early exit logic in:
> 1. mark_chain_precision: Check if the register is already precise.
> 2. propagate_precision: Skip registers and stack slots that are already
>    precise in the current state when propagating from an old state.
>
> This significantly reduces redundant backtracking in complex BPF
> programs with frequent state pruning and merges.
>
> Signed-off-by: wujing <realwujing@...il.com>
> Signed-off-by: Qiliang Yuan <yuanql9@...natelecom.cn>
> ---

__mark_chain_precision already stops propagation at states boundary.
States are introduced often, so I don't think this patch solves a real
world problem. In any case, the correct place to put such checks is
the bt setup code in __mark_chain_precision:

  static int __mark_chain_precision(...)
  {
	...
        func = st->frame[bt->frame];
        if (regno >= 0) {
                reg = &func->regs[regno];
                if (reg->type != SCALAR_VALUE) {
                        verifier_bug(env, "backtracking misuse");
                        return -EFAULT;
                }
		>>>>> add a condition here <<<<<
                bt_set_reg(bt, regno);
        }
	...
  }

But unless you see real measurable performance improvement,
I don't think the code should be changed.

[...]