Skip to contentSkip to conversation

bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

PATCH Superseded Kurt Manucredo 3 participants 8 messages May 26, 2021 – Jun 4, 2021

Subsystems (2)
BPF BPF core

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Kurt Manucredo

author
#0 lore raw

PATCH 1/1 bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

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 [email protected]
Signed-off-by Kurt Manucredo <[email protected]>
---
 kernel/bpf/core.c | 31 +++++++++++++++++++++++++++++--
 1 file changed, 29 insertions(+), 2 deletions(-)
kernel/bpf/core.c +29 -2
index 5e31ee9f7512..35cba247c531 100644
@@ -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;
Signature · 6 lines
2.30.2

_______________________________________________
Linux-kernel-mentees mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees
#1 lore raw
Quoted 60 lines · 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 [email protected]
Signed-off-by Kurt Manucredo <[email protected]>
---
 kernel/bpf/core.c | 31 +++++++++++++++++++++++++++++--
 1 file changed, 29 insertions(+), 2 deletions(-)
kernel/bpf/core.c +29 -2
index 5e31ee9f7512..35cba247c531 100644
@@ -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;
Signature · 1 line
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
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

author
#2 lore raw

PATCH v2 1/1 bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

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 [email protected]
Signed-off-by Kurt Manucredo <[email protected]>

---

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(-)
kernel/bpf/verifier.c +17 -5
index 94ba5163d4c5..04e3bf344ecd 100644
@@ -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;
+				}
 			}
 		}
Signature · 6 lines
2.30.2

_______________________________________________
Linux-kernel-mentees mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees
#3 lore raw
Quoted 1 line · Kurt Manucredo

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

How is this "fixed"?

Quoted 3 lines
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?

Quoted 1 line
Reported-by [email protected]

Does this pass the syzbot testing?

thanks,

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

author
#4 lore raw
Quoted 6 lines · Greg KH
Quoted 1 line · Kurt Manucredo

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.

Quoted 5 lines
Quoted 3 lines
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

Quoted 3 lines

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?

Quoted 4 lines
Quoted 2 lines
Reported-by [email protected]

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

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
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

#5 lore raw
Quoted 9 lines · Kurt Manucredo
Quoted 6 lines · Greg KH
Quoted 1 line · Kurt Manucredo

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.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 3 lines
Quoted 1 line
Reported-by [email protected]

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.

Quoted 2 lines

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
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

#6 lore raw
Quoted 35 lines · On Wed, 2 Jun 2021 08:09:48 +0200 Greg KH <[email protected]> wrote:
Quoted 10 lines · Kurt Manucredo
Quoted 6 lines · Greg KH
Quoted 1 line · Kurt Manucredo

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.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 3 lines
Quoted 3 lines
Quoted 2 lines

Reported-by:
[email protected]

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

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
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

author
#7 lore raw
Quoted 44 lines · Pavel Skripkin
Quoted 40 lines · On Wed, 2 Jun 2021 08:09:48 +0200 Greg KH <[email protected]> wrote:
Quoted 10 lines · Kurt Manucredo
Quoted 6 lines · Greg KH
Quoted 1 line · Kurt Manucredo

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.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

Reported-by:
[email protected]

Does this pass the syzbot testing?

Yes, it says 'OK' in the 'Result' column at:
https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Quoted 8 lines
Quoted 3 lines

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
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees