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

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

[Dmitry Vyukov]

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

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

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

[Yonghong Song]

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.

> 

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

[Dmitry Vyukov]

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()?

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

[Yonghong Song]

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.

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

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.

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

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

The shift-out-of-bounds happens when we have BPF_X. This means we have
to go the same way we go when we want to avoid a divide-by-zero. We do
it in do_misc_fixups().

When we have BPF_K we find divide-by-zero and shift-out-of-bounds guards
next each other in check_alu_op(). It seems only logical to me that the
same should be true for BPF_X in do_misc_fixups() since it is there where
I found the divide-by-zero guard. Or is there a reason I'm not aware of,
that dictates that the checks should be in adjust_scalar_min_max_vals(),
as they are now?

This patch was tested by syzbot.

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:
----------
v5 - Fix shift-out-of-bounds in do_misc_fixups().
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 | 53 +++++++++++++++++++++++++------------------
 1 file changed, 31 insertions(+), 22 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..83c7c1ccaf26 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7496,7 +7496,6 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	u64 umin_val, umax_val;
 	s32 s32_min_val, s32_max_val;
 	u32 u32_min_val, u32_max_val;
-	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	int ret;
 
@@ -7592,39 +7591,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
@@ -12353,6 +12331,37 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
 			continue;
 		}
 
