[PATCH bpf 1/3] bpf: Fix incorrect delta propagation between linked registers

[PATCH bpf 1/3] bpf: Fix incorrect delta propagation between linked registers

[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 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.

Fixes: 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")
Reported-by: Nathaniel Theis <nathaniel.theis@nccgroup.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/verifier.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a8a0b6e4110e..411ab1b57af4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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 */
-- 
2.43.0

[PATCH bpf 2/3] bpf: Fix print_reg_state's constant scalar dump

[Daniel Borkmann]

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.

Fixes: 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")
Reported-by: Nathaniel Theis <nathaniel.theis@nccgroup.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 kernel/bpf/log.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
index 5aebfc3051e3..4a858fdb6476 100644
--- a/kernel/bpf/log.c
+++ b/kernel/bpf/log.c
@@ -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;
 	}
 
-- 
2.43.0

[PATCH bpf 3/3] selftests/bpf: Add test case for delta propagation

[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
  [...]

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 .../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

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index e26b5150fc43..5356f26bbb3f 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -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); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
new file mode 100644
index 000000000000..8f755d2464cf
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -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)
+{
+	asm volatile ("				\
+	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";
-- 
2.43.0

Re: [PATCH bpf 2/3] bpf: Fix print_reg_state's constant scalar dump

[Andrii Nakryiko]

On Wed, Oct 16, 2024 at 6:49 AM Daniel Borkmann <daniel@iogearbox.net> wrote:
>
> 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.
>
> Fixes: 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")
> Reported-by: Nathaniel Theis <nathaniel.theis@nccgroup.com>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  kernel/bpf/log.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
> index 5aebfc3051e3..4a858fdb6476 100644
> --- a/kernel/bpf/log.c
> +++ b/kernel/bpf/log.c
> @@ -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.

Acked-by: Andrii Nakryiko <andrii@kernel.org>

>         }
>
> --
> 2.43.0
>

Re: [PATCH bpf 3/3] selftests/bpf: Add test case for delta propagation

[Eduard Zingerman]

On Wed, 2024-10-16 at 15:49 +0200, Daniel Borkmann wrote:
> 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
>   [...]
> 
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

Re: [PATCH bpf 1/3] bpf: Fix incorrect delta propagation between linked registers

[Eduard Zingerman]

On Wed, 2024-10-16 at 15:49 +0200, Daniel Borkmann 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 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.
> 
> Fixes: 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")
> Reported-by: Nathaniel Theis <nathaniel.theis@nccgroup.com>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---

Thank you for the fix, missed this on the code review :(

Reviewed-by: Eduard Zingerman <eddyz87@gmail.com>

[...]

Re: [PATCH bpf 1/3] bpf: Fix incorrect delta propagation between linked registers

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf.git (master)
by Andrii Nakryiko <andrii@kernel.org>:

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 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.
> 
> [...]

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!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html