[PATCH bpf-next 1/2] bpf: Fail verification for sign-extension of packet data/data_end/data_meta

[PATCH bpf-next 1/2] bpf: Fail verification for sign-extension of packet data/data_end/data_meta

[Yonghong Song]

syzbot reported a kernel crash due to
  commit 1f1e864b6555 ("bpf: Handle sign-extenstin ctx member accesses").
The reason is due to sign-extension of 32-bit load for
packet data/data_end/data_meta uapi field.

The original code looks like:
        r2 = *(s32 *)(r1 + 76) /* load __sk_buff->data */
        r3 = *(u32 *)(r1 + 80) /* load __sk_buff->data_end */
        r0 = r2
        r0 += 8
        if r3 > r0 goto +1
        ...
Note that __sk_buff->data load has 32-bit sign extension.

After verification and convert_ctx_accesses(), the final asm code looks like:
        r2 = *(u64 *)(r1 +208)
        r2 = (s32)r2
        r3 = *(u64 *)(r1 +80)
        r0 = r2
        r0 += 8
        if r3 > r0 goto pc+1
        ...
Note that 'r2 = (s32)r2' may make the kernel __sk_buff->data address invalid
which may cause runtime failure.

Currently, in C code, typically we have
        void *data = (void *)(long)skb->data;
        void *data_end = (void *)(long)skb->data_end;
        ...
and it will generate
        r2 = *(u64 *)(r1 +208)
        r3 = *(u64 *)(r1 +80)
        r0 = r2
        r0 += 8
        if r3 > r0 goto pc+1

If we allow sign-extension,
        void *data = (void *)(long)(int)skb->data;
        void *data_end = (void *)(long)skb->data_end;
        ...
the generated code looks like
        r2 = *(u64 *)(r1 +208)
        r2 <<= 32
        r2 s>>= 32
        r3 = *(u64 *)(r1 +80)
        r0 = r2
        r0 += 8
        if r3 > r0 goto pc+1
and this will cause verification failure since "r2 <<= 32" is not allowed
as "r2" is a packet pointer.

To fix this issue for case
  r2 = *(s32 *)(r1 + 76) /* load __sk_buff->data */
this patch added additional checking in is_valid_access() callback
function for packet data/data_end/data_meta access. If those accesses
are with sign-extenstion, the verification will fail.

  [1] https://lore.kernel.org/bpf/000000000000c90eee061d236d37@google.com/