+		/* Make shift-out-of-bounds exceptions impossible. */
+		if (insn->code == (BPF_ALU64 | BPF_LSH | BPF_X) ||
+		    insn->code == (BPF_ALU64 | BPF_RSH | BPF_X) ||
+		    insn->code == (BPF_ALU64 | BPF_ARSH | BPF_X) ||
+		    insn->code == (BPF_ALU | BPF_LSH | BPF_X) ||
+		    insn->code == (BPF_ALU | BPF_RSH | BPF_X) ||
+		    insn->code == (BPF_ALU | BPF_ARSH | BPF_X)) {
+			bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
+			u8 insn_bitness = is64 ? 64 : 32;
+			struct bpf_insn chk_and_shift[] = {
+				/* [R,W]x shift >= 32||64 -> 0 */
+				BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
+					     BPF_JLT | BPF_K, insn->src_reg,
+					     insn_bitness, 2, 0),
+				BPF_ALU32_REG(BPF_XOR, insn->dst_reg, insn->dst_reg),
+				BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+				*insn,
+			};
+
+			cnt = ARRAY_SIZE(chk_and_shift);
+
+			new_prog = bpf_patch_insn_data(env, i + delta, chk_and_shift, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			continue;
+		}
+
 		/* Implement LD_ABS and LD_IND with a rewrite, if supported by the program type. */
 		if (BPF_CLASS(insn->code) == BPF_LD &&
 		    (BPF_MODE(insn->code) == BPF_ABS ||
-- 
2.30.2

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

[Edward Cree]

On 15/06/2021 17:42, Kurt Manucredo wrote:
> Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()
> kernel/bpf/core.c:1414:2.
> 
> The shift-out-of-bounds happens when we have BPF_X. This means we have
> to go the same way we go when we want to avoid a divide-by-zero. We do
> it in do_misc_fixups().

Shifts by more than insn_bitness are legal in the eBPF ISA; they are
 implementation-defined behaviour, rather than UB, and have been made
 legal for performance reasons.  Each of the JIT backends compiles the
 eBPF shift operations to machine instructions which produce
 implementation-defined results in such a case; the resulting contents
 of the register may be arbitrary but program behaviour as a whole
 remains defined.
Guard checks in the fast path (i.e. affecting JITted code) will thus
 not be accepted.
The case of division by zero is not truly analogous, as division
 instructions on many of the JIT-targeted architectures will raise a
 machine exception / fault on division by zero, whereas (to the best of
 my knowledge) none will do so on an out-of-bounds shift.
(That said, it would be possible to record from the verifier division
 instructions in the program which are known never to be passed zero as
 divisor, and eliding the fixup patch in those cases.  However, the
 extra complexity may not be worthwhile.)

As I understand it, the UBSAN report is coming from the eBPF interpreter,
 which is the *slow path* and indeed on many production systems is
 compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
 to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
 bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

-ed

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

[Eric Biggers]

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
> 
> As I understand it, the UBSAN report is coming from the eBPF interpreter,
>  which is the *slow path* and indeed on many production systems is
>  compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
> Perhaps a better approach to the fix would be to change the interpreter
>  to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
>  bitnesses), thus matching the behaviour of most chips' shift opcodes.
> This would shut up UBSAN, without affecting JIT code generation.
> 

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
get optimized out when compiling for most CPUs.

- Eric

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

[Daniel Borkmann]

On 6/15/21 9:33 PM, Eric Biggers wrote:
> On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
>>
>> As I understand it, the UBSAN report is coming from the eBPF interpreter,
>>   which is the *slow path* and indeed on many production systems is
>>   compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
>> Perhaps a better approach to the fix would be to change the interpreter
>>   to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
>>   bitnesses), thus matching the behaviour of most chips' shift opcodes.
>> This would shut up UBSAN, without affecting JIT code generation.
> 
> Yes, I suggested that last week
> (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
> get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same
before/after with that?

How does UBSAN detect this in general? I would assume generated code for
interpreter wrt DST = DST << SRC would not really change as otherwise all
valid cases would be broken as well, given compiler has not really room
to optimize or make any assumptions here, in other words, it's only
propagating potential quirks under such cases from underlying arch.

Thanks,
Daniel

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

[Eric Biggers]

On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:
> On 6/15/21 9:33 PM, Eric Biggers wrote:
> > On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
> > > 
> > > As I understand it, the UBSAN report is coming from the eBPF interpreter,
> > >   which is the *slow path* and indeed on many production systems is
> > >   compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
> > > Perhaps a better approach to the fix would be to change the interpreter
> > >   to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
> > >   bitnesses), thus matching the behaviour of most chips' shift opcodes.
> > > This would shut up UBSAN, without affecting JIT code generation.
> > 
> > Yes, I suggested that last week
> > (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
> > get optimized out when compiling for most CPUs.
> 
> Did you check if the generated interpreter code for e.g. x86 is the same
> before/after with that?

Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same
both before and after (with UBSAN disabled).  Here is the patch I used:

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..996db8a1bbfb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
 		DST = (u32) DST OP (u32) IMM;	\
 		CONT;
 
+	/*
+	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
+	 * behavior.  Normally this won't affect the generated code.
+	 */
+#define ALU_SHIFT(OPCODE, OP)		\
+	ALU64_##OPCODE##_X:		\
+		DST = DST OP (SRC & 63);\
+		CONT;			\
+	ALU_##OPCODE##_X:		\
+		DST = (u32) DST OP ((u32)SRC & 31);	\
+		CONT;			\
+	ALU64_##OPCODE##_K:		\
+		DST = DST OP (IMM & 63);	\
+		CONT;			\
+	ALU_##OPCODE##_K:		\
+		DST = (u32) DST OP ((u32)IMM & 31);	\
+		CONT;
+
 	ALU(ADD,  +)
 	ALU(SUB,  -)
 	ALU(AND,  &)
 	ALU(OR,   |)
-	ALU(LSH, <<)
-	ALU(RSH, >>)
+	ALU_SHIFT(LSH, <<)
+	ALU_SHIFT(RSH, >>)
 	ALU(XOR,  ^)
 	ALU(MUL,  *)
 #undef ALU

> 
> How does UBSAN detect this in general? I would assume generated code for
> interpreter wrt DST = DST << SRC would not really change as otherwise all
> valid cases would be broken as well, given compiler has not really room
> to optimize or make any assumptions here, in other words, it's only
> propagating potential quirks under such cases from underlying arch.

UBSAN inserts code that checks that shift amounts are in range.

In theory there are cases where the undefined behavior of out-of-range shift
amounts could cause problems.  For example, a compiler could make the following
function always return true, as it can assume that 'b' is in the range [0, 31].

	bool foo(int a, int b, int *c)
	{
		*c = a << b;
		return b < 32;
	}

- Eric

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

[Eric Biggers]

On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:
> On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:
> > On 6/15/21 9:33 PM, Eric Biggers wrote:
> > > On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
> > > > 
> > > > As I understand it, the UBSAN report is coming from the eBPF interpreter,
> > > >   which is the *slow path* and indeed on many production systems is
> > > >   compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
> > > > Perhaps a better approach to the fix would be to change the interpreter
> > > >   to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
> > > >   bitnesses), thus matching the behaviour of most chips' shift opcodes.
> > > > This would shut up UBSAN, without affecting JIT code generation.
> > > 
> > > Yes, I suggested that last week
> > > (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
> > > get optimized out when compiling for most CPUs.
> > 
> > Did you check if the generated interpreter code for e.g. x86 is the same
> > before/after with that?
> 
> Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same
> both before and after (with UBSAN disabled).  Here is the patch I used:
> 
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index 5e31ee9f7512..996db8a1bbfb 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
>  		DST = (u32) DST OP (u32) IMM;	\
>  		CONT;
>  
> +	/*
> +	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
> +	 * behavior.  Normally this won't affect the generated code.
> +	 */
> +#define ALU_SHIFT(OPCODE, OP)		\
> +	ALU64_##OPCODE##_X:		\
> +		DST = DST OP (SRC & 63);\
> +		CONT;			\
> +	ALU_##OPCODE##_X:		\
> +		DST = (u32) DST OP ((u32)SRC & 31);	\
> +		CONT;			\
> +	ALU64_##OPCODE##_K:		\
> +		DST = DST OP (IMM & 63);	\
> +		CONT;			\
> +	ALU_##OPCODE##_K:		\
> +		DST = (u32) DST OP ((u32)IMM & 31);	\
> +		CONT;
> +
>  	ALU(ADD,  +)
>  	ALU(SUB,  -)
>  	ALU(AND,  &)
>  	ALU(OR,   |)
> -	ALU(LSH, <<)
> -	ALU(RSH, >>)
> +	ALU_SHIFT(LSH, <<)
> +	ALU_SHIFT(RSH, >>)
>  	ALU(XOR,  ^)
>  	ALU(MUL,  *)
>  #undef ALU
> 

Note, I missed the arithmetic right shifts later on in the function.  Same
result there, though.

- Eric

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

[Daniel Borkmann]

On 6/15/21 11:38 PM, Eric Biggers wrote:
> On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:
>> On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:
>>> On 6/15/21 9:33 PM, Eric Biggers wrote:
>>>> On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
>>>>>
>>>>> As I understand it, the UBSAN report is coming from the eBPF interpreter,
>>>>>    which is the *slow path* and indeed on many production systems is
>>>>>    compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
>>>>> Perhaps a better approach to the fix would be to change the interpreter
>>>>>    to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
>>>>>    bitnesses), thus matching the behaviour of most chips' shift opcodes.
>>>>> This would shut up UBSAN, without affecting JIT code generation.
>>>>
>>>> Yes, I suggested that last week
>>>> (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
>>>> get optimized out when compiling for most CPUs.
>>>
>>> Did you check if the generated interpreter code for e.g. x86 is the same
>>> before/after with that?
>>
>> Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same
>> both before and after (with UBSAN disabled).  Here is the patch I used:
>>
>> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
>> index 5e31ee9f7512..996db8a1bbfb 100644
>> --- a/kernel/bpf/core.c
>> +++ b/kernel/bpf/core.c
>> @@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
>>   		DST = (u32) DST OP (u32) IMM;	\
>>   		CONT;
>>   
>> +	/*
>> +	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
>> +	 * behavior.  Normally this won't affect the generated code.

The last one should probably be more specific in terms of 'normally', e.g. that
it is expected that the compiler is optimizing this away for archs like x86. Is
arm64 also covered by this ... do you happen to know on which archs this won't
be the case?

Additionally, I think such comment should probably be more clear in that it also
needs to give proper guidance to JIT authors that look at the interpreter code to
see what they need to implement, in other words, that they don't end up copying
an explicit AND instruction emission if not needed there.

>> +	 */
>> +#define ALU_SHIFT(OPCODE, OP)		\
>> +	ALU64_##OPCODE##_X:		\
>> +		DST = DST OP (SRC & 63);\
>> +		CONT;			\
>> +	ALU_##OPCODE##_X:		\
>> +		DST = (u32) DST OP ((u32)SRC & 31);	\
>> +		CONT;			\
>> +	ALU64_##OPCODE##_K:		\
>> +		DST = DST OP (IMM & 63);	\
>> +		CONT;			\
>> +	ALU_##OPCODE##_K:		\
>> +		DST = (u32) DST OP ((u32)IMM & 31);	\
>> +		CONT;

For the *_K cases these are explicitly rejected by the verifier already. Is this
required here nevertheless to suppress UBSAN false positive?

>>   	ALU(ADD,  +)
>>   	ALU(SUB,  -)
>>   	ALU(AND,  &)
>>   	ALU(OR,   |)
>> -	ALU(LSH, <<)
>> -	ALU(RSH, >>)
>> +	ALU_SHIFT(LSH, <<)
>> +	ALU_SHIFT(RSH, >>)
>>   	ALU(XOR,  ^)
>>   	ALU(MUL,  *)
>>   #undef ALU
> 
> Note, I missed the arithmetic right shifts later on in the function.  Same
> result there, though.
> 
> - Eric
> 

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

[Eric Biggers]

On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote:
> On 6/15/21 11:38 PM, Eric Biggers wrote:
> > On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:
> > > On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:
> > > > On 6/15/21 9:33 PM, Eric Biggers wrote:
> > > > > On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
> > > > > > 
> > > > > > As I understand it, the UBSAN report is coming from the eBPF interpreter,
> > > > > >    which is the *slow path* and indeed on many production systems is
> > > > > >    compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
> > > > > > Perhaps a better approach to the fix would be to change the interpreter
> > > > > >    to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
> > > > > >    bitnesses), thus matching the behaviour of most chips' shift opcodes.
> > > > > > This would shut up UBSAN, without affecting JIT code generation.
> > > > > 
> > > > > Yes, I suggested that last week
> > > > > (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
> > > > > get optimized out when compiling for most CPUs.
> > > > 
> > > > Did you check if the generated interpreter code for e.g. x86 is the same
> > > > before/after with that?
> > > 
> > > Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same
> > > both before and after (with UBSAN disabled).  Here is the patch I used:
> > > 
> > > diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> > > index 5e31ee9f7512..996db8a1bbfb 100644
> > > --- a/kernel/bpf/core.c
> > > +++ b/kernel/bpf/core.c
> > > @@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
> > >   		DST = (u32) DST OP (u32) IMM;	\
> > >   		CONT;
> > > +	/*
> > > +	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
> > > +	 * behavior.  Normally this won't affect the generated code.
> 
> The last one should probably be more specific in terms of 'normally', e.g. that
> it is expected that the compiler is optimizing this away for archs like x86. Is
> arm64 also covered by this ... do you happen to know on which archs this won't
> be the case?
> 
> Additionally, I think such comment should probably be more clear in that it also
> needs to give proper guidance to JIT authors that look at the interpreter code to
> see what they need to implement, in other words, that they don't end up copying
> an explicit AND instruction emission if not needed there.

Same result on arm64 with gcc 10.2.0.

On arm32 it is different, probably because the 64-bit shifts aren't native in
that case.  I don't know about other architectures.  But there aren't many ways
to implement shifts, and using just the low bits of the shift amount is the most
logical way.

Please feel free to send out a patch with whatever comment you want.  The diff I
gave was just an example and I am not an expert in BPF.

> 
> > > +	 */
> > > +#define ALU_SHIFT(OPCODE, OP)		\
> > > +	ALU64_##OPCODE##_X:		\
> > > +		DST = DST OP (SRC & 63);\
> > > +		CONT;			\
> > > +	ALU_##OPCODE##_X:		\
> > > +		DST = (u32) DST OP ((u32)SRC & 31);	\
> > > +		CONT;			\
> > > +	ALU64_##OPCODE##_K:		\
> > > +		DST = DST OP (IMM & 63);	\
> > > +		CONT;			\
> > > +	ALU_##OPCODE##_K:		\
> > > +		DST = (u32) DST OP ((u32)IMM & 31);	\
> > > +		CONT;
> 
> For the *_K cases these are explicitly rejected by the verifier already. Is this
> required here nevertheless to suppress UBSAN false positive?
> 

No, I just didn't know that these constants are never out of range.  Please feel
free to send out a patch that does this properly.

- Eric

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

[Kurt Manucredo]

On Tue, 15 Jun 2021 15:07:43 -0700, Eric Biggers <ebiggers@kernel.org> wrote:
> 
> On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote:
> > On 6/15/21 11:38 PM, Eric Biggers wrote:
> > > On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:
> > > > On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:
> > > > > On 6/15/21 9:33 PM, Eric Biggers wrote:
> > > > > > On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
> > > > > > > 
> > > > > > > As I understand it, the UBSAN report is coming from the eBPF interpreter,
> > > > > > >    which is the *slow path* and indeed on many production systems is
> > > > > > >    compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
> > > > > > > Perhaps a better approach to the fix would be to change the interpreter
> > > > > > >    to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
> > > > > > >    bitnesses), thus matching the behaviour of most chips' shift opcodes.
> > > > > > > This would shut up UBSAN, without affecting JIT code generation.
> > > > > > 
> > > > > > Yes, I suggested that last week
> > > > > > (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
> > > > > > get optimized out when compiling for most CPUs.
> > > > > 
> > > > > Did you check if the generated interpreter code for e.g. x86 is the same
> > > > > before/after with that?
> > > > 
> > > > Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same
> > > > both before and after (with UBSAN disabled).  Here is the patch I used:
> > > > 
> > > > diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> > > > index 5e31ee9f7512..996db8a1bbfb 100644
> > > > --- a/kernel/bpf/core.c
> > > > +++ b/kernel/bpf/core.c
> > > > @@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
> > > >   		DST = (u32) DST OP (u32) IMM;	> > >   		CONT;
> > > > +	/*
> > > > +	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
> > > > +	 * behavior.  Normally this won't affect the generated code.
> > 
> > The last one should probably be more specific in terms of 'normally', e.g. that
> > it is expected that the compiler is optimizing this away for archs like x86. Is
> > arm64 also covered by this ... do you happen to know on which archs this won't
> > be the case?
> > 
> > Additionally, I think such comment should probably be more clear in that it also
> > needs to give proper guidance to JIT authors that look at the interpreter code to
> > see what they need to implement, in other words, that they don't end up copying
> > an explicit AND instruction emission if not needed there.
> 
> Same result on arm64 with gcc 10.2.0.
> 
> On arm32 it is different, probably because the 64-bit shifts aren't native in
> that case.  I don't know about other architectures.  But there aren't many ways
> to implement shifts, and using just the low bits of the shift amount is the most
> logical way.
> 
> Please feel free to send out a patch with whatever comment you want.  The diff I
> gave was just an example and I am not an expert in BPF.
> 
> > 
> > > > +	 */
> > > > +#define ALU_SHIFT(OPCODE, OP)		> > > +	ALU64_##OPCODE##_X:		> > > +		DST = DST OP (SRC & 63);> > > +		CONT;			> > > +	ALU_##OPCODE##_X:		> > > +		DST = (u32) DST OP ((u32)SRC & 31);	> > > +		CONT;			> > > +	ALU64_##OPCODE##_K:		> > > +		DST = DST OP (IMM & 63);	> > > +		CONT;			> > > +	ALU_##OPCODE##_K:		> > > +		DST = (u32) DST OP ((u32)IMM & 31);	> > > +		CONT;
> > 
> > For the *_K cases these are explicitly rejected by the verifier already. Is this
> > required here nevertheless to suppress UBSAN false positive?
> > 
> 
> No, I just didn't know that these constants are never out of range.  Please feel
> free to send out a patch that does this properly.
> 
The shift-out-of-bounds on syzbot happens in ALU_##OPCODE##_X only. To
pass the syzbot test, only ALU_##OPCODE##_X needs to be guarded.

This old patch I tested on syzbot puts a check in all four.
https://syzkaller.appspot.com/text?tag=Patch&x=11f8cacbd00000

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

thanks,

kind regards

Kurt Manucredo

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

[Daniel Borkmann]

On 6/16/21 12:07 AM, Eric Biggers wrote:
> On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote:
>> On 6/15/21 11:38 PM, Eric Biggers wrote:
>>> On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:
>>>> On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:
>>>>> On 6/15/21 9:33 PM, Eric Biggers wrote:
>>>>>> On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:
>>>>>>>
>>>>>>> As I understand it, the UBSAN report is coming from the eBPF interpreter,
>>>>>>>     which is the *slow path* and indeed on many production systems is
>>>>>>>     compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
>>>>>>> Perhaps a better approach to the fix would be to change the interpreter
>>>>>>>     to compute "DST = DST << (SRC & 63);" (and similar for other shifts and
>>>>>>>     bitnesses), thus matching the behaviour of most chips' shift opcodes.
>>>>>>> This would shut up UBSAN, without affecting JIT code generation.
>>>>>>
>>>>>> Yes, I suggested that last week
>>>>>> (https://lkml.kernel.org/netdev/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
>>>>>> get optimized out when compiling for most CPUs.
>>>>>
>>>>> Did you check if the generated interpreter code for e.g. x86 is the same
>>>>> before/after with that?
>>>>
>>>> Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same
>>>> both before and after (with UBSAN disabled).  Here is the patch I used:
>>>>
>>>> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
>>>> index 5e31ee9f7512..996db8a1bbfb 100644
>>>> --- a/kernel/bpf/core.c
>>>> +++ b/kernel/bpf/core.c
>>>> @@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
>>>>    		DST = (u32) DST OP (u32) IMM;	\
>>>>    		CONT;
>>>> +	/*
>>>> +	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
>>>> +	 * behavior.  Normally this won't affect the generated code.
>>
>> The last one should probably be more specific in terms of 'normally', e.g. that
>> it is expected that the compiler is optimizing this away for archs like x86. Is
>> arm64 also covered by this ... do you happen to know on which archs this won't
>> be the case?
>>
>> Additionally, I think such comment should probably be more clear in that it also
>> needs to give proper guidance to JIT authors that look at the interpreter code to
>> see what they need to implement, in other words, that they don't end up copying
>> an explicit AND instruction emission if not needed there.
> 
> Same result on arm64 with gcc 10.2.0.
> 
> On arm32 it is different, probably because the 64-bit shifts aren't native in
> that case.  I don't know about other architectures.  But there aren't many ways
> to implement shifts, and using just the low bits of the shift amount is the most
> logical way.
> 
> Please feel free to send out a patch with whatever comment you want.  The diff I
> gave was just an example and I am not an expert in BPF.
> 
>>
>>>> +	 */
>>>> +#define ALU_SHIFT(OPCODE, OP)		\
>>>> +	ALU64_##OPCODE##_X:		\
>>>> +		DST = DST OP (SRC & 63);\
>>>> +		CONT;			\
>>>> +	ALU_##OPCODE##_X:		\
>>>> +		DST = (u32) DST OP ((u32)SRC & 31);	\
>>>> +		CONT;			\
>>>> +	ALU64_##OPCODE##_K:		\
>>>> +		DST = DST OP (IMM & 63);	\
>>>> +		CONT;			\
>>>> +	ALU_##OPCODE##_K:		\
>>>> +		DST = (u32) DST OP ((u32)IMM & 31);	\
>>>> +		CONT;
>>
>> For the *_K cases these are explicitly rejected by the verifier already. Is this
>> required here nevertheless to suppress UBSAN false positive?
> 
> No, I just didn't know that these constants are never out of range.  Please feel
> free to send out a patch that does this properly.

Summarized and fixed via:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=28131e9d933339a92f78e7ab6429f4aaaa07061c

Thanks everyone,
Daniel