bpf: Fix missed var_off related to movsx in verifier
Subsystems (4)
Yonghong Song
reviewercover 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
Yonghong Song
reviewerPATCH 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/
--- kernel/bpf/verifier.c | 1 + 1 file changed, 1 insertion(+)
kernel/bpf/verifier.c +1 -0
@@ -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
Yonghong Song
reviewerPATCH 2/3 bpf: Add missed var_off setting in coerce_subreg_to_size_sx()
In reply to Yonghong SongIn 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.
--- kernel/bpf/verifier.c | 1 + 1 file changed, 1 insertion(+)
kernel/bpf/verifier.c +1 -0
@@ -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
Yonghong Song
reviewerPATCH 3/3 selftests/bpf: Add a few tests to cover
In reply to Yonghong SongAdd 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
@@ -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 ) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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) +{ + asmvolatile (" \ +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
Quoted 11 lines · Yonghong Song
Zac reported a verification issue ([1]) where verification unexpectedly succeeded. This is due to missing proper
var_offsetting 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 missedvar_offsetting inset_sext32_default_val()
bpf: Add missedvar_offsetting incoerce_subreg_to_size_sx()selftests/bpf: Add a few tests to cover
All looks good, tests cover both patches.
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_offsetting 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