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

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

[Kurt Manucredo]

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-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in ___bpf_prog_run().

Hi everyone,

I hope this fixes it!

kind regards

 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 v3] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Greg KH]

On Wed, Jun 02, 2021 at 09:27:26PM +0000, Kurt Manucredo wrote:
> UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
> shift exponent 248 is too large for 32-bit type 'unsigned int'

I'm sorry, but I still do not understand what this changelog text means.

Please be very descriptive about what you are doing and why you are
doing it.  All that is here is a message from a random tool :(

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 v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Kurt Manucredo]

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
kernel/bpf/core.c:1414:2.

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
missing them and return with error when detected.

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

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
     Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
     check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
     check in ___bpf_prog_run().

thanks

kind regards

Kurt

 kernel/bpf/verifier.c | 30 +++++++++---------------------
 1 file changed, 9 insertions(+), 21 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	u32_min_val = src_reg.u32_min_value;
 	u32_max_val = src_reg.u32_max_value;
 
+	if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+			umax_val >= insn_bitness) {
+		/* Shifts greater than 31 or 63 are undefined.
+		 * This includes shifts by a negative number.
+		 */
+		verbose(env, "invalid shift %lld\n", umax_val);
+		return -EINVAL;
+	}
+
 	if (alu32) {
 		src_known = tnum_subreg_is_const(src_reg.var_off);
 		if ((src_known &&
@@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		scalar_min_max_xor(dst_reg, &src_reg);
 		break;
 	case BPF_LSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_lsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_lsh(dst_reg, &src_reg);
 		break;
 	case BPF_RSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_rsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_rsh(dst_reg, &src_reg);
 		break;
 	case BPF_ARSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_arsh(dst_reg, &src_reg);
 		else
-- 
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 v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Yonghong Song via Linux-kernel-mentees]

On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens
so we can judge whether the patch indeed fixed the issue.

> 
> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> missing them and return with error when detected.
> 
> Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> ---
> 
> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> 
> Changelog:
> ----------
> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
>       Fix commit message.
> v3 - Make it clearer what the fix is for.
> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>       check in check_alu_op() in verifier.c.
> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>       check in ___bpf_prog_run().
> 
> thanks
> 
> kind regards
> 
> Kurt
> 
>   kernel/bpf/verifier.c | 30 +++++++++---------------------
>   1 file changed, 9 insertions(+), 21 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 94ba5163d4c5..ed0eecf20de5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>   	u32_min_val = src_reg.u32_min_value;
>   	u32_max_val = src_reg.u32_max_value;
>   
> +	if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> +			umax_val >= insn_bitness) {
> +		/* Shifts greater than 31 or 63 are undefined.
> +		 * This includes shifts by a negative number.
> +		 */
> +		verbose(env, "invalid shift %lld\n", umax_val);
> +		return -EINVAL;
> +	}

I think your fix is good. I would like to move after
the following code though:

         if (!src_known &&
             opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                 __mark_reg_unknown(env, dst_reg);
                 return 0;
         }

> +
>   	if (alu32) {
>   		src_known = tnum_subreg_is_const(src_reg.var_off);
>   		if ((src_known &&
> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>   		scalar_min_max_xor(dst_reg, &src_reg);
>   		break;
>   	case BPF_LSH:
> -		if (umax_val >= insn_bitness) {
> -			/* Shifts greater than 31 or 63 are undefined.
> -			 * This includes shifts by a negative number.
> -			 */
> -			mark_reg_unknown(env, regs, insn->dst_reg);
> -			break;
> -		}

I think this is what happens. For the above case, we simply
marks the dst reg as unknown and didn't fail verification.
So later on at runtime, the shift optimization will have wrong
shift value (> 31/64). Please correct me if this is not right
analysis. As I mentioned in the early please write detailed
analysis in commit log.

Please also add a test at tools/testing/selftests/bpf/verifier/.


>   		if (alu32)
>   			scalar32_min_max_lsh(dst_reg, &src_reg);
>   		else
>   			scalar_min_max_lsh(dst_reg, &src_reg);
>   		break;
>   	case BPF_RSH:
> -		if (umax_val >= insn_bitness) {
> -			/* Shifts greater than 31 or 63 are undefined.
> -			 * This includes shifts by a negative number.
> -			 */
> -			mark_reg_unknown(env, regs, insn->dst_reg);
> -			break;
> -		}
>   		if (alu32)
>   			scalar32_min_max_rsh(dst_reg, &src_reg);
>   		else
>   			scalar_min_max_rsh(dst_reg, &src_reg);
>   		break;
>   	case BPF_ARSH:
> -		if (umax_val >= insn_bitness) {
> -			/* Shifts greater than 31 or 63 are undefined.
> -			 * This includes shifts by a negative number.
> -			 */
> -			mark_reg_unknown(env, regs, insn->dst_reg);
> -			break;
> -		}
>   		if (alu32)
>   			scalar32_min_max_arsh(dst_reg, &src_reg);
>   		else
> 
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

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

[Alexei Starovoitov]

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
>
>
>
> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> > Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> > kernel/bpf/core.c:1414:2.
>
> This is not enough. We need more information on why this happens
> so we can judge whether the patch indeed fixed the issue.
>
> >
> > I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> > missing them and return with error when detected.
> >
> > Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> > ---
> >
> > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> >
> > Changelog:
> > ----------
> > v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
> >       Fix commit message.
> > v3 - Make it clearer what the fix is for.
> > v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >       check in check_alu_op() in verifier.c.
> > v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >       check in ___bpf_prog_run().
> >
> > thanks
> >
> > kind regards
> >
> > Kurt
> >
> >   kernel/bpf/verifier.c | 30 +++++++++---------------------
> >   1 file changed, 9 insertions(+), 21 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 94ba5163d4c5..ed0eecf20de5 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >       u32_min_val = src_reg.u32_min_value;
> >       u32_max_val = src_reg.u32_max_value;
> >
> > +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> > +                     umax_val >= insn_bitness) {
> > +             /* Shifts greater than 31 or 63 are undefined.
> > +              * This includes shifts by a negative number.
> > +              */
> > +             verbose(env, "invalid shift %lld\n", umax_val);
> > +             return -EINVAL;
> > +     }
>
> I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

> the following code though:
>
>          if (!src_known &&
>              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>                  __mark_reg_unknown(env, dst_reg);
>                  return 0;
>          }
>
> > +
> >       if (alu32) {
> >               src_known = tnum_subreg_is_const(src_reg.var_off);
> >               if ((src_known &&
> > @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >               scalar_min_max_xor(dst_reg, &src_reg);
> >               break;
> >       case BPF_LSH:
> > -             if (umax_val >= insn_bitness) {
> > -                     /* Shifts greater than 31 or 63 are undefined.
> > -                      * This includes shifts by a negative number.
> > -                      */
> > -                     mark_reg_unknown(env, regs, insn->dst_reg);
> > -                     break;
> > -             }
>
> I think this is what happens. For the above case, we simply
> marks the dst reg as unknown and didn't fail verification.
> So later on at runtime, the shift optimization will have wrong
> shift value (> 31/64). Please correct me if this is not right
> analysis. As I mentioned in the early please write detailed
> analysis in commit log.

The large shift is not wrong. It's just undefined.
syzbot has to ignore such cases.
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

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

[Yonghong Song via Linux-kernel-mentees]

On 6/5/21 12:10 PM, Alexei Starovoitov wrote:
> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
>>
>>
>>
>> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
>>> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
>>> kernel/bpf/core.c:1414:2.
>>
>> This is not enough. We need more information on why this happens
>> so we can judge whether the patch indeed fixed the issue.
>>
>>>
>>> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
>>> missing them and return with error when detected.
>>>
>>> Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
>>> ---
>>>
>>> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
>>>
>>> Changelog:
>>> ----------
>>> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
>>>        Fix commit message.
>>> v3 - Make it clearer what the fix is for.
>>> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>        check in check_alu_op() in verifier.c.
>>> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>        check in ___bpf_prog_run().
>>>
>>> thanks
>>>
>>> kind regards
>>>
>>> Kurt
>>>
>>>    kernel/bpf/verifier.c | 30 +++++++++---------------------
>>>    1 file changed, 9 insertions(+), 21 deletions(-)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 94ba5163d4c5..ed0eecf20de5 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>        u32_min_val = src_reg.u32_min_value;
>>>        u32_max_val = src_reg.u32_max_value;
>>>
>>> +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
>>> +                     umax_val >= insn_bitness) {
>>> +             /* Shifts greater than 31 or 63 are undefined.
>>> +              * This includes shifts by a negative number.
>>> +              */
>>> +             verbose(env, "invalid shift %lld\n", umax_val);
>>> +             return -EINVAL;
>>> +     }
>>
>> I think your fix is good. I would like to move after
> 
> I suspect such change will break valid programs that do shift by register.

Oh yes, you are correct. We should guard it with src_known.
But this should be extremely rare with explicit shifting amount being
greater than 31/64 and if it is the case, the compiler will has a
warning.

> 
>> the following code though:
>>
>>           if (!src_known &&
>>               opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>>                   __mark_reg_unknown(env, dst_reg);
>>                   return 0;
>>           }
>>
>>> +
>>>        if (alu32) {
>>>                src_known = tnum_subreg_is_const(src_reg.var_off);
>>>                if ((src_known &&
>>> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>                scalar_min_max_xor(dst_reg, &src_reg);
>>>                break;
>>>        case BPF_LSH:
>>> -             if (umax_val >= insn_bitness) {
>>> -                     /* Shifts greater than 31 or 63 are undefined.
>>> -                      * This includes shifts by a negative number.
>>> -                      */
>>> -                     mark_reg_unknown(env, regs, insn->dst_reg);
>>> -                     break;
>>> -             }
>>
>> I think this is what happens. For the above case, we simply
>> marks the dst reg as unknown and didn't fail verification.
>> So later on at runtime, the shift optimization will have wrong
>> shift value (> 31/64). Please correct me if this is not right
>> analysis. As I mentioned in the early please write detailed
>> analysis in commit log.
> 
> The large shift is not wrong. It's just undefined.
> syzbot has to ignore such cases.

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

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

[Kurt Manucredo]

On Sat, 5 Jun 2021 10:55:25 -0700, Yonghong Song <yhs@fb.com> wrote:
> 
> 
> 
> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> > Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> > kernel/bpf/core.c:1414:2.
> 
> This is not enough. We need more information on why this happens
> so we can judge whether the patch indeed fixed the issue.
> 
> > 
> > I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> > missing them and return with error when detected.
> > 
> > Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> > ---
> > 
> > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> > 
> > Changelog:
> > ----------
> > v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
> >       Fix commit message.
> > v3 - Make it clearer what the fix is for.
> > v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >       check in check_alu_op() in verifier.c.
> > v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >       check in ___bpf_prog_run().
> > 
> > thanks
> > 
> > kind regards
> > 
> > Kurt
> > 
> >   kernel/bpf/verifier.c | 30 +++++++++---------------------
> >   1 file changed, 9 insertions(+), 21 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 94ba5163d4c5..ed0eecf20de5 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >   	u32_min_val = src_reg.u32_min_value;
> >   	u32_max_val = src_reg.u32_max_value;
> >   
> > +	if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> > +			umax_val >= insn_bitness) {
> > +		/* Shifts greater than 31 or 63 are undefined.
> > +		 * This includes shifts by a negative number.
> > +		 */
> > +		verbose(env, "invalid shift %lldn", umax_val);
> > +		return -EINVAL;
> > +	}
> 
> I think your fix is good. I would like to move after
> the following code though:
> 
>          if (!src_known &&
>              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>                  __mark_reg_unknown(env, dst_reg);
>                  return 0;
>          }
> 

It can only be right before that code not after. That's the latest. In the
case of the syzbot bug, opcode == BPF_LSH and !src_known. Therefore it
needs to be before that block of code.

> > +
> >   	if (alu32) {
> >   		src_known = tnum_subreg_is_const(src_reg.var_off);
> >   		if ((src_known &&
> > @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >   		scalar_min_max_xor(dst_reg, &src_reg);
> >   		break;
> >   	case BPF_LSH:
> > -		if (umax_val >= insn_bitness) {
> > -			/* Shifts greater than 31 or 63 are undefined.
> > -			 * This includes shifts by a negative number.
> > -			 */
> > -			mark_reg_unknown(env, regs, insn->dst_reg);
> > -			break;
> > -		}
> 
> I think this is what happens. For the above case, we simply
> marks the dst reg as unknown and didn't fail verification.
> So later on at runtime, the shift optimization will have wrong
> shift value (> 31/64). Please correct me if this is not right
> analysis. As I mentioned in the early please write detailed
> analysis in commit log.
> 

Shouldn't the src reg be changed so that the shift-out-of-bounds can't
occur, if return -EINVAL is not what we want here? Changing the dst reg
might not help. If I look into kernel/bpf/core.c I can see:
	DST = DST OP SRC;

> Please also add a test at tools/testing/selftests/bpf/verifier/.
> 
I'm going to look into selftests,

kind regards
thanks,

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

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

[Kurt Manucredo]

On Sat, 5 Jun 2021 14:39:57 -0700, Yonghong Song <yhs@fb.com> wrote:
> 
> 
> 
> On 6/5/21 12:10 PM, Alexei Starovoitov wrote:
> > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
> >>
> >>
> >>
> >> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> >>> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> >>> kernel/bpf/core.c:1414:2.
> >>
> >> This is not enough. We need more information on why this happens
> >> so we can judge whether the patch indeed fixed the issue.
> >>
> >>>
> >>> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> >>> missing them and return with error when detected.
> >>>
> >>> Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> >>> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> >>> ---
> >>>
> >>> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> >>>
> >>> Changelog:
> >>> ----------
> >>> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
> >>>        Fix commit message.
> >>> v3 - Make it clearer what the fix is for.
> >>> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >>>        check in check_alu_op() in verifier.c.
> >>> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >>>        check in ___bpf_prog_run().
> >>>
> >>> thanks
> >>>
> >>> kind regards
> >>>
> >>> Kurt
> >>>
> >>>    kernel/bpf/verifier.c | 30 +++++++++---------------------
> >>>    1 file changed, 9 insertions(+), 21 deletions(-)
> >>>
> >>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >>> index 94ba5163d4c5..ed0eecf20de5 100644
> >>> --- a/kernel/bpf/verifier.c
> >>> +++ b/kernel/bpf/verifier.c
> >>> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >>>        u32_min_val = src_reg.u32_min_value;
> >>>        u32_max_val = src_reg.u32_max_value;
> >>>
> >>> +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> >>> +                     umax_val >= insn_bitness) {
> >>> +             /* Shifts greater than 31 or 63 are undefined.
> >>> +              * This includes shifts by a negative number.
> >>> +              */
> >>> +             verbose(env, "invalid shift %lldn", umax_val);
> >>> +             return -EINVAL;
> >>> +     }
> >>
> >> I think your fix is good. I would like to move after
> > 
> > I suspect such change will break valid programs that do shift by register.
> 
> Oh yes, you are correct. We should guard it with src_known.
> But this should be extremely rare with explicit shifting amount being
> greater than 31/64 and if it is the case, the compiler will has a
> warning.
> 
> > 
> >> the following code though:
> >>
> >>           if (!src_known &&
> >>               opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> >>                   __mark_reg_unknown(env, dst_reg);
> >>                   return 0;
> >>           }
> >>
> >>> +
> >>>        if (alu32) {
> >>>                src_known = tnum_subreg_is_const(src_reg.var_off);
> >>>                if ((src_known &&
> >>> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >>>                scalar_min_max_xor(dst_reg, &src_reg);
> >>>                break;
> >>>        case BPF_LSH:
> >>> -             if (umax_val >= insn_bitness) {
> >>> -                     /* Shifts greater than 31 or 63 are undefined.
> >>> -                      * This includes shifts by a negative number.
> >>> -                      */
> >>> -                     mark_reg_unknown(env, regs, insn->dst_reg);
> >>> -                     break;
> >>> -             }
> >>
> >> I think this is what happens. For the above case, we simply
> >> marks the dst reg as unknown and didn't fail verification.
> >> So later on at runtime, the shift optimization will have wrong
> >> shift value (> 31/64). Please correct me if this is not right
> >> analysis. As I mentioned in the early please write detailed
> >> analysis in commit log.
> > 
> > The large shift is not wrong. It's just undefined.
> > syzbot has to ignore such cases.
> 
> Agree. This makes sense.

Thanks for your input. If you find I should look closer into this bug
just let me know. I'd love to help. If not it's fine, too. :-)

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 v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Dmitry Vyukov via Linux-kernel-mentees]

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
> > On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> > > Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> > > kernel/bpf/core.c:1414:2.
> >
> > This is not enough. We need more information on why this happens
> > so we can judge whether the patch indeed fixed the issue.
> >
> > >
> > > I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> > > missing them and return with error when detected.
> > >
> > > Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > > Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> > > ---
> > >
> > > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> > >
> > > Changelog:
> > > ----------
> > > v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
> > >       Fix commit message.
> > > v3 - Make it clearer what the fix is for.
> > > v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> > >       check in check_alu_op() in verifier.c.
> > > v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> > >       check in ___bpf_prog_run().
> > >
> > > thanks
> > >
> > > kind regards
> > >
> > > Kurt
> > >
> > >   kernel/bpf/verifier.c | 30 +++++++++---------------------
> > >   1 file changed, 9 insertions(+), 21 deletions(-)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 94ba5163d4c5..ed0eecf20de5 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> > >       u32_min_val = src_reg.u32_min_value;
> > >       u32_max_val = src_reg.u32_max_value;
> > >
> > > +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> > > +                     umax_val >= insn_bitness) {
> > > +             /* Shifts greater than 31 or 63 are undefined.
> > > +              * This includes shifts by a negative number.
> > > +              */
> > > +             verbose(env, "invalid shift %lld\n", umax_val);
> > > +             return -EINVAL;
> > > +     }
> >
> > I think your fix is good. I would like to move after
>
> I suspect such change will break valid programs that do shift by register.
>
> > the following code though:
> >
> >          if (!src_known &&
> >              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> >                  __mark_reg_unknown(env, dst_reg);
> >                  return 0;
> >          }
> >
> > > +
> > >       if (alu32) {
> > >               src_known = tnum_subreg_is_const(src_reg.var_off);
> > >               if ((src_known &&
> > > @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> > >               scalar_min_max_xor(dst_reg, &src_reg);
> > >               break;
> > >       case BPF_LSH:
> > > -             if (umax_val >= insn_bitness) {
> > > -                     /* Shifts greater than 31 or 63 are undefined.
> > > -                      * This includes shifts by a negative number.
> > > -                      */
> > > -                     mark_reg_unknown(env, regs, insn->dst_reg);
> > > -                     break;
> > > -             }
> >
> > I think this is what happens. For the above case, we simply
> > marks the dst reg as unknown and didn't fail verification.
> > So later on at runtime, the shift optimization will have wrong
> > shift value (> 31/64). Please correct me if this is not right
> > analysis. As I mentioned in the early please write detailed
> > analysis in commit log.
>
> The large shift is not wrong. It's just undefined.
> syzbot has to ignore such cases.

Hi Alexei,

The report is produced by KUBSAN. I thought there was an agreement on
cleaning up KUBSAN reports from the kernel (the subset enabled on
syzbot at least).
What exactly cases should KUBSAN ignore?
+linux-hardening/kasan-dev for KUBSAN false positive
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

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

[Kees Cook]

On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:
> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
> > > On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> > > > Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> > > > kernel/bpf/core.c:1414:2.
> > >
> > > This is not enough. We need more information on why this happens
> > > so we can judge whether the patch indeed fixed the issue.
> > >
> > > >
> > > > I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> > > > missing them and return with error when detected.
> > > >
> > > > Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> > > > Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> > > > ---
> > > >
> > > > https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> > > >
> > > > Changelog:
> > > > ----------
> > > > v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
> > > >       Fix commit message.
> > > > v3 - Make it clearer what the fix is for.
> > > > v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> > > >       check in check_alu_op() in verifier.c.
> > > > v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> > > >       check in ___bpf_prog_run().
> > > >
> > > > thanks
> > > >
> > > > kind regards
> > > >
> > > > Kurt
> > > >
> > > >   kernel/bpf/verifier.c | 30 +++++++++---------------------
> > > >   1 file changed, 9 insertions(+), 21 deletions(-)
> > > >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 94ba5163d4c5..ed0eecf20de5 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> > > >       u32_min_val = src_reg.u32_min_value;
> > > >       u32_max_val = src_reg.u32_max_value;
> > > >
> > > > +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> > > > +                     umax_val >= insn_bitness) {
> > > > +             /* Shifts greater than 31 or 63 are undefined.
> > > > +              * This includes shifts by a negative number.
> > > > +              */
> > > > +             verbose(env, "invalid shift %lld\n", umax_val);
> > > > +             return -EINVAL;
> > > > +     }
> > >
> > > I think your fix is good. I would like to move after
> >
> > I suspect such change will break valid programs that do shift by register.
> >
> > > the following code though:
> > >
> > >          if (!src_known &&
> > >              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> > >                  __mark_reg_unknown(env, dst_reg);
> > >                  return 0;
> > >          }
> > >
> > > > +
> > > >       if (alu32) {
> > > >               src_known = tnum_subreg_is_const(src_reg.var_off);
> > > >               if ((src_known &&
> > > > @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> > > >               scalar_min_max_xor(dst_reg, &src_reg);
> > > >               break;
> > > >       case BPF_LSH:
> > > > -             if (umax_val >= insn_bitness) {
> > > > -                     /* Shifts greater than 31 or 63 are undefined.
> > > > -                      * This includes shifts by a negative number.
> > > > -                      */
> > > > -                     mark_reg_unknown(env, regs, insn->dst_reg);
> > > > -                     break;
> > > > -             }
> > >
> > > I think this is what happens. For the above case, we simply
> > > marks the dst reg as unknown and didn't fail verification.
> > > So later on at runtime, the shift optimization will have wrong
> > > shift value (> 31/64). Please correct me if this is not right
> > > analysis. As I mentioned in the early please write detailed
> > > analysis in commit log.
> >
> > The large shift is not wrong. It's just undefined.
> > syzbot has to ignore such cases.
> 
> Hi Alexei,
> 
> The report is produced by KUBSAN. I thought there was an agreement on
> cleaning up KUBSAN reports from the kernel (the subset enabled on
> syzbot at least).
> What exactly cases should KUBSAN ignore?
> +linux-hardening/kasan-dev for KUBSAN false positive

Can check_shl_overflow() be used at all? Best to just make things
readable and compiler-happy, whatever the implementation. :)

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

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

[Yonghong Song via Linux-kernel-mentees]

On 6/9/21 11:20 AM, Kees Cook wrote:
> On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:
>> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
>> <alexei.starovoitov@gmail.com> wrote:
>>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
>>>> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
>>>>> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
>>>>> kernel/bpf/core.c:1414:2.
>>>>
>>>> This is not enough. We need more information on why this happens
>>>> so we can judge whether the patch indeed fixed the issue.
>>>>
>>>>>
>>>>> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
>>>>> missing them and return with error when detected.
>>>>>
>>>>> Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
>>>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
>>>>> ---
>>>>>
>>>>> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
>>>>>
>>>>> Changelog:
>>>>> ----------
>>>>> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
>>>>>        Fix commit message.
>>>>> v3 - Make it clearer what the fix is for.
>>>>> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>>>        check in check_alu_op() in verifier.c.
>>>>> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>>>        check in ___bpf_prog_run().
>>>>>
>>>>> thanks
>>>>>
>>>>> kind regards
>>>>>
>>>>> Kurt
>>>>>
>>>>>    kernel/bpf/verifier.c | 30 +++++++++---------------------
>>>>>    1 file changed, 9 insertions(+), 21 deletions(-)
>>>>>
>>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>>> index 94ba5163d4c5..ed0eecf20de5 100644
>>>>> --- a/kernel/bpf/verifier.c
>>>>> +++ b/kernel/bpf/verifier.c
>>>>> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>>>        u32_min_val = src_reg.u32_min_value;
>>>>>        u32_max_val = src_reg.u32_max_value;
>>>>>
>>>>> +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
>>>>> +                     umax_val >= insn_bitness) {
>>>>> +             /* Shifts greater than 31 or 63 are undefined.
>>>>> +              * This includes shifts by a negative number.
>>>>> +              */
>>>>> +             verbose(env, "invalid shift %lld\n", umax_val);
>>>>> +             return -EINVAL;
>>>>> +     }
>>>>
>>>> I think your fix is good. I would like to move after
>>>
>>> I suspect such change will break valid programs that do shift by register.
>>>
>>>> the following code though:
>>>>
>>>>           if (!src_known &&
>>>>               opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>>>>                   __mark_reg_unknown(env, dst_reg);
>>>>                   return 0;
>>>>           }
>>>>
>>>>> +
>>>>>        if (alu32) {
>>>>>                src_known = tnum_subreg_is_const(src_reg.var_off);
>>>>>                if ((src_known &&
>>>>> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>>>                scalar_min_max_xor(dst_reg, &src_reg);
>>>>>                break;
>>>>>        case BPF_LSH:
>>>>> -             if (umax_val >= insn_bitness) {
>>>>> -                     /* Shifts greater than 31 or 63 are undefined.
>>>>> -                      * This includes shifts by a negative number.
>>>>> -                      */
>>>>> -                     mark_reg_unknown(env, regs, insn->dst_reg);
>>>>> -                     break;
>>>>> -             }
>>>>
>>>> I think this is what happens. For the above case, we simply
>>>> marks the dst reg as unknown and didn't fail verification.
>>>> So later on at runtime, the shift optimization will have wrong
>>>> shift value (> 31/64). Please correct me if this is not right
>>>> analysis. As I mentioned in the early please write detailed
>>>> analysis in commit log.
>>>
>>> The large shift is not wrong. It's just undefined.
>>> syzbot has to ignore such cases.
>>
>> Hi Alexei,
>>
>> The report is produced by KUBSAN. I thought there was an agreement on
>> cleaning up KUBSAN reports from the kernel (the subset enabled on
>> syzbot at least).
>> What exactly cases should KUBSAN ignore?
>> +linux-hardening/kasan-dev for KUBSAN false positive
> 
> Can check_shl_overflow() be used at all? Best to just make things
> readable and compiler-happy, whatever the implementation. :)

This is not a compile issue. If the shift amount is a constant,
compiler should have warned and user should fix the warning.

This is because user code has
something like
     a << s;
where s is a unknown variable and
verifier just marked the result of a << s as unknown value.
Verifier may not reject the code depending on how a << s result
is used.

If bpf program writer uses check_shl_overflow() or some kind
of checking for shift value and won't do shifting if the
shifting may cause an undefined result, there should not
be any kubsan warning.

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

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

[Dmitry Vyukov via Linux-kernel-mentees]

On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote:
> On 6/9/21 11:20 AM, Kees Cook wrote:
> > On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:
> >> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
> >> <alexei.starovoitov@gmail.com> wrote:
> >>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
> >>>> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> >>>>> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> >>>>> kernel/bpf/core.c:1414:2.
> >>>>
> >>>> This is not enough. We need more information on why this happens
> >>>> so we can judge whether the patch indeed fixed the issue.
> >>>>
> >>>>>
> >>>>> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
> >>>>> missing them and return with error when detected.
> >>>>>
> >>>>> Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
> >>>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
> >>>>> ---
> >>>>>
> >>>>> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
> >>>>>
> >>>>> Changelog:
> >>>>> ----------
> >>>>> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
> >>>>>        Fix commit message.
> >>>>> v3 - Make it clearer what the fix is for.
> >>>>> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >>>>>        check in check_alu_op() in verifier.c.
> >>>>> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
> >>>>>        check in ___bpf_prog_run().
> >>>>>
> >>>>> thanks
> >>>>>
> >>>>> kind regards
> >>>>>
> >>>>> Kurt
> >>>>>
> >>>>>    kernel/bpf/verifier.c | 30 +++++++++---------------------
> >>>>>    1 file changed, 9 insertions(+), 21 deletions(-)
> >>>>>
> >>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >>>>> index 94ba5163d4c5..ed0eecf20de5 100644
> >>>>> --- a/kernel/bpf/verifier.c
> >>>>> +++ b/kernel/bpf/verifier.c
> >>>>> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >>>>>        u32_min_val = src_reg.u32_min_value;
> >>>>>        u32_max_val = src_reg.u32_max_value;
> >>>>>
> >>>>> +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
> >>>>> +                     umax_val >= insn_bitness) {
> >>>>> +             /* Shifts greater than 31 or 63 are undefined.
> >>>>> +              * This includes shifts by a negative number.
> >>>>> +              */
> >>>>> +             verbose(env, "invalid shift %lld\n", umax_val);
> >>>>> +             return -EINVAL;
> >>>>> +     }
> >>>>
> >>>> I think your fix is good. I would like to move after
> >>>
> >>> I suspect such change will break valid programs that do shift by register.
> >>>
> >>>> the following code though:
> >>>>
> >>>>           if (!src_known &&
> >>>>               opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> >>>>                   __mark_reg_unknown(env, dst_reg);
> >>>>                   return 0;
> >>>>           }
> >>>>
> >>>>> +
> >>>>>        if (alu32) {
> >>>>>                src_known = tnum_subreg_is_const(src_reg.var_off);
> >>>>>                if ((src_known &&
> >>>>> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> >>>>>                scalar_min_max_xor(dst_reg, &src_reg);
> >>>>>                break;
> >>>>>        case BPF_LSH:
> >>>>> -             if (umax_val >= insn_bitness) {
> >>>>> -                     /* Shifts greater than 31 or 63 are undefined.
> >>>>> -                      * This includes shifts by a negative number.
> >>>>> -                      */
> >>>>> -                     mark_reg_unknown(env, regs, insn->dst_reg);
> >>>>> -                     break;
> >>>>> -             }
> >>>>
> >>>> I think this is what happens. For the above case, we simply
> >>>> marks the dst reg as unknown and didn't fail verification.
> >>>> So later on at runtime, the shift optimization will have wrong
> >>>> shift value (> 31/64). Please correct me if this is not right
> >>>> analysis. As I mentioned in the early please write detailed
> >>>> analysis in commit log.
> >>>
> >>> The large shift is not wrong. It's just undefined.
> >>> syzbot has to ignore such cases.
> >>
> >> Hi Alexei,
> >>
> >> The report is produced by KUBSAN. I thought there was an agreement on
> >> cleaning up KUBSAN reports from the kernel (the subset enabled on
> >> syzbot at least).
> >> What exactly cases should KUBSAN ignore?
> >> +linux-hardening/kasan-dev for KUBSAN false positive
> >
> > Can check_shl_overflow() be used at all? Best to just make things
> > readable and compiler-happy, whatever the implementation. :)
>
> This is not a compile issue. If the shift amount is a constant,
> compiler should have warned and user should fix the warning.
>
> This is because user code has
> something like
>      a << s;
> where s is a unknown variable and
> verifier just marked the result of a << s as unknown value.
> Verifier may not reject the code depending on how a << s result
> is used.
>
> If bpf program writer uses check_shl_overflow() or some kind
> of checking for shift value and won't do shifting if the
> shifting may cause an undefined result, there should not
> be any kubsan warning.

I guess the main question: what should happen if a bpf program writer
does _not_ use compiler nor check_shl_overflow()?
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

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

[Yonghong Song via Linux-kernel-mentees]

On 6/9/21 10:32 PM, Dmitry Vyukov wrote:
> On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote:
>> On 6/9/21 11:20 AM, Kees Cook wrote:
>>> On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:
>>>> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
>>>> <alexei.starovoitov@gmail.com> wrote:
>>>>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
>>>>>> On 6/5/21 8:01 AM, Kurt Manucredo wrote:
>>>>>>> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
>>>>>>> kernel/bpf/core.c:1414:2.
>>>>>>
>>>>>> This is not enough. We need more information on why this happens
>>>>>> so we can judge whether the patch indeed fixed the issue.
>>>>>>
>>>>>>>
>>>>>>> I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
>>>>>>> missing them and return with error when detected.
>>>>>>>
>>>>>>> Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
>>>>>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@gmail.com>
>>>>>>> ---
>>>>>>>
>>>>>>> https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231
>>>>>>>
>>>>>>> Changelog:
>>>>>>> ----------
>>>>>>> v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
>>>>>>>         Fix commit message.
>>>>>>> v3 - Make it clearer what the fix is for.
>>>>>>> v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>>>>>         check in check_alu_op() in verifier.c.
>>>>>>> v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
>>>>>>>         check in ___bpf_prog_run().
>>>>>>>
>>>>>>> thanks
>>>>>>>
>>>>>>> kind regards
>>>>>>>
>>>>>>> Kurt
>>>>>>>
>>>>>>>     kernel/bpf/verifier.c | 30 +++++++++---------------------
>>>>>>>     1 file changed, 9 insertions(+), 21 deletions(-)
>>>>>>>
>>>>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>>>>> index 94ba5163d4c5..ed0eecf20de5 100644
>>>>>>> --- a/kernel/bpf/verifier.c
>>>>>>> +++ b/kernel/bpf/verifier.c
>>>>>>> @@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>>>>>         u32_min_val = src_reg.u32_min_value;
>>>>>>>         u32_max_val = src_reg.u32_max_value;
>>>>>>>
>>>>>>> +     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
>>>>>>> +                     umax_val >= insn_bitness) {
>>>>>>> +             /* Shifts greater than 31 or 63 are undefined.
>>>>>>> +              * This includes shifts by a negative number.
>>>>>>> +              */
>>>>>>> +             verbose(env, "invalid shift %lld\n", umax_val);
>>>>>>> +             return -EINVAL;
>>>>>>> +     }
>>>>>>
>>>>>> I think your fix is good. I would like to move after
>>>>>
>>>>> I suspect such change will break valid programs that do shift by register.
>>>>>
>>>>>> the following code though:
>>>>>>
>>>>>>            if (!src_known &&
>>>>>>                opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>>>>>>                    __mark_reg_unknown(env, dst_reg);
>>>>>>                    return 0;
>>>>>>            }
>>>>>>
>>>>>>> +
>>>>>>>         if (alu32) {
>>>>>>>                 src_known = tnum_subreg_is_const(src_reg.var_off);
>>>>>>>                 if ((src_known &&
>>>>>>> @@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>>>>>>                 scalar_min_max_xor(dst_reg, &src_reg);
>>>>>>>                 break;
>>>>>>>         case BPF_LSH:
>>>>>>> -             if (umax_val >= insn_bitness) {
>>>>>>> -                     /* Shifts greater than 31 or 63 are undefined.
>>>>>>> -                      * This includes shifts by a negative number.
>>>>>>> -                      */
>>>>>>> -                     mark_reg_unknown(env, regs, insn->dst_reg);
>>>>>>> -                     break;
>>>>>>> -             }
>>>>>>
>>>>>> I think this is what happens. For the above case, we simply
>>>>>> marks the dst reg as unknown and didn't fail verification.
>>>>>> So later on at runtime, the shift optimization will have wrong
>>>>>> shift value (> 31/64). Please correct me if this is not right
>>>>>> analysis. As I mentioned in the early please write detailed
>>>>>> analysis in commit log.
>>>>>
>>>>> The large shift is not wrong. It's just undefined.
>>>>> syzbot has to ignore such cases.
>>>>
>>>> Hi Alexei,
>>>>
>>>> The report is produced by KUBSAN. I thought there was an agreement on
>>>> cleaning up KUBSAN reports from the kernel (the subset enabled on
>>>> syzbot at least).
>>>> What exactly cases should KUBSAN ignore?
>>>> +linux-hardening/kasan-dev for KUBSAN false positive
>>>
>>> Can check_shl_overflow() be used at all? Best to just make things
>>> readable and compiler-happy, whatever the implementation. :)
>>
>> This is not a compile issue. If the shift amount is a constant,
>> compiler should have warned and user should fix the warning.
>>
>> This is because user code has
>> something like
>>       a << s;
>> where s is a unknown variable and
>> verifier just marked the result of a << s as unknown value.
>> Verifier may not reject the code depending on how a << s result
>> is used.
>>
>> If bpf program writer uses check_shl_overflow() or some kind
>> of checking for shift value and won't do shifting if the
>> shifting may cause an undefined result, there should not
>> be any kubsan warning.
> 
> I guess the main question: what should happen if a bpf program writer
> does _not_ use compiler nor check_shl_overflow()?

If kubsan is not enabled, everything should work as expected even with
shl overflow may cause undefined result.

if kubsan is enabled, the reported shift-out-of-bounds warning
should be ignored. You could disasm the insn to ensure that
there indeed exists a potential shl overflow.


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

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

[Kees Cook]

On Wed, Jun 09, 2021 at 11:06:31PM -0700, Yonghong Song wrote:
> 
> 
> On 6/9/21 10:32 PM, Dmitry Vyukov wrote:
> > On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote:
> > > On 6/9/21 11:20 AM, Kees Cook wrote:
> > > > On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:
> > > > > On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
> > > > > <alexei.starovoitov@gmail.com> wrote:
> > > > > > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote:
> > > > > > > On 6/5/21 8:01 AM, Kurt Manucredo wrote:
> > > > > > > > Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> > > > > > > > kernel/bpf/core.c:1414:2.
> > > > > > > [...]
> > > > > > > 
> > > > > > > I think this is what happens. For the above case, we simply
> > > > > > > marks the dst reg as unknown and didn't fail verification.
> > > > > > > So later on at runtime, the shift optimization will have wrong
> > > > > > > shift value (> 31/64). Please correct me if this is not right
> > > > > > > analysis. As I mentioned in the early please write detailed
> > > > > > > analysis in commit log.
> > > > > > 
> > > > > > The large shift is not wrong. It's just undefined.
> > > > > > syzbot has to ignore such cases.
> > > > > 
> > > > > Hi Alexei,
> > > > > 
> > > > > The report is produced by KUBSAN. I thought there was an agreement on
> > > > > cleaning up KUBSAN reports from the kernel (the subset enabled on
> > > > > syzbot at least).
> > > > > What exactly cases should KUBSAN ignore?
> > > > > +linux-hardening/kasan-dev for KUBSAN false positive
> > > > 
> > > > Can check_shl_overflow() be used at all? Best to just make things
> > > > readable and compiler-happy, whatever the implementation. :)
> > > 
> > > This is not a compile issue. If the shift amount is a constant,
> > > compiler should have warned and user should fix the warning.
> > > 
> > > This is because user code has
> > > something like
> > >       a << s;
> > > where s is a unknown variable and
> > > verifier just marked the result of a << s as unknown value.
> > > Verifier may not reject the code depending on how a << s result
> > > is used.

Ah, gotcha: it's the BPF code itself that needs to catch it.

> > > If bpf program writer uses check_shl_overflow() or some kind
> > > of checking for shift value and won't do shifting if the
> > > shifting may cause an undefined result, there should not
> > > be any kubsan warning.

Right.

> > I guess the main question: what should happen if a bpf program writer
> > does _not_ use compiler nor check_shl_overflow()?

I think the BPF runtime needs to make such actions defined, instead of
doing a blind shift. It needs to check the size of the shift explicitly
when handling the shift instruction.

> If kubsan is not enabled, everything should work as expected even with
> shl overflow may cause undefined result.
> 
> if kubsan is enabled, the reported shift-out-of-bounds warning
> should be ignored. You could disasm the insn to ensure that
> there indeed exists a potential shl overflow.

Sure, but the point of UBSAN is to find and alert about undefined
behavior, so we still need to fix this.


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

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

[Alexei Starovoitov]

On Thu, Jun 10, 2021 at 10:06 AM Kees Cook <keescook@chromium.org> wrote:
>
> > > I guess the main question: what should happen if a bpf program writer
> > > does _not_ use compiler nor check_shl_overflow()?
>
> I think the BPF runtime needs to make such actions defined, instead of
> doing a blind shift. It needs to check the size of the shift explicitly
> when handling the shift instruction.

Such ideas were brought up in the past and rejected.
We're not going to sacrifice performance to make behavior a bit more
'defined'. CPUs are doing it deterministically. It's the C standard
that needs fixing.

> Sure, but the point of UBSAN is to find and alert about undefined
> behavior, so we still need to fix this.

No. The undefined behavior of C standard doesn't need "fixing" most of the time.
_______________________________________________
Linux-kernel-mentees mailing list
Linux-kernel-mentees@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees

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

[Eric Biggers]

On Thu, Jun 10, 2021 at 10:52:37AM -0700, Alexei Starovoitov wrote:
> On Thu, Jun 10, 2021 at 10:06 AM Kees Cook <keescook@chromium.org> wrote:
> >
> > > > I guess the main question: what should happen if a bpf program writer
> > > > does _not_ use compiler nor check_shl_overflow()?
> >
> > I think the BPF runtime needs to make such actions defined, instead of
> > doing a blind shift. It needs to check the size of the shift explicitly
> > when handling the shift instruction.
> 
> Such ideas were brought up in the past and rejected.
> We're not going to sacrifice performance to make behavior a bit more
> 'defined'. CPUs are doing it deterministically.

What CPUs do is not the whole story.  The compiler can assume that the shift
amount is less than the width and use that assumption in other places, resulting
in other things being miscompiled.

Couldn't you just AND the shift amounts with the width minus 1?  That would make
the shifts defined, and the compiler would optimize out the AND on any CPU that
interprets the shift amounts modulo the width anyway (e.g., x86).

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