[PATCH] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[PATCH] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Kurt Manucredo]

Fix shift-out-of-bounds in ___bpf_prog_run().

UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
shift exponent 248 is too large for 32-bit type 'unsigned int'
https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
---
 kernel/bpf/core.c | 31 +++++++++++++++++++++++++++++--
 1 file changed, 29 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..35cba247c531 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -1411,11 +1411,38 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
 	ALU(SUB,  -)
 	ALU(AND,  &)
 	ALU(OR,   |)
-	ALU(LSH, <<)
-	ALU(RSH, >>)
 	ALU(XOR,  ^)
 	ALU(MUL,  *)
 #undef ALU
+#define ALU(OPCODE, OP)		\
+	ALU64_##OPCODE##_X:		\
+		if (SRC >= 64)		\
+			DST = 0;	\
+		else			\
+			DST = DST OP SRC;	\
+		CONT;			\
+	ALU_##OPCODE##_X:		\
+		if (SRC >= 32)		\
+			DST = 0;	\
+		else			\
+			DST = (u32) DST OP (u32) SRC;	\
+		CONT;			\
+	ALU64_##OPCODE##_K:		\
+		if (IMM >= 64)		\
+			DST = 0;	\
+		else			\
+			DST = DST OP IMM;	\
+		CONT;			\
+	ALU_##OPCODE##_K:		\
+		if (IMM >= 32)		\
+			DST = 0;	\
+		else			\
+			DST = (u32) DST OP (u32) IMM;	\
+		CONT;
+
+	ALU(LSH, <<)
+	ALU(RSH, >>)
+#undef ALU
 	ALU_NEG:
 		DST = (u32) -DST;
 		CONT;
-- 
2.30.2

_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

Re: [PATCH] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Greg KH]

On Wed, May 26, 2021 at 11:40:27PM +0200, Kurt Manucredo wrote:
> Fix shift-out-of-bounds in ___bpf_prog_run().
> 
> UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> shift exponent 248 is too large for 32-bit type 'unsigned int'
> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> 
> Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> ---
>  kernel/bpf/core.c | 31 +++++++++++++++++++++++++++++--
>  1 file changed, 29 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index 5e31ee9f7512..35cba247c531 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -1411,11 +1411,38 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
>  	ALU(SUB,  -)
>  	ALU(AND,  &)
>  	ALU(OR,   |)
> -	ALU(LSH, <<)
> -	ALU(RSH, >>)
>  	ALU(XOR,  ^)
>  	ALU(MUL,  *)
>  #undef ALU
> +#define ALU(OPCODE, OP)		\
> +	ALU64_##OPCODE##_X:		\
> +		if (SRC >= 64)		\
> +			DST = 0;	\
> +		else			\
> +			DST = DST OP SRC;	\
> +		CONT;			\
> +	ALU_##OPCODE##_X:		\
> +		if (SRC >= 32)		\
> +			DST = 0;	\
> +		else			\
> +			DST = (u32) DST OP (u32) SRC;	\
> +		CONT;			\
> +	ALU64_##OPCODE##_K:		\
> +		if (IMM >= 64)		\
> +			DST = 0;	\
> +		else			\
> +			DST = DST OP IMM;	\
> +		CONT;			\
> +	ALU_##OPCODE##_K:		\
> +		if (IMM >= 32)		\
> +			DST = 0;	\
> +		else			\
> +			DST = (u32) DST OP (u32) IMM;	\
> +		CONT;
> +
> +	ALU(LSH, <<)
> +	ALU(RSH, >>)
> +#undef ALU
>  	ALU_NEG:
>  		DST = (u32) -DST;
>  		CONT;
> -- 
> 2.30.2
> 

This looks odd, shouldn't the caller be checked before it gets to this
part of the code?

did syzbot pass its tests with this change?

thanks,

greg k-h
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

[PATCH v2] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Kurt Manucredo]

Fix shift-out-of-bounds in ___bpf_prog_run().

UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
shift exponent 248 is too large for 32-bit type 'unsigned int'

Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
---

Changes since last version:
 - fix shift-out-of-bounds in verifier.c check_alu_op()

 kernel/bpf/verifier.c | 22 +++++++++++++++++-----
 1 file changed, 17 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..04e3bf344ecd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7880,13 +7880,25 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			return -EINVAL;
 		}
 
