bpf: Fix incorrect delta propagation between linked registers
Subsystems (4)
Daniel Borkmann
maintainerPATCH 1/3 bpf: Fix incorrect delta propagation between linked registers
Nathaniel reported a bug in the linked scalar delta tracking, which can lead to accepting a program with OOB access. The specific code is related to the sync_linked_regs() function and the BPF_ADD_CONST flag, which signifies a constant offset between two scalar registers tracked by the same register id.
The verifier attempts to track "similar" scalars in order to propagate bounds information learned about one scalar to others. For instance, if r1 and r2 are known to contain the same value, then upon encountering 'if (r1 != 0x1234) goto xyz', not only does it know that r1 is equal to 0x1234 on the path where that conditional jump is not taken, it also knows that r2 is.
Additionally, with env->bpf_capable set, the verifier will track scalars which should be a constant delta apart (if r1 is known to be one greater than r2, then if r1 is known to be equal to 0x1234, r2 must be equal to 0x1233.) The code path for the latter in adjust_reg_min_max_vals() is reached when processing both 32 and 64-bit addition operations. While adjust_reg_min_max_vals() knows whether dst_reg was produced by a 32 or a 64-bit addition (based on the alu32 bool), the only information saved in dst_reg is the id of the source register (reg->id, or'ed by BPF_ADD_CONST) and the value of the constant offset (reg->off).
Later, the function sync_linked_regs() will attempt to use this information to propagate bounds information from one register (known_reg) to others, meaning, for all R in linked_regs, it copies known_reg range (and possibly adjusting delta) into R for the case of R->id == known_reg->id.
For the delta adjustment, meaning, matching reg->id with BPF_ADD_CONST, the verifier adjusts the register as reg = known_reg; reg += delta where delta is computed as (s32)reg->off - (s32)known_reg->off and placed as a scalar into a fake_reg to then simulate the addition of reg += fake_reg. This is only correct, however, if the value in reg was created by a 64-bit addition. When reg contains the result of a 32-bit addition operation, its upper 32 bits will always be zero. sync_linked_regs() on the other hand, may cause the verifier to believe that the addition between fake_reg and reg overflows into those upper bits. For example, if reg was generated by adding the constant 1 to known_reg using a 32-bit alu operation, then reg->off is 1 and known_reg->off is 0. If known_reg is known to be the constant 0xFFFFFFFF, sync_linked_regs() will tell the verifier that reg is equal to the constant 0x100000000. This is incorrect as the actual value of reg will be 0, as the 32-bit addition will wrap around.
Example:
0: (b7) r0 = 0; R0_w=0 1: (18) r1 = 0x80000001; R1_w=0x80000001 3: (37) r1 /= 1; R1_w=scalar() 4: (bf) r2 = r1; R1_w=scalar(id=1) R2_w=scalar(id=1) 5: (bf) r4 = r1; R1_w=scalar(id=1) R4_w=scalar(id=1) 6: (04) w2 += 2147483647; R2_w=scalar(id=1+2147483647,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) 7: (04) w4 += 0 ; R4_w=scalar(id=1+0,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
8: (15) if r2 == 0x0 goto pc+1
10: R0=0 R1=0xffffffff80000001 R2=0x7fffffff R4=0xffffffff80000001 R10=fp0
What can be seen here is that r1 is copied to r2 and r4, such that {r1,r2,r4}.id are all the same which later lets sync_linked_regs() to be invoked. Then, in a next step constants are added with alu32 to r2 and r4, setting their ->off, as well as id |= BPF_ADD_CONST. Next, the conditional will bind r2 and propagate ranges to its linked registers. The verifier now believes the upper 32 bits of r4 are r4=0xffffffff80000001, while actually r4=r1=0x80000001.
One approach for a simple fix suitable also for stable is to limit the constant delta tracking to only 64-bit alu addition. If necessary at some later point, BPF_ADD_CONST could be split into BPF_ADD_CONST64 and BPF_ADD_CONST32 to avoid mixing the two under the tradeoff to further complicate sync_linked_regs(). However, none of the added tests from dedf56d775c0 ("selftests/bpf: Add tests for add_const") make this necessary at this point, meaning, BPF CI also passes with just limiting tracking to 64-bit alu addition.
--- kernel/bpf/verifier.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +6 -5
@@ -14270,12 +14270,13 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,* r1 += 0x1 * if r2 < 1000 goto ... * use r1 in memory access -* So remember constant delta between r2 and r1 and update r1 after -* 'if' condition. +* So for 64-bit alu remember constant delta between r2 and r1 and +* update r1 after 'if' condition. */ -if (env->bpf_capable &&BPF_OP (insn->code) ==BPF_ADD && - dst_reg->id &&is_reg_const (src_reg, alu32)) { -u64 val =reg_const_value (src_reg, alu32); +if (env->bpf_capable && +BPF_OP (insn->code) ==BPF_ADD && !alu32 && + dst_reg->id &&is_reg_const (src_reg, false)) { +u64 val =reg_const_value (src_reg, false); if ((dst_reg->id & BPF_ADD_CONST) ||/* prevent overflow in sync_linked_regs() later */
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH 2/3 bpf: Fix print_reg_state's constant scalar dump
print_reg_state() should not consider adding reg->off to reg->var_off.value when dumping scalars. Scalars can be produced with reg->off != 0 through BPF_ADD_CONST, and thus as-is this can skew the register log dump.
--- kernel/bpf/log.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/bpf/log.c +1 -2
@@ -688,8 +688,7 @@ static void print_reg_state(struct bpf_verifier_env *env,if (t ==SCALAR_VALUE && reg->precise)verbose (env,"P" );if (t ==SCALAR_VALUE &&tnum_is_const (reg->var_off)) { -/* reg->off should be 0 for SCALAR_VALUE */ -verbose_snum (env, reg->var_off.value + reg->off); +verbose_snum (env, reg->var_off.value);return ; }
Signature · 1 line
2.43.0
Re: [PATCH bpf 2/3] bpf: Fix print_reg_state's constant scalar dump
Quoted 17 lines · Daniel Borkmann
print_reg_state()should not consider addingreg->offtoreg->var_off.valuewhen dumping scalars. Scalars can be produced withreg->off!= 0 throughBPF_ADD_CONST, and thus as-is this can skew the register log dump.Fixes 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")Reported-by Nathaniel Theis <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>--- kernel/bpf/log.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)kernel/bpf/log.c +0
-0
kernel/bpf/log.c static void print_reg_state(struct bpf_verifier_env *env, · line 692
Quoted 7 lines
kernel/bpf/log.c +1
-2@@ -688,8 +688,7 @@ static void print_reg_state(struct bpf_verifier_env *env,if (t ==SCALAR_VALUE && reg->precise)verbose (env,"P" );if (t ==SCALAR_VALUE &&tnum_is_const (reg->var_off)) { -/* reg->off should be 0 for SCALAR_VALUE */ -verbose_snum (env, reg->var_off.value + reg->off); +verbose_snum (env, reg->var_off.value);return ;
The original code was handling SCALAR_VALUE and PTR_TO_STACK cases, so + reg->off under assumption of reg->off being zero for SCALAR_VALUE case made sense. Now this is a SCALAR_VALUE-only code path, so there is no point in doing this.
Quoted 5 lines
kernel/bpf/log.c +0
-1} --2.43.0
Daniel Borkmann
maintainerPATCH 3/3 selftests/bpf: Add test case for delta propagation
In reply to Daniel BorkmannAdd a small BPF verifier test case to ensure that alu32 additions to registers are not subject to linked scalar delta tracking.
# ./vmtest.sh -- ./test_progs -t verifier_linked_scalars [...] ./test_progs -t verifier_linked_scalars [ 1.413138] tsc: Refined TSC clocksource calibration: 3407.993 MHz [ 1.413524] clocksource: tsc: mask: 0xffffffffffffffff max_cycles: 0x311fcd52370, max_idle_ns: 440795242006 ns [ 1.414223] clocksource: Switched to clocksource tsc [ 1.419640] bpf_testmod: loading out-of-tree module taints kernel. [ 1.420025] bpf_testmod: module verification failed: signature and/or required key missing - tainting kernel #500/1 verifier_linked_scalars/scalars: find linked scalars:OK #500 verifier_linked_scalars:OK Summary: 1/1 PASSED, 0 SKIPPED, 0 FAILED [ 1.590858] ACPI: PM: Preparing to enter system sleep state S5 [ 1.591402] reboot: Power down [...]
--- .../selftests/bpf/prog_tests/verifier.c | 2 ++ .../bpf/progs/verifier_linked_scalars.c | 34 +++++++++++++++++++ 2 files changed, 36 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -44,6 +44,7 @@#include "verifier_ld_ind.skel.h" #include "verifier_ldsx.skel.h" #include "verifier_leak_ptr.skel.h" +#include "verifier_linked_scalars.skel.h" #include "verifier_loops1.skel.h" #include "verifier_lwt.skel.h" #include "verifier_map_in_map.skel.h"
@@ -170,6 +171,7 @@ void test_verifier_jit_convergence(void) { RUN(verifier_jit_convergence); }void test_verifier_ld_ind (void ) {RUN (verifier_ld_ind); }void test_verifier_ldsx (void ) {RUN (verifier_ldsx); }void test_verifier_leak_ptr (void ) {RUN (verifier_leak_ptr); } +void test_verifier_linked_scalars (void ) {RUN (verifier_linked_scalars); }void test_verifier_loops1 (void ) {RUN (verifier_loops1); }void test_verifier_lwt (void ) {RUN (verifier_lwt); }void test_verifier_map_in_map (void ) {RUN (verifier_map_in_map); }
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c new file +34 -0
@@ -0,0 +1,34 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +SEC("socket") +__description("scalars: find linked scalars") +__failure +__msg("math between fp pointer and 2147483647 is not allowed") +__naked void scalars(void) +{ + asmvolatile (" \ +r0 = 0; \ +r1 = 0x80000001 ll; \ +r1 /= 1; \ +r2 = r1; \ +r4 = r1; \ +w2 += 0x7FFFFFFF; \ +w4 += 0; \ +if r2 == 0 goto l1; \ +exit; \ +l1: \ +r4 >>= 63; \ +r3 = 1; \ +r3 -= r4; \ +r3 *= 0x7FFFFFFF; \ +r3 += r10; \ +*(u8*)(r3 - 1) = r0; \ +exit; \ +" ::: __clobber_all); +} + +char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
Re: [PATCH bpf 3/3] selftests/bpf: Add test case for delta propagation
Quoted 18 lines · Daniel Borkmann
Add a small BPF verifier test case to ensure that alu32 additions to registers are not subject to linked scalar delta tracking.
# ./vmtest.sh -- ./test_progs -t verifier_linked_scalars [...] ./test_progs -t verifier_linked_scalars [ 1.413138] tsc: Refined TSC clocksource calibration: 3407.993 MHz [ 1.413524] clocksource: tsc: mask: 0xffffffffffffffff max_cycles: 0x311fcd52370, max_idle_ns: 440795242006 ns [ 1.414223] clocksource: Switched to clocksource tsc [ 1.419640] bpf_testmod: loading out-of-tree module taints kernel. [ 1.420025] bpf_testmod: module verification failed: signature and/or required key missing - tainting kernel #500/1 verifier_linked_scalars/scalars: find linked scalars:OK #500 verifier_linked_scalars:OK Summary: 1/1 PASSED, 0 SKIPPED, 0 FAILED [ 1.590858] ACPI: PM: Preparing to enter system sleep state S5 [ 1.591402] reboot: Power down [...]
Quoted 2 lines
Signed-off-by Daniel Borkmann <[email protected]>---
Quoted 68 lines · Daniel Borkmann
Nathaniel reported a bug in the linked scalar delta tracking, which can lead to accepting a program with OOB access. The specific code is related to the
sync_linked_regs()function and theBPF_ADD_CONSTflag, which signifies a constant offset between two scalar registers tracked by the same register id.The verifier attempts to track "similar" scalars in order to propagate bounds information learned about one scalar to others. For instance, if r1 and r2 are known to contain the same value, then upon encountering 'if (r1 !=
0x1234) goto xyz', not only does it know that r1 is equal to0x1234on the path where that conditional jump is not taken, it also knows that r2 is.Additionally, with
env->bpf_capableset, the verifier will track scalars which should be a constant delta apart (if r1 is known to be one greater than r2, then if r1 is known to be equal to0x1234, r2 must be equal to0x1233.) The code path for the latter inadjust_reg_min_max_vals()is reached when processing both 32 and 64-bit addition operations. Whileadjust_reg_min_max_vals()knows whetherdst_regwas produced by a 32 or a 64-bit addition (based on the alu32 bool), the only information saved indst_regis the id of the source register (reg->id, or'ed byBPF_ADD_CONST) and the value of the constant offset (reg->off).Later, the function
sync_linked_regs()will attempt to use this information to propagate bounds information from one register (known_reg) to others, meaning, for all R inlinked_regs, it copiesknown_regrange (and possibly adjusting delta) into R for the case ofR->id==known_reg->id.For the delta adjustment, meaning, matching
reg->idwithBPF_ADD_CONST, the verifier adjusts the register as reg =known_reg; reg += delta where delta is computed as (s32)reg->off - (s32)known_reg->off and placed as a scalar into afake_regto then simulate the addition of reg +=fake_reg. This is only correct, however, if the value in reg was created by a 64-bit addition. When reg contains the result of a 32-bit addition operation, its upper 32 bits will always be zero.sync_linked_regs()on the other hand, may cause the verifier to believe that the addition betweenfake_regand reg overflows into those upper bits. For example, if reg was generated by adding the constant 1 toknown_regusing a 32-bit alu operation, thenreg->offis 1 andknown_reg->offis 0. Ifknown_regis known to be the constant0xFFFFFFFF,sync_linked_regs()will tell the verifier that reg is equal to the constant0x100000000. This is incorrect as the actual value of reg will be 0, as the 32-bit addition will wrap around.Example:
0: (b7) r0 = 0; R0_w=0 1: (18) r1 = 0x80000001; R1_w=0x80000001 3: (37) r1 /= 1; R1_w=scalar() 4: (bf) r2 = r1; R1_w=scalar(id=1) R2_w=scalar(id=1) 5: (bf) r4 = r1; R1_w=scalar(id=1) R4_w=scalar(id=1) 6: (04) w2 += 2147483647; R2_w=scalar(id=1+2147483647,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) 7: (04) w4 += 0 ; R4_w=scalar(id=1+0,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))8: (15) if r2 ==
0x0goto pc+1
10: R0=0 R1=0xffffffff80000001 R2=0x7fffffff R4=0xffffffff80000001 R10=fp0What can be seen here is that r1 is copied to r2 and r4, such that {r1,r2,r4}.id are all the same which later lets
sync_linked_regs()to be invoked. Then, in a next step constants are added with alu32 to r2 and r4, setting their ->off, as well as id |=BPF_ADD_CONST. Next, the conditional will bind r2 and propagate ranges to its linked registers. The verifier now believes the upper 32 bits of r4 are r4=0xffffffff80000001, while actually r4=r1=0x80000001.One approach for a simple fix suitable also for stable is to limit the constant delta tracking to only 64-bit alu addition. If necessary at some later point,
BPF_ADD_CONSTcould be split intoBPF_ADD_CONST64andBPF_ADD_CONST32to avoid mixing the two under the tradeoff to further complicatesync_linked_regs(). However, none of the added tests fromdedf56d775c0("selftests/bpf: Add tests foradd_const") make this necessary at this point, meaning, BPF CI also passes with just limiting tracking to 64-bit alu addition.
Quoted 4 lines
Fixes 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")Reported-by Nathaniel Theis <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>---
Thank you for the fix, missed this on the code review :(
[...]
This series was applied to bpf/bpf.git (master) by Andrii Nakryiko <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Andrii Nakryiko <[email protected]>:
Quoted 5 lines · On Wed, 16 Oct 2024 15:49:11 +0200 you wrote:
Nathaniel reported a bug in the linked scalar delta tracking, which can lead to accepting a program with OOB access. The specific code is related to the
sync_linked_regs()function and theBPF_ADD_CONSTflag, which signifies a constant offset between two scalar registers tracked by the same register id.
Quoted 7 lines
The verifier attempts to track "similar" scalars in order to propagate bounds information learned about one scalar to others. For instance, if r1 and r2 are known to contain the same value, then upon encountering 'if (r1 !=
0x1234) goto xyz', not only does it know that r1 is equal to0x1234on the path where that conditional jump is not taken, it also knows that r2 is.[...]
Here is the summary with links:
- [bpf,1/3] bpf: Fix incorrect delta propagation between linked registers
https://git.kernel.org/bpf/bpf/c/3878ae04e9fc - [bpf,2/3] bpf: Fix print_reg_state's constant scalar dump https://git.kernel.org/bpf/bpf/c/3e9e708757ca - [bpf,3/3] selftests/bpf: Add test case for delta propagation https://git.kernel.org/bpf/bpf/c/db123e42304d
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html