Re: [PATCH v5 bpf-next 20/23] bpf: enhance BPF_JEQ/BPF_JNE is_branch_taken logic

Alexei Starovoitov
2023-10-31T02:20:38Z

On Fri, Oct 27, 2023 at 11:13:43AM -0700, Andrii Nakryiko wrote:
> Use 32-bit subranges to prune some 64-bit BPF_JEQ/BPF_JNE conditions
> that otherwise would be "inconclusive" (i.e., is_branch_taken() would
> return -1). This can happen, for example, when registers are initialized
> as 64-bit u64/s64, then compared for inequality as 32-bit subregisters,
> and then followed by 64-bit equality/inequality check. That 32-bit
> inequality can establish some pattern for lower 32 bits of a register
> (e.g., s< 0 condition determines whether the bit #31 is zero or not),
> while overall 64-bit value could be anything (according to a value range
> representation).
>
> This is not a fancy quirky special case, but actually a handling that's
> necessary to prevent correctness issue with BPF verifier's range
> tracking: set_range_min_max() assumes that register ranges are
> non-overlapping, and if that condition is not guaranteed by
> is_branch_taken() we can end up with invalid ranges, where min > max.

This is_scalar_branch_taken() logic makes sense,
but if set_range_min_max() is delicate, it should have its own sanity
check for ranges.
Shouldn't be difficult to check for that dangerous overlap case.