Reported-by: syzbot+ad9ec60c8eaf69e6f99c@syzkaller.appspotmail.com
Fixes: 1f1e864b6555 ("bpf: Handle sign-extenstin ctx member accesses")
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 include/linux/bpf.h   |  1 +
 kernel/bpf/verifier.c |  5 +++--
 net/core/filter.c     | 21 ++++++++++++++++-----
 3 files changed, 20 insertions(+), 7 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 4f1d4a97b9d1..d7ca17bd314e 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -919,6 +919,7 @@ static_assert(__BPF_REG_TYPE_MAX <= BPF_BASE_TYPE_LIMIT);
  */
 struct bpf_insn_access_aux {
 	enum bpf_reg_type reg_type;
+	bool is_ldsx;
 	union {
 		int ctx_field_size;
 		struct {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8da132a1ef28..3a04eab7a962 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5587,11 +5587,12 @@ static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off,
 /* check access to 'struct bpf_context' fields.  Supports fixed offsets only */
 static int check_ctx_access(struct bpf_verifier_env *env, int insn_idx, int off, int size,
 			    enum bpf_access_type t, enum bpf_reg_type *reg_type,
-			    struct btf **btf, u32 *btf_id)
+			    struct btf **btf, u32 *btf_id, bool is_ldsx)
 {
 	struct bpf_insn_access_aux info = {
 		.reg_type = *reg_type,
 		.log = &env->log,
+		.is_ldsx = is_ldsx,
 	};
 
 	if (env->ops->is_valid_access &&
@@ -6891,7 +6892,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
 			return err;
 
 		err = check_ctx_access(env, insn_idx, off, size, t, &reg_type, &btf,
-				       &btf_id);
+				       &btf_id, is_ldsx);
 		if (err)
 			verbose_linfo(env, insn_idx, "; ");
 		if (!err && t == BPF_READ && value_regno >= 0) {
diff --git a/net/core/filter.c b/net/core/filter.c
index 4cf1d34f7617..771872e43e3f 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -8572,13 +8572,16 @@ static bool bpf_skb_is_valid_access(int off, int size, enum bpf_access_type type
 		if (off + size > offsetofend(struct __sk_buff, cb[4]))
 			return false;
 		break;
+	case bpf_ctx_range(struct __sk_buff, data):
+	case bpf_ctx_range(struct __sk_buff, data_meta):
+	case bpf_ctx_range(struct __sk_buff, data_end):
+		if (info->is_ldsx || size != size_default)
+			return false;
+		break;
 	case bpf_ctx_range_till(struct __sk_buff, remote_ip6[0], remote_ip6[3]):
 	case bpf_ctx_range_till(struct __sk_buff, local_ip6[0], local_ip6[3]):
 	case bpf_ctx_range_till(struct __sk_buff, remote_ip4, remote_ip4):
 	case bpf_ctx_range_till(struct __sk_buff, local_ip4, local_ip4):
-	case bpf_ctx_range(struct __sk_buff, data):
-	case bpf_ctx_range(struct __sk_buff, data_meta):
-	case bpf_ctx_range(struct __sk_buff, data_end):
 		if (size != size_default)
 			return false;
 		break;
@@ -9022,6 +9025,14 @@ static bool xdp_is_valid_access(int off, int size,
 			}
 		}
 		return false;
+	} else {
+		switch (off) {
+		case offsetof(struct xdp_md, data_meta):
+		case offsetof(struct xdp_md, data):
+		case offsetof(struct xdp_md, data_end):
+			if (info->is_ldsx)
+				return false;
+		}
 	}
 
 	switch (off) {
@@ -9347,12 +9358,12 @@ static bool flow_dissector_is_valid_access(int off, int size,
 
 	switch (off) {
 	case bpf_ctx_range(struct __sk_buff, data):
-		if (size != size_default)
+		if (info->is_ldsx || size != size_default)
 			return false;
 		info->reg_type = PTR_TO_PACKET;
 		return true;
 	case bpf_ctx_range(struct __sk_buff, data_end):
-		if (size != size_default)
+		if (info->is_ldsx || size != size_default)
 			return false;
 		info->reg_type = PTR_TO_PACKET_END;
 		return true;
-- 
2.43.0

[PATCH bpf-next 2/2] selftests/bpf: Add tests for ldsx of pkt data/data_end/data_meta accesses

[Yonghong Song]

The following tests are added to verifier_ldsx.c:
  - sign extension of data/data_end/data_meta for tcx programs.
    The actual checking is in bpf_skb_is_valid_access() which
    is called by sk_filter, cg_skb, lwt, tc(tcx) and sk_skb.
  - sign extension of data/data_end/data_meta for xdp programs.
  - sign extension of data/data_end for flow_dissector programs.

All newly-added tests have verification failure with message
"invalid bpf_context access". Without previous patch, all these
tests succeeded verification.

Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 .../selftests/bpf/progs/verifier_ldsx.c       | 168 ++++++++++++++++++
 1 file changed, 168 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_ldsx.c b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
index d4427d8e1217..982b6c9c0b6d 100644
--- a/tools/testing/selftests/bpf/progs/verifier_ldsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
@@ -144,6 +144,174 @@ __naked void ldsx_s32_range(void)
 	: __clobber_all);
 }
 
+SEC("xdp")
+__description("LDSX, xdp s32 xdp_md->data")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_1(void)
+{
+        asm volatile (
+        "r2 = *(s32 *)(r1 + %[xdp_md_data]);"
+        "r3 = *(u32 *)(r1 + %[xdp_md_data_end]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(xdp_md_data, offsetof(struct xdp_md, data)),
+	  __imm_const(xdp_md_data_end, offsetof(struct xdp_md, data_end))
+        : __clobber_all);
+}
+
+SEC("xdp")
+__description("LDSX, xdp s32 xdp_md->data_end")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_2(void)
+{
+        asm volatile (
+        "r2 = *(u32 *)(r1 + %[xdp_md_data]);"
+        "r3 = *(s32 *)(r1 + %[xdp_md_data_end]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(xdp_md_data, offsetof(struct xdp_md, data)),
+	  __imm_const(xdp_md_data_end, offsetof(struct xdp_md, data_end))
+        : __clobber_all);
+}
+
+SEC("xdp")
+__description("LDSX, xdp s32 xdp_md->data_meta")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_3(void)
+{
+        asm volatile (
+        "r2 = *(s32 *)(r1 + %[xdp_md_data_meta]);"
+        "r3 = *(u32 *)(r1 + %[xdp_md_data]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(xdp_md_data_meta, offsetof(struct xdp_md, data_meta)),
+	  __imm_const(xdp_md_data, offsetof(struct xdp_md, data))
+        : __clobber_all);
+}
+
+SEC("tcx/ingress")
+__description("LDSX, tcx s32 __sk_buff->data")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_4(void)
+{
+        asm volatile (
+        "r2 = *(s32 *)(r1 + %[sk_buff_data]);"
+        "r3 = *(u32 *)(r1 + %[sk_buff_data_end]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(sk_buff_data, offsetof(struct __sk_buff, data)),
+	  __imm_const(sk_buff_data_end, offsetof(struct __sk_buff, data_end))
+        : __clobber_all);
+}
+
+SEC("tcx/ingress")
+__description("LDSX, tcx s32 __sk_buff->data_end")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_5(void)
+{
+        asm volatile (
+        "r2 = *(u32 *)(r1 + %[sk_buff_data]);"
+        "r3 = *(s32 *)(r1 + %[sk_buff_data_end]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(sk_buff_data, offsetof(struct __sk_buff, data)),
+	  __imm_const(sk_buff_data_end, offsetof(struct __sk_buff, data_end))
+        : __clobber_all);
+}
+
+SEC("tcx/ingress")
+__description("LDSX, tcx s32 __sk_buff->data_meta")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_6(void)
+{
+        asm volatile (
+        "r2 = *(s32 *)(r1 + %[sk_buff_data_meta]);"
+        "r3 = *(u32 *)(r1 + %[sk_buff_data]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(sk_buff_data_meta, offsetof(struct __sk_buff, data_meta)),
+	  __imm_const(sk_buff_data, offsetof(struct __sk_buff, data))
+        : __clobber_all);
+}
+
+SEC("flow_dissector")
+__description("LDSX, flow_dissector s32 __sk_buff->data")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_7(void)
+{
+        asm volatile (
+        "r2 = *(s32 *)(r1 + %[sk_buff_data]);"
+        "r3 = *(u32 *)(r1 + %[sk_buff_data_end]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(sk_buff_data, offsetof(struct __sk_buff, data)),
+	  __imm_const(sk_buff_data_end, offsetof(struct __sk_buff, data_end))
+        : __clobber_all);
+}
+
+SEC("flow_dissector")
+__description("LDSX, flow_dissector s32 __sk_buff->data_end")
+__failure __msg("invalid bpf_context access")
+__naked void ldsx_ctx_8(void)
+{
+        asm volatile (
+        "r2 = *(u32 *)(r1 + %[sk_buff_data]);"
+        "r3 = *(s32 *)(r1 + %[sk_buff_data_end]);"
+        "r1 = r2;"
+        "r1 += 8;"
+        "if r1 > r3 goto l0_%=;"
+        "r0 = *(u64 *)(r1 - 8);"
+"l0_%=:"
+	"r0 = 0;"
+        "exit;"
+	:
+        : __imm_const(sk_buff_data, offsetof(struct __sk_buff, data)),
+	  __imm_const(sk_buff_data_end, offsetof(struct __sk_buff, data_end))
+        : __clobber_all);
+}
+
 #else
 
 SEC("socket")
-- 
2.43.0

Re: [PATCH bpf-next 1/2] bpf: Fail verification for sign-extension of packet data/data_end/data_meta

[Eduard Zingerman]

On Mon, 2024-07-15 at 13:18 -0700, Yonghong Song wrote:
> syzbot reported a kernel crash due to
>   commit 1f1e864b6555 ("bpf: Handle sign-extenstin ctx member accesses").
> The reason is due to sign-extension of 32-bit load for
> packet data/data_end/data_meta uapi field.
> 
> The original code looks like:
>         r2 = *(s32 *)(r1 + 76) /* load __sk_buff->data */
>         r3 = *(u32 *)(r1 + 80) /* load __sk_buff->data_end */
>         r0 = r2
>         r0 += 8
>         if r3 > r0 goto +1
>         ...
> Note that __sk_buff->data load has 32-bit sign extension.

[...]

> To fix this issue for case
>   r2 = *(s32 *)(r1 + 76) /* load __sk_buff->data */
> this patch added additional checking in is_valid_access() callback
> function for packet data/data_end/data_meta access. If those accesses
> are with sign-extenstion, the verification will fail.
> 
>   [1] https://lore.kernel.org/bpf/000000000000c90eee061d236d37@google.com/
> 
> Reported-by: syzbot+ad9ec60c8eaf69e6f99c@syzkaller.appspotmail.com
> Fixes: 1f1e864b6555 ("bpf: Handle sign-extenstin ctx member accesses")
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---

I looked through all context types and seems like only two types
identified in this patch use u32 values to obtain pointers:
- struct xdp_md       fields: data, data_end, data_meta
- struct __sk_buff    fields: data, data_end, data_meta

Double checked all locations where access to the above fields is
verified, every location is covered by is_ldsx check.

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

Re: [PATCH bpf-next 2/2] selftests/bpf: Add tests for ldsx of pkt data/data_end/data_meta accesses

[Eduard Zingerman]

On Mon, 2024-07-15 at 13:18 -0700, Yonghong Song wrote:

[...]

> +SEC("xdp")
> +__description("LDSX, xdp s32 xdp_md->data")
> +__failure __msg("invalid bpf_context access")
> +__naked void ldsx_ctx_1(void)
> +{
> +        asm volatile (
> +        "r2 = *(s32 *)(r1 + %[xdp_md_data]);"

Nit: this test fails at the first instruction,
     hence there is no need to include it's tail.
     I think it would be good to keep these tests minimal.

> +        "r3 = *(u32 *)(r1 + %[xdp_md_data_end]);"
> +        "r1 = r2;"
> +        "r1 += 8;"
> +        "if r1 > r3 goto l0_%=;"
> +        "r0 = *(u64 *)(r1 - 8);"
> +"l0_%=:"
> +	"r0 = 0;"
> +        "exit;"
> +	:
> +        : __imm_const(xdp_md_data, offsetof(struct xdp_md, data)),
> +	  __imm_const(xdp_md_data_end, offsetof(struct xdp_md, data_end))
> +        : __clobber_all);
> +}

[...]

Re: [PATCH bpf-next 2/2] selftests/bpf: Add tests for ldsx of pkt data/data_end/data_meta accesses

[Yonghong Song]

On 7/16/24 12:54 PM, Eduard Zingerman wrote:
> On Mon, 2024-07-15 at 13:18 -0700, Yonghong Song wrote:
>
> [...]
>
>> +SEC("xdp")
>> +__description("LDSX, xdp s32 xdp_md->data")
>> +__failure __msg("invalid bpf_context access")
>> +__naked void ldsx_ctx_1(void)
>> +{
>> +        asm volatile (
>> +        "r2 = *(s32 *)(r1 + %[xdp_md_data]);"
> Nit: this test fails at the first instruction,
>       hence there is no need to include it's tail.
>       I think it would be good to keep these tests minimal.

Okay, I will shorten the test to have minimum instructions
to reproduce the issue.

>
>> +        "r3 = *(u32 *)(r1 + %[xdp_md_data_end]);"
>> +        "r1 = r2;"
>> +        "r1 += 8;"
>> +        "if r1 > r3 goto l0_%=;"
>> +        "r0 = *(u64 *)(r1 - 8);"
>> +"l0_%=:"
>> +	"r0 = 0;"
>> +        "exit;"
>> +	:
>> +        : __imm_const(xdp_md_data, offsetof(struct xdp_md, data)),
>> +	  __imm_const(xdp_md_data_end, offsetof(struct xdp_md, data_end))
>> +        : __clobber_all);
>> +}
> [...]