Re: [PATCH bpf-next 06/13] bpf: make __reg{32,64}_deduce_bounds logic more robust

Shung-Hsi Yu
2023-11-09T09:03:12Z

On Thu, Nov 02, 2023 at 05:08:15PM -0700, Andrii Nakryiko wrote:
> This change doesn't seem to have any effect on selftests and production
> BPF object files, but we preemptively try to make it more robust.
>
> First, "learn sign from signed bounds" comment is misleading, as we are
> learning not just sign, but also values.
>
> Second, we simplify the check for determining whether entire range is
> positive or negative similarly to other checks added earlier, using
> appropriate u32/u64 cast and single comparisons. As explain in comments
> in __reg64_deduce_bounds(), the checks are equivalent.
>
> Last but not least, smin/smax and s32_min/s32_max reassignment based on
> min/max of both umin/umax and smin/smax (and 32-bit equivalents) is hard
> to explain and justify. We are updating unsigned bounds from signed
> bounds, why would we update signed bounds at the same time? This might
> be correct, but it's far from obvious why and the code or comments don't
> try to justify this. Given we've added a separate deduction of signed
> bounds from unsigned bounds earlier, this seems at least redundant, if
> not just wrong.
>
> In short, we remove doubtful pieces, and streamline the rest to follow
> the logic and approach of the rest of reg_bounds_sync() checks.
>
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> ---
> kernel/bpf/verifier.c | 24 ++++++++----------------
> 1 file changed, 8 insertions(+), 16 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index e7b2fe78a07f..91271961c9c2 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2399,17 +2399,13 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
> reg->s32_min_value = max_t(s32, reg->s32_min_value, reg->u32_min_value);
> reg->s32_max_value = min_t(s32, reg->s32_max_value, reg->u32_max_value);
> }
> - /* Learn sign from signed bounds.
> - * If we cannot cross the sign boundary, then signed and unsigned bounds
> + /* If we cannot cross the sign boundary, then signed and unsigned bounds
> * are the same, so combine. This works even in the negative case, e.g.
> * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff.
> */
> - if (reg->s32_min_value >= 0 || reg->s32_max_value < 0) {
> - reg->s32_min_value = reg->u32_min_value =
> - max_t(u32, reg->s32_min_value, reg->u32_min_value);
> - reg->s32_max_value = reg->u32_max_value =
> - min_t(u32, reg->s32_max_value, reg->u32_max_value);
> - return;

I'd guess updating signed bounds here is sort of a shortcut to reach the
tighest bound possible without going having to go through
__reg32_deduce_bounds() twice, maybe.

Agree that the changes below is more straight forward, same goes for
__reg64_deduce_bounds().

Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>

> + if ((u32)reg->s32_min_value <= (u32)reg->s32_max_value) {
> + reg->u32_min_value = max_t(u32, reg->s32_min_value, reg->u32_min_value);
> + reg->u32_max_value = min_t(u32, reg->s32_max_value, reg->u32_max_value);
> }
> }
>
> @@ -2486,17 +2482,13 @@ static void __reg64_deduce_bounds(struct bpf_reg_state *reg)
> reg->smin_value = max_t(s64, reg->smin_value, reg->umin_value);
> reg->smax_value = min_t(s64, reg->smax_value, reg->umax_value);
> }
> - /* Learn sign from signed bounds.
> - * If we cannot cross the sign boundary, then signed and unsigned bounds
> + /* If we cannot cross the sign boundary, then signed and unsigned bounds
> * are the same, so combine. This works even in the negative case, e.g.
> * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff.
> */
> - if (reg->smin_value >= 0 || reg->smax_value < 0) {
> - reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value,
> - reg->umin_value);
> - reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value,
> - reg->umax_value);
> - return;
> + if ((u64)reg->smin_value <= (u64)reg->smax_value) {
> + reg->umin_value = max_t(u64, reg->smin_value, reg->umin_value);
> + reg->umax_value = min_t(u64, reg->smax_value, reg->umax_value);