diff mbox series

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

Message ID 20231027181346.4019398-21-andrii@kernel.org (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series BPF register bounds logic and testing improvements | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-16 / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-32 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-33 success Logs for x86_64-llvm-16 / veristat
netdev/series_format fail Series longer than 15 patches (and no cover letter)
netdev/tree_selection success Clearly marked for bpf-next, async
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 1374 this patch: 1374
netdev/cc_maintainers warning 8 maintainers not CCed: john.fastabend@gmail.com kpsingh@kernel.org song@kernel.org sdf@google.com jolsa@kernel.org martin.lau@linux.dev yonghong.song@linux.dev haoluo@google.com
netdev/build_clang fail Errors and warnings before: 15 this patch: 15
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 1399 this patch: 1399
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 36 lines checked
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-15 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-16 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-llvm-16 / build / build for x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-25 success Logs for x86_64-llvm-16 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-10 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc

Commit Message

Andrii Nakryiko Oct. 27, 2023, 6:13 p.m. UTC 
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.

  [0] https://lore.kernel.org/bpf/CACkBjsY2q1_fUohD7hRmKGqv1MV=eP2f6XK8kjkYNw7BaiF8iQ@mail.gmail.com/

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

Comments

Alexei Starovoitov Oct. 31, 2023, 2:20 a.m. UTC | #1 
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.
Andrii Nakryiko Oct. 31, 2023, 6:16 a.m. UTC | #2 
On Mon, Oct 30, 2023 at 7:20 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> 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.

So let me clarify. As far as I'm concerned, is_branch_taken() is such
a check for set_reg_min_max, and so duplicating such checks in
set_reg_min_max() is just that a duplication of code and logic, and
just a chance for more typos and subtle bugs.

But the concern about invalid ranges is valid, so I don't know,
perhaps we should just do a quick check after adjustment to validate
that umin<=umax and so on? E.g., we can do that outside of
reg_set_min_max(), to keep reg_set_min_max() non-failing. WDYT?
Alexei Starovoitov Oct. 31, 2023, 4:36 p.m. UTC | #3 
On Mon, Oct 30, 2023 at 11:16 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Oct 30, 2023 at 7:20 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > 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.
>
> So let me clarify. As far as I'm concerned, is_branch_taken() is such
> a check for set_reg_min_max, and so duplicating such checks in
> set_reg_min_max() is just that a duplication of code and logic, and
> just a chance for more typos and subtle bugs.
>
> But the concern about invalid ranges is valid, so I don't know,
> perhaps we should just do a quick check after adjustment to validate
> that umin<=umax and so on? E.g., we can do that outside of
> reg_set_min_max(), to keep reg_set_min_max() non-failing. WDYT?

Sounds like a good option too.
Just trying to minimize breakage in the future.
Sanity check before or after should catch it.
Andrii Nakryiko Oct. 31, 2023, 6:04 p.m. UTC | #4 
On Tue, Oct 31, 2023 at 9:36 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Mon, Oct 30, 2023 at 11:16 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Oct 30, 2023 at 7:20 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > 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.
> >
> > So let me clarify. As far as I'm concerned, is_branch_taken() is such
> > a check for set_reg_min_max, and so duplicating such checks in
> > set_reg_min_max() is just that a duplication of code and logic, and
> > just a chance for more typos and subtle bugs.
> >
> > But the concern about invalid ranges is valid, so I don't know,
> > perhaps we should just do a quick check after adjustment to validate
> > that umin<=umax and so on? E.g., we can do that outside of
> > reg_set_min_max(), to keep reg_set_min_max() non-failing. WDYT?
>
> Sounds like a good option too.
> Just trying to minimize breakage in the future.
> Sanity check before or after should catch it.

Sounds good, I'll have a separate register state sanity check and will
see what minimal amount of places where we should call it.

I'm assuming we are ok with returning -EFAULT and failing validation
whenever we detect violation, right?
Alexei Starovoitov Oct. 31, 2023, 6:06 p.m. UTC | #5 
On Tue, Oct 31, 2023 at 11:04 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Tue, Oct 31, 2023 at 9:36 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Mon, Oct 30, 2023 at 11:16 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Mon, Oct 30, 2023 at 7:20 PM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > 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.
> > >
> > > So let me clarify. As far as I'm concerned, is_branch_taken() is such
> > > a check for set_reg_min_max, and so duplicating such checks in
> > > set_reg_min_max() is just that a duplication of code and logic, and
> > > just a chance for more typos and subtle bugs.
> > >
> > > But the concern about invalid ranges is valid, so I don't know,
> > > perhaps we should just do a quick check after adjustment to validate
> > > that umin<=umax and so on? E.g., we can do that outside of
> > > reg_set_min_max(), to keep reg_set_min_max() non-failing. WDYT?
> >
> > Sounds like a good option too.
> > Just trying to minimize breakage in the future.
> > Sanity check before or after should catch it.
>
> Sounds good, I'll have a separate register state sanity check and will
> see what minimal amount of places where we should call it.
>
> I'm assuming we are ok with returning -EFAULT and failing validation
> whenever we detect violation, right?

Yep and I'll take back WARN suggestion. Let's not add any WARN to avoid
triggering panic_on_warn.
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f18a8247e5e2..cf5bf7ab4410 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14214,6 +14214,18 @@  static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
 			return 0;
 		if (smin1 > smax2 || smax1 < smin2)
 			return 0;
+		if (!is_jmp32) {
+			/* if 64-bit ranges are inconclusive, see if we can
+			 * utilize 32-bit subrange knowledge to eliminate
+			 * branches that can't be taken a priori
+			 */
+			if (reg1->u32_min_value > reg2->u32_max_value ||
+			    reg1->u32_max_value < reg2->u32_min_value)
+				return 0;
+			if (reg1->s32_min_value > reg2->s32_max_value ||
+			    reg1->s32_max_value < reg2->s32_min_value)
+				return 0;
+		}
 		break;
 	case BPF_JNE:
 		/* const tnums */
@@ -14229,6 +14241,18 @@  static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
 			return 1;
 		if (smin1 > smax2 || smax1 < smin2)
 			return 1;
+		if (!is_jmp32) {
+			/* if 64-bit ranges are inconclusive, see if we can
+			 * utilize 32-bit subrange knowledge to eliminate
+			 * branches that can't be taken a priori
+			 */
+			if (reg1->u32_min_value > reg2->u32_max_value ||
+			    reg1->u32_max_value < reg2->u32_min_value)
+				return 1;
+			if (reg1->s32_min_value > reg2->s32_max_value ||
+			    reg1->s32_max_value < reg2->s32_min_value)
+				return 1;
+		}
 		break;
 	case BPF_JSET:
 		if (!is_reg_const(reg2, is_jmp32)) {