diff mbox series

[v2,bpf-next] bpf: relax verifier restriction on BPF_MOV | BPF_ALU

Message ID 1544202978-19548-1-git-send-email-jiong.wang@netronome.com
State Accepted, archived
Delegated to: BPF Maintainers
Headers show
Series [v2,bpf-next] bpf: relax verifier restriction on BPF_MOV | BPF_ALU | expand

Commit Message

Jiong Wang Dec. 7, 2018, 5:16 p.m. UTC 
Currently, the destination register is marked as unknown for 32-bit
sub-register move (BPF_MOV | BPF_ALU) whenever the source register type is
SCALAR_VALUE.

This is too conservative that some valid cases will be rejected.
Especially, this may turn a constant scalar value into unknown value that
could break some assumptions of verifier.

For example, test_l4lb_noinline.c has the following C code:

    struct real_definition *dst

1:  if (!get_packet_dst(&dst, &pckt, vip_info, is_ipv6))
2:    return TC_ACT_SHOT;
3:
4:  if (dst->flags & F_IPV6) {

get_packet_dst is responsible for initializing "dst" into valid pointer and
return true (1), otherwise return false (0). The compiled instruction
sequence using alu32 will be:

  412: (54) (u32) r7 &= (u32) 1
  413: (bc) (u32) r0 = (u32) r7
  414: (95) exit

insn 413, a BPF_MOV | BPF_ALU, however will turn r0 into unknown value even
r7 contains SCALAR_VALUE 1.

This causes trouble when verifier is walking the code path that hasn't
initialized "dst" inside get_packet_dst, for which case 0 is returned and
we would then expect verifier concluding line 1 in the above C code pass
the "if" check, therefore would skip fall through path starting at line 4.
Now, because r0 returned from callee has became unknown value, so verifier
won't skip analyzing path starting at line 4 and "dst->flags" requires
dereferencing the pointer "dst" which actually hasn't be initialized for
this path.

This patch relaxed the code marking sub-register move destination. For a
SCALAR_VALUE, it is safe to just copy the value from source then truncate
it into 32-bit.

A unit test also included to demonstrate this issue. This test will fail
before this patch.

This relaxation could let verifier skipping more paths for conditional
comparison against immediate. It also let verifier recording a more
accurate/strict value for one register at one state, if this state end up
with going through exit without rejection and it is used for state
comparison later, then it is possible an inaccurate/permissive value is
better. So the real impact on verifier processed insn number is complex.
But in all, without this fix, valid program could be rejected.

From real benchmarking on kernel selftests and Cilium bpf tests, there is
no impact on processed instruction number when tests ares compiled with
default compilation options. There is slightly improvements when they are
compiled with -mattr=+alu32 after this patch.

Also, test_xdp_noinline/-mattr=+alu32 now passed verification. It is
rejected before this fix.

Insn processed before/after this patch:

                        default     -mattr=+alu32

Kernel selftest

Comments

Alexei Starovoitov Dec. 9, 2018, 10:17 p.m. UTC | #1 
On Fri, Dec 07, 2018 at 12:16:18PM -0500, Jiong Wang wrote:
> Currently, the destination register is marked as unknown for 32-bit
> sub-register move (BPF_MOV | BPF_ALU) whenever the source register type is
> SCALAR_VALUE.
> 
> This is too conservative that some valid cases will be rejected.
> Especially, this may turn a constant scalar value into unknown value that
> could break some assumptions of verifier.
> 
> For example, test_l4lb_noinline.c has the following C code:
> 
>     struct real_definition *dst
> 
> 1:  if (!get_packet_dst(&dst, &pckt, vip_info, is_ipv6))
> 2:    return TC_ACT_SHOT;
> 3:
> 4:  if (dst->flags & F_IPV6) {
> 
> get_packet_dst is responsible for initializing "dst" into valid pointer and
> return true (1), otherwise return false (0). The compiled instruction
> sequence using alu32 will be:
> 
>   412: (54) (u32) r7 &= (u32) 1
>   413: (bc) (u32) r0 = (u32) r7
>   414: (95) exit
> 
> insn 413, a BPF_MOV | BPF_ALU, however will turn r0 into unknown value even
> r7 contains SCALAR_VALUE 1.
> 
> This causes trouble when verifier is walking the code path that hasn't
> initialized "dst" inside get_packet_dst, for which case 0 is returned and
> we would then expect verifier concluding line 1 in the above C code pass
> the "if" check, therefore would skip fall through path starting at line 4.
> Now, because r0 returned from callee has became unknown value, so verifier
> won't skip analyzing path starting at line 4 and "dst->flags" requires
> dereferencing the pointer "dst" which actually hasn't be initialized for
> this path.
> 
> This patch relaxed the code marking sub-register move destination. For a
> SCALAR_VALUE, it is safe to just copy the value from source then truncate
> it into 32-bit.
> 
> A unit test also included to demonstrate this issue. This test will fail
> before this patch.
> 
> This relaxation could let verifier skipping more paths for conditional
> comparison against immediate. It also let verifier recording a more
> accurate/strict value for one register at one state, if this state end up
> with going through exit without rejection and it is used for state
> comparison later, then it is possible an inaccurate/permissive value is
> better. So the real impact on verifier processed insn number is complex.
> But in all, without this fix, valid program could be rejected.
> 
> From real benchmarking on kernel selftests and Cilium bpf tests, there is
> no impact on processed instruction number when tests ares compiled with
> default compilation options. There is slightly improvements when they are
> compiled with -mattr=+alu32 after this patch.
> 
> Also, test_xdp_noinline/-mattr=+alu32 now passed verification. It is
> rejected before this fix.
> 
> Insn processed before/after this patch:
> 
>                         default     -mattr=+alu32
> 
> Kernel selftest
> ===
> test_xdp.o              371/371      369/369
> test_l4lb.o             6345/6345    5623/5623
> test_xdp_noinline.o     2971/2971    rejected/2727
> test_tcp_estates.o      429/429      430/430
> 
> Cilium bpf
> ===
> bpf_lb-DLB_L3.o:        2085/2085     1685/1687
> bpf_lb-DLB_L4.o:        2287/2287     1986/1982
> bpf_lb-DUNKNOWN.o:      690/690       622/622
> bpf_lxc.o:              95033/95033   N/A
> bpf_netdev.o:           7245/7245     N/A
> bpf_overlay.o:          2898/2898     3085/2947
> 
> NOTE:
>   - bpf_lxc.o and bpf_netdev.o compiled by -mattr=+alu32 are rejected by
>     verifier due to another issue inside verifier on supporting alu32
>     binary.
>   - Each cilium bpf program could generate several processed insn number,
>     above number is sum of them.
> 
> v1->v2:
>  - Restrict the change on SCALAR_VALUE.
>  - Update benchmark numbers on Cilium bpf tests.
> 
> Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
> ---
>  kernel/bpf/verifier.c                       | 16 ++++++++++++----
>  tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
>  2 files changed, 25 insertions(+), 4 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9584438..777720a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3583,12 +3583,15 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  			return err;
>  
>  		if (BPF_SRC(insn->code) == BPF_X) {
> +			struct bpf_reg_state *src_reg = regs + insn->src_reg;
> +			struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
> +
>  			if (BPF_CLASS(insn->code) == BPF_ALU64) {
>  				/* case: R1 = R2
>  				 * copy register state to dest reg
>  				 */
> -				regs[insn->dst_reg] = regs[insn->src_reg];
> -				regs[insn->dst_reg].live |= REG_LIVE_WRITTEN;
> +				*dst_reg = *src_reg;
> +				dst_reg->live |= REG_LIVE_WRITTEN;
>  			} else {
>  				/* R1 = (u32) R2 */
>  				if (is_pointer_value(env, insn->src_reg)) {
> @@ -3596,9 +3599,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  						"R%d partial copy of pointer\n",
>  						insn->src_reg);
>  					return -EACCES;
> +				} else if (src_reg->type == SCALAR_VALUE) {
> +					*dst_reg = *src_reg;
> +					dst_reg->live |= REG_LIVE_WRITTEN;
> +				} else {
> +					mark_reg_unknown(env, regs,
> +							 insn->dst_reg);

shouldn't we do dst_reg->live |= REG_LIVE_WRITTEN here as well ?
Not a new issue, but probably should fix in the same patch?

>  				}
> -				mark_reg_unknown(env, regs, insn->dst_reg);
> -				coerce_reg_to_size(&regs[insn->dst_reg], 4);
> +				coerce_reg_to_size(dst_reg, 4);
>  			}
>  		} else {
>  			/* case: R = imm
> diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
> index 17021d2..18d0b7f 100644
> --- a/tools/testing/selftests/bpf/test_verifier.c
> +++ b/tools/testing/selftests/bpf/test_verifier.c
> @@ -2936,6 +2936,19 @@ static struct bpf_test tests[] = {
>  		.result = ACCEPT,
>  	},
>  	{
> +		"alu32: mov u32 const",
> +		.insns = {
> +			BPF_MOV32_IMM(BPF_REG_7, 0),
> +			BPF_ALU32_IMM(BPF_AND, BPF_REG_7, 1),
> +			BPF_MOV32_REG(BPF_REG_0, BPF_REG_7),
> +			BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
> +			BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_7, 0),
> +			BPF_EXIT_INSN(),
> +		},
> +		.result = ACCEPT,
> +		.retval = 0,
> +	},
> +	{
>  		"unpriv: partial copy of pointer",
>  		.insns = {
>  			BPF_MOV32_REG(BPF_REG_1, BPF_REG_10),
> -- 
> 2.7.4
>
Jiong Wang Dec. 10, 2018, 9:45 a.m. UTC | #2 
On 09/12/2018 22:17, Alexei Starovoitov wrote:
> On Fri, Dec 07, 2018 at 12:16:18PM -0500, Jiong Wang wrote:
>> Currently, the destination register is marked as unknown for 32-bit
>> sub-register move (BPF_MOV | BPF_ALU) whenever the source register type is
>> SCALAR_VALUE.
>>
>> This is too conservative that some valid cases will be rejected.
>> Especially, this may turn a constant scalar value into unknown value that
>> could break some assumptions of verifier.
>>
>> For example, test_l4lb_noinline.c has the following C code:
>>
>>      struct real_definition *dst
>>
>> 1:  if (!get_packet_dst(&dst, &pckt, vip_info, is_ipv6))
>> 2:    return TC_ACT_SHOT;
>> 3:
>> 4:  if (dst->flags & F_IPV6) {
>>
>> get_packet_dst is responsible for initializing "dst" into valid pointer and
>> return true (1), otherwise return false (0). The compiled instruction
>> sequence using alu32 will be:
>>
>>    412: (54) (u32) r7 &= (u32) 1
>>    413: (bc) (u32) r0 = (u32) r7
>>    414: (95) exit
>>
>> insn 413, a BPF_MOV | BPF_ALU, however will turn r0 into unknown value even
>> r7 contains SCALAR_VALUE 1.
>>
>> This causes trouble when verifier is walking the code path that hasn't
>> initialized "dst" inside get_packet_dst, for which case 0 is returned and
>> we would then expect verifier concluding line 1 in the above C code pass
>> the "if" check, therefore would skip fall through path starting at line 4.
>> Now, because r0 returned from callee has became unknown value, so verifier
>> won't skip analyzing path starting at line 4 and "dst->flags" requires
>> dereferencing the pointer "dst" which actually hasn't be initialized for
>> this path.
>>
>> This patch relaxed the code marking sub-register move destination. For a
>> SCALAR_VALUE, it is safe to just copy the value from source then truncate
>> it into 32-bit.
>>
>> A unit test also included to demonstrate this issue. This test will fail
>> before this patch.
>>
>> This relaxation could let verifier skipping more paths for conditional
>> comparison against immediate. It also let verifier recording a more
>> accurate/strict value for one register at one state, if this state end up
>> with going through exit without rejection and it is used for state
>> comparison later, then it is possible an inaccurate/permissive value is
>> better. So the real impact on verifier processed insn number is complex.
>> But in all, without this fix, valid program could be rejected.
>>
>>  From real benchmarking on kernel selftests and Cilium bpf tests, there is
>> no impact on processed instruction number when tests ares compiled with
>> default compilation options. There is slightly improvements when they are
>> compiled with -mattr=+alu32 after this patch.
>>
>> Also, test_xdp_noinline/-mattr=+alu32 now passed verification. It is
>> rejected before this fix.
>>
>> Insn processed before/after this patch:
>>
>>                          default     -mattr=+alu32
>>
>> Kernel selftest
>> ===
>> test_xdp.o              371/371      369/369
>> test_l4lb.o             6345/6345    5623/5623
>> test_xdp_noinline.o     2971/2971    rejected/2727
>> test_tcp_estates.o      429/429      430/430
>>
>> Cilium bpf
>> ===
>> bpf_lb-DLB_L3.o:        2085/2085     1685/1687
>> bpf_lb-DLB_L4.o:        2287/2287     1986/1982
>> bpf_lb-DUNKNOWN.o:      690/690       622/622
>> bpf_lxc.o:              95033/95033   N/A
>> bpf_netdev.o:           7245/7245     N/A
>> bpf_overlay.o:          2898/2898     3085/2947
>>
>> NOTE:
>>    - bpf_lxc.o and bpf_netdev.o compiled by -mattr=+alu32 are rejected by
>>      verifier due to another issue inside verifier on supporting alu32
>>      binary.
>>    - Each cilium bpf program could generate several processed insn number,
>>      above number is sum of them.
>>
>> v1->v2:
>>   - Restrict the change on SCALAR_VALUE.
>>   - Update benchmark numbers on Cilium bpf tests.
>>
>> Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
>> ---
>>   kernel/bpf/verifier.c                       | 16 ++++++++++++----
>>   tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
>>   2 files changed, 25 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 9584438..777720a 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -3583,12 +3583,15 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>>   			return err;
>>   
>>   		if (BPF_SRC(insn->code) == BPF_X) {
>> +			struct bpf_reg_state *src_reg = regs + insn->src_reg;
>> +			struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
>> +
>>   			if (BPF_CLASS(insn->code) == BPF_ALU64) {
>>   				/* case: R1 = R2
>>   				 * copy register state to dest reg
>>   				 */
>> -				regs[insn->dst_reg] = regs[insn->src_reg];
>> -				regs[insn->dst_reg].live |= REG_LIVE_WRITTEN;
>> +				*dst_reg = *src_reg;
>> +				dst_reg->live |= REG_LIVE_WRITTEN;
>>   			} else {
>>   				/* R1 = (u32) R2 */
>>   				if (is_pointer_value(env, insn->src_reg)) {
>> @@ -3596,9 +3599,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>>   						"R%d partial copy of pointer\n",
>>   						insn->src_reg);
>>   					return -EACCES;
>> +				} else if (src_reg->type == SCALAR_VALUE) {
>> +					*dst_reg = *src_reg;
>> +					dst_reg->live |= REG_LIVE_WRITTEN;
>> +				} else {
>> +					mark_reg_unknown(env, regs,
>> +							 insn->dst_reg);
> shouldn't we do dst_reg->live |= REG_LIVE_WRITTEN here as well ?
> Not a new issue, but probably should fix in the same patch?

check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK) is called before this
chunk of code, it has set REG_LIVE_WRITTEN in dst_reg->live, it just
doesn't update range info. So, if we don't do full register copy, then
I think there is no need to re-set REG_LIVE_WRITTEN, make sense?

Regards,
Jiong
Alexei Starovoitov Dec. 10, 2018, 5:26 p.m. UTC | #3 
On Mon, Dec 10, 2018 at 09:45:30AM +0000, Jiong Wang wrote:
> > >   					return -EACCES;
> > > +				} else if (src_reg->type == SCALAR_VALUE) {
> > > +					*dst_reg = *src_reg;
> > > +					dst_reg->live |= REG_LIVE_WRITTEN;
> > > +				} else {
> > > +					mark_reg_unknown(env, regs,
> > > +							 insn->dst_reg);
> > shouldn't we do dst_reg->live |= REG_LIVE_WRITTEN here as well ?
> > Not a new issue, but probably should fix in the same patch?
> 
> check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK) is called before this
> chunk of code, it has set REG_LIVE_WRITTEN in dst_reg->live, it just
> doesn't update range info. So, if we don't do full register copy, then
> I think there is no need to re-set REG_LIVE_WRITTEN, make sense?

ahh. right. Applied to bpf-next. Thanks!
diff mbox series

Patch

===
test_xdp.o              371/371      369/369
test_l4lb.o             6345/6345    5623/5623
test_xdp_noinline.o     2971/2971    rejected/2727
test_tcp_estates.o      429/429      430/430

Cilium bpf
===
bpf_lb-DLB_L3.o:        2085/2085     1685/1687
bpf_lb-DLB_L4.o:        2287/2287     1986/1982
bpf_lb-DUNKNOWN.o:      690/690       622/622
bpf_lxc.o:              95033/95033   N/A
bpf_netdev.o:           7245/7245     N/A
bpf_overlay.o:          2898/2898     3085/2947

NOTE:
  - bpf_lxc.o and bpf_netdev.o compiled by -mattr=+alu32 are rejected by
    verifier due to another issue inside verifier on supporting alu32
    binary.
  - Each cilium bpf program could generate several processed insn number,
    above number is sum of them.

v1->v2:
 - Restrict the change on SCALAR_VALUE.
 - Update benchmark numbers on Cilium bpf tests.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/verifier.c                       | 16 ++++++++++++----
 tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++
 2 files changed, 25 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9584438..777720a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3583,12 +3583,15 @@  static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			return err;
 
 		if (BPF_SRC(insn->code) == BPF_X) {
+			struct bpf_reg_state *src_reg = regs + insn->src_reg;
+			struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
+
 			if (BPF_CLASS(insn->code) == BPF_ALU64) {
 				/* case: R1 = R2
 				 * copy register state to dest reg
 				 */
-				regs[insn->dst_reg] = regs[insn->src_reg];
-				regs[insn->dst_reg].live |= REG_LIVE_WRITTEN;
+				*dst_reg = *src_reg;
+				dst_reg->live |= REG_LIVE_WRITTEN;
 			} else {
 				/* R1 = (u32) R2 */
 				if (is_pointer_value(env, insn->src_reg)) {
@@ -3596,9 +3599,14 @@  static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 						"R%d partial copy of pointer\n",
 						insn->src_reg);
 					return -EACCES;
+				} else if (src_reg->type == SCALAR_VALUE) {
+					*dst_reg = *src_reg;
+					dst_reg->live |= REG_LIVE_WRITTEN;
+				} else {
+					mark_reg_unknown(env, regs,
+							 insn->dst_reg);
 				}
-				mark_reg_unknown(env, regs, insn->dst_reg);
-				coerce_reg_to_size(&regs[insn->dst_reg], 4);
+				coerce_reg_to_size(dst_reg, 4);
 			}
 		} else {
 			/* case: R = imm
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 17021d2..18d0b7f 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -2936,6 +2936,19 @@  static struct bpf_test tests[] = {
 		.result = ACCEPT,
 	},
 	{
+		"alu32: mov u32 const",
+		.insns = {
+			BPF_MOV32_IMM(BPF_REG_7, 0),
+			BPF_ALU32_IMM(BPF_AND, BPF_REG_7, 1),
+			BPF_MOV32_REG(BPF_REG_0, BPF_REG_7),
+			BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
+			BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_7, 0),
+			BPF_EXIT_INSN(),
+		},
+		.result = ACCEPT,
+		.retval = 0,
+	},
+	{
 		"unpriv: partial copy of pointer",
 		.insns = {
 			BPF_MOV32_REG(BPF_REG_1, BPF_REG_10),