-		if ((opcode == BPF_LSH || opcode == BPF_RSH ||
-		     opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
+		if (opcode == BPF_LSH || opcode == BPF_RSH ||
+		     opcode == BPF_ARSH) {
 			int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
 
-			if (insn->imm < 0 || insn->imm >= size) {
-				verbose(env, "invalid shift %d\n", insn->imm);
-				return -EINVAL;
+			if (BPF_SRC(insn->code) == BPF_K) {
+				if (insn->imm < 0 || insn->imm >= size) {
+					verbose(env, "invalid shift %d\n", insn->imm);
+					return -EINVAL;
+				}
+			}
+			if (BPF_SRC(insn->code) == BPF_X) {
+				struct bpf_reg_state *src_reg;
+
+				src_reg = &regs[insn->src_reg];
+				if (src_reg->umax_value >= size) {
+					verbose(env, "invalid shift %lld\n",
+							src_reg->umax_value);
+					return -EINVAL;
+				}
 			}
 		}
 
-- 
2.30.2

_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

Re: [PATCH v2] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Greg KH]

On Tue, Jun 01, 2021 at 04:33:09PM +0200, Kurt Manucredo wrote:
> Fix shift-out-of-bounds in ___bpf_prog_run().

How is this "fixed"?

> 
> UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> shift exponent 248 is too large for 32-bit type 'unsigned int'

What is this from?

Any reason you didn't cc: the bpf maintainers and developers?


> Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com

Does this pass the syzbot testing?

thanks,

greg k-h
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

Re: [PATCH v2] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Kurt Manucredo]

On Tue, 1 Jun 2021 17:43:24 +0200, Greg KH <gregkh@linuxfoundation.org> wrote:
> 
> On Tue, Jun 01, 2021 at 04:33:09PM +0200, Kurt Manucredo wrote:
> > Fix shift-out-of-bounds in ___bpf_prog_run().
> 
> How is this "fixed"?
> 
Fix shift-out-of-bounds in ___bpf_prog_run() by adding extra boundary
check in check_alu_op() in verifier.c.

> > 
> > UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> > shift exponent 248 is too large for 32-bit type 'unsigned int'
> 
> What is this from?

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> 
> Any reason you didn't cc: the bpf maintainers and developers?
> 
Yes. I send them to you, the mentees mailing list and Shuah, first, for
review, comment and help. Is this not okay? 

> 
> > Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> 
> Does this pass the syzbot testing?

Yes, it says 'OK' in the 'Result' column at:
https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
It's the latest from fuzzybritches0@gmail.com.

But at this point I cannot say if this is right. Should I send the next
version to everyone?

thanks and kind regards,

Kurt Manucredo

_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

Re: [PATCH v2] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Greg KH]

On Tue, Jun 01, 2021 at 11:28:00PM +0200, Kurt Manucredo wrote:
> On Tue, 1 Jun 2021 17:43:24 +0200, Greg KH <gregkh@linuxfoundation.org> wrote:
> > 
> > On Tue, Jun 01, 2021 at 04:33:09PM +0200, Kurt Manucredo wrote:
> > > Fix shift-out-of-bounds in ___bpf_prog_run().
> > 
> > How is this "fixed"?
> > 
> Fix shift-out-of-bounds in ___bpf_prog_run() by adding extra boundary
> check in check_alu_op() in verifier.c.

Great, say this in the changelog text.

> > > 
> > > UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> > > shift exponent 248 is too large for 32-bit type 'unsigned int'
> > 
> > What is this from?
> 
> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

You should provide this link in the changelog text.

> > Any reason you didn't cc: the bpf maintainers and developers?
> > 
> Yes. I send them to you, the mentees mailing list and Shuah, first, for
> review, comment and help. Is this not okay? 

Ok, didn't know what you were wanting here, you can always ask questions
like this below the --- line of a patch.

> > > Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > 
> > Does this pass the syzbot testing?
> 
> Yes, it says 'OK' in the 'Result' column at:
> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

You should also say something like "passes the syzbot reproducer test"
in the changelog text as well.

