* [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking
@ 2023-04-17 22:21 Yonghong Song
2023-04-17 22:21 ` [PATCH bpf-next v2 2/2] selftests/bpf: Add a selftest for checking subreg equality Yonghong Song
2023-04-17 23:00 ` [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking patchwork-bot+netdevbpf
0 siblings, 2 replies; 3+ messages in thread
From: Yonghong Song @ 2023-04-17 22:21 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
kernel-team, Martin KaFai Lau
In [1], I tried to remove bpf-specific codes to prevent certain
llvm optimizations, and add llvm TTI (target transform info) hooks
to prevent those optimizations. During this process, I found
if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode
transformation, I will hit the following verification failure with selftests:
...
8: (18) r1 = 0xffffc900001b2230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
13: (bc) w2 = w1 ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (test < __NR_TESTS)
14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0
;
16: (27) r2 *= 28 ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
17: (18) r3 = 0xffffc900001b2118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
19: (0f) r3 += r2 ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
20: (61) r2 = *(u32 *)(r3 +0)
R3 unbounded memory access, make sure to bounds check any such access
processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6
-- END PROG LOAD LOG --
libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
libbpf: failed to load object 'test_tc_dtime'
libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
...
At insn 14, with condition 'w1 < 9', register r1 is changed from an arbitrary
u32 value to `scalar(umax=8,var_off=(0x0; 0xf))`. Register r2, however, remains
as an arbitrary u32 value. Current verifier won't claim r1/r2 equality if
the previous mov is alu32 ('w2 = w1').
If r1 upper 32bit value is not 0, we indeed cannot clamin r1/r2 equality
after 'w2 = w1'. But in this particular case, we know r1 upper 32bit value
is 0, so it is safe to claim r1/r2 equality. This patch exactly did this.
For a 32bit subreg mov, if the src register upper 32bit is 0,
it is okay to claim equality between src and dst registers.
With this patch, the above verification sequence becomes
...
8: (18) r1 = 0xffffc9000048e230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
13: (bc) w2 = w1 ; R1_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff))
; if (test < __NR_TESTS)
14: (a6) if w1 < 0x9 goto pc+1 ; R1_w=scalar(id=6,umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
...
from 14 to 16: R0=2 R1_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R2_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R6=ctx(off=0,imm=0) R10=fp0
16: (27) r2 *= 28 ; R2_w=scalar(umax=224,var_off=(0x0; 0xfc))
17: (18) r3 = 0xffffc9000048e118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
19: (0f) r3 += r2
20: (61) r2 = *(u32 *)(r3 +0) ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R3_w=map_value(off=280,ks=4,vs=564,umax=224,var_off=(0x0; 0xfc),s32_max=252,u32_max=252)
...
and eventually the bpf program can be verified successfully.
[1] https://reviews.llvm.org/D147968
Signed-off-by: Yonghong Song <yhs@fb.com>
---
kernel/bpf/verifier.c | 9 +++++++--
1 file changed, 7 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5dae11ee01c3..1e05355facdc 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12421,12 +12421,17 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
insn->src_reg);
return -EACCES;
} else if (src_reg->type == SCALAR_VALUE) {
+ bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
+
+ if (is_src_reg_u32 && !src_reg->id)
+ src_reg->id = ++env->id_gen;
copy_register_state(dst_reg, src_reg);
- /* Make sure ID is cleared otherwise
+ /* Make sure ID is cleared if src_reg is not in u32 range otherwise
* dst_reg min/max could be incorrectly
* propagated into src_reg by find_equal_scalars()
*/
- dst_reg->id = 0;
+ if (!is_src_reg_u32)
+ dst_reg->id = 0;
dst_reg->live |= REG_LIVE_WRITTEN;
dst_reg->subreg_def = env->insn_idx + 1;
} else {
--
2.34.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH bpf-next v2 2/2] selftests/bpf: Add a selftest for checking subreg equality
2023-04-17 22:21 [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking Yonghong Song
@ 2023-04-17 22:21 ` Yonghong Song
2023-04-17 23:00 ` [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking patchwork-bot+netdevbpf
1 sibling, 0 replies; 3+ messages in thread
From: Yonghong Song @ 2023-04-17 22:21 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
kernel-team, Martin KaFai Lau, Eduard Zingerman
Add a selftest to ensure subreg equality if source register
upper 32bit is 0. Without previous patch, the test will
fail verification.
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Yonghong Song <yhs@fb.com>
---
.../selftests/bpf/prog_tests/verifier.c | 2 +
.../selftests/bpf/progs/verifier_reg_equal.c | 58 +++++++++++++++++++
2 files changed, 60 insertions(+)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_reg_equal.c
v1 -> v2:
- Add some comments for the test
- Add a negative test
diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 73dff693d411..25bc8958dbfe 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -31,6 +31,7 @@
#include "verifier_meta_access.skel.h"
#include "verifier_raw_stack.skel.h"
#include "verifier_raw_tp_writable.skel.h"
+#include "verifier_reg_equal.skel.h"
#include "verifier_ringbuf.skel.h"
#include "verifier_spill_fill.skel.h"
#include "verifier_stack_ptr.skel.h"
@@ -95,6 +96,7 @@ void test_verifier_masking(void) { RUN(verifier_masking); }
void test_verifier_meta_access(void) { RUN(verifier_meta_access); }
void test_verifier_raw_stack(void) { RUN(verifier_raw_stack); }
void test_verifier_raw_tp_writable(void) { RUN(verifier_raw_tp_writable); }
+void test_verifier_reg_equal(void) { RUN(verifier_reg_equal); }
void test_verifier_ringbuf(void) { RUN(verifier_ringbuf); }
void test_verifier_spill_fill(void) { RUN(verifier_spill_fill); }
void test_verifier_stack_ptr(void) { RUN(verifier_stack_ptr); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_reg_equal.c b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
new file mode 100644
index 000000000000..dc1d8c30fb0e
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_reg_equal.c
@@ -0,0 +1,58 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+SEC("socket")
+__description("check w reg equal if r reg upper32 bits 0")
+__success
+__naked void subreg_equality_1(void)
+{
+ asm volatile (" \
+ call %[bpf_ktime_get_ns]; \
+ *(u64 *)(r10 - 8) = r0; \
+ r2 = *(u32 *)(r10 - 8); \
+ /* At this point upper 4-bytes of r2 are 0, \
+ * thus insn w3 = w2 should propagate reg id, \
+ * and w2 < 9 comparison would also propagate \
+ * the range for r3. \
+ */ \
+ w3 = w2; \
+ if w2 < 9 goto l0_%=; \
+ exit; \
+l0_%=: if r3 < 9 goto l1_%=; \
+ /* r1 read is illegal at this point */ \
+ r0 -= r1; \
+l1_%=: exit; \
+" :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+SEC("socket")
+__description("check w reg not equal if r reg upper32 bits not 0")
+__failure __msg("R1 !read_ok")
+__naked void subreg_equality_2(void)
+{
+ asm volatile (" \
+ call %[bpf_ktime_get_ns]; \
+ r2 = r0; \
+ /* Upper 4-bytes of r2 may not be 0, thus insn \
+ * w3 = w2 should not propagate reg id, and \
+ * w2 < 9 comparison should not propagate \
+ * the range for r3 either. \
+ */ \
+ w3 = w2; \
+ if w2 < 9 goto l0_%=; \
+ exit; \
+l0_%=: if r3 < 9 goto l1_%=; \
+ /* r1 read is illegal at this point */ \
+ r0 -= r1; \
+l1_%=: exit; \
+" :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
--
2.34.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking
2023-04-17 22:21 [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking Yonghong Song
2023-04-17 22:21 ` [PATCH bpf-next v2 2/2] selftests/bpf: Add a selftest for checking subreg equality Yonghong Song
@ 2023-04-17 23:00 ` patchwork-bot+netdevbpf
1 sibling, 0 replies; 3+ messages in thread
From: patchwork-bot+netdevbpf @ 2023-04-17 23:00 UTC (permalink / raw)
To: Yonghong Song; +Cc: bpf, ast, andrii, daniel, kernel-team, martin.lau
Hello:
This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Mon, 17 Apr 2023 15:21:34 -0700 you wrote:
> In [1], I tried to remove bpf-specific codes to prevent certain
> llvm optimizations, and add llvm TTI (target transform info) hooks
> to prevent those optimizations. During this process, I found
> if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode
> transformation, I will hit the following verification failure with selftests:
>
> ...
> 8: (18) r1 = 0xffffc900001b2230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
> 10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
> ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
> 11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
> ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
> 12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
> 13: (bc) w2 = w1 ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
> ; if (test < __NR_TESTS)
> 14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0
> ;
> 16: (27) r2 *= 28 ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
> 17: (18) r3 = 0xffffc900001b2118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
> 19: (0f) r3 += r2 ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
> 20: (61) r2 = *(u32 *)(r3 +0)
> R3 unbounded memory access, make sure to bounds check any such access
> processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6
> -- END PROG LOAD LOG --
> libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
> libbpf: failed to load object 'test_tc_dtime'
> libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
> ...
>
> [...]
Here is the summary with links:
- [bpf-next,v2,1/2] bpf: Improve verifier u32 scalar equality checking
https://git.kernel.org/bpf/bpf-next/c/3be49f79555e
- [bpf-next,v2,2/2] selftests/bpf: Add a selftest for checking subreg equality
https://git.kernel.org/bpf/bpf-next/c/49859de997c3
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-04-17 23:00 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-04-17 22:21 [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking Yonghong Song
2023-04-17 22:21 ` [PATCH bpf-next v2 2/2] selftests/bpf: Add a selftest for checking subreg equality Yonghong Song
2023-04-17 23:00 ` [PATCH bpf-next v2 1/2] bpf: Improve verifier u32 scalar equality checking patchwork-bot+netdevbpf
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).