1. Patchew
  2. linux
  3. View series

[PATCH bpf] bpf: Do more tight ALU bounds tracking

Kuee K1r0a posted 1 patch 3 years, 8 months ago
There is a newer version of this series
kernel/bpf/verifier.c | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
[PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Kuee K1r0a 3 years, 8 months ago 
32bit bounds and 64bit bounds are updated separately in
adjust_scalar_min_max_vals() currently, let them learn from each other to
get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().

Before:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
    6: (95) exit

It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.

After:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
    6: (95) exit

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Kuee K1r0a <liulin063@gmail.com>
---
 kernel/bpf/verifier.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0efbac0fd126..888aa50fbdc0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		break;
 	}
 
-	/* ALU32 ops are zero extended into 64bit register */
-	if (alu32)
+	if (alu32) {
+		/* ALU32 ops are zero extended into 64bit register */
 		zext_32_to_64(dst_reg);
-	reg_bounds_sync(dst_reg);
+		__reg_combine_32_into_64(dst_reg);
+	} else {
+		__reg_combine_64_into_32(dst_reg);
+	}
 	return 0;
 }
 
-- 
2.25.1
Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Hao Luo 3 years, 8 months ago 
Hi,

On Thu, Jul 28, 2022 at 8:31 PM Kuee K1r0a <liulin063@gmail.com> wrote:
>
> 32bit bounds and 64bit bounds are updated separately in
> adjust_scalar_min_max_vals() currently, let them learn from each other to
> get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Before:
>
>     func#0 @0
>     0: R1=ctx(off=0,imm=0) R10=fp0
>     0: (b7) r0 = 0                        ; R0_w=0
>     1: (b7) r1 = 0                        ; R1_w=0
>     2: (87) r1 = -r1                      ; R1_w=scalar()
>     3: (87) r1 = -r1                      ; R1_w=scalar()
>     4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>     5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
>     6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
>     func#0 @0
>     0: R1=ctx(off=0,imm=0) R10=fp0
>     0: (b7) r0 = 0                        ; R0_w=0
>     1: (b7) r1 = 0                        ; R1_w=0
>     2: (87) r1 = -r1                      ; R1_w=scalar()
>     3: (87) r1 = -r1                      ; R1_w=scalar()
>     4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>     5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
>     6: (95) exit
>
> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
> Signed-off-by: Kuee K1r0a <liulin063@gmail.com>

Please sign with your real name. Thanks.


> ---
>  kernel/bpf/verifier.c | 9 ++++++---
>  1 file changed, 6 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0efbac0fd126..888aa50fbdc0 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>                 break;
>         }
>
> -       /* ALU32 ops are zero extended into 64bit register */
> -       if (alu32)
> +       if (alu32) {
> +               /* ALU32 ops are zero extended into 64bit register */
>                 zext_32_to_64(dst_reg);
> -       reg_bounds_sync(dst_reg);
> +               __reg_combine_32_into_64(dst_reg);
> +       } else {
> +               __reg_combine_64_into_32(dst_reg);
> +       }
>         return 0;
>  }
>
> --
> 2.25.1
>
[PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Youlin Li 3 years, 8 months ago 
32bit bounds and 64bit bounds are updated separately in
adjust_scalar_min_max_vals() currently, let them learn from each other to
get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().

Before:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
    6: (95) exit

It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.

After:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
    6: (95) exit

Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Youlin Li <liulin063@gmail.com>
---
 kernel/bpf/verifier.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0efbac0fd126..888aa50fbdc0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		break;
 	}
 
-	/* ALU32 ops are zero extended into 64bit register */
-	if (alu32)
+	if (alu32) {
+		/* ALU32 ops are zero extended into 64bit register */
 		zext_32_to_64(dst_reg);
-	reg_bounds_sync(dst_reg);
+		__reg_combine_32_into_64(dst_reg);
+	} else {
+		__reg_combine_64_into_32(dst_reg);
+	}
 	return 0;
 }
 
-- 
2.25.1
Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Hao Luo 3 years, 8 months ago 
Hi Youlin,

On Thu, Jul 28, 2022 at 9:44 PM Youlin Li <liulin063@gmail.com> wrote:
>
> 32bit bounds and 64bit bounds are updated separately in
> adjust_scalar_min_max_vals() currently, let them learn from each other to
> get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Before:
>
>     func#0 @0
>     0: R1=ctx(off=0,imm=0) R10=fp0
>     0: (b7) r0 = 0                        ; R0_w=0
>     1: (b7) r1 = 0                        ; R1_w=0
>     2: (87) r1 = -r1                      ; R1_w=scalar()
>     3: (87) r1 = -r1                      ; R1_w=scalar()
>     4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>     5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
>     6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
>     func#0 @0
>     0: R1=ctx(off=0,imm=0) R10=fp0
>     0: (b7) r0 = 0                        ; R0_w=0
>     1: (b7) r1 = 0                        ; R1_w=0
>     2: (87) r1 = -r1                      ; R1_w=scalar()
>     3: (87) r1 = -r1                      ; R1_w=scalar()
>     4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>     5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
>     6: (95) exit
>
> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")

This change looks to me like an improvement, rather than a bug fix. We
probably don't need this tag.

> Signed-off-by: Youlin Li <liulin063@gmail.com>
> ---
>  kernel/bpf/verifier.c | 9 ++++++---
>  1 file changed, 6 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0efbac0fd126..888aa50fbdc0 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>                 break;
>         }
>
> -       /* ALU32 ops are zero extended into 64bit register */
> -       if (alu32)
> +       if (alu32) {
> +               /* ALU32 ops are zero extended into 64bit register */
>                 zext_32_to_64(dst_reg);
> -       reg_bounds_sync(dst_reg);
> +               __reg_combine_32_into_64(dst_reg);

This __reg_combine_32_into_64 can be replaced with simply
reg_bounds_sync, because the above zext_32_to_64 has already
propagated 32 to 64. Using reg_bounds_sync would be more efficient.

It turns out we can now fold reg_bounds_sync into zext_32_to_64. Can
you do that and resend? IMO that will make the code slightly cleaner.

> +       } else {
> +               __reg_combine_64_into_32(dst_reg);
> +       }
>         return 0;
>  }
>
> --
> 2.25.1
>
[PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Youlin Li 3 years, 8 months ago 
In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
to get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().

Also, we can now fold reg_bounds_sync() into zext_32_to_64().

Before:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
    6: (95) exit

It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.

After:

    func#0 @0
    0: R1=ctx(off=0,imm=0) R10=fp0
    0: (b7) r0 = 0                        ; R0_w=0
    1: (b7) r1 = 0                        ; R1_w=0
    2: (87) r1 = -r1                      ; R1_w=scalar()
    3: (87) r1 = -r1                      ; R1_w=scalar()
    4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
    5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
    6: (95) exit

Signed-off-by: Youlin Li <liulin063@gmail.com>
---
 kernel/bpf/verifier.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0efbac0fd126..1f5c6e3634d6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4383,6 +4383,7 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
 {
 	reg->var_off = tnum_subreg(reg->var_off);
 	__reg_assign_32_into_64(reg);
+	reg_bounds_sync(reg);
 }
 
 /* truncate register to smaller size (in bytes)
@@ -8934,10 +8935,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		break;
 	}
 
-	/* ALU32 ops are zero extended into 64bit register */
-	if (alu32)
+	if (alu32) {
+		/* ALU32 ops are zero extended into 64bit register */
 		zext_32_to_64(dst_reg);
-	reg_bounds_sync(dst_reg);
+	} else {
+		__reg_combine_64_into_32(dst_reg);
+	}
 	return 0;
 }
 
@@ -9126,7 +9129,6 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 							 insn->dst_reg);
 				}
 				zext_32_to_64(dst_reg);
-				reg_bounds_sync(dst_reg);
 			}
 		} else {
 			/* case: R = imm
-- 
2.25.1
Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Hao Luo 3 years, 8 months ago 
On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
>
> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
> to get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>
> Before:
>
>     func#0 @0
>     0: R1=ctx(off=0,imm=0) R10=fp0
>     0: (b7) r0 = 0                        ; R0_w=0
>     1: (b7) r1 = 0                        ; R1_w=0
>     2: (87) r1 = -r1                      ; R1_w=scalar()
>     3: (87) r1 = -r1                      ; R1_w=scalar()
>     4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>     5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
>     6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
>     func#0 @0
>     0: R1=ctx(off=0,imm=0) R10=fp0
>     0: (b7) r0 = 0                        ; R0_w=0
>     1: (b7) r1 = 0                        ; R1_w=0
>     2: (87) r1 = -r1                      ; R1_w=scalar()
>     3: (87) r1 = -r1                      ; R1_w=scalar()
>     4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>     5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
>     6: (95) exit
>
> Signed-off-by: Youlin Li <liulin063@gmail.com>

Looks good to me. Thanks Youlin.

Acked-by: Hao Luo <haoluo@google.com>

Hao
Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
Posted by Daniel Borkmann 3 years, 8 months ago 
On 7/30/22 12:48 AM, Hao Luo wrote:
> On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
>>
>> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
>> to get more tight bounds tracking. Similar operation can be found in
>> reg_set_min_max().
>>
>> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>>
>> Before:
>>
>>      func#0 @0
>>      0: R1=ctx(off=0,imm=0) R10=fp0
>>      0: (b7) r0 = 0                        ; R0_w=0
>>      1: (b7) r1 = 0                        ; R1_w=0
>>      2: (87) r1 = -r1                      ; R1_w=scalar()
>>      3: (87) r1 = -r1                      ; R1_w=scalar()
>>      4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>>      5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff))  <--- [*]
>>      6: (95) exit
>>
>> It can be seen that even if the 64bit bounds is clear here, the 32bit
>> bounds is still in the state of 'UNKNOWN'.
>>
>> After:
>>
>>      func#0 @0
>>      0: R1=ctx(off=0,imm=0) R10=fp0
>>      0: (b7) r0 = 0                        ; R0_w=0
>>      1: (b7) r1 = 0                        ; R1_w=0
>>      2: (87) r1 = -r1                      ; R1_w=scalar()
>>      3: (87) r1 = -r1                      ; R1_w=scalar()
>>      4: (c7) r1 s>>= 63                    ; R1_w=scalar(smin=-1,smax=0)
>>      5: (07) r1 += 2                       ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3))  <--- [*]
>>      6: (95) exit
>>
>> Signed-off-by: Youlin Li <liulin063@gmail.com>
> 
> Looks good to me. Thanks Youlin.
> 
> Acked-by: Hao Luo <haoluo@google.com>

Thanks Youlin! Looks like the patch breaks CI [0] e.g.:

   #142/p bounds check after truncation of non-boundary-crossing range FAIL
   Failed to load prog 'Permission denied'!
   invalid access to map value, value_size=8 off=16777215 size=1
   R0 max value is outside of the allowed memory range
   verification time 296 usec
   stack depth 8
   processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0

Please take a look. Also it would be great to add a test_verifier selftest to
assert above case from commit log against future changes.

Thanks,
Daniel

   [0] https://github.com/kernel-patches/bpf/runs/7696324041?check_suite_focus=true

Patchew 2.1-devel-ea86937

© 2016 - 2026 Red Hat, Inc.