> But at this point I cannot say if this is right. Should I send the next
> version to everyone?

Please do!

thanks,

greg k-h
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

Re: [PATCH v2] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Pavel Skripkin]

On Wed, 2 Jun 2021 08:09:48 +0200
Greg KH <gregkh@linuxfoundation.org> wrote:

> On Tue, Jun 01, 2021 at 11:28:00PM +0200, Kurt Manucredo wrote:
> > On Tue, 1 Jun 2021 17:43:24 +0200, Greg KH
> > <gregkh@linuxfoundation.org> wrote:
> > > 
> > > On Tue, Jun 01, 2021 at 04:33:09PM +0200, Kurt Manucredo wrote:
> > > > Fix shift-out-of-bounds in ___bpf_prog_run().
> > > 
> > > How is this "fixed"?
> > > 
> > Fix shift-out-of-bounds in ___bpf_prog_run() by adding extra
> > boundary check in check_alu_op() in verifier.c.
> 
> Great, say this in the changelog text.
> 
> > > > 
> > > > UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> > > > shift exponent 248 is too large for 32-bit type 'unsigned int'
> > > 
> > > What is this from?
> > 
> > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> 
> You should provide this link in the changelog text.
> 
> > > Any reason you didn't cc: the bpf maintainers and developers?
> > > 
> > Yes. I send them to you, the mentees mailing list and Shuah, first,
> > for review, comment and help. Is this not okay? 
> 
> Ok, didn't know what you were wanting here, you can always ask
> questions like this below the --- line of a patch.
> 
> > > > Reported-by:
> > > > syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > > 
> > > Does this pass the syzbot testing?
> > 
> > Yes, it says 'OK' in the 'Result' column at:
> > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> 
> You should also say something like "passes the syzbot reproducer test"
> in the changelog text as well.
> 

Other possible way to tell maintainer, that patch was tested
somehow, is to change Reported-by to Reported-and-tested-by tag received
from syzbot. It might be more nicely :)



With regards,
Pavel Skripkin
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

Re: [PATCH v2] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Kurt Manucredo]

On Wed, 2 Jun 2021 09:36:45 +0300, Pavel Skripkin <paskripkin@gmail.com> wrote:
> 
> On Wed, 2 Jun 2021 08:09:48 +0200
> Greg KH <gregkh@linuxfoundation.org> wrote:
> 
> > On Tue, Jun 01, 2021 at 11:28:00PM +0200, Kurt Manucredo wrote:
> > > On Tue, 1 Jun 2021 17:43:24 +0200, Greg KH
> > > <gregkh@linuxfoundation.org> wrote:
> > > > 
> > > > On Tue, Jun 01, 2021 at 04:33:09PM +0200, Kurt Manucredo wrote:
> > > > > Fix shift-out-of-bounds in ___bpf_prog_run().
> > > > 
> > > > How is this "fixed"?
> > > > 
> > > Fix shift-out-of-bounds in ___bpf_prog_run() by adding extra
> > > boundary check in check_alu_op() in verifier.c.
> > 
> > Great, say this in the changelog text.
> > 
> > > > > 
> > > > > UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> > > > > shift exponent 248 is too large for 32-bit type 'unsigned int'
> > > > 
> > > > What is this from?
> > > 
> > > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> > 
> > You should provide this link in the changelog text.
> > 
> > > > Any reason you didn't cc: the bpf maintainers and developers?
> > > > 
> > > Yes. I send them to you, the mentees mailing list and Shuah, first,
> > > for review, comment and help. Is this not okay? 
> > 
> > Ok, didn't know what you were wanting here, you can always ask
> > questions like this below the --- line of a patch.
> > 
> > > > > Reported-by:
> > > > > syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > > > 
> > > > Does this pass the syzbot testing?
> > > 
> > > Yes, it says 'OK' in the 'Result' column at:
> > > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> > 
> > You should also say something like "passes the syzbot reproducer test"
> > in the changelog text as well.
> > 
> 
> Other possible way to tell maintainer, that patch was tested
> somehow, is to change Reported-by to Reported-and-tested-by tag received
> from syzbot. It might be more nicely :)
> 

thanks Pavel

kind regards

Kurt Manucredo

_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees