Skip to contentSkip to conversation

bpf: Fix missed var_off related to movsx in verifier

PATCH Applied Yonghong Song 3 participants 6 messages Jun 15, 2024 – Jun 17, 2024

Subsystems (4)
lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

cover bpf: Fix missed var_off related to movsx in verifier

Zac reported a verification issue ([1]) where verification unexpectedly succeeded. This is due to missing proper var_off setting in verifier related to movsx insn. I found another similar issue as well. This patch set fixed both problems and added three inline asm tests to test these fixes.

[1] https://lore.kernel.org/bpf/CAADnVQLPU0Shz7dWV4bn2BgtGdxN3uFHPeobGBA72tpg5Xoykw@mail.gmail.com/

Yonghong Song (3):
bpf: Add missed var_off setting in set_sext32_default_val()
bpf: Add missed var_off setting in coerce_subreg_to_size_sx() selftests/bpf: Add a few tests to cover

 kernel/bpf/verifier.c                         |  2 +
 .../selftests/bpf/progs/verifier_movsx.c      | 63 +++++++++++++++++++
 2 files changed, 65 insertions(+)
Signature · 1 line
2.43.0
author reviewer
#1 lore raw

PATCH 1/3 bpf: Add missed var_off setting in set_sext32_default_val()

Zac reported a verification failure and Alexei reproduced the issue with a simple reproducer ([1]). The verification failure is due to missed setting for var_off.

The following is the reproducer in [1]:
0: R1=ctx() R10=fp0

  0: (71) r3 = *(u8 *)(r10 -387)        ;
     R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff)) R10=fp0
  1: (bc) w7 = (s8)w3                   ;
     R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))
     R7_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=127,var_off=(0x0; 0x7f))
  2: (36) if w7 >= 0x2533823b goto pc-3
     mark_precise: frame0: last_idx 2 first_idx 0 subseq_idx -1
     mark_precise: frame0: regs=r7 stack= before 1: (bc) w7 = (s8)w3
     mark_precise: frame0: regs=r3 stack= before 0: (71) r3 = *(u8 *)(r10 -387)

2: R7_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=127,var_off=(0x0; 0x7f))
3: (b4) w0 = 0 ; R0_w=0
4: (95) exit

Note that after insn 1, the var_off for R7 is (0x0; 0x7f). This is not correct since upper 24 bits of w7 could be 0 or 1. So correct var_off should be (0x0; 0xffffffff). Missing var_off setting in set_sext32_default_val() caused later incorrect analysis in zext_32_to_64(dst_reg) and reg_bounds_sync(dst_reg).

To fix the issue, set var_off correctly in set_sext32_default_val(). The correct reg state after insn 1 becomes:

  1: (bc) w7 = (s8)w3                   ;
     R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))
     R7_w=scalar(smin=0,smax=umax=0xffffffff,smin32=-128,smax32=127,var_off=(0x0; 0xffffffff))

and at insn 2, the verifier correctly determines either branch is possible.

[1] https://lore.kernel.org/bpf/CAADnVQLPU0Shz7dWV4bn2BgtGdxN3uFHPeobGBA72tpg5Xoykw@mail.gmail.com/

Fixes 8100928c8814 ("bpf: Support new sign-extension mov insns")
---
 kernel/bpf/verifier.c | 1 +
 1 file changed, 1 insertion(+)
kernel/bpf/verifier.c +1 -0
index 010cfee7ffe9..904ef5a03cf5 100644
@@ -6236,6 +6236,7 @@ static void set_sext32_default_val(struct bpf_reg_state *reg, int size)
 	}
 	reg->u32_min_value = 0;
 	reg->u32_max_value = U32_MAX;
+	reg->var_off = tnum_subreg(tnum_unknown);
 }
 
 static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
Signature · 1 line
2.43.0
author reviewer
#2 lore raw

PATCH 2/3 bpf: Add missed var_off setting in coerce_subreg_to_size_sx()

In reply to Yonghong Song

In coerce_subreg_to_size_sx(), for the case where upper sign extension bits are the same for smax32 and smin32 values, we missed to setup properly. This is especially problematic if both smax32 and smin32's sign extension bits are 1.

The following is a simple example illustrating the inconsistent verifier states due to missed var_off:

  0: (85) call bpf_get_prandom_u32#7    ; R0_w=scalar()
  1: (bf) r3 = r0                       ; R0_w=scalar(id=1) R3_w=scalar(id=1)
  2: (57) r3 &= 15                      ; R3_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf))
  3: (47) r3 |= 128                     ; R3_w=scalar(smin=umin=smin32=umin32=128,smax=umax=smax32=umax32=143,var_off=(0x80; 0xf))
  4: (bc) w7 = (s8)w3
  REG INVARIANTS VIOLATION (alu): range bounds violation u64=[0xffffff80, 0x8f] s64=[0xffffff80, 0x8f]
    u32=[0xffffff80, 0x8f] s32=[0x80, 0xffffff8f] var_off=(0x80, 0xf)

