[RFC,v2,2/7] bpf: Mark ALU32 operations in bpf_reg_state structure

Commit Message

Roberto Sassu Dec. 7, 2022, 5:24 p.m. UTC

From: Roberto Sassu <[e-mail]>

BPF LSM needs a reliable source of information to determine if the return
value given by eBPF programs is acceptable or not. At the moment, choosing
either the 64 bit or the 32 bit one does not seem to be an option
(selftests fail).

If we choose the 64 bit one, the following happens.

      14:	61 10 00 00 00 00 00 00	r0 = *(u32 *)(r1 + 0)
      15:	74 00 00 00 15 00 00 00	w0 >>= 21
      16:	54 00 00 00 01 00 00 00	w0 &= 1
      17:	04 00 00 00 ff ff ff ff	w0 += -1

This is the last part of test_deny_namespace. After #16, the register
values are:

smin_value = 0x0, smax_value = 0x1,
s32_min_value = 0x0, s32_max_value = 0x1,

After #17, they become:

smin_value = 0x0, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0x0

where only the 32 bit values are correct.

If we choose the 32 bit ones, the following happens.

0000000000000000 <check_access>:
       0:	79 12 00 00 00 00 00 00	r2 = *(u64 *)(r1 + 0)
       1:	79 10 08 00 00 00 00 00	r0 = *(u64 *)(r1 + 8)
       2:	67 00 00 00 3e 00 00 00	r0 <<= 62
       3:	c7 00 00 00 3f 00 00 00	r0 s>>= 63

This is part of test_libbpf_get_fd_by_id_opts (no_alu32 version). In this
case, 64 bit register values should be used (for the 32 bit ones, there is
no precise information from the verifier).

As the examples above suggest that which register values to use depends on
the specific case, mark ALU32 operations in bpf_reg_state structure, so
that BPF LSM can choose the proper ones.

Signed-off-by: Roberto Sassu <[e-mail]>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 10 +++++++++-
 2 files changed, 10 insertions(+), 1 deletion(-)

Comments

Alexei Starovoitov Dec. 11, 2022, 2:28 a.m. UTC | #1

On Wed, Dec 7, 2022 at 9:25 AM Roberto Sassu
<[e-mail]> wrote:
>
> From: Roberto Sassu <[e-mail]>
>
> BPF LSM needs a reliable source of information to determine if the return
> value given by eBPF programs is acceptable or not. At the moment, choosing
> either the 64 bit or the 32 bit one does not seem to be an option
> (selftests fail).
>
> If we choose the 64 bit one, the following happens.
>
>       14:       61 10 00 00 00 00 00 00 r0 = *(u32 *)(r1 + 0)
>       15:       74 00 00 00 15 00 00 00 w0 >>= 21
>       16:       54 00 00 00 01 00 00 00 w0 &= 1
>       17:       04 00 00 00 ff ff ff ff w0 += -1
>
> This is the last part of test_deny_namespace. After #16, the register
> values are:
>
> smin_value = 0x0, smax_value = 0x1,
> s32_min_value = 0x0, s32_max_value = 0x1,
>
> After #17, they become:
>
> smin_value = 0x0, smax_value = 0xffffffff,
> s32_min_value = 0xffffffff, s32_max_value = 0x0
>
> where only the 32 bit values are correct.
>
> If we choose the 32 bit ones, the following happens.
>
> 0000000000000000 <check_access>:
>        0:       79 12 00 00 00 00 00 00 r2 = *(u64 *)(r1 + 0)
>        1:       79 10 08 00 00 00 00 00 r0 = *(u64 *)(r1 + 8)
>        2:       67 00 00 00 3e 00 00 00 r0 <<= 62
>        3:       c7 00 00 00 3f 00 00 00 r0 s>>= 63
>
> This is part of test_libbpf_get_fd_by_id_opts (no_alu32 version). In this
> case, 64 bit register values should be used (for the 32 bit ones, there is
> no precise information from the verifier).
>
> As the examples above suggest that which register values to use depends on
> the specific case, mark ALU32 operations in bpf_reg_state structure, so
> that BPF LSM can choose the proper ones.

I have a hard time understanding what is the problem you're
trying to solve and what is the proposed fix.

The patch is trying to remember the bitness of the last
operation, but what for?
The registers are 64-bit. There are 32-bit operations,
but they always update the upper 32-bits of the register.
reg_bounds_sync() updates 32 and 64 bit bounds regardless
whether the previous operation was on 32 or 64 bit.
It seems you're trying to hack around something that breaks
patch 3 which also looks fishy.
Please explain the problem first with a concrete example.

Roberto Sassu Dec. 12, 2022, 12:44 p.m. UTC | #2

On Sat, 2022-12-10 at 18:28 -0800, Alexei Starovoitov wrote:
> On Wed, Dec 7, 2022 at 9:25 AM Roberto Sassu
> <[e-mail]> wrote:
> > From: Roberto Sassu <[e-mail]>
> > 
> > BPF LSM needs a reliable source of information to determine if the return
> > value given by eBPF programs is acceptable or not. At the moment, choosing
> > either the 64 bit or the 32 bit one does not seem to be an option
> > (selftests fail).
> > 
> > If we choose the 64 bit one, the following happens.
> > 
> >       14:       61 10 00 00 00 00 00 00 r0 = *(u32 *)(r1 + 0)
> >       15:       74 00 00 00 15 00 00 00 w0 >>= 21
> >       16:       54 00 00 00 01 00 00 00 w0 &= 1
> >       17:       04 00 00 00 ff ff ff ff w0 += -1
> > 
> > This is the last part of test_deny_namespace. After #16, the register
> > values are:
> > 
> > smin_value = 0x0, smax_value = 0x1,
> > s32_min_value = 0x0, s32_max_value = 0x1,
> > 
> > After #17, they become:
> > 
> > smin_value = 0x0, smax_value = 0xffffffff,
> > s32_min_value = 0xffffffff, s32_max_value = 0x0
> > 
> > where only the 32 bit values are correct.
> > 
> > If we choose the 32 bit ones, the following happens.
> > 
> > 0000000000000000 <check_access>:
> >        0:       79 12 00 00 00 00 00 00 r2 = *(u64 *)(r1 + 0)
> >        1:       79 10 08 00 00 00 00 00 r0 = *(u64 *)(r1 + 8)
> >        2:       67 00 00 00 3e 00 00 00 r0 <<= 62
> >        3:       c7 00 00 00 3f 00 00 00 r0 s>>= 63
> > 
> > This is part of test_libbpf_get_fd_by_id_opts (no_alu32 version). In this
> > case, 64 bit register values should be used (for the 32 bit ones, there is
> > no precise information from the verifier).
> > 
> > As the examples above suggest that which register values to use depends on
> > the specific case, mark ALU32 operations in bpf_reg_state structure, so
> > that BPF LSM can choose the proper ones.
> 
> I have a hard time understanding what is the problem you're
> trying to solve and what is the proposed fix.

The problem is allowing BPF LSM programs to return positive values when
LSM hooks expect zero or negative values. Those values could be
converted to a pointer, and escape the IS_ERR() check.

The challenge is to ensure that the verifier prediction of R0 is
accurate, so that the eBPF program is not unnecessarily rejected.

> The patch is trying to remember the bitness of the last
> operation, but what for?
> The registers are 64-bit. There are 32-bit operations,
> but they always update the upper 32-bits of the register.
> reg_bounds_sync() updates 32 and 64 bit bounds regardless
> whether the previous operation was on 32 or 64 bit.

Ok, yes. I also thought that using the 64 bit register should be ok,
but selftests fail.

Regarding your comment, I have not seen reg_bounds_sync() for the case
R = imm.

> It seems you're trying to hack around something that breaks
> patch 3 which also looks fishy.

I thought it was a good idea that changes in the LSM infrastructure are
automatically reflected in the boundaries that BPF LSM should enforce.

If not, I'm open to new ideas. If we should use BTF ID sets, I'm fine
with it.

> Please explain the problem first with a concrete example.

Ok, I have a simple one:

$ llvm-objdump -d test_bpf_cookie.bpf.o

0000000000000000 <test_int_hook>:

[...]

       8:	85 00 00 00 0e 00 00 00	call 14
       9:	b4 06 00 00 ff ff ff ff	w6 = -1
      10:	5e 08 07 00 00 00 00 00	if w8 != w0 goto +7 <LBB11_3>
      11:	bf 71 00 00 00 00 00 00	r1 = r7
      12:	85 00 00 00 ae 00 00 00	call 174
      13:	18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00	r1 = 0 ll
      15:	79 12 00 00 00 00 00 00	r2 = *(u64 *)(r1 + 0)
      16:	4f 02 00 00 00 00 00 00	r2 |= r0
      17:	7b 21 00 00 00 00 00 00	*(u64 *)(r1 + 0) = r2

smin_value = 0xffffffff, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,

This is what I see at the time the BPF LSM check should be done.

How this should be properly handled?

Thanks

Roberto

Alexei Starovoitov Dec. 12, 2022, 5:04 p.m. UTC | #3

On Mon, Dec 12, 2022 at 4:45 AM Roberto Sassu
<[e-mail]> wrote:
>
> On Sat, 2022-12-10 at 18:28 -0800, Alexei Starovoitov wrote:
> > On Wed, Dec 7, 2022 at 9:25 AM Roberto Sassu
> > <[e-mail]> wrote:
> > > From: Roberto Sassu <[e-mail]>
> > >
> > > BPF LSM needs a reliable source of information to determine if the return
> > > value given by eBPF programs is acceptable or not. At the moment, choosing
> > > either the 64 bit or the 32 bit one does not seem to be an option
> > > (selftests fail).
> > >
> > > If we choose the 64 bit one, the following happens.
> > >
> > >       14:       61 10 00 00 00 00 00 00 r0 = *(u32 *)(r1 + 0)
> > >       15:       74 00 00 00 15 00 00 00 w0 >>= 21
> > >       16:       54 00 00 00 01 00 00 00 w0 &= 1
> > >       17:       04 00 00 00 ff ff ff ff w0 += -1
> > >
> > > This is the last part of test_deny_namespace. After #16, the register
> > > values are:
> > >
> > > smin_value = 0x0, smax_value = 0x1,
> > > s32_min_value = 0x0, s32_max_value = 0x1,
> > >
> > > After #17, they become:
> > >
> > > smin_value = 0x0, smax_value = 0xffffffff,
> > > s32_min_value = 0xffffffff, s32_max_value = 0x0
> > >
> > > where only the 32 bit values are correct.
> > >
> > > If we choose the 32 bit ones, the following happens.
> > >
> > > 0000000000000000 <check_access>:
> > >        0:       79 12 00 00 00 00 00 00 r2 = *(u64 *)(r1 + 0)
> > >        1:       79 10 08 00 00 00 00 00 r0 = *(u64 *)(r1 + 8)
> > >        2:       67 00 00 00 3e 00 00 00 r0 <<= 62
> > >        3:       c7 00 00 00 3f 00 00 00 r0 s>>= 63
> > >
> > > This is part of test_libbpf_get_fd_by_id_opts (no_alu32 version). In this
> > > case, 64 bit register values should be used (for the 32 bit ones, there is
> > > no precise information from the verifier).
> > >
> > > As the examples above suggest that which register values to use depends on
> > > the specific case, mark ALU32 operations in bpf_reg_state structure, so
> > > that BPF LSM can choose the proper ones.
> >
> > I have a hard time understanding what is the problem you're
> > trying to solve and what is the proposed fix.
>
> The problem is allowing BPF LSM programs to return positive values when
> LSM hooks expect zero or negative values. Those values could be
> converted to a pointer, and escape the IS_ERR() check.

The bigger goal is clear.

> The challenge is to ensure that the verifier prediction of R0 is
> accurate, so that the eBPF program is not unnecessarily rejected.

There is a code in the verifier already that checks ret values.
lsm restrictions should fit right in.

> > The patch is trying to remember the bitness of the last
> > operation, but what for?
> > The registers are 64-bit. There are 32-bit operations,
> > but they always update the upper 32-bits of the register.
> > reg_bounds_sync() updates 32 and 64 bit bounds regardless
> > whether the previous operation was on 32 or 64 bit.
>
> Ok, yes. I also thought that using the 64 bit register should be ok,
> but selftests fail.

maybe selftests are buggy?
they fail with patch 3 alone without patch 2 ?
please explain exactly the problem.

> Regarding your comment, I have not seen reg_bounds_sync() for the case
> R = imm.

because it's unnecessary there.

> > It seems you're trying to hack around something that breaks
> > patch 3 which also looks fishy.
>
> I thought it was a good idea that changes in the LSM infrastructure are
> automatically reflected in the boundaries that BPF LSM should enforce.

That's fine. Encoding restrictions in lsm_hook_defs.h
is the cleanest approach.

> If not, I'm open to new ideas. If we should use BTF ID sets, I'm fine
> with it.
>
> > Please explain the problem first with a concrete example.
>
> Ok, I have a simple one:
>
> $ llvm-objdump -d test_bpf_cookie.bpf.o
>
> 0000000000000000 <test_int_hook>:
>
> [...]
>
>        8:       85 00 00 00 0e 00 00 00 call 14
>        9:       b4 06 00 00 ff ff ff ff w6 = -1
>       10:       5e 08 07 00 00 00 00 00 if w8 != w0 goto +7 <LBB11_3>
>       11:       bf 71 00 00 00 00 00 00 r1 = r7
>       12:       85 00 00 00 ae 00 00 00 call 174
>       13:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
>       15:       79 12 00 00 00 00 00 00 r2 = *(u64 *)(r1 + 0)
>       16:       4f 02 00 00 00 00 00 00 r2 |= r0
>       17:       7b 21 00 00 00 00 00 00 *(u64 *)(r1 + 0) = r2
>
> smin_value = 0xffffffff, smax_value = 0xffffffff,
> s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,

and this applies where?
what reg are you talking about?
Where is the issue?

> This is what I see at the time the BPF LSM check should be done.
>
> How this should be properly handled?

The patch 3 should be fine alone. I don't see a need for patch 2 yet.

Roberto Sassu Dec. 12, 2022, 6:10 p.m. UTC | #4

On Mon, 2022-12-12 at 09:04 -0800, Alexei Starovoitov wrote:
> On Mon, Dec 12, 2022 at 4:45 AM Roberto Sassu
> <[e-mail]> wrote:
> > On Sat, 2022-12-10 at 18:28 -0800, Alexei Starovoitov wrote:
> > > On Wed, Dec 7, 2022 at 9:25 AM Roberto Sassu
> > > <[e-mail]> wrote:
> > > > From: Roberto Sassu <[e-mail]>
> > > > 
> > > > BPF LSM needs a reliable source of information to determine if the return
> > > > value given by eBPF programs is acceptable or not. At the moment, choosing
> > > > either the 64 bit or the 32 bit one does not seem to be an option
> > > > (selftests fail).
> > > > 
> > > > If we choose the 64 bit one, the following happens.
> > > > 
> > > >       14:       61 10 00 00 00 00 00 00 r0 = *(u32 *)(r1 + 0)
> > > >       15:       74 00 00 00 15 00 00 00 w0 >>= 21
> > > >       16:       54 00 00 00 01 00 00 00 w0 &= 1
> > > >       17:       04 00 00 00 ff ff ff ff w0 += -1
> > > > 
> > > > This is the last part of test_deny_namespace. After #16, the register
> > > > values are:
> > > > 
> > > > smin_value = 0x0, smax_value = 0x1,
> > > > s32_min_value = 0x0, s32_max_value = 0x1,
> > > > 
> > > > After #17, they become:
> > > > 
> > > > smin_value = 0x0, smax_value = 0xffffffff,
> > > > s32_min_value = 0xffffffff, s32_max_value = 0x0
> > > > 
> > > > where only the 32 bit values are correct.
> > > > 
> > > > If we choose the 32 bit ones, the following happens.
> > > > 
> > > > 0000000000000000 <check_access>:
> > > >        0:       79 12 00 00 00 00 00 00 r2 = *(u64 *)(r1 + 0)
> > > >        1:       79 10 08 00 00 00 00 00 r0 = *(u64 *)(r1 + 8)
> > > >        2:       67 00 00 00 3e 00 00 00 r0 <<= 62
> > > >        3:       c7 00 00 00 3f 00 00 00 r0 s>>= 63
> > > > 
> > > > This is part of test_libbpf_get_fd_by_id_opts (no_alu32 version). In this
> > > > case, 64 bit register values should be used (for the 32 bit ones, there is
> > > > no precise information from the verifier).
> > > > 
> > > > As the examples above suggest that which register values to use depends on
> > > > the specific case, mark ALU32 operations in bpf_reg_state structure, so
> > > > that BPF LSM can choose the proper ones.
> > > 
> > > I have a hard time understanding what is the problem you're
> > > trying to solve and what is the proposed fix.
> > 
> > The problem is allowing BPF LSM programs to return positive values when
> > LSM hooks expect zero or negative values. Those values could be
> > converted to a pointer, and escape the IS_ERR() check.
> 
> The bigger goal is clear.
> 
> > The challenge is to ensure that the verifier prediction of R0 is
> > accurate, so that the eBPF program is not unnecessarily rejected.
> 
> There is a code in the verifier already that checks ret values.
> lsm restrictions should fit right in.
> 
> > > The patch is trying to remember the bitness of the last
> > > operation, but what for?
> > > The registers are 64-bit. There are 32-bit operations,
> > > but they always update the upper 32-bits of the register.
> > > reg_bounds_sync() updates 32 and 64 bit bounds regardless
> > > whether the previous operation was on 32 or 64 bit.
> > 
> > Ok, yes. I also thought that using the 64 bit register should be ok,
> > but selftests fail.
> 
> maybe selftests are buggy?
> they fail with patch 3 alone without patch 2 ?
> please explain exactly the problem.

Ok, I let it run getting what the verifier provides (smin/smax).

smin_value = 0xffffffff, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,
Invalid R0, cannot return > 1
#10      bpf_cookie:FAIL

smin_value = 0x0, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0x0,
Invalid R0, cannot return 1
#58/1    deny_namespace/unpriv_userns_create_no_bpf:FAIL
#58      deny_namespace:FAIL

smin_value = 0x0, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0x0,
Invalid R0, cannot return 1
#100     libbpf_get_fd_by_id_opts:FAIL

smin_value = 0xfffffffe, smax_value = 0xfffffffe,
s32_min_value = 0xfffffffe, s32_max_value = 0xfffffffe,
#114     lookup_key:FAIL

smin_value = 0xffffffff, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,
Invalid R0, cannot return > 1
#210     test_ima:FAIL

smin_value = 0xffffffff, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,
Invalid R0, cannot return > 1
#211     test_local_storage:FAIL

smin_value = 0xffffffff, smax_value = 0xffffffff,
s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,
Invalid R0, cannot return > 1
#212     test_lsm:FAIL

As you can see, these tests fail because smin or smax are positive
values.

I kept the selftest patches. In test_lsm, for example, ret is a
parameter, populated by previous eBPF programs. In this case, I added
an additional check to explicitly reject positive values.

> > Regarding your comment, I have not seen reg_bounds_sync() for the case
> > R = imm.
> 
> because it's unnecessary there.

	__mark_reg_known(regs + insn->dst_reg,
			 (u32)insn->imm);

This prevents smin/smax from being negative. But I know that this was
patched by Jann Horn. Remembering the endianness of the operation,
makes it clear what register value you should use.

> > > It seems you're trying to hack around something that breaks
> > > patch 3 which also looks fishy.
> > 
> > I thought it was a good idea that changes in the LSM infrastructure are
> > automatically reflected in the boundaries that BPF LSM should enforce.
> 
> That's fine. Encoding restrictions in lsm_hook_defs.h
> is the cleanest approach.
> 
> > If not, I'm open to new ideas. If we should use BTF ID sets, I'm fine
> > with it.
> > 
> > > Please explain the problem first with a concrete example.
> > 
> > Ok, I have a simple one:
> > 
> > $ llvm-objdump -d test_bpf_cookie.bpf.o
> > 
> > 0000000000000000 <test_int_hook>:
> > 
> > [...]
> > 
> >        8:       85 00 00 00 0e 00 00 00 call 14
> >        9:       b4 06 00 00 ff ff ff ff w6 = -1
> >       10:       5e 08 07 00 00 00 00 00 if w8 != w0 goto +7 <LBB11_3>
> >       11:       bf 71 00 00 00 00 00 00 r1 = r7
> >       12:       85 00 00 00 ae 00 00 00 call 174
> >       13:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
> >       15:       79 12 00 00 00 00 00 00 r2 = *(u64 *)(r1 + 0)
> >       16:       4f 02 00 00 00 00 00 00 r2 |= r0
> >       17:       7b 21 00 00 00 00 00 00 *(u64 *)(r1 + 0) = r2
> > 
> > smin_value = 0xffffffff, smax_value = 0xffffffff,
> > s32_min_value = 0xffffffff, s32_max_value = 0xffffffff,
> 
> and this applies where?

This is in check_return_code(), for BPF_PROG_TYPE_LSM.

> what reg are you talking about?

R0.

> Where is the issue?

s32_min_value/s32_max_value are the values we should get.

Roberto

Patch

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 70d06a99f0b8..29c9cf6b0d01 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -181,6 +181,7 @@  struct bpf_reg_state {
 	enum bpf_reg_liveness live;
 	/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
 	bool precise;
+	bool alu32;
 };
 
 enum bpf_stack_slot_type {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8c5f0adbbde3..edce85c425a2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10524,9 +10524,13 @@  static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		break;
 	}
 
+	dst_reg->alu32 = false;
+
 	/* ALU32 ops are zero extended into 64bit register */
-	if (alu32)
+	if (alu32) {
 		zext_32_to_64(dst_reg);
+		dst_reg->alu32 = true;
+	}
 	reg_bounds_sync(dst_reg);
 	return 0;
 }
@@ -10700,6 +10704,7 @@  static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 				*dst_reg = *src_reg;
 				dst_reg->live |= REG_LIVE_WRITTEN;
 				dst_reg->subreg_def = DEF_NOT_SUBREG;
+				dst_reg->alu32 = false;
 			} else {
 				/* R1 = (u32) R2 */
 				if (is_pointer_value(env, insn->src_reg)) {
@@ -10716,6 +10721,7 @@  static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 					dst_reg->id = 0;
 					dst_reg->live |= REG_LIVE_WRITTEN;
 					dst_reg->subreg_def = env->insn_idx + 1;
+					dst_reg->alu32 = true;
 				} else {
 					mark_reg_unknown(env, regs,
 							 insn->dst_reg);
@@ -10733,9 +10739,11 @@  static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			if (BPF_CLASS(insn->code) == BPF_ALU64) {
 				__mark_reg_known(regs + insn->dst_reg,
 						 insn->imm);
+				regs[insn->dst_reg].alu32 = false;
 			} else {
 				__mark_reg_known(regs + insn->dst_reg,
 						 (u32)insn->imm);
+				regs[insn->dst_reg].alu32 = true;
 			}
 		}