linux-kernel - Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Sat, 5 Jun 2021 14:39:57 -0700
From:   Yonghong Song <yhs@...com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>
CC:     Kurt Manucredo <fuzzybritches0@...il.com>,
        <syzbot+bed360704c521841c85d@...kaller.appspotmail.com>,
        Andrii Nakryiko <andrii@...nel.org>,
        Alexei Starovoitov <ast@...nel.org>, bpf <bpf@...r.kernel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        "David S. Miller" <davem@...emloft.net>,
        Jesper Dangaard Brouer <hawk@...nel.org>,
        John Fastabend <john.fastabend@...il.com>,
        Martin KaFai Lau <kafai@...com>,
        KP Singh <kpsingh@...nel.org>,
        Jakub Kicinski <kuba@...nel.org>,
        LKML <linux-kernel@...r.kernel.org>,
        Network Development <netdev@...r.kernel.org>,
        Song Liu <songliubraving@...com>,
        syzkaller-bugs <syzkaller-bugs@...glegroups.com>,
        <nathan@...nel.org>, Nick Desaulniers <ndesaulniers@...gle.com>,
        Clang-Built-Linux ML <clang-built-linux@...glegroups.com>,
        <linux-kernel-mentees@...ts.linuxfoundation.org>,
        Shuah Khan <skhan@...uxfoundation.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Subject: Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run



On 6/5/21 12:10 PM, Alexei Starovoitov wrote:
> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@...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@...kaller.appspotmail.com
>>> Signed-off-by: Kurt Manucredo <fuzzybritches0@...il.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.