linux-kernel - Re: [PATCH v3 1/2] bpf, verifier: Improve precision for BPF_ADD and BPF

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: <11d71d3c2ac47438e4f366ec555e1695880f454e.camel@gmail.com>
Date: Tue, 24 Jun 2025 14:59:40 -0700
From: Eduard Zingerman <eddyz87@...il.com>
To: Harishankar Vishwanathan <harishankar.vishwanathan@...il.com>, 
	ast@...nel.org
Cc: m.shachnai@...gers.edu, srinivas.narayana@...gers.edu, 
	santosh.nagarakatte@...gers.edu, Daniel Borkmann <daniel@...earbox.net>,
 John Fastabend <john.fastabend@...il.com>, Andrii Nakryiko
 <andrii@...nel.org>, 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
Subject: Re: [PATCH v3 1/2] bpf, verifier: Improve precision for BPF_ADD and
 BPF_SUB

On Mon, 2025-06-23 at 00:03 -0400, Harishankar Vishwanathan wrote:
> This patch improves the precison of the scalar(32)_min_max_add and
> scalar(32)_min_max_sub functions, which update the u(32)min/u(32)_max
> ranges for the BPF_ADD and BPF_SUB instructions. We discovered this more
> precise operator using a technique we are developing for automatically
> synthesizing functions for updating tnums and ranges.
> 
> According to the BPF ISA [1], "Underflow and overflow are allowed during
> arithmetic operations, meaning the 64-bit or 32-bit value will wrap".
> Our patch leverages the wrap-around semantics of unsigned overflow and
> underflow to improve precision.
> 
> Below is an example of our patch for scalar_min_max_add; the idea is
> analogous for all four functions.
> 
> There are three cases to consider when adding two u64 ranges [dst_umin,
> dst_umax] and [src_umin, src_umax]. Consider a value x in the range
> [dst_umin, dst_umax] and another value y in the range [src_umin,
> src_umax].
> 
> (a) No overflow: No addition x + y overflows. This occurs when even the
> largest possible sum, i.e., dst_umax + src_umax <= U64_MAX.
> 
> (b) Partial overflow: Some additions x + y overflow. This occurs when
> the largest possible sum overflows (dst_umax + src_umax > U64_MAX), but
> the smallest possible sum does not overflow (dst_umin + src_umin <=
> U64_MAX).
> 
> (c) Full overflow: All additions x + y overflow. This occurs when both
> the smallest possible sum and the largest possible sum overflow, i.e.,
> both (dst_umin + src_umin) and (dst_umax + src_umax) are > U64_MAX.
> 

[...]

> Co-developed-by: Matan Shachnai <m.shachnai@...gers.edu>
> Signed-off-by: Matan Shachnai <m.shachnai@...gers.edu>
> Co-developed-by: Srinivas Narayana <srinivas.narayana@...gers.edu>
> Signed-off-by: Srinivas Narayana <srinivas.narayana@...gers.edu>
> Co-developed-by: Santosh Nagarakatte <santosh.nagarakatte@...gers.edu>
> Signed-off-by: Santosh Nagarakatte <santosh.nagarakatte@...gers.edu>
> Signed-off-by: Harishankar Vishwanathan <harishankar.vishwanathan@...il.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@...il.com>

(Please don't drop acks).