The var_off=(0x80, 0xf) is not correct, and the correct one should be var_off=(0xffffff80; 0xf) since from insn 3, we know that at insn 4, the sign extension bits will be 1. This patch fixed this issue by setting var_off properly.

Fixes 8100928c8814 ("bpf: Support new sign-extension mov insns")
---
 kernel/bpf/verifier.c | 1 +
 1 file changed, 1 insertion(+)
kernel/bpf/verifier.c +1 -0
index 904ef5a03cf5..e0a398a97d32 100644
@@ -6281,6 +6281,7 @@ static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
 		reg->s32_max_value = s32_max;
 		reg->u32_min_value = (u32)s32_min;
 		reg->u32_max_value = (u32)s32_max;
+		reg->var_off = tnum_subreg(tnum_range(s32_min, s32_max));
 		return;
 	}
 
Signature · 1 line
2.43.0
author reviewer
#3 lore raw

PATCH 3/3 selftests/bpf: Add a few tests to cover

In reply to Yonghong Song

Add three unit tests in verifier_movsx.c to cover
cases where missed var_off setting can cause
unexpected verification success or failure.

---
 .../selftests/bpf/progs/verifier_movsx.c      | 63 +++++++++++++++++++
 1 file changed, 63 insertions(+)
tools/testing/selftests/bpf/progs/verifier_movsx.c +63 -0
index cbb9d6714f53..028ec855587b 100644
@@ -224,6 +224,69 @@ l0_%=:							\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("MOV32SX, S8, var_off u32_max")
+__failure __msg("infinite loop detected")
+__failure_unpriv __msg_unpriv("back-edge from insn 2 to 0")
+__naked void mov64sx_s32_varoff_1(void)
+{
+	asm volatile ("					\
+l0_%=:							\
+	r3 = *(u8 *)(r10 -387);				\
+	w7 = (s8)w3;					\
+	if w7 >= 0x2533823b goto l0_%=;			\
+	w0 = 0;						\
+	exit;						\
+"	:
+	:
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("MOV32SX, S8, var_off not u32_max, positive after s8 extension")
+__success __retval(0)
+__failure_unpriv __msg_unpriv("frame pointer is read only")
+__naked void mov64sx_s32_varoff_2(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r3 = r0;					\
+	r3 &= 0xf;					\
+	w7 = (s8)w3;					\
+	if w7 s>= 16 goto l0_%=;			\
+	w0 = 0;						\
+	exit;						\
+l0_%=:							\
+	r10 = 1;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("MOV32SX, S8, var_off not u32_max, negative after s8 extension")
+__success __retval(0)
+__failure_unpriv __msg_unpriv("frame pointer is read only")
+__naked void mov64sx_s32_varoff_3(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];			\
+	r3 = r0;					\
+	r3 &= 0xf;					\
+	r3 |= 0x80;					\
+	w7 = (s8)w3;					\
+	if w7 s>= -5 goto l0_%=;			\
+	w0 = 0;						\
+	exit;						\
+l0_%=:							\
+	r10 = 1;					\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 #else
 
 SEC("socket")
Signature · 1 line
2.43.0
maintainer Acked-by on the v1 series
#4 lore raw
In reply to Yonghong Song
Quoted 11 lines · Yonghong Song

Zac reported a verification issue ([1]) where verification unexpectedly succeeded. This is due to missing proper var_off setting in verifier related to movsx insn. I found another similar issue as well. This patch set fixed both problems and added three inline asm tests to test these fixes.

[1] https://lore.kernel.org/bpf/CAADnVQLPU0Shz7dWV4bn2BgtGdxN3uFHPeobGBA72tpg5Xoykw@mail.gmail.com/

Yonghong Song (3):
bpf: Add missed var_off setting in set_sext32_default_val()
bpf: Add missed var_off setting in coerce_subreg_to_size_sx() selftests/bpf: Add a few tests to cover

All looks good, tests cover both patches.

#5 lore raw
In reply to Yonghong Song
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:

Quoted 8 lines · On Sat, 15 Jun 2024 10:46:21 -0700 you wrote:

Zac reported a verification issue ([1]) where verification unexpectedly succeeded. This is due to missing proper var_off setting in verifier related to movsx insn. I found another similar issue as well. This patch set fixed both problems and added three inline asm tests to test these fixes.

[1] https://lore.kernel.org/bpf/CAADnVQLPU0Shz7dWV4bn2BgtGdxN3uFHPeobGBA72tpg5Xoykw@mail.gmail.com/

[...]

Here is the summary with links:
- [bpf,1/3] bpf: Add missed var_off setting in set_sext32_default_val()

    https://git.kernel.org/bpf/bpf/c/380d5f89a481
  - [bpf,2/3] bpf: Add missed var_off setting in coerce_subreg_to_size_sx()
    https://git.kernel.org/bpf/bpf/c/44b7f7151dfc
  - [bpf,3/3] selftests/bpf: Add a few tests to cover
    https://git.kernel.org/bpf/bpf/c/a62293c33b